Welcome to the resource topic for 2010/384
Title:
Practical consequences of the aberration of narrow-pipe hash designs from ideal random functions
Authors: Danilo Gligoroski, 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.
ePrint: https://eprint.iacr.org/2010/384
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .