Analysis of the scheme
Source code we’re dealing with:
#!/usr/local/bin/python
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os
from secrets import token_bytes
from flag import FLAG
KEY = token_bytes(16)
FLAG_IV = token_bytes(16)
CHOSEN_PLAINTEXT_IV = token_bytes(16)
def regenerate_constants():
global KEY, FLAG_IV, CHOSEN_PLAINTEXT_IV
KEY = token_bytes(16)
FLAG_IV = token_bytes(16)
CHOSEN_PLAINTEXT_IV = token_bytes(16)
if FLAG_IV == CHOSEN_PLAINTEXT_IV:
regenerate_constants()
def encrypt_flag():
cipher = AES.new(KEY, AES.MODE_CFB, FLAG_IV)
encrypted_flag = FLAG_IV + cipher.encrypt(pad(FLAG.encode(), 16))
return encrypted_flag
def encrypt_chosen_text(text):
cipher = AES.new(KEY, AES.MODE_CFB, CHOSEN_PLAINTEXT_IV)
encrypted_text = CHOSEN_PLAINTEXT_IV + cipher.encrypt(pad(text, 16))
return encrypted_text
def main():
regenerate_constants()
while True:
print("Choose an option:")
print("1. Encrypt flag")
print("2. Encrypt chosen text")
print("3. Regenerate constants")
print("4. Exit")
choice = input("Enter your choice: ")
if choice == '1':
encrypted_flag = encrypt_flag()
print(f"Encrypted flag: {encrypted_flag.hex()}")
elif choice == '2':
text = bytes.fromhex(input("Enter text to encrypt (in hex): "))
encrypted_text = encrypt_chosen_text(text)
print(f"Encrypted text: {encrypted_text.hex()}")
elif choice == '3':
regenerate_constants()
print("Regenerated constants!")
elif choice == '4':
print("Goodbye!")
exit()
else:
print("Invalid choice. Please try again.")
if __name__ == "__main__":
main()
The first thing to notice with the challenge is that it’s using AES-CFB. One well known fact about AES-CFB is that the encryption function is identical to the decryption function, so the first thought is that we can just decrypt the flag by encrypting the encrypted flag! Unfortunately, this is only true if the cipher has the same inputs, which in our case is not true due to the IV being unique for the flag encryption and for the chosen plaintext encryption. Review this diagram of AES CFB running in full block feedback mode, this is the most commonly known mode, and pretty much what you’ll see if you search for any diagrams online.
But, is that really what our cipher is doing?
If every diagram online seems to show the same thing, and we’re just importing a library, we must be in line with the diagram, right? In this case no, there are additional CFB modes that are less documented in general overviews. The most relivent one in our case is CFB-8, in this mode instead of the whole output block feeding back into the input for the cipher, 15 of the last input blocks are combined with a single byte from the new output to make the next input, working byte by byte. See the following diagram:
Suprisingly, this is actually the mode that python defaults to!
Breaking the static IV
Ignoring decrypting the flag for a moment, how can we break encrypted inputs that we choose, knowing they all have the same IV? The answer is fairly simple, we just have to re-encrypt the encrypted segment one at a time, ensuring that every segment before the one we’re decrypting has the same state. Let’s do a quick example:
Enter text to encrypt (in hex): 42
Encrypted text: 0b5fd2b1251206e2057dc541ae8aaa4f6bb4d8cb68cce5c215580c0d18758ede
Choose an option:
1. Encrypt flag
2. Encrypt chosen text
3. Regenerate constants
4. Exit
Enter your choice: 2
Enter text to encrypt (in hex): 6b
Encrypted text: 0b5fd2b1251206e2057dc541ae8aaa4f42e398a8602df1644feaf5db3c98785d
You might look at that and say, “WHERE WAS THE BLOCK????”, the block was the single 6b byte directly following the IV, the reason the byte is not at the end of the message is because despite everything actually being done on segments, the challenge still pads the input to 16 byte blocks. So in our example, the CHOSEN_PLAINTEXT_IV is 0x0b5fd2b1251206e2057dc541ae8aaa4f, and the segment we care about is 60xb. Re-encrypting 0x6b does in fact get us our plaintext of 0x42. We can’t simple decrypt multiple bytes in a row, because remember that output of the cipher will go into the encryption for each following byte. However, we can get the next bytes if we take that first byte and prepend that to our input, as the output will match the original encrypted output, meaning the cipher’s state remains as expected. Our padded plaintext should be 0x420f0f0f0f0f0f… and so on. Decrypting the next byte of the ciphertext with the method described does in fact give us 0x0f, showing the method works.
Enter text to encrypt (in hex): 42b4
Encrypted text: 0b5fd2b1251206e2057dc541ae8aaa4f6b0f30cb2dc081809b6b3288dc515fb9
Breaking the alternate IV
This method works great for an IV that we can append to, but in the challenge, the flag has an entirely unique IV that we can’t use. How can we possibly decrypt that? The answer, is we need to get the CFB cipher into the same state it was in immediately after injesting the FLAG_IV. We know that output is fed back into the CFB8 cipher one byte at a time, replacing bytes of the input, until all 16 bytes are fully controlled by ciphertext. With that in mind, we can forge whatever state we want for the cipher, since our IV is static. Take the following example: We have an IV of 0x000102030405060708090a0b0c0d0e0f, but we want an IV of 0x0102030405060708090a0b0c0d0e0faa, we can get to exactly this state just by giving the cipher an input that will encrypt to \xaa with the initial IV of 0x000102030405060708090a0b0c0d0e0f, as it will trim the first byte off the state, then append the ciphertext. After that, we can append our actual byte we want encrypted to the input, and it will encrypt exactly as if it had the desired IV. Continuing this futher, we can replace the entire IV, one byte at a time, simply by bruteforcing which inputs will get us the desired ciphertext outputs.
Solve script
from pwn import *
import binascii
from Crypto.Util.Padding import unpad
HOST = "kubenode.mctf.io"
PORT = 30007
def get_encrypted_flag():
"""
Sends a request to the server to encrypt the flag and returns the IV and ciphertext.
"""
io.sendlineafter(b"Enter your choice: ", b"1")
io.recvuntil(b"Encrypted flag: ")
encrypted_flag_hex = io.recvline().strip().decode()
encrypted_flag = bytes.fromhex(encrypted_flag_hex)
iv, ciphertext = encrypted_flag[:16], encrypted_flag[16:]
return iv, ciphertext
def encrypt_chosen_text(text):
"""
Sends a known plaintext to the oracle for encryption and returns the IV and ciphertext.
"""
io.sendlineafter(b"Enter your choice: ", b"2")
io.sendlineafter(b"Enter text to encrypt (in hex): ", binascii.hexlify(text).decode())
io.recvuntil(b"Encrypted text: ")
encrypted_text_hex = io.recvline().strip().decode()
encrypted_text = bytes.fromhex(encrypted_text_hex)
iv, ciphertext = encrypted_text[:16], encrypted_text[16:]
return iv, ciphertext
def forge_iv(desired_iv):
"""
Forges the IV to match the desired IV using the technique from app_with_semisolution.py.
"""
forge = b""
for i, c in enumerate(desired_iv):
for j in range(0, 256):
test_byte = bytes([j])
encrypted_text = encrypt_chosen_text(forge + test_byte)[1]
if i == 15:
check_byte = encrypted_text[-32 + i]
else:
check_byte = encrypted_text[-16 + i]
if check_byte == c:
forge += bytes([j])
break
return forge
def recover_flag():
"""
Recovers the flag byte-by-byte by leveraging the oracle.
"""
# Get the encrypted flag
iv_flag, flag_ciphertext = get_encrypted_flag()
# Forge the IV to match the flag's IV
forged_iv = forge_iv(iv_flag)
flag_bytes = b""
while len(flag_ciphertext) > 0:
iv, flag_pt_bytes = encrypt_chosen_text(forged_iv + flag_bytes + flag_ciphertext)
flag_bytes += bytes([flag_pt_bytes[16+len(flag_bytes)]])
flag_ciphertext = flag_ciphertext[1:]
return(unpad(flag_bytes,16))
if __name__ == "__main__":
io = remote(HOST, PORT)
# Recover the flag using the chosen plaintext attack
flag = recover_flag()
print(f"Recovered Flag: {flag}")
Flag
And that gets us the flag: MetaCTF{byt3_by_byt3_w3_br34k_th3_s7at1c_iv}