[53775] in cryptography@c2.net mail archive
Re: hashes on restricted domains: random functions or
daemon@ATHENA.MIT.EDU (Greg Rose)
Wed Oct 18 07:16:28 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
In-Reply-To: <d4f1333a0610171713k414561fctdba16c14559e2356@mail.gmail.com>
Date: Tue, 17 Oct 2006 21:59:55 -0700
To: "Travis H." <solinym@gmail.com>
From: Greg Rose <ggr@qualcomm.com>
Cc: Cryptography <cryptography@metzdowd.com>
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@metzdowd.com
