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