# Combining two keys

What is the most secure way to combine two "random" keys X of size k (k ≤ 512 bits) and Y of size 512 bits in one key Z of size k? Result Z will be used for encryption/decryption with various symmetric ciphers (most commonly with AES-256 in CBC mode) or as HMAC key (most commonly with SHA1 and SHA256).

There are two distinct use cases:

1. a single Y will be combined with a single X (of size 512 bits) and resulting Z will be used many times
2. a single Y will be reused many times with different X-es (with variable unknown size or various sizes) and resulting Z-s will be used

I know that simple XOR-ing is not a good idea, because in case 2. if a single X+Z pair will get compromised then Y also will be known to attacker.

Currently I think that a hash function (SHA-512) can be used on X || Y (|| denotes concatenation) and first k bits of the output can be used as Z. The only reason why I still haven't chosen this solution is due to fact that I want to lose as little entropy of key X as possible (and due to collisions in hash function some entropy may be lost).

Another idea is to use a symmetric cipher on X with Y used as key (most likely AES-256 in CBC mode without IV taking first k bits of output as Z). The only pro of this solution is, if X is 256 or 512 bits long then (due to bijectional nature of symmetric ciphers) no entropy should be lost.

I would like to get some opinions on this, may be there are some standard solutions/methods for this?

-
You should make it clear if $X$ combined with $Y$ is expected to give the same result as $Y$ combined with $X$ or not. – kasperd Aug 12 '14 at 22:20
$A$ combined with $B$ should give different result than $B$ combined with $A$ (unless $A$ and $B$ are equal). – DavisNT Aug 14 '14 at 6:06

A key derivation function lets you derive keys from others. In this case I would use HKDF, which means using HMAC in a predefined way.

Your key material is the keys $X$ and $Y$, so you can concatenate those to get the PRK for HKDF-Expand. An output key would then be $\operatorname{HMAC}(X||Y, \text{info} || \text{0x01})$, if the size of the HMAC is long enough. If not you concatenate iterated HMACs as described in 2.3.

The info string should be used to customize each different key you want to derive from the same $X$ and $Y$. You should not reuse a key for e.g. both AES and HMAC.

Even HMAC-SHA-1 should be secure here, but with SHA-256 you can use a single block of output to derive keys for even AES-256. If you for some reason needed longer keys (e.g. for Blowfish) you could even use SHA-512.

The only reason why I still haven't chosen this solution is due to fact that I want to lose as little entropy of key X as possible (and due to collisions in hash function some entropy may be lost).

If you derive an $n$-bit key from an $n$-bit (completely random) key, you lose less than a bit of entropy to collisions when running it through $n$-bit HMAC. When $n \ge 128$ that doesn't matter at all. Further, if you derive a key with $k\ll n$ bits from an $n$-bit key, you lose no entropy.

-

HMAC is considered the most secure way of combining two keys, as compared to a single round of SHA256. is designed to fold in the key material in 2 hash operations, which helps resist chosen plaintext attacks on , although SHA256 has no known chosen plaintext attacks at this time.

Symmetric ciphers are considered less reliable than hashes for this purpose, because they are not designed to provide the same guarantees as a hash with regard to irreversibility, large internal state, and bit mixing. Symmetric ciphers are however much faster than hashes, so for some purposes where very high request volume is required, it might be sufficient and desirable to use a cipher instead of a hash.

-
Thanks for answer! Won't HMAC (with Y as key and X as message) hurt the entropy of X? Or the expected number of bits lost in SHA-2 collisions should be irrelevant? – DavisNT Aug 10 '14 at 22:47
Some entropy loss isn't necessarily bad, because it helps to guarantee irreversibility. HMAC-SHA256 has 128 bits of security, so if you want more, maybe go with HMAC-SHA512. – Jeff-Inventor ChromeOS Aug 10 '14 at 22:52
In this case HMAC-SHA-256 is enough for 256-bit security, because only preimage attacks are relevant. – otus Aug 11 '14 at 4:50
@Jeff-InventorChromeOS, yes, when a collision attack applies. Here it does not, since finding a "random" pair of KDF inputs that give the same output key doesn't help the attacker. – otus Aug 12 '14 at 6:03
I would say it's 256-bit secure. Simply using it $2^{128}$ times is insecure, just like AES can only be used to encrypt fewer than $2^{64}$ blocks (regardless of key size) unless you want to give the attacker an advantage. As long as you ensure proper key lifetime, both HMAC-SHA-256 and AES-256 have 256-bit security. – otus Aug 13 '14 at 14:38