読者です 読者をやめる 読者になる 読者になる

なるようになるかも

力は多くの場合、その人の思いを超えない。

擬似乱数というかarc4random()の話。

擬似乱数と言えば、かのカルドセプトサーガの悲劇が有名です。

ダイスの出目が必ず奇数と偶数の繰り返しになるという、地味ながらゲームバランスの根幹を破壊するバグが話題となりました。しかしその話題から得るべき教訓は、

その論調は一様に、サイコロすらまともに作れないなんて馬鹿すぎる、担当プログラマが低脳すぎて笑える、といったような物だった。やがてそのような書き込みの中に、Cコードを示して「サイコロなんかたったこれだけで作れるのに」と発言する者が何人か現れた。そしてこれが最も重要な点だが、そのようにして示されたコードは、なぜか全部カルドセプトサーガのプログラマが犯したのと同じミスを犯していた。

真の低脳は意外なところに潜む - うさだBlog

擬似乱数の特性について、正確に把握しているプログラマはあまりにも少ない、という事実だと思います。

とあるiOSの入門書では、arc4random()の呼び出しにsrand()が必要かのような記述が放置されていました。

その本はiOSのバージョンが上がる度に追従して改訂している本だったため、いつこの記述が修正されるのか毎年楽しみにしていたのですが、結局サンプルコードがSwiftに書き直されるまでの3~4年、間違った記述のまま直されることはありませんでした…。

乱数の種類と特性

良い乱数・悪い乱数を読めば終わる話なので深入りはしません。

真性乱数

現実世界でサイコロを振った場合の出目は、本当の意味のランダムなので、計算機が作り出す乱数と比較して、真性乱数と呼ばれたりします。

高度なセキュリティを要求されるケースでは、真性乱数を生成するために専用のハードウェアが用いられることがあります。

擬似乱数

計算機が算出するものは「次の値が予測可能である」という点において乱数とは言えないので、擬似乱数と区別して呼ばれます。

Cの標準ライブラリであるrand()が生成する乱数列は、ほとんどが線形合同法を利用した低い品質のものであることが多いのです。これはC99標準が乱数の強度に関する規定を行っていないこと、また線形合同法があらゆるハードウェアで高速で動作する実装であることなどが理由かと思われます。

計算機による擬似乱数は、再現性のある乱数列を生み出せるという特徴を持ちます。これは一見すると欠点のように思えますが、特定のシードを与えることでゲームの難易度を調整できたり、シードとユーザーの入力を記録するだけでリプレイデータを作れるなど、うまく使えば利点にもなります。

ただし質の悪い線形合同法によるrand()の実装では、下位1ビットが同じものが出続けるか、0と1の繰り返しになることがあります。ゲームでの乱数として用いる場合、下位ビットを切り捨てて使うのが当たり前でした。

これがカルドセプトサーガが犯した過ちですが、意外にプログラマをやっていてもこうした「お約束」を理解している人は少ないのではないでしょうか。rand()エントロピーを凌駕して、真性乱数を生成すると思い込んでいる方が少なくないように思います。

メルセンヌツイスター教に入信しておけば、おおむね問題ないと思います。

暗号論的擬似乱数

乱数の品質は計算量や出目の偏り、周期の長さで評価されることが多いのですが、それとは別に暗号用途で利用できるかどうかという軸があります。

通常の擬似乱数は、例え乱数列として品質が良くとも、暗号用途としては決して使ってはいけません。

両者を区別する、面倒な数学的な定義がありますが、「現実的な時間を掛けても、それが真の乱数列なのかアルゴリズムによって生成された擬似乱数なのか識別できない場合に暗号論的擬似乱数と呼ばれる」…程度のゆるふわな認識でいい気がします。

厳密な定義は人によって様々で怖いです。(メルセンヌツイスタで作った擬似乱数に暗号学的ハッシュ関数を掛けたものは暗号論的擬似乱数と言えるのか?とか)

arc4random()って何?

iOSでの開発では、arc4random()関数を用いて乱数を生成することが多いと思います。

これはお手軽に暗号論的擬似乱数列を得られます。

この関数はFreeBSD由来と言われることが多いのですが、manを読めば分かるように大本はRC4です。

RC

ロナルド・リン・リベスト氏という暗号分野で著名な研究者がおり、RC4は氏の作成した暗号アルゴリズムです。RCとは「リベスト暗号(Rivest Cipher)」の略だと言われており、RC1、RC3など開発中に解読されて欠番となったものもありますが、RC4やRC5、RC6などシリーズ化しています。

このネーミングでピンときた方がいるかもしれませんが、MD2やMD4、MD5の作者でもあります。

ARCFOUR

RC4は1987年にRSAデータセキュリティ社で開発され、そのアルゴリズムは長らく企業秘密でした。

しかし1990年代末に、ニュースグループにてその実装が解説が流出したことで、インターネットで公知なアルゴリズムとなりました。

こうして、RC4のオープン実装である、ARCFOUR(Alleged-RC4、「RC4以外の何か」)が普及しました。arc4random()もその実装の一つでした。

RC4の終焉とarc4random

現在ではRC4への攻撃方法が発見され、もはやセキュアではないといわれており(HTTPS通信におけるRC4の使用が禁止されるなど)、NetBSDなどのarc4random()の実装も、ChaCha20によるものに置き換えられています。

OSXiOSarc4random()は、まだRC4モドキらしいですが…。

そんなわけで、玄人はきっと/dev/randomから暗号論的乱数列を取得できるSecRandomCopyBytes()を使っているんだと思います。これがまた超使いにくいんですよね…。

追記

上の内容は、OSX 10.10のターミナルでman arc4randomした内容/dev/urandomでS-Boxを埋めてから、ARC4ストリーム暗号を使って乱数生成している)を元に書いていますが、Appleが公開しているLibc-997.90.3のソースコードではS-Boxの生成に/dev/randomを利用しているみたいです。

その後はARC4を使っていますが、脆弱性対策として最初の1024byteを捨てたあと、1600000byte毎に/dev/randomから再度シードを与えてるっぽい?

iOS/OSXカーネルにおいて/dev/randomの実装がどうなっているのかも興味があるところです(FreeBSDだと/dev/random/dev/urandomシンボリックリンクだったりするので。英語版のWikipediaの/dev/randomの記事ではiOS/OSXはYarrowアルゴリズムを使っているとあるけれど、この記述は古いような気がします)