This is a writeup of the AES-128 TSB challenge from Teaser Dragon CTF 2018
Prompt
Haven’t you ever thought that GCM mode is overcomplicated and there must be a simpler way to achieve Authenticated Encryption? Here it is!
Server: aes-128-tsb.hackable.software 1337
Introduction
The Advanced Encryption Standard, or AES, is a widely used block cipher. A block cipher works by performing a transformation on fixed-length of bits using a predefined secret key. The 128 in AES-128 indicates that the encryption is using 16 byte blocks (16 * 8 = 128). TSB indicates that the mode of encryption, which in this case is unique to the challenge. The most basic mode of encryption is ECB which splits the plaintext into fixed length blocks, applies the block cipher to each, and then appends the results back together.
AES-128-TSB is an implementation of the AES cipher similar to AES-128-CBC. CBC encryption works by XORing the plaintext with the previous ciphertext block before applying the block cipher to it. On the initial run, there is no previous block, so a randomly generated block called the Initialization Vector (IV) is used. By XORing with each previous ciphertext block, we ensure that consecutive blocks are influenced by any prior changes. So any change in the first block would impact every other block.
The code snippet below shows the algorithm being used by TSB for encryption.
def tsb_encrypt(aes, msg):
msg = pad(msg)
iv = get_random_bytes(16)
prev_pt = iv
prev_ct = iv
ct = ''
for block in split_by(msg, 16) + [iv]:
ct_block = xor(block, prev_pt)
ct_block = aes.encrypt(ct_block)
ct_block = xor(ct_block, prev_ct)
ct += ct_block
prev_pt = block
prev_ct = ct_block
return iv + ct
Internally the AES encryption used is ECB, however similar to CBC, additional XOR operations are done. Unlike CBC, the current plaintext block is also XOR’d with the previous plaintext block before encryption. Similar to CBC, the ciphertext block is also XOR’d with the previous ciphertext block. On the intial run, the IV is used for both XOR operations.
The encryption algorithm above also encrypts the IV as shown by the line:
for block in split_by(msg, 16) + [iv]:
It then sends the IV prepended to the ciphertext.
The code snippet below shows the algorithm being used by TSB for decryption.
def tsb_decrypt(aes, msg):
iv, msg = msg[:16], msg[16:]
prev_pt = iv
prev_ct = iv
pt = ''
for block in split_by(msg, 16):
pt_block = xor(block, prev_ct)
pt_block = aes.decrypt(pt_block)
pt_block = xor(pt_block, prev_pt)
pt += pt_block
prev_pt = pt_block
prev_ct = block
pt, mac = pt[:-16], pt[-16:]
if mac != iv:
raise CryptoError()
return unpad(pt)
During decryption, the decrypted IV is checked against the original IV being sent as shown by the line:
if mac != iv:
raise CryptoError()
AES only works when each block is of the same length, however it cannot be guaranteed that the plaintext can be evenly divided. Therefore, padding is usually added to the end of the plaintext to ensure that every block has the same length.
The padding used in TSB is shown in the code snippet below:
def pad(msg):
byte = 16 - len(msg) % 16
return msg + chr(byte) * byte
def unpad(msg):
if not msg:
return ''
return msg[:-ord(msg[-1])]
The pad function finds how many bytes are need to make the plaintext divisible by 16. Then, it appends to the plaintext the amount needed to make it divisible by 16. The padding used is the ascii character corresponding to the number of bytes missing.
The unpad function checks the last character of the message and finds the decimal equivalent of the ascii character. It then removes that number of bytes from the end of the message, which should equal to the number of bytes of padding if the pad function was used.
The challenge also allows us to check whether a ciphertext decrypts to a message. This is shown in the code snippet below:
a = recv_binary(s)
b = recv_enc(s, aes)
print('b', b)
if a == b:
if a == 'gimme_flag':
send_enc(s, aes, FLAG)
else:
# Invalid request, send some random garbage instead of the
# flag :)
send_enc(s, aes, get_random_bytes(len(FLAG)))
else:
send_binary(s, 'Looks like you don\'t know the secret key? Too bad.')
The variable a is the plaintext that we send the server. The variable b is the decrypted ciphertext that we send the server. The TSB server lets us know if the two values match. If the values match and the value is ‘gimme_flag’ we are given the encrypted flag.
Observations
We control the IV being used for decryption and the message being decrypted. However, the encrypted IV is expected to be at the end of the message. Since we do not know the secret key being used by the server, we have no way of appending the proper encrypted IV to the end of our message.
On the initial block of the decryption, there is a unique case where the IV is used for both the prev_pt and the prev_ct. If we only send two blocks where the first is our message and the second is the IV, we can bypass the encrypted IV check as shown below:
Original decryption method:
pt_block = xor(block, prev_ct)
pt_block = aes.decrypt(pt_block)
pt_block = xor(pt_block, prev_pt)
For the first block (message):
prev_pt = IV
prev_ct = IV
block = message
to_decrypt = xor(message, IV)
decrypted = aes.decrypt(to_decrypt)
plaintext = xor(decrypted, IV)
On the second block (IV):
prev_pt = plaintext
prev_ct = message
block = IV
to_decrypt = xor(IV, message)
decrypted = aes.decrypt(to_decrypt)
mac = xor(decrypted, plaintext)
mac = xor(decrypted, decrypted, IV)
mac = IV
With AES-ECB decrypting the same value always has the same result. We take advantage of the fact that XOR is commutative to ensure that the same text is being decrypted in both blocks. When a value is XOR’d by itself, the result is 0, therefore xor(decrypted, decrypted) is always 0. When a value is XOR’d by 0, it is unchanged, therefore the resulting mac will always equal to IV, passing the encrypted IV check.
Knowing this, we can pass our own ciphertext to the server without it returning a CryptoError. However, we still cannot predict what the decrypted plaintext will be.
My goal at this point was to somehow send a ciphertext that decrypted to ‘gimme_flag’ to the server and retrieve the encrypted flag. However, all blocks need to be 16 bytes long. Taking advantage of the unpad function we can send ‘gimme_flag—–\x06’. The unpad function will remove 6 bytes from the end, resulting in just ‘gimme_flag’.
The value of IV and message do not matter. As long as we send IV as the second block of our ciphertext, it will pass all checks. Playing around with the XORs I noticed something interesting.
If IV was equal to xor(decrypted, ‘gimme_flag—–\x06’):
prev_pt = IV
prev_ct = IV
block = message
to_decrypt = xor(message, IV)
decrypted = aes.decrypt(to_decrypt)
plaintext = xor(decrypted, IV)
plaintext = xor(decrypted, decrypted, 'gimme_flag-----\x06')
plaintext = 'gimme_flag-----\x06'
In order for this to work however, the value of decrypted would have to be known. Therefore, I sought out to find what the value of aes.decrypt(0) would be. 0 would be easiest as just setting IV equal to message (XORing equal values results in 0) would result in decrypting 0.
Exploit
If we can control the value of the last byte of plaintext, we can control the length of the unpadded plaintext. The server indicates whether your decrypted ciphertext matches the plaintext you send. Therefore, If we can set the last byte to be 0x15, we can make the length 1. We can then brute force the 1 character by checking against all possible 256 ascii characters. Once we know the first character, we can make the length 2 and brute force the second character and so on.
If we set IV equal to 15 null bytes with the 16th byte being our filter, we can control the length of resulting plaintext while leaving the first 15 bytes of the decryption untouched. However, we need to be able to detect when the last byte is 0x15 in order to start brute forcing the value of the decryption.
response = ""
filter = 0
while response != "Looks like you don't know the secret key? Too bad.":
r = remote('aes-128-tsb.hackable.software', 1337)
iv = chr(0) * 15 + chr(filter)
message = iv * 2
ciphertext = iv + message
r.sendline(p32(0) + '' + p32(len(ciphertext)) + ciphertext)
r.recv(1024)
response = r.recv(1024)
if filter > 255:
break
print(filter)
We send an empty plaintext and our modified ciphertext with the last byte filter. When the response indicates that our plaintext and the decrypted ciphertext do not match, we know that our filter resulted in a byte that was less than or equal to 0x15 because the decrypted ciphertext was not empty.
At this point we only know that our filter XORd into a value that is less than 0x15. The unpad function uses python string splicing. If the last byte is 0, then the unpadded message would be blank since string[:0] results in an empty string.
From here we change only the last 4 bits of the filter until the ciphertext decrypts into empty string as shown below:
initial_filter = 160
for x in range(16):
upper_bits = bin(initial_filter)[:-4]
b_num = bin(x).replace('0b', '')
while len(b_num) != 4:
b_num = '0' + b_num
filter = int(test + b_num, 2)
r = remote('aes-128-tsb.hackable.software', 1337)
iv = chr(0) * 15 + chr(filter)
message = iv * 2
ciphertext = iv + message
r.sendline(p32(0) + '' + p32(len(ciphertext)) + ciphertext)
r.recv(1024)
response = r.recv(1024)
if response != "Looks like you don't know the secret key? Too bad.":
print(filter)
break
Now that we know the filter that results in a XOR result of 0, we can control the last byte. Lets say for example that we got 167 as the filter. We know that two numbers can only XOR into 0 when they are equal.
167 = 1010 0111
1010 0111
1010 0111
---------
0000 0000
168 = 1010 1000
1010 0111
1010 1000
---------
0000 1111
15 = 0000 1111
169 = 1010 1000
1010 0111
1010 1001
---------
0000 1110
14 = 0000 1110
As shown above, we can easily control how many bytes are removed with the unpad function by incrementing our filter.
With this, we can start to brute force out the value of aes.decrypt(0):
leak_list = []
filter = 168
curr = 15
while curr > 0:
response = "Looks like you don't know the secret key? Too bad."
curr_char = 0
while response == "Looks like you don't know the secret key? Too bad.":
r = remote('aes-128-tsb.hackable.software', 1337)
iv = chr(0) * 15 + chr(filter)
message = iv * 2
ciphertext = iv + message
leak = ''.join([chr(i) for i in leak_list])
r.sendline(p32(len(leak)) + leak + chr(curr_char) + p32(len(ciphertext)) + ciphertext)
r.recv(1024)
response = r.recv(1024)
r.close()
curr_char += 1
leak_list.append(curr_char - 1)
filter += 1
curr -= 1
print(leak_list)
We do not get the last byte with this method since it is used for the padding trick. However, we can try all possibilities until an encrypted flag is returned
iv = xor(leak + chr(curr_char), 'gimme_flag-----' + '\x06')
message = iv * 2
ciphertext = iv + message
r.sendline(p32(len(10)) + 'gimme_flag' + p32(len(ciphertext)) + ciphertext)
With the encrypted flag, we can attempt to use the same method to leak out the decrypted blocks. For the first block, we know that the decryption algorithm XORs the IV with the current block and then AES decrypts the result. On consecutive blocks, we can treat the previous block as our IV. We know that XORing two values does not result in a unique value. We also know that the result of AES decrypt is XOR’d by our IV.
First we XOR the last byte of the original IV and message. We modify the last byte of our IV and then find another byte such that the XOR of the bytes are equivalent to the original. Our modified IV and message will XOR into the same value, therefore the same value is being AES decrypted. However, we can control how many bytes the padding cuts off and brute force the result of the decryption.
# target = filter ^ target ^ filter
target = ord(xor(head, iv_orig)[-1])
msg_orig = msg_orig[:-1]
iv_orig = iv_orig[:-1]
iv = msg_orig + chr(filter)
msg = iv_orig + chr(target ^ filter) + iv
ciphertext = iv + msg
Again we will only be able to leak out 15 bytes of the flag at a time, but the 16th byte is very clear from looking at the flag.
Consecutive blocks are XOR’d with the previous block decrypted. So after, leaking out the decrypted value, we XOR the result with the previous 16 bytes of the flag which we have already found.
DrgnS{Thank_god_no_one_deployed_this_on_production}