脆弱性"&'<<>\ 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))