「katagaitai CTF勉強会 - 関東|hard」の復習（脆弱なAES暗号の攻撃法）

[脆弱性"&'<<>\ Advent Calendar 2015](http://www.adventar.org/calendars/811) 20日目の記事です。

[katagaitai CTF勉強会 - 関東|hard](https://atnd.org/events/71808)に参加してきた。午前中の暗号の問題の手抜き版の解き方。

問題は[ここに](https://ctftime.org/task/236)。ラウンド数2段のAESっぽい秘密鍵暗号。暗号化は、鍵とのxor、バイトごとに表を引く`x=Table[x]`という操作（Substitution）、ビットの並び替え（Permutation）を2段だけ繰り返し、最後に鍵を足す。

```
C(P) = perm(sub(xor(perm(sub(xor(P, k1))), k2))) + k3
```

勉強会の内容を理解し切れてはいないけど、要は2段では少なすぎて充分に攪拌されないので、2段目の入力の1bitが変化した場合の2段目の出力をリストに持って、2段目の出力の変化が1bitになるような1段目の入力を探索して～ということができるらしい。3段目の足し算については、xorと足し算の結果が異なるのは繰り上がりがあった場合だけだから、ありえないものを弾くことができると。

足し算がどうこうとかを手抜きして、1段目も2段目も入力の内容を変えながら、差分のビット数が小さいものを選べば解けた。試行回数を増やさないと精度は悪いと思う。

1段目の1文字目は正解が`K`でこんな感じ。`[]`の中が各試行で右端がその合計。

```
73 I [31, 11, 27, 16, 17, 30, 7] 139
74 J [27, 17, 18, 18, 11, 13, 26] 130
75 K [9, 11, 14, 15, 6, 21, 16] 92
76 L [20, 16, 21, 15, 28, 13, 19] 132
77 M [19, 25, 19, 24, 26, 21, 23] 157
```

2段目の1文字目はこんな感じ。

```
99 c [10, 11, 5, 13, 17, 3, 10] 69
100 d [17, 6, 7, 8, 4, 5, 10] 57
101 e [1, 2, 3, 2, 3, 3, 5] 19
102 f [11, 6, 5, 12, 3, 6, 14] 57
103 g [14, 4, 12, 4, 6, 13, 2] 55
```

1段目。`C=perm(sub(xor(perm(P), k2))) + k3`と`C'=perm(sub(xor(perm(P'), k2))) + k3`を考える。`C`と`C'`の差分が少なくて8bitくらいならば、`P`と`P'`の差分が1bitである可能性が高い。なぜなら、permとxorでは差分のビット数は変化せず、subによる差分の拡大は高々8bitで、足し算も**だいたい**xorと同じ結果になるから。あとは勉強会の内容と同じで、`a`を0, 1, 2…と変えながら、`P=sub⁻¹(0)^a`と`P'=sub⁻¹(1)^a`とした場合の差分を見れば良い。差分が少ないということは、`P`と`P'`の差が1bitである可能性が高いということで、`a`が鍵である可能性が高い。

2段目も同様に。足し算さえ無ければ、暗号文の差分は1bitになるので、足し算を通してもそんなに差分は増えない。

3段目は、`0`をStep2とStep1の復号処理に通してから暗号化すれば、`k3`となる。

```
step2(step1(step1⁻¹(step2⁻¹(0)))) + k3 = k3
```

```py
# coding: utf-8

from socket import *
from itertools import *
from hashlib import *
from struct import *
from time import *
import subme

# 配列を送信してサーバーで暗号化
def encrypt(v):
    s = socket(AF_INET, SOCK_STREAM)
    s.connect(("katagaitai.orz.hm", 9999))

    # SHA1問題を解く
    q = s.recv(9999).split()[-1]
    for x in product("abcdefghijklmnopqrstuvwxz", repeat=5):
        a = q+"".join(x)
        if sha1(a).hexdigest().endswith("ffff"):
            break
    s.sendall(a)

    # 暗号化
    s.sendall(pack("<H",len(v)) + "".join(map(chr, v)))
    sleep(3)
    return map(ord, eval(s.recv(999999)[20:]))

# 探索空間
A = range(0x20, 0x7f)
# 1文字あたりの試行回数
m = 7

# 1ステップ戻す
def unStep(v, key):
    v = v[:]
    v = map(ord, subme.unPermute("".join(map(chr, v))))
    v = subme.unSubStr(v)
    v = [a^k for a,k in zip(v,key)]
    return v

# Step 1, Step 2の探索
# Step 2を探索する場合はk1にStep 1の鍵を指定する
def solveStep(step, k1):
    key = []

    for i in range(8):
        print "i:", i

        p = []
        for a in A:
            p += [0]*i + [subme.sinv[0]^a] + [0]*(7-i)
            for j in range(m):
                p += [0]*i + [subme.sinv[1<<j]^a] + [0]*(7-i)

        if step==2:
            for j in range(0,len(p),8):
                p[j:j+8] = unStep(p[j:j+8], k1)

        c = encrypt(p)

        ansd = 9999
        for t,a in enumerate(A):
            # 差分を求める
            x = []
            for j in range(m+1):
                x += [c[:8]]
                c = c[8:]
            diff = []
            for j in range(m):
                d = 0
                for k in range(8):
                    d += bin(x[0][k]^x[j+1][k]).count("1")
                diff += [d]
            print a, chr(a), diff, sum(diff)

            # 差分が少なければ鍵
            if sum(diff)<ansd:
                ansd = sum(diff)
                ans = a

        print "key[%s] = %s" % (i, ans)
        key += [ans]

    return key

k1 = solveStep(1, [])
k2 = solveStep(2, k1)

# Step 3
k3 = encrypt(unStep(unStep([0]*8, k2), k1))[::-1]

print "k1:", "".join(map(chr, k1))
print "k2:", "".join(map(chr, k2))
print "k3:", "".join(map(chr, k3))
```