ラバランプの無用性: ランダムが実際に意味するもの
(loup-vaillant.fr)- Cloudflareのラバランプベースの乱数プロモーションは、インターネット暗号化に大きな実質的貢献をするというより、マーケティングとセキュリティ劇場に近い
- 暗号で重要なのは、値の本質的なランダム性そのものよりも、攻撃者がその値についてどれだけ知っているかであり、この知識差が安全性を左右する
- One-time padは、十分にランダムな鍵を一度だけ使えば平文情報を隠せるが、同じ鍵を再利用すると観測された情報と結びついて破られる
- 現代のシステムはワンタイムパッドの代わりにCSPRNGとストリーム暗号を使い、ChaCha20やAES-256-CTRは256ビット鍵で現実的な安全性を提供する
- 物理的なtrue RNGはバイアス除去が難しく、安全性向上も小さいため、サーバーが直接シードを作成し、fast key erasureを使う単純な設計のほうが安全である
ランダム性は対象ではなく観測者の知識に依存する
- Cloudflareはlava lampがインターネット暗号化に役立つと宣伝しているが、この方式は安全性への大きな貢献というよりマーケティングとセキュリティ劇場に近い
- Cloudflareはラバランプのほかにも、double pendulums、wave motion、mobilesのような物理的に予測不能な装置を使っている
return 4しかしないXKCD風の関数は常に4を返すため、対象自体としてはランダムではないが、呼び出し側が「公平なサイコロで選ばれた定数」という情報だけを知って一度呼び出したなら、観測者の確率分布においてはランダムとして扱える- 暗号で重要な問いは、結果が本質的にランダムかどうかではなく、攻撃者がその結果についてどれだけ知っているかである
- 同じ値でも、誰がどの情報を持っているかによってランダム性の意味は変わり、暗号システムではこの知識差が安全性を決める
One-time padが機能し、破られる仕組み
- ロシアンルーレットの比喩では、共犯者は弾の位置を知っており、プレイヤーと事前共有したサイコロ値を弾の位置に足した結果だけを外部に伝える
- プレイヤーは叫ばれた値からサイコロ値を引いて弾の位置を復元できるが、相手はサイコロ値を知らないため、叫ばれた値だけでは弾の位置を知ることはできない
- 公平なサイコロであれば、相手が持つ事前確率
P(Ci)と、特定の数字S3を聞いた後の事後確率P(Ci|S3)は等しくなる - ベイズの公式では
P(Ci|S3) = P(Ci) × 1/6 ÷ 1/6 = P(Ci)となり、相手は叫ばれた値を聞いても 何の情報も得られない - この構造がOne-time padの核心であり、十分にランダムな鍵をメッセージと一度だけ組み合わせれば、暗号文は平文情報を明かさない
- 同じ鍵を2回目のゲームでも再利用すると、最初のゲームで明らかになった情報のため、相手はサイコロ値の可能範囲を絞り込める
- 最初のゲームで銃の前4つの薬室が空であると確認されると、相手はサイコロが3か4であった可能性だけが残ると分かり、2回目に共犯者が「Four」と叫べば、弾が最初の薬室または最後の薬室のどちらかだという情報まで得る
- One-time padはその名の通り一度しか安全ではなく、同じ鍵を再利用すると、観測された暗号文と以前の情報が結びついて安全性が崩れる
鍵長と現代暗号の現実的な安全性
- インターネットでは弾の位置の代わりにビットやバイトを送っており、1ビットの「yes/no」メッセージはコイントス1回で隠せる
- 表ならメッセージをそのままにし、裏なら「yes」と「no」を反転させる方式は、コイン結果を知らない観測者に対して平文を隠す
- しかし同じコイン結果で2ビットを暗号化すると、暗号文は4通りの平文候補を2通りにまで減らしてしまう
- “Yes yes” は平文が “yes yes” または “no no” だったことを意味する
- “No no” は平文が “no no” または “yes yes” だったことを意味する
- “Yes no” は平文が “yes no” または “no yes” だったことを意味する
- “No yes” は平文が “no yes” または “yes no” だったことを意味する
- 一般化すると、nビットを1回のコイントスだけで暗号化した場合、可能な平文空間は
2^nから2個にまで減る - 完全な情報理論的意味でnビットを正しく暗号化するには、nビット鍵が必要であり、それより長いメッセージでは一部が復号され、観測者がすでにnビット以上の情報を知っていれば、たいてい全体が復号され得る
- Cloudflareが処理する全トラフィックにワンタイムパッドを適用するには天文学的な量の乱数が必要に見えるが、現代のシステムはワンタイムパッドを使っていない
- 認証付き暗号とストリーム暗号を正しく使えば、256ビット鍵で大量のデータを現実的に安全に暗号化できる
- ChaCha20 や AES-256-CTR のような適切なストリーム暗号を使えば、受動的観測者は平文を見つけるために約
2^255通りの組み合わせを試す必要がある - 鍵を知る者にとってストリームは完全に予測可能だが、鍵を知らない地球文明レベルの観測者にとっては、完全に予測不能な「エントロピー」のように振る舞う
- この方式の正式名称は Cryptographically Secure Pseudo-Random Number Generator、略して CSPRNG である
実際の乱数生成と fast key erasure
- 256ビットのマスター鍵1つから必要な乱数を導出するには、マスターサーバーやハードウェアセキュリティモジュールにマスター鍵を置き、ローカル鍵ストリームを生成して会社全体へ安全に配布できる
- 各サーバーやCPUコアは、256ビットのローカル鍵とカウンターで必要なだけランダムなバイト列を生成できる
- 核心的な問題は、安全な配布が非常に難しいことにある
- ローカル鍵が漏えいすると、そのマシンが過去に暗号化したすべてのメッセージと今後暗号化するメッセージが危険にさらされ、マスター鍵が漏えいすれば被害はさらに大きい
- fast key erasure は、鍵漏えいの可能性と、漏えい時の被害を減らすための手順である
- 512バイトバッファの先頭に32バイトのランダムシードを置く
- そのシードで512バイトを生成し、バッファを上書きする
- 最初の32バイトを除いた残りを要求に応じて出力した後、消去する
- バッファを使い切ったら再び生成段階に戻る
- 「erasure」という名前は、生成段階で既存の鍵が消去されることに由来する
- バッファが漏えいすると将来のメッセージは危険にさらされ得るが、すでに出力され消去された過去の値は保護される
- より重要な注意点は、バッファを複製しないことである
- 同じシードから2つのストリームを作ってはならない
- プロセスをforkする際には、ストリームを適切に2つへ分割しなければならない
- 同じストリームが2つ以上生じると、同一のランダムバイト列が繰り返され、致命的になり得る
- このためユーザー空間RNGは推奨されず、カーネルRNGは簡単ではないにせよ、監査対象がより少ない
ストリーム暗号の選択と安全余裕
- 基盤となるストリーム暗号の内部ブロックサイズも重要である
- ChaCha20 の512ビットブロックは心配不要なほど大きく、AES の128ビットブロックも十分に大きい
- AESには単純な総当たりより成功確率がはるかに高い現実的攻撃があり、AES-128は破られ得るが、AES-256は安全と見なされる
- これより小さいブロックサイズは、この用途では破られたものと見なすべきである
- 推奨される選択肢はChaCha20またはAES-256であり、好みはChaCha20寄りである
- 現代のストリーム暗号は非常に安全であり、学術文献や各国政府、特に米国での利用事例まで考慮すると、近い将来に破られる可能性は非常に低いと見られる
- CSPRNGと暗号化はどちらも暗号に依存するため、そのどちらかが破られればシステム全体も破られる
- AES-256やChaCha20が近い将来に意味のある確率で破られると仮定するなら、安全余裕を増やす選択肢はある
- CSPRNGと暗号化に同じ暗号を使えば、攻撃者がAESとChaChaのどちらか一方を破ればよいという選択肢をなくし、特定の1つを破る必要がある状態にできる
- ラウンド数を増やせば、総当たりコストだけでなく、総当たりより優れた攻撃を防ぐ助けにもなる
- AES-256は14ラウンド、ChaCha20は20ラウンドを使用する
- ChaCha7にはexhaustive searchより優れた攻撃があるが、ChaCha8には現時点でそのような攻撃はない
- ChaCha20は20ラウンドを使うことで、仮に突然12ラウンド攻撃が見つかっても問題にならないよう余裕を持たせている
- 複数のシステムを並列に使う方式は全体の複雑さを大きく増やし、その複雑さは構成要素の1つに対する数学的攻撃よりも深刻な脆弱性を生みやすい
物理的 true RNG と初期シード
- 物理的なtrue RNGが、理論上破られ得るCSPRNGより常に安全だと考えるのは慎重であるべきだ
- ランダム出力は、安全性のため検出可能なバイアスがないことを求められる場合が多く、これは
2^64個のサンプルを解析してもバイアスを検出できないほど一様な分布を意味する - 物理過程をそのレベルまで調整するのは難しいため、実際にはノイズ源の出力を暗号学的ハッシュに通す必要がある
- fast key erasureを使うストリーム暗号と比べると、安全性の向上は小さく、必要に応じた性能コストは大きくなり得る
- 任意量の乱数を作るには、最初の数バイトのシードが必要である
- 予測不能なソースを十分長くデジタル記録して256ビット以上のエントロピーを得て、その記録をSHA-256やBLAKE2sのような256ビットハッシュでハッシュすれば、マスターシードを作れる
- 利用可能な乱数源としては、hardware random number generator、CPU jitter、ランダムな木の写真、beam splitter、キーボード入力やマウスイベント、サイコロなどがある
- サイト間での乱数配布は実用的ではなく、複雑なだけでなく侵害の原因にもなり得る
- 乱数は一度だけ必要なのではなく、侵害が疑われるときや重要なセキュリティアップデートを行うたびに必要になる
- 手間とリスクを減らすには、外部から持ち込むより、そのコンピュータ自身が使う乱数シードを直接生成するほうが概してよい
- 一般的なサーバーにはCPU jitter、周辺機器の相互作用、ネットワークイベントがあり、通常用途にはそれで十分である
- 追加の安全性が欲しければ、サーバーラックごとにハードウェアRNGドングルをいくつか追加できるが、それ以上に複雑な方式は不要な複雑性である
ラバランプの壁が不要な理由
- Cloudflareのラバランプの壁は不要であり、ローカルネットワーク経由でサーバーに接続すると、複雑性と攻撃面が増えるだけである
- 適切に実装すれば危険は非常に低く抑えられるかもしれないが、それでも得られる利益より危険のほうが大きい
- Cloudflareが安全性を真剣に考えるなら、ラバランプの使用はやめ、装飾とマーケティング用途にだけ残すべきである
- サーバーはそれぞれ自前で乱数を生成するほうが、より単純でより安全である
- Cloudflareがすでにそうしている可能性もある
1件のコメント
Lobste.rsの意見
この記事は誤解に基づいて書かれていて、しかも少し白ける内容に見える。現代の乱数生成は複数の独立したエントロピー源を使い、コンピュータの動作中もそれらをエントロピープールにハッシュして混ぜ込み続ける
コンピュータに単一の「乱数シード」があるわけではなく、実行中に
seed = hash(seed, new_data)のような形で複数ソースのエントロピーを使って継続的に再シードされる。ラバランプを撮影したカメラのデータを追加しても、システムのセキュリティが下がることは決してない。エントロピープールに入ったデータは、すでに入っている他のデータと一緒にハッシュされる。攻撃者の知らない情報がほんの少しでもあれば安全になるよう設計されているので、乱雑さの異なるデータを大量に混ぜてもセキュリティは損なわれないラバランプはシステムのセキュリティを損なわず、個人的にはシステムの一部を構成する楽しく機能的なアート作品だと思う。乱数の品質もごくわずかに向上させるし、乱数性とエントロピーの概念を視覚的に示してくれる
それはそうだが、カーネル乱数生成器はすでに30年以上にわたってさまざまなハードウェア由来の乱数性を使ってきたし、どれほど「継続的に」あるいは「絶えず」再シードされるかは誇張しないほうがよい
ハードウェアからの乱数性は継続的に収集されるが、Linuxの乱数生成器は周期的に再シードされる。起動後最初の1分間は数秒ごと、その後はおおむね1分に1回程度まで遅くなる
https://zx2c4.com/projects/linux-rng-5.17-5.18/…
既存システムがそうではないと言ったり示唆したりしている印象を、どこで与えたのかはわからない。ここではラバランプの部分を除けば既存システムを説明する意図はなく、実際に必要なのがどれほど少ないか、つまり 256ビットで足りるという点を強調したかった
ラバランプを撮影したカメラのデータを追加してもセキュリティが下がらないという話からは、攻撃面のことを連想する。組み込みコンピュータと、そのコンピュータとサーバーの間のネットワーク通信を追加することになる。私には、こうして追加される低いリスクのほうが、実際にラバランプが必要になるようなばかげたほど低いリスクより、ずっと大きく見える
哲学的な区別を別の言い方で表すとこうなる。あり得る結果はいくつあるか、そして結果はどれほど予測可能か、ということだ
暗号学的な目的では予測可能性は 2^-256 の水準に落ち着いているが、興味深いことに、あり得る結果の数がはるかに大きいありふれた過程も存在し、どれほど確率が低くても可能な結果をすべて出せることを望む場合がある。そういう状況では 暗号学的乱数性 では足りないかもしれない
標準的なトランプ1組には 52! 通りの並びがあり、これは約 2^226 なので、暗号学的にランダムなシードで全ての並びを生成できる。しかしUnoをしたり複数組のカードを一緒にシャッフルしたりすると、256ビット乱数生成器では全ての並びを作るのに十分な状態を持てない。システムのユーザー空間の乱数性がすべてカーネル由来で、カーネルがすべてのハードウェア乱数性を256ビットのCSPRNGに流し込むなら、Las Vegasでカードをシャッフルするには十分でないかもしれない :-)
この記事で抜けているのは 再シード で、これは高速鍵消去との相互作用や、初期シードを得ることの難しさを示す点で興味深い話題だ。記事はLinuxがCPUジッターしか使っていないかのように示唆しているが、それは単純化しすぎている。Linuxは多くの乱数源を使っており、ジッターのダンスは最後の手段としてしか使わない
現実世界では 2^128 個のサンプルですら決して得られない。実際にはそれよりずっと少なく、だからこそAES-128でも今なお多くの用途で十分安全なのだ。可能な結果の数が 2^256 より大きいときに「可能な結果をすべて実行する」ことは完全に 不可能 だ。忘れたほうがいい。そんなものは存在しない
ブラックジャックで1組ではなく6組のカードを使う場合でも、実際に求めているのは、すべての可能なシャッフルに対して確率を均等に分布させるシャッフル手順ではない。できるだけ多く標本を取っても違いを区別できないほど良い分布であれば十分だ。シャッフル数が 2^256、さらには 2^128 に制限されていても違いには気づかないだろう
記事から再シードを外したのは意図的だ。再シードが必要なのは、侵害の疑いがあるときや一部のセキュリティ更新のような特定の時点だけだ。乱数生成器の状態を不揮発性メモリに保持するより単純または安全であるなら、再起動時も同様だ。だから「再シード」と呼ぶより、新しい初期シードで再開すると考えるほうを好む
正常動作中の再シードはまったく不要だ。実装しても複雑さが増すだけだ
LinuxがCPUジッターしか使わないという示唆は確認しておくべきだった。私の理解では 起動時点 ではそれが唯一だった。特にユーザー入力やネットワーク入力が来る前はそうだと思っていた。ほかに知っているソースはある？ ハードウェア乱数生成器のサポートはすでにあるはずだが
できない。だがその点は脇に置いて、安全にやる方法はこうだ……
推測するに、乱数生成ハードウェアカードは、ビット密度だけでなく単位時間あたりのビット数でも測られる並列的な乱数源を得るために存在したのだろう
個々の主張で大きく同意できない部分はそれほど多くないが、全体の論旨はぼやけているように感じた。記事は「現代暗号が必要とする真の乱数性は、人々が思っているよりずっと少ない」という話を積み上げ、その後で「したがってラバランプは 攻撃面 を広げるのでより悪い」と結論づけている
どちらの主張も真ではあり得るが、結論へつながる流れは粗く感じられる
LavaRand は20年以上前にすでにこうしたことをやっていた。当時はかわいかったが、あの頃のカメラセンサーはずっと小さく、レンズなどの予測可能な特性のせいでエントロピー源としてはあまり良くなかった
ラバランプは好きだけど、何百個も並んだ壁の消費電力は、おもちゃのような装置にしてはかなり大きいと思う
自己宣伝に近い。ほとんどリンクを共有せず、共有するときは自分のリンクを載せる。直近5件の投稿のうち5件が自分の資料を指している
「著者がコミュニティに参加するのは良いことだが、製品発表や自分の仕事にトラフィックを誘導するための書きっぱなしの道具として悪用してはならない。経験則として、自己宣伝は自分のstoriesとcommentsの4分の1未満であるべきだ」
投稿15件にコメント1399件なら、明らかにコミュニティに参加している。自分の投稿ごとに自分で90件以上コメントしているのでなければ
Cloudflareはラバランプ由来のエントロピーを、University of Chileは地震データを、記憶が正しければEPFLは 放射性崩壊 の測定値を、そして他の多くの参加者はさまざまなデータをdrandネットワークの最初の鍵生成式に提供した
CSPRNGを使えただろうか？ もちろんだ。だが、そうしたら面白さがないではないか？