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

脆弱性"&'<<>\ Advent Calendar 2015 20日目の記事です。

katagaitai CTF勉強会 - 関東|hardに参加してきた。午前中の暗号の問題の手抜き版の解き方。

問題はここに。ラウンド数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

# 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))