hashes on restricted domains: random functions or permutations?

[Greg Rose]

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 majordomo at metzdowd.com