Are there any serious problems with this technique for generating symmetric keys?

I'm using a technique borrowed out of a book by Bruce Schneier and Niels Ferguson called Practical Cryptography. Basically, it boils down to this:

Bob does this:

pubk_A = Alice's public key

entropy = bytes from PRNG

encrypted_entropy = RSA_Encryptpubk_A(entropy)

hashed_entropy = SHA2-512(entropy)

encrypt_keyBA = hashed_entropy[0:32]
encrypt_nonceBA = hashed_entropy[32:48]
hmac_keyBA = hashed_entropy[48:64]

Bob then sends encrypted_entropy to Alice.

Then Alice does this:

privk_A = Alice's private key

entropy = RSA_Decryptprivk_A(encrypted_entropy)

hashed_entropy = SHA2-512(entropy)

encrypt_keyBA = hashed_entropy[0:32]
encrypt_nonceBA = hashed_entropy[32:48]
hmac_keyBA = hashed_entropy[48:64]

This works great for generating keys that can be used to communicate from Bob to Alice. But I need keys I can use in both directions. I was thinking of modifying the algorithm in this way:

Bob does this with entropy:

pubk_B = Bob's public key

hashed_entropyBA = SHA2-512(SHA2-256(pubk_A) || entropy)

encrypt_keyBA = hashed_entropy[0:32]
encrypt_nonceBA = hashed_entropy[32:48]
hmac_keyBA = hashed_entropy[48:64]

hashed_entropyAB = SHA2-512(SHA2-256(pubk_B) || entropy)

encrypt_keyAB = hashed_entropy[0:32]
encrypt_nonceAB = hashed_entropy[32:48]
hmac_keyAB = hashed_entropy[48:64]

Alice can do the same thing on her side after she obtains entropy by decrypting encrypted_entropy.

As you can see, now there are two sets of keys, one used for communicating from Bob to Alice, and another for communicating from Alice to Bob.

Is there anything wrong with this? What security risks am I taking? Is the security of the system less or more than if I simply had one party tweak a bit in the nonce? Is there a better way to handle this problem without adding round-trips?

• You have a missing parenthesis in your definition of hashed_entropy. Also, can you define `+`? Is it concatenation, addition modulo 2^512, bitwise xor, or something else? Also, is it reasonable to assume both endpoints know Bob's public key as well as Alice's public key? If you can clarify those points, I'll be glad to try to share some analysis of this. – D.W. Mar 29 '11 at 6:22
• I should've used more standard cryptographic notation. I meant `+` as concatenation. It is reasonable to assume that both endpoints know both Alice's and Bob's public key. This is partly because Alice's name for Bob is SHA2-256(pubk_B), and Bob's name for Alice is SHA2-256(pubk_A). – Omnifarious Mar 29 '11 at 6:40

With RSA you can safely transmit n-1 bytes of entropy based on the size of the key chosen. Thus a 2048bit RSA key can encrypt 2047bits of data, which more than enough for a pair of key/nonce/hmac. Stretching entropy with a message digest function should be avoided, however there is more than enough entropy to go around so long as the RSA message isn't padded. The first step is to split the 2047 bits of entropy in half and hash the results:

``````hashed_entropyA=SHA2-512(entropy[0:1023])
hashed_entropyB=SHA2-512(entropy[1024:2047])
``````

The first set:

``````encrypt_keyB = hashed_entropyB[0:32]
encrypt_nonceB = hashed_entropyB[32:48]
hmac_keyB = hashed_entropyB[48:64]
``````

The second set:

``````encrypt_keyA = hashed_entropyA[0:32]
encrypt_nonceA = hashed_entropyA[32:48]
hmac_keyA = hashed_entropyA[48:64]
``````

The results are independent and strong form of key derivation such that two parties can communicate. One side of the communication can be compromised without the entire system being compromised. Defense in depth, security in layers.

• I have to disagree with this advice. I don't think it represents good practice. You have no clue whether it is secure, and neither do I. There are proofs of security for the scheme in Practical Cryptography, which demonstrate that it is likely to be secure (i.e., if we make assumptions that are widely accepted in the crypto community). The scheme @Rook proposes has no proof of security. This is dangerous. In the past we've had a very bad experience with schemes with no proof of security. For instance, Bleichenbacher's attack totally broke PKCS#1 RSA encryption. – D.W. Mar 31 '11 at 6:39
• (continued) In retrospect, the flaw in PKCS#1 could have been anticipated, because it did not have any proof of security under reasonable assumptions. The lesson from the Bleichenbacher debacle was to adjust our standards for design of new cryptographic schemes, and in particular, to insist on a proof of security under reasonable assumptions. Therefore, it is my assessment that @Rook's scheme does not meet the standards that the modern crypto community would expect. It's not what I would choose. – D.W. Mar 31 '11 at 6:42
• @D.W. If you read my profile you'll see that I agree that no one should take the advice of SO or secuirty.se. Everything should be tested. That being said, you post is pure flame and you should be more professional. Posts like this are embracing. – rook Mar 31 '11 at 7:05
• You can easily be vindicated by posting a proof of security for your scheme. – Bruno Rohée Mar 31 '11 at 10:46
• @Bruno Rohée This post is tame, I think the security benefit is obvious. – rook Mar 31 '11 at 18:55

Answer to your specific question: There's an easier way to tweak their scheme to achieve what you have in mind. Go with what's in the book, except make the following modification:

``````hashed_entropy = SHA2-512(0 || entropy) || SHA2-512(1 || entropy)
``````

so that hashed_entropy now contains 128 bytes. Now use the first 64 bytes for the Bob->Alice direction (e.g., extracting keys and nonce as in the book), and the next 64 bytes for the Alice->Bob direction (similarly, extracting keys and nonce).

(Here I write `||` for the concatenation of two byte-sequences.)

Important cautionary note: This scheme does not authenticate Bob. It is not suitable for use in environments where mutual authentication is expected or required.

High-level comment: I tried to answer the specific question you asked. However, I would be negligent if I stopped there. Are you sure you are asking the right question? Are you sure you need to implement your own way of building a secure (encrypted, authenticated) channel?

While Practical Cryptography is a fantastic book, I'd be pretty reluctant to use a custom design, even one taken from that book, unless I had no other choice. If it were me, I would first make a serious attempt to reuse some well-vetted, widely-deployed design, e.g., TLS. Only if that completely failed to meet my requirements would I then consider doing something custom.

My criticism has nothing to do with the quality of Practical Cryptography, but rather with the broad variety of things that can go wrong if you design and implement your own secure channel (including, e.g., subtle implementation flaws that can be introduced).

• +1 for simplicity, +100 for reusing existing channel. – AviD Mar 29 '11 at 6:45
• In the protocol, after the encrypted_entropy, a digital signature, signed by privk_B, appears that signs all of the header fields up to that point, including the encrypted entropy. The protocol I'm implementing is called CAKE. There are specific reasons I'm designing a new protocol. And yes, there will initially be implementation issues (sidechannel attacks for example). cakem.net – Omnifarious Mar 29 '11 at 6:45
• @AviD: I consider TLS broken because the CA system is fundamentally the wrong way to handle the issue it purports to solve. It also requires a transport that is somewhat like TCP, and I want a system that works over a wider variety of transports, some with arbitrarily high latency (like email for example). – Omnifarious Mar 29 '11 at 6:49
• @Omnifarious, Regarding your goal of avoiding the CA system, I suspect TLS already solves your problem. When you say "TLS is broken", perhaps you're not aware of how flexible TLS is. TLS is not tied to a CA system. TLS does not require you to rely upon CAs. You can define any method you like for validating the other endpoint's cert, and use the TLS protocol with that. Don't confuse "TLS the protocol" with "the way that web browsers use TLS". – D.W. Mar 31 '11 at 6:44
• @Omnifarious, one last comment. The fact that you have to ask these questions is a sign that designing a scheme yourself is probably not a great idea, if you can possibly avoid it. I don't mean this as an insult to your abilities or intelligence. This stuff is subtle and even the most advanced cryptographers probably would not lightly engage in design of a new crypto protocol, unless they had to. For example, I know lots of theory, but personally I still would try hard to reuse an existing, vetted scheme, instead of designing my own. – D.W. Mar 31 '11 at 6:57

What you want is a Key Derivation Function: a KDF takes as input a "master key" (here, your "entropy" string) and produces as many bytes as you need for your symmetric cryptography. A single hash function call is a crude KDF which produces as much output as the hash function output size, i.e. 64 bytes for SHA-512.

Many protocols include a custom KDF. E.g., in SSL/TLS, the "PRF" function (defined in section 5) is a construction using the underlying hash function (usually SHA-256 for TLS 1.2) within HMAC, repeatedly. Another standard KDF is PBKDF2 (section 5.2). Actually any good stream cipher would be a decent KDF (see the eSTREAM Project for some good stream ciphers).

Another option would be to be less wasteful with your key material. From the names you give to the derived elements ("encrypt_key", "encrypt_nonce", "hmac_key"), I surmise that you wish to symmetrically encrypt things, with a keyed integrity check. Symmetric encryption and MAC together are not an easy task; there are many hidden pitfalls. The smart thing is to use an Authenticated Encryption mode for a block cipher. An AE mode combines symmetric encryption and integrity check, and internally handle its own KDF. I suggest EAX. Such a mode only requires a "nonce": that's an IV with only one requirement, i.e. not to be used twice with the same key. This would yield the following protocol:

• Bob obtains some bytes M from a PRNG (at least 16 bytes).
• Bob encrypts M with Alice's public key; Alice will use here private key to get M.
• Both Alice and Bob compute SHA-256(M) yielding a 32-byte string K.
• Afterwards, Bob sends messages to Alice, using K[0..15] as key with EAX mode; the nonce is a message counter (1 for first message, 2 for second message, and so on). The nonce can be appended to each message, or known implicitly by Alice (e.g. the "messages" are successive records on a TCP connection).
• Similarly, Alice can send messages to Bob, using K[16..31] as key with EAX mode.

And there you are: only 256 bits worth of initial key material required, so a simple hash function invocation will be fine; no clunky KDF needed.

But, really, that's just reinventing SSL. That's fine for research / educational purposes, but, for anything which is meant to be deployed in practice, you really should stick to standard protocols where security issues and implementation hurdles have already been (painfully) reconnoitred. Did I mention SSL ?

• I already have to the code to use AES in CTR mode with an HMAC verifier. I will investigate EAX though. – Omnifarious Sep 26 '11 at 20:20
• And, I do not like TLS. I do not like TLS because X.509 certificates are exactly the completely wrong thing to be doing, and having that be a part of TLS in any way was a horrible mistake. I also do not like it because it assumes an underlying ordered stream of bytes and I want something that works in a more general environment. – Omnifarious Sep 26 '11 at 21:17
• @Omnifarious: the X.509 certificates are quite well-contained in TLS; they are blobs with a three-byte header which gives the length. You can skip them if you already happen to know the peer's public key. For the underlying stream: things can become hairy if you use a fuzzier transport medium, with regards to lost/repeated/inverted packets. Have a look at DTLS (that's TLS for UDP). You are not on an easy quest. – Thomas Pornin Sep 26 '11 at 21:27
• @Omnifarious Nobody forces you to use the usual CA hierarchy, simply deploy your own one (can be one-level). Or don't you like the X.509 certificate format? – Paŭlo Ebermann Sep 26 '11 at 22:42
• @PaŭloEbermann: The X.509 certificate format itself implies putting the cart before the horse. It implies a model of identity in which a trusted authority authenticates an identity to you. This is excessively centralized, and at variance with how human beings themselves handle the problem of identity. People who were sufficiently aware and paranoid predicted the current problems we have with CAs 10 years ago. Additionally, the statements made in X.509 certificates have no clear standard definition anyway. I know, I made an X.509 creator once. – Omnifarious Sep 27 '11 at 1:40