Advances in Cryptology

EUROCRYPT 2007
1. Auflage 2007
ISBN: 978-3-540-72540-4
Verlag: Springer-Verlag
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 605 Seiten

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

Autoren/Hrsg.

Inhaltsverzeichnis

1;Preface;6
2;Eurocrypt 2007;8
3;Table of Contents;12
4;Chosen-Prefix Collisions for MD5 andColliding X.509 Certificates for DifferentIdentities;15
5;Non-trivial Black-Box Combiners for Collision-Resistant Hash-Functions Don’t Exist;37
6;The Collision Intractability of MDC-2 in the Ideal-Cipher Model;48
7;An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries;66
8;Revisiting the Efficiency of Malicious Two-Party Computation;93
9;Efficient Two-Party Secure Computation on Committed Inputs;111
10;Universally Composable Multi-party Computation Using Tamper-Proof Hardware;129
11;Generic and Practical Resettable Zero-Knowledge in the Bare Public-Key Model;143
12;Instance-Dependent Verifiable Random Functions and Their Application to Simultaneous Resettability;162
13;Conditional Computational Entropy, or Toward Separating Pseudoentropy from Compressibility;183
14;Zero Knowledge and Soundness Are Symmetric;201
15;Mesh Signatures How to Leak a Secret with Unwitting and Unwilling Participants;224
16;The Power of Proofs-of-Possession: Securing Multiparty Signatures against Rogue-Key Attacks;242
17;Batch Verification of Short Signatures;260
18;Cryptanalysis of SFLASH with Slightly Modified Parameters;278
19;Differential Cryptanalysis of the Stream Ciphers Py, Py6 and Pypy;290
20;Secure Computation from Random Error Correcting Codes;305
21;Round-Efficient Secure Computation in Point-to-Point Networks;325
22;Atomic Secure Multi-party Multiplication with Low Communication;343
23;Cryptanalysis of the Sidelnikov Cryptosystem;361
24;Toward a Rigorous Variation of Coppersmith’s Algorithm on Three Variables;375
25;An L(1/3 + e) Algorithm for the Discrete Logarithm Problem for Low Degree Curves;393
26;General Ad Hoc Encryption from Exponent Inversion IBE;408
27;Non-interactive Proofs for Integer Multiplication;426
28;Ate Pairing on Hyperelliptic Curves;444
29;Ideal Multipartite Secret Sharing Schemes;462
30;Non-wafer-Scale Sieving Hardware for the NFS: Another Attempt to Cope with 1024-Bit;480
31;Divisible E-Cash Systems Can Be Truly Anonymous;496
32;A Fast and Key-Efficient Reduction of Chosen-Ciphertext to Known-Plaintext Security;512
33;Range Extension for Weak PRFs; The Good, the Bad, and the Ugly;531
34;Feistel Networks Made Public, and Applications;548
35;Oblivious-Transfer Amplification;569
36;Simulatable Adaptive Oblivious Transfer;587
37;Author Index;605

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.