expanding a password into many keys

Eric Rescorla ekr at rtfm.com
Tue Jun 14 13:34:36 EDT 2005


Ian G <iang at systemics.com> writes:

> I'd like to take a password and expand it into
> several keys.  It seems like a fairly simple operation
> of hashing the concatonatonation of the password
> with each key name in turn to get each key.
>
> Are there any 'gotchas' with that?
>
> iang
>
> PS: some psuedo code if the above is not clear.
>
> for k in {set of keys needed}
> do
>     key[k] = sha1( pass | k );
> done

Some terminology first. Let's assume that we have a password P and
that we want to generate a series of n keys K_1, K_2, ... K_n, each of
which has a label L_1, L_2, ... L_n. What we want is a function
F(P,L_i) that produces K_i values. There are a number of desirable
elements that one would like to incorporate in such a scheme.

The most basic one is that it the best attack should be to brute force
the password space.

So, this means that:

1. You shouldn't be able to compute P from K_i in any less 
   time than exhaustive (or at least dictionary) search of P.
2. You shouldn't be able to compute K_j from K_i (for i!=j)
   in less time than search of P.

Hash-based constructions are the standard here, but I'm generally
leary of using a pure hash. Probably the best basic function is to use
HMAC(P,L_i) or perhaps HMAC(H(P),L_i), since HMAC wasn't designed to
be used with non-random key values.  You'd need someone with a better
understanding of hash functions than I have to tell you which one of
these is better.

But this only gets you part of the way there. We'd really like
to make it harder to dictionary search the password. We can
do this by making F slower. The standard way to do this is simply
to iterate the underlying function. This is what PKCS #5 does.
This of course slows down the user, but that's barely noticeable
in ordinary operation and it of course slows down the attacker
by a comparable margin.

An additional trick, used by Halderman, Waters, and Felten [1]
(which pretty much embodies the state of the art here)
is to have a two-level system where you substitute K in F with
G(K), where G(K) is computed by a similar, very expensive 
iterative procedure. The idea is that the first time you
use the password generator on a given computer, you compute
G(K) and then cache it. This takes maybe a minute or so,
but in the future all of your authentications are fast and this
obviously really slows down the attacker.

-Ekr

Halderman, Waters, and Felten, "A Convenient Method for Securely Managing
Passwords", WWW 2005.
http://www.cs.princeton.edu/~jhalderm/papers/www2005.pdf

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



More information about the cryptography mailing list