> I don't even think anyone has analyzed the entropy preservation of a >
theoretically perfect "random oracle"
Well, I know this particular point wasn't central to your email, but
I'm not sure I agree with you on this small point. I believe it should
be more or less straightforward to analyze the entropy preservation of
a random oracle (alas, so straightforward you probably won't find any
paper on it in the literature).
The problem can really be divided into two parts:
1. Is our entropy crunching algorithm secure when used with
a random oracle instead of SHA1?
2. Does SHA1 behave enough like a random oracle that the answer
to question 1. is in any way relevant to the real world?
I suspect that question 1. is not hard to answer in a formal, rigorous,
provable way. It is only question 2. that is hard to answer. It is
absolutely true that we have no proof for question 2.
That said, we should keep in mind that none of our cryptographic
algorithms (even 3DES) come with a proof of security. All we have to
rest on is years of unsuccessful cryptanalysis. This is true for 3DES,
and this is true for SHA1 (albeit less so than for DES). Our faith
in SHA1 is based on the fact that years of analysis have found no
significant evidence that SHA1 doesn't behave like a random oracle,
and the hope that no new cryptanalytic breakthrough will be found.
We can also question the random oracle model. The random oracle model
has problems. However, for entropy generation, it's the best thing
we've got, and (as I argued in a previous post) there are good reasons to
believe that there are fundamental barriers to sound proofs of security
in the standard computational-theoretic model.
So, yes, I agree that entropy generation has not been well-analyzed in
the literature. I agree that there are fundamental reasons to think it
will be hard to analyze in the standard model. I don't agree that there
are fundamental barriers to analyzing it in the random oracle model.
I think you're absolutely right to point out gaps in our theoretical
understanding of entropy crunching.
> The entropy of the output of a "random oracle" is independent of the
> entropy of the input,
Well, this is probably tangential again, but I'm not sure you're using
the right definition of entropy. Remember, in the random oracle model,
the bad guys also have oracle access to the hash function, just like the
good guys. (We have to assume the bad guys can compute the hash of any
message they like.) Hence, any useful definition of entropy should be
made in the context where the random oracle is known, but the entropy
inputs are unknown to the attacker.
In other words, you want something more akin to the conditional entropy.
Define random variables:
I = the entropy input,
R = the random oracle,
O = the output of the entropy crunching algorithm.
Then I claim the right measure is somehow closer to the conditional
entropy H(O | R) than to the unconditional entropy H(O). (Caveat:
I'm using language very sloppily and informally here.)
That said, "entropy" is almost always used in a very informal way, and
I'm not sure that the notion of entropy is 100% meaningful here once you
look at the details. If you want to formalize this, you instead should
ask whether a computationally-bounded adversary (with oracle access to
R) can distinguish O from a true-random source. If we followed that
formulation, I think we'd find that the security of the algorithm does
depend on the entropy of the input. I haven't worked out the details,
so maybe it's not reasonable for me to speculate like this, but I think
this project is closer to a homework problem for a graduate student than
to a open research problem.
I'd love to see a paper giving a solid theoretical analysis of these
issues. (On the other hand, if I tried to write one, I'm not sure I
could get it published...)
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
