Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities

M.M.J. Stevens; A.K. Lenstra; B.M.M. Weger, de

doi:10.1007/978-3-540-72540-4_1

Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities

M.M.J. Stevens, A.K. Lenstra, B.M.M. Weger, de

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

129 Citations (Scopus)

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', suffixes S and S' can be constructed such that the concatenated values P||S and P'||S' 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 certificates required identical name fields. We speculate on other possibilities for abusing chosen-prefix collisions. More details than can be included here can be found on www.win.tue.nl/hashclash/ChosenPrefixCollisions/ .

Original language	English
Title of host publication	Proceedings of the 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2007) 20-24 May 2007, Barcelona, Spain
Editors	M. Naor
Place of Publication	Berlin, Germany
Publisher	Springer
Pages	1-22
ISBN (Print)	978-3-540-72539-8
DOIs	https://doi.org/10.1007/978-3-540-72540-4_1
Publication status	Published - 2007
Event	26th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2007) - Barcelona, Spain Duration: 20 May 2007 → 24 May 2007 Conference number: 26

Publication series

Name	Lecture Notes in Computer Science
Volume	4515
ISSN (Print)	0302-9743

Conference

Conference	26th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2007)
Abbreviated title	Eurocrypt 2007
Country/Territory	Spain
City	Barcelona
Period	20/05/07 → 24/05/07

Access to Document

10.1007/978-3-540-72540-4_1

Cite this

Stevens, M. M. J., Lenstra, A. K., & Weger, de, B. M. M. (2007). Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities. In M. Naor (Ed.), Proceedings of the 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2007) 20-24 May 2007, Barcelona, Spain (pp. 1-22). (Lecture Notes in Computer Science; Vol. 4515). Springer. https://doi.org/10.1007/978-3-540-72540-4_1

Stevens, M.M.J. ; Lenstra, A.K. ; Weger, de, B.M.M. / Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities. Proceedings of the 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2007) 20-24 May 2007, Barcelona, Spain. editor / M. Naor. Berlin, Germany : Springer, 2007. pp. 1-22 (Lecture Notes in Computer Science).

@inproceedings{d9574c53e6d840dbba1b1094b9c304f0,

title = "Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities",

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', suffixes S and S' can be constructed such that the concatenated values P||S and P'||S' 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 certificates required identical name fields. We speculate on other possibilities for abusing chosen-prefix collisions. More details than can be included here can be found on www.win.tue.nl/hashclash/ChosenPrefixCollisions/ .",

author = "M.M.J. Stevens and A.K. Lenstra and {Weger, de}, B.M.M.",

year = "2007",

doi = "10.1007/978-3-540-72540-4_1",

language = "English",

isbn = "978-3-540-72539-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "1--22",

editor = "M. Naor",

booktitle = "Proceedings of the 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2007) 20-24 May 2007, Barcelona, Spain",

address = "Germany",

note = "26th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2007), Eurocrypt 2007 ; Conference date: 20-05-2007 Through 24-05-2007",

}

Stevens, MMJ, Lenstra, AK & Weger, de, BMM 2007, Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities. in M Naor (ed.), Proceedings of the 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2007) 20-24 May 2007, Barcelona, Spain. Lecture Notes in Computer Science, vol. 4515, Springer, Berlin, Germany, pp. 1-22, 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2007), Barcelona, Spain, 20/05/07. https://doi.org/10.1007/978-3-540-72540-4_1

Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities. / Stevens, M.M.J.; Lenstra, A.K.; Weger, de, B.M.M.
Proceedings of the 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2007) 20-24 May 2007, Barcelona, Spain. ed. / M. Naor. Berlin, Germany: Springer, 2007. p. 1-22 (Lecture Notes in Computer Science; Vol. 4515).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities

AU - Stevens, M.M.J.

AU - Lenstra, A.K.

AU - Weger, de, B.M.M.

N1 - Conference code: 26

PY - 2007

Y1 - 2007

N2 - 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', suffixes S and S' can be constructed such that the concatenated values P||S and P'||S' 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 certificates required identical name fields. We speculate on other possibilities for abusing chosen-prefix collisions. More details than can be included here can be found on www.win.tue.nl/hashclash/ChosenPrefixCollisions/ .

AB - 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', suffixes S and S' can be constructed such that the concatenated values P||S and P'||S' 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 certificates required identical name fields. We speculate on other possibilities for abusing chosen-prefix collisions. More details than can be included here can be found on www.win.tue.nl/hashclash/ChosenPrefixCollisions/ .

U2 - 10.1007/978-3-540-72540-4_1

DO - 10.1007/978-3-540-72540-4_1

M3 - Conference contribution

SN - 978-3-540-72539-8

T3 - Lecture Notes in Computer Science

SP - 1

EP - 22

BT - Proceedings of the 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2007) 20-24 May 2007, Barcelona, Spain

A2 - Naor, M.

PB - Springer

CY - Berlin, Germany

T2 - 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2007)

Y2 - 20 May 2007 through 24 May 2007

ER -

Stevens MMJ, Lenstra AK, Weger, de BMM. Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities. In Naor M, editor, Proceedings of the 26th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2007) 20-24 May 2007, Barcelona, Spain. Berlin, Germany: Springer. 2007. p. 1-22. (Lecture Notes in Computer Science). doi: 10.1007/978-3-540-72540-4_1

Chosen-prefix collisions for MD5 and colliding X.509 certificates for different identities

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this