0CTF 2017 Quals


Category: Crypto

Posted on April 11, 2017

You are given ciphertexts 1, 2, and 3.

You see that each ciphertext is just the XOR of a 'secret' block (32 bytes) with another generated block of 'random' bytes.

Two 'secret' blocks, corresponding to ciphertexts 2 and 3, are plainly revealed to you.

So, if you do ciphertext XOR secret, you can get the generated bytes for 2 and 3.

To get the flag, you need to figure out how to get generated bytes for ciphertext 1.

Looking at the keygen function, it turns out that generated_random_bytes3 = process(generated_random_bytes2, seed)

If there is a way to find b, when you know a, and c, of a = process(b, c), you would be able to recover the seed.

It turns out, if you keep doing:

a = process(x, y)
b = process(a, y)
c = process(b, y)
d = process(c, y)
e = process(d, y)

Eventually it will loop back around, and you'll arrive back at a.

Something like this:

a = process(x, y)
b = process(a, y)
c = process(b, y)
d = process(c, y)
e = process(d, y)
a = process(z, y)

Now you see, the original problem is, if you have a = process(b, c), and you know a and c, but you want to find b.

Here, z is the answer to finding a value X such that a = process(X, y).

So the solution:

from os import urandom

P = 0x10000000000000000000000000000000000000000000000000000000000000425L

def process(m, k):
    tmp = m ^ k
    res = 0
    for i in bin(tmp)[2:]:
        res = res << 1;
        if (int(i)):
            res = res ^ tmp
        if (res >> 256):
            res = res ^ P
    return res

def xprocess(c, a):
    f = lambda x: process(a, x)
    pp = c
    p = f(pp)
    while p != c:
        pp = p
        p = f(p)
    return pp 

def keygen(seed):
    key = str2num(urandom(32))
    while True:
        yield key
        key = process(key, seed)

def str2num(s):
    return int(s.encode('hex'), 16)

fake_secret1 = "I_am_not_a_secret_so_you_know_me"
fake_secret2 = "feeddeadbeefcafefeeddeadbeefcafe"

with open("ciphertext", "r") as f:
    ctxt1, ctxt2, ctxt3 = f.read().splitlines()

c1 = int(ctxt1, 16)
c2 = int(ctxt2, 16)
c3 = int(ctxt3, 16)
key2 = c2 ^ str2num(fake_secret1)
key3 = c3 ^ str2num(fake_secret2)
seed = xprocess(key3, key2)
key1 = xprocess(key2, seed)
flagN = (key1 ^ c1)
flag = hex(flagN)[2:-1].decode('hex')

Flag: flag{t0_B3_r4ndoM_en0Ugh_1s_nec3s5arY}

Copyright © Cornell Hacking Club 2021