At 19:13 -0500 2006/10/17, Travis H. wrote:
So I was reading about the OTP system (based on S/Key) described in RFC 2289.
It basically hashes a secret several times (with salt to individualize
it) and stores
the value that the correct password will hash to.
Now my question is, if we restrict ourselves to, say, 160-bit inputs, is SHA-1
a permutation, or do collisions exist? If there are collisions,
then iterating
the hash could lead to fewer possible values each time, potentially converging
on a set of inputs that form a permutation and are closed under composition.
It would be unexpected and certainly very surprising if SHA-1 formed
a permutation of 160-bit inputs.
Is that correct? What are the expected sizes of such sets?
Is it worth worrying about?
Yes, it's correct. No, it's not worth worrying about. See the
Handbook of Applied Cryptography for more details, but the executive
summary is:
If you start with a particular input and repeatedly hash it (and on
the assumption that SHA-1 is an approximation of a decent PRF), you
expect to go through about 2^80 unique values before eventually
settling into a cycle of length about 2^80. There are probably a
(smallish) number of distinct such cycles. But since you'd have to
wait a very long time before this mattered, it isn't a practical
worry.
Greg.
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
