Source Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#!/usr/bin/python -u
import random
import string
import time
from base64 import b64encode, b64decode
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives.ciphers.aead import AESGCM
from cryptography.hazmat.primitives.kdf.scrypt import Scrypt
max_queries = 150
query_delay = 10
passwords = [bytes(''.join(random.choice(string.ascii_lowercase) for _ in range(3)), 'UTF-8') for _ in range(3)]
flag = open("flag.txt", "rb").read()
def menu():
print("What you wanna do?")
print("1- Set key")
print("2- Read flag")
print("3- Decrypt text")
print("4- Exit")
try:
return int(input(">>> "))
except:
return -1
print("Welcome!\n")
key_used = 0
for query in range(max_queries):
option = menu()
if option == 1:
print("Which key you want to use [0-2]?")
try:
i = int(input(">>> "))
except:
i = -1
if i >= 0 and i <= 2:
key_used = i
else:
print("Please select a valid key.")
elif option == 2:
print("Password?")
passwd = bytes(input(">>> "), 'UTF-8')
print("Checking...")
# Prevent bruteforce attacks...
time.sleep(query_delay)
if passwd == (passwords[0] + passwords[1] + passwords[2]):
print("ACCESS GRANTED: " + flag.decode('UTF-8'))
else:
print("ACCESS DENIED!")
elif option == 3:
print("Send your ciphertext ")
ct = input(">>> ")
print("Decrypting...")
# Prevent bruteforce attacks...
time.sleep(query_delay)
try:
nonce, ciphertext = ct.split(",")
nonce = b64decode(nonce)
ciphertext = b64decode(ciphertext)
except:
print("ERROR: Ciphertext has invalid format. Must be of the form \"nonce,ciphertext\", where nonce and ciphertext are base64 strings.")
continue
kdf = Scrypt(salt=b'', length=16, n=2**4, r=8, p=1, backend=default_backend())
key = kdf.derive(passwords[key_used]) #kdf.derive(passwords[key_used])
try:
cipher = AESGCM(key)
plaintext = cipher.decrypt(nonce, ciphertext, associated_data=None)
except:
print("ERROR: Decryption failed. Key was not correct.")
continue
print("Decryption successful")
elif option == 4:
print("Bye!")
break
else:
print("Invalid option!")
print("You have " + str(max_queries - query) + " trials left...\n")
Solution
After googling around, we found this paper which detailed a way of recovering the key from AES GCM using repeating nonces.
PS: I will be using the notation the paper uses so check on section 3 in particular if you aren’t sure about the notation I use
The attack
AES GCM works over GF(2^128) so all the operations work over that field.
One thing about AES GCM is that it is an Authenticated encryption with additional data (AEAD). In particular, GCM adds a tag at the end of of the ciphertext and computes it with the following equation:
\[T = C_1 \cdot H^{k-1} + ... + C_{k-1} \cdot H^2 + L \cdot H + E_K(N || 0^{31}1)\]Where L is the length of the ciphertext. Each block of the cipher text C_i is essentially considered a coefficient of a polynomial under GF(2^128)
The attack described consists in constructing a ciphertext and a tag from one nonce that is reused N and a set of keys K. Using this we can construct the following linear equation:
where \(H_i = E_{K_i}(0^n) = E_{K_i}(0^128)\)
and H_i is the associated GHASH to key i
Since each C_i is a coefficient of a polynimial, we essentially have a polynomial of degree k-1 on the left hand side. This results in a system of equation with k unkowns as follows
This is easily solvable using something like SAGEMATH for example.
The Implementation
The goal of the challenge is to recover 3 keys. To implement this attack, we do need to know the keyspace we are working with so that we can feed it or a slice of it to our collision function.
1
passwords = [bytes(''.join(random.choice(string.ascii_lowercase) for _ in range(3)), 'UTF-8') for _ in range(3)]
Thankfully, we are given this line which indicates that the 3 passwords can be chosen from the set of 3 lowercase letters ( more or less 17500 keys possible). Knowing this we can generate all possible keys before starting each collision:
1
2
3
4
5
6
7
8
9
10
11
12
13
for i in string.ascii_lowercase:
for j in string.ascii_lowercase:
for k in string.ascii_lowercase:
passwords.append(i+j+k)
keys = []
for pw in passwords:
#print(pw)
kdf = Scrypt(salt=b'', length=16, n=2**4, r=8, p=1, backend=default_backend())
key = kdf.derive(pw.encode())
#print(key)
keys.append(key)
The other problem we face is that we need to find said 3 keys in 150 queries or less:
1
2
3
max_queries = 150
#--SNIP--
for query in range(max_queries):
For this we decided to do a binary search but we still needed to know what slice length to use. We decided to go for 1000 since there is about 17500 that gives us 18 queries at first in the worst case adn with recursive binary search it would take around 10 more queries at most to find the correct key. This leaves us short of the 150 queries max: PERFECT.
Our implementation took around 1min to generate collisions for a slice of 1000 keys so we decided to precompute all slices of 1000 keys and then compute the rest on the fly.
Solve script
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
import time
from base64 import b64encode, b64decode
from pwn import *
from bitstring import BitArray
from string import ascii_lowercase
from itertools import product
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.primitives.ciphers.aead import AESGCM
from cryptography.hazmat.primitives.kdf.scrypt import Scrypt
from Crypto.Util.number import bytes_to_long, long_to_bytes
F.<X> = GF(2)[]
G.<x> = GF(2^128, modulus=X^128 + X^7 + X^2 + X + 1)
K.<y> = G[]
passwords = []
# passwords = [''.join(letters).encode() for letters in list(product(ascii_lowercase, repeat=3))]
for i in string.ascii_lowercase:
for j in string.ascii_lowercase:
for k in string.ascii_lowercase:
passwords.append(i+j+k)
keys = []
for pw in passwords:
#print(pw)
kdf = Scrypt(salt=b'', length=16, n=2**4, r=8, p=1, backend=default_backend())
key = kdf.derive(pw.encode())
#print(key)
keys.append(key)
def bytes_to_elt(in_bytes):
return G([int(v) for v in BitArray(in_bytes).bin])
def collide(keys, nonce, tag):
L_bytes = long_to_bytes(len(keys) * 128)
L_bytes = bytes([0]) * (16 - len(L_bytes)) + L_bytes
L = bytes_to_elt(L_bytes)
T = bytes_to_elt(tag)
pairs = []
for key in keys:
# print(key)
# print(type(key))
H_cipher = Cipher(algorithms.AES(key), modes.ECB(), backend=default_backend())
H_encryptor = H_cipher.encryptor()
H_bytes = H_encryptor.update(bytes([0]) * 16) + H_encryptor.finalize()
H = bytes_to_elt(H_bytes)
P_cipher = Cipher(algorithms.AES(key), modes.ECB(), backend=default_backend())
P_encryptor = P_cipher.encryptor()
P_bytes = P_encryptor.update(nonce + bytes([0]) * 3 + bytes([1])) + P_encryptor.finalize()
P = bytes_to_elt(P_bytes)
y = ((L * H) + P + T) * H^(-2)
pairs.append((H, y))
coeffs = K.lagrange_polynomial(pairs).list()
ciphertext = b''
for coeff in coeffs[::-1]:
cc = coeff.polynomial().list()
cc += [0] * (128 - len(cc))
ciphertext += BitArray(cc).bytes
ciphertext += bytes([0]) * 16 # tag at end
return ciphertext
# test it works
""" ciphertext = collide(keys[:3], bytes([0]) * 12, bytes([0]) * 16)
print(f"[+] CT created: {ciphertext}")
cipher = AESGCM(keys[0])
plaintext = cipher.decrypt(bytes([0]) * 12, ciphertext, associated_data=None)
print(f"[*] decrypted PT: {plaintext}") """
print(len(keys))
#print(passwords[0])
# ciphertext = collide(keys[:3], bytes([0]) * 12, bytes([0])*16)
# print(b64encode(b'0'*12)+b','+b64encode(ciphertext))
def binary_search(start, end):
pivot = (start + end) // 2
if start == pivot:
print(f'[+] Creating collision ciphertext of slice keys[{start}]')
print(f"key type = {type(keys[start])}")
ciphertext = collide([keys[start]], bytes([0]) * 12, bytes([0])*16)
print(f'[->] Sending cipher text of slice keys[{start}]')
conn.sendline(b'3')
conn.recvuntil(b'>>> ')
conn.sendline(b64encode(bytes([0]) * 12)+b','+b64encode(ciphertext))
response = conn.recvuntil(b'>>> ')
if b'ERROR: Decryption failed. Key was not correct' not in response:
print(f"[+] FOUND KEY: {passwords[start]}")
return start
else:
print(f"[+] FOUND KEY: {passwords[end]}")
return end
print(f'[+] Creating collision ciphertext of slice keys[{start}:{pivot}]')
ciphertext = collide(keys[start:pivot], bytes([0]) * 12, bytes([0])*16)
print(f'[->] Sending cipher text of slice keys[{start}:{pivot}]')
conn.sendline(b'3')
conn.recvuntil(b'>>> ')
conn.sendline(b64encode(bytes([0]) * 12)+b','+b64encode(ciphertext))
response = conn.recvuntil(b'>>> ')
if b'ERROR: Decryption failed. Key was not correct' not in response:
return binary_search(start, pivot)
else:
return binary_search(pivot, end)
#context.log_level = 'debug'
conn = remote('pythia.2021.ctfcompetition.com', 1337)
with open('ciphers.p', 'rb') as f:
ciphers = pickle.load(f)
key_list = []
conn.recvuntil(b'>>> ')
for j in range(3):
print(f'[+] Setting key to {j}')
conn.sendline(b'1')
conn.recvuntil(b'>>> ')
conn.sendline(str(j).encode())
conn.recvuntil(b'>>> ')
for i in range(0, len(keys), 1000):
print(f'[+] Creating collision ciphertext of slice keys[{i}:{i+1000}]')
ciphertext = ciphers[i // 1000] # collide(keys[i:i+1000], bytes([0]) * 12, bytes([0])*16)
print(f'[->] Sending cipher text of slice keys[{i}:{i+1000}]')
conn.sendline(b'3')
conn.recvuntil(b'>>> ')
conn.sendline(b64encode(bytes([0]) * 12)+b','+b64encode(ciphertext))
response = conn.recvuntil(b'>>> ')
print(response)
if b'ERROR: Decryption failed. Key was not correct' not in response:
key_list.append(passwords[binary_search(i, i+1000)].encode('utf-8'))
break
if len(key_list) == 3:
conn.sendline(b'2')
conn.recvuntil(b'>>> ')
conn.sendline(b''.join(key_list))
stuff = conn.recvuntil(b'>>> ')
print(stuff)
FLAG: CTF{gCm_1s_n0t_v3ry_r0bust_4nd_1_sh0uld_us3_s0m3th1ng_els3_h3r3}