Advances in Cryptology - EUROCRYPT 2007

This book constitutes the refereed proceedings of the 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2007, held in Barcelona, Spain in May 2007.

The 33 revised full papers presented were carefully reviewed and selected from 173 submissions. The papers address all current foundational, theoretical and research aspects of cryptology, cryptography, and cryptanalysis as well as advanced applications.

Written for: Researchers and professionals

Keywords: RSA, anonymity, authentication, biometric anthentication, computational entropy, computational number theory, cryptanalysis, cryptographic attacks, cryptographic hash functions, cryptographic protocols, cryptographic systems, cryptography, cryptology, data encryption, data security, digital signature systems, elliptic curve cryptography, hyperelliptic curves, information security

Chosen-Prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities (p.13)
Abstract.

We present a novel, automated way to find differential paths for MD5. As an application we have shown how, at an approximate expected cost of 250 calls to the MD5 compression function, for any two chosen message prefixes P and P, sufixes S and S can be constructed such that the concatenated values PS and PS collide under MD5. Although the practical attack potential of this construction of chosen-prefix collisions is limited, it is of greater concern than random collisions for MD5. To illustrate the practicality of our method, we constructed two MD5 based X.509 certificates with identical signatures but different public keys and different Distinguished Name fields, whereas our previous construction of colliding X.509 certi.cates required identical name fields. We speculate on other possibilities for abusing chosenprefix collisions. More details than can be included here can be found on www.win.tue.nl/hashclash/ChosenPrefixCollisions/.

1 Introduction

In March 2005 we showed how Xiaoyun Wang’s ability [17] to quickly construct random collisions for the MD5 hash function could be used to construct two different valid and unsuspicious X.509 certificates with identical digital signatures (see [10] and [11]). These two colliding certificates differed in their public key values only. In particular, their Distinguished Name fields containing the identities of the certificate owners were equal. This was the best we could achieve because

– Wang’s hash collision construction requires identical Intermediate Hash Values (IHVs),

– the resulting colliding values look like random strings: in an X.509 certificate the public key field is the only suitable place where such a value can unsuspiciously be hidden.

A natural and often posed question (cf. [7], [3], [1]) is if it would be possible to allow more freedom in the other fields of the certificates, at a cost lower than 264 calls to the MD5 compression function. Specifically, it has often been suggested that it would be interesting to be able to select Distinguished Name fields that are different and, preferably, chosen at will, non-random and human readable as one would expect from these fields. This can be realized if two arbitrarily chosen messages, resulting in two different IHVs, can be extended in such a way that the extended messages collide. Such collisions will be called chosen-prefix collisions.

We describe how chosen-prefix collisions for MD5 can be constructed, and show that our method is practical by constructing two MD5 based X.509 certificates with different Distinguished Name fields and identical digital signatures. The full details of the chosen-prefix collision construction and the certificates can be found in [16] and [14], respectively.