0
$\begingroup$

As we all know, nonce reuse in AES/GCM can easily be catastrophic.

However, I'm wondering if the same risks are present if an adversary has access to:

  1. Ciphertext and corresponding MAC of one message
  2. Small amount of plaintexts and MACs of different messages

using the same (key, nonce) tuple.

Would this leak part of the key K or subkey H? And would MAC truncation decrease information about the subkey gained by an adversary? (Despite making it easier to bruteforce a forgery)


Motivation: Sending a network packet, then sending an ACK for the same packet.
ACK plaintext is uninteresting, but should be protected against forgery.
Nonce is derived from packet sequence number, which ACKs naturally want to reuse.
ACKs contain a bitfield for previous packets, may change over time if an ACK for the same packet is resent.

$\endgroup$
3
  • $\begingroup$ What prevent the attacker to see the ciphertext and MAC of the different messages using the same (key, nonce) tuple? Crib-draging can only leak the messages, however, using the same (key, nonce) tuple can cause lost of the authentication key which is calculated $H = AES_K(0^{128} ).$, i.e. the encryption key $K$ is protected by AES. $\endgroup$
    – kelalaka
    Commented Oct 11, 2023 at 16:49
  • $\begingroup$ @kelalaka Ok so you suppose $H$ would be entirely leaked if nonce was reused to authenticate different plaintext? $\endgroup$ Commented Oct 11, 2023 at 17:51
  • $\begingroup$ Well, they can combine old messages and authenticate them on their behalf. $\endgroup$
    – kelalaka
    Commented Oct 11, 2023 at 17:54

1 Answer 1

1
$\begingroup$

However, I'm wondering if the same risks are present if an adversary has access to:

Ciphertext and corresponding MAC of one message Small amount of plaintexts and MACs of different messages

If there is a 16-byte aligned block in the second message that the attacker has no information about (that is, all $2^{128}$ values are equally likely), then the adversary learns nothing about $H$ (unless $H=0$, which is true with probability $2^{-128}$). This remains true even if the attacker knows the rest of the message, the entire AAD and the entire MAC.

When we have a nonce collision, the two tags are computed as:

$$p_nH^n + p_{n-1}H^{n-1} + ... + p_1H^1 + C = tag_p$$ $$q_mH^m + q_{m-1}H^{m-1} + ... + q_1H^1 + C = tag_q$$

(where $p_n, ..., p_1, q_m, ..., q_1$ are the two polynomials that the messages are converted to, and $C$ is the common constant value that is a function of the nonce, and is the same for both messages because of the nonce reuse).

If the adversary is missing one of the blocks of the message (say, $q_z$), then he has two equations in three unknowns ($H, C, q_z$).

In particular, if $H \ne 0$, then for any value of $H$, there are corresponding $q_z$ (and $C$) value which makes both equations work, hence no value of $H$ (other than 0) can be eliminated from consideration (and a slightly more indepth analysis would show that the adversary doesn't get any probabilistic information).

Of course, the above doesn't apply if the adversary has partial information about $q_x$. Even if there are enough secret bits that the adversary can't do an exhaustive search, they would appear to be likely to be able to recover something if the nonce is repeated more than two times.

$\endgroup$
4
  • $\begingroup$ ACKs are entirely plaintext, no need for confidentiality. The only ciphertext known is that of the original message. $\endgroup$ Commented Oct 11, 2023 at 17:41
  • $\begingroup$ To clarify: Recipient decrypts original message, then sends any number of different plaintext ACKs, whose GMAC is generated with the same public nonce as the original message. $\endgroup$ Commented Oct 11, 2023 at 17:48
  • 1
    $\begingroup$ @JulianDurchholz: my advice would be to not reuse nonces. If you derive the nonce from the sequence number, you can (for example) have the original message use $nonce = 2\times seqno$ and the ack use $nonce = 2\times seqno + 1$ $\endgroup$
    – poncho
    Commented Oct 11, 2023 at 17:51
  • $\begingroup$ Considering an ACK might be lost, and later resent (at which point the bitfield could have changed), I would need multiple new nonces. Then the receiver of an ACK can't derive the nonce anymore, forcing me to allocate and include dedicated sequence numbers just for ACKs, which for the most part won't even be used with normal packet loss. Probably best not to update the bitfield, even though that ignores some new information. That makes your suggestion somewhat practical. $\endgroup$ Commented Oct 11, 2023 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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