We managed to intercep communication with a critical mission. We can't decipher it but managed to break into the system and recover what looks like part of the communication and an algorithm for it.
Can you get the full message?
Solution
Given source code below.
from Crypto.Random import get_random_bytes
KEY_LEN = 100
key = get_random_bytes(KEY_LEN)
R = 0x01
def RGEN():
global R
R = ((R << 1) ^ (0x71 if (R & 0x80) else 0)) & 0xFF
return R
def xor_text(text, key):
return bytes([text[i] ^ key[i] for i in range(len(text))])
def next_key(key):
return bytes([key[i] ^ RGEN() for i in range(len(key))])
def encrypt(text, key):
ciphertext = b""
blocks = [text[i : i + KEY_LEN] for i in range(0, len(text), KEY_LEN)]
for block in blocks:
ciphertext += xor_text(block, key)
key = next_key(key)
return ciphertext
# ---
text = b""
with open("text.txt", "rb") as f:
text = f.read()
ciphertext = encrypt(text, key)
with open("ct.txt", "wb") as g:
g.write(ciphertext)
Below is the program flow:
Generate random key with length 100 bytes
Split plaintext to block with each block length is 100 bytes
Loop until all encrypted
Xor block plaintext with key
Create new key based on previous key and RGEN function
So if we know the the first generated key we will decrypt the rest ciphertext because the next key is based on previous key. Since it is almost impossible to brute 100 bytes immediately so my idea is brute 4 bytes first key with assumption we can read partial valid "plaintext" that consist of 4 bytes then bruteforce 1 bytes semi automatically. To reduce the possibility we can loop through all blocks and validate only specific index on decrypted text, if those value on specific index on all blocks are printable so it is one of the possible key. For example if we want to get key on index 10 we only validate plaintext on index 10 on block1,block2,..block100, if there is 100 valid printable character at index 10 from all blocks it is one of the possible key.
import string
from itertools import product
def RGEN():
global R
R = ((R << 1) ^ (0x71 if (R & 0x80) else 0)) & 0xFF
return R
def xor_text(text, key):
return bytes([text[i] ^ key[i] for i in range(len(text))])
def next_key(key):
return [key[i] ^ RGEN() for i in range(len(key))]
KEY_LEN = 100
key = [0 for i in range(KEY_LEN)]
f = open("ciphertext.txt", "rb").read()
target_length = 4
possible_key = [[] for i in range(target_length)]
possible_key += [[0] for i in range(100 - target_length)]
for target in range(target_length):
for j in range(0x100):
R = 0x01
key[target] = j
counter = 0
for i in range(0, len(f), KEY_LEN):
tmp = f[i:i+KEY_LEN]
result = xor_text(tmp, key)
if(chr(result[target]) in string.printable):
counter += 1
key = next_key(key)
if counter >= int(len(f)//100) + 1:
possible_key[target].append(j)
for i in product(*possible_key):
R = 0x01
tmp_key = list(i)
plaintext = []
for j in range(0, len(f), KEY_LEN):
block = f[j:j+KEY_LEN]
tmp = xor_text(block, tmp_key)
plaintext.append(tmp[:target_length])
tmp_key = next_key(tmp_key)
print(list(i)[:target_length], plaintext)
print()
After getting first 4 bytes key, lets do semi automatic bruteforce for each next byte key.
import string
from itertools import product
def RGEN():
global R
R = ((R << 1) ^ (0x71 if (R & 0x80) else 0)) & 0xFF
return R
def xor_text(text, key):
return bytes([text[i] ^ key[i] for i in range(len(text))])
def next_key(key):
return [key[i] ^ RGEN() for i in range(len(key))]
KEY_LEN = 100
ct = open("ciphertext.txt", "rb").read()
pt = b"-----BEGIN PGP SIGNED MESSAGE-----\n" # well known format after leaking ----BEG
ori_key = []
for i in range(len(pt)):
ori_key.append(pt[i] ^ ct[i])
ori_key += [0 for i in range(100 - len(ori_key))]
target = len(pt)
while True:
for x in range(0x100):
R = 0x1
key = ori_key[:]
key[target] = x
for i in range(0, len(ct), KEY_LEN):
block = ct[i:i+KEY_LEN]
tmp = xor_text(block, key)
print(x, tmp[:target + 1])
key = next_key(key)
print()
print(ori_key)
ori_key[target] = int(input("dec: "))
target += 1
Here the super-secure hash of my secret: 2033251f4b3161e4455a4c261e3f631e18653c3a6c136e30304037373e6e1f6c6f6448673e686b1e18603d10306d323f3a4b626eee636c3c3c62483592123e6d6c6c3a49ca
Feeling generous to share some hints about my secret that you definitely will not able to recover:
Text length: 69 characters
Flag regex: CTF{[a-f0-9]{64}}
Flag contains somewhere the text: beebeef
Solution
Given source code below
from functools import reduce
import sys
def KekF1601onLanes(lanes):
R = 1
for _ in range(24):
C = [reduce(lambda a, b: a ^ b, lanes[x]) for x in range(len(lanes))]
D = [
C[(x + 4) % len(lanes)] ^ C[(x + 1) % len(lanes)] for x in range(len(lanes))
]
lanes = [[lanes[x][y] ^ D[y] for y in range(8)] for x in range(len(lanes))]
for i in range(len(lanes)):
aux = lanes[i][0]
for j in range(len(lanes[0]) - 1):
lanes[i][j] = lanes[i][j + 1]
lanes[i][-1] = aux
aux = lanes[0]
for j in range(len(aux)):
for i in range(len(lanes) - 1):
lanes[i][j] = lanes[i][j] ^ lanes[i + 1][j]
lanes[-1][j] = lanes[-1][j] ^ aux[j]
R = ((R << 1) ^ ((R >> 7) * 0x71)) % 256
lanes[0][0] ^= R & 2
return lanes
def KekF1601(state):
lanes = [state[x * 8 : (x + 1) * 8] for x in range(len(state) // 8)]
lanes = KekF1601onLanes(lanes)
state = [item for row in lanes for item in row]
return state
OUT_LEN = 69
def Kek(rate, state, delimitedSuffix):
rateInBytes = rate // 8
blockSize = 69
state[blockSize] = state[blockSize] ^ delimitedSuffix
state[rateInBytes - 1] = state[rateInBytes - 1] ^ 0x80
state = KekF1601(state)
return state[0:OUT_LEN]
def SAH3_652(state_arr):
return Kek(1088, state_arr, 0x06)
pt = "" # Flag
state0 = list(pt.encode("utf-8"))
state0.extend([0] * (200 - len(state0)))
out = SAH3_652(state0)
print(bytes(out).hex())
# 2033251f4b3161e4455a4c261e3f631e18653c3a6c136e30304037373e6e1f6c6f6448673e686b1e18603d10306d323f3a4b626eee636c3c3c62483592123e6d6c6c3a49ca
Below is the program flow:
Create delimiter at index 69 by xoring value on index 69
Split to block with each block consist of 8 bytes data
Loop 24 times
Xor all value on each block and store on C
Xor C on index (x+1) with (x + 4) and store on D
Xor original block value with D
Shift value on each row
Do something like mix row (xor value different row)
Xor first value with R
From above flow i assume that SAT/SMT solver can solve this challenge. The idea is trying to get the plaintext by utilizing z3. Below is my script
from functools import reduce
import sys
from z3 import *
def KekF1601onLanes(lanes):
R = 1
for _ in range(24):
C = [reduce(lambda a, b: a ^ b, lanes[x]) for x in range(len(lanes))]
D = [
C[(x + 4) % len(lanes)] ^ C[(x + 1) % len(lanes)] for x in range(len(lanes))
]
lanes = [[lanes[x][y] ^ D[y] for y in range(8)] for x in range(len(lanes))]
for i in range(len(lanes)):
aux = lanes[i][0]
for j in range(len(lanes[0]) - 1):
lanes[i][j] = lanes[i][j + 1]
lanes[i][-1] = aux
aux = lanes[0]
for j in range(len(aux)):
for i in range(len(lanes) - 1):
lanes[i][j] = lanes[i][j] ^ lanes[i + 1][j]
lanes[-1][j] = lanes[-1][j] ^ aux[j]
R = ((R << 1) ^ ((R >> 7) * 0x71)) % 256
lanes[0][0] ^= R & 2
return lanes
def KekF1601(state):
lanes = [state[x * 8 : (x + 1) * 8] for x in range(len(state) // 8)]
lanes = KekF1601onLanes(lanes)
state = [item for row in lanes for item in row]
return state
OUT_LEN = 69
def Kek(rate, state, delimitedSuffix):
rateInBytes = rate // 8
blockSize = 69
state[blockSize] = state[blockSize] ^ delimitedSuffix
state[rateInBytes - 1] = state[rateInBytes - 1] ^ 0x80
state = KekF1601(state)
return state[0:OUT_LEN]
def SAH3_652(state_arr):
return Kek(1088, state_arr, 0x06)
s = Solver()
known = b"ctf{"
pt = [BitVec("x{}".format(i), 8) for i in range(69)]
pt += [0 for i in range(131)]
output = "2033251f4b3161e4455a4c261e3f631e18653c3a6c136e30304037373e6e1f6c6f6448673e686b1e18603d10306d323f3a4b626eee636c3c3c62483592123e6d6c6c3a49ca"
data = list(bytes.fromhex(output))
out = SAH3_652(pt)
# found another valid character, so add some constraints
s.add(pt[61] == ord('e'))
s.add(pt[62] == ord('e'))
s.add(pt[63] == ord('f'))
for i in range(len(out)):
s.add(out[i] == data[i])
print(s.check())
model = s.model()
flag = b""
for i in pt:
flag += bytes([model[i].as_long()])
print(i, flag)
