1
$\begingroup$

Using the keystream from the block cipher for both parts of the GMAC key (initialization and encrypting the auth tag) seems to produce a better mode of operation than GCM, as successful forgeries and nonce reuse only compromise the particular (key, nonce) pair, rather than compromising integrity for every message encrypted with the given key.

It seems surprising that I can improve upon a well-known and widely-used algorithm as GCM, so I would like to know if there are flaws in this approach.

$\endgroup$
  • $\begingroup$ I'm not clear on what you're proposing. Can you be more specific? $\endgroup$ – pg1989 Feb 17 '16 at 20:40
  • 1
    $\begingroup$ Use block 1 as GCM key. Use block 2 to encrypt the auth tag. $\endgroup$ – Demi Feb 17 '16 at 20:44
  • 1
    $\begingroup$ It's better security wise. But I'm not sure if you can implement it efficiently without special CPU instructions, or if you need to recompute per-key lookup tables for each message, increasing the per-message overhead. $\endgroup$ – CodesInChaos Feb 17 '16 at 20:44
  • $\begingroup$ Which ones, beyond those for standard GCM? $\endgroup$ – Demi Feb 17 '16 at 20:45
  • $\begingroup$ @Demetri I'm no expert on GCM, but it's my understanding that many implementations use a per-key lookup table to compute GHash. Since you propose using a unique key for each message, these lookup tables can't be reused across messages. $\endgroup$ – CodesInChaos Feb 17 '16 at 20:52
1
$\begingroup$

If I understand your proposal, you are suggesting to modify GCM by not using a fixed secret $H$, but instead you're making it a secret function of the nonce $f_{key}(nonce)$.

If so, I don't believe that actually improves security.

For attacks on GCM integrity, the attacker needs to recover the value of $H$. Now, because of how we xor in a nonce-dependent value at the end, using different ciphertexts with different nonces doesn't really help the attacker. Instead, what the attacker needs to do is either:

  • Wait for the encryptor to slip up and encrypt two different messages with the same nonce, or

  • Manage to generate a valid forgery (that is, one that is accepted by the decryptor) with a nonce that is also used by the encryptor.

With GCM, either of these events allows him to compute a handful of possible values of $H$ (and generating a few more forgeries would allow him to eliminate the incorrect values).

Now, with your proposal, either of these events would allow the attacker to recover $f_{key}(nonce)$, for the specific nonce that was used. This is just as good for the attacker; he can then modify the encrypted packet by flipping arbitrary bits, making it whatever he likes (this assumes he knows/guesses the plaintext contents; with him being able to flip arbitrary bits and seeing how the decryptor reacts, we can reasonably expect that this is a feasible problem, even if the attacker didn't know the message contents beforehand).

The only restriction the attacker has is that he must use the same nonce value (as a different nonce would yield a different $f_{key}(nonce)$ value); however the attacker will likely find that to be a quite minor restriction.

| improve this answer | |
$\endgroup$
1
$\begingroup$

Is this a better GCM? Not really.

You can derive an independent GHASH key for each message instead of using the same GHASH key for many messages as AES-GCM does. It won't reduce security. It's costlier without hardware support: you can't reuse the same GHASH lookup table to quickly leak secrets through timing side channelsauthenticate multiple messages.

But it's not much of an improvement in security: the difference is relevant only in the case that an adversary has already succeeded in forging a message and confirmed by the receiver that the forgery was successful (or the sender has reused a nonce, which works out to be just like the forger had made a forgery with the same nonce).

  • In this case, with AES-GCM, the adversary can forge arbitrarily many additional messages by recovering the GHASH key.

  • In contrast, with crypto_secretbox_xsalsa20poly1305, if the receiver demands sequential nonces or otherwise rejects repeated nonces, the forger can't use this to forge more than one message because the receiver will expect a different key for subsequent nonces.

It makes a difference only if the cost of a single forgery is small and you're really worried about how many forgeries you accept, which is not relevant to most applications—usually we consider a single forgery to be fatal, and strive to ensure it never happens.

This method is essentially what NaCl does in crypto_secretbox_xsalsa20poly1305: choose the Poly1305 key as the first 256 bits of the pad generated by the stream cipher XSalsa20, as suggested by Tanja Lange in 2006. Exactly the issue you describe is addressed in the NaCl validation paper on p. 30, where Dan Bernstein points out the real security comes from bounding the forgery probability below $2^{-100}$. This method is also by TLS with the TLS_*_WITH_CHACHA20_POLY1305_* cipher suites defined in RFC 7539 and RFC 7905, updated in RFC 8439 and included in TLS 1.3 in RFC 8446. Of course, Salsa20, ChaCha, and Poly1305 also avoid leaking secrets by avoiding designs that present conflicts between speed and security in software implementations. More on the background and shortcomings of AES-GCM.

| improve this answer | |
$\endgroup$

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.