Crib Dragging: Why You Shouldn’t Ever Reuse a Nonce With the Same Key in AES-GCM?
Hermione’s stolen treasure
One fine night while reading some secret book in the library, Hermione found a secret goblin treasure. She needs help from her dear friend and lover Harry and Ron.
So she wrote to Harry
Dear Harry, I’ve found a goblin secret. meet me at the library.
My Love Ron, I’ve found a goblin secret. meet me at the library.
Now, there is this Malfoy guy, who’ll always sneak into the letter they exchange. But Hermione is a clever girl. She encrypts these two plaintexts in AES-128-GCM with the shared secret key only the three knows. She sent the letter and wait impatiently for the other two to join her. After they came upon receiving Hermione’s secret message. They set their foot into the secret passage to get the treasure. after much hassle when they arrived at the scene. The treasure was already gone.
How in the world that happened?
Before we investigate what Hermione did wrong, let’s make us all comfy and cozy with some terminologies.
AES: Advanced Encryption Standard (AES) is a symmetric-key block cipher. given a 128bit plaintext with a 128bit secret key. It’ll output 128bit of ciphertext. The secret key can be of 192 bit and 256bit too.let’s take a 128bit key today.
GCM: Galois/Counter Mode (GCM) is a mode of operation for symmetric-key block ciphers(like AES) which not only takes care of encryption but also authentication. We’ll be only talking about the encryption part(the CM part from GCM) here.
Counter Mode: What will happen when you want to encrypt something larger than 128bit in size? the counter mode helps you do just that by chopping up your plaintext into 128bit chunks and tag them with Counter(1,2,3…).
Nonce: Tagging the chunks with only counter makes them very predictable and simple.How about adding a random string with the counter? that’s nonce for you. It’s a 96bit string concatenated with a 32bit integer counter that we already have, which makes a total of 128bit of random string that is a little less predictable.
If you look closely enough you’ll see the counter mode never encrypts the plaintext! what kind of sorcery is this?
What it does, it encrypts the 128bit nonce-counter with the given secret key and what comes out of that AES box is an intermediate key material, let’s denote it by IKM.which is then XORed with the plaintext and result in a ciphertext.
IKM = Intermediate Key Material
Though the nonce is the same, the counter is different(1,2,3) for every block, which results in a different IKM for every block. Different IKM will always translate to different ciphertext. So no risk of having any sort of repeated pattern in the ciphertext, unlike ECB mode. clever, isn’t it?
How do you decrypt your ciphertext? you don’t need any decryption method at all! no, I’m not joking, I’m dead serious. What you’ll do for each block, you’ll generate the IKM the same way as you did during encryption and XOR it with your ciphertext block. Why that works? XORing something twice undoes itself. awesome, isn’t it?
An advantage of using the counter mode over other available modes like CBC is, it’s parallelizable. You can jump to any block and decrypt it independently; especially useful for movie streaming sites. If I don’t like the first 30mins of a movie, I can skip that part instantly, no problem.
Now that we are armed with all the knowledge to investigate Hermione’s case. let’s dig in.
Hermione was very excited discovering the secret, she impatiently used the same nonce twice for sending the two messages to Harry and Ron. You may ask,
So what? the key is still secret. How the hell Malfoy got to the treasure first?
What’s wrong with reusing a nonce?
As the key remains the same, it’ll produce the identical 128bit intermediate key material(IKM) in both cases, which will then be XORed with the plaintext block to generate the ciphertext block. As the messages are different, the generated ciphertext will be different. Where is the problem then?
P1 = Dear Harry, I’ve found a goblin secret. meet me at the library.P2 = My Love ron, I’ve found a goblin secret. meet me at the library.
Now let’s look at the encryption process. Remember the counter mode we discussed earlier?
C1 = P1 ⊕ IKM
C2 = P1 ⊕ IKM
What if we XOR the two ciphertexts C1 and C2?
C1 ⊕ C2 = (P1 ⊕ IKM) ⊕ (P2 ⊕ IKM) = (P1 ⊕ P2) ⊕ (IKM ⊕ IKM) = (P1 ⊕ P2)
You know Malfoy is from Slytherin, he is a clever guy. He can guess some words that could be in the letter, we call it the crib!
If he guesses Dear, let’s see what’ll happen. We’ll XOR this crib with our C1 ⊕ C2 = P1 ⊕ P2 equation.
Crib = Dear
C1 ⊕ C2 = P1 ⊕ P2
leaked_message = C1 ⊕ C2 ⊕ Crib = My l Dear Harry.............
⊕ My love................
We know XORing something with itself will always result in 0 and XORing something with 0 will always result in itself.
As Malfoy knows something is going on between Hermione and Ron. He can easily guess that My l translates to My love. Let’s try it now as our new crib,
Crib = My love
C1 ⊕ C2 = P1 ⊕ P2
leaked_message = C1 ⊕ C2 ⊕ Crib Dear Harry.............
⊕ My love................
⊕ My love
Dear Ha will translate to Dear Harry. Come on! Even I can guess it.
So you got the idea? Malfoy can keep dragging the crib and leaked more messages until he reaches the end. Then,
IKM = (C1 ⊕ P1)
Once you figure out a plaintext. simply XORing with its corresponding ciphertext will tell you the IKM. Now that you know the IKM, you can decrypt the second one and any subsequent messages sent with the same key and nonce combination without ever needing to know the key.
Now you know
Hermione, if you’re reading this, never reuse a nonce-key combination to send messages in AES-GCM or naughty Malfoy will read everything.