Private Key Generation from Passwords/phrases

[Bill Stewart]

> > With 4K possible salts, you'd need a
> > very large password file to have more than a very few collisions,

>Definition of "very large" can vary. (alliteration intended).[...]
>UCSD has maybe 60,000 active users.  I think "very large" is very common
>in the University environment.

Different decade, different threat models, different scales.
It was probably pretty rare to have more than a
couple of hundred users on a PDP-11,
but even at 60-70 you're in birthday-collision range with a 12-bit salt.
But a website could easily have a million users in its password files,
and some systems like Yahoo and Hotmail have hundreds of millions,
though obviously they're not all separate Unix userids.
Sometimes it matters if they get stolen, sometimes not -
I don't care if someone discovers that
my New York Times web password is "password",
but I'd be really annoyed if my online banking password got cracked.

Salt is designed to address a couple of threats
- Pre-computing password dictionaries for attacking wimpy passwords
         These become harder to do online, pushing a dictionary of
         e.g. a million words to 4 billion, or ~32GB,
         an unreasonably large database for ~1975 crackers,
         though obviously you could use a manageable stack of tapes.
         Today that fits in my iPod, though it's still impractical
         to store an unsalted full-56-bit DES password dictionary.
- Detecting password collisions within systems, and between systems
         Testing a known password against 4096 salts
         took a long time at 0.5 MIPS, but it's faster at 4000 MHz.
         Large systems will have internal collisions,
         and the web makes it even more likely that somebody
         will have logins on insecure systems
         that might have the same password as their "secure" logins.
- Annoying then-hypothetical hardware DES crackers
         That's still useful against some designs today,
         though many designs, especially software,
         are table-driven in ways that aren't annoyed much.

There are probably times that salt is useful, and that password files
using hashes are useful, but I'd think that if you're going to do that
today you might as well use 64 or preferably 128 bits of salt,
and of course you might want a hash other than MD5 or SHA-1.


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com