password strengthening: salt vs. IVs
Jon Callas
jon at callas.org
Thu Nov 1 21:28:23 EDT 2007
>> Before the bad old days of using DES, there was the old days of one-
>> way functions. These one-way functions were not hash functions, they
>> were one-way. They were in a sense related to hash functions, but
>> perhaps more directly related to redundancy checks and similar
>> polynomials.
>
> Except that those aren't one-way at all, just many-to-one, right?
> It seems to me that if the CRC poly is known than it's easy to come
> up with something with a particular CRC.
Well, real hash functions are many-to-one. Consider the set of all 33-
byte strings. Consider s', which is the set of all the 256-bit hashes
of all of those strings. It doesn't matter what hash function you
use, there will be duplicates. There must be duplicates.
The functions we used in those pre-bad-old-days included the AUTODIN-
II polynomial and the Purdy Polynomial (I had to go look it up,
because those parts of my memory were put on the free list). AUTODIN-
II had undesirable qualities, which is why things migrated to Purdy.
But based upon my quick research, Purdy seems to still be good for
its purpose, namely grinding up passwords.
The way we used Purdy had to be improved, as time went on. There was
a time in which you could bypass a password length limit by small
bits of cleverness. If you had your favorite three-character
password, and that mean old system manager set the minimum length to
6, you could bypass that by appending the string
"UUUUUUUUVVVVVVVVVVVVVVVV" (that's 8x 'U' and 16x 'V') to your three-
character password and poof it worked again. Why this worked and the
fix are left as an exercise to the reader, but I'll note that the
underlying issue is something that hash function designers still have
to make sure they solve to this day. Joux and Kelsey have written a
lot about this very same problem, the length extension attack.
>> With salt, you want the number to be unique-ish, as the whole point
>> is to stymie dictionary attacks. A counter is likely not such a great
>> idea, because of collisions,
>
> Do you mean if everyone starts at zero, the adversary could generate
> dictionaries for 0..9 etc., or something else?
I mean precisely that. If you use a counter, the dictionary low
numbers is valuable. This is one of the many problems that came up in
WEP.
>
> It seems to me that a single counter is ideal for preventing
> collisions.
>
> Randomly-generated numbers have collisions because of birthday
> paradox.
Let's suppose you selected a "full-width" prime number, and your
counter incremented (or multiplied) by that prime. That's better than
0, 1, 2, ... but only if everyone doesn't select the same prime. Thus
you get back to using the RNG. If the width of your salt is wide
enough, you don't have to worry about birthday attacks. If you have 8
bytes of salt, the chance of a single collision is .5 when you have
about 4 billion numbers selected. 4 billion is a large number if it
is the number of accounts on your mail server. If you are fortunate
enough that it is not a large number, you can either go to 16 bytes
of salt, or weasel out of the issue by observing that even with 100
billion accounts, the number of collisions is not so large that there
is a clear advantage to the attacker who precomputes a single
dictionary. (And how do they know which dictionary to compute, a
priori?) When we're talking about precomputed rainbow tables, 2^64 is
a large number.
>
> How does this design sound:
>
> Each system has a randomly-generated seed which should be unique to
> the
> computer. They may then either derive a system-specific seed from
> that,
> or use it directly. They then use CTR mode with that seed as a key to
> create a computationally-unpredictable sequence which is guaranteed to
> not repeat until it has exhaused the entire period.
>
> Aside: I have recently taken a job doing crypto for a financial
> institution. If anyone has any suggestions with respect to reading
> about this industry, or conferences to go to (I seem to recall a
> financial crypto conference of some kind), I'd greatly appreciate it.
>
Simple is good. Why not just pull enough salt off of /dev/urandom and
make a small handwave about how big "enough" needs to be? If you tell
me that, I listen, nod, and we're done. With your scheme, I have to
think before I understand. Having to think before understanding is
not a feature. I think I can see a minor flaw, but I don't want to
spend the brain power on it. The RNG is your friend.
Eight bytes of salt is almost certainly fine. If you have to worry
about single collisions, use 16 or 32 bytes of salt. In general, I
recommend using a width of salt that is the size of an underlying
block size. If you're using AES somewhere, just go with 16, because
that's the natural amount.
Jon
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com
More information about the cryptography
mailing list