Join Log in
Score:1
MichaelW avatar Crypto

Why using same nonce (IV) twice voids confidentiality of plain text or even key?

in flag
MichaelW

I understand roughly (without details of GF algebra) the scheme of GCS/GMAC:

enter image description here

IV is to be put into Counter-0, so initializing counters.

It is known, that using a IV twice can not only reveal the plain text but also the AES-Key itself.

I understand neither the first nor the second:

Q1: Why is confidentiality of the messages lost when using the same IV twice? Does it mean the plaintext can be inferred? Or only part of it? I cannot imagine how this could be...what part of information can be inferred from the plaintexts and how/why does it work? From the principle I could only see that the result XOR(p1, p2) can be inferred because the upper line of data is the same - but not the p1, p2 itself.

Q2: How/Why can the AES-Key itself be revealed by using the same IV a couple of time?

Note that I want to understand why and how such attack can be done; I believe that it is possible.

215
1 + 1
aes
gcm
et flag
user93353
Does this answer your question? [How bad it is using the same IV twice with AES/GCM?](https://crypto.stackexchange.com/questions/26790/how-bad-it-is-using-the-same-iv-twice-with-aes-gcm)
2
Reply
Score:3
poncho avatar Crypto
my flag
poncho

Q1: Why is confidentiality of the messages lost when using the same IV twice? From the principle I could only see that the result XOR(p1, p2) can be inferred because the upper line of data is the same - but not the p1, p2 itself.

Actually, in quite a lot of cases, knowledge of $p_1 \oplus p_2$ can be used to recover a good guess of $p_1, p_2$. That is dependent on the distribution $p_1, p_2$ were drawn from - if there are random bit strings, that obviously can't be exploited to recover $p_1, p_2$ - on the other hand, if they were English ASCII strings, then it is actually surprisingly easy (except you won't know which is $p_1$ and which is $p_2$)

Q2: How/Why can the AES-Key itself be revealed by using the same IV a couple of time?

Actually, you won't recover the AES-key itself; you can recover the internal value $H$.

GCM authentication works like this; the tag is computed by expanding the AAD and ciphertext into a series of 128 bit values $x_n, x_{n-1}, ..., x_1$ and computing:

$$tag = x_n H^n + x_{n-1}H^{n-1} + ... + x_1H^1 + E_k(nonce)$$

If we get two distinct messages encrypted with the same nonce, we can subtract the two equations, resulting in [1]:

$$tag - tag' = (x_n - x'_n) H^n + (x_{n-1} - x'_{n-1} ) H^{n-1} + ... + (x_1 - x'_1)H^1$$

Because the ciphertexts (or the AAD) was different, there will be some nonzero coefficients in this equations.

And, we know all the coefficients (unlike the single GCM case, where we didn't know the value $E_k(nonce)$); this is a known polynomial of the unknown $H$ of degree $n$; it turns out that, in finite fields, this is practical to solve.

Now, knowledge of $H$ doesn't allow us to read any ciphertexts; what it would allow us to do is modify ciphertexts in such a way to keep the tag valid, thus voiding the integrity guarantee of GCM.

[1]: Minor notational note: since we are working in a finite field of characteristic two, the operations $+$ and $-$ are actually the same, and it's traditional to always write it as $+$. I wrote it as $-$ to make it more obvious what we're doing.

0 + 5
MichaelW avatar
in flag
MichaelW
This explains a lot! My understanding now is: An attacker can find out some details of the plaintext by XOR. Moreover, maybe more interesting, he can find out H quite easily. so he can change parts of the cipher in a way which keeps T still valid. This can be done efficiently. However, can you please confirm, the Attacker cannot find out the AES-Key itself - right? So the attacker in the middle could generate garbage cipher blocks with the right signature. This is bad enough, but in lack of the key it is not possible to generate a cipher with a given plaintext content - right?
0
Reply
poncho avatar
my flag
poncho
@MichaelW: no, he cannot learn the AES key (unless he can break AES itself); however if he guesses the contents of a particular plaintext (say, by using the XOR of the two ciphertexts), then he can flip arbitrary bits in that plaintext (and computing the modified tag value using the H value he learned); that means he can generate the ciphertext for any plaintext that's no longer than the original.
1
Reply
MichaelW avatar
in flag
MichaelW
hmmm. I have to 'digest' this first...maybe there is another question soon. But at the moment I'm overloaded ;-)
0
Reply
MichaelW avatar
in flag
MichaelW
Is my understanding right: For simplicity I refer to my image of the GCM algorithm: Lets say the attacker managed in some way to find out plaintext-1 and plaintext-2. Since he knows also Ciphertext-1 and Ciphertext-2, he can calculate back easily the values E_K(counter-1) and E_K(counter-2). Knowing this, he can now put in new values for Plaintext-1 and Plaintext-2 and calculate new Values for Ciphertext-1 and Ciphertext-2 plus a valid Tag. Did I understand correctly? It appears quite logical for me, but I'm not sure...anyway: it seems for me that GCM/GMAC is inherently a little dangerous...
0
Reply
poncho avatar
my flag
poncho
@MichaelW: yes, that's one way to put it. Actually, I'd express it in terms of bit flips (to flip this bit on the plaintext, we'd flip this bit of the the ciphertext, and so xor in this pattern into the tag so that it'd still validate); however what you have looks to be a valid approach.
1
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.