担当：谷

目次

• 乱数の性質
  • 無作為性
  • 予測不可能性
  • 再現不可能性
• 疑似乱数生成器
  • 線形合同法
  • 一方向性ハッシュ
  • 暗号
  • ANSI X9.17
• 乱数に対する攻撃
  • 種に対する攻撃
  • ランダムプールに対する攻撃

乱数

乱数列

• ランダムな数列のこと
• 数学的に述べれば、今得られている数列 x1, x2, …, xn から次の数列の値 xn+1 が予測できない数列
• 乱数列の各要素を乱数という

乱数の性質

【弱い疑似乱数】無作為性(randomness):暗号技術として使用不可

• 統計的な偏りがなく,でたらめな数列になっている性質
• 攻撃者に「見破られないこと」が重要なため,暗号技術として使用するのは不向き(例：線形合同法)
• 通常のコンピュータゲームで使用する乱数は無作為性を満たしていれば十分
  • 乱数の検定
    • 疑似乱数列が無作為であるかどうかを調べる方法
    • たくさんの種類がある

【強い疑似乱数】予測不可能性(unpredictability):暗号技術として使用可

過去の数列から次の数を予測できないという性質

【真の乱数】再現不可能性:暗号技術として使用可

• 同じ数列を再現できないといった性質
• 再現するためには数列そのものを保持しておく必要あり

乱数の性質 – 予測不可能性 –

• 疑似乱数生成器のアルゴリズムは攻撃者が知っている
• 疑似乱数の種(疑似乱数を生成するための初期値)は攻撃者に秘密

上記の2つを満たす場合,たとえ過去の疑似乱数列を攻撃者に知られても,次に出力する疑似乱数は予測不可能

予測不可能性を持つ疑似乱数生成器を作る方法
→「一方向性ハッシュ関数の一方向性」や「暗号の機密性」などの他の暗号技術を用いて,疑似乱数生成器の予測不可能性を確保する

乱数の性質 – 再現不可能性 –

• ある乱数列と同じ数列を再現することができない性質
• ある乱数列を再現するためには,ある乱数列そのものを保存しておく以外方法がない場合に,ある乱数列は再現不可能性を持つといえる

ソフトウェアだけでは再現不可能性乱数列を作成することは不可能！

• ソフトウェアを支えているコンピュータが有限の内部状態しか持たないため
• ソフトウェアは同じ内部状態から必ず同じ乱数を生成するため,いつか繰り返しになる.
• ソフトウェアが生成する乱数は常に有限の周期をもつため,再現不可能性とは言えない.
  • 周期
    • 繰り返しに陥るまでの数列の長さ

再現不可能性をもつ乱数の身近な例

公開鍵生成時に使用したツール「PuttyGen」の鍵生成時に行った,ゲージ100％になるまでマウスぐるぐる

再現不可能性を持つ乱数列

• マウスぐるぐる
• キーボードを打つ時の時間間隔
• 放射線観測機からの出力
  上記はいずれもハードウェアから得られた情報をもとに生成した数列

疑似乱数生成器

乱数生成器(random number generator/RNG)

熱や音の変化等の予測や再現が事実上不可能である自然現象をセンサーで検知した結果をもとに乱数列を生成するハードウェアのこと

疑似乱数生成器(pseudo random number generator/PRNG)

• 乱数を生成するソフトウェアのこと
• ソフトウェアのみで真の乱数を生成することはできないため「疑似」がつく
  • 線形合同法
  • 一方向ハッシュ関数を使う方法
  • 暗号を使う方法
  • ANSI X9.17

疑似乱数生成器 – 種と内部状態 –

内部状態

• 疑似乱数生成器が管理しているメモリの値
• 内部状態を攻撃者に知られてはいけない

種(seed)

• 疑似乱数生成器の内部処理を初期化するために使用
• ランダムなビット列かつ予測不可能な値
• 種を攻撃者に知られてはいけない

疑似乱数生成器 – 線形合同法(liner congruential method) –

非常によく使われる疑似乱数生成器だが,予測不可能性を持たないため暗号技術には使用不可

疑似乱数 = (A * 内部状態 + C) mod M

• 最初の疑似乱数を求める場合に限り,「内部状態」の部分に「種」が入る
• A,C,Mは定数でA<M,C<Mを満たすこと

周期とかについてはもうPHPで説明する (liner_seed.php)
PHPでの計算をもとに説明
* 疑似乱数列の結果を見ると偏りがあることがわかる。
* A,C,Mの値を注意深く選択(周期が大きいもの)すれば,偏りについては解決できるため,無作為性の性質は持つ

Cのライブラリ関数randやJavaのjava.util.Randomクラスなどは線形合同法を使用している

疑似乱数生成器 – 一方向ハッシュ関数を使用する方法 –

攻撃者が過去に出力した疑似乱数列を入手しても,次の疑似乱数列を予測するのは不可能
※予測するには一方向ハッシュ関数の一方向性を破らないといけないため
→一方向ハッシュ関数の一方向性が疑似乱数生成器の予測不可能性を満たしている

疑似乱数生成器 – 暗号を使用する方法 –

攻撃者が次の疑似乱数列を使用するには,現在のカウンタを知る必要あり出力される疑似乱数列は暗号化されているため,カウンタを知るためには暗号を解読する必要あり解読は困難のため,暗号の機密性が予測不可能性を満たしている

内部状態(カウンタ)を初期化

1. 鍵を使用しカウンタを暗号化したものを疑似乱数として出力
2. 疑似乱数1つ生成ごと内部状態のカウンタを1増加する

必要なだけの疑似乱数列を得られるまで上記を繰り返す

疑似乱数生成器 – ANSI X9.17 –

• 現在時刻自体は攻撃者が予測できるが,攻撃者は暗号化の鍵を知らないため,かき混ぜ役を予測することはできない
• かき混ぜ役はビット列をランダムに反転するために使用される
• 暗号を解読しないことには攻撃者は見破ることができないため,これまでに出力された疑似乱数列から内部状態を推測することはできない
• 疑似乱数生成器の内部状態を暗号がガードしている

攻撃

種に対する攻撃

種は暗号の「鍵」に匹敵する重要性をもつ
攻撃者に疑似乱数生成器のアルゴリズムを知られている状態で,
種まで知られてしまうと,疑似乱数列をすべて知られることになる
　→攻撃者に知られないよう,再現不可能性を持つ乱数を種とする必要がある

ランダムプールに対する攻撃

ランダムプール

• ファイルにランダムなビット列を蓄えておく方法
• 暗号ソフトウェアが疑似乱数の種を必要とするときは,
• このランダムプールから必要なだけのランダムなビット列を取り出して使用する
  攻撃者にランダムプールを知られてしまうと,疑似乱数の種を予測されてしまう可能性がある

乱数の使用例

ノンス(nonce) と ソルト(salt)

ノンス(nonce)

　暗号通信で使用される使い捨てのランダムな値.
　認証の過程で使われリプレイ攻撃(再生攻撃)を行えないようにする働きを担う
　サーバが401 Unauthorizedを返すため,リプレイ攻撃はほぼ不可能

ノンスの使用例

　HTTPのダイジェスト(Digest)認証
　　パスワードのMD5ダイジェストを生成する過程で使用
　　ダイジェスト認証はBasic認証では防げなかった盗聴や改ざんを防ぐために考案された

ソルト(salt)

　パスワードを暗号化する際に付与されるデータ
　ブルートフォース攻撃にはほとんど効果がない物の,レインボー攻撃に対しては有効

ブルートフォース攻撃

　　総当たりにハッシュ値を計算

レインボー攻撃　

　　あらかじめハッシュ値を計算し,標的のパスワードのハッシュ値と比較することでパスワードを推察.
　　ブルートフォース攻撃に比べ短時間でパスワードを解読することが可能

参考書籍

結城浩(2015)『暗号技術入門 第3版 秘密の国のアリス』SB Creative 446pp.
ISBN978-4-7973-8222-8
第12章 乱数(p312-p332)