1bit欠損メルセンヌ・ツイスタの予測 (魔女のお茶会 2021/冬)

kurenaif さん主催のCTF勉強会、魔女のお茶会 2021/冬にて発表させていただいた際のスライドです。

Transcript

1. 1bit欠損メルセンヌ・ツイスタの 予測 artoy
2. Who am I? • 名前： artoy (twitter: @artoy5884) • 専門： プログラム検証 • CTF歴： 1週間
3. Outline • メルセンヌ・ツイスタとは • メルセンヌ・ツイスタの予測 • 1bit欠損メルセンヌ・ツイスタの予測
4. Outline • メルセンヌ・ツイスタとは • メルセンヌ・ツイスタの予測 • 1bit欠損メルセンヌ・ツイスタの予測
5. メルセンヌ・ツイスタとは 擬似乱数生成アルゴリズムの一種 • 周期が長い • 高次元均等分布 • 生成が速い • メモリ効率がいい → 様々な言語の標準ライブラリで用いられている
9. 乱数生成方法 1. 内部状態の初期化 2. 内部状態の更新 3. 乱数の生成 * 3で624個乱数を生成したら2に戻る 𝑆! 𝑆" ・・・ 𝑆#$% シード値 𝑆#$& 𝑆#$' 𝑆!"#$ ・・・ 𝑟! 𝑟" 𝑟#$% 1 2 3 ・・・ *
10. 内部状態の更新 • twist ： 𝑆" , 𝑆"#$, , 𝑆"#&'( から 𝑆"#)*+ を求める操作 twist によって新しく624個の値を求めてそれらを新しい内部状態とする 𝑆! 𝑆" 𝑆$ ・・・ 𝑆%() ・・・ 𝑆#$% 𝑆%(* 内部状態
11. 内部状態の更新 • twist ： 𝑆" , 𝑆"#$, , 𝑆"#&'( から 𝑆"#)*+ を求める操作 twist によって新しく624個の値を求めてそれらを新しい内部状態とする 𝑆! 𝑆" 𝑆$ ・・・ 𝑆%() ・・・ 𝑆#$% 𝑆%(* twist 𝑆#$&
12. 内部状態の更新 • twist ： 𝑆" , 𝑆"#$, , 𝑆"#&'( から 𝑆"#)*+ を求める操作 twist によって新しく624個の値を求めてそれらを新しい内部状態とする 𝑆! 𝑆" 𝑆$ ・・・ 𝑆%() ・・・ 𝑆#$% 𝑆%(* twist 𝑆#$& 𝑆#$'
13. 内部状態の更新 • twist ： 𝑆" , 𝑆"#$, , 𝑆"#&'( から 𝑆"#)*+ を求める操作 twist によって新しく624個の値を求めてそれらを新しい内部状態とする 𝑆! 𝑆" 𝑆$ ・・・ 𝑆%() ・・・ 𝑆#$% 𝑆%(* 𝑆#$& 𝑆#$' ・・・ 𝑆!"#$ 新しい内部状態
14. twist • 𝑆"#$ の最下位ビットが0の時 𝑆"#)*+ = 𝑆"#&'( ⊕ 𝑆" & 0x80000000 | 𝑆"#$ & 0x7ffffffff ≫ 1 • 𝑆"#$ の最下位ビットが1の時 𝑆"#)*+ = 𝑆"#&'( ⊕ 𝑆" & 0x80000000 | 𝑆"#$ & 0x7ffffffff ≫ 1 ⊕ 0x9908b0df
15. twist • 𝑆"#$ の最下位ビットが0の時 𝑆"#)*+ = 𝑆"#&'( ⊕ 𝑆" & 0x80000000 | 𝑆"#$ & 0x7ffffffff ≫ 1 • 𝑆"#$ の最下位ビットが1の時 𝑆"#)*+ = 𝑆"#&'( ⊕ 𝑆" & 0x80000000 | 𝑆"#$ & 0x7ffffffff ≫ 1 ⊕ 0x9908b0df 𝑆& の最上位ビットのみを取っている
16. twist • 𝑆"#$ の最下位ビットが0の時 𝑆"#)*+ = 𝑆"#&'( ⊕ 𝑆" & 0x80000000 | 𝑆"#$ & 0x7ffffffff ≫ 1 • 𝑆"#$ の最下位ビットが1の時 𝑆"#)*+ = 𝑆"#&'( ⊕ 𝑆" & 0x80000000 | 𝑆"#$ & 0x7ffffffff ≫ 1 ⊕ 0x9908b0df 𝑆&'" の最上位ビット以外を取っている
17. twist • 𝑆"#$ の最下位ビットが0の時 𝑆"#)*+ = 𝑆"#&'( ⊕ 𝑆" & 0x80000000 | 𝑆"#$ & 0x7ffffffff ≫ 1 • 𝑆"#$ の最下位ビットが1の時 𝑆"#)*+ = 𝑆"#&'( ⊕ 𝑆" & 0x80000000 | 𝑆"#$ & 0x7ffffffff ≫ 1 ⊕ 0x9908b0df 異なるのはここだけ
18. twist 𝑆+ 𝑆+," ＝ ＝ 最上位ビット 最上位ビット 最下位ビット 30ビット 31ビット
19. twist 𝑆+ 𝑆+," 𝑆!"#$% ＝ ＝ ⊕ (⊕ 0x9908b0df) 𝑆!"&'( = = 1 のとき = 0
20. 乱数の生成 内部状態のそれぞれの値に temper を施して得られた値を乱数として出力する 𝑆#$& 𝑆#$' 𝑆!"#$ ・・・ 𝑟! 𝑟" 𝑟#$% temper ・・・
21. temper temper を疑似コードで表すと以下のようになっている temper 𝑥 : 𝑥 ← 𝑥 ⊕ 𝑥 ≫ 11 𝑥 ← 𝑥 ⊕ 𝑥 ≪ 7 & 0x9d2c5680 𝑥 ← 𝑥 ⊕ 𝑥 ≪ 15 & 0xefc6000 𝑥 ← 𝑥 ⊕ 𝑥 ≫ 18 return 𝑥
22. Outline • メルセンヌ・ツイスタとは • メルセンヌ・ツイスタの予測 • 1bit欠損メルセンヌ・ツイスタの予測
23. メルセンヌ・ツイスタの予測 以下のどちらかが分かれば後続の乱数を全て予測することができる • シード値 • ある時点においての内部状態
24. メルセンヌ・ツイスタの予測 以下のどちらかが分かれば後続の乱数を全て予測することができる • シード値 • ある時点においての内部状態 → 本当は連続する624個の値であれば内部状態を跨いでもいい 例 ： 𝑆"!, 𝑆"", … , 𝑆#%%
25. メルセンヌ・ツイスタの予測 以下のどちらかが分かれば後続の乱数を全て予測することができる • シード値 • ある時点においての内部状態 → 本当は連続する624個の値であれば内部状態を跨いでもいい 例 ： 𝑆"!, 𝑆"", … , 𝑆#%% もし temper の逆操作(untemper)が可能なら、624個の連続する乱数を観測 すれば二つ目の条件を満たせるのでは？
26. untemper temper は 𝑥 と 𝑥 をシフトさせたものの XOR という操作で構成されている → 𝑥 のままの部分を利用してその操作の逆操作ができる 例 ： 𝑥 ⊕ 𝑥 ≫ 11 𝑥 = 上位ビット 下位ビット
27. untemper temper は 𝑥 と 𝑥 をシフトさせたものの XOR という操作で構成されている → 𝑥 のままの部分を利用してその操作の逆操作ができる 例 ： 𝑥 ⊕ 𝑥 ≫ 11 ⊕ ) 11ビット → 𝑥 のまま 𝑥 = 𝑥 ⊕ 𝑥 ≫ 11 =
28. untemper 例 ： 𝑦 = 𝑥 ⊕ 𝑥 ≫ 11 目標 ： 𝑦 から 𝑥 を求める 𝑥 = 11ビット （既知） 11ビット 10ビット
29. untemper 例 ： 𝑦 = 𝑥 ⊕ 𝑥 ≫ 11 目標 ： 𝑦 から 𝑥 を求める ⊕ ) 𝑦 = 𝑥 = 11ビット
30. untemper 例 ： 𝑦 = 𝑥 ⊕ 𝑥 ≫ 11 目標 ： 𝑦 から 𝑥 を求める ⊕ ) 𝑦 ⊕ (𝑦 ≫ 11) = 𝑥 = 11ビット = 𝑦 = 𝑦 ≫ 11
31. untemper 例 ： 𝑦 = 𝑥 ⊕ 𝑥 ≫ 11 目標 ： 𝑦 から 𝑥 を求める ⊕ ) 𝑦 ⊕ (𝑦 ≫ 11) = 𝑥 = 打ち消せる！
32. untemper 例 ： 𝑦 = 𝑥 ⊕ 𝑥 ≫ 11 目標 ： 𝑦 から 𝑥 を求める ⊕ ) 𝑦 ⊕ (𝑦 ≫ 11) = 𝑥 = 11ビット11ビット 緑の部分が分かった！
33. untemper 例 ： 𝑦 = 𝑥 ⊕ 𝑥 ≫ 11 目標 ： 𝑦 から 𝑥 を求める ⊕ ) 𝑦 ⊕ (𝑦 ≫ 11) = 𝑥 = 11ビット11ビット = 𝑧 緑の部分が分かった！
34. untemper 例 ： 𝑦 = 𝑥 ⊕ 𝑥 ≫ 11 目標 ： 𝑦, 𝑧 から 𝑥 を求める ⊕ ) 𝑦 ⊕ (𝑧 ≫ 11) = 𝑥 = 11ビット = 𝑦 = 𝑧 ≫ 11
35. untemper 例 ： 𝑦 = 𝑥 ⊕ 𝑥 ≫ 11 目標 ： 𝑦, 𝑧 から 𝑥 を求める ⊕ ) 𝑦 ⊕ (𝑧 ≫ 11) = 𝑥 = 11ビット 打ち消せる！
36. untemper 例 ： 𝑦 = 𝑥 ⊕ 𝑥 ≫ 11 目標 ： 𝑦, 𝑧 から 𝑥 を求める 𝑦 ⊕ (𝑧 ≫ 11) = 𝑥 = 𝑥 に戻せた！
37. untemper この操作を疑似コードで表すと以下のようになる untemper_right_shift (𝑦, shift): 𝑧 = 𝑦 known_bits = shift while (𝑖 < 32) begin 𝑧 ← 𝑦 ⊕ 𝑧 ≫ shift known_bits ← known_bits + shift end return 𝑧
38. 再掲 ： temper temper を疑似コードで表すと以下のようになっている temper 𝑥 : 𝑥 ← 𝑥 ⊕ 𝑥 ≫ 11 𝑥 ← 𝑥 ⊕ 𝑥 ≪ 7 & 0x9d2c5680 𝑥 ← 𝑥 ⊕ 𝑥 ≪ 15 & 0xefc6000 ビットが and されている場合は？ 𝑥 ← 𝑥 ⊕ 𝑥 ≫ 18 → ほぼ同様の方法で戻せる return 𝑥
39. untemper 例 ： 𝑦 = 𝑥 ⊕ 𝑥 ≪ 7 & 0x9d2c5680 目標 ： 𝑦 から 𝑥 を求める 𝑥 = 7ビット 7ビット 7ビット 7ビット 4ビット ⊕ ) 𝑦 = 7ビット & 0x9d2c5680
40. untemper 例 ： 𝑦 = 𝑥 ⊕ 𝑥 ≪ 7 & 0x9d2c5680 目標 ： 𝑦 から 𝑥 を求める ⊕ ) 𝑦 ⊕ 𝑦 ≪ 7 & 0x9d2c5680 = 𝑥 = & 0x9d2c5680 & 0x9d2c5680 & 0x9d2c5680 & 0x9d2c5680 = 𝑦 = 𝑦 ≪ 7 & 0x9d2c5680
41. untemper 例 ： 𝑦 = 𝑥 ⊕ 𝑥 ≪ 7 & 0x9d2c5680 目標 ： 𝑦 から 𝑥 を求める ⊕ ) 𝑦 ⊕ 𝑦 ≪ 7 & 0x9d2c5680 = 𝑥 = & 0x9d2c5680 & 0x9d2c5680 & 0x9d2c5680 & 0x9d2c5680 打ち消せる！
42. untemper 例 ： 𝑦 = 𝑥 ⊕ 𝑥 ≪ 7 & 0x9d2c5680 目標 ： 𝑦 から 𝑥 を求める ⊕ ) 𝑦 ⊕ 𝑦 ≪ 7 & 0x9d2c5680 = 𝑥 = & 0x9d2c5680 水色の部分が分かった！ → 後はこれの繰り返し
43. untemper この操作を疑似コードで表すと以下のようになる untemper_left_shift (𝑦, shift, mask): 𝑧 = 𝑦 known_bits = shift while (𝑖 < 32) begin 𝑧 ← 𝑦 ⊕ 𝑧 ≪ shift & mask known_bits ← known_bits + shift end return 𝑧
44. untemper untemper を疑似コードで表すと以下のようになる untemper 𝑥 : 𝑥 ← untemper_right_shift (𝑥, 18) 𝑥 ← untemper_left_shift (𝑥, 15, 0xefc60000) 𝑥 ← untemper_left_shift (𝑥, 7, 0x9d2c5680) 𝑥 ← untemper_right_shift (𝑥, 11) return 𝑥
45. メルセンヌ・ツイスタの予測 • 目標 ： 内部状態の復元 • 条件 ： 連続する624個の乱数が分かっている 𝑆#$& 𝑆#$' 𝑆!"#$ ・・・ 𝑟! 𝑟" 𝑟#$% untemper 内部状態 ・・・
46. どんな言語でも予測できるのか？ • Python の random.getrandbits(32) はこの方法を使って予測することがで きる • 他の言語の標準ライブラリで実装されているメルセンヌ・ツイスタも同じ方法で 予測できるの？
47. どんな言語でも予測できるのか？ • Python の random.getrandbits(32) はこの方法を使って予測することがで きる • 他の言語の標準ライブラリで実装されているメルセンヌ・ツイスタも同じ方法で 予測できるの？ → No!!!
48. PHP : mt_rand() PHP の mt_rand()では 乱数を生成した後に1 ビット右シフトして出力し ている 範囲を指定した場合も… https://github.com/php/php-src/blob/master/ext/standard/mt_rand.c
49. PHP : mt_rand() 右に1ビットシフトしてから 返している! https://github.com/php/php-src/blob/master/ext/standard/mt_rand.c
50. PHP : mt_rand() 観測した624個の乱数の落ちた最下位ビットが全て当たったときのみ先述の方法 で内部状態を復元できる → 最大 2624 回試さなくてはならない！ シード値をブルートフォースした方が早い…
51. Outline • メルセンヌ・ツイスタとは • メルセンヌ・ツイスタの予測 • 1bit欠損メルセンヌ・ツイスタの予測
52. 1bit欠損メルセンヌ・ツイスタの予測 mt_rand() が生成する乱数を予測する方法はある • AMBIONICS SECURITY “BREAKING PHP'S MT_RAND() WITH 2 VALUES AND NO BRUTEFORCE” https://www.ambionics.io/blog/php-mt-rand-prediction • kurenaif “kurenaif Valentine Problems/three_values_twister” https://github.com/kurenaif/kurenaif_valentine_problems/tree/ main/three_values_twister
53. 1bit欠損メルセンヌ・ツイスタの予測 これらの方法は、観測する乱数の個数は少なくてよいが、比較的早く生成された ものでなければならないという制限が付いている 例 ： 𝑟$:::: から 𝑟*:::: までの乱数が分かってる → たくさん分かってても生成されたのが遅すぎて予測できない
54. 1bit欠損メルセンヌ・ツイスタの予測 • 乱数の生成された早さに依存しない予測方法はないのか？ • 最初の方法は乱数の生成された早さに依存しないが、条件を緩めれば同じよう な方法で内部状態を復元できないか？ • 624個の乱数の最下位ビットを全て当てるまで試すのではなく、1つずつ確定 させることはできないのか？
55. 1bit欠損メルセンヌ・ツイスタの予測 • twist ： 𝑆" , 𝑆"#$, , 𝑆"#&'( から 𝑆"#)*+ を求める操作 𝑟"#)*+ が正しい時、𝑟", 𝑟"#$, 𝑟"#&'( の落ちた最下位ビットのうち一つくらいは 正しいのではないか？ 𝑆+ 𝑆+," 𝑆!"#$% 𝑆!"&'( twist 𝑟& ≪ 1 | 0, 𝑟& ≪ 1 | 1 untemper 𝑟&'" ≪ 1 | 0, 𝑟&'" ≪ 1 | 1 𝑟&'#$( 𝑟&'%)* ≪ 1 | 0, 𝑟&'%)* ≪ 1 | 1 temper, ≫ 1
56. どの最下位ビットを採用するのか？ 再掲 : twist 𝑆+ 𝑆+," 𝑆!"#$% ＝ ＝ ⊕ (⊕ 0x9908b0df) 𝑆!"&'( = = 1 のとき = 0
57. どの最下位ビットを採用するのか？ 再掲 : twist 𝑆+ 𝑆+," 𝑆!"#$% ＝ ＝ ⊕ (⊕ 0x9908b0df) 𝑆!"&'( = = 1 のとき = 0 1ビットしか残ってない
58. どの最下位ビットを採用するのか？ 再掲 : twist 𝑆+ 𝑆+," 𝑆!"#$% ＝ ＝ ⊕ (⊕ 0x9908b0df) 𝑆!"&'( = = 1 のとき = 0 全ビット使われている
59. どの最下位ビットを採用するのか？ 再掲 : twist 𝑆+ 𝑆+," 𝑆!"#$% ＝ ＝ ⊕ (⊕ 0x9908b0df) 𝑆!"&'( = = 1 のとき = 0 32ビット中実質31ビット使われている そのうち1ビットは大きな違いをもたらす
60. 1bit欠損メルセンヌ・ツイスタの予測 • 目標 ： 内部状態の復元 • 条件 ： 連続する1248個の乱数が分かっている 𝑆+ 𝑆+," 𝑆!"#$% 𝑆!"&'( twist 𝑟& ≪ 1 | 0, 𝑟& ≪ 1 | 1 untemper 𝑟&'" ≪ 1 | 0, 𝑟&'" ≪ 1 | 1 𝑟&'#$( 𝑟&'%)* ≪ 1 | 0, 𝑟&'%)* ≪ 1 | 1 temper, ≫ 1 合っているか確かめる
61. 1bit欠損メルセンヌ・ツイスタの予測 • 目標 ： 内部状態の復元 • 条件 ： 連続する1248個の乱数が分かっている 𝑆+," 𝑆+,$ 𝑆!"#$) 𝑆!"&'* twist 𝑟&'" ≪ 1 | 0, 𝑟&'" ≪ 1 | 1 untemper 𝑟&'$ ≪ 1 | 0, 𝑟&'$ ≪ 1 | 1 𝑟&'#$+ 𝑟&'%), ≪ 1 | 0, 𝑟&'%), ≪ 1 | 1 temper, ≫ 1 合っているか確かめる
62. 1bit欠損メルセンヌ・ツイスタの予測 • 目標 ： 内部状態の復元 • 条件 ： 連続する1248個の乱数が分かっている この方法だと計算するのは 2&×624 通りでいい 𝑆+," 𝑆+,$ ・・・ 𝑆!"#$% ・・・ 𝑆!"&'# 𝑆!"#$) 𝑆!"&'( 内部状態が復元できた!!
63. 本当に正しく予測できているのか？ • 𝑆"#$ を復元した内部状態として採用すると必ず正しく予測できる • 正しく予測できない時 → 𝑟"#$ に付けるビットが異なるにもかかわらず 𝑟"#)*+ が同じになる場合がある時 𝑆+ 𝑆+," 𝑆!"#$% 𝑆!"&'( twist 𝑟& ≪ 1 | 0, 𝑟& ≪ 1 | 1 untemper 𝑟&'" ≪ 1 | 0, 𝑟&'" ≪ 1 | 1 𝑟&'#$( 𝑟&'%)* ≪ 1 | 0, 𝑟&'%)* ≪ 1 | 1 temper, ≫ 1
64. 本当に正しく予測できているのか？ • 全ての乱数に対してこの場合を探すのは大変すぎる • 二元体上では XOR もビットシフトも行列の演算で表せる → それらの合成関数である untemper は線型写像なので、 untemper 𝑥 ⊕ 1 = untermper 𝑥 ⊕ untemper 1 これを使うと正しく予測できない場合を次のように変えることができる
65. 本当に正しく予測できているのか？ 正しく予測できないのは、以下を満たす 𝑏: , 𝑏&'( が存在する時 𝑏: , 𝑏&'( = 0, 1 untemper 𝑏! ＝ ＝ ⊕ (⊕ 0x9908b0df) = = 1 のとき = 0 untemper 1 0 untemper 𝑏%()
66. 本当に正しく予測できているのか？ • そのような 𝑏: , 𝑏&'( は存在しないので 𝑆"#$ を採用すれば正しく予測できる • この方法を使えば1ビット欠損したメルセンヌ・ツイスタを乱数が生成された早さ にかかわらず、ブルートフォースも無しで予測することができる！！
67. まとめ • 普通のメルセンヌ・ツイスタは連続する624個の乱数を観測すれば予測できる • 1bit 欠損メルセンヌ・ツイスタは連続する1248個の乱数を観測すれば予測 できる • メルセンヌ・ツイスタに興味を持った方は kurenaif さんの kurenaif Valentine Problems を解こう！
68. 謝辞 本スライドで説明した、1248個の乱数から1bit欠損メルセンヌ・ツイスタを予測 する方法は、セキュリティキャンプ全国大会2021で kurenaif さんから出題してい ただいた問題によるものです。 また、untemper の線形性を利用した、1bit欠損メルセンヌ・ツイスタの予測方法 の正当性の説明は、同じく 魔女のお茶会 2021/冬 にて発表した しとおさん の 証明を元にスライドにさせていただきました。 kurenaif さん、しとおさん、本当にありがとうございました。
69. 参考文献 • Makoto Matsumoto, Takuji Nishimura “Mersenne Twister: A 623- dimensionally equidistributed uniform pseudorandom number generator” http://www.math.sci.hiroshima-u.ac.jp/m-mat/MT/ARTICLES/mt.pdf • 松本 眞 「あなたの使っている乱数、大丈夫？」 http://www.math.sci.hiroshima-u.ac.jp/m-mat/TEACH/ichimura-sho- koen.pdf • inaz2 ももいろテクノロジー 「Mersenne Twisterの出力を推測してみる」 https://inaz2.hatenablog.com/entry/2016/03/07/194147
70. 参考文献 • AMBIONICS SECURITY “BREAKING PHP'S MT_RAND() WITH 2 VALUES AND NO BRUTEFORCE” https://www.ambionics.io/blog/php-mt-rand-prediction • kurenaif “kurenaif Valentine Problems/three_values_twister” https://github.com/kurenaif/kurenaif_valentine_problems/tree/main/ three_values_twister • sekai 6715.jp 「メルセンヌ・ツイスタを倒す」 https://6715.jp/posts/6/