Paper 2010/384
Practical consequences of the aberration of narrowpipe hash designs from ideal random functions
Danilo Gligoroski and Vlastimil Klima
Abstract
In a recent note to the NIST hashforum list, the following observation was presented: narrowpipe hash functions differ significantly from ideal random functions $H:\{0,1\}^{N} \rightarrow \{0,1\}^n$ that map bit strings from a big domain where $N=n+m,\ m\geq n$ ($n=256$ or $n=512$). Namely, for an ideal random function with a big domain space $\{0,1\}^{N}$ and a finite codomain space $Y=\{0,1\}^n$, for every element $y \in Y$, the probability $Pr\{H^{1}(y) = \varnothing\} \approx e^{2^{m}} \approx 0$ where $H^{1}(y) \subseteq \{0,1\}^{N}$ and $H^{1}(y) = \{x \ \ H(x)=y \}$ (in words  the probability that elements of $Y$ are ``unreachable'' is negligible). However, for the narrowpipe hash functions, for certain values of $N$ (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 nonempty subset $Y_\varnothing \subseteq Y$ with a volume $Y_\varnothing\approx e^{1}Y\approx 0.36 Y$ for which it is true that for every $y \in Y_\varnothing,\ H^{1}(y) = \varnothing$. In this paper we extend the same finding to SHA2 and show consequences of this abberation when narrowpipe hash functions are employed in HMAC and in two widely used protocols: 1. The pseudorandom function defined in SSL/TLS 1.2 and 2. The Passwordbased 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)
 Publication info
 Published elsewhere. none
 Keywords
 Hash functions
 Contact author(s)
 danilog @ item ntnu no
 History
 20100731: last of 3 revisions
 20100707: received
 See all versions
 Short URL
 https://ia.cr/2010/384
 License

CC BY
BibTeX
@misc{cryptoeprint:2010/384, author = {Danilo Gligoroski and Vlastimil Klima}, title = {Practical consequences of the aberration of narrowpipe hash designs from ideal random functions}, howpublished = {Cryptology {ePrint} Archive, Paper 2010/384}, year = {2010}, url = {https://eprint.iacr.org/2010/384} }