katagaitai CTF 勉強会 #5 -関東 |med おまけ問題 Parlor (Plaid CTF 2014) @m1z0r3勉強会
?
1 like?1,892 views
2016/7/27 m1z0r3勉強会（暗号班）で発表した資料です。
katagaitai CTF 勉強会 #5 -関東 |med おまけ問題 Parlor (Plaid CTF 2014) @m1z0r3勉強会
- 1. Parlor m1z0r3 (crypto) meeting sonickun 2016/7/27 m1z0r3 meeting 1
- 2. はじめに ? Katagaitai CTF 勉強会 行ってきました ? https://atnd.org/events/77451 ? m1z0r3からの参加者は7人くらい ? 復習大事 ? 今日はParlaor解きます ? 勉強会参加した人なら解ける(た)よなあ？ ? 初心者にはLength-extensionの簡単な問題を出します 2016/7/27 m1z0r3 meeting 2
- 3. Problem ? Plaid CTF 2014 – Parlor (Crypto 250) ? katagaitai CTF勉強会 #5 - 関東|med おまけ問題 ? Task 2016/7/27 m1z0r3 meeting 3 The Plague is running a betting service to build up funds for his massive empire. Can you figure out a way to beat the house? The service is running at katagaitai.orz.hm:4321
- 5. 概要 ? Flag入手条件 ? お金を$1,000→$1,000,000,000に増やす ? 以下の式を満たすとbet額×oddsが手に入る（外せばbet没収） ? できること ? odds(2^n)とbet額のセット ? client_numberを設定してプレイ ? 所持金額の確認 ? secretの確認（確認するとsecretはリセットされる） 2016/7/27 m1z0r3 meeting 5 md5(secret + client_number) % odds = 0 ※ secretは未知
- 6. 問題の整理 ? この問題の難しいところ ? secretが未知なのでMD5ハッシュの値が分からない（操作 できない） ? 勝利の必須条件 ? 自分の思い通り（後述）のMD5ハッシュを計算する （ハッシュ値に合わせてoddsを調節してやればいい） 2016/7/27 m1z0r3 meeting 6 md5(secret + client_number) % odds = 0 方針 secretが分からなくてもハッシュ値を 計算できる方法を使う
- 7. Length-extension Attack ? 詳しくはkatagaitai勉強会のtrmrさんの資料を参照 ? Length-extension Attack ツール ? hashpump: https://github.com/bwall/HashPump ? hash_extender: https://github.com/iagox86/hash_extender 2016/7/27 m1z0r3 meeting 7 y = Hash(secret + x) のxとyが既知である時、secretが 逆算できなくも Hash(secret + x + y) が計算できる
- 8. 方針（1/3） “仮に”MD5ハッシュ値が分かっている場合… ↑このハッシュ値が作れる（”y”部分を変えていくらでも） ?下位ビットが0になるハッシュ値が作れた時、oddsを調整してPlay! ex.) MD5の下位ビットが10…100の時、odds=2^2とすればWin 2016/7/27 m1z0r3 meeting 8 md5(secret + “x”) % odds = 0 md5(secret + “x”+ pad + “y”) % odds = 0 Extend! client_nuber = “x” としたとき
- 9. 方針（2/3） 課題：MD5ハッシュ値をどうやって求めるか 実は MD5 % odds の値を教えてくれる oddsの最大値は2^100なのでMD5の下位100/128bitがわかる！ 2016/7/27 m1z0r3 meeting 9 md5(secret + “x”) % odds = 0 残りの28bit は…？？
- 10. 方針（3/3） 課題：MD5の残りの28bitをどうやって求めるか（ここが最難関） ?Length-extensionを駆使して28bitをブルートフォースする 2016/7/27 m1z0r3 meeting 10 100bit28bit md5(secret + “x”+ pad + “y”) client_number = “x” client_number = “x” + pad + “y” md5(secret + “x”) 100bit28bit サーバーから 二つのハッシュの 下位ビットを得る 求めたいやつ このページがんばった
- 11. 方針（3/3） 課題：MD5の残りの28bitをどうやって求めるか（ここが最難関） ?Length-extensionを駆使して28bitをブルートフォースする 2016/7/27 m1z0r3 meeting 11 100bit28bit ！ md5(secret + “x”+ pad + “y”) 100bit00..01 100bit00..02 100bitXX..XX … client_number = “x” Length- extension client_number = “x” + pad + “y” md5(secret + “x”) Brute Force 100bit00..03 100bit28bit 100bit28bit 100bit28bit 100bit28bit 100bit28bit … 下位 100bitが 一致 サーバーから 二つのハッシュの 下位ビットを得る 求めたいやつ ↓ローカルの仕事（高速化必須） このページがんばった md5(secret+“x”)のLength-extensionの結果の下位100bitがmd5(secret+“x”+pad+“y”) の下位100bitと一致するようにmd5(secret+“x”)の上位28bitを総当たりする
- 12. ? 自分で思い通りのハッシュ値を作りたいぞ ? Length-extension Attackでハッシュを量産するぞ ? 元のハッシュ値を知る必要があるぞ ? 下位100bitなら分かるぞ ? 残りの28bitは総当たりするぞ 2016/7/27 m1z0r3 meeting 12 攻撃の流れ 思考の流れ
- 13. 攻撃手順まとめ 1. HASH1=md5(secret + “x”) の下位100bitを求める 2. HASH2=md5(secret + “x” + pad + “y”) の下位100bitを求める 3. HASH1のLength-extensionの結果の下位100bitがHASH2の下位 100bitと一致するようにHASH1の上位28bitを総当たりする 4. HASH1のすべてのbitが求まる 5. HASH1に任意の文字でLength-extensionを施し、下位ビットが 0になるようにする 6. 下位ビットの0の数に応じてoddsを設定しplayする（勝率100%） 7. 所持金が$1,000,000,000になるまで5と6を繰り返す 8. Flagゲット 2016/7/27 m1z0r3 meeting 13
- 14. Solver ? https://gist.github.com/sonickun/01515eaa48b4d983 1e42df40164f7720 2016/7/27 m1z0r3 meeting 14
- 15. 2016/7/27 m1z0r3 meeting 15