-----BEGIN PGP SIGNED MESSAGE-----
[ To: Steve, Arnold ## Cc: Perry's Crypto List ##
Date: 06/01/99 ##
Subject: Re: ICSA certifies weak crypto as secure ]
>To: "Arnold G. Reinhold" <[EMAIL PROTECTED]>
>Cc: John Kelsey <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
>Subject: Re: ICSA certifies weak crypto as secure
>Date: Tue, 01 Jun 1999 22:20:05 -0400
>From: "Steven M. Bellovin" <[EMAIL PROTECTED]>
>> It is also desireable 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.
Actually, I can see some advantage to this, at least in the
extreme case where you're worried about someone building a
password searching engine specifically for your key
stretching scheme. The idea is to make each node in a
massively parallel password-searcher require a substantial
amount of memory, so it costs more to build. A
general-purpose computer will have enough memory that
requiring (say) 64 KB of RAM to run the key stretching
algorithm won't make it unusable, but it *will* have a big
impact on the cost a massively-parallel password-searcher.
This has to be balanced against performance and usability
issues, of course.
[Stuff deleted]
>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.)
This makes sense. This is just a seat-of-the-pants number;
half a second is barely noticeable in most situations. It
would be better if the passphrase hashing took longer, but
it's hard to imagine a set of users that would seriously
complain about passphrase entry taking an extra half-second.
[ Much deleted.]
>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.
Right. Though I worry a bit about just iterating SHA1,
because it's nicely parallelizeable, and it doesn't require
much memory. These are features, not bugs, in its intended
application as a hash function, of course. On the other
hand, I've designed systems that used iterated SHA1 hashing,
just as you describe; it's straightforward to code up, and
it's very easy to see you're not shooting yourself in the
foot with the design.
>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.
I'll admit 32 bits is a seat-of-the-pants number, but I
think it's at least somewhat defensible. There are a couple
ways to look at this:
a. A k-bit salt means the precomputed dictionary ends up
being 2^k times as big. We can choose k to make
dictionaries unacceptably large.
b. A k-bit salt means that an attacker must do N * 2^k
password hashes to precompute all possible values for an
N-entry dictionary. We can choose k to make this work
factor unacceptably high.
c. A k-bit salt means that the precomputation attack only
makes sense if the attacker intends to deal with a sizeable
fraction of 2^k different hashed passwords. Otherwise, the
attacker would do less work by just attacking the passwords
individually. This ignores some details, like situations
where the attacker has lots of processing time available
today but expects not to have any available tomorrow.
By any of these measures, k=32 seems more reasonable than
k=10. However, I agree that there are cases where making k
longer doesn't work too well. The systems I am used to
thinking about use the passphrase to derive a cryptographic
key, and can typically be used just fine with very big
salts. (You can use the same 64 bits as both IV and salt,
for example, or just prepend 160 random bits to an encrypted
file.)
[Stuff deleted]
>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.
Ideally, we'd get rid of passphrases used this way, and also
used to derive cryptographic keys. However, there are
situations where they work better than the alternatives.
Not all systems can require their users to have smartcards,
connect to an online server, etc.
>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.
Yes, this is definitely true. All these techniques against
passphrase-guessing attacks can only help a little bit;
passphrases that were just barely insecure can be made just
barely secure. Their effectiveness is also tied to the
amount of delay the user can stand.
- --John Kelsey, Counterpane Systems, [EMAIL PROTECTED]
NEW PGP print = 5D91 6F57 2646 83F9 6D7F 9C87 886D 88AF
-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 5.5.3i for non-commercial use <http://www.pgpi.com>
iQCVAwUBN1WAUiZv+/Ry/LrBAQE9IgP/WKFHZDBinRj14oidYIMn/QgGYktKTi0d
URojQwgLqzXfBOBnh/Grt2FZIdZspZBzkIwmz2PuiBu77FPD8jZiunJdxdncGkyr
mPnldmxom/XZ/AotDciAT5B+2pWuKNeITFohRouNifPBPzKMe/e5F/5+TEpDLHff
FsQF/f1eRNU=
=F29p
-----END PGP SIGNATURE-----
