Help us understand the problem. What is going on with this article?

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

More than 3 years have passed since last update.

脆弱性"&'<<>\ 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))) + k3C'=perm(sub(xor(perm(P'), k2))) + k3を考える。CC'の差分が少なくて8bitくらいならば、PP'の差分が1bitである可能性が高い。なぜなら、permとxorでは差分のビット数は変化せず、subによる差分の拡大は高々8bitで、足し算もだいたいxorと同じ結果になるから。あとは勉強会の内容と同じで、aを0, 1, 2…と変えながら、P=sub⁻¹(0)^aP'=sub⁻¹(1)^aとした場合の差分を見れば良い。差分が少ないということは、PP'の差が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))
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした