狠狠撸

katagaitai
CTF Workshop #7
Crypto
2017.02.25 TOKYO
trmr (@trmr105)
katagaitai

#7 はじまるよー！
? katagaitai CTF勉強会の歴史
? 2012年～2014年：某所での下積み時代
? 2014年冬：CTF勉強会 #1 共通素数を持つRSA
? 2015年夏：CTF勉強会 #2 CRIME
? 2015年冬：CTF勉強会 #3 SPN構造ブロック暗号の差分解析
? 2015年冬：CTF勉強会 #4 Feistel構造ブロック暗号の差分解析
? 2016年夏：CTF勉強会 #5 ハッシュ関数の衝突＆Length Extention
? 2016年夏：CTF勉強会 #6 ー
? 2016年冬：CTF勉強会 #7 ナップサック暗号
? 下記URLで過去の勉強会資料を公開中
? https://speakerdeck.com/bata_24
? http://www.slideshare.net/trmr105
イマココ！
2

katagaitai勉強会とは
好きなことを分かり合える人を増やしたい！
3

Special Thanks
? 本資料は以下の方にご協力いただいてます
? Bonoさん（@bono_ipad）
? shiho midorikawaさん（@elliptic_shiho）
? nomeaningさん（@__nomeaning__ ）
4

katagaitaiのモチベーション
Twitterの巡回 Writeup収集
#katagaitaiCTF
5

katagaitaiとの約束6
W
r
i
t
e
u
p
書

今日の問題
? [TW CTF 2nd 2016] Crypto200 – Backpacker’s cipher easy mode
? [Plaid CTF 2015] Crypto180 – Lazy
? [TW CTF 2nd 2016] Crypto450 – Backpacker’s cipher extra mode
7
TWCTF : Tokyo Westerns/MMA CTF

目次
? ナップサック暗号
? 数学のお話
8

公開鍵暗号
? 公開鍵暗号
? 暗号化用の鍵（公開鍵）と復号用の鍵（秘密鍵）が異なる暗
号
? 一方向性関数を利用して構築
? 一方向性関数
? 入力→出力は容易に計算可能
? 出力→入力が計算が困難
? 一方向性関数の例
? 素因数分解問題 -> RSA
? 離散対数問題 -> Elgamal, 楕円曲線暗号
? 部分和問題 -> ナップサック暗号 etc.
10

部分和問題
? 部分和問題 (subset sum problem)
? (?1, … , ? ?)からある値?を構成する部分和を見つける問題
? ?=0
?
?? ? ?? = ?となるような (?1, ?2, ? , ? ?)を導出する問題
? ?? ∈ 0,1 ; ? ∈ { 1, … , ?}
? NP完全：多項式時間で答えを見つけることができない
? ?の値が大きい場合、 (?1, ?2, ? , ? ?)を求めることは計算量的に困難
11
例
? = 1,3,7,15,40
? = 1,0,1,1,0
? = 1 + 7 + 15 = 23
Photo by Dake

ナップサック暗号
? ナップサック暗号 (knapsack crypto system)
? 一方向性関数として部分和問題を利用
? 秘密鍵：? = { ?1, … , ? ? | ?? ∈ ?}; ?, ?
? ? > ?=1
?
??
? ?, ?は互いに素
? 公開鍵：? = { ?1, … , ? ? | ?? = ? ? ?? mod ?}
? 平文：? = ?1, … , ? ? ?? ∈ {0,1}}
? 暗号化
? ?=1
?
?? ? ?? = ?
? 暗号文?から平文/鍵を導出するには？
? 部分和問題を解く必要
? このままでは受信者も平文を導出できないのでトラップドアが必要
? MHナップサック暗号
? トラップドアに超増加数列を利用
? 超増加数列：? ?+1 > ?=1
?
?? を満たす数列(?1, … , ? ?)
12

トラップドアと超増加数列
? トラップドアを用いた部分和の導出
? 超増加数列の性質より、下記で??を導出可能
? ? ? = ?=1
?
?? ? ? ?, ? = ? とする
? ① ? ≥ ? ?であれば、? ? = 1とし、? = ? ? ? ?とする
? ② ? < ? ?であれば、? ? = 0とする
? ③ ?をデクリメント
? ①～③を繰り返す
13
例
? = 1,3,7,15,40 , ? = 23, ? = 5
?5 = 40 > ? よって?5 = 0
?4 = 15 ≤ ? よって?4 = 1 W = 23 ? 15 = 8
?3 = 7 ≤ ? よって?3 = 1 W = 8 ? 7 = 1
?2 = 3 > ? よって?2 = 0
?1 = 1 ≤ ? よって?1 = 1 W = 1 ? 1 = 0
? = 1,0,1,1,0

[TW CTF 2nd 2016] Crypto200
Backpacker’s cipher easy mode14

鍵生成
? 下記が読み取れる
? 秘密鍵： ?1, … , ? ? , ?, ?
? ?? = (????(2 ???
) 1 ? 2?
? ?, ? ：互いに素
? 公開鍵： ?1, … , ? ?
? ?? =q ? ?? ??? ?
15

暗号化
? ①メッセージをDESで暗号化
? DES暗号文：DES ? = {(??1, … , ?? ?)|??? ∈ {0,1}}
? 鍵は秘密ではない（’testpass’）
? ②ナップサック暗号化
? ?=1
?
?? ? ??? = ?
16

復号
? 疲れたらしい
17

方針
? バックパック暗号の「復号」を目指す
? 復号に必要な秘密鍵は？
? 復号に必要なトラップドアは？
? Step 1 秘密鍵の取得
? Step 2 トラップドアを利用した復号
18
Step1：15分
Step2：15分

秘密鍵の取得
? 公開鍵：?? = ? ? (rand(2 ??? ) 1 ? 2? mod ?
? ? = ? の場合、? ? = ? ? 2 ?
mod ?
? rand(2 ???
) 1 = rand 1 1 = 1
? ? = ? ? 1 の場合、? ??1 = ? ? 2 ??1 ? (1 or 3) mod ?
? rand(2 ???
) 1 = rand 2 1 = 1 or 3
? 公開鍵(pubkey)を見てみると
? pubkey[1022](=? ??1) とpubkey[1023](=? ?)が手に入る
19

秘密鍵の取得
? rand 2 |1 = 1の場合、? = 2 ? ? ??1 ? ? ?として導出可能
? 2 ? ? ??1 ≡ ? ? mod ? ≡ ? ? + ?? (? ∈ ?)
? rand 2 |1 = 3の場合も同様に導出可能
20

秘密鍵の取得
? ? ≡ ? ? ? 2??
mod ?
? ? が導出できたので、2??
mod ? が導出可能
? 秘密鍵とメッセージの積も導出可能
? ?? = ?? ? ??1
mod ?
? ? ? ??1
mod p = ?=0
?
?? ? ???
? まだ平文は手に入らない
? トラップドアが分からないから
? 疲れちゃったから仕方ない
21
Step2：15分

トラップドア
? ?? = (rand(2 ???
) 1 ? 2?
? or 1 → 最下位ビットに1
? 2?
→ iビットシフト
? ?? ? ???
? ??? = 0の場合：影響を与えない
? ??? = 1の場合：?ビット目に1、? + 1ビット以上にランダム
ビット加算、?ビット未満には影響を与えない
22
?1 = 1111001011001
?2 = 1100110001110
?3 = 1011001100100
?4 = 1111110111000
??1 = 1
??2 = 0
??3 = 1
??4 = 1
?=1
4
?? ? ??? = 101010001110101

トラップドア
? 復号アルゴリズム
? 暗号文?の下位ビットから順にビットをチェック
? もし?ビット目が1ならば??? = 1と判断し、C = ? ? ??とする
? もし?ビット目が0ならば??? = 0と判断
? 次のビットへ移動
23
?=1
4
?? ? ??? = 101010001110101
?1 = 1111001011001 ??1 = 1
?=1
4
?? ? ??? ? ?1 = 11011000011100
??2 = 0
??3 = 1?=1
4
?? ? ??? ? ?1 = 11011000011100
??4 = 1
?=1
4
?? ? ??? ? ?1 ? ?3 = 1111110111000
?2 = 1100110001110
?3 = 1011001100100

トラップドア
? 導出できるのはDESで暗号化された平文
? 鍵はわかっているので復号するだけ
? KEY=‘testpass’
24
確認：10分

基底
? 基底：線形独立なベクトルから成る集合で、そのベクトル
の（有限個の）線型結合として、与えられたベクトル空間
の全てのベクトルを表すことができるもの（by wikipedia）
? もし2次元なら下記?1, ?2は基底となる
? ?1 ?1 + ?2 ?2 (? ∈ ?)で2次元のすべての空間を表せればよい
26
?2
?1
?1 =
1
0
?2 =
0
1
?2
?1
?1 =
1
1/2
?2 =
1
3

格子
? 格子：実ベクトル空間 Rn を生成するような Rn の離散部分
群をいう。すなわち、Rn の任意の格子は、ベクトル空間と
しての基底から、その整数係数線型結合の全体として得ら
れる。(by wikipedia)
? もし2次元なら下記L(B) は基底となる
? ? ? = ?1 ?1 + ?2 ?2 ? ∈ ?
? 係数が整数に限定
27
?2
?1
?2
?1

最短ベクトル問題
? 格子に存在する最も距離（=ユークリッドノルム）が短い非
零ベクトルを見つける問題
? NP困難：NP完全と同等以上に難しい
? 高次元の場合、 (?1, ?2, ? , ? ?)を求めることは計算量が非常に
大きい
28
?2
?1
?2
?1

LLLアルゴリズム
? Lenstra, Lenstra, Lovaszらにより1982年に提案
? グラムシュミットの直行化を利用
? ある格子?(?)と同じ格子を生成する異なる基底?′を導出す
るアルゴリズム
? 導出された基底?′はLLL簡約基底となる
? LLL簡約基底：距離が短い基底
? LLL簡約基底の第一ベクトルは、（近似）最短ベクトルとなる
? LLLアルゴリズムを格子に適用すると、確率的に（近似）最
短ベクトルが導出できる！
29

SageでLLLを使ってみる
? 行列型のオブジェクトがLLL()メソッドを持つ
? 強い
30

[Plaid CTF 2015] Crypto180
Lazy31

準備
? Plaid CTF 2015 Lazy
? https://github.com/ctfs/write-ups-2015/tree/master/plaidctf-
2015/crypto/lazy
32

鍵生成
? Markle-Hellmanナップサック暗号
? 秘密鍵： ?1, … , ? ? , ?, ?
? ?はsuperincreasing(超増加数列) であり ?=1
??1
? ? < ?? を満たす
? N, ?は互いに素
? 公開鍵： ?1, … , ? ?
? ?? = ? ? ?? mod ?
33

暗号化
? ナップサック暗号化
? ?=1
?
?? ? ?? = ?
34

復号
? ナップサック復号
? ? ? ??1
mod ? ≡ ?=1
?
?? ? ??
? 超増加数列の性質より、下記で??を導出可能
? ? S = ?=1
?
?? ? ??, ? = ? とする
? ① S ≥ ? ?であれば、? ? = 1とし、? = ? ? ? ?とする
? ② S < ? ?であれば、? ? = 0とする
? ③ ?をデクリメント
? ①～③を繰り返す
35

方針
? Markle-Hellmanナップサック暗号
? とくにひねりはない（よね？）
? いくつか攻撃手法が報告
? 低密度攻撃
? 密度：平文のビット数/暗号文の平均ビット数
? 平文空間と暗号文空間の大きさの違い
? 密度? = ?/ log2 max ??
? 密度が小さい場合、部分和問題を（近似）最短ベクトル問題
と結びつけナップサック暗号を解読可能
? LO法：? < 0.64のナップサック暗号を解読
? CLOS法：LO法で解読できる密度を? < 0.94まで改良
? Lazyの密度：0.90
? 低密度攻撃で解ける！
36

低密度攻撃の考え方
? 準備
? ?=1
?
?? ? ?? = ?は?次元空間におけるベクトルとみなせる
? 考え方
? ?=1
?
??
′
? ??が最短ベクトルとなる格子?(?′
)を準備
? ?′
= (?1
′
, … , ? ?
′
) ≠ (?1, … , ? ?)
? 格子?(?′
)の最短ベクトルを導出すれば平文が導出可能
? LLLアルゴリズム等で最短ベクトルを導出可能
37
Step1：15分
Step2：15分

都合の良い最短ベクトル
? 次のような基底?とベクトル?を考える
? ? = ?1 ?2 ? ? ??1 ? ? =
?1 ?2 ? ? ??1 ? ?
2 0 ? 0 0
0 2 ? 0 0
? ? ? ? ?
0 0 ? 2 0
0 0 ? 0 2
=
?
2? ?
? ? = ? 1 ? 1 1 ?
? ここでS = ?=1
?
?? ? ??より格子上のベクトル??と?の距離ベクトルは
下記で導出できる
? ?? ? ? =
?=1
?
?? ? ?? ? ?
2?1 ? 1
2?2 ? 1
?
2? ??1 ? 1
2? ? ? 1
38

都合の良い最短ベクトル
? ?? ? ?の距離は下記で導出できる
? ?? ? ? = ( ?=1
?
?? ? ?? ? S)2 + ?=1
?
2?? ? 1 2 = ?
? ??1
?
?? ? ?? ? ?=0
? 2?? ? 1 ∈ {?1,1}
? ?? ? ?の距離は??や?の大きさに左右されず、高々 ?におさまる
39

都合の良い格子
? 次のような基底?′を考える
? ?′
=
? ? ? ?? ? ?
2? ?1
=
? ? ?1 ? ? ?2 ? ? ? ? ? ?? ? ?
2 0 ? 0 ?1
0 2 ? 0 ?1
? ? ? ? ?
0 0 ? 0 ?1
0 0 ? 2 ?1
? ?は十分に大きな定数
? 一般にベクトルが大きくなることが期待できる
? 前頁より、この基底は1～?列の係数が??、? + 1列の係数が1の場合、
長さ ?のベクトル(= ?? ? ?)を持つ
? 他のベクトルが大きい場合、最短ベクトルとなることが期待できる
? ?(?′
)の最短ベクトルの係数が0,1, ?1のみであれば、そのベクトル
は?? ? ?である可能性が高い
40

部分和問題の解答
? 最短ベクトルが?? ? ?の条件を満たしているならば、
? ?? ? ? =
0
2?1 ? 1
2?2 ? 1
?
2? ??1 ? 1
2? ? ? 1
? 2番目～n+1番目の係数より下記手順で??が導出できる
? 係数が1の場合
? 2?? ? 1 = 1よって?? = 1
? 係数が?1の場合
? 2?? ? 1 = ?1 よって?? = 0
41
Step2：15分

こたえ
? 基底?′を生成
? LLLアルゴリズムを適用
? SageのLLLの仕様上、転置（transpose）
42

こたえ
? ?? ? ?の条件を満たすベクトルを探索
? ??を導出
43
確認：10分

[TW CTF 2nd 2016] Crypto450
Backpacker’s cipher extra mode44

準備
? TWCTF 2nd 2016 Backpacker's cipher - extra mode
? https://github.com/TokyoWesterns/twctf-2016-
problems/tree/master/Backpacker's%20cipher%20-%20extra%20mode
45

鍵生成
? ナップサック暗号っぽい
? 秘密鍵：(s1, … , ? ?), ?, ?
? ??はランダムな整数
? ?は ?=1
?
? ? < ? を満たす素数
? ?は
?
2
< ? < ?を満たす整数
? 公開鍵： ?1, … , ? ? , ?1, … , ? ? , ? = 2128
, ? = 300
? ?? = ? ? ?? ??? ?
? ?? = ?? ??? ?
46

暗号化
? ナップサック暗号でAESの鍵(???)を生成
? ?1, … , ? ? ? ∈ 0,1
? ??? = ?=1
?
?? ? ?? mod ?
? ??はランダムな値
? ナップサック暗号でAESの初期化ベクトル(???_???)を生成
? ???_??? = ?=1
?
?? ? ??
? AESでflag(???????)を暗号化
? ???_??????? = AES_enc ???, ???_???, ???????
? 初期化ベクトル, 暗号文を公開
? 暗号化に使った鍵(???)は公開しない
47

復号
? ???_???から???を導出し、AESを復号
? ???_??? ? ??1
mod ? mod ? ≡ ?=1
?
?? mod ? ≡ ???
? ??????? = AES_dec(???, ???_???, ???_???????)
48

ナップサック鍵共有
? ナップサック鍵共有
? 暗号化に利用する鍵(???, ???_???)＝ナップサック暗号で生成
? 暗号化自体はAESで実施
? AESの復号には???が必要
? ???_???は公開されているが???は秘密
? ???の導出には?, ?が必要
? ??1
? ???_??? = ???を導出するため
49

低密度攻撃（LLLアルゴリズム
を用いた解法）の注意
? ???_???は?をナップサック暗号化した暗号文
? ???_??? = ?=1
?
?? ? ??
? ???_???にLLLアルゴリズムを適用して??を求めればよい？
? 低密度攻撃を実施する際の注意
? LLLアルゴリズムを利用する攻撃＝低密度攻撃
? 密度が0.94よりも大きい場合、??を導出できない
? ? = ?/ log2 max ??
? 本問題の密度：1.21
50

密度が１を超えるとは？
? 密度が1よりも小さい場合、平文空間＜暗号文空間
? 一つの暗号文を生成する平文は一つ（の可能性が高い）
? 平文空間から暗号文空間への写像は単射（の可能性が高い）
? 密度が１よりも大きい場合、平文空間＞暗号文空間
? 一つの暗号文を生成する平文が多数存在（の可能性が高い）
? 平文空間から暗号文空間への写像は全射（の可能性が高い）
? 本問題は???_??? = ?=1
?
?? ? ??を構成する??が複数存在する
（可能性が高い）
51

方針
? 密度が1を超える場合、複数の平文が同じ暗号文を生成
? この状況で???_??? に対して、前問と同様にLLLアルゴリズ
ムを利用すると？
? ???_??? = ?=1
?
?? ? ??′を生成する??
′
を導出可能
? ?? ≠ ??
′
∈ ? (not only 0 or 1)
? 本問題では??′ ≠ ??であっても??? = ?=1
?
?? ? ??′ mod ?を導
出可能
? ?=1
?
?? ? ??′ mod ? ≡ ( ?=1
?
??1
? ?? ? ??
′
mod ?) mod ?
≡ ???_??? ? ??1
mod ? mod ? ≡ ?=1
?
?? mod ? ≡ ???
52
Step1：15分
Step2：15分

都合のよい格子
? 次のような基底?′を考える
? ?′
=
1 0 ? 0 0
0 1 ? 0 0
? ? ? ? ?
0 0 ? 1 0
? ? ?1 ? ? ?2 ? ? ? ? ? ?? ? ?
0 0 ? 0 1
? ?は十分に大きな定数
? Lazyの基底でも導出できるが、より簡単に導出するため
? この基底は1～?列の係数が??′、? + 1列の係数が1の場合、下記
ベクトル?を持つ
? ? =
?1′
?2′
?3′
?
??1
?
?? ? ?? ? ? =0
1
? 他のベクトルが大きい場合、最短ベクトルとなることが期待できる
? ?(?′
)の最短ベクトルのn + 1番目の係数が0, ? +
2番目の係数が1であれば、ベクトルは?である可能性が高い
? ??
′
を構成する値は0,1だけではないことに注意
53

こたえ
? 基底?′を生成
? LLLアルゴリズムを適用
? SageのLLLの仕様上、転置（transpose）
54

こたえ
? ?の条件を満たすベクトルを探索
? ???を導出し、AESを復号
55
確認：10分

まとめ
? ナップサック暗号の基本について学習した
? 低密度攻撃について学習した
? 高密度攻撃？について学習した
56
今日から君もナップサック暗号マスターだ！

参考文献
? Ralph Merkle, Martin Hellman, "Hiding Information and Signatures in Trapdoor Knapsacks", IEEE
Trans. Information Theory, 24(5), September 1978, pp.525–530.
? J. C. Lagarias and A. M. Odlyzko, “Solving Low Density Subset Sum Problems,” J. Assoc.
Comp.Math., vol.32, pp.229–246, Preliminary version in Proc. 24th IEEE, 1985
? M. J. Coster, B. A. LaMacchia, A. M. Odlyzko and C. P. Schnorr, “An Improved Low-Density Subset
Sum Algorithm,” In Advances in Cryptology Proc. EUROCRYPTO'91,LNCS, pp.54–67.Springer-Verlag,
Berlin, 1991.
? D.ミッチアンチオ, S. ゴールドヴァッサー, “暗号理論のための格子の数学” シュプリン
ガー?ジャパン, 2006.
? https://github.com/everping/ctfs/blob/master/2015/4/plaidctf/crypto/lazy/solve.py
? http://www.gnoobz.com/plaid-ctf-2015-lazy-writeup.html
? https://gist.github.com/Bono-iPad/2731d096a3756d582d9c0310fb145543
? http://bono-ipad.github.io/burningctf2015_writeup.html
57

狠狠撸

katagaitai workshop #7 crypto ナップサック暗号と低密度攻撃

More Related Content

katagaitai workshop #7 crypto ナップサック暗号と低密度攻撃