**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} \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 co-domain 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 narrow-pipe 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
non-empty 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 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.

**Category / Keywords: **Hash functions

**Publication Info: **none

**Date: **received 7 Jul 2010, last revised 31 Jul 2010

**Contact author: **danilog at item ntnu no

**Available format(s): **PDF | BibTeX Citation

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

**Version: **20100731:095300 (All versions of this report)

**Short URL: **ia.cr/2010/384

[ Cryptology ePrint archive ]