[暗号技術入門] 暗号学的に安全な擬似乱数生成器 (CSPRNG)

暗号学において、ランダム性 (エントロピー) は非常に重要な役割を果たします。多くのアルゴリズムでは、乱数 (つまり予測不可能な値) が必要です。もしこれらの数値が予測不可能でない場合、アルゴリズムは危険にさらされてします。この章では、コンピュータサイエンスにおける乱数と暗号学における役割、そして、疑似乱数生成器 (PRNG) とセキュアな疑似乱数生成器 (CSPRNG) について詳しく説明し、開発者がコード内で乱数を生成および使用する際のいくつかのガイドラインについて見ていきたいと思います。

乱数生成

例えば、情報資産を保護する秘密鍵が必要だとします。この秘密鍵は、他の誰もが同じ鍵を生成または持つことができないようにランダムに生成される必要があります。もし鍵をセキュアな乱数生成器から生成すれば、それは予測不可能であり、システムは安全になります。したがって、セキュアなランダムとは単に「予測不可能なランダム」を意味します。

コンピュータサイエンスにおいて、ランダムな数値は通常、ある予測不可能な初期乱数 (エントロピー) によって初期化された疑似乱数生成器 (PRNG) から生成されます。暗号学では、CSPRNG として知られる安全なPRNGが使用され、通常、エントロピーとPRNG、その他の技術を組み合わせて生成される乱数を予測不可能にします。

疑似乱数生成器 (PRNG)

疑似乱数生成器 (PRNG) は、少量の初期乱数を大量の疑似乱数に拡張するために使用され、通常は暗号システムで使用されます。 PRNGは暗号論的に安全ではなく、CSPRNGとは異なります。 PRNGは、ある初期エントロピー (シード) から始まり、シードを知らないと予測できない計算によって次の乱数を計算する関数です。このような計算は疑似乱数関数と呼ばれます。暗号学的に安全ではない疑似ランダム関数は通常、内部の状態を使用します。開始時に、状態は初期シードによって初期化されます。次の乱数が生成されるとき、内部の状態から計算され、その後に、疑似ランダム関数の内部状態が変更されます。次の乱数が生成されるとき、再び関数の内部状態に基づいて計算され、この状態が再び変更されます。

この一連のプロセスを簡単に示すと、次のように実装できます：

def init(entropy):
  state = entropy
  counter = 0

def nextNum():
  counter += 1
  state = HMAC(state, counter)
  return state

疑似乱数生成器は内部に状態を持ち、ある初期乱数で初期化され、時間の経過とともに内部状態を変更し、現在の状態に基づいて疑似乱数を生成します。良い乱数生成器は高速であり、統計的ランダム性を生成する必要があります (Diehard検定法を参照)。つまり、すべての数値が時間の経過とともに生成される確率が同じであるべきです。これは暗号学的に十分ではないため、CSPRNGにはより高い要件があります。

HMAC(key + counter) に基づいてランダムな疑似数を生成する上記の考え方は、HMAC_DRBG 擬似乱数生成アルゴリズムでも使われており、セキュリティ標準 NIST 800-90A で説明されています。

初期エントロピー (シード)

セキュリティを確保するために、統計的にランダムなPRNG (擬似乱数生成器) は、真にランダムな初期シードで始めるべきであり、それは絶対に予測不可能であるべきです。もしシードが予測可能であれば、予測可能な乱数列を生成し、全体のランダム生成プロセスが安全でなくなります。そのため、開始時に予測不可能なランダム性 (安全なシード) を持つことが非常に重要です。

擬似乱数生成器を安全に初期化するための方法は、ランダム性 (エントロピー) を収集することです。

エントロピー

コンピュータサイエンスにおいて「エントロピー」とは予測不能なランダム性を意味し、通常はビットで測定されます。例えば、コンピュータのマウスを動かすと、マウスカーソルの開始位置や終了位置など、予測が難しいイベントが生成されます。マウスが位置を[0…255]ピクセルの範囲で変更したと仮定すると、このマウスの動きから収集されるエントロピーは約8ビットになるはずです (2^8 = 255)。別の例として、ユーザに[0…1000]の範囲で数字を考えるよう求めた場合、その数字は約9〜10ビットのエントロピーを持つことになります (2^10 = 1024)。256ビットのエントロピーを収集するためには (例えば256ビットの整数を安全に生成するために)、複数のこのようなイベントのシーケンス (ユーザからのマウスの動きやキーボード入力など) を考慮する必要があります。

エントロピーの収集

コンピュータ内の多くの予測困難なイベントからエントロピーを収集することができます：キーボードのクリック、マウスの動き、ネットワークのアクティビティ、カメラのアクティビティ、マイクのアクティビティなどが、それらが発生する時間と組み合わされます。この初期乱雑さの収集は一般的に、オペレーティングシステム (OS) によって内部的に実行され、それにアクセスするための標準APIを提供します (例：Linuxの /dev/random ファイルから読み取る)。デスクトップシステム、ノートパソコン、または携帯電話では、エントロピーを収集するのは簡単ですが、一部の限られたハードウェアデバイス (単純なマイクロコントローラなど) では、エントロピーを収集することが困難または不可能です。

アプリケーションソフトウェアは、明示的にエントロピーを収集することができます。これは、ユーザーにマウスを動かしたり、キーボードで何かを入力したり、マイクで何かを言ったり、カメラの前でしばらく動いたりするように求めることです。例えば bitaddress.org というサイトでは、マウスの動きとキーボードイベントを組み合わせてエントロピーを収集します。

十分なエントロピーが収集されると、それを使用して乱数生成器を初期化します。

不安定な乱数

不安定な乱数や侵害された乱数は暗号を危険にさらす可能性があります。壊れた乱数生成器を使用したことでビットコインが盗まれてしまう可能性もあります。そのため、開発者は暗号を使用する際に乱数に注意を払い、乱数生成器が安全であることを確認する必要があります。

Pythonの古いバージョンでは、乱数のセキュリティを危険にさらすことが簡単にできてしまいます。例えば、次のプログラムは暗号学的に安全ではない乱数生成方法です。：

import random
print(random.randrange(1000000, 9999999))

上記のコードはランダムな数値を生成することを想定していますが、この数値は予測できる可能があります。これは、古いバージョンのPythonのrandomライブラリが乱数生成器のシードを現在の時刻で初期化するためです。したがって、ランダムな数値を生成するマシンでの現在時刻を知っている場合、ランダムシードを予測し、生成されるランダムな数値を予測することができます。

これをよりよく説明するために、次のより明示的な例を見てみましょう。この例では、50桁の整数を2つ生成します：

import random
import time

random.seed(int(time.time()))
r1 = random.randrange(1e49, 1e50-1)

random.seed(int(time.time()))
r2 = random.randrange(1e49, 1e50-1)

print(r1)
print(r2)

上記のコードは、2つの等しい数値を出力します。どちらも現在時刻に依存しています。初期シードで同じ時刻が設定されると、出力で同じ (予測可能な) 疑似乱数が生成されることが明らかです。上記のコードのサンプル出力は次のとおりです：

58360156071482168893599555600275701003496706690263
58360156071482168893599555600275701003496706690263

このコードをデバッガで実行するか、処理が遅い環境で実行すると、生成される数値が異なる場合があります。これは、2つのランダム生成の実行間での時刻の変更によるものです。通常、対話型コンソールのPythonインタプリタは2つの異なる数値を生成します。上記の結果と同様の結果を得るには、まずコードをスクリプトファイルに保存して、その後Pythonスクリプトファイルを実行してください。

基本的に、初期ランダムシードが現在時刻のような予測可能な数値で初期化されると、悪意のある攻撃者は範囲内の +5秒〜 -5秒のすべての可能性を試し、正確な初期シードを見つけることを試みます。初期シードが特定されてしまうと、その乱数生成器によって作成された乱数を特定でき、擬似乱数生成器で作成された秘密鍵が特定できるため、セキュリティを危険にさらすことになります。

ランダム性と暗号化

暗号化は予測不可能なランダム性なしには機能しません。もし乱数生成器が危険にさらされると、予測可能な数値を生成し、悪意のある攻撃者が通信を解読したり、秘密鍵を明らかにしたり、デジタル署名を改ざんしたりすることができるようになります。開発者として、使用する暗号化ライブラリでどのように乱数値が生成されているかを常に気にかける必要があります。

CSPRNG (Cryptography Secure Random Number Generators)

CSPRNG (Cryptography Secure Random Number Generators) は、暗号学で使用するのに適した擬似乱数生成器 (PRNG) であり、特定の特性を持っています。 PRNGがCSPRNGであるためには、主に2つの要件があります：

Next-bit検定法を満たすこと：
- PRNGの開始時点からすべての k ビットを知っている人でも、合理的な計算リソースを使用してビット k+1 を予測することができないこと。
状態侵害拡張攻撃に耐えること：
- 攻撃者がPRNGの内部状態を推測したり、何らかの方法で明らかになった場合、その攻撃者は明らかになる前のすべての前の乱数を再構築することができないこと。

オペレーティングシステムのエントロピーは通常、限られた量しかなく、さらなるエントロピーを待つことは遅くて非効率的です。ほとんどの暗号アプリケーションは、オペレーティングシステムからの利用可能なエントロピーをより多くのビットに「伸ばし」、暗号目的に必要なものに合致し、上記のCSPRNGの要件を満たすCSPRNGを使用しています。

多くの設計が提案されていますが、CSPRNGアルゴリズムを構築するためにはいくつかの方法があります：

ブロック暗号をカウンターモードで使用したCSPRNG
ストリーム暗号または安全な安全なハッシュ関数に基づくCSPRNG
整数の因数分解問題 (IFP)、離散対数問題 (DLP) または楕円曲線離散対数問題 (ECDLP) の難しさに依存する数論に基づくCSPRNG
暗号学的に安全なランダム性のための特別な設計に基づくCSPRNGには、例えばYarrowアルゴリズムやFortunaなどがあり、これらはMacOSやFreeBSDで使用されています。

ほとんどのCSPRNGは、オペレーティングシステムからのエントロピーと高品質のPRNGジェネレーターの組み合わせを使用し、定期的に「再シード」(reseed) を行います。これは、たとえば、ユーザー入力、システム割り込み、ディスクI/O、またはハードウェア乱数生成器のような新しいエントロピーがOSから供給されると、基礎となるPRNGが新しいエントロピーのビットに基づいて内部状態を変更することを意味します。この定期的な再シードにより、CSPRNGは予測や分析が非常に困難になります。

結論 : 暗号学的に安全な擬似乱数生成器を使用すること

Pythonであれば secrets ライブラリ、Javaであれば java.security.SecureRandom など、暗号学的に安全な乱数生成器ライブラリを常に使用してください：

import secrets
print(secrets.randbelow(int(1e50)))

上記のコードは現在の時刻に依存せず、基本的にはオペレーティングシステムによって収集されたエントロピーに基づいて予測不可能な乱数を生成します。