algorithm - 疑似ランダムに選択された IP アドレスへの ping を使用して、真の乱数を生成できますか?

Question

提起された質問は、決定論的な計算デバイスで数値を生成することの不可能性について議論しているときに、2年目のコンプサイエンスの講義中に出てきました.

これは、非コモディティクラスのハードウェアに依存しない唯一の提案でした。

その後、誰も彼らの評判を賭けて、それに賛成または反対する決定的な議論をすることはありませんでした.

誰でも賛成または反対の立場を表明したいと考えています。もしそうなら、可能な実装についての言及はどうですか?

score 83 · Accepted Answer

いいえ。

ネットワーク上の悪意のあるマシンは、ARPスプーフィング（または他の多くの手法）を使用してpingを傍受し、一定期間後に応答する可能性があります。そうすれば、彼らはあなたの乱数が何であるかを知るだけでなく、それらを制御するでしょう。

もちろん、ローカルネットワークがどれほど決定論的であるかという問題はまだあるので、実際のすべてのことほど簡単ではないかもしれません。ただし、インターネット上でランダムなIPにpingを実行してもメリットがないため、イーサネットトラフィックからエントロピーを引き出すこともできます。

マシンに接続されたデバイスからエントロピーを引き出すことはよく研究された原則であり、さまざまな種類のデバイスと測定方法の長所と短所は、たとえば/ dev/randomの実装から盗まれる可能性があります。

[編集：一般原則として、セキュリティの基礎で作業する場合（そして、大量の真にランダムなデータの実際的なニーズはセキュリティ関連のみです）、非常にリソースが豊富で、断固とした攻撃者がすべてを行うと想定する必要がありますシステムを破壊する力。

実用的なセキュリティについては、誰もあなたのPGPキーをそれほどひどく望んでいないと想定し、セキュリティとコストのトレードオフを受け入れることができます。しかし、アルゴリズムや手法を発明するときは、彼らが直面する可能性のある最強のセキュリティ保証を提供する必要があります。誰かが、どこかで、誰かの秘密鍵をひどく欲しがって、あなたの提案を打ち負かすためにこのキットを作成するのに十分であると私は信じることができるので、現在のベストプラクティスを超える進歩としてそれを受け入れることはできません。AFAIK / dev / randomは、安価な家庭用PCで真にランダムなデータを生成するためのベストプラクティスにかなり近いものです]

[別の編集：コメントで、（1）物理プロセスが影響を受ける可能性があることはすべてのTRNGに当てはまり、（2）セキュリティ上の懸念はとにかくここには当てはまらないことを示唆しています。

（1）の答えは、実際のハードウェアでは、pingの応答時間よりもはるかに優れており、より多くのエントロピーをより速く収集できるため、この提案は解決策ではないということです。CSの用語では、決定論的マシンで乱数を生成できないことは明らかです。これが問題を引き起こしました。しかし、CSの用語では、外部入力ストリームを持つマシンは定義上非決定論的であるため、pingについて話している場合は、決定論的マシンについて話しているのではありません。したがって、実際のマシンが持つ実際の入力を見て、それらをランダム性のソースと見なすのは理にかなっています。お使いのマシンに関係なく、利用可能なソースのリストで生のping時間は長くないため、優れたソースがどれほど優れているかを心配する前に、それらを除外することができます。

（2）の答えは哲学的です。偶然ではなく気まぐれに選択できるという性質を持つ乱数を気にしないのであれば、この提案は問題ありません。しかし、それは私が「ランダム」という用語で理解していることではありません。何かに一貫性がないからといって、それが必ずしもランダムであるとは限りません。

最後に、要求に応じて提案の実装の詳細に対処します。ping時間をランダムに受け入れると仮定すると、未処理のping時間をRNG出力として使用することはできません。あなたはそれらの確率分布を知りません、そしてそれらは確かに均一に分布されていません（これは通常人々がRNGに望むものです）。

したがって、pingごとに信頼できるエントロピーのビット数を決定する必要があります。エントロピーは、確率変数の正確に定義された数学的特性であり、実際の「ランダム」の尺度と合理的に見なすことができます。実際には、満足している下限が見つかります。次に、いくつかの入力をハッシュし、それを入力の依存エントロピーの合計以下の出力のビット数に変換します。「合計」は必ずしも合計を意味するわけではありません。入力が統計的に独立している場合は合計ですが、pingの場合はそうではないため、エントロピー推定の一部は相関を考慮することになります。このハッシュ操作の洗練された姉は「エントロピーコレクター」と呼ばれ、すべての優れたOSに1つあります。

ただし、データを使用してPRNGをシードし、PRNGが任意の大きなシード入力を使用できる場合は、ハッシュする必要はありません。シード値がどの程度「ランダム」であるかを知りたい場合は、エントロピーを推定する必要があります。世界で最高のPRNGを使用できますが、そのエントロピーはシードのエントロピーによって制限されます。]

score 27 · Accepted Answer

27

乱数は、偶然に任せるにはあまりにも重要です。

または外部の影響/操作。

于 2008-09-26T02:49:22.750 に答える

score 22 · Accepted Answer

短い答え

pingタイミングデータを単独で使用することは、真にランダムではありませんが、エントロピーのソースとして使用でき、真にランダムなデータを生成するために使用できます。

長いバージョン

ping時間はどのくらいランダムですか？

それ自体では、ネットワーク操作（pingなど）からのタイミングデータは均一に分散されません。（そして、ランダムなホストを選択するという考えは実用的ではありません-多くはまったく応答しません、そしてホスト間の違いは応答時間の範囲の間にギャップがあり、巨大になる可能性があります-衛星接続を考えてください）。

ただし、タイミングは適切に分散されませんが、データにはある程度のランダム性があります。言い換えれば、あるレベルの情報エントロピーが存在します。タイミングデータを乱数ジェネレーターにフィードしてシードすることをお勧めします。では、どのレベルのエントロピーが存在するのでしょうか？

たとえば約50ミリ秒のネットワークタイミングデータの場合、0.1ミリ秒単位で測定され、値の広がりは2ミリ秒で、約20個の値があります。最も近い2の累乗（16 = 2 ^ 4）に切り捨てると、タイミング値ごとに4ビットのエントロピーが得られます。あらゆる種類の安全なアプリケーション（暗号化キーの生成など）の場合、私は控えめに言って、読み取りごとに2ビットまたは3ビットのエントロピーしかなかったと言います。 （ここでは非常に大まかな見積もりを行い、攻撃の可能性を無視していることに注意してください）。

真にランダムなデータを生成する方法

真の乱数の場合、エントロピーを収集し、データストア内に分散する/ dev / randomの線に沿って設計されたものにデータを送信する必要があります（ある種のハッシュ関数、通常は安全な関数を使用）。同時に、エントロピー推定が増加します。したがって、128ビットのAESキーの場合、エントロピープールに十分なエントロピーが得られるまでに64回のpingタイミングが必要になります。

さらに堅牢にするために、キーボードとマウスの使用状況、ハードディスクの応答時間、マザーボードのセンサーデータ（温度など）などからタイミングデータを追加できます。これにより、エントロピー収集の速度が上がり、攻撃者がすべてを監視するのが難しくなります。エントロピーのソース。そして確かに、これは現代のシステムで行われていることです。MS Windowsエントロピーソースの完全なリストは、この投稿の2番目のコメントにリストされています。

もっと読む

乱数ジェネレーターに対する（コンピューターのセキュリティ）攻撃、および暗号的に安全な乱数ジェネレーターの設計については、ブルース・シュナイアーとジョン・ケルシーによるヤロウの論文を読むよりも悪いことをする可能性があります。（YarrowはBSDおよびMac OS Xシステムで使用されます）。

score 13 · Accepted Answer

いいえ。

ネットワークケーブル (または/etc/init.d/networking stop) を抜くと、エントロピーは基本的にゼロに低下します。

ping を実行しているマシンでサービス拒否攻撃を実行すると、予測可能な結果 (ping タイムアウト値) も得られます。

score 10 · Accepted Answer

私が見たコモディティハードウェアのランダム性の最良の原因は、ウェブカメラからフィルターなどを取り外し、レンズに不透明な接着剤を塗布し、CCDに当たる宇宙線から個々の白いピクセルを簡単に検出できた男でした。これらは可能な限り完全にランダムに近く、量子効果によって外部スヌーピングから保護されています。

score 10 · Accepted Answer

できると思います。注意すべき点がいくつかあります。

ランダムな IP アドレスに ping を実行した場合でも、最初の数ホップ (ユーザーから ISP ネットワーク内の最初の実際の L3 ルーターまで) は、すべてのパケットで同じになります。これにより、最初の Point of Presence のデータセンターで何かに ping を実行したとしても、往復時間の下限が設定されます。そのため、タイミングの正規化には注意する必要があります。往復には下限があります。
また、ネットワーク内のトラフィックシェーピングにも注意する必要があります。ルーターでの典型的なリーキーバケットの実装では、M マイクロ秒ごとに N バイトが解放されます。これにより、連続した時間範囲ではなく、特定のタイムスロットでタイミングが効果的に乱れます。そのため、タイムスタンプの下位ビットを破棄する必要がある場合があります。

しかし、コモディティハードウェアには適切なエントロピーのソースがないという前提には同意しません。ここ数年の多くの x86 チップセットには、乱数ジェネレーターが含まれています。私がよく知っているものは、比較的感度の高い ADC を使用して、ダイの 2 つの異なる場所で温度を測定し、それらを減算します。この温度差の下位ビットは、（カイ二乗分析によって）非常にランダムであることを示すことができます。システムの処理負荷が増加すると、全体的な温度が上昇しますが、ダイの 2 つの領域間の温度差は相関せず、予測不可能なままです。

score 2 · Accepted Answer

コモディティハードウェアが必要な場合は、サウンドカードで十分です。アナログ入力の音量を上げるだけで、安価なホワイトノイズソースが得られます。ネットワークを必要としない安価なランダム性。

score 2 · Accepted Answer

優れた乱数ジェネレーターの一部は、n -> 無限大としてすべての数値の確率が等しいことです。

したがって、ランダムなバイトを生成する予定がある場合は、適切な rng から十分なデータがあれば、各バイトが返される可能性が等しくなるはずです。さらに、返される特定の数値のパターンまたは予測可能性 (特定の期間中の確率のスパイク) があってはなりません。

確率変数を取得するために何を測定するのか ping を使用してもよくわかりません。それは応答時間ですか? その場合、一部の応答時間または応答時間の範囲が他の応答時間よりも頻繁になり、安全でない乱数ジェネレーターになる可能性があることを確信できます。

score 1 · Accepted Answer

数学的な計算でランダムな結果を生成することはできませんが、「現実の世界」では、コンピューターは正確に数字を処理するだけではありません...少しの創造性があれば、既知の方法がないようなランダムな結果を生成できるはずです。正確な結果を再現または予測する。

私が見た実装が最も簡単で、すべてのシステムで普遍的に機能するアイデアの 1 つは、コンピューターのサウンドカードライン入力/マイクポートから静的を使用することです。

その他のアイデアには、熱ノイズとキャッシュラインの低レベルタイミングが含まれます。TPM チップを搭載した最新の PC の多くには、暗号化品質のハードウェア乱数ジェネレーターが既に搭載されています。

ping に対する私のお決まりの反応 (特に ICMP を使用している場合) は、あなたの不正行為が露骨すぎるということです。その時点で、ギガーカウンターを作成し、ランダムソースとして背景放射を使用することもできます。

score 1 · Accepted Answer

大気ノイズを使用するほどではありませんが、ランダムで再現性のない動作で悪名高いネットワークの特性に依存するため、それでも真にランダムです。

ランダム性の詳細については、 Random.orgを参照してください。

実装の試みは次のとおりです。

@ips  : list = getIpAddresses();
@rnd         = PseudorandomNumberGenerator(0 to (ips.count - 1));

@getTrueRandomNumber() { ping(ips[rnd.nextNumber()]).averageTime }

score 1 · Accepted Answer

何かを測定してランダムなシードを生成するアプローチは、かなり優れているようです。O'Reilly の著書『Practical Unix and Internet Security 』には、ユーザーにいくつかのキーストロークを入力してからキーストローク間の時間を測定するなど、ランダムシードを決定する同様の追加の方法がいくつか記載されています。(この本は、この手法がランダム性のソースとして PGP で使用されていることを示しています。)

システムの CPU の現在の温度(小数点以下の桁数まで測定) が、ランダムシードの実行可能なコンポーネントであるかどうか疑問に思います。このアプローチには、ネットワークにアクセスする必要がないという利点があります (そのため、ネットワーク接続がダウンしてもランダムジェネレーターが使用できなくなります)。

ただし、CPU の内部センサーが CPU 温度を十分な小数点以下の桁数まで正確に測定して、その値を乱数シードとして実際に使用できるようにすることはおそらくありません。少なくとも、質問で述べたように、「コモディティクラスのハードウェア」ではありません。

score 1 · Accepted Answer

YouTube は動作中のデバイスを示しています: http://www.youtube.com/watch?v=7n8LNxGbZbs

ランダムは、誰も次の状態を予測できない場合です。

score 1 · Accepted Answer

はい、可能ですが... 悪魔は細部に宿ります。

32 ビット整数を生成する場合は、32 ビットを超えるエントロピーを収集する必要があります (そして、十分な混合関数を使用してそのエントロピーを分散させますが、それは既知で実行可能です)。大きな問題は次のとおりです。

ping 時間のエントロピーはどれくらいですか?

この質問に対する答えは、ネットワークと攻撃モデルに関するあらゆる種類の仮定に依存し、状況によって異なる答えがあります。

攻撃者が ping 時間を完全に制御できる場合、ping ごとに得られるエントロピーは 0 ビットであり、どれだけ混合しても合計で 32 ビットのエントロピーになることはありません。それらが ping 時間を完全に制御できない場合、ある程度のエントロピーが得られ、(収集しているエントロピーの量を過大評価しない場合) 完全にランダムな 32 ビット数値が得られます。

score 0 · Accepted Answer

ここに私の提案があります：

1-あなたの場所からできるだけ遠くにあるウェブサイトのパンチを選択してください。たとえば、米国にいる場合は、マレーシア、中国、ロシア、インドなどにサーバーIPがあるいくつかのWebサイトを試してください。トラフィックの多いサーバーの方が優れています。

2-あなたの国のインターネットトラフィックが多い時間帯（私の国では午後7時から11時のようです）に、これらのWebサイトに何度もpingを実行し、各ping結果（整数値のみを使用）を取得して、そのモジュラス2を計算します（つまり、各ping操作から、1ビット（0または1）を取得します。

3-プロセスを数日間繰り返し、結果を記録します。

4-すべてのpingから取得したすべてのビットを収集し（おそらく数十万ビットを取得します）、それらからビットを選択します。（多分あなたは上記と同じ方法からのいくつかのデータを使ってあなたのビットを選びたいでしょう:)）

注意してください：あなたのコードでは、タイムアウトをチェックする必要があります..etc

score 0 · Accepted Answer

真のランダム性は非効率的であるように私には思えます。シーケンスがランダムであるかどうかを知る方法はありません。定義上、どんなにありそうもないものでも何でも含めることができるからです。特定の分布パターンを保証すると、ランダム性が減少します。「パターン」という言葉はちょっとしたプレゼントです。

    I MADE U A RANDOM NUMBER
           BUT I EATED IT

score 0 · Accepted Answer

tracerouteで乱数を作成するコードを入手しました。pingを使用してそれを行うプログラムもあります。私は1年以上前にクラスプロジェクトのためにそれをしました。それが行うのは、tracerouteをアドレスで実行することだけであり、ms回の最小のsig桁を取ります。乱数を取得するのに非常にうまく機能しますが、真の乱数にどれだけ近いかは本当にわかりません。

これは私がそれを実行したときに私が得た8つの数字のリストです。

455298558263758292242406192

506117668905625112192115962

805206848215780261837105742

095116658289968138760389050

465024754117025737211084163

995116659108459780006127281

814216734206691405380713492

124216749135482109975241865

#include <iostream>
#include <string>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <vector>
#include <fstream>

using namespace std;

int main()
{
system("traceroute -w 5 www.google.com >> trace.txt");

string fname = "trace.txt";
ifstream in;
string temp;

vector<string> tracer;
vector<string> numbers;

in.open(fname.c_str());
while(in>>temp)
tracer.push_back(temp);

system("rm trace.txt");

unsigned index = 0;

string a = "ms";
while(index<tracer.size())
{
if(tracer[index]== a)
numbers.push_back(tracer[index-1]);
++index;
}


std::string rand;

for(unsigned i = 0 ; i < numbers.size() ; ++i)
{
std::string temp = numbers[i];
int index = temp.size();
rand += temp[index - 1];
}

cout<<rand<<endl;

return 0;

}

score 0 · Accepted Answer

ええと、この種の質問は、「本当にランダム」の意味についての議論にすぐにつながることがわかりました.

pingを測定すると、まともな品質のランダムビットが生成されると思いますが、十分な速度で使用するには不十分です（深刻なDDOSを実行する場合を除きます）.

そして、コンピューターのアナログ/機械的特性、またはそれを操作するミートバッグの動作を測定するよりもランダムであるとは思いません.

(編集) 実際問題として、このアプローチでは、ネットワーク上の誰かが「乱数」ジェネレーターを操作する可能性が生じます。

score 0 · Accepted Answer

賛成か反対かは断言できませんが、この実装には問題があります。

これらの IP アドレスはどこから来ているのか、ランダムに選択されている場合、応答しない場合や応答が遅い場合はどうなりますか?それは、乱数の表示が遅くなることを意味しますか?

また、100.000 件の結果の視覚的なグラフを作成し、数値間に相関関係がない、またはほとんどないことを計算したとしても、それが本当にランダムであることを意味するわけではありません。ディルバートが説明したように:)

score 0 · Accepted Answer

ランダム性の良いソースとは思えません。

どのメトリックを使用しますか? 明らかなメトリックは応答時間ですが、合理的に期待できる値の範囲は小さく、数十ミリ秒から数千ミリ秒です。応答時間自体は鐘型曲線に従い、任意の間隔でランダムに分散されるわけではありません (間隔をどのように選択しますか?) ため、数値からいくつかの「ランダムな」ビットを試して選択する必要があります。

LSB はランダムなビットストリームを提供する可能性がありますが、クロックの粒度の問題を考慮する必要があります。おそらく、システムによっては、割り込みがどのように機能するかにより、常に 2 ミリ秒の倍数になることがあります。

おそらく、ランダムなビットを取得するもっと優れた「興味深い」方法があります。おそらく、ランダムな単語をグーグルで検索し、最初のページを取得して、ページからN番目のビットを選択します。

score 0 · Accepted Answer

ランダム性はバイナリプロパティではありません。ストリーム内の次の値を予測することがどれほど難しいかを表す 0 と 1 の間の値です。

「値をpingに基づいた場合、値はどの程度ランダムになるか?」と尋ねます。実際に「pingはどのくらいランダムですか？」と尋ねています。十分な量のデータセット (たとえば 100 万 ping) を収集し、それらの分布曲線と動作を時間でマッピングすることによって、それを見積もることができます。分布が平坦で動作の予測が難しい場合、データはよりランダムに見えます。でこぼこした分布または予測可能な動作は、ランダム性が低いことを示しています。

サンプルの解像度も考慮する必要があります。結果が何らかの方法でミリ秒単位に丸められることを想像できたので、ping を使用すると、0 から 500 までの整数値を持つことができます。これは多くの解像度ではありません。

実用的な面では、ping は予測および操作される可能性があり、ランダム性がさらに低下するため、お勧めしません。

一般に、ランダムネスジェネレーター、暗号化方法、およびハッシュアルゴリズムを「独自に作成する」ことはお勧めしません。楽しいように見えますが、ほとんどの場合、非常に威圧的な数学がたくさんあります。

本当に優れたエントロピージェネレーターを構築する方法については、おそらく、原子またはサブアトミックレベルでの何らかの相互作用の結果を出力する密閉されたボックスである必要があると思います。つまり、敵も簡単に読み取れるエントロピーのソースを使用している場合、敵はあなたのアルゴリズムを見つけるだけで済みます。あらゆる形式の接続が攻撃ベクトルになる可能性があるため、エントロピーのソースを、それを消費するサービスのできるだけ近くに配置する必要があります。

score 0 · Accepted Answer

簡単に言えば、ネットワークは所定のルールに従うため、結果はランダムではありません。

ウェブカメラのアイデアは (少し) 合理的に聞こえます。Linux の人々は、マイクが接続されていないサウンドカードからのランダムノイズを単純に使用することを推奨することがよくあります。

algorithm - 疑似ランダムに選択された IP アドレスへの ping を使用して、真の乱数を生成できますか?

23 に答える 23

短い答え

長いバージョン

ping時間はどのくらいランダムですか？

真にランダムなデータを生成する方法

もっと読む

Related

Reference