Paper 2010/384

Practical consequences of the aberration of narrow-pipe hash designs from ideal random functions

Danilo Gligoroski and Vlastimil Klima

Abstract

In a recent note to the NIST hash-forum list, the following observation was presented: narrow-pipe hash functions differ significantly from ideal random functions H:{0,1}N{0,1}n that map bit strings from a big domain where N=n+m, mn (n=256 or n=512). Namely, for an ideal random function with a big domain space {0,1}N and a finite co-domain space Y={0,1}n, for every element yY, the probability where and (in words - the probability that elements of are ``unreachable'' is negligible). However, for the narrow-pipe hash functions, for certain values of (the values that are causing the last padded block that is processed by the compression function of these functions to have no message bits), there exists a huge non-empty subset with a volume for which it is true that for every . In this paper we extend the same finding to SHA-2 and show consequences of this abberation when narrow-pipe hash functions are employed in HMAC and in two widely used protocols: 1. The pseudo-random function defined in SSL/TLS 1.2 and 2. The Password-based Key Derivation Function No.1, i.e. PBKDF1.

Note: A typo is corrected in Lemma 3 (thanks to Ralph Wernsdorf from Rohde & Schwarz SIT GmbH)

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. none
Keywords
Hash functions
Contact author(s)
danilog @ item ntnu no
History
2010-07-31: last of 3 revisions
2010-07-07: received
See all versions
Short URL
https://ia.cr/2010/384
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/384,
      author = {Danilo Gligoroski and Vlastimil Klima},
      title = {Practical consequences of the aberration of narrow-pipe hash designs from ideal random functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2010/384},
      year = {2010},
      url = {https://eprint.iacr.org/2010/384}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.