狠狠撸

CTF勉強会 #3
Crypto編
20151220
trmr (@trmr105)
katagaitai

注意事項
? 本スライドは勉強会で利用したものを元に作成しています。
? 勉強会では問題サーバを利用しましたが、既に停止しています。
? 問題サーバのIPやホスト名が出てくる箇所がありますが、随時読み
替えをお願いいたします。
? リンク切れ等ご容赦ください。
? 問題は下記URLに配置しています。
? http://pastebin.com/Ea3Gm8w2
? 最後のページに勉強会参加者有志のwriteupを載せています。
? 私のwriteupよりも100倍いい出来なので、ぜひそちらを参照してく
ださい。
2

上級編とはなんぞや
好きなことを分かり合える人を増やしたい！
3

楽しみにしていること
Twitterの巡回 Writeup収集
#katagaitaiCTF
4

katagaitaiと愉快な仲間たち
? 今回発表する人
? bata(@bata_24) リーダー
? trmr(@trmr105) センセイ
? 資料レビュー
? askn(@asai_ken) エース
# 実は他にも結構いるらしい
# 総数は誰も知らない
We are katagaitai!
5

今日の問題
? [Ghost in the shellcode CTF 2013] Q20 - Subme
CODE
6

今日submeをやるべき4つの理由
? 共通鍵暗号だから
? 公開鍵暗号の解き方がパターン化してる問題
? あまりwriteupないから
? MSLCのwriteupしか見つけられんかった
? たぶんMMAがもっと詳しいwriteup書いてくれるはず
? 暗号解析してるから
? 問題を解く過程が実際の暗号アルゴリズム解析に近い気がし
た
? 最近の問題についていけてないから
? 子育てに追われている
? 復帰目指して頑張る
7

最初の問題
? まずはじめに次のSHA1ハッシュを要求される
? SHA1ハッシュの末尾16ビットが”1”
? 入力値が与えられた文字列で始まる
? 入力長は21バイト
? 腕慣らしにやってみましょう。
? 終わったら問題を解き始めてください。
20分8

共通鍵暗号と公開鍵暗号
? 共通鍵暗号 – 共通の鍵を利用して暗号化/復号を実施
? 公開鍵暗号 – 暗号化と復号に異なる鍵を利用
9

共通鍵暗号のカテゴリー
? 大体このようなカテゴリわけできる（はず）
? ストリーム暗号
? LFSR型：snow, K-Cipher2 etc.
? 状態遷移型：RC4, trivium, chacha-20 etc.
? ブロック暗号
? Feistel構造：DES, MISTY, Camellia etc.
? SPN構造：AES, Serpent etc.
今日はこれ
10

SPN構造
? GaborPete
AddRoundKey
Substitution
Permutation
1 Round is
and iterate it
12

SPN構造の概要
? Substitution
? 非線形関数で乱雑化
? 小さい単位（バイト）ごとに処理することが多い
? 置換テーブル（S-box）が利用されることが多い
? Permutation
? 全体をシャッフルして影響を広範化
? ブロック全体に対する処理
Input
S S S S S S S S
Permutation
13

SPN構造の概要
? Substitution
? 非線形関数で乱雑化
? 小さい単位（バイト）ごとに処理することが多い
? 置換テーブル（S-box）が利用されることが多い
? Permutation
? 全体をシャッフルして影響を広範化
? ブロック全体に対する処理
S S S S S S S S
Permutation
1byteの違いが
全体に影響
14

AESを見ていこう！
? AES: Advanced Encryption Standard
? 元Rijndael。リンデール？ラインダール？
? 2001年にFIPS197。米国標準なのにベルギー製
? 128, 192, 256bitがあり、微妙に仕様が違う
15

AESの構造
? AES: Advanced Encryption Standard
? 初期化として
? KEY EXPANTION
? 通常処理として下記処理を1ラウンドとする
? AddRoundKey
? SubBytes
? ShiftRows
? MixColumns
? 上記処理を10ラウンド繰り返す(128bitの場合)
16

AESの構造 (1ラウンド)
Input
Key (K) (expanded)
Output
S S S S S S S S
MixColumns
1 AddRoundKey
2 SubBytes
ShiftRows 3 ShiftRows
4 MixColumns
17

AESの構造 (1ラウンド)
Input
Key (K) (expanded)
Output
S S S S S S S S
MixColumns
1 AddRoundKey
2 SubBytes
→ Substitution
ShiftRows 3 ShiftRows
→ Permutation
4 MixColumns
→ Permutation
Permutation
18

AESの全体概観
S S S S S S S S
ShiftRowsPermutation
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
平文
暗号文
19

AESの全体概観
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
平文
暗号文
AESを書くのはしんどい
20

submeのソースコード
? Subme.py
21

? Subme.py
22
1 AddRoundKey
2 Substitution
3 Permutation

? Subme.py
23
1 AddRoundKey
2 Substitution
3 Permutation
AESと同じSPN構造やん！

? 説明の都合上、下記と定義
24
Step 1
Step 2
Step 3

Submeの構造
Step1
Plaintext (P)
Key (K)
Ciphertext (C)
Step2
Step3
25

Subme Step1
Input
Key (K)
Output
S S S S S S S S
Permutation
26

Subme Step1
Input
Key (K)
Output
S S S S S S S S
Permutation
1-2 S-box変換
=Substitution
1-3 置換テーブル変換
=Permutation
1-1 入力に鍵の値をXoR
=AddRoundKey
27

Subme Step2
Input
Key (K)
Output
S S S S S S S S
Permutation
1-2 S-box変換
=Substitution
=Permutation
=AddRoundKey
Step2はStep1と同じ処理
28

Subme Step3
Input
Key (K)
Output
3-1 入力値をbyte単位
でリバース
3-2 鍵の値を足す
※ 桁上がり分は捨てる
Add
29

Subme 全体概観
Output
S S S S S S S S
Permutation
S S S S S S S S
Permutation
+
平文
暗号文
30

[再掲] AESの全体概観
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
平文
暗号文
31

比較
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
Permutation
S S S S S S S S
Permutation
AES subme
32

比較
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
S S S S S S S S
Permutation
S S S S S S S S
Permutation
AES subme
Submeは解けそうな気がする！
33

比較
? ラウンド数
? AES-128:10ラウンド
? Subme:2ラウンド
? 変換処理
? Substitution
? AES: [0x63, 0x7c, 0x77,….,0xbb, 0x16]
? Subme: [0x63, 0x7c, 0x77,….,0xbb, 0x16]
? Permutation
?AES: Shift-Rows&MixColumns
?Subme: bit並び替え
AESと同じ処理でラウンド数が少ない
＝十分鍵の情報が混ざらんのでは？
34

入力情報の適切な攪拌
Key (K) Key (K)
暗号化暗号化
? 入力情報（鍵?平文）の適切な攪拌ができてないと
暗号文に鍵の情報が残る
35

差分解析
Plaintext A Plaintext A + ⊿
Key (K) Key (K)
暗号化暗号化
diff
入力に差分
? 入力情報（鍵?平文）ペアに差分を与える
? 出力に相関が生じないか解析
入力情報が得られる
36

Submeの相関を見ていこう
S S S S S S S S
Permutation
S S S S S S S S
Permutation
+
平文
暗号文
? Stepごとに相関を見ていく
37

定義
Output
S S S S S S S S
Permutation
S S S S S S S S
Permutation
+
平文
暗号文
K1
K2
K3
C11
C12
C13
C21
C22
C23
C31
C=C33
38

Submeの相関（Step 1）
Input
Key (K)
Output
S S S S S S S S
Permutation
1-2 S-box変換
=Substitution
=Permutation
=AddRoundKey
C11
C12
C13
39

Submeの相関（Step 1）
Input
Output
S S S S S S S S
Permutation
Key (K)
C11に1byte差分を与える
Key (K)
Permutationで攪拌も
8bitにしか影響しない
Key (K)
S-boxで非線形変換されるが
他のbyteに影響はしない
C11
C12
C13
40

Submeの相関(Step1)
S S S S S S S S
Permutation
S S S S S S S S
Permutation
Perm(S(A)) Perm(S(A+⊿))
diff
A
A + ⊿
B
41

Submeの差分(Step1)
diff
この差分パターンBが出れば
C11が特定ペアAとA+⊿である可能性が高い
? =
? ??????に差分パターン ?????に差分 ? ?[?????に差分]
?[??????に差分パターン]
42

攻撃原理 (Step1)
? 前提：次の状況を仮定（今回と同じ状況）
? 攻撃者は鍵の情報はわからない
? 任意の平文に対応した暗号文を取得可能（選択平文攻撃）
43

? 差分⊿を決定
? あるC11ペア(A, A+⊿)を決定し差分パターンBを取得
44
S S S S S S S S
Permutation
S S S S S S S S
Permutation
C11[0] = A C11[0] = A + ⊿
K
diff
B

S S S S S S S S
Permutation
S S S S S S S S
Permutation
? 下記の平文を入力(σは{0,..,255}の任意の値)
K
45
P[0] = A+σ P[0] = A+⊿+σ

S S S S S S S S
Permutation
S S S S S S S S
Permutation
? σ ≠ K[0]のとき:とくになし
K
46
P[0] = A+σ P[0] = A+⊿+σ
A + σ + K[0] A + ⊿ +σ + K[0]

S S S S S S S S
Permutation
S S S S S S S S
Permutation
? σ = K[0]のとき:パターンが出る！
K
47
P[0] = A+σ P[0] = A+⊿+σ
A + K[0] + K[0] = A
A + ⊿ + K[0] + K[0]
= A + ⊿

S S S S S S S S
Permutation
S S S S S S S S
Permutation
? σ = K[0]のとき:パターンが出る！
K
48
P[0] = A+σ P[0] = A+⊿+σ
A + K[0] + K[0] = A
A + ⊿ + K[0] + K[0]
= A + ⊿
暗号文に特定の差分パターンBが出た際の
平文の差分σの値が鍵の1バイトと推測可能！

現実はstepは2回ある
S S S S S S S S
Permutation
S S S S S S S S
Permutation
1byte目に差分
Step1終了時に
8bit差分
Step2終了時に
全体に広がる
単に入力差分を与えるだけでは
Step2終了時に
全体に攪拌される
→ 解析しづらい
Step1の手法は
この時点の出力が
得られることが前提
49

現実はstepは2回ある
S S S S S S S S
Permutation
S S S S S S S S
Permutation
1byte目に差分
Step1終了時に
8bit差分
Step2終了時に
全体に広がる
単に入力差分を与えるだけでは
Step2終了時に
全体に攪拌される
→ 解析しづらい
Step1の手法は
この時点の出力が
得られるこあと前提
50
Stepを2回実施することで
対策済み？

方針
? 問題点
? 1回のStepだけなら鍵の推測が可能
? 2回のStep実施で鍵の推測が困難に
51
S S S S S S S S
Permutation
S S S S S S S S
Permutation
Step2への入力が
様々なbyteに広がる
ことが問題

方針
? 問題点
? 考察
? Step1の出力が広がらなければ
? Step2の出力はStep1と同等に
52
S S S S S S S S
Permutation
S S S S S S S S
Permutation
都合のよい処理
をするStep1
Step1の出力が
1byteにしか
広がらなければ
Step2の出力が
先のStep1と同等に

方針
? 問題点
? 考察
53
S S S S S S S S
Permutation
全体に
広がってしまう…。
入力差分を
1bitにしてみる
S S S S S S S S
Permutation
S-boxが
byte-to-byte変換

方針
? 問題点
? 考察
54
S S S S S S S S
Permutation
全体に
広がってしまう…。
入力差分を
1bitにしてみる
S S S S S S S S
Permutation
S-boxが
byte-to-byte変換
ここじゃね？

方針
? 問題点
? 考察
55
S S S S S S S S
Permutation
鍵が解読できる
パターンが出力！
ここの差分が
1bitであれば
S S S S S S S S
Permutation
Permutationでは
影響範囲は広がらない

方針
? 問題点
? 考察
56
S S S S S S S S
Permutation
鍵が解読できる
パターンが出力！
ここの差分が
1bitであれば
S S S S S S S S
Permutation
Permutationでは
影響範囲は広がらない
とは言っても
直接内部状態は
いじれない

方針
? 問題点
? 考察
? 方針
? S-boxを1回通過後に1bit差分を
生み出す平文ペアを入力
? 特定の出力が出る差分を探索
57
S S S S S S S S
Permutation
S S S S S S S S
Permutation
S-box通過後に1bit差分を生み
出すような平文ペアを入力
特定の出力
差分パターンをゲット！

平文の作り方
S S S S S S S S
Permutation
S S S S S S S S
Permutation
? 実際に差分がある状態から逆算
K
58
C12[0] = D C12’[0] = D+1

平文の作り方
S S S S S S S S
Permutation
S S S S S S S S
Permutation
K
59
C12[0] = D C12’[0] = D+1
C11[0] = inv_S[D] C12’[0] = inv_S[D+1]

平文の作り方
S S S S S S S S
Permutation
S S S S S S S S
Permutation
K
60
C12[0] = D C12’[0] = D+1
C11[0] = inv_S[D] C12’[0] = inv_S[D+1]
P[0] = inv_S[D]+σ P’[0] = inv_S[D+1]+σ

平文の作り方
S S S S S S S S
Permutation
S S S S S S S S
Permutation
K
61
C12[0] = D C12’[0] = D+ 1
C11[0] = inv_S[D] C12’[0] = inv_S[D+1]
P[0] = inv_S[D]+σ P’[0] = inv_S[D+1]+σ
σ=K[0]のとき暗号文に
特定の差分パターンBが出力
σの値が鍵の1バイトと推測可能！

K1, K2の鍵が解読可能？
S S S S S S S S
Permutation
S S S S S S S S
Permutation
1) 順次試していく
ことでK1が解読
62
2)ここで同様の手順
を実施することで
K2が解読

K1, K2の鍵が解読可能？
S S S S S S S S
Permutation
S S S S S S S S
Permutation
63
2)ここで同様の手順
を実施することで
K2が解読
なんか忘れてない？

? 鍵の処理がXoRではなくAdd
? 2進数で見た際に桁上がりの概念が発生
? XoRで差分をとった際にノイズが混じる
? 差分をとる際に桁上がりを意識する必要がある
Input = Step2の出力
Key (K)
Output
3-1 入力値をbyte単位
でリバース
3-2 鍵の値を足す
※ 桁上がり分は捨てる
Add
64

? もしK3がXoRであればStep2の出力がXoRで出る
Output
65
Output
diff

? もしK3がAddであればStep2の出力がXoRで出る
Output
66
Output
diff
足し算なのでXoRで
Step2の出力が出ない

AddとXoRの違い
? XoRの場合
１１１１ 0 １１１１
１１１１ 0 １ 0 0 １
67
暗号文 C
暗号文 C’
0 1 0 0 1 1 0 1 0 K3
0 1 0 0 1 1 0 1 0 K3
1 0 1 1 1 0 1 0 1
1 0 1 1 0 0 0 1 1
C23
C23’
XoR
XoR

AddとXoRの違い
? XoRの場合
１１１１ 0 １１１１
１１１１ 0 １ 0 0 １
暗号文のXoR
0 0 0 0 1 0 1 1 0
68
暗号文 C
暗号文 C’
0 1 0 0 1 1 0 1 0 K3
0 1 0 0 1 1 0 1 0 K3
1 0 1 1 1 0 1 0 1
1 0 1 1 0 0 0 1 1
C23
C23’
XoR
XoR
C23のXoR
0 0 0 0 1 0 1 1 0
期待する差分パターン出力差分パターン

AddとXoRの違い
? XoRの場合
１１１１ 0 １１１１
１１１１ 0 １ 0 0 １
暗号文のXoR
0 0 0 0 1 0 1 1 0
69
暗号文 C
暗号文 C’
0 1 0 0 1 1 0 1 0 K3
0 1 0 0 1 1 0 1 0 K3
1 0 1 1 1 0 1 0 1
1 0 1 1 0 0 0 1 1
C23
C23’
XoR
XoR
C23のXoR
0 0 0 0 1 0 1 1 0
K3がXoRであれば暗号文ペアのXoRは
C23, C23’のXoRと一致する

AddとXoRの違い
? Addの場合
0 0 0 0 0 1 1 1 1
1 1 1 1 1 1 1 0 1
70
暗号文 C
暗号文 C’
0 1 0 0 1 1 0 1 0 K3
0 1 0 0 1 1 0 1 0 K3
1 0 1 1 1 0 1 0 1
1 0 1 1 0 0 0 1 1
C23
C23’
Add
Add

AddとXoRの違い
? Addの場合
0 0 0 0 0 1 1 1 1
1 1 1 1 1 1 1 0 1
71
暗号文 C
暗号文 C’
0 1 0 0 1 1 0 1 0 K3
0 1 0 0 1 1 0 1 0 K3
1 0 1 1 1 0 1 0 1
1 0 1 1 0 0 0 1 1
C23
C23’
Add
Add
暗号文のXoR
1 1 1 1 1 0 0 1 0
C23のXoR
0 0 0 0 1 0 1 1 0

AddとXoRの違い
? Addの場合
0 0 0 0 0 1 1 1 1
1 1 1 1 1 1 1 0 1
72
暗号文 C
暗号文 C’
0 1 0 0 1 1 0 1 0 K3
0 1 0 0 1 1 0 1 0 K3
1 0 1 1 1 0 1 0 1
1 0 1 1 0 0 0 1 1
C23
C23’
Add
Add
暗号文のXoR
1 1 1 1 1 0 0 1 0
C23のXoR
0 0 0 0 1 0 1 1 0
K3がAddなので暗号文ペアのXoRは
C23, C23’のXoRと一致しない

AddとXoRの違い
? AddとXoRの違い = 繰り上がり
XoR
1 1 1 1 0 0 1 0 0
73
0 0 0 0 1 0 1 1 0
1 1 1 1 1 0 0 1 0
C23,C23’の差分
Addの出力差分
Addの出力差分（繰り上がり）の特徴
?C23,C23’の差分で1が立ってる場所以降に1が出力
?必ず連続して出力

trmr版Step3攻略
? 下記手法で識別
? もっといい方法はあるはず
1 0 0 1 0 0 0 0 1
74
事前にC23,C23’の
差分パターン取得

trmr版Step3攻略
? 下記手法で識別
? もっといい方法はあるはず
1 0 0 1 0 0 0 0 1
75
事前にC23,C23’の
差分パターン取得
1 0 1 0 0 1 0 1 1
平文ペアP[0], P’[0]
のdiff結果
XoR
0 0 1 1 0 1 0 1 0XoR結果が次の条件を
満たすか確認
?C23,C23’で1が立っ
てる場所から連続して
1が立っているか
NG

すべての鍵を解読可能
S S S S S S S S
Permutation
S S S S S S S S
Permutation
+
? Stepごとに鍵を導出
76
3)K3 =
暗号文 – C23

実習
? とりあえずやってみましょう
? 先にwriteupを紹介します
? trmr版：http://pastebin.com/WQdc2knT
? MSLC版：http://mslc.ctf.su/wp/gits-ctf-2013-crypto-500
? わかる人はガシガシやってください
? 残り30分になったらwriteupのコード解説しようと思ってます
? が、そんな良いコードでもないのであんまやりたくないです
? 誰か書き直して
? 音楽にリクエストがあれば@trmr105または#katagaitaiでツ
イートしてください
90分77

trmr版Submeの解き方
? 差分を使った解き方はいろいろある、と思う。
? あくまで一例。
78

? 1) C12の差分リストをGET
79
C12が1bit違うとC22は1byte異なる。
それぞれの出力差分が出る場所を、submeのpermutation
テーブルより求めれば、差分リストとなる

? 2) 鍵を戻すよー
80
C12と差分1ビットのC12’を作成
Inv_S変換したものを暗号化
※リスト処理してるのは、
サーバ負荷と計算速度のため
出力のdiffが差分リストに
合致してるかチェック

? 3) 差分チェック (MSLCインスパイア)
? そんな変わったことはしてないけど
81
差分リストの場所以降は
繰り上がりの可能性あり
実際の出力差分とリストの違いが
連続しなければ繰り上がりの
可能性がなくなったと仮定
繰り上がりの可能性がない状態で
出力差分とリストに違いがあれば
NG

解答
? Key{HackerLikesHakkaAme}
? ※k1||k2||k3[::-1]の値
? Flag{HackTheKatagaitai!}
? と、いう値が勉強会の問題サーバでは入っていました。
82

[余談]当日のtrmr
? Step3
? 鍵をAdd
? AddはXoRと高い相関
? 2つの出力の差分をとればほぼ消せる
? Step1,2
? S-box
s = [0x63, 0x7c, 0x77,….,0xbb, 0x16]
→ AESと同じs-boxを利用
? Permutation → bitの並び替え
? 実施したこと
? Step3はいったん無視して2回Step1を通った入力と出力に着目
? 差分を与えたペアを作成し、相関分析
→ 解けなかった
何かしら差分を与えて、それ
らのペアをXoRしてやれば、
面白い相関が出そう
AESと同じs-box
→ いったん安全と仮定
置換テーブル
→ 1byteの違いを8bitに攪拌
→ 1回のラウンドで大きく攪
拌するわけではない
83

参考文献
? 参考文献
? More Smoked Leet Chicken
? http://mslc.ctf.su/wp/gits-ctf-2013-crypto-500/
? Wikipedia[英語版]
? https://en.wikipedia.org/wiki/Advanced_Encryption_Standard
? 暗号技術大全 (アップデート希望)
? その他論文
84

Writeup & Impression85
? 勉強会実施後のreconで見つけたwriteupや感想です。
? http://fish.minidns.net/news/55
? kanataさんによる感想。今頃解いてくれてるはず？
? http://qiita.com/kusano_k/items/33d3d634f80a4999a400
? kusano_kさんによるwriteup。3段目の導出処理を変えてるのがさ
すがです。
? https://bitbucket.org/snippets/nomeaning777/kEK5j
? no_meaningさんによるwriteup。rubyにて記述。これも3段目の導
出処理を変えてますね。
? 他載せられてない人。私のRecon力不足です。ごめんなさい。
? もしwriteup書いたらtwitter等で連絡いただけると助かります。

狠狠撸

katagaitai CTF勉強会 #3 crypto

Recommended

More Related Content

What's hot (20)

Recently uploaded (8)

katagaitai CTF勉強会 #3 crypto