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_bytesKEY_LEN =100key =get_random_bytes(KEY_LEN)R =0x01defRGEN():global R R = ((R <<1) ^ (0x71if (R &0x80) else0)) &0xFFreturn Rdefxor_text(text,key):returnbytes([text[i] ^ key[i] for i inrange(len(text))])defnext_key(key):returnbytes([key[i] ^RGEN() for i inrange(len(key))])defencrypt(text,key): ciphertext =b"" blocks = [text[i : i + KEY_LEN]for i inrange(0, len(text), KEY_LEN)]for block in blocks: ciphertext +=xor_text(block, key) key =next_key(key)return ciphertext# ---text =b""withopen("text.txt", "rb")as f: text = f.read()ciphertext =encrypt(text, key)withopen("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 stringfrom itertools import productdefRGEN():global R R = ((R <<1) ^ (0x71if (R &0x80) else0)) &0xFFreturn Rdefxor_text(text,key):returnbytes([text[i] ^ key[i] for i inrange(len(text))])defnext_key(key):return [key[i]^RGEN()for i inrange(len(key))]KEY_LEN =100key = [0for i inrange(KEY_LEN)]f =open("ciphertext.txt", "rb").read()target_length =4possible_key = [[] for i inrange(target_length)]possible_key += [[0] for i inrange(100- target_length)]for target inrange(target_length):for j inrange(0x100): R =0x01 key[target]= j counter =0for i inrange(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 inproduct(*possible_key): R =0x01 tmp_key =list(i) plaintext = []for j inrange(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 stringfrom itertools import productdefRGEN():global R R = ((R <<1) ^ (0x71if (R &0x80) else0)) &0xFFreturn Rdefxor_text(text,key):returnbytes([text[i] ^ key[i] for i inrange(len(text))])defnext_key(key):return [key[i]^RGEN()for i inrange(len(key))]KEY_LEN =100ct =open("ciphertext.txt", "rb").read()pt =b"-----BEGIN PGP SIGNED MESSAGE-----\n"# well known format after leaking ----BEGori_key = []for i inrange(len(pt)): ori_key.append(pt[i] ^ ct[i])ori_key += [0for i inrange(100-len(ori_key))]target =len(pt)whileTrue:for x inrange(0x100): R =0x1 key = ori_key[:] key[target]= xfor i inrange(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 reduceimport sysdefKekF1601onLanes(lanes): R =1for _ inrange(24): C = [reduce(lambdaa, b: a ^ b, lanes[x])for x inrange(len(lanes))] D = [ C[(x +4) %len(lanes)]^ C[(x +1) %len(lanes)]for x inrange(len(lanes)) ] lanes = [[lanes[x][y] ^ D[y]for y inrange(8)] for x inrange(len(lanes))]for i inrange(len(lanes)): aux = lanes[i][0]for j inrange(len(lanes[0]) -1): lanes[i][j] = lanes[i][j +1] lanes[i][-1] = aux aux = lanes[0]for j inrange(len(aux)):for i inrange(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 &2return lanesdefKekF1601(state): lanes = [state[x *8: (x +1) *8]for x inrange(len(state) //8)] lanes =KekF1601onLanes(lanes) state = [item for row in lanes for item in row]return stateOUT_LEN =69defKek(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]defSAH3_652(state_arr):returnKek(1088, state_arr, 0x06)pt =""# Flagstate0 =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 reduceimport sysfrom z3 import*defKekF1601onLanes(lanes): R =1for _ inrange(24): C = [reduce(lambdaa, b: a ^ b, lanes[x])for x inrange(len(lanes))] D = [ C[(x +4) %len(lanes)]^ C[(x +1) %len(lanes)]for x inrange(len(lanes)) ] lanes = [[lanes[x][y] ^ D[y]for y inrange(8)] for x inrange(len(lanes))]for i inrange(len(lanes)): aux = lanes[i][0]for j inrange(len(lanes[0]) -1): lanes[i][j] = lanes[i][j +1] lanes[i][-1] = aux aux = lanes[0]for j inrange(len(aux)):for i inrange(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 &2return lanesdefKekF1601(state): lanes = [state[x *8: (x +1) *8]for x inrange(len(state) //8)] lanes =KekF1601onLanes(lanes) state = [item for row in lanes for item in row]return stateOUT_LEN =69defKek(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]defSAH3_652(state_arr):returnKek(1088, state_arr, 0x06)s =Solver()known =b"ctf{"pt = [BitVec("x{}".format(i), 8)for i inrange(69)]pt += [0for i inrange(131)]output = "2033251f4b3161e4455a4c261e3f631e18653c3a6c136e30304037373e6e1f6c6f6448673e686b1e18603d10306d323f3a4b626eee636c3c3c62483592123e6d6c6c3a49ca"
data =list(bytes.fromhex(output))out =SAH3_652(pt)# found another valid character, so add some constraintss.add(pt[61] ==ord('e'))s.add(pt[62] ==ord('e'))s.add(pt[63] ==ord('f'))for i inrange(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)