Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
SECCON Beginners CTF2021のCryptoを解いてみよう
Search
ushigai
October 17, 2021
Technology
0
1.1k
SECCON Beginners CTF2021のCryptoを解いてみよう
ushigai
October 17, 2021
Tweet
Share
More Decks by ushigai
See All by ushigai
暗号目線で俯瞰するSSL/TLS / security minicamp in Tokyo 2022 TLS
ushigai
0
610
Crypto超入門 / SECCON Beginners Live 2022
ushigai
2
1.8k
Other Decks in Technology
See All in Technology
LinkX_GitHubを基点にした_AI時代のプロジェクトマネジメント.pdf
iotcomjpadmin
0
160
(非公式) AWS Summit Japan と 海浜幕張 の歩き方 2025年版
coosuke
PRO
1
340
Amazon Bedrockで実現する 新たな学習体験
kzkmaeda
1
410
初めてのAzure FunctionsをClaude Codeで作ってみた / My first Azure Functions using Claude Code
hideakiaoyagi
1
190
25分で解説する「最小権限の原則」を実現するための AWS「ポリシー」大全
opelab
9
2.2k
UIテスト自動化サポート- Testbed for XCUIAutomation practice
notoroid
0
110
CI/CDとタスク共有で加速するVibe Coding
tnbe21
0
230
フィンテック養成勉強会#54
finengine
0
120
_第3回__AIxIoTビジネス共創ラボ紹介資料_20250617.pdf
iotcomjpadmin
0
150
20250623 Findy Lunch LT Brown
3150
0
790
標準技術と独自システムで作る「つらくない」SaaS アカウント管理 / Effortless SaaS Account Management with Standard Technologies & Custom Systems
yuyatakeyama
2
1k
変化する開発、進化する体系時代に適応するソフトウェアエンジニアの知識と考え方(JaSST'25 Kansai)
mizunori
0
140
Featured
See All Featured
Building Adaptive Systems
keathley
43
2.6k
Large-scale JavaScript Application Architecture
addyosmani
512
110k
Dealing with People You Can't Stand - Big Design 2015
cassininazir
367
26k
Fireside Chat
paigeccino
37
3.5k
Product Roadmaps are Hard
iamctodd
PRO
53
11k
The Cult of Friendly URLs
andyhume
79
6.4k
Navigating Team Friction
lara
187
15k
Building Flexible Design Systems
yeseniaperezcruz
328
39k
Art, The Web, and Tiny UX
lynnandtonic
299
21k
Sharpening the Axe: The Primacy of Toolmaking
bcantrill
44
2.4k
Six Lessons from altMBA
skipperchong
28
3.8k
How to Ace a Technical Interview
jacobian
277
23k
Transcript
SECCON Beginners CTF 2021の Cryptoを解いてみよう SECCON Beginners Live 2021 2021/10/17
自己紹介 • うしがぃ@ushigai_sub • 所属 • 都立産業技術高等専門学校(4年) • SECCON Beginners
運営チーム • 趣味 • ピアノ:小6から7年間 • ルービックキューブ3×3:1/5/100=13.89/18.88/23.19 • 将棋:アマ二段 1/24
内容 • simple_RSA解説 • Logical_SEESAW解説 • 発展問題の紹介 2/24
お話の対象層 3/25 Beginner Easy Medium Hard • 過去問解説はBeginner向け • 発展問題はEasy向け
CTF Beginnerへ 4/24 • 昨今のCTFは難しすぎる… • プログラミングはできて当たり前 • 文字コードいじるだけ問題はどこへ? Merkle-Dam
Mersenne T CopperS bcrypto
CTF Beginnerへ • 勉強方法(主観) • 本・常設での勉強 • 迷路本 • picoCTF
• 分からないことがあったら? • 誰かに聞く • おいしいものを食べる 5/24
simple_RSA解説 •simple_RSA • 難易度Beginner • 75points/289solves •RSA暗号の自明な脆弱性を攻撃する問題 → Low public
exponent attack 6/24
RSA暗号 鍵生成: 素数𝑝, 𝑞について𝑛 = 𝑝𝑞, φ 𝑛 = (𝑝
− 1)(𝑞 − 1)とおき、 𝑔𝑐𝑑 φ 𝑛 , 𝑒 = 1を満たす𝑒から𝑑 = 𝑒−1 mod φ(𝑛)とおく。 このとき公開鍵の組を 𝑒, 𝑛 , 秘密鍵を𝑑とする。 暗号化: 任意の平文𝑚について暗号文𝑐は𝑐 = 𝑚𝑒 mod 𝑛となる。 復号: 平文𝑚は𝑚 = 𝑐𝑑 mod 𝑛と複号できる。 7/24
CTFにおけるRSA暗号 • Beginner • 暗号化・復号の計算方法 • factorDB等ツールの使用 • RSA暗号の典型的な脆弱性の攻撃 •
Easy ~ Medium • 簡単な代数方程式の計算 • 鍵共有・署名 • Hard ~ • CopperSmiths Method • 数学力でぶん殴る • etc… 8/24
problem.pyについて① 𝑛 = 𝑝𝑞 𝑒 = 3 𝑐 = 𝑓𝑙𝑎𝑔𝑒
mod 𝑛 9/24
problem.pyについて② • assert 2046 < n.bit_length() → nは2047bit or nは2048bit
• assert 375 == flag.bit_length() → flagは375bitの数 ⇒ 𝑐 = 𝑓𝑙𝑎𝑔𝑒 ∵ 𝑓𝑙𝑎𝑔𝑒 < 𝑛 ⇒ Low public exponent attack 10/24 ⇒ 𝑓𝑙𝑎𝑔 = 𝑒 𝑐
solverの作成 11/24
Logical_SEESAW解説 • Logical_SEESAW • 難易度Beginner • 118points/190solves • パズル問(自作暗号) •
論理演算・コーディング 12/24
problem.pyについて① 13/24
problem.pyについて② flagの各bitに対して適用確立0.5で flagとkeyのAND演算を行っている 14/24
暗号化部分のAND演算 flag key n > m cipher 0 0 0
0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 1 cipherが1ならflagは確実に1で 0なら8割がた0になる! 15/24
攻撃 • cipherが1ならflagは確実に1 • cipherが0ならflagは8割方0 ⇒ 各bitに対して1個でも1が含まれていれば1で 全部0なら0 ⇒ OR演算で実装・復号できる
16/24
solverの作成 17 /24
復号でノイズが乗る確率は? • 簡単のために入力値は1で固定 • あるiでcipher[0, 16)[i]がすべて0のとき正しく復号できない • 1回でノイズが乗る確率は1/4 ⇒ 1
4 16 ≒ 2.32 × 10−10 18/24 flag key n > m cipher 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 1 23200000000回に1回しか ノイズのらないんじゃね?
復号でノイズが乗る確率は? • 現実には確率の罠が存在する • 2.32 × 1010回1を入力したとき1回でもノイズが乗る確率 • 確率が1/2を超える入力回数は? 2977044472回
⇒ 2.32 × 1010回と大きな差がある 19/24 1 − 1 − 1 4 16 23200000000 × 100% ≒ 99.5%
誕生日のパラドクス 20/24 クラス40人で同じ誕生日の人が2人以上いる確率はいくつか? 1 − 364 365 ∙ 363 365
∙ ⋯ ∙ 326 365 × 100% ≒ 89.23% 確率が1/2を超えるために必要な人数は何人か? ⇒ 23人
誕生日攻撃 • ハッシュ関数の衝突を見つける攻撃 • 無作為な入力を行いハッシュ値と一致させる 21/24 出力bit 出力の個数 衝突確立 1%
衝突確立 50% 衝突確立 75% 32 4.3 × 109 2.9 × 103回 7.7 × 104回 1.1 × 105回 64 1.8 × 1019 6.1 × 108回 5.1 × 109回 7.2 × 109回 128 3.4 × 1038 2.6 × 1018回 2.2 × 1019回 3.1 × 1019回
発展問題の紹介 22/24
さいごに 23/24 • CTFはとても楽しいです • ぜひ一緒に楽しみましょう
お世話になったところ • イラスト https://www.irasutoya.com/ • 誕生日攻撃の出力bitと衝突確立の関係 https://ja.wikipedia.org/wiki/%E8%AA%95%E7%94%9F%E6%97 %A5%E6%94%BB%E6%92%83 • SECCON
Beginners CTF 2021(GitHub) https://github.com/SECCON/Beginners_CTF_2021 24/24