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 × 269 bytes of memory, the attack requires 2113 DES encryptions, and given 3 × 245 bytes of memory, the attack requires 2137 DES encryptions. We conclude with some questions raised by the analysis.
Chapter PDF
Similar content being viewed by others
References
B. Biham, A. Biryukov, N. Ferguson, L. Knudsen, B. Schneier, and A. Shamir, “Cryptanalysis of Magenta,” Second AES Candidate Conference, Mar 99.
C. Burwick, D. Coppersmith, E. D’Avignon, R. Gennaro, S. Halevi, C. Jutla, S.M. Matyas, L. O’Connor, M. Peyravian, D. Safford, and N. Zunic, “MARS — A Candidate Cipher for AES,” NIST AES Proposal, Jun 98.
E. Biham, “New Types of Cryptanalytic Attacks Using Related Keys,” Journal of Cryptology, v. 7, n. 4, 1994, pp. 229–246.
E. Biham, “Cryptanalysis of Ladder-DES,” Fast Software Encryption, Fourth International Workshop, Springer-Verlag, 1997.
J. Borst, “Weak Keys of Crypton,” Second AES Candidate Conference, rump session presentation, Mar 99.
L. Chen, J.L. Massey, G.H. Khachatrian, and M.K. Kuregian, “Nomination of SAFER+ as Candidate Algorithm for the Advanced Encryption Standard (AES),” NIST AES Proposal, Jun 98.
D. Coppersmith, “DFC Weak Keys,” Note to NIST AES Discussion Group, 10 Sep 98.
D. Coppersmith, “Re: DFC Weak Keys,” Note to NIST AES Discussion Group, 22 Oct 98.
C. D’Halluin, G. Bijnens, B. Preneel, V. Rijmen, “Equivalent keys of HPC, draft paper, 1999. Available online at: http://www.esat.kuleuven.ac.be/~cosicart/ps/VR-9900.ps.gz
H. Gilbert, M. Girault, P. Hoogvorst, F. Noilhan, T. Pornin, G. Poupard, J. Stern, and S. Vaudenay, “Decorrelated Fast Cipher: an AES Candidate,” NIST AES Proposal, Jun 98.
D. Georgoudis, D. Lerous, and B.S. Chaves, “The ‘Frog’ Encryption Algorithm,” NIST AES Proposal, Jun 98.
M.J. Jacobson and K. Huber, “The MAGENTA Block Cipher Algorithm,” NIST AES Proposal, Jun 98.
J. Kelsey, B. Schneier, and D. Wagner, “Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES,” Advances in Cryptology — CRYPTO’ 96 Proceedings, Springer-Verlag, 1996, pp. 237–251.
J. Kelsey, B. Schneier, and D. Wagner, “Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2, and TEA,” Information and Communications Security, First International Conference Proceedings, Springer-Verlag, 1997, pp. 203–207.
J. Kelsey, B. Schneier, and D. Wagner “Key Schedule Weaknesses in SAFER+,” Second AES Candidate Conference, Mar 99.
L. Knudsen, “Cryptanalysis of LOKI’ 91,” Advances in Cryptography — AUSCRYPT’ 92 Proceedings, Springer-Verlag, 1993.
L Knudsen, “DEAL — A 128-bit Block Cipher,” NIST AES Proposal, Jun 98.
C.H. Lim, “CRYPTON: A New 128-bit Block Cipher,” NIST AES Proposal, Jun 98.
M. Luby, and C. Rackoff, “How to construct pseudorandom permutations from pseudorandom functions,” SIAM Journal of Computing, 17: #2, 373–386, 1988.
S. Lucks, “On the Security of the 128-bit Block Cipher DEAL,” Fast Software Encryption, Sixth International Workshop, Springer-Verlag, 1999, to appear.
R.C. Merkle, “Fast Software Encryption Functions,” Advances in Cryptology — CRYPTO’ 90 Proceedings, Springer-Verlag, 1991, pp. 476–501.
P. Rogaway and D. Coppersmith, “A Software-Optimized Encryption Algorithm,” Journal of Cryptology, v. 11, n. 4, 1998, pp. 273–287.
T. Ritter, Ladder-DES: A Proposed Candidate to Replace DES, appeared in the Usenet newsgroup sci.crypt, Feb 1994.
R. Rivest, M. Robshaw, R. Sidney, and Y.L. Yin, “The RC6 Block Cipher,” NIST AES Proposal, Jun 98.
M. Saarinen, “A Note Regarding the Hash Function Use of MARS and RC6,” available online from http://www.jyu.fi/~mjos/, 1999.
B. Schneier, “Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish),” Fast Software Encryption, Cambridge Security Workshop Proceedings, Springer-Verlag, 1994, pp. 191–204.
R. Schroeppel “Hasty Pudding Cipher Specification,” NIST AES Proposal, Jun 98.
D. Wagner, “Equivalent keys for HPC,” Second AES Candidate Conference, rump session presentation, Mar 99.
D. Wagner, N. Ferguson, and B. Schneier, “Cryptanalysis of FROG,” Second AES Candidate Conference, Mar 99.
R.S. Winternitz, “Producing One-Way Hash Functions from DES,” Advances in Cryptology: Proceedings of Crypto 83, Plenum Press, 1984, pp. 203–207.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kelsey, J., Schneier, B. (2000). Key-Schedule Cryptanalysis of DEAL. In: Heys, H., Adams, C. (eds) Selected Areas in Cryptography. SAC 1999. Lecture Notes in Computer Science, vol 1758. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46513-8_9
Download citation
DOI: https://doi.org/10.1007/3-540-46513-8_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67185-5
Online ISBN: 978-3-540-46513-3
eBook Packages: Springer Book Archive