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 [EMAIL PROTECTED]
