0ctf 2017: oneTimePad

,

solution

線形性に気付いて復元。

generator.next() の$2,3$回目の出力は分かるので、$1$回目の出力を求めればよい。 seed, keyと$2$変数あるので、process(m, k)の逆関数を書くことになる。

ここでprocessは以下のような性質を持つ。

  • process(tmp=m ^ k) という$1$変数関数と見做してよい
  • 線形性: process(x) ^ process(y) == process(x ^ y)

この線形性により、processの逆関数x = invert(y)はそのyを$0$にするように掃き出し法やLights Out風の探索で実装できる。

implementation

#!/usr/bin/env python2
from os import urandom
def str2num(s):
    return int(s.encode('hex'), 16)
def num2str(n):
    return hex(n)[2:].rstrip('L').decode('hex')

ctxt1 = 0xaf3fcc28377e7e983355096fd4f635856df82bbab61d2c50892d9ee5d913a07f
ctxt2 = 0x630eb4dce274d29a16f86940f2f35253477665949170ed9e8c9e828794b5543c
ctxt3 = 0xe913db07cbe4f433c7cdeaac549757d23651ebdccf69d7fbdfd5dc2829334d1b
fake_secret1 = 'I_am_not_a_secret_so_you_know_me'
fake_secret2 = 'feeddeadbeefcafefeeddeadbeefcafe'
generator2 = ctxt2 ^ str2num(fake_secret1)
generator3 = ctxt3 ^ str2num(fake_secret2)
assert generator2 == 0x2a51d5b1bd1abdee4999363397902036332916fbce0982ebd3f5ece8e3ea3959
assert generator3 == 0x8f76be63af819557a5a88fca37f631b750348eb8ab0cb69fbdb0b94e4a522b7e

P = (1 << 256) + 0x425
def process(x):
    assert (1 << 256) > x
    y = 0
    for i in bin(x)[2:]:
        y <<= 1
        if int(i):
            y ^= x
        if y >> 256:
            y ^= P
    return y

import random
for _ in range(1000):
    x = random.randrange(1 << 256)
    y = random.randrange(1 << 256)
    assert process(x) ^ process(y) == process(x ^ y)

def ilog2(n):
    if n == 0:
        return -1
    return len(bin(n)) - 3
table = [ list() for _ in range(256) ]
for i in range(256):
    proc_i = process(1 << i)
    table[ilog2(proc_i)] += [( 1 << i, proc_i )]
for i in reversed(list(range(256))):
    table[i] = sorted(list(set(table[i])))
    for j, proc_j in table[i]:
        for k, proc_k in table[i]:
            jk = j ^ k
            proc_jk = proc_j ^ proc_k
            if proc_jk == 0:
                continue
            table[ilog2(proc_jk)] += [( jk, proc_jk )]
def recur(y, i):
    if i == -1:
        if y == 0:
            return 0
        else:
            return
    else:
        if y & (1 << i):
            for j, proc_j in table[i]:
                x = recur(y ^ proc_j, i-1)
                if x is not None:
                    return x ^ j
        else:
            return recur(y, i-1)
def unprocess(y):
    return recur(y, 255)

seed = unprocess(generator3) ^ generator2
generator1 = unprocess(generator2) ^ seed
true_secret = generator1 ^ ctxt1
print(repr('flag{' + num2str(true_secret) + '}'))