From:	CSBVAX::CSBVAX::MRGATE::"SMTP::PYRITE.RUTGERS.EDU::SECURITY" 27-FEB-1989 11:57
To:	MRGATE::"ARISIA::EVERHART"
Subj:	collision in DES


Sender: security@pyrite.rutgers.edu
Date: 5 Feb 89 10:54:41 GMT
From: jjq@prlb.philips.be (Jean-Jac. Quisquater)
Subject: collision in DES
To: misc-security@uunet.uu.net

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,

(Program chairman of EUROCRYPT '89)