Upgrade to Pro — share decks privately, control downloads, hide ads and more …

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

kobaryo
November 14, 2021

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

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

kobaryo

November 14, 2021
Tweet

More Decks by kobaryo

Other Decks in Programming

Transcript

  1. Who am I? • 名前: artoy (twitter: @artoy5884) • 専門:

    プログラム検証 • CTF歴: 1週間
  2. 乱数生成方法 1. 内部状態の初期化 2. 内部状態の更新 3. 乱数の生成 * 3で624個乱数を生成したら2に戻る 𝑆!

    𝑆" ・・・ 𝑆#$% シード値 𝑆#$& 𝑆#$' 𝑆!"#$ ・・・ 𝑟! 𝑟" 𝑟#$% 1 2 3 ・・・ *
  3. 内部状態の更新 • twist : 𝑆" , 𝑆"#$, , 𝑆"#&'( から

    𝑆"#)*+ を求める操作 twist によって新しく624個の値を求めてそれらを新しい内部状態とする 𝑆! 𝑆" 𝑆$ ・・・ 𝑆%() ・・・ 𝑆#$% 𝑆%(* 内部状態
  4. 内部状態の更新 • twist : 𝑆" , 𝑆"#$, , 𝑆"#&'( から

    𝑆"#)*+ を求める操作 twist によって新しく624個の値を求めてそれらを新しい内部状態とする 𝑆! 𝑆" 𝑆$ ・・・ 𝑆%() ・・・ 𝑆#$% 𝑆%(* twist 𝑆#$&
  5. 内部状態の更新 • twist : 𝑆" , 𝑆"#$, , 𝑆"#&'( から

    𝑆"#)*+ を求める操作 twist によって新しく624個の値を求めてそれらを新しい内部状態とする 𝑆! 𝑆" 𝑆$ ・・・ 𝑆%() ・・・ 𝑆#$% 𝑆%(* twist 𝑆#$& 𝑆#$'
  6. 内部状態の更新 • twist : 𝑆" , 𝑆"#$, , 𝑆"#&'( から

    𝑆"#)*+ を求める操作 twist によって新しく624個の値を求めてそれらを新しい内部状態とする 𝑆! 𝑆" 𝑆$ ・・・ 𝑆%() ・・・ 𝑆#$% 𝑆%(* 𝑆#$& 𝑆#$' ・・・ 𝑆!"#$ 新しい内部状態
  7. twist • 𝑆"#$ の最下位ビットが0の時 𝑆"#)*+ = 𝑆"#&'( ⊕ 𝑆" &

    0x80000000 | 𝑆"#$ & 0x7ffffffff ≫ 1 • 𝑆"#$ の最下位ビットが1の時 𝑆"#)*+ = 𝑆"#&'( ⊕ 𝑆" & 0x80000000 | 𝑆"#$ & 0x7ffffffff ≫ 1 ⊕ 0x9908b0df
  8. twist • 𝑆"#$ の最下位ビットが0の時 𝑆"#)*+ = 𝑆"#&'( ⊕ 𝑆" &

    0x80000000 | 𝑆"#$ & 0x7ffffffff ≫ 1 • 𝑆"#$ の最下位ビットが1の時 𝑆"#)*+ = 𝑆"#&'( ⊕ 𝑆" & 0x80000000 | 𝑆"#$ & 0x7ffffffff ≫ 1 ⊕ 0x9908b0df 𝑆& の最上位ビットのみを取っている
  9. twist • 𝑆"#$ の最下位ビットが0の時 𝑆"#)*+ = 𝑆"#&'( ⊕ 𝑆" &

    0x80000000 | 𝑆"#$ & 0x7ffffffff ≫ 1 • 𝑆"#$ の最下位ビットが1の時 𝑆"#)*+ = 𝑆"#&'( ⊕ 𝑆" & 0x80000000 | 𝑆"#$ & 0x7ffffffff ≫ 1 ⊕ 0x9908b0df 𝑆&'" の最上位ビット以外を取っている
  10. twist • 𝑆"#$ の最下位ビットが0の時 𝑆"#)*+ = 𝑆"#&'( ⊕ 𝑆" &

    0x80000000 | 𝑆"#$ & 0x7ffffffff ≫ 1 • 𝑆"#$ の最下位ビットが1の時 𝑆"#)*+ = 𝑆"#&'( ⊕ 𝑆" & 0x80000000 | 𝑆"#$ & 0x7ffffffff ≫ 1 ⊕ 0x9908b0df 異なるのはここだけ
  11. temper temper を疑似コードで表すと以下のようになっている temper 𝑥 : 𝑥 ← 𝑥 ⊕

    𝑥 ≫ 11 𝑥 ← 𝑥 ⊕ 𝑥 ≪ 7 & 0x9d2c5680 𝑥 ← 𝑥 ⊕ 𝑥 ≪ 15 & 0xefc6000 𝑥 ← 𝑥 ⊕ 𝑥 ≫ 18 return 𝑥
  12. untemper temper は 𝑥 と 𝑥 をシフトさせたものの XOR という操作で構成されている →

    𝑥 のままの部分を利用してその操作の逆操作ができる 例 : 𝑥 ⊕ 𝑥 ≫ 11 𝑥 = 上位ビット 下位ビット
  13. untemper temper は 𝑥 と 𝑥 をシフトさせたものの XOR という操作で構成されている →

    𝑥 のままの部分を利用してその操作の逆操作ができる 例 : 𝑥 ⊕ 𝑥 ≫ 11 ⊕ ) 11ビット → 𝑥 のまま 𝑥 = 𝑥 ⊕ 𝑥 ≫ 11 =
  14. untemper 例 : 𝑦 = 𝑥 ⊕ 𝑥 ≫ 11

    目標 : 𝑦 から 𝑥 を求める 𝑥 = 11ビット (既知) 11ビット 10ビット
  15. untemper 例 : 𝑦 = 𝑥 ⊕ 𝑥 ≫ 11

    目標 : 𝑦 から 𝑥 を求める ⊕ ) 𝑦 = 𝑥 = 11ビット
  16. untemper 例 : 𝑦 = 𝑥 ⊕ 𝑥 ≫ 11

    目標 : 𝑦 から 𝑥 を求める ⊕ ) 𝑦 ⊕ (𝑦 ≫ 11) = 𝑥 = 11ビット = 𝑦 = 𝑦 ≫ 11
  17. untemper 例 : 𝑦 = 𝑥 ⊕ 𝑥 ≫ 11

    目標 : 𝑦 から 𝑥 を求める ⊕ ) 𝑦 ⊕ (𝑦 ≫ 11) = 𝑥 = 打ち消せる!
  18. untemper 例 : 𝑦 = 𝑥 ⊕ 𝑥 ≫ 11

    目標 : 𝑦 から 𝑥 を求める ⊕ ) 𝑦 ⊕ (𝑦 ≫ 11) = 𝑥 = 11ビット11ビット 緑の部分が分かった!
  19. untemper 例 : 𝑦 = 𝑥 ⊕ 𝑥 ≫ 11

    目標 : 𝑦 から 𝑥 を求める ⊕ ) 𝑦 ⊕ (𝑦 ≫ 11) = 𝑥 = 11ビット11ビット = 𝑧 緑の部分が分かった!
  20. untemper 例 : 𝑦 = 𝑥 ⊕ 𝑥 ≫ 11

    目標 : 𝑦, 𝑧 から 𝑥 を求める ⊕ ) 𝑦 ⊕ (𝑧 ≫ 11) = 𝑥 = 11ビット = 𝑦 = 𝑧 ≫ 11
  21. untemper 例 : 𝑦 = 𝑥 ⊕ 𝑥 ≫ 11

    目標 : 𝑦, 𝑧 から 𝑥 を求める ⊕ ) 𝑦 ⊕ (𝑧 ≫ 11) = 𝑥 = 11ビット 打ち消せる!
  22. untemper 例 : 𝑦 = 𝑥 ⊕ 𝑥 ≫ 11

    目標 : 𝑦, 𝑧 から 𝑥 を求める 𝑦 ⊕ (𝑧 ≫ 11) = 𝑥 = 𝑥 に戻せた!
  23. untemper この操作を疑似コードで表すと以下のようになる untemper_right_shift (𝑦, shift): 𝑧 = 𝑦 known_bits =

    shift while (𝑖 < 32) begin 𝑧 ← 𝑦 ⊕ 𝑧 ≫ shift known_bits ← known_bits + shift end return 𝑧
  24. 再掲 : temper temper を疑似コードで表すと以下のようになっている temper 𝑥 : 𝑥 ←

    𝑥 ⊕ 𝑥 ≫ 11 𝑥 ← 𝑥 ⊕ 𝑥 ≪ 7 & 0x9d2c5680 𝑥 ← 𝑥 ⊕ 𝑥 ≪ 15 & 0xefc6000 ビットが and されている場合は? 𝑥 ← 𝑥 ⊕ 𝑥 ≫ 18 → ほぼ同様の方法で戻せる return 𝑥
  25. untemper 例 : 𝑦 = 𝑥 ⊕ 𝑥 ≪ 7

    & 0x9d2c5680 目標 : 𝑦 から 𝑥 を求める 𝑥 = 7ビット 7ビット 7ビット 7ビット 4ビット ⊕ ) 𝑦 = 7ビット & 0x9d2c5680
  26. untemper 例 : 𝑦 = 𝑥 ⊕ 𝑥 ≪ 7

    & 0x9d2c5680 目標 : 𝑦 から 𝑥 を求める ⊕ ) 𝑦 ⊕ 𝑦 ≪ 7 & 0x9d2c5680 = 𝑥 = & 0x9d2c5680 & 0x9d2c5680 & 0x9d2c5680 & 0x9d2c5680 = 𝑦 = 𝑦 ≪ 7 & 0x9d2c5680
  27. untemper 例 : 𝑦 = 𝑥 ⊕ 𝑥 ≪ 7

    & 0x9d2c5680 目標 : 𝑦 から 𝑥 を求める ⊕ ) 𝑦 ⊕ 𝑦 ≪ 7 & 0x9d2c5680 = 𝑥 = & 0x9d2c5680 & 0x9d2c5680 & 0x9d2c5680 & 0x9d2c5680 打ち消せる!
  28. untemper 例 : 𝑦 = 𝑥 ⊕ 𝑥 ≪ 7

    & 0x9d2c5680 目標 : 𝑦 から 𝑥 を求める ⊕ ) 𝑦 ⊕ 𝑦 ≪ 7 & 0x9d2c5680 = 𝑥 = & 0x9d2c5680 水色の部分が分かった! → 後はこれの繰り返し
  29. untemper この操作を疑似コードで表すと以下のようになる untemper_left_shift (𝑦, shift, mask): 𝑧 = 𝑦 known_bits

    = shift while (𝑖 < 32) begin 𝑧 ← 𝑦 ⊕ 𝑧 ≪ shift & mask known_bits ← known_bits + shift end return 𝑧
  30. untemper untemper を疑似コードで表すと以下のようになる untemper 𝑥 : 𝑥 ← untemper_right_shift (𝑥,

    18) 𝑥 ← untemper_left_shift (𝑥, 15, 0xefc60000) 𝑥 ← untemper_left_shift (𝑥, 7, 0x9d2c5680) 𝑥 ← untemper_right_shift (𝑥, 11) return 𝑥
  31. 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
  32. 1bit欠損メルセンヌ・ツイスタの予測 • twist : 𝑆" , 𝑆"#$, , 𝑆"#&'( から

    𝑆"#)*+ を求める操作 𝑟"#)*+ が正しい時、𝑟", 𝑟"#$, 𝑟"#&'( の落ちた最下位ビットのうち一つくらいは 正しいのではないか? 𝑆+ 𝑆+," 𝑆!"#$% 𝑆!"&'( twist 𝑟& ≪ 1 | 0, 𝑟& ≪ 1 | 1 untemper 𝑟&'" ≪ 1 | 0, 𝑟&'" ≪ 1 | 1 𝑟&'#$( 𝑟&'%)* ≪ 1 | 0, 𝑟&'%)* ≪ 1 | 1 temper, ≫ 1
  33. どの最下位ビットを採用するのか? 再掲 : twist 𝑆+ 𝑆+," 𝑆!"#$% = = ⊕

    (⊕ 0x9908b0df) 𝑆!"&'( = = 1 のとき = 0 1ビットしか残ってない
  34. どの最下位ビットを採用するのか? 再掲 : twist 𝑆+ 𝑆+," 𝑆!"#$% = = ⊕

    (⊕ 0x9908b0df) 𝑆!"&'( = = 1 のとき = 0 全ビット使われている
  35. どの最下位ビットを採用するのか? 再掲 : twist 𝑆+ 𝑆+," 𝑆!"#$% = = ⊕

    (⊕ 0x9908b0df) 𝑆!"&'( = = 1 のとき = 0 32ビット中実質31ビット使われている そのうち1ビットは大きな違いをもたらす
  36. 1bit欠損メルセンヌ・ツイスタの予測 • 目標 : 内部状態の復元 • 条件 : 連続する1248個の乱数が分かっている 𝑆+

    𝑆+," 𝑆!"#$% 𝑆!"&'( twist 𝑟& ≪ 1 | 0, 𝑟& ≪ 1 | 1 untemper 𝑟&'" ≪ 1 | 0, 𝑟&'" ≪ 1 | 1 𝑟&'#$( 𝑟&'%)* ≪ 1 | 0, 𝑟&'%)* ≪ 1 | 1 temper, ≫ 1 合っているか確かめる
  37. 1bit欠損メルセンヌ・ツイスタの予測 • 目標 : 内部状態の復元 • 条件 : 連続する1248個の乱数が分かっている 𝑆+,"

    𝑆+,$ 𝑆!"#$) 𝑆!"&'* twist 𝑟&'" ≪ 1 | 0, 𝑟&'" ≪ 1 | 1 untemper 𝑟&'$ ≪ 1 | 0, 𝑟&'$ ≪ 1 | 1 𝑟&'#$+ 𝑟&'%), ≪ 1 | 0, 𝑟&'%), ≪ 1 | 1 temper, ≫ 1 合っているか確かめる
  38. 1bit欠損メルセンヌ・ツイスタの予測 • 目標 : 内部状態の復元 • 条件 : 連続する1248個の乱数が分かっている この方法だと計算するのは

    2&×624 通りでいい 𝑆+," 𝑆+,$ ・・・ 𝑆!"#$% ・・・ 𝑆!"&'# 𝑆!"#$) 𝑆!"&'( 内部状態が復元できた!!
  39. 本当に正しく予測できているのか? • 𝑆"#$ を復元した内部状態として採用すると必ず正しく予測できる • 正しく予測できない時 → 𝑟"#$ に付けるビットが異なるにもかかわらず 𝑟"#)*+

    が同じになる場合がある時 𝑆+ 𝑆+," 𝑆!"#$% 𝑆!"&'( twist 𝑟& ≪ 1 | 0, 𝑟& ≪ 1 | 1 untemper 𝑟&'" ≪ 1 | 0, 𝑟&'" ≪ 1 | 1 𝑟&'#$( 𝑟&'%)* ≪ 1 | 0, 𝑟&'%)* ≪ 1 | 1 temper, ≫ 1
  40. 本当に正しく予測できているのか? • 全ての乱数に対してこの場合を探すのは大変すぎる • 二元体上では XOR もビットシフトも行列の演算で表せる → それらの合成関数である untemper

    は線型写像なので、 untemper 𝑥 ⊕ 1 = untermper 𝑥 ⊕ untemper 1 これを使うと正しく予測できない場合を次のように変えることができる
  41. 本当に正しく予測できているのか? • そのような 𝑏: , 𝑏&'( は存在しないので 𝑆"#$ を採用すれば正しく予測できる •

    この方法を使えば1ビット欠損したメルセンヌ・ツイスタを乱数が生成された早さ にかかわらず、ブルートフォースも無しで予測することができる!!
  42. 参考文献 • 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
  43. 参考文献 • 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/