Katagaitai CTF勉強会　関東med (Crypt 理論編？）

先週末に行ってきた勉強会。とてもタメになった。

が、なかなか本腰いれて取り組めないので、少しずつアップすることにした。

今回は午前中のcryptについて、理論面を整理。 実装は、きっとこのあとやる・・・はず。

問題

CSAW CTF 2014 – Crypto300 – feal.py

FEAL（the Fast Data Encipherment Algorithm）

https://ja.wikipedia.org/wiki/FEAL

の復号を扱う問題。

第１段階

特定条件を満たす値が要求される

  • a sha1 sum ending in 16bits set to 1
  • it must be of length 21 bytes
  • starting with [毎度変化する乱数]

時間制限は特に無いもよう。 何度か試したが乱数は必ず16byteなので、21-16=5byteのブルートフォースを考える。

以下のループを作る。（速度考えC言語）

  • 末尾5byteを1bitずつインクリメントする
  • 各ループでSHA1hashを計算
  • 計算したSHA1hashの末尾16bitが1になっていたらbreak

また、ネットワーク経由で回答するので、以下のスクリプトを用意

第2段階

暗号文の復号を求められる。

任意の値を入力すると、その暗号化結果を返してくる。 （この時、同じ鍵を使って暗号化している）

↑重要。しばらくこれに気づかなかったので解法のアプローチが理解できなかった

問題名をググるとFEAL暗号に行き着く。

金言：暗号問題は、とにかくググッて暗号文アルゴリズムと解法を見つける

FEAL暗号の仕組みを書こうとすると勉強会スライドのコピペになってしまいそうなので、自分が理解する過程で書いたメモをここにおいておく。

注意点(自分へのToDoも兼ねて）

  • ページ数は勉強会資料のスライド番号
  • 勉強会資料のURLは公開され次第反映予定（覚えていれば
  • 勉強会当時と内容が修正されている場合、ページ数に齟齬が出るかも（覚えていれば修正する
  • 以降勉強会資料中では XOR演算を + と表記しているので、ここでもそれに習います。 （+ は加算ではないので注意）

FEALの概要 (pp25-27)

暗号解析のアプローチ(pp28-29)

僅かに異なる2つの入力を与えてみて、暗号化結果の相関を見る。 （共通部分が同じ暗号化結果になる場合、それはヒントになり得る）

差分解析

FEALにおける差分解析の有効性(pp30-31)

４ラウンドあるので、１ラウンドずつ見ていく。(p30)

  • 8byte毎に分割した4つの入力を処理しているので、これらの組み合わせ（同じ／違う）を考える
  • ラウンド内にある関数G0,G1は入力が(0,0)の場合に特定の値(0 or 4)を吐き出す。
    • Gn(a,b) = (n or a or b) mod 256 <<< 2
    • G0(0,0) = (0 or 0 or 0) mod 256 <<< 2 = 0 <<< 0 = 0
    • G1(0,0) = (1 or 0 or 0) mod 256 <<< 2 = 1 <<< 2 = 4

x0～x4までの値の組み合わせを工夫して、G0とG1への入力を0にする方法を考える
（考えるというか、誰かが考えた内容を見つけて理解する）

解析手順(p32)

  • 途中にXOR演算が存在する
  • XOR演算の箇所に同じ値が入るようにすれば 0 が作れる

具体的な値を入れて差分をとってみる(pp33- )

(pp33-34)

図中でも書いてくれているが、自分で各値を計算して整理してみたのが以下。
（計算して資料と合わない点は質問ちう）

(x0,x1,x2,x3) → (y0,y1,y2,y3)
とした時、y0～y3の定義は

y0 = G0(x0, y1)
= G0(x0, G1(x0+x1, x2+x3))
y1 = G1(x0+x1, x2+x3)
y2 = G0(y1, x2+x3)
= G0(G1(x0+y1,x2+x3), x2+x3)
y3 = G1(y2, x3)
= G1(G0(G1(x0+y1,x2+x3), x2+x3),x3)

ここで、x0=x1, x2=x3 とすると、x0+x1=0, x2+x3=0のため、

y0 = G0(x0, G1(x0+x1, x2+x3))
= G0(x0, G1(0,0))
= G0(x0, 4)
y1 = G1(0,0)
= 4
y2 = G0(y1,0)
= G0(4,0)
= 16
y3 = G1(16,x3)

スライドだとy2=32だが? →(2/6追記)
bataさんより、本問は3bitシフトなので32で正しいとご指摘いただいた。

確かに、ソースを見たらその通りだった。
何故見ようとしなかったのだろう・・・

def rot3(x):
    return ((x<<3)|(x>>5))&0xff
def gBox(a,b,mode):
    return rot3((a+b+mode)%256)

(追記おわり)

もう一つの入力

(x'0,x'1,x'2,x'3) → (y'0,y'1,y'2,y'3)

については、x,yをx',y'にするだけなので省略

差分は

⊿y0 = G0(x0,4)+G0(x'0,4)
⊿y1 = 4 + 4
= 0 （※一見おかしいけど、 + は xor なので正しい）
⊿y2 = 32 + 32
= 0
⊿y3 = G1(32,x3) + G1(32,x'3)

出力差分がx1, x3のみに依存する＝偏る

(pp35-36)

  • X = 0x00000000 (X0=0x00, X1=0x00, X2=0x00, X3=0x00)
  • X' = 0x80800000 (X0=0x80, X1=0x80, X2=0x00, X3=0x00)
y0 = G0(0,4) = 0x10
y'0 = G0(0x80,4) = 0x84 <<< 3 = 0x12 
⊿y0 = 0x02

y3 = y'3 = G1(32, 0)
⊿y3 = 0
  • 特定の⊿xになる入力で⊿yを推測可能 *

(pp37-41)

以上は1ラウンドだけの話
これを4ラウンド続けたらどうなるか。

Y, Y'を計算してから⊿Yを導いてみる

  • X = 0x00000000 (X0=0x00, X1=0x00, X2=0x00, X3=0x00)
  • X' = 0x80800000 (X0=0x80, X1=0x80, X2=0x00, X3=0x00)

1段目入力

左：P1l=X+K4 ⊿P1l=⊿X
右：P1r=K4+K5 ⊿P1r=0

1段目出力

左：C1l=X+K4+f(K0+K4+K5)
⊿C1l = ⊿X = 0x80800000
右；C1r=K4+K5
⊿C1r = 0

2段目入力

左：P2l=P1r ⊿P2l = 0
右：P2r=C1l ⊿P2r = 0x80800000

2段目出力

左：C2l=P2l+f(K1+C1l)
⊿C2l = f(0x80800000) = 0x02000000
右：C2r=P2r
⊿C2r = 0x80800000

3段目入力

左：P3l=C2r ⊿P3l=0x80800000
右：P3r=C2l ⊿P3r=0x02000000

3段目出力

左：C3l=P3l+f(K2+P3r)
⊿C3l = 0x80800000 + ⊿f(K2+P3r) = ???
右：C3r=P3r
⊿C3r = 0x02000000

4段目入力

左：P4l=C3r ⊿P4l=0x02000000
右：P4r=C3l ⊿P4r=不明

4段目出力

左：C4l=P4l+f(K3+P4r)
⊿不明
右：C4r=P4r
⊿P4r=不明

(pp42-46)

最終的な出力から考えてみると、

左出力： Cl = C4l
右出力： Cr = C4r+C4l = P4r + Cl

よって、

P4r=Cr+Cl となる。

つまり、狙った差分の入力X,X'から、C, C'を得られれば、逆算可能。
（そして、C,C'は暗号化結果なので取得可能な値）

(pp47-53)

4つの値（左右入出力差分）がわかったので、Key3が逆算可能

あとは芋づる式に K2, K1 K0, K4, K5 を求める。

K3：
⊿C1= ⊿P4l+f(C4r+K3)+f(C'4r+K3)
=0x02000000+f(Cl+Cr+K3)+f(C'l+C'r+K3)
C4r=Cr+Cl
C4l=Cl
K2:
⊿C3l=⊿P3l+f(C3r+K2)+f(C'3r+K2)
C3r=C4l+f(C4r+K3)
C3l=C4r
K1:
⊿C2l=⊿P2l+f(C2r+K1)+f(C'2r+K1)
C2r=C3l+f(C3r+K2)
=C1+C2+f(C3r+K2)
C2l=C3r
K0:
⊿C1l=⊿P1l+f(C1r+K0)+f(C'1r+K0)
C1r=C2l+f(C2r+K0)
C1l=C2r
K4:
K4=P1l+Pl=C1l+f(C1r+K0)+Pl
K5:
K5=C1r+Pr+K4+Pl

後はこれを実装すれば、きっと・・・（まだやっていない）