from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from Crypto.Util.Padding import pad
import random
def chunks(lst, n):
"""Yield successive n-sized chunks from lst."""
for i in range(0, len(lst), n):
yield lst[i:i + n]
flag = open("flag.txt", "rb").read()
flag = list(chunks(flag, len(flag)//8))
seeds = bytearray(random.getrandbits(4) for _ in range(8))
print(seeds)
random.seed(seeds)
key = bytearray(random.getrandbits(8) for _ in range(16))
iv = bytearray(random.getrandbits(8) for _ in range(16))
cipher = AES.new(key, AES.MODE_CBC, iv = iv)
ct_lst= []
for i in range(len(flag)):
ct_bytes = flag[i]
for _ in range(seeds[i]):
ct_bytes = pad(ct_bytes, AES.block_size)
ct_bytes = cipher.encrypt(ct_bytes)
cipher = AES.new(key, AES.MODE_CBC, iv = iv)
ct_lst.append(ct_bytes.hex())
print(f"ct_lst = {ct_lst}")
So there is a seed generated from getrandbits(4) 8 times. The seed will be used as seed for random that will be used to generate key and iv. If we can leak seed we can easily generate key and iv.
Lets take a look on encryption process. In encryption process, the plaintext (flag[i]) will be encrypted several times using the same key and iv. Number of encryptions performed base on the seed for each index. For example, for the first block plaintext if the first byte of seed is 3 the encryption will be performed 3 times. The 3 times of encryption + padding will affect to the length of the output (ciphertext). So based on this information we can leak the seed by using the length of each ciphertext block.
plaintext[0] -> 16 bytes [1]
enc(pad(plaintext[0])) -> 32 bytes [1]
enc(pad(enc(pad(plaintext[0])))) -> 48 bytes [2]
By assuming that each chunk is not more than 16 bytes, we can leak the seed by dividing the length with 16 (cause each pad add 16 more bytes). Below is the script to solve the challenge
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import random
ct_lst = ['765852323e93d7ea22803eabad3f23ba27f8738a933ac64780d5de145fe7618c2142d714e7b412d247e12823e469629f', 'a4fd67b4efc533f1caf67283b4da6289d932a32e681b41b775773cc3ff826edc3914850acdc583ded61d5855f9c976671c497d3607a0b9c4220e421f973f2b15cbf3abc334f8004834110f68a42c901cf0ba3ade7f4e3a242702066b57470373ccd4c824cae1f7fc5ac9c67afd88d51e842c1f14a008db4bfa67e3c81335cb476b13cf73c91162387f95a37c14ca4dd3f8080149f88454adf9ffcef6d05a6ebc10cfa22cb25f9e269aeeeb733544c27fd715128de3ef215db6103d4cecfdc42c45e199c49fb8f475959ce5005a808d83', 'a6b227f5cb857bfeecb5af298764cb4e9ffe54840c4e6b940a5a90298de91f326a0405c1d47d5690e0e5c1b042c6033c1f0fec87efcd3464466cf51d18a5eae02326f4ea762bb6aa46c3219f91fc83e0e93c842e64885c335e1abe293bc6d6a51529e6886a2ab0f5d2d6f500dad6ce5e', '520348a37d0004eb610cb9a315b7352386403439d463724d1d4e1bec2d5c2041be1f911bbae9374612c12141dd24192d095158af743a490f1896c38ee86aa13895e00736dbab01f09b263b6cdc7c71a5bfb1c87113a0141e06d075295e76dcf6', '3d27697fa697265ed76c0498ee8285a1d930af543b4171a56bbb262e82fdee58b252316b849f2425c115e8b89070a476', '511234c0852228c50b1bc97ab7928d99c2e237161a06c9a5fc268ddb5769c1abc698deb5f93586b8c8f1375b96d5d35bdffd28a0b1c76965217b261bef7ae00605cfb3c4d429de56c6794ed719e8991cdda33bfc59f2e37ec294f789c19c81774bcb3bd690af3e09a37160a0327f438019d37cc372076277f85a029afe3821fe75b07c6af27c20bc2a6e4af4419dd84f019c89da471dde2815dc7f9d8adec572d78d89333ee4aa530364182cb55b5a85eb38145e5e6508694af0881d48c55e7749d5ec9484c1a581a0e7a05b5ec1365c0e8d9a7304f66d6c51a5699ebd824182337ef5a90bfc9527f03c83daf038d75b', 'aeafa8570515a50fce2ac05acdce55e5b5ae218100e8c6f07373a463dd34d529a4d7925adf41053da160bb282eed8e3423d482bba7a4905b18fc658ac643f511', 'bd425afaddbd71dae3562294b911116609cdda350892ba0e916eb22ba4e7ba971ba59e724dd3659b141276a0fa4dc514']
fix_ct = [bytes.fromhex(i) for i in ct_lst]
seeds = b""
for i in fix_ct:
seeds += bytes([len(i) // 16])
random.seed(seeds)
key = bytearray(random.getrandbits(8) for _ in range(16))
iv = bytearray(random.getrandbits(8) for _ in range(16))
cipher = AES.new(key, AES.MODE_CBC, iv = iv)
flag = b""
for i in range(len(seeds)):
ct_bytes = fix_ct[i]
for _ in range(seeds[i]):
ct_bytes = cipher.decrypt(ct_bytes)
cipher = AES.new(key, AES.MODE_CBC, iv = iv)
flag += unpad(ct_bytes[:16], 16)
print(flag)
from Crypto.Util.number import *
import random
def gen_key_1():
p = getPrime(512)
q = getPrime(512)
e = getPrime(64)
d = inverse(e, (p-1)*(q-1))
n = p * q
return e, d, n
def gen_key_2():
while True:
a = random.randint(10 ** 6, 10 ** 7)
b = random.randint(10 ** 6, 10 ** 7)
p = 2 * a * b + 1
q = a ** 2 + b ** 2
if isPrime(p) and isPrime(q):
break
e = 65537
d = inverse(e, (p-1)*(q-1))
n = p * q
return e, d, n
flag = open("flag.txt", "rb").read()
m = bytes_to_long(flag)
e1, d1, n1 = gen_key_1()
c1 = pow(m, d1, n1)
e2, d2, n2 = gen_key_2()
c2 = pow(e1, e2, n2)
print("n1 = ", n1)
print("c1 = ", c1)
print("n2 = ", n2)
print("e2 = ", e2)
print("c2 = ", c2)
So there is 2 function provided, gen_key_1 and gen_key_2. Nothing interesting in gen_key_1, so lets continue on gen_key_2. gen_key_2 create prime based on a and b. Lets check the constructed prime
From above equation we know that the maximum bits for p is 48 bits and q is 164 bits which we know is not a secure factor. In this case we can factorize it using sage. After we leak the factor of key_2, we will get e1, lets continue to key_1. key_1 is used to do the encryption but it actually not encryption process, it is a decryption process because it use d1 as a power. So to get the m value we just need to do the power of e1 by the concept of RSA. Below is the script to solve the challenge
import random
from Crypto.Util.number import *
class LCG:
def __init__(self, state, a, c, m):
self.state = state
self.a = a
self.c = c
self.m = m
def next(self):
self.state = (self.a * self.state + self.c) % self.m
return self.state
state = ## REDACTED ##
a = ## REDACTED ##
c = ## REDACTED ##
m = 2594826617
LCGs = LCG(state, a, c, m)
ct_lst = []
flag = open('flag.txt', "rb").read()
for i in range(0, len(flag), 3):
pt = bytes_to_long(flag[i:i+3])
ct = LCGs.next() ^ pt
ct_lst.append(ct)
print("ct_lst =", ct_lst)
From code above we know that the challenge use LCG as the RNG. In this case we know that increment, multiplier, and state are unknown. Flag are processed 3 bytes each time, based on the LCG crack algorithm i know we need to get at least 3 states to leak the unknown multiplier. We know that the format flag is "CBC2024{" which is 8 bytes. So basically we just need to brute 1 byte to crack the unknown multiplier. After we leak the multiplier we need to leak the increment than just use known state to generate the next state and do decryption using xor. Below is the script to solve the challenge
import random
from Crypto.Util.number import *
from functools import reduce
from math import gcd
def egcd(a, b):
if a == 0:
return b, 0, 1
else:
g, x, y = egcd(b % a, a)
return g, y - (b // a) * x, x
def modinv(b, n):
g, x, _ = egcd(b, n)
if g == 1:
return x % n
def crack_unknown_increment(states, modulus, multiplier):
increment = (states[1] - states[0] * multiplier) % modulus
return increment
def crack_unknown_multiplier(states, modulus):
# multiplier = (states[2] - states[1]) * modinv(states[1] - states[0], modulus) % modulus
multiplier = (states[2] - states[1]) * inverse(states[1] - states[0], modulus) % modulus
return multiplier
def crack_unknown_modulus(states):
diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
zeroes = [t2 * t0 - t1 * t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
modulus = abs(reduce(gcd, zeroes))
return modulus
class LCG:
# Xn = (a*Xn-1 + c) % n
def __init__(self, seed, a, c, m):
self.seed = seed
self.a = a
self.c = c
self.m = m
def next(self):
self.seed = (self.a * self.seed + self.c) % self.m
return self.seed
import string
known = [b"CBC", b"202"]
ct_lst = [2102339510, 201697442, 2493158946, 166672257, 3789596, 1160668690, 1481975077, 2124350211, 943329066, 2044520621, 82513028, 2207880904, 1436817304, 1083426542, 35086421, 1371601831, 1511718692, 1079607174]
what = []
for i in string.printable[:-6]:
known_elements = []
for j in range(len(known)):
known_elements.append(bytes_to_long(known[j]) ^ ct_lst[j]) # 0, 1
known_elements.append( bytes_to_long(b"4{" + i.encode()) ^ ct_lst[2])
modulus = 2594826617
flag = b"CBC"
try:
multiplier = crack_unknown_multiplier(known_elements, modulus)
increment = crack_unknown_increment(known_elements, modulus, multiplier)
lcg = LCG(known_elements[0], multiplier, increment, modulus)
tmp = []
for k in range(1, len(ct_lst)):
flag += long_to_bytes(lcg.next() ^ ct_lst[k])
if flag[-1] == ord('}'):
print(flag)
except Exception as e:
continue
from Crypto.Util.number import *
flag = open("flag.txt", "rb").read()
binFlag = "".join([bin(i)[2:].rjust(8, "0") for i in flag])
p = getPrime(64)
c_list = []
for b in binFlag:
e = getPrime(32)
res = pow(e, 2, p)
if b == "1":
c_list.append(res)
else:
c_list.append(-res % p)
print("p =", p)
print("c_list =", c_list)
From above code we know that there is to possibility of value in c_list, 1 if the value is square number and 0 if the value is not square number. To solve this challenge we can utilize legendre symbol.
pow(i, (p - 1)//2, p)
if return is 1 , it is modular square number
if return is 0, it is not a modular square number
After that just convert it back to bytes. Below is the script to solve the challenge
