At 10:20 PM -0400 6/1/99, Steven M. Bellovin wrote:
>In message <v04011703b379ec9890f1@[24.218.56.100]>, "Arnold G. Reinhold"
>writes
>:
>
>>
>> It is also desirable to be able to increase the memory footprint of your
>> key stretcher as well its iteration count.
>
>That's far from clear. More or less any reasonable factor is dwarfed by
>the rapid expansion in memory sizes.
If you think your attacker is using a farm of PCs you may be correct, but
if they are using arrays of custom chips or FPGAs, using lots of memory
complicates their task significantly.
...
>> 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.)
>
>You're arguing with 20-20 hindsight. 16 gig of disk space wasn't even
>comprehensible then. 16 *meg* of disk space sufficed to bring up UNIX.
>(I just checked my 7th Edition manual. The binaries took 2.5M bytes; the
>source to the entire system took 9M.)
>
For the record, I visited an apparel company sometime around 1974 (when I
left that job) that had 3 gigabytes on line. It was the first commercial
installation I ever saw that did not have mag tapes. They backed up to
removable platters. It was a big room full of drives and I was very
impressed, but that was well before 1979.
I did a similar back of the envelope calculation, with a smaller
dictionary, when I first ran into Crypt in the mid 80's. We were running
BSD on a VAX 750 (Vaxine). A shelf of mag tapes could have held the
dictionary.
>The .5 second number was John's recommendation, but if I recall correctly
>that was about how long crypt() took on UNIX in 1979 on the PDP-11. (In
>a quick scan through the Morris-Thompson paper, I didn't see a precise
>number.)
I seem to recall that number too. I also remember rumors that NSA leaned on
ATT to keep the salt short.
...
>
>As for custom chips -- we're talking about authentication passwords, not
>secrecy passwords. I don't think many big boys are building
>password-guessers.
>The goal was to be sure that a secrecy-cracker -- in those days, a
>Diffie-Hellman DES-cracking machine -- couldn't be turned into a password-
>guesser.
I think you are wildly underestimating the importance of UNIX crypt() as an
intellegence target. Why crack codes if you can just login? And Infowar is
red-hot these days. Here's one strategy: you break into an adversary's low
security systems and run their passwd file against your dictionary. Then
identify cracked users who are likely to have an account at a target high
security system (whose passwd file is not accessable) and try the same
login name and password there, along with simple varients.
I'd bet NSA's first crypt chip was done in the early 80's and is in some
secret muesum now, that their crypt() dictionary is at least 10 terabytes,
maybe a petabyte and that they have their custom crypt() chip farm cranking
away at serbo-croation and albanian passwords as we speak. Come to think of
it, they probably have all pronounceable passwords in their dictionary
already.
Based on this analysis, anything less than 8 character random printable
ASCII passwords are probably insufficient for high security UNIX use where
the threat includes large codebreaking agencies.
>>
>> 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?
>
>My own simple-minded scheme for hashed password storage is N interations
>of SHA-1 on the concatenation of the password, the salt, and a per-site
>constant. If you do that, more or less any size salt will cause no
>perceptible
>difference in time. Sure, use a long salt.
>
>But you misunderstood my basic point: I'm asking for engineering numbers.
>John cited a precise figure; I want to know where it comes from. When I
>do the calculations, I keep coming up with numbers that are a lot closer
>to 12 bits than to 32.
John would have to say what he had in mind, of course. But in my opinion
the discussion we are having is the best engineering calculation possible.
We can at least learn something from history even if it seems like 20/20
hindsight. The designers of crypt() probably never imagined it would still
be in widespread use 20 years later. And with a little imagination they
could have predicted it was inadaquate. We should do no less. A password
dictionary sounds like a perfect application for DNA storage. I am
starting to think 32 bits of salt are not enough.
>
>Btw -- large password files using anything like this scheme are obsolescent.
>You can't use a hashed password for challenge/response, which is the technique
>of choice for PPP. Similarly, POP3 can support APOP. Both require plaintext
>passwords on the server side. Sure, there are weaknesses to doing that.
>They're less relevant today for large installations than they were 20 years
>ago, because they're stored on special-purpose machines. We can't pick
>tomorrow's answers from yesterday's questions.
But then something like HushMail comes along where server side plaintext
passwords are totally unacceptable.
>
>How would I like to do it, given a blank slate? Most likely, I'd use SHA-1 on
>the user's password, probably concatenated with a salt, to produce a DSA
>private key; the server would store the corresponding public key. (It's
>harder to pull a trick like that using RSA keys.) But really, I'd get rid
>of passwords -- in the sense of "a typed string, some function of which is
>stored on the server" -- entirely. Passwords should be entered into a
>user's smart card to unlock a real key. The fundamental problem is that
>users pick bad passwords and passphrases -- and tinkering with the machinery
>to hide them isn't going to produce a fundamental change in the outcome.
I am not convinced consumers will adopt smart cards any time soon. In the
mean time there is a lot that can be done to make passphrases more
effective, including better key strechers, having programs offer to pick
good passphrases, and at least providing good advice to users.
Here is a simple UNIX tool that ought to exist (maybe it does?): a varient
login that accepts a long passphrase, hashes it with SHA1 and produces a
random printable ASCII password that is then used as the normal UNIX
password. You could optionally display the random printable password and
write it down for use on systems that lacked this tool.
Arnold Reinhold
