AES-128-CFB repeated IV and KPA

Question

I'm doing reverse-engineering a product and identified a critical issue with it. The work is done and the developer was notified, but for my own personal curiosity, I'd like to learn how to exploit it so I can make a small write-up.

The short of it is, the developer is using a fixed key and IV for encrypting multiple similar messages using AES-128-CFB. Since I know the IV for all messages, and I know parts of the plaintext (the messages have a standard format, JSON), can I recover the plaintext or key? I'm not looking for someone to do this for me, I'm just looking for how I would tackle this.

Below is a small replication of what is happening, and I noticed that the output is very similar which leads me to believe that is can be cracked.

import base64
from Crypto.Cipher import AES


key = b'\x00'*16
iv  = b'\xFF'*16
p1  = b'Hello, world'
p2  = b'Hello, world!'

cipher = AES.new(key, AES.MODE_CFB, iv=iv)
c1 = cipher.encrypt(p1)
e1 = base64.b64encode(c1)

cipher = AES.new(key, AES.MODE_CFB, iv=iv)
c2 = cipher.encrypt(p2)
e2 = base64.b64encode(c2)


print(' '.join('{:02X}'.format(c) for c in c1))
print(' '.join('{:02X}'.format(c) for c in c2))
print(e1.decode())
print(e2.decode())

$ python3 test.py
77 6D 0C 86 D8 6B C9 9F 72 FD F4 3B
77 6D 0C 86 D8 6B C9 9F 72 FD F4 3B 04
d20MhthryZ9y/fQ7
d20MhthryZ9y/fQ7BA==

Answer 1

First of all, as you've noticed, the first part is always the same. So if you have two ciphertext that are identical in the first bytes produced you can immediately see that this is the case. That's the first leak.

What you can do is to XOR the first block of ciphertext that differ. What you get back is a XOR of the plaintext of the two messages that were encrypted. You can then XOR any of the bits that you know and immediate get the plaintext of the other message at those locations. It's also possible to use known information to guess, e.g. if it is English then the XOR of characters A and B will produce output 0x03 as only the last two bits differ. Note that you can do this with any pair of ciphertext that you get. That way you can quickly get information about the blocks of plaintext.

It would of course help if you have an encryption oracle. In that case you can simply feed it guessed plaintext or plaintext that helps you with the XOR trick.

---

Now onto the things you cannot do.

First of all, the AES block cipher - or any known secure cipher - will not allow you to get the key even if you have multiple plaintext / ciphertext pairs (to the block cipher).

Secondly, you won't be able to guess the IV if it isn't indicated, as it is a plaintext block to the block cipher.

Finally, it is impossible to get to the plaintext when the previous block of ciphertext differs from all the others. In that case the block cipher generates what is basically random bytes, and you can therefore not retrieve any information about the corresponding plaintext block after it has been XOR'ed.

Image is Wikimedia Commons, by Gwenda.