A New Class of Collision Attacks and its Application to DES

K. Schramm, Thomas Wollinger, Chris­tof Paar

In proceedings of Fast Software Encryption 2003 (FSE), pp. 217-230, Lund, Sweden, February 24-26, 2003.


Until now in cryptography the term collision was mainly associated with the surjective mapping of di erent inputs to an equal output of a hash function. Previous collision attacks were only able to detect collisions at the output of a particular function. In this publication we introduce a new class of attacks which originates from Hans Dobbertin and is based on the fact that side channel analysis can be used to detect internal collisions. We applied our attack against the widely used Data Encryption Standard (DES). We exploit the fact that internal collisions can be caused in three adjacent S-Boxes of DES [DDQ84] in order to gain information about the secret key-bits. As result, we were able to exploit an internal collision with a minimum of 140 encryptions 1 yielding 10.2 key-bits. Moreover, we successfully applied the attack to a smart card processor

[pdf] [gzipped postscript]

tags: collision attack, DES, internal collisions, power analysis, S-Boxes, side channel attacks