quisquat@prlb2.UUCP (Jac. Quisquater) (02/06/89)
We (Jean-Paul Delescaille and Jean-Jacques Quisquater) were able to find 3 collisions in DES using a network of workstations during some weeks. Definition of a collision: given a message M and an cryptographic algorithm f with 2 parameters M and K (the key), a collision is a pair (K1, K2) such that f (M, K1) = f (M, K2), that is, for a fixed message M and using a cryptographic algorithm f, the key K1 and the key K2 give the SAME encrypted message. Jean-Jacques devised a new probabilistic distributed asynchronous algorithm for finding collisions without any sorting and with a small storage (a la Pollard). We used a fast implementation of DES in C (by Jean-Paul: about 2000 * (encryption + change of key) /second/machine) We used the idle time of a network of 20 SUN-3's and 10 microVAXes (a la Lenstra and Manasse). Total: about 100 Mips during one month. 37 2 encryptions performed (about 20 potential collisions) only in software! The message M is 0404040404040404 (hexadecimal form) for the 3 collisions. Collision 1: found Fri Jan 13 23:15 GMT (birthday of Jean-Jacques! Yes, it is another birthday attack (Hi! Don Coppersmith)). cipher = F02D67223CEAF91C K1 = 4A5AA8D0BA30585A K2 = suspense! Collision 2: found Fri Jan 20 19:13 GMT cipher = E20332821871EB8F K1, K2 = suspense! Collision 3; found Fri Feb 3 03:22 GMT suspense! Conclusion: Friday is a good day for finding collisions :-) Well, there is a problem because there is no proof we effectively found such collisions. Question 1: Find a protocol for proving or for convincing you that we know K2 for collision 1 (zero-knowledge protocols are useful in this context). Question 2: Find a protocol for proving or convincing that we know K1 and K2 for collision 2 (idem). Question 3: Find a protocol for proving or convincing that we know 3 different collisions (idem). Useful information: the nice paper by Brassard, Chaum and Crepeau, ``Minimum disclosure proofs of knowledge'', 1987. The complete information will be given at EUROCRYPT '89, Houthalen, Belgium, with the restriction that the submitted abstract is accepted :-) The paper will be sent in April if you want it. Thanks are due to Paul Branquart, Frans Heymans, Michel Lacroix, Vincent Marlair, Marc Vauclair, the members of PRLB for permission and active help in the effective implementation of the distributed algorithm on their workstations. Warning: There is no implication about the security of DES used for encryption. Indeed these experiments only prove that DES is a good random mapping (a necessary property for any cryptographic algorithm). However the use of DES for protecting the integrity of files is not very easy and needs very careful studies. Jean-Jacques Quisquater,