Cross-post: https://cstheory.stackexchange.com/q/41435/873

Regarding GCM, NIST specifies the following:

The total number of invocations of the authenticated encryption function shall not exceed $2^{32}$, including all IV lengths and all instances of the authenticated encryption function with the given key.

In another thread on this forum, @Lery suggests deriving session keys from the long-term key using a key-derivation function (KDF) by computing $k_s = \mathrm{KDF}(k,r)$. Here, $k$ is the long-term key, and $r$ is a random nonce generated per GCM usage. $k_s$ is the key used for GCM.

This makes sense from a security standpoint, but to increase performance, I'd like to investigate whether computing the session key as $k_s = k \oplus r$ poses any threat to the security of GCM.

You can assume that the value of $r$ is appended to the ciphertext, but is not encrypted. So, anyone seeing the ciphertext can easily deduce the value of $r$.

The adversary is said to attack this scheme if he can break the properties often associated with authenticated encrypted: IND-CCA security, or unforgeability.

  • 2
    $\begingroup$ Key derivation functions are pretty fast. You can even generate a KDF by using a single run of a hash function over the master key and a counter. Besides that, even $2^{24}\cdot16=268435456$, about 268 MB. On KBKDF per 268 MB will not slow down computation much. Note that you can use a KBKDF rather than a PBKDF (also known as a password hash). KBKDF's can be pretty fast. $\endgroup$ – Maarten Bodewes Aug 20 '18 at 14:28
  • 1
    $\begingroup$ @MaartenBodewes: I've also considered your points, but unfortunately they are moot in the application I'm working on. Besides, the question is interesting from a theoretical point of view. $\endgroup$ – M.S. Dousti Aug 20 '18 at 17:30
  • 2
    $\begingroup$ No problem, it is not an answer. But as others may read the same Q/A it is important to note these things somewhere... already voted the question up. $\endgroup$ – Maarten Bodewes Aug 20 '18 at 18:08
  • $\begingroup$ Can you expand on what engineering constraints lead you to conclude that Maarten's suggestions are moot for your application? $\endgroup$ – Squeamish Ossifrage Mar 8 at 0:06
  • $\begingroup$ @SqueamishOssifrage: A very tiny piece of hardware with extremely low amount of resources. $\endgroup$ – M.S. Dousti Mar 10 at 20:19

There are two parts to AES-GCM: AES and GHASH. This can completely ruin the security of both of them. AES is not designed to resist related-key attacks, so you're in hot water already if you derive multiple keys like this. Not only does GHASH not resist related-key attacks, but it has a particularly simple structure that illustrates how bad things can get if you make this mistake.

GHASH authenticates a series of messages $m_1, m_2, \dots, m_\ell$ with a long-term key $k$ and a per-message key $s_i$ by $m_i \mapsto \operatorname{GHASH}_k(m_i) + s_i$. Note that xor, $\oplus$, is just addition in the field $\operatorname{GF}(2^{128})$ that GHASH works in, and for a single-block message, $\operatorname{GHASH}_k(m_i) = m_i \cdot k$ is just multiplication, so the authenticator is simply $m_i \cdot k + s$.

Suppose the sender authenticates a (say) one-block message $m_0$ under $k$ with $r_0$ and a one-block message $m_1$ under $k$ with $r_1$. That is, suppose you use $k \oplus r_0$ instead of $k$ for one purpose and $k \oplus r_1$ instead of $k$ in another purpose. Then the adversary learns the authenticators $a_0 = m_0 \cdot (k + r_0) + s$ and $a_1 = m_1 \cdot (k + r_1) + s$. By the advanced cryptanalytic technique of subtraction, the adversary will find $$a_0 - a_1 = (m_0 - m_1) k + m_0 r_0 - m_1 r_1$$ which they can easily solve for $k$ and forge messages under any nonce $r_i$ of their choice with wild abandon.


Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.