International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: How Risky is the Random-Oracle Model?

Gaëtan Leurent
Phong Q. Nguyen
Search ePrint
Search Google
Abstract: RSA-FDH and many other schemes provably secure in the Random-Oracle Model (ROM) require a cryptographic hash function whose output size does not match any of the standard hash functions. We show that the random-oracle instantiations proposed in the literature for such general cases are insecure, including the two historical instantiations proposed by Bellare and Rogaway themselves in their seminal papers from ACM~CCS~'93 and EUROCRYPT~'96: for instance, for 1024-bit digests, we present a $2^{68}$ preimage attack on BR93 and a $2^{106}$ collision attack on BR96. This leads us to study the potential security impact of such defects. While one might think that a hash collision may at worst give rise to an existential forgery on a signature scheme, we show that for several (real-world) schemes secure in the ROM, collisions or slight hash function defects can have much more dramatic consequences, namely key-recovery attacks. For instance, we point out that a hash collision discloses the master key in the Boneh-Gentry-Hamburg identity-based cryptosystem from FOCS~'07, and the secret key in the Rabin-Williams signature scheme for which Bernstein proved tight security at EUROCRYPT~'08. This problem can be fixed, but still, such schemes, as well as the Rabin-Williams variant implemented in the IEEE P1363 standard, strongly require that the hash function is immune to malleability variants of collision attacks, which does not hold for the BR93 instantiation. Our results suggest an additional criterion to compare schemes secure in the ROM: assessing the risks by carefully studying the impact of potential flaws in the random-oracle instantiation. In this light, RSA-PSS seems more robust than other RSA signatures secure in the ROM.
  title={How Risky is the Random-Oracle Model?},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / hash functions, cryptanalysis, public-key cryptography},
  note={ 14165 received 13 Oct 2008},
  author={Gaëtan Leurent and Phong Q. Nguyen},