Re: hashes on restricted domains: random functions or permutations?
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. Is that correct? What are the expected sizes of such sets? Is it worth worrying about? posts discussing other kinds of attack on 2289 ... assuming the original circumstances that 2289 is supposed to address; most of the fixes for the attacks ... in turn, negate/invalidate the original purpose/justification for 2289 http://www.garlic.com/~lynn/2003m.html#50 public key vs passwd authentication? http://www.garlic.com/~lynn/2003n.html#1 public key vs passwd authentication? http://www.garlic.com/~lynn/2003n.html#2 public key vs passwd authentication? http://www.garlic.com/~lynn/2003n.html#3 public key vs passwd authentication? http://www.garlic.com/~lynn/2005o.html#0 The Chinese MD5 attack http://www.garlic.com/~lynn/2005t.html#28 RSA SecurID product http://www.garlic.com/~lynn/2005t.html#31 Looking for Information on password systems http://www.garlic.com/~lynn/2006d.html#41 Caller ID spoofing - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: hashes on restricted domains: random functions or permutations?
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]
Re: hashes on restricted domains: random functions or permutations?
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. Is that correct? Yes. What are the expected sizes of such sets? More relevant is how many iterations it takes to get to a significantly smaller set. Is it worth worrying about? No. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: hashes on restricted domains: random functions or permutations?
On Wed, Oct 18, 2006 at 12:00:41AM -0400, Victor Duchovni wrote: Hash functions are supposed to be pseudo-random. For a 160 bit hash In an input set of 2^80 elements we should expect to find a collision... If we iterate from a random starting point we expect to enter a cycle of length ~2^79 after ~2^79 initial outputs. So the subsets on which an iterated hash acts as a right-shift are expected to be ~2^79 in length. This part is right. An intuitive (but possibly grossly wrong) leap is that there should be ~~2^80 disjoint cycles with half of the inputs outside a cycle and half inside a cycle. None of this should lead to any apparent weakness after a modest number of iterations. This had to be wrong of course, the range does not separate into disjoint loops with a single linear strand leading into the loop. There is branching before the loop and multiple entry points into the loop. This reminds me of the analysis of the space-time tradeoff for brute forcing password hashes. Don't have it in front of me, but in that work effective estimates of the branching were taken into account. -- /\ ASCII RIBBON NOTICE: If received in error, \ / CAMPAIGN Victor Duchovni please destroy and notify X AGAINST IT Security, sender. Sender does not waive / \ HTML MAILMorgan Stanley confidentiality or privilege, and use is prohibited. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
hashes on restricted domains: random functions or permutations?
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. Is that correct? What are the expected sizes of such sets? Is it worth worrying about? -- The obvious mathematical breakthrough would be the development of an easy way to factor large prime numbers.'' [sic] -- Bill Gates -- URL:http://www.subspacefield.org/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
