はまやんはまやんはまやん

hamayanhamayan's blog

CTFのCryptoにおける乱数まとめ

Security

CTFにおけるCrypto入門とまとめの1つです。

乱数全般

  • PRNG: 疑似乱数ジェネレータ
  • HRNG: ハードウェア乱数ジェネレータ。物理プロセス（電子ノイズ、放射性崩壊、熱ノイズなど）を利用して真の乱数を生成できる専用チップを使用する
  • 色々な性質
    • 無作為性、ランダム性: 統計的偏りがない
    • 予測不可能性: 数値の次の発生は過去のシーケンスから推測不可
    • 非再現性: 例えばシードから同じシーケンスを再現できたりしない
  • カテゴリ
    • 弱い疑似乱数 = ランダム性
    • 強い疑似乱数 = ランダム性 and 予測不可能性
      • 暗号ではこれを使う
    • 真の乱数 = ランダム性 and 予測不可能性 and 非再現性
  • PRNGの種類
  • CPRNG: 暗号学的に安全な疑似乱数ジェネレータ
    • 統計的ランダム性テスト: 特定のシーケンスにおいて、次のビットを50%を超える確率で予測できないことをテスト
    • 十分に強力な攻撃に耐えられる必要がある。生成済みのシーケンスから次の乱数が推測できないか
  • CPRNGの設計カテゴリ
  • CSPRNG: 暗号論的擬似乱数列生成器
  • Intel CPUのrdseed, rdrand命令
    • Ivy Bridge以降のIntel CPUにはrdrandという命令が追加され、CPU内部の不確かな電子状態を使うことで乱数列を生成する
      • std::random_deviceはこれをそのまま使っている
    • だが/dev/urandomはこの命令だけに依存するような作り方をしていない。仮にrdrandが疑似乱数であった場合（つまり、バックドアがあった場合）に判断が付かないためである
  • /dev/urandom Linuxで乱数が欲しくなったらとりあえずこれを使っておけばいい
  • 乱数ジェネレータのベンチマークツール dieharder
  • 探索空間が小さい secrets.randbits(17)は全探索可能
  • 数学的な（統計的な？）法則
  • 用語
    • TRNG: 真性乱数生成器
      • 熱雑音や放射性崩壊といった予測不可能な物理現象を利用して乱数を生成
      • RSAやECCなどのアルゴリズムの鍵生成など、機密性の高い暗号処理によく使用されます
      • TRNGは専用のハードウェアを必要とし、他のRNGよりも速度が遅いがち
    • PRNG: 擬似乱数生成器
      • 統計PRNG: 統計的ランダム性テストに合格する数値を生成するように設計。これはランダム性は求められるが、セキュリティは最重要ではない
      • 暗号的に安全なPRNG（CSPRNG）: ランダム性が予測不可能で攻撃に対する耐性が求められる暗号用途向けに設計されたPRNG
    • エントロピー: ランダム性または予測不可能性の大きさを表す
      • 乱数を作るときはエントロピーを考えましょう Black Hat 2010 / Defcon 18
        • セッションIDに十分なエントロピーがあるように思われて、実は条件を絞っていくと組合せがどんどん減っていき、最終的には20bitsくらいのエントロピーにまで落ちる。そこまで落ちると、候補が106通りくらいになるから、全探索しても当たってしまうという話
    • seeding: シードと呼ばれる初期値を安全な暗号関数に与え、ランダムに見える数値列を生成する。シードが同じであれば、常に同じ列を生成する
  • ランダムの和

LCG, 線形合同法

QCG: Quadratic Congruential Generator, 二次関数合同法？

FSR: フィードバックシフトレジスタ

  • 初期状態 a0, a1, ..., an-1のn個の数列を用意
  • フィードバック関数 f(ax, ax+1, ..., ax+n-1) を用意
  • フィードバック関数を使って、ax, ax+1, ..., ax+n-1からax+nを作成して、状態をax+1, ax+2, ..., ax+nに遷移させて乱数を生成していく
  • 出力される乱数
    • a0, a1, a2, ... のように乱数が出力されていく場合もあるし
    • x0 = sum_{i=0..N-1} ci*ai みたいにある種の式を使って決定される場合もある

LFSR

  • LFSRの流れ
    1. 初期状態Rと、フィードバック関数maskがある
    2. R&maskをして1各桁の総和(xor和)を取ったものを次の乱数シーケンスの出力rとする
    3. 状態をR'=R<<1 + rで更新
    4. 2-3を繰り返す
    5. 大体maskと乱数列が与えられるのでRを求める問題が出る
  • 連続するn個の出力が得られれば特定状態を再現できるので、そこから逆行列を用いて初期状態を特定する
    • これはR'の下位1ビットと乱数シーケンスの出力rが一致することから内部状態が漏洩することになるため
    • 32bitsのLFSRであれば、連続する32bitsが分かれば、その1つ前の1bitsの状態のみが変数となる方程式が得られて計算できる
      • r = mask[0]*R[0] + mask[1]*R[1] + ... + mask[31]*R[31]でrとmask全部とRの0～30が既知なのでR[31]が計算できるということ
  • 連続してなくてもサンプルが取れれば、z3である程度解けるっぽい？
  • フィードバック関数が線形であるということは行列計算に帰着させることが可能になる
    • LFSRはGF(2n)上で線形。積は普通に積で、和はxorにしたもの
    • 繰り返し二乗法も行けるし、逆行列による計算も可能
  • 20220522_LFSRの超難問を解く - Google スライド
    • LFSRへの攻撃手法まとめ。
    • これを理解できればゴールした感ある
  • Berlekamp-Masseyアルゴリズム
    • 与えられた2進出力シーケンスに対して最短のLFSRを求めるアルゴリズム
    • N次のLFSR多項式を復元するには少なくとも2Nビットの出力が必要
      • 2N～4Nくらいあると安心？
    • BCHのデコードの一部としても使われている
  • LFSRは線形で逆算可能なので非線形要素を取り入れようという考えがある
  • sagemathでLFSRの計算をするときはBooleanPolynomialRingが使える
    • PR = BooleanPolynomialRing(names = [f'x{i}' for i in range(1, 7*2+24+1)])
  • いいまとめ
  • 問題

メルセンヌツイスター, Mersenne Twister, MT, MT19937

XorShift

  • 最初にstateを定めたあと、以下の処理を1サイクルとして、次の乱数を生成していく。 state = state ^ (state << a); state = state ^ (state >> b); state = state ^ (state << b);
  • シフトパラメタa,b,cによって乱数の質が変わる。周期性が変わる。
    • 13,17,5 -> Xorshiftの論文にもあるパラメタで32ビット用。64ビットに使うには微妙らしい
    • 64ビットでは、21,35,4が良い？
    • https://www.cepstrum.co.jp/hobby/xorshift/xorshift.html
    • 17,9,18だと280が周期になって与えられている試行回数を使うと2周目に突入できて、推測できた
  • XorShiftの計算は行列計算に変換し、高速化可能
  • 派生のxoshiro256/xoshiro256+/xoshiro256++/xoshiro256**というのもある

実装