Naor Advances in Cryptology – EUROCRYPT 2007

26th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Barcelona, Spain, May 20-24, 2007, Proceedings
2007
ISBN: 978-3-540-72540-4
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 605 Seiten, eBook

Reihe: Security and Cryptology

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

Zielgruppe

Research

Autoren/Hrsg.

Naor, Moni

Inhaltsverzeichnis

Chosen-Prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities.- Non-trivial Black-Box Combiners for Collision-Resistant Hash-Functions Don’t Exist.- The Collision Intractability of MDC-2 in the Ideal-Cipher Model.- An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries.- Revisiting the Efficiency of Malicious Two-Party Computation.- Efficient Two-Party Secure Computation on Committed Inputs.- Universally Composable Multi-party Computation Using Tamper-Proof Hardware.- Generic and Practical Resettable Zero-Knowledge in the Bare Public-Key Model.- Instance-Dependent Verifiable Random Functions and Their Application to Simultaneous Resettability.- Conditional Computational Entropy, or Toward Separating Pseudoentropy from Compressibility.- Zero Knowledge and Soundness Are Symmetric.- Mesh Signatures.- The Power of Proofs-of-Possession: Securing Multiparty Signatures against Rogue-Key Attacks.- Batch Verification of Short Signatures.- Cryptanalysis of SFLASH with Slightly Modified Parameters.- Differential Cryptanalysis of the Stream Ciphers Py, Py6 and Pypy.- Secure Computation from Random Error Correcting Codes.- Round-Efficient Secure Computation in Point-to-Point Networks.- Atomic Secure Multi-party Multiplication with Low Communication.- Cryptanalysis of the Sidelnikov Cryptosystem.- Toward a Rigorous Variation of Coppersmith’s Algorithm on Three Variables.- An L (1/3?+??) Algorithm for the Discrete Logarithm Problem for Low Degree Curves.- General Ad Hoc Encryption from Exponent Inversion IBE.- Non-interactive Proofs for Integer Multiplication.- Ate Pairing on Hyperelliptic Curves.- Ideal Multipartite Secret Sharing Schemes.- Non-wafer-Scale Sieving Hardware for the NFS: Another Attempt toCope with 1024-Bit.- Divisible E-Cash Systems Can Be Truly Anonymous.- A Fast and Key-Efficient Reduction of Chosen-Ciphertext to Known-Plaintext Security.- Range Extension for Weak PRFs; The Good, the Bad, and the Ugly.- Feistel Networks Made Public, and Applications.- Oblivious-Transfer Amplification.- Simulatable Adaptive Oblivious Transfer.

Leseproben

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.