0ctf 2017 writeup - liniku's blog

チーム yharima として参戦。 Welcome を除くと、onetimepad と integrity の二問だけしか解けず。

onetimepad

暗号化に使われたスクリプトと暗号文が渡されるので、それを復号する、そんな問題。

16byteの鍵と平文(16byte)をXORにかけて暗号化するが、鍵の生成法は次の通り（問題より抜粋）

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 keygen(seed):
    key = str2num(urandom(32))
    while True:
        yield key
        key = process(key, seed)

暗号文が三つ(16byte×3)、平文が二つ与えられるので、二つ分の鍵がわかる。フラグの暗号用の鍵は一番最初に作られていて、その後生成された二つの鍵が既知。

結局のところ、process(m, k) の中の res が与えられたときに tmp を求めることができればよい。これができれば既知の鍵二つから seed が求められ、seedと既知の鍵が分かっていれば一つ前に生成された鍵が求められる。

ここで、次の部分の処理にだけ注目する。

    for i in bin(tmp)[2:]:
        res = res << 1;
        if (int(i)):
            res = res ^ tmp

この処理を行うと元のビット列の間に 0 を挟んだものが結果となる。 tmp == 0b101 であれば res == 0b10001 になり、tmp == 0b1111 であれば res == 0b1010101 になる。つまり、下から偶数番目のビットが必ず 0 になる。この tmp * tmp 的な値を復元していく。

実際は if (res >> 256): res = res ^ P の処理が入るため、そうはならない。しかし、ここで P の下位12bit に着目すると 0b0010000100101 となっており、下から偶数番目のビットが 1 となっているのは、6ビット目だけ。基本的には、res の偶数番目のビットが立っていればそれは res = res ^ P の影響であることになる。このことから、下位 bit から少しずつ復元が可能になる。ただし、res = res ^ P で立ったビットがシフトされることにより再度 res = res ^ P されることも考慮すると、このやり方では6ビットは一意に特定できない。 6ビットだけ全探索して、tmp * tmp 的な値を気合で復元し、奇数番目のビットだけ抜き出すと res の候補がでる。

コードは下のようになった。

#!/usr/bin/env python
# coding=utf-8

def encode(tmp):
    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 str2num(s):
    return int(s.encode('hex'), 16)

def decode(k):
    for x in range(1 << 6):
        t = k
        for i in range(6):
            if x & (1 << i):
                t ^= 0x425 << i

        if t & 0b10101010:
            continue

        bh = x
        t = x << 256 | t
        for i in range(6, 256):
            if i % 2 == 0 and t & (1 << (i + 5)):
                bh ^= 1 << i
                m = 0x425 << i
                t ^= m
                if m >= (1 << 256):
                    bh ^= m >> 256
        y = bh << 256 | t

        b = 0
        for i in range(0, 512, 2):
            if y & (1 << i):
                b |= 1 << (i/2)

        if encode(b) == k:
            return b


P = 0x10000000000000000000000000000000000000000000000000000000000000425L
ctxt1 = 0xaf3fcc28377e7e983355096fd4f635856df82bbab61d2c50892d9ee5d913a07f
ctxt2 = 0x630eb4dce274d29a16f86940f2f35253477665949170ed9e8c9e828794b5543c
ctxt3 = 0xe913db07cbe4f433c7cdeaac549757d23651ebdccf69d7fbdfd5dc2829334d1b
fake_secret1 = "I_am_not_a_secret_so_you_know_me"
fake_secret2 = "feeddeadbeefcafefeeddeadbeefcafe"
f1 = str2num(fake_secret1)
f2 = str2num(fake_secret2)

k2 = ctxt2 ^ f1
k3 = ctxt3 ^ f2
d2 = decode(k2)
d3 = decode(k3)
seed = k2 ^ d3
k1 = seed ^ d2
f = k1 ^ ctxt1
print hex(f)[2:-1].decode('hex')

復号すると t0_B3_r4ndoM_en0Ugh_1s_nec3s5arY が出る。フラグの形式で提出しておわり。

他の方の writeup を見るとこれはガロア体における平方根を出す問題だったらしい。。。ガロア体を知らずに解けたのは運がよかっただけっぽい。ガロア体を勉強するいい機会になりました。

integrity

サーバに繋ぐと AES-CBC をもとにした暗号化と復号化ができる。adminだけ暗号化できないのだが、復号化して admin となる文字列を与えることができればフラグが出る。そんな問題。

暗号化は AES-CBC そのままではなく、以下のようになっている（問題より抜粋）。pad は16byteの倍数になるよう後ろにパディングするだけの関数。

    def encrypt(self,raw):
        raw = pad(raw)
        raw = md5(raw).digest() + raw

        iv = Random.new().read(BS)
        cipher = AES.new(self.key,AES.MODE_CBC,iv)

        return ( iv + cipher.encrypt(raw) ).encode("hex")

入力文字列に対して md5 を付け加えているのがミソ。まず、適当な16文字の後に admin と付け足した文字列 (0123456789012345admin) を暗号化してやる。 CBC モードでの解凍は後ろのブロックから順に行われ、iv は最初のブロックに影響を与えるだけなので、iv を除いた暗号文の最初16byteを削っても admin のブロックは正しく復号化される。後は先頭のブロックの復号結果が md5(pad('admin')) になるよう iv を調整するだけ。

変数名がとても雑だが下のようなコードで、復号結果が admin の文字列を生成できる。

t = '0123456789012345'
a = 'admin'
p = t + a
c = scheme.encrypt(p)
d = int(c[32:64],16)
e = int(t.encode('hex'), 16)
f = int(md5(pad(a)).hexdigest(), 16)
x = d ^ e ^ f
y = hex(x)[2:-1] + c[64:128]
print scheme.decrypt(y)

あとはこれの暗号/復号部分をソケット通信でやるように置き換えるなどして終わり。フラグは flag{Easy_br0ken_scheme_cann0t_keep_y0ur_integrity}

志半ばで終わった問題たち

simplesqlin
- WAF が破れなかったのでスキーマやテーブルを漁れず死亡
Temmo’s tiny shop
- ほぼお買い物しただけ
onetimepad2
- 式を弄って A^N を出せたっぽいが、そこから N を求めることができずに結局復号できず
- Discrete logarithm?