foobarCTF 2022 | random fandom

#foobarCTF_2022

#!/usr/bin/env python3

import random
import math

secret = #REDACTED
flag = #REDACTED

def keygen(n):
    privKey = [0]*n
    privKey[0] = #REDACTED
    for i in range(1, n):
        total = sum(privKey)
        privKey[i] = random.randint(total*2 ,total*3) 

    privKey = tuple(privKey)
    total = sum(privKey)
    modulo = random.randint(total*2 ,total*3)

    while True:
        multiplier = random.randint(modulo//4, modulo-1)
        if math.gcd(multiplier, modulo):
            break

    pubKey = [multiplier*privKey[i]%modulo for i in range(n)]

    return pubKey

def encryption(enc_state):
    global pubKey
    pubKey = keygen(n=32)
    enc_array = []

    for i in state_one:
        result = 0
        j= bin(i)[2:].zfill(32)
        for k,b in zip(j, pubKey):
            result+=(int(k)*b)
        enc_array.append(result)

    return(tuple(enc_array))


random.seed(secret)

state = random.getstate()

enc_flag = 0
state_one = state[1]

random_number = random.randint(1, 2**8)

shuffled_flag = (''.join(random.sample(flag,len(flag))))


for i in shuffled_flag:
    enc_flag=(enc_flag*(random_number**ord(i)))+ord(i)

enc_state_one = encryption(state_one)
enc_state = tuple([state[0], enc_state_one, state[2]])

print(enc_flag)
print(enc_state)
print(pubKey)

フラグがshuffleされたり、一文字ずつ暗号化されたりしている。暗号化の鍵は乱数の種で、このseedを求めるのが今回の問題の主眼っぽい。（その後unshuffleするとか、めんどうな作業はあるけど、フラグの長さがわかっていればあとからエミュするのは大した労力ではないはず）

乱数のステートはenc_stateとして暗号化して渡されている。

stateの暗号化は

• 鍵生成

• • 32要素の 超増加列

    priv と、 として得られる pub を生成する

  • • m や M はランダムに生成されて不明

• state[i] の暗号化は↓のように ナップザック暗号 になっている

• 

要するにこの問題を解くためには

• ナップザック暗号を解いて、暗号化のstateを復号

• randomの様子を再生し直して、フラグの暗号化を逆再生

すればいい。一応今回の密度を求めると0.3...でかなり疎だった。これならCLOS法でもLO法でも好きな方で解けそう

フラグ本体の暗号化は単に割り切れるかどうかをみながらBFSとかすればいい

import ast
import random

with open("Output.txt") as f:
    enc_flag = ast.literal_eval(f.readline().strip())
    enc_state = ast.literal_eval(f.readline().strip())
    pubkey = ast.literal_eval(f.readline().strip())



def clos(pubkey, ciphertext):
    # check the density
    b = pubkey
    c = ciphertext

    n = len(b)
    d = float(n / log(max(b), 2))
    assert(d < 0.9048)

    # low-density attack, CLOS method
    # prepare a basis
    MULTIPLIER = 1
    B = matrix(ZZ, n + 1, n + 1)
    B.set_block(0, 0, MULTIPLIER * matrix(n, 1, b))
    B.set_block(n, 0, MULTIPLIER * matrix([-c]))
    B.set_block(0, 1, 2 * identity_matrix(n))
    B.set_block(n, 1, matrix([-1] * n))

    # LLL algorithm
    for x in B.LLL():
        if x[0] == 0 and all((x_i in [-1, +1]) for x_i in x[1:]):

            # decode x
            m = 0
            for x_i in x[1:]:
                m *= 2
                m += int(x_i == +1)
            return m

state = []
for i in range(len(enc_state[1])):
    print("{} / {}".format(i + 1, len(enc_state[1])))
    state.append(clos(pubkey, enc_state[1][i]))

# print(state)

state = tuple([int(x) for x in state])
random.setstate((enc_state[0], state, enc_state[2]))
random_number = random.randint(1, 2**8)

states = [(enc_flag, [])]
while len(states) > 0:
    (cur_enc_flag, bs), states = states[0], states[1:]
    if cur_enc_flag == 0:
        random.setstate((enc_state[0], state, enc_state[2]))
        random_number = random.randint(1, 2**8)

        index = [i for i in range(len(bs))]
        shuffled_index = random.sample(index, len(bs))
        unshuffled = [bs[shuffled_index.index(i)] for i in range(len(bs)) ]

        print(bytes(unshuffled))
        continue


    for b in range(0x20, 0x7f):
        if (cur_enc_flag - b) % (random_number ** b) == 0:
            next_enc_flag = (cur_enc_flag - b) // (random_number ** b) 
            states.append((next_enc_flag, [b] + bs))