At 11:48 AM -0400 6/1/99, Steven M. Bellovin replied to John Kelsey
<[EMAIL PROTECTED]> message:
>>
>> a. Make the passphrase hash expensive. There are lots of
>> ways to do this. Users shouldn't mind a half-second delay
>> for hashing their passphrase, but this will make dictionary
>> attacks much harder to mount.
>
>Right, though of course Moore's Law will tend to erode this over time
>if it's simply CPU-intensive. Use a scheme that lets you adjust it with time.
>For example, if you're simply iterating a hash function, store the count with
>the password, and let the adminstrator increase it for new passwords as
>needed.
It is also desirable to be able to increase the memory footprint of your
key stretcher as well its iteration count.
>>
>> b. Use a unique per-passphrase salt of at least 32 bits.
>>
>Why 32 bits? Salts are good, and often cheap, but I'm curious what your
>rationale is. Traditionally, a salt serves two purposes: to increase the
>expense (CPU and storage) of precomputing a dictionary, and to make it harder
>to find two passwords with the same salt. UNIX uses a 12-bit salt, which is
>often quite sufficient. Given a million-entry dictionary, and using your
>number of .5 seconds/guess, with no salt at all it would take ~139 hours to
>precompute the hash of all guesses. Clearly, that's too low. But 4096*139
>is ~24000 days. Granted, that process can be parallelized, but it's still
>a lot of computing -- 240 days for a hundred machines crunching.
I would argue that UNIX is an excellent object lesson for John's point. 12
bits was a bad design decision, even in the 70's. Remember for a dictionary
attack, the 24000 machine days compute only has to take place once. If we
just store the first 32 bits of each pre computation, we are talking
4*4096*10**6 = 16 gigabytes, a few DVD's, to store the complete dictionary.
(And I don't know of anyone who is doing .5 sec of key stretching.)
>
>That number is still too low for long-term safety of a password used for
>secrecy, rather than login. But it's far from clear to me that one needs
>to go to 32 bits, if that process is at all expensive. (UNIX implemented
>its salt by swapping entries in the E-box of DES. That's not a scheme that
>scales well to a bigger salt. Note, though, that it also had the advantage of
>ruling out the use of stock DES chips for password-guessing.)
The E-box argument is bogus. They could have used the first 12 bits to
scramble the E box and appended additional salt bits to the password.
Anyway, the big guys make custom chips.
Steve, how many bits of salt do you think are enough? 20? 24? In how many
applications does 8 to 12 bits of savings matter? If you are protecting a
system with a large number of users, there is a good chance at least one
password will be in the first 10,000 dictionary entries. How much will a
terabyte cost in 20 years? Why mess around?
More salt, please.
Arnold Reinhold
