note

この記事は次を見た後に書いた。

参照されてるページは私も見た記憶があるが、回答がなくコメントだけだったので素通りしてしまっていた。反省したい。

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)$ を提出せよ:

  1. 衝突: $(k_1, x_1) \ne (k_2, x_2)$ かつ $F_{k_1}(x_1) = F_{k_2}(x_2)$
  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}$個以上あると推測できる。