Key-Schedule Cryptanalysis of DEAL
Sixth Annual Workshop on Selected Areas in Cryptography, Springer Verlag, August 1999.
ABSTRACT: DEAL is a six- or eight-round Luby-Rackoff cipher that uses DES as its round function, with allowed key lengths of 128, 192, and 256 bits. In this paper, we discuss two new results on the DEAL key schedule. First, we discuss the existence of equivalent keys for all three key lengths; pairs of equivalent keys in DEAL-128 require about 264 DES encryptions to find, while equivalent keys in DEAL-192 and DEAL-256 require only six or eight DES encryptions to find. Second, we discuss a new related-key attack on DEAL-192 and DEAL-256. This attack requires 233 related key queries, the same $3$ plaintexts encrypted under each key, and may be implemented with a variety of time-memory tradeoffs; Given $3 x 269 bytes of memory, the attack requires 2113 DES encryptions, and given $3 x 245 bytes of memory, the attack requires 2137 DES encryptions. We conclude with some questions raised by the analysis.
[full text – PDF (Acrobat)] [full text – Postscript]
Categories: Algorithm Analyses