# Hash function based on block cipher (and proof of security in the PRP model)

Do there exist proofs of security for primitives like hash functions (based on a block cipher) in the PRP model.

I often see proofs in the random oracle model (for hash function based on compression function) and proofs in the ideal cipher model (for hash function based on block cipher).

Are there proofs of such primitive in a real world model?

-
My impression is that security definitions of unkeyed primitives are generally problematic and that these problems lead to the use of ROM. –  CodesInChaos Sep 10 '13 at 18:03
For posterity: the constructions Dingo13 is referring to are outlined in this article. –  pg1989 Sep 10 '13 at 18:19
Thank you for your comments. –  Dingo13 Sep 11 '13 at 12:37
Very similar to a previous question of yours. Given that that a PRP (this question) is a PRF (previous question) for large enough blocks, the questions are pretty much the same. –  B-Con Sep 11 '13 at 21:28

A PRP is a keyed primitive, so proving properties of a keyed hash on top of it is often possible. Reducing the security of an unkeyed hash to a keyed primitive on the other hand is rarely possible.

For example keyed Skein (a hash) is provably a PRF if Threefish (a block-cipher) is a PRP:

PRF, MAC, and KDF. We prove that if Threefish is a tweakable PRP (pseudorandom permutation) then Skein is a PRF. It is important to understand that we are referring, in this context, to the keyed version of Skein. The PRF property is that the input-output behavior of keyed Skein should look like that of a random function to an attacker who is not given the key. This proof supports the usage of keyed Skein for key derivation (KDF). It also supports the use of keyed Skein as a MAC. This is true because any PRF is a secure MAC

-
Thank you for your answer. Is this impossible to determine quantitatively the security of a hash function ? That is, by using the advantage at breaking a prp (or a prf) ? Use a ROM or an ICM is the only solution ? –  Dingo13 Sep 11 '13 at 12:36

Let $b$ be the number of elements in the block cipher's domain. $\:$ Let $n$ be the block cipher's key size.
If $\:\frac{2^n}{b!}\:$ is negligible, then one can construct an eTCR (page 4) hash from the block cipher as follows:

If $b$ is greater than, say, $\:2\hspace{-0.05 in}\cdot\hspace{-0.04 in}n\:$,$\:$ then one can fix a subset of $n$ elements
of the block cipher's domain, and define $\hspace{.04 in}f$ to take a key as input and
output the evaluation of the block cipher with that key on those inputs.
If one used a truly random permutation instead, then that function
would have $\:\displaystyle\prod_{0\leq q< n} (b\hspace{-0.04 in}-\hspace{-0.03 in}q)\:$ possible outputs. $\;\;\;$ If $\: 4\leq n \:$ then

$$\frac{2^n}{\displaystyle\prod_{0\leq q< n} (b\hspace{-0.04 in}-\hspace{-0.03 in}q)} \; \leq \; \frac{2^n}{\displaystyle\prod_{0\leq q< n} ((2\hspace{-0.05 in}\cdot\hspace{-0.04 in}n)\hspace{-0.04 in}-\hspace{-0.03 in}n)} \; = \; \frac{2^n}{\displaystyle\prod_{0\leq q< n} n} \; = \; \frac{2^n}{n^n} \; = \; \left(\hspace{-0.04 in}\frac2{n}\hspace{-0.04 in}\right)^{\hspace{-0.04 in}n} \; \leq \; \left(\hspace{-0.04 in}\frac24\hspace{-0.04 in}\right)^{\hspace{-0.04 in}n} \; = \; \left(\hspace{-0.04 in}\frac12\hspace{-0.04 in}\right)^{\hspace{-0.04 in}n} \; = \; \frac1{2^n}$$

If one uses the construction of $\hspace{.04 in}f$ on a truly random permutation rather than the block cipher with a given key, then the probability of there existing a preimage is negligible. $\:$ By the PRP property, if one attempts to invert $\hspace{.04 in}f$ on its actual output for a randomly chosen input, the probability of success will
still be negligible. $\:$ Thus $\hspace{.04 in}f$ is one-way. $\;\;\;$ If $b$ is at most $\:2\hspace{-0.05 in}\cdot\hspace{-0.04 in}n\:$,$\:$ then one can efficiently evaluate the
block cipher on its entire domain. $\;\;\;$ In that case, one defines $g$ to take a key as input and output the evaluation of the block cipher with that key on its entire domain. $\;\;\;$ If one uses the construction of
$g$ on a truly random permutation rather than the block cipher with a given key, then the probability
of there existing a preimage is $\;\frac{2^n}{b!}\:\:$. $\;\;\;$ By assumption, $\:\frac{2^n}{b!}\:$ is negligible. $\;\;\;$ By the PRP property,
if one attempts to invert $g$ on its actual output for a randomly chosen input, the probability of
success will still be negligible. $\:$ Thus $g$ is one-way. $\:$ In either case, one gets a one-way function.

Next, by this paper, one gets a "universal one-way hash function", now known as a TCR hash.
By chaining with independent keys a number of times equal to the length of the
TCR hash's outputs, one gets a TCR hash that compresses by at least a factor of 2.
By padding the message to an appropriate length, truncating the result if that would be too long,
using one of a linear number of independent keys for each layer in a hash tree, and ignoring the rest
of those keys, one gets a TCR hash with fixed-length output that can handle arbitrary length inputs.
Finally, by making the entire key (including the parts that were previously ignored)
of such a TCR hash part of the output, one gets an eTCR hash.

-
Is there a typo in "what I've not understood in what this supplies arguments on proofs of security"? $\hspace{.4 in}$ I can't parse it. $\:$ –  Ricky Demer Sep 12 '13 at 8:35
Sorry, my comment is: Thank you for this answer. This is very interesting but what I've not understood is in what this supplies arguments on proofs of security of hash function using pseudorandom permutation, and not random permutation... –  Dingo13 Sep 12 '13 at 8:43
Should "in what" have been "how"? $\:$ I attempted to clarify my answer. $\;\;\;$ –  Ricky Demer Sep 12 '13 at 9:05