At 16:38 1/06/99 -0400, it was written:
>At 11:48 AM -0400 6/1/99, Steven M. Bellovin replied to John Kelsey
><[EMAIL PROTECTED]> message:
>>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.
I take exception to this last statement. The design (of the salted
passwords) was done in the late 70s, and given the constraints of the time
was quite a reasonable decision. Remember that memory and long term storage
on PDP-11s was tight. The machines couldn't possibly support user
populations greater than hundreds (in particular, UIDs were only 8 bits!);
10-12 was typical, and 40 was a hugely overloaded university. Therefore,
2^12 salts came pretty close to guaranteeing uniqueness of the passwords on
each machine. Networking was *not* common, let alone ubiquitous, so
gathering password files off other machines was not part of the threat
model. And lastly, as with any security design, all you need to do is move
the weak point somewhere else; nobody tries to precompute the lists (well,
let's face it, you're not stopping the people who *do*), because cracking
them individually is essentially more cost efficient... so the salt did
what it was designed to do.
In fact, I think that (intentionally or not) this choice makes a great
example of the right kind of engineering tradeoffs. As Bruce Schneier
recently said more eloquently than I, anyone can overengineer it...
designing to constraints is much harder and more interesting. People who
believe in day-to-day use of One Time Pads (I'm not accusing anyone here of
this :-) ) are merely the furthest away from practicality.
Today, the design parameters are not so tight; even inside mobile phones,
we are looking at 32 bits of salt; why not? We have 32 bits of spare stuff
lying around that we can use and SHA will take the same time no matter what
we shove in (note: can't store it or communicate it, we have to use what
both ends already know and can agree on). But if there didn't happen to be
32 bits lying around... say only 16 bits... we'd be happy with that.
Overengineering leads to things like SET, multimegabyte key schedules (I
hope David Scott isn't listening), and software bloat in general. I *like*
the elegance of the UNIX salt scheme, and we all learned from it. Sure,
we'd do it differently today. That's partly because of what it taught us.
But, knowing what we know now, would we have done it differently *then*,
with that set of constraints? The answer to that is not at all obvious.
(IMHO the design decision that would most profitably have changed was the
limitation to 8 character passwords, not the salt. But that's another
story. That we are still using password based schemes at all, and patching
the problems with other mechanisms like shadow password files, is also
another story. If I design something like this that is still in very
widespread use in 2020, I'll consider myself to have done very well, or
society will be to blame, one or the other. More kudos to Bob Morris, Ken
Thompson and (IIRC) Fred Grampp.)
apology for the rant,
Greg.
[PS. Perry, it's Menezes, *van* Oorschot, *and Vanstone*. I, too, think
Stinson is a more appropriate reference for a beginner. I rarely recommend
the encyclopaedia as a starting point for anything. (I apologise again.)]
Greg Rose INTERNET: [EMAIL PROTECTED]
Qualcomm Australia VOICE: +61-2-9181-4851 FAX: +61-2-9181-5470
Suite 410, Birkenhead Point, http://people.qualcomm.com/ggr/
Drummoyne NSW 2047 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
