On 3/26/06, Phillip Susi <psusi@xxxxxxxxxx> wrote: > Phillip Hellewell wrote: > > Again I concur with Mike. Iterative hashing is a very common technique, > > and is very effective against this type of dictionary attack. If you > > hash 1000 times, then an attack that normally could check 1 million > > passwords per second would now only be able to check 1000 passwords per > > second. > > > > Without iterative hashing, as computers get faster, so would dictionary > > attacks, and then people would have to keep using longer and longer > > passwords to be as effective. Iterative hashing "levels the playing > > field" in a way. > > > > > Except that I believe you can write code to compute the nth hash in O(1) > time rather than O(n) time, so that kind of defeats the purpose, though > I'm no expert so I could be wrong. I do not believe it is possible to compute the nth hash in O(1) time, starting with no previously-computer hashes, since in order to computer the nth hash, you need input which is the n-1th hash. This takes the form: hash(n) = hash(hash(n-1)). In order to know the hash of n-1, you need to know the hash of n-2. This chains down to your original hash. This argument holds if you retaining the standard properties of hashes: that is it is non-trivial to find input which yields a given hash. -- Michael C. Thompson <mcthomps@xxxxxxxxxx> Software-Engineer, IBM LTC Security - To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
