deriving multiple keys from one passphrase

Leichter, Jerry leichter_jerrold at
Mon Feb 5 00:07:50 EST 2007

| Hey, quick question.
| If one wants to have multiple keys, but for ease-of-use considerations
| want to only have the user enter one, is there a preferred way to
| derive multiple keys that, while not independent, are "computationally
| independent"?
| I was thinking of hashing the passphrase with a unique string for each
| one; is this sufficient?  If sufficient, is a cryptographically strong
| hash necessary?
The property you presumably want is that knowing n generated keys gives
you "no information" about the n+1'st generated key.  The usual way
that's proposed to do this is to take the master secret, concatenate
some identifying data - say k encoded in 32 bits for the k'th secret -
and run the result though a cryptographic one-way function.  This
*seems* like it ought to work - "you can't invert the function", etc.,
etc. - but even if the one-way function has all the usual properties,
it's not clear they really give you the property you need.  (In fact,
the arguments have the flavor of older arguments that you can "easily"
construct a keyed checksum from a hash by "just" prepending, or
appending, secret keying material.  In fact, you need to use something
more clever, like HMAC.   Using HMAC here looks like a good try, but
it's no clear that it does the trick either.)

Of course, there is a primitive that does have the right property,
namely an encryption function.  Suppose we took k and decrypted it
with the secret master key.  Any good encryption function will
certainly have, as part of its assumed properties, that seeing the
decryption of n blocks gives you no information about the decryption
of any other block (at least as long as n is small compared to the
2^(block size), which it certainly will be).
| I got a clarification about the "use CRCs to process passphrase" idea
| someone mentioned.  The salient bit is that he was using several CRCs
| (not sure if it's random or carefully chosen), and each one is run on
| the passphrase, and the output of all of them concatenated to
| initialize a PRNG seed.  The passphrase and seed are both secret, so
| according to him there's no need to use a cryptographically strong
| hash, and CRCs have a well-understood mathematical basis.
| I presume this would be insufficient for deriving independent keys,
| but perhaps there is a way to do that with careful selection of the
| CRC polys?
He's perhaps relying Rabin's "fingerprinting using random polynomials"
results.  What it basically says is that, even though it's easy to
attack a CRC any *known* polynomial, if I choose a polynomial *at
random* and keep it secret, your chance of modifying something I
checksum with that CRC and getting away with it is essentially just
1 in 2^n (for an n-bit checksum).  Of course, I have to keep both
the polynomial and the checksum secret; and there is some math involved
to pick a primitive polynomial randomly.

However, coupling all this with seeding a PRNG makes it highly likely
that he's cross the line from "obviously no vulnerabilities" to "no
obvious vulnerabilities".
							-- Jerry

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at

More information about the cryptography mailing list