Google Capture The Flag 2018 (Quals): DM Collision
note
この記事は次を見た後に書いた。
DM COLLISION、これを見て、100億連ガチャを回してそのままにして寝ていたら衝突してた……。信じてもっと早めに試していれば……。
— kusanoさん@がんばらない (@kusano_k) 2018年6月25日
block cipher - What is the fixed point attribute of DES (when used with weak-keys) - Cryptography Stack Exchangehttps://t.co/rGM5SrzwxQ pic.twitter.com/9gPzfmwLYH
参照されてるページは私も見た記憶があるが、回答がなくコメントだけだったので素通りしてしまっていた。反省したい。
problem
S-boxの順序が次のように変更されているDESを用いて、Davies-Meyer型 one-way compression function $F_k(x) = E_k(x) \oplus x$ を考える。
SBOXES = [S6, S4, S1, S5, S3, S2, S8, S7]
次を満たすような $(k_1, x_1), (k_2, x_2), (k_3, x_3)$ を提出せよ:
- 衝突: $(k_1, x_1) \ne (k_2, x_2)$ かつ $F_{k_1}(x_1) = F_{k_2}(x_2)$
- 原像: $F_{k_3}(x_3) = 0$
solution
衝突
DESの鍵にはparity bitというものがあり、これは歴史的なもので現在ではたいてい無視される (参考)。 具体的には各byteのLSB。例としては次を実行せよ:
#!/usr/bin/env python3
import Crypto.Cipher.DES # https://pypi.org/project/pycrypto/
key1 = "01234567"
des1 = Crypto.Cipher.DES.new(key1, Crypto.Cipher.DES.MODE_ECB)
key2 = "10325476"
des2 = Crypto.Cipher.DES.new(key2, Crypto.Cipher.DES.MODE_ECB)
plaintext = b"Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliq"
assert des2.decrypt(des1.encrypt(plaintext)) == plaintext
これはS-boxの順序には依存しないため同様にすればよい。
原像
これはDESの不動点を求めろという問題である。
$F_k(x) = E_k(x) \oplus x = 0$ を変形すると $E_k(x) = x$ なため。
検索すると「weak-keyなら$2^{32}$個の不動点があるよ」とでてくる (SO)。
これもS-boxの順序には依存しない。
全空間は$2^{64}$なので$10^9$個ぐらい試せばよくて、これは十分可能。
not_des.py
をそのまま使うと$100$個/秒と厳しいが、Cで実装して$100$倍速と仮定、さらに並列化で例えば$32$倍速と仮定すると、これは$1$時間程度で結果が出ると予想できる (試してはいない)。
不動点が$2^{32}$個というのの説明があるのはこれ: The Real Reason for Rivest’s Phenomenon | SpringerLink。 たった$2$ページと読みやすいので読んで。 概要は以下。 DESはFeistel構造なのでそのround関数を$f$があって、平文が$M_0, M_1$と分割され $M_{i+1} = M_{i-1} \oplus f(K_i, M_i)$ と処理されて$M_{17}, M_{16}$が暗号文。 weak-keyを選べば内部鍵$K_i$はすべて一致し、加えて $M_8 = M_9$ なら$M_7 = M_{10}, M_6 = M_{11}, \dots$と伝播して平文と暗号文が一致する。 さて$M_8 = M_9$となるような入力$Y$がいくつあるかだが、内部状態$M_8, M_9 \in 2^{32}$なので(ぞろ目の出る確率のように見て)確率$\frac{1}{2^{32}}$で一致し、入力は$Y \in 2^{64}$。 よって不動点はおよそ$2^{32}$個以上あると推測できる。