Can I prove AES-GCM nonce reuse just from the bytes?

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.

• You need a correlation test. Mar 18 at 20:02

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.
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'$$.