>> 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 metzdowd.com
|
