# using random encrypted RSA challenge as key material

Assume a simple protocol for authentication - one side sends a randomly generated challenge string and encrypts it with RSA.

The receiver decrypts it and replies with a hash of the challenge, proving that he owns the private key (and nothing more).

My question: is it safe to also use parts of the same random challenge to derive encryption keys, e.g. for a symmetric cipher or a HMAC?

If not, is it safe to hash only part of the challenge as proof, and use another part of the challenge as key material?

As concrete example: send e.g. a 2600 bit random challenge, encrypted via 3072 bit RSA-OAEP. Is it safe to hash the 2600 bits (and return the hash to the sender in cleartext) as proof, and use hkdf on the first 128 bits to derive a shared AES key?

-

If you want to be really sure, you could generate both the reply and the encryption keys from the challenge using a suitable key derivation function, such as HKDF (RFC 5869), e.g. as in:

salt = sender-ID | recipient-ID
PRK = HKDF-Extract(salt, challenge)

encrypt_key = HKDF-Expand(PRK, "encrypt", keylen)


Provided that HKDF is instantiated appropriately and that the underlying hash function is secure, it should not be possible for an attacker observing the reply to learn anything useful about the challenge or the encryption key, at least provided that the same challenge is never sent twice between the same parties. (If you want to eliminate even that minor loophole, include something unique, such as a timestamp, in the salt.)

Edit: Your originally proposed scheme could also be safe, but there are some potential pitfalls. For example, if you're using the same hash function to generate the reply as for HMAC, and if your challenge is longer than one hash input block, and you're not using any kind of salting to differentiate the two uses, then you could have a problem.

That's because, if the keystring is too long, HMAC will first hash it down to less than one input block using the underlying hash function, and then use the hash output as the actual key. Thus, anyone knowing the hash of the key would be able to compute the HMAC output just as easily as if they had the key itself.

That's one reason why I'd recommend using a KDF to generate both the reply and the encryption / HMAC keys, with different role strings as I suggest above. That's exactly what a KDF is designed for.

-
Thanks for the reassurance! –  Marc Lehmann Jul 18 '13 at 19:04
Hmm, I have trouble setting your answer as the accepted answer (clicking has no effect) :( Ah, and now I really understand your answer: using a hkdf also for the reply is a great idea. –  Marc Lehmann Jul 18 '13 at 19:08
One minor additional question though: in other replies I read that using hkdf-expand for more than one key (using the same extract data) is not correct - I was under a different impression after reading the rfc, but re-reading indeed doesn't seem to allow multiple expand steps for the same PRK. It's not a problem in this case (one could use different parts of the challenge), I just wonder about this in general. –  Marc Lehmann Jul 18 '13 at 19:11
As for the original scheme: the actually implemented scheme uses a different (auth) HMAC key for the response, and uses HKDF on different parts of the challenge to derive (message) HMAC and cipher key. However, the extra effort of using HKDF for the auth reply seems well worth it, and answers the next question I wanted to ask, namely what kind of hash mechanism to use for the reply. –  Marc Lehmann Jul 18 '13 at 19:14
The output of HKDF-Expand is uniquely determined by its parameters (PRK, info, length). Thus, if you want to derive multiple independent keys from the same PRK using HKDF, you need to either 1) use a different info parameter for each, or 2) generate them all with one call to HKDF-Expand and split the output. Generally, just appending a counter to the info string will work fine. (Ps. See also my edit to the answer.) –  Ilmari Karonen Jul 18 '13 at 19:16
show 1 more comment