SilentC で作った乱数生成プログラム：新適当マイコン電子工作研究所：So-netブログ

	ブログをはじめるログイン

SilentC で作った乱数生成プログラム　[ColdFire V2] [編集]

main(){
  long seed=0x5180009F;
  long i;
  for (i=0;i<20;i++){
    seed+=102;
    seed = ((seed << 8) ^ 0x31415926) + 0x65358979;
    if (seed < 0) seed = ~seed;
    PrHex(seed); PrStr("\r\n");
  }
}

102は、魔法の数字です。

OK
run
1675e59f
56231a60
7791289f
059de59f
11dce59f
52dce59f
52dce59f
52dce59f
52dce59f
52dce59f
52dce59f
52dce59f
52dce59f
52dce59f
52dce59f
52dce59f
52dce59f
52dce59f
52dce59f
52dce59f
OK

あれっ？

2008-10-07 14:15 nice!(0) コメント(9) トラックバック(0)

nice! 0

おお不思議だ！、まるで魔法みたい。なんでこんな結果になるんだろう。
試しにやったbcc32でも同じ結果でした。
と言うかこれ、本当に乱数を生成するプログラムなのですか？。

あと、シーケンス番号は乱数で生成するものではないっす。
by hamayan (2008-10-07 21:49)

わー、すごいー
前回のシーケンス番号と完全に一致してますね。弱い乱数生成器ってことなのでしょうか。それにしても、よく見つけられましたね。

by Sim (2008-10-08 00:58)

はじめました。
いつも楽しく読ませていただいています。
今回の記事は、全く予備知識がありませんが、
前回の記事の（不可解な）分析結果の原因の推測なのでしょうか。
by ぼのぐらし (2008-10-08 08:36)

ぼのぐらしさん、はじめまして。

表向きは「『たまたま』前回と同じ数列が出る乱数生成器」としておいてください。ゴニョゴニョ…

評価解析結果については、逐一、サイレント・システムさんと連絡をとりあっております。

さて、私が読んだ「ウワサ」では、シーケンス番号（の初期値）に乱数が必要である事ついて、

1) コネクション間でシーケンス番号が衝突することによる混乱を避ける。
2) シーケンス番号が予測されることによるハッキングを防ぐ。
3) 乱数にすることが推奨されている。

という理由が挙げられていました。1) は、今回のぜひとも避けたいケースですが、2) は、そこまで必要かということになると思います。

by noritan (2008-10-08 09:24)

> 3) 乱数にすることが推奨されている。

TCPの実装が、RFC793から変わったのですね。

by hamayan (2008-10-08 11:04)

しかし乱数の種が固定では、、、。
このページに対応策が書いて有ります。
http://www.ipa.go.jp/security/rfc/RFC1948JA.html
ISN = M + F(localhost, localport, remotehost, remoteport)
つまり内部タイマーによるシーケンシャルな番号と、ソケットペアによるランダムな番号を加算すると。

単純に乱数を使っただけでは、1)は確立が低いだけで避けられないでしょう。
しかし上のページの方法ならば、1)を避ける事はできそうですね。

by hamayan (2008-10-08 11:18)

1) を避けるなら、RFC793に書かれていた4マイクロ秒ごとに更新されるカウンタを使うだけでも十分だと思います。ただ、このためにタイマを一個使うのはもったいないとは思います。

もし、なりすましクライアントがColdFireに接続するのを避けるために RFC1948 の方法で初期値を生成すれば、ハッシュ関数 F が知られない限り、次のシーケンス番号を予測することは出来ないはずです。ところが、ハッシュ関数は、ColdFireにハードコーディングされるので、誰でも入手可能です。ColdFire基板に固有の種が必要ですね。

ちなみに、「内部タイマー」が魔法の数字「102」でした。この番号生成器は、ある周期でデータを送受信すると周期1の擬似乱数を発生します。「内部タイマ」に絶対値ではなく相対値を使っていたところがこの場合の問題点ではあります。

http://tools.ietf.org/html/rfc793
http://tools.ietf.org/html/rfc1948

by noritan (2008-10-08 13:47)

> このためにタイマを一個

NavajoではRFC793での実装を行っている為に、タイマー値を初期値に使っています。もちろん開発途中からTCPの問題点として成りすましは知っていましたが、基本的にWAN環境ではなくLAN環境で使う事を想定していたので、そこまでの実装は行っていません。LANで成りすましとか、、、「ネットワーク管理者は何をやっている！」と言う事ですね。

でタイマーなのですが、4μsで一つの更新頻度でシーケンス番号を進めた場合でも、循環するのに4時間半掛かるから、MSL時間に対してこれで十分と言う理由でなっている数字であり、きっちり4μsでやる必要は無いでしょう。

ITRONでは1ms周期のシステムタイマーの実装を推奨しているので、Navajoではシステムタイマーの値に256を掛けて、つまり8bitシフトして使っています。特別なタイマーは用意していません。

by hamayan (2008-10-08 15:06)

なるほど、なるほど。

SilentC (SilentMoon) の場合、常時動作しているのは、10m秒ごとに満期になる PIT0 タイマだけです。

PIT0カウンタは、1.0677マイクロ秒ごとにインクリメントされ、0x249Fで割り込みがかかり、カウンタはリセットされます。ここから、32ビットのフリーランニングカウンタを作るには、PIT割り込みで動作するソフトウェア・カウンタ（システム・タイマ）とPITのカウンタ値を組み合わせれば実現できそうですね。提案しておこう。

PIT0の調査結果は、こちら。
http://noritan-micon.blog.so-net.ne.jp/2008-08-25-2

by noritan (2008-10-08 15:46)