Subject: [Cfrg] Derivation of an AES key from hash function

From: ngaga Gisse <[email-masked]>
Date: Fri, 21 Jul 2006 03:59:37 -0700 (PDT)

Dear all,
  Is there a way to prove that, a  collision resistant hash function gives a random output?.  That is,  given that you are using a collision resistant hash  function, can it be proved that the output hash result is random?
   
  Regards

---------------------------------
Talk is cheap. Use Yahoo! Messenger to make PC-to-Phone calls.  Great rates starting at 1¢/min.

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Helger Lipmaa <[email-masked]>
Date: Fri, 21 Jul 2006 15:18:30 +0300 (EEST)

No!

For example if h is a collision-resistant hf then also the next function 
is crhf: take h(x), concatenate it with 50 zeros. The result is clearly 
not random.

CRHF-s are not supposed to be random, randomness is guaranteed by 
different primitives.

Helger
PS I did not read the previous discussion...

On Fri, 21 Jul 2006, ngaga Gisse wrote:

> Dear all,
>  Is there a way to prove that, a collision resistant hash function gives 
> a random output?.  That is, given that you are using a collision 
> resistant hash function, can it be proved that the output hash result is 
> random?
>
>  Regards

---

From: Helger Lipmaa <[email-masked]>
Date: Fri, 21 Jul 2006 16:18:14 +0300 (EEST)

Again, no. There is no reason why a CRHF should have a random output. 
There is some research on the direction of finding 'randomly behaving' 
CRHF-s, but here everything depends on your applications. The sound 
approach is to use primitives in their correct place. If you want to get a 
random output, use a PRG (if you have a short random input & want to get a 
longer pseudorandom output) or a randomness extractor. There are for 
example nice deterministic randomness extractors (google it) that get as 
an input a source that is weakly random, e.g., with a high min-entropy, 
and output a shorter string that is pseudorandom/close to random. Clearly, 
all such approaches need that either the input message is weakly random or 
that you have another, short, random string.

Like I said I missed the previous discussion, so I don't have a clear 
understanding of your application.

Helger

On Fri, 21 Jul 2006, ngaga Gisse wrote:

> Thank you Helger for the comments,
>  I reformulate my question to make it clear,
>
>  Generally, is it possible to show/prove that a collision restant hash 
> function gives a random output? (Assume that there are no bits padded or 
> truncated from the hash result of the CRHF).
>
>  If Yes, what are the possible sources (papers or books)?
>
>  Regards
>
>
> Helger Lipmaa <[email-masked]> wrote:
>  No!
>
> __________________________________________________
> Do You Yahoo!?
> Tired of spam?  Yahoo! Mail has the best spam protection around
> http://mail.yahoo.com

---

From: ngaga Gisse <[email-masked]>
Date: Fri, 21 Jul 2006 06:04:30 -0700 (PDT)

Generally, is it possible to show/prove  that a collision restant hash function gives a random output? (Assume that there are  no bits padded or truncated from the hash result of  the  CRHF).

  Regards

Helger

---

From: Daniel Brown <[email-masked]>
Date: Fri, 21 Jul 2006 10:08:34 -0400

> is crhf: take h(x), concatenate it with 50 zeros. The result is clearly 

If "fully collision-resistant" is defined to mean with a strength matching 
its length (e.g., it takes 2^(L/2) work to find a collision where L is the 
length -- admittedly, this is a bit imprecise), then your padded hash 
would not be not fully collision-resistant.    If h is 160 bits long, and 
it takes 2^80 work to find a collision, so it is fully collision 
resistant.  But the padded hash is 210 bits long, and it takes 2^80 work 
to find a collision, so it is not fully collision resistant, because 2^80 
< 2^105.

I'm not aware of (or have forgotten about) a publication that decides if 
fully collision resistant implies pseudorandomness or not.  One obvious 
way to devise counterexample is to fix a single bit.  Pseudorandomness 
clearly fails, and collision resistance only decreases very slightly. 
However, if the definition of fully collision resistant is stated 
precisely, fixing the bit should cause full collision resistance to fail 
too.  A while ago, I posted an argument to the CFRG that a fully collision 
resistant hash has some pseudorandomness properties, but that argument was 
flimsy at best (or perhaps the flimsiness was in the notion of fully 
collision resistant itself, because we recognize some attacks and reject 
others, even though their work is within a factor of two.)

On the flip side, the 2^63 attacks on SHA-1 imply that it is very far from 
fully collision-resistant (informally one could take the view that it 
behaves like a fully collision resistant hash of 126 bits, extended by 
some deterministic padding to 160 bits).  Therefore any pseudorandomness 
properties of SHA-1 could not be derived from its full collision 
resistance (assuming there was such a derivation).  Since SHA-1 is often 
used in PRGs (and in the ROM), there ought to be some useful papers that 
study its pseudorandomness directly.

---

From: Helger Lipmaa <[email-masked]>
Date: Fri, 21 Jul 2006 18:40:07 +0300 (EEST)

First, please define pseudorandomness. CRHF(fixed message) is not 
pseudorandom by any meaningful definition. You must assume that message 
comes from some distribution D, and then look at the distribution of 
CRHF(D). What can you assume from this distribution?

Of course, if you look at hash families then you can get a meaningful 
result. For example, take the classical DL-based hash H_k(x,y)=g^x*h^y, 
where h=g^k. I.e., H_k(x,y)=g^{x+k y}. If you choose a random k, and y is 
not 0 then H_k(x,y) is a completely random element of the group since 
x+ky is a random exponent. You can apply elementary transformations to 
make it work even if y=0.

But it definitely does not work with a fixed hash function like SHA1. 
Moreover, k must be randomly chosen, and then I'd rather suggest to use a 
designated PRG with a short seed k. You don't need collision-resistancy, 
do you?

Helger

---

From: Daniel Brown <[email-masked]>
Date: Fri, 21 Jul 2006 12:20:09 -0400

Helger Lipmaa <[email-masked]> wrote on 07/21/2006 11:40:07 AM:

> ...
> ...

Suppose D has min-entropy at least 160 bits or higher (i.e. the maximum 
probability of any value is 2^-160).  It is natural to hope that SHA1(D) 
appears indistuinguishable from a random 160 bit string (with a given 
amount of work, say 2^160, and with a given advantage): that's what I mean 
by pseudorandom.   I recall that there's entropy-smoothing functions that 
combine a small-entropy but uniformly-distributed key with some biased 
source of larger min-entropy to obtain a comparatively large pseudorandom 
key, which is great, but it's still interesting to ask what can be done 
with min-entropy alone.  It seems plausible to me that 
full-collision-resistance could imply min-entropy-only-pseudorandomness, 
for if SHA1(D) has less than 160 bits of min-entropy, this must be caused 
by collisions (d,d') in D-outputs, i.e. SHA1(d) = SHA1(d').  Crunching the 
numbers, however, if the work needed to use this D to find one of these 
collision exceed 2^80 threshold, this idea would fall apart.