こういう典型っぽいのでも意外と知らないのはいくらでもあるんだなと言うことでupsolveです。こういうのってどこで学ぶんですかね。知識を体系的に獲得していないとこういうところでボロが出る……。
問題概要
- 2種類のブロック暗号のロジック
encrypt1, encrypt2 があります。ブロック長は32bitで鍵の長さも32bit。２つの暗号化ロジックは共通のSBoxを用いています
- ある秘密の鍵
key を使って任意の平文をencrypt1、encrypt2 で暗号化できるオラクルがそれぞれ500回まで利用できます
key を当てるのが今回の目的です
暗号化ロジックは以下の通り。それぞれの暗号化ロジックは非常に単純ですが、ラウンド数が尋常じゃない回数あって入力を工夫したりして直接暗号鍵を求めることは難しそうです。
また、ロジックをよく見るとラウンド鍵が奇数ラウンドと偶数ラウンドで別れていることがわかります。
ROUNDS = 2**22 + 2
def encrypt1(k, plaintext):
a,b,c,d = plaintext
for i in range(ROUNDS):
a ^= sbox[b ^ k[(2*i)&3]]
c ^= sbox[d ^ k[(2*i+1)&3]]
a,b,c,d = b,c,d,a
return bytes([a,b,c,d])
def encrypt2(k, plaintext):
a,b,c,d = plaintext
for i in range(ROUNDS)[::-1]:
b,c,d,a = a,b,c,d
c ^= sbox[d ^ k[(2*i)&3]]
a ^= sbox[b ^ k[(2*i+1)&3]]
return bytes([a,b,c,d])
スライド攻撃（slide attack）
今回の問題設定のように複数ラウンドで同じラウンド鍵が使われている時、スライド攻撃によってラウンド鍵を求めることができるかもしれません。
スライド攻撃のアイデアは非常に単純です。
まず、今回の問題設定は一旦忘れて、より単純なブロック暗号のモデルを考えます。今回考える暗号方式では、全てのラウンドで同じラウンド関数
を用い、暗号化
であるとします（lはラウンド数）。つまり、メッセージ
をラウンド関数にかける処理を
と書いて、暗号化は
です。
この時、ラウンド関数を一回だけ適用したメッセージを 
と書くとして
をslid pair*1と呼びますが、このようなペアをもし知っていればという式からラウンド鍵を求められます。
当然そのようなペアを意図的に手に入れることは多くの場合難しいでしょうが、もし暗号化オラクルがあるなどの状況でknown-plaintextとそれに対応するciphertextのペアをいくつも手に入れられる場合、偶然その集合の中にはslid pairになるような組み合わせが存在するかもしれません。ブロック長を
bitとしてbirthday boundを考えると、
個のペアが存在すれば1つはslid pairが存在することが期待できます。そして、任意のペア
と
がslid pairかどうかは、
と仮定して算出した鍵と
と仮定して算出した鍵が一致しているかどうかで確かめられます（一致していればslid pair）。
したがってスライド攻撃は（最もナイーブには）
- 各ラウンドで同じラウンド鍵が用いられるブロック暗号において
- 暗号化オラクルを有している時
- ブロック長に対しておよその探索でラウンド鍵を求めることができる攻撃
と言えそうです。もし鍵長がブロック長と同じなら、鍵を全探索すると
の空間を探索することになりますからそれに比べると遥かに効率の良い*2攻撃と言えます。
2k-DES構造のブロック暗号に対するスライド攻撃
本題からは少しずれますがこちらも合わせて書いておきます。これまでは非常に単純な、各ラウンドで同じラウンド関数が用いられるようなケースを考えていましたが、例えば（今回の問題のように）奇数ラウンドと偶数ラウンドで異なる鍵が用いられるようなブロック暗号に対してはどのようにアプローチすると良いのでしょうか。一つの方針としては、
のようなslid pairを探すことが考えられます。2ラウンド程度の処理であればそれぞれのラウンド鍵を求めることは造作もない、という場合であればこの攻撃は非常に単純明快で同様に効果的と言えそうです。一方、それが難しい場合にも（ブロック暗号の構造次第ではあるものの）工夫すれば効率的にスライド攻撃が可能であるということだったので紹介します。
今回取り上げるのは2k-DESと呼ばれるラウンド鍵が2種類のDESの亜種です。DESはfeistel構造と呼ばれる構成になっていて、これはブロックを半分に分けて左半分を
、右半分を
と置き、
をラウンド関数として
と表せます。DESの場合は特に
です。
この時
というslid pairを考えることができます。記法としてはこれまで通り
で、
は適当な差分です*3。
を暗号化するとどうなるかを考えてみると、がなければ
となりますがいまはがあるので
となり、同様に
*4となるところが
となり、どんどん差分が伝搬していきます。最終的に得られた
に対応する暗号文を
とすると、 に対応する暗号文は
*5となります。
この時、
が成立することからslid pairかどうかを判定でき、
からの具体的な値がわかるので、ラウンド鍵を求めることができます。
今回の問題の場合
さてでは早速スライド攻撃をやってみましょう！ 今回はブロック長が32bitなので、およそ
個程度の平文と暗号文のペアがあればスライド攻撃が適用できそうです！ それでは65535回クエリを……
……今回の問題設定では500回までしかクエリを投げられないということでした。500個のペアではslid pairが存在する確率は65536個の場合に比べて著しく低いので、これで問題が解けることは期待できそうにありません。更に工夫が必要になりそうです。
この工夫は天才的なひらめきをするか、全ての考えられる組み合わせをやってみるか、問題設定から感じ取る必要があるのですが、
としてみます。ここで
です。
この時次の関係が成り立ちます。なぜこうなるかまで逐一説明したかったのですが（私が）却って混乱するので気になる場合は自分で追いかけてみてください。
この場合は
が成り立っていればslid pairと判断でき、slid pairが得られればを全探索しながらうまく一致する鍵を探せば
が求まり、
より
を全探索してkey全体を求めることができます。
今回は
の値は
によって決まっているので、slid pairが存在するには
の組み合わせが偶然いい感じになればよく、birthday boundは
ということになりそうです。これなら500回もクエリできれば十分そうに見えます。
exploit
でき上がったものがこちら
from ptrlib import Socket, chunks
from tqdm import tqdm
import secrets
ROUNDS = 2**22 + 2
sbox = [109, 86, 136, 240, 199, 237, 30, 94, 134, 162, 49, 78, 111, 172, 214, 117, 90, 226, 171, 105, 248, 216, 48, 196, 130, 203, 179, 223, 12, 123, 228, 96, 225, 113, 168, 5, 208, 124, 146, 184, 206, 77, 72, 155, 191, 83, 142, 197, 144, 218, 255, 39, 236, 221, 251, 102, 207, 57, 15, 159, 98, 80, 145, 22, 235, 63, 125, 120, 245, 198, 10, 233, 56, 92, 99, 55, 187, 43, 25, 210, 153, 101, 44, 252, 93, 82, 182, 9, 36, 247, 129, 3, 84, 74, 128, 69, 20, 246, 141, 2, 41, 169, 59, 217, 137, 95, 189, 138, 116, 7, 180, 60, 18, 238, 73, 133, 121, 62, 87, 40, 213, 37, 33, 122, 200, 192, 118, 205, 135, 53, 58, 89, 201, 21, 193, 149, 8, 112, 81, 243, 131, 158, 188, 154, 211, 147, 164, 195, 181, 222, 178, 67, 76, 115, 150, 127, 103, 254, 1, 249, 186, 88, 177, 61, 14, 152, 106, 161, 229, 70, 160, 175, 29, 224, 66, 38, 91, 79, 185, 114, 190, 6, 110, 194, 250, 119, 0, 230, 176, 51, 104, 219, 215, 151, 75, 13, 23, 165, 11, 139, 42, 167, 52, 85, 156, 253, 163, 19, 35, 140, 107, 31, 143, 166, 32, 47, 132, 239, 234, 71, 241, 157, 170, 64, 100, 16, 97, 227, 204, 34, 4, 50, 126, 209, 174, 46, 45, 28, 232, 24, 212, 244, 220, 173, 17, 54, 231, 108, 65, 202, 27, 68, 26, 183, 148, 242]
inv = {v:i for i,v in enumerate(sbox)}
def encrypt1(k, plaintext):
a,b,c,d = plaintext
for i in range(ROUNDS):
a ^= sbox[b ^ k[(2*i)&3]]
c ^= sbox[d ^ k[(2*i+1)&3]]
a,b,c,d = b,c,d,a
return bytes([a,b,c,d])
def encrypt1_reduced(k, plaintext):
a,b,c,d = plaintext
order = 0
for i in range(ROUNDS):
a ^= sbox[b ^ k[(2*i)&3]]
c ^= sbox[d ^ k[(2*i+1)&3]]
a,b,c,d = b,c,d,a
key = bytes([a,b,c,d])
if key == plaintext:
order = i + 1
break
else:
raise ValueError("ha?")
for i in range(ROUNDS % order):
a ^= sbox[b ^ k[(2*i)&3]]
c ^= sbox[d ^ k[(2*i+1)&3]]
a,b,c,d = b,c,d,a
return bytes([a,b,c,d])
def encrypt2(k, plaintext):
a,b,c,d = plaintext
for i in range(ROUNDS)[::-1]:
b,c,d,a = a,b,c,d
c ^= sbox[d ^ k[(2*i)&3]]
a ^= sbox[b ^ k[(2*i+1)&3]]
return bytes([a,b,c,d])
def encrypt2_reduced(k, plaintext):
a,b,c,d = plaintext
order = 0
for i in range(ROUNDS)[::-1]:
b,c,d,a = a,b,c,d
c ^= sbox[d ^ k[(2*i)&3]]
a ^= sbox[b ^ k[(2*i+1)&3]]
key = bytes([a,b,c,d])
order += 1
if key == plaintext:
break
else:
raise ValueError("ha?")
for i in range(ROUNDS % order)[::-1]:
b,c,d,a = a,b,c,d
c ^= sbox[d ^ k[(2*i)&3]]
a ^= sbox[b ^ k[(2*i+1)&3]]
return bytes([a,b,c,d])
N = 500
def main():
sock = Socket("localhost", 9999)
B, D = secrets.token_bytes(2)
query1 = set()
while len(query1) != N:
a, c = secrets.token_bytes(2)
query1.add(bytes([a, B, c, D]))
query1 = list(query1)
query2 = set()
while len(query2) != N:
a, c = secrets.token_bytes(2)
query2.add(bytes([c, D, a, B]))
query2 = list(query2)
sock.recvuntil("ENCRYPT 1")
sock.sendlineafter("hex): ", b"".join(query1).hex())
sock.recvuntil("ENCRYPT 2")
sock.sendlineafter("hex): ", b"".join(query2).hex())
res = bytes.fromhex(sock.recvlineafter("result:").decode().strip())
res = chunks(res, 4)
res1 = res[:N]
res2 = res[N:]
for i in tqdm(range(len(res1))):
a, b, c, d = query1[i]
x, y, z, w = res1[i]
for j in range(len(res2)):
a_, b_, c_, d_ = query2[j]
x_, y_, z_, w_ = res2[j]
if y_ == w and w_ == y:
print("[+] slid pair is found")
for t in tqdm(range(256)):
k0 = inv[c_ ^ t ^ a] ^ b
k1 = inv[a_ ^ t ^ c] ^ d
k0_ = inv[x ^ t ^ z_] ^ y
k1_ = inv[z ^ t ^ x_] ^ w
if k0 == k0_ and k1 == k1_:
print("[+] delta is found")
for k2 in tqdm(range(256)):
k3 = t ^ k2
key = bytes([k0, k1, k2, k3])
if encrypt1_reduced(key, query1[i]) == res1[i]:
print("k2, k3 are found")
print("key is: {}".format(key.hex()))
sock.sendlineafter("hex): ", key.hex())
sock.interactive()
quit()
if __name__ == '__main__':
main()
まとめ
ブロック暗号でラウンド鍵が使い回されている場合に誕生日攻撃によって任意のラウンド数だけずれた平文と暗号文のペア、slid pairを発見することによって任意のラウンドだけが適用されたペアを発見し攻撃するというスライド攻撃の原理を紹介し、応用としてPlaid CTF 2022で出題されてchoreographyという問題を解いてきました。いかがでしたか？ 私はこんなの解けるわけないだろと思いましたが、本番で意外と14solves もあるんですよね。嘘だろ！ それでpressureが18solvesということは、CTF界隈の暗号屋は大別して何でも解ける層と何も解けない層に分類されることがわかりますね。そこそこの問題だけ解けるという存在は意外とレアなのか……？
スライド攻撃についてここがわからなかった / スライド攻撃のことをお前は何もわかっとらん。教えたるから正座せんかい / choreographyはこう考えるとわかりやすいです / 〇〇についても知りたいですなどの声をお待ちしております
参考文献
