0
$\begingroup$

I have AES-GCM output with GMAC tag. The plaintext consists of some bitfields I know the structure of. When I generate input which should only affect timestamps and counters in very specific bytes, I see corresponding ciphertext changes only in those bytes for 2 subsequent calls to the encryption function.

Ignoring the GMAC part for now, what would I need to mathematically prove that there is nonce reuse scenario based on those simple equations?

P_1 ⊕ KS_1 = C_1
P_2 ⊕ KS_2 = C_2

based on observation that

C1 = C2

on the same byte position that

P_1 = P_2

I'm aware that set of implication might not be enough for proof, but I'm trying to understand what I'm missing of how to calculate probability that my theory is true, based on the fact that - for bits x out of y, this is true.

$\endgroup$
1
  • $\begingroup$ You need a correlation test. $\endgroup$
    – kelalaka
    Commented Mar 18 at 20:02

1 Answer 1

1
$\begingroup$

When I generate input which should only affect timestamps and counters in very specific bytes, I see corresponding ciphertext changes only in those bytes for 2 subsequent calls to the encryption function.

Stop right there; if you encrypt two similar messages $P$ and $P'$ (where most of the bits of $P, P'$ are common), and you get two ciphertexts $C, C'$ for which most of the bits are also common, then yes, something hideously wrong is happening, and the most likely hideously wrong thing is the two encryptions used the same IV.

If GCM is used correctly, then the output ciphertext should look completely random (except for close analysis by someone who knows the key); the encryption of two plaintexts (including plaintexts that are similar, or for the matter, the same) should appear to be independent random values, and the probability of two independent random values agreeing on most of the bits is neglectable.

To take this from 'quite likely' to 'almost certain', check to see if where $P, P'$ disagree corresponds to where $C, C'$ disagree (ignoring the tag at the end; that would look different regardless). If everywhere $C, C'$ disagree corresponds to where $P, P'$ disagree (and visa versa), then you almost certainly have a repeated IV. Note that $C, C'$ may have the IV up front, and so byte 19 of $P, P'$ might be byte 19+12 = 31 of $C, C'$.

$\endgroup$
1
  • $\begingroup$ So I see above through kind of 'intuition' but how to prove it using algebraic notation ? $\endgroup$
    – nusch
    Commented Mar 22 at 14:18

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.