This new pesky mode of CBC makes decrypting too hard >:(
ncat --ssl peskycbc.atreides.b01lersc.tf 8443Attachments: pesky_cbc.py
In pesky_cbc.py:
import secrets
from Crypto.Cipher import AES
try:
with open('./flag.txt', 'r') as f:
flag = f.read()
except:
flag = 'bctf{REDACTED}'
key1 = secrets.token_bytes(32)
key2 = secrets.token_bytes(32)
def pesky_decrypt(ciphertext):
assert len(ciphertext) % 16 == 0
iv1 = secrets.token_bytes(16)
iv2 = secrets.token_bytes(16)
c1 = AES.new(key1, AES.MODE_CBC, iv1)
c2 = AES.new(key2, AES.MODE_CBC, iv2)
return c1.decrypt(c2.decrypt(ciphertext))
def main():
cipher = AES.new(key2, AES.MODE_ECB)
secret = secrets.token_bytes(16)
ciphertext = cipher.encrypt(secret)
print('Here is the encrypted secret:')
print(ciphertext.hex())
print()
print('Here are some hints for you ^_^')
for _ in range(8):
random_value = secrets.token_bytes(16)
ciphertext = cipher.encrypt(random_value)
print(random_value.hex())
print(ciphertext.hex())
print()
while True:
print('Options:')
print('1: pesky decrypt')
print('2: guess secret')
choice = input('>> ').strip()
if choice == '1':
ciphertext = bytes.fromhex(input('>> '))
print(pesky_decrypt(ciphertext).hex())
elif choice == '2':
guess = bytes.fromhex(input('>> '))
if secret == guess:
print('Here is your flag :)')
print(flag)
return
else:
print('lmao skill issue')
return
else:
print('Invalid Choice')
return
if __name__ == '__main__':
main()This challenge involves attacking a custom CBC decryption oracle. The server generates two 32-byte AES keys pesky_decrypt(). The oracle is unusual because it applies CBC decryption twice, first with
The server also provides 8 random plaintext/ciphertext pairs under
Recall that in classic CBC decryption, each plaintext block is XORed with the previous ciphertext block:
It gets somewhat more complicated with pesky_decrypt() since CBC is nested twice:
Notice that both
-
$P_2,P_3,...P_n$ are all exactly the same equation except for which$C_i$ they depend on. We can therefore focus on a single block (e.g.$P_2$ ) and ignore the rest. - Since AES is secure and nothing is known about
$k_1$ , it is easier to treat$DEC_{k1}$ as a black box function$F$ . It simply maps some 16-byte input to another 16-byte output, but we don't know anything else about it. - The final XOR with
$C_i$ at the end does not provide any extra information, and it can therefore be set to any arbitrary value.
Let's attempt to simplify pesky_decrypt() by defining a new oracle,
Note that pesky_decrypt() directly can also be obtained by just querying pesky_decrypt():
def D(C1, C2):
# D(C1, C2) = F(DEC(C2) ^ C1) ^ DEC(C1)
assert len(C1) == len(C2) == 16
return pesky_decrypt(b'\x00' * 16 + C1 + C2)[32:48]From now on, let's ignore pesky_decrypt() and work exclusively with
Recall that the goal is to decrypt
Now we have
In other words, we want another input pair
This comes back to the 8 plaintext/ciphertext pairs we get for free in the beginning. For brevity I'll label these pairs as
which implies that
Knowing this, suppose we make two calls to
It follows that
Now this is interesting! Everything on the LHS is known, so if we can find
To rephrase the above differently, we converted the problem of decrypting
We already know that
Unfortunately, only 8 values of
So we need to generate 120 additional plaintext/ciphertext pairs, given what we have so far. Is this possible?
Let's go back and experiment with
Rearranging, we get
How does this help us find pairs for
Recall that since we now know the value of
Since
Ok, so given 224 + 8
The answer is linear algebra! This is essentially solving the XOR subset sum problem, which unlike the subset sum problem has a
polynomial time solution in
Gaussian elimination is perfectly valid
We have everything needed to solve this challenge, so the rest is about implementation. I imagine there are several ways to implement
the logic that solves
The unknown part of the equation is
Let's unpack one more layer...
We're essentially peeling back layers of
For the linear algebra part, we can just use SageMath's .solve_right() which has a built-in GF(2) solver:
def xor_subset_sum(nums, target):
from sage.all import GF, matrix, vector
# introduce extra `+ [1]` constraint to ensure an even-length subset
mat = matrix(GF(2), [[(x >> i) & 1 for i in range(128)] + [1] for x in nums])
vec = vector(GF(2), [(target >> i) & 1 for i in range(128)] + [0])
return mat.T.solve_right(vec)Here is the final solution script:
from pwn import *
from functools import reduce
def xor(*a):
assert all(len(x) == 16 for x in a)
return bytes([reduce(int.__xor__, x) for x in zip(*a)])
def pesky_decrypt(ct):
io.sendlineafter(b'>> ', b'1')
io.sendlineafter(b'>> ', ct.hex().encode())
return bytes.fromhex(io.recvline().decode())
def D(C1, C2):
# D(C1, C2) = F(DEC(C2) ^ C1) ^ DEC(C1)
assert len(C1) == len(C2) == 16
return pesky_decrypt(b'\x00' * 16 + C1 + C2)[32:48]
# io = process(['python', 'pesky_cbc.py'])
io = remote('peskycbc.atreides.b01lersc.tf', 8443, ssl=True)
io.recvuntil(b'Here is the encrypted secret:\n')
s_enc = bytes.fromhex(io.recvline().decode())
io.recvuntil(b'Here are some hints for you ^_^\n')
k2_pairs = []
for _ in range(8):
X = bytes.fromhex(io.recvline().decode())
Y = bytes.fromhex(io.recvline().decode())
k2_pairs.append((X, Y))
k1_dec = {}
for x1, y1 in k2_pairs:
for x2, y2 in k2_pairs:
c = xor(y1, x2)
p = xor(D(y1, y2), x1)
k1_dec[c] = p
k2_dec = {}
for x1, y1 in k2_pairs[:3]:
for x2, y2 in k2_pairs:
for x3, y3 in k2_pairs:
if x1 != x2:
c = xor(x1, x2, y3)
p = xor(D(c, y1), k1_dec[xor(x2, y3)])
k2_dec[c] = p
def xor_subset_sum(nums, target):
from sage.all import GF, matrix, vector
# introduce extra `+ [1]` constraint to ensure an even-length subset
mat = matrix(GF(2), [[(x >> i) & 1 for i in range(128)] + [1] for x in nums])
vec = vector(GF(2), [(target >> i) & 1 for i in range(128)] + [0])
return mat.T.solve_right(vec)
X_0, Y_0 = k2_pairs[0]
# find a subset of plaintexts whose xor is `s_enc ^ Y_0`
k2_dec_pairs = [(pt, ct) for ct, pt in k2_dec.items()]
plaintexts = [int.from_bytes(pt) for pt, _ in k2_dec_pairs]
solution = xor_subset_sum(plaintexts, int.from_bytes(xor(s_enc, Y_0)))
soln_pairs = [(pt, ct) for b, (pt, ct) in zip(solution, k2_dec_pairs) if b]
secret = X_0
acc = s_enc
for i in range(len(soln_pairs)):
secret = xor(secret, D(acc, soln_pairs[i][1]))
if i % 2 == 0:
acc = xor(acc, soln_pairs[i][0], soln_pairs[i + 1][0])
io.sendlineafter(b'>> ', b'2')
io.sendlineafter(b'>> ', secret.hex().encode())
io.interactive()bctf{neighbor_c5975dc61dbfd49a} Hooray, we get the flag :)
This was a really nice challenge involving CBC, and my favorite crypto this year so far. Wow, a CBC challenge that isn't padding oracle!