Newsgroups: sci.crypt,alt.security From: mkwan@mullauna.cs.mu.OZ.AU (Matthew Kwan) Subject: Biham & Shamir break DES Message-ID: Keywords: DES differential cryptanalysis Organization: Computer Science, University of Melbourne, Australia Date: Wed, 15 Jan 1992 06:22:08 GMT Well, I've finally got a copy of the paper describing Biham and Shamir's new attack on DES (thanks Eli!). A quick summary - it is a chosen-plaintext attack, requiring approximately 2^47 plaintexts (yes, the rumours were correct). To save further explanation, I'll simply type in the first page verbatim. Differential Cryptanalysis of the Full 16-round DES Eli Biham Computer Science Department Technion - Israel Institute of Technology Haifa 32000, Israel Adi Shamir Dept of Applied Math and Comp Sci The Weizmann Institute of Science Rehovot 76100, Israel December 19, 1991 Abstract In this paper we develop the first known attack which is capable of breaking the full 16 round DES in less than the 2^55 complexity of exhaustive search. The data analysis phase computes the key by analyzing about 2^36 ciphertexts in 2^37 time. The 2^36 usable ciphertexts are obtained during the data collection phase from a pool of 2^47 chosen plaintexts by a simple bit repetition criteria which discards more than 99.9% of the ciphertexts as soon as they are generated. While earlier versions of differential attacks were based on huge counter arrays, the new attack can be carried out even if the analyzed ciphertexts are derived from up to 2^33 different keys due to frequent key changes during the data collection phase. The attack can be carried out incrementally with any number of available ciphertexts, and probability of success grows linearly with this number (e.g., when 2^29 usable ciphertexts are generated from a smaller pool of 2^40 plaintexts, the analysis time decreases to 2^30 and the probability of success is about 1%). I haven't studied the paper carefully, but from what I've read, it appears they've managed to overcome the signal/noise problems in the old version, and make use of a 13 round characteristic (with prob 2^-47) to break the 16 round DES. The old version had to use a 15 round attack. The paper is 10 pages long, and is available from Technion Comp Sci Dept, where it is Technical Report #708. Please don't ask me any difficult questions about it, since I retired >From cryptography last week ;-) mkwan -------------------------------------------------------------------- Matthew Kwan who is no longer associated with Centre for Computer Security Research Australian Defence Force Academy Canberra ACT 2600