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

https://stackoverflow.com/questions/137340

02-07-2019
|

質問

提起された問題は、2年目のComp Science講義で決定論的計算デバイスで数値を生成することの不可能性について議論したときに発生しました。

これは、商品クラス以外のハードウェアに依存しない唯一の提案でした。

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

賛成または反対の立場をとる人は誰でもかまいません。もしそうなら、可能な実装についての言及はどうですか？

解決

いいえ。

ネットワーク上の悪意のあるマシンは、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ごとに依存するエントロピーのビット数を決定する必要があります。エントロピーは、ランダム変数の正確に定義された数学的特性であり、実際に「ランダム」であるかどうかの尺度と合理的に考えることができます。実際には、満足している下限を見つけます。次に、いくつかの入力をハッシュし、それを依存する合計en以下の出力のビット数に変換します。

他のヒント

ランダムな数字はあまりにも重要なので、偶然に任せることはできません。

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

簡単な回答

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

より長いバージョン

ping時間はランダムですか？

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

ただし、タイミングは十分に分散されませんが、データにはある程度のランダム性があります。別の言い方をすれば、情報エントロピーのレベルが存在します。タイミングデータを乱数ジェネレータに入力してシードするのは良い考えです。では、どのレベルのエントロピーが存在しますか？

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

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

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

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

その他の読み物

乱数発生器への（コンピューターセキュリティ）攻撃の議論、および暗号的に安全な乱数発生器の設計については、 yarrow paper Bruce Schneier ジョン・ケルシー。（YarrowはBSDおよびMac OS Xシステムで使用されます。）

いいえ。

ネットワークケーブルを抜く（または /etc/init.d/networking stop ）と、エントロピーは基本的にゼロになります。

pingを実行しているマシンでDoS攻撃を実行すると、予測可能な結果（ping-timeout値）が得られます

できると思います。次の点に注意してください。

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

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

私が見た商品ハードウェアのランダム性の最良のソースは、ウェブカメラからフィルターまたは何かを削除し、レンズに不透明な接着剤を塗り、宇宙線の衝突から個々の白いピクセルを簡単に検出できる人でしたCCD。これらは可能な限り完全にランダムに近く、量子効果によって外部のby索から保護されています。

優れた乱数ジェネレーターの一部は、n-＆gt;のようにすべての数値の等しい確率です。無限大。

したがって、ランダムバイトを生成することを計画している場合、適切なrngから十分なデータがあれば、各バイトは同じ確率で返されるはずです。さらに、返される特定の数字のパターンまたは予測（特定の期間中の確率の急上昇）がないようにする必要があります。

pingを使用して、ランダム変数を取得するために測定するものがあまりよくわかりません。応答時間ですか？その場合、一部の応答時間または応答時間の範囲が他の応答時間よりも頻繁に発生するため、安全でない可能性のある乱数ジェネレーターが作成される可能性が十分にあります。

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

ランダムなシードを生成するための何かを測定するアプローチは、かなり良い方法のようです。 O'Reillyの本実用的なUnixおよびインターネットセキュリティは、ユーザーにいくつかのキーストロークを入力してから、キーストローク間の時間を測定するなど、ランダムシードを決定するいくつかの同様の追加の方法。（本は、この手法がPGPによってランダム性のソースとして使用されていることに注意しています。）

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

ただし、CPUの内部センサーがCPU温度を十分な小数位まで正確に測定して、乱数シードとして値を実際に実行できる可能性は低いでしょう。少なくとも、「コモディティクラスのハードウェア」ではありません。質問で述べたように！

大気ノイズを使用するほど良くはありませんが、ランダムで繰り返し不可能な動作で悪名高いネットワークの特性に依存するため、本当にランダムです。

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

ここに実装の試みがあります：

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

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

ISAAC のようなものを、ラウンドトリップを信頼する前に、より強力なPRNGとして使用したいエントロピーとしてのping。他の人が言ったように、誰かがあなたの番号を推測するだけでなく、おそらくそれらをさまざまな程度に制御するのは簡単すぎるでしょう。

他の偉大なエントロピーのソースが存在します。言及されていないもの（実用的ではないかもしれません）は、オンボードオーディオデバイスからのサンプリングノイズです。これは、マイクが接続されていない場合でも、通常は少しうるさくなります。

私が書いていたクライアント/サーバーRPCメカニズムのための強力な（そして高速な）PRNGを考え出そうと9ラウンドを行った。両側に32文字の暗号の1024行で構成される同一のキーがありました。クライアントはAUTH xxを送信し、サーバーはAUTH yy ..を返します。そして、両側は、ふぐの秘密（+ salt）を生成するために使用するキーの2行を知っていました。その後、サーバーはキー全体（暗号化された）のSHA-256ダイジェストを送信し、クライアントは正しいキーを持っている何かと通信していることを知っていました。ええ、真ん中の人に対する保護は非常に弱いですが、デバイスがどのように使用されているかについては公開鍵は問題外です。

つまり、最大256の接続を処理する必要のあるノンブロッキングサーバーがありました。PRNGは強力であるだけでなく、高速である必要がありました。クライアントでエントロピーを収集するためにより遅い方法を使用することはそれほど困難ではありませんでしたが、サーバーでそれを提供することはできませんでした。

だから、あなたのアイデアについて尋ねなければならない..それはどれほど実用的でしょうか？

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

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

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

ping（ICMPを使用している場合はesp）に対する私の大嫌いな反応は、あなたの不正行為が遅すぎることです。その時点で、ギガーカウンターを作成し、ランダムソースとしてバックグラウンド放射線を使用することもできます。

はい、それは可能ですが、...詳細は悪魔です。

32ビット整数を生成する場合、＆gt; 32ビットのエントロピーを収集する必要があります（そして、そのエントロピーが周囲に広がるのに十分な混合関数を使用しますが、それは既知で実行可能です）。大きな質問：

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

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

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

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

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

絶対に賛成または反対のサイトはできませんが、この実装には問題があります。

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

また、100.000の結果の視覚的なグラフを作成し、数値間に相関がないか、またはほとんどないと計算しても、それが本当にランダムであることを意味しません。 dilbert で説明されているように：）

ランダム性の良いソースとして私を打つことはありません。

使用するメトリック-明らかなものは応答時間ですが、合理的に期待できる値の範囲はわずかです：数十ミリ秒から数千です。応答時間自体はベル曲線をたどり、どの間隔でもランダムに分散されないため（間隔をどのように選択しますか？）、数からいくつかの「ランダム」ビットを選択する必要があります。

LSBはランダムなビットストリームを提供する可能性がありますが、クロックの粒度の問題を考慮する必要があります-割り込みの動作方法により、一部のシステムでは常に2msの倍数になります。

ランダムビットを取得するための「面白い」方法がおそらくはるかにあります-ランダムな単語をグーグルで検索し、最初のページを取得して、ページからN番目のビットを選択します。

ええ、この種の質問は「真にランダム」の意味についての議論に非常に迅速につながることがわかりました。

pingを測定すると、適切な品質のランダムビットが得られると思いますが、十分なレートではあまり役に立ちません（深刻なDDOSを実行する意思がない限り）。

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

（編集）実際には、このアプローチにより、ネットワーク上の誰かが「乱数」ジェネレータを操作する可能性が開かれます。

真のランダム性は言い表せないように思えます-シーケンスがランダムであるかどうかを知る方法はありません。特定の分布パターンを保証すると、ランダム性が減少します。「パターン」という言葉ちょっとしたプレゼントです。

    I MADE U A RANDOM NUMBER
           BUT I EATED IT

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

「pingを基にした場合、値がどの程度ランダムになる可能性がありますか？」実際に「pingはどの程度ランダムですか？」これは、十分な量のデータセット（たとえば1 mln ping）を収集し、それらの分布曲線と動作を時間内にマッピングすることで推定できます。分布が平坦で、動作を予測するのが難しい場合、データはよりランダムに見えます。凹凸の多い分布または予測可能な動作は、ランダム性の低下を示唆しています。

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

実用的な面では、pingを予測および操作でき、ランダム性がさらに低下するため、これに反対することをお勧めします。

一般的に、「独自のローリング」に反対することをお勧めします。ランダムネスジェネレーター、暗号化方法、ハッシュアルゴリズム。楽しいように思えますが、ほとんどが非常に威圧的な数学です。

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

XKCDメソッドを使用できます：

ランダム番号ジェネレーター

tracerouteで乱数を作成するコードを入手しました。 pingを使用してそれを行うプログラムもあります。私はクラスプロジェクトのために一年以上前にそれをやった。 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;

}

非常に簡単に言えば、ネットワークは規定の規則に従っているため、結果はランダムではありません。

ウェブカムのアイデアは（少し）合理的です。 Linuxの人々は、マイクが接続されていないサウンドカードからのランダムノイズを単に使用することをお勧めします。

私の提案：

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

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

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

4-すべてのpingから取得したすべてのビットを収集し（おそらく数十万ビットを取得します）、それらからビットを選択します。（おそらく、上記と同じ方法のデータを使用してビットを選択したいかもしれません:)）

注意：コード内でタイムアウトを確認する必要があります..etc

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow