[Cfrg] Fwd: Hash-Based Key Derivation

[David Wagner <[e-mail]>]

Uri Blumenthal writes:
>David Wagner writes:
>> In the random oracle model, it is easy to prove that pre-hashing then
>> applying a PRF makes a good PRF. 
>
>What properties of hash are assumed in this proof?

Like I said, this is in the random oracle model.  The random oracle
model does not make any testable 'assumptions' about the hash.  Rather,
it replaces the concrete hash (e.g., SHA256) by a theoretical model
(the random oracle).  Roughly speaking, the model assumes that the hash
is ideal and has no bad interactions with the rest of the system -- but
this is not an 'assumption' in the usual provable-security sense.
The only way that I can identify a meaningful assumption is to assume
that the model accurately reflects reality; but that's not very helpful.

>> In other words, let
>>     F'(S,X) = F(H(S),X)
>> where F is a PRF (when its key-input is uniformly distributed) and H is
>> a random oracle.  Then F' is a PRF, even when its secret-input S is not
>> uniformly distributed, so long as S has sufficient min-entropy.
>
>Is it proven that hash function output is uniformly distributed?

Are you asking about a concrete hash function like SHA256, or a model
of the hash function (the oracle oracle)?

Yes, a random oracle is uniformly distributed.  This is proven.

No, it is not proven whether SHA256 is uniformly distributed.  Most likely
the output of SHA256 is computationally indistinguishable from uniform,
but not actually uniform in the information-theoretic sense.

>Are most cryptographers OK with modelling hash functions as random
>oracles?

The topic of the random oracle model has been well-discussed before
on several cryptography mailing lists.  But here is my view:

There is no broad agreement.  Personally, I believe the random oracle
model is a reasonable approach.  There is some possibility that real
vulnerabilities could go undetected by the random oracle model.  There has
been theoretical work pointing out examples of how this might happen,
though all the examples so far have been contrived.  I am not aware of
any case where this has ever happened in a real system.  I believe the
probability of a failure due to gaps in the random oracle model is much
lower than the probability of other kinds of failure modes, so I believe
this failure mode is so negligibly rare that it's not worth spending too
much time worrying over.  Of course, it is better to have a proof security
in the standard model, where possible, but if that isn't possible, then
the random oracle model seems to me to be a very reasonable fallback.
But that's just my personal opinion, and I know that others assess
things differently.  I feel sure that this has been discussed at great
length on CFRG before (and if it hasn't already, it will be soon).

If you're interested in learning more, I bet a search through the
archives of this list and of Perry Metzger's mailing list would yield
more useful background.

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