mono での NewGuid と RngCryptoServiceProvider

コードを読んでみた

mono において Guid.NewGuid() で Guid がどうやって生成されているのかが気になったので、せっかくソースコードが公開されていることであるし、読んでみた。

また、NewGuid の実装には後述の通り RngCryptoServiceProvider が使われているので、結果として mono における乱数生成機(RNG)の造りも調べることになったという次第。

なお、全部丁寧に解説しようとするとモチベーションが折れるので、気分に応じてのおおざっぱな解説である。

前知識

Guid とは: GUID - Wikipedia
UUID とは: UUID - Wikipedia

Wikipedia を読めば分かるが、UUID や Guid は、

  • 管理するサーバーなどなしに、一つのマシンの中だけで簡潔に生成できる
  • (現実的な条件下では、ほぼ間違いなく)全世界において一意

という性質があり、Microsoft 関連でないオープンソースソフトウエアなどでも、すでに陰でかなり使われている代物である。

んで、要するに便利な一意 ID なのでもっと使おうよ、と思うのだが、やはり都合の良い話をするからには実装の詳細も知りたいよね、というのがコードを読んだきっかけ。

なお、.net における System.Guid は、GUID という名前だけど実際には UUID 値ならなんでも保持できる(mono なり .net framework なりのソースコードからも分かる)。

ここで、GUID は UUID に含まれる概念で、ある特定の生成方法によって作られた UUID が Guid である。が、実際には UUID なのに Guid と呼んでしまうことも少なくないし、.net framework / mono もその一例なのである。

UUID の生成手法は RFC 4122 に規定があり、おおざっぱに言うと

  • NIC の MAC アドレス + タイムスタンプ
  • ハッシュ関数(NIC の MAC アドレス + タイムスタンプ)
  • 乱数 (pseudo-random UUID とも)
  • Guid

のどれかである*1。ちなみに、どの手法で生成されたのかは、UUID の先頭の方のビットで分かるようにもなっている。

mono のソースコードの流れ

で、mono での Guid の生成の流れを追っかけてみたのだが、以下に概要を示す。上から順にコードの流れで、付加されているソースコードは mono の svn head へのものである。

  1. static Guid.NewGuid()
  2. static RandomNumberGenerator.Create()
  3. static CryptoConfig.CreateFromName(string)
  4. RNGCryptoServiceProvider.GetBytes(byte[])
  5. RngOpen(), RngInitialize(byte), RngGetBytes(IntPtr, byte)

以下では、それぞれについて気になった点などをハイライトしてみた・・・つもりが、実際にはほとんど順をおった解説になってしまった。これだから現実逃避でコードを読むのは(ry

各論の前に: 長くなってしまったので概略

  1. Guid.NewGuid() は、RNGCryptoServiceProvider の乱数を使っているだけ
    • pseudo-random UUID が生成される。
  2. RNGCryptoServiceProvider は、Win32 環境なら CAPI をラップするだけ
  3. 非 Win32 環境の RNGCryptoServiceProvider は、以下を順に試して使えるやつを使う
    1. /dev/urandom
    2. /dev/random
    3. EGD な Unix ソケット: MONO_EGD_SOCKET 環境変数が接続先

メモ: 自分への宿題 (= 読んだはいいが分からなかった点)

  • mono のクラスライブラリ実装で、static readonly による singleton よりも、lock + if なシングルトンが用いられているのはなぜなのでしょう
  • mono が libuuid を使わずに独自実装したのはなぜなのでしょう
  • 非 Win32 環境の場合、RNGCryptoServiceProvider が AppDomain 単位で lock するのに対して、ファイルデスクリプタはプロセス内で一つ、とスレッドセーフ性*2に問題があるように見えるのは、実際どうなのでしょう

Guid.NewGuid() と RNG とロック

NewGuid() では、

// generated as per section 3.4 of the specification

とある通り、RFC 4122 の §3.4 にのっとって疑似乱数による UUID を生成している。つまり、現行の mono の NewGuid は疑似乱数による生成法を使ったものである。

ちなみに、古い mono のソースコード*4を見ると、MAC アドレスとタイムスタンプを使った Guid を作ろうとしていたのだが、MAC アドレスの取得が出来ていなくて TODO になっていたりもして興味深い。それにしても libuuid 使わないのはなんでなのでしょう。

ここで、乱数で作るとはいうものの、使っている乱数は RandomNumberGenerator.Create メソッドによって得られる乱数生成機(RNG)を使っている。

また、

// thread-safe access to the prng
lock (_rngAccess) {
	if (_rng == null) _rng = RandomNumberGenerator.Create ();
	_rng.GetBytes (b);
}

と言う風に、一つの乱数生成機を排他制御しながら使い回しているようだ。乱数生成機の内部でも後述するように排他制御してくれるので、単に Singleton でもええやんと思うのだが、歴史的事情なり何らかの問題なりがあるのだろうか。気になる・・・。

RandomNumberGenerator.Create

RandomNumberGenerator には Create() や Create(string) といった static メソッドがあるのだが、これは乱数生成機のアルゴルズム名(のデフォルト値)からインスタンスを作ってくれる(see: RandomNumberGenerator.Create メソッド)。

ここで、RandomNumberGenerator のそれらのメソッドは、

public static RandomNumberGenerator Create (){
	// create the default random number generator
	return Create ("System.Security.Cryptography.RandomNumberGenerator");
}

public static RandomNumberGenerator Create (string rngName) {
	return (RandomNumberGenerator) (CryptoConfig.CreateFromName (rngName));
}

となっており、要するに CryptoConfig.CreateFromName に丸投げしている。

ちなみに、これって CryptoConfig.CreateFromName の結果次第では InvalidCastException になるのだが大丈夫か？と思うのだが、MSDN には例外の種類の記述すら無いという・・・。どうにも、mono のみならず本家 .net framework でも、あまり使われていないであろう API になると記述がはしょられたり、例外処理が甘くなる(そして、何が起こったのかわかりにくくなる)傾向があるのだが、まぁ当然ではあるのだろう。むしろ、それをトレースしやすいだけマネージドな世界はありがたいとも思うし。

CryptoConfig.CreateFromName

というわけで、UUID 生成のための RNG は結局 CryptoConfig.CreateFromName を使って作製されることが分かったのが、ここまでのあらまし。

ここで、CreateFromName(string) のやっていることは実はかなり簡単で、

  • 引数で与えられたアルゴリズム名から、対応するクラスの完全限定名をテーブルで引く
    • テーブルに無かった場合、指定されたアルゴリズム名が型の完全限定名そのものだと見なす
  • ↑で分かったクラスを、Activator.CreateInstance を使ってインスタンス生成する

だけである。仰々しいインターフェースの割には原始的な仕様だが、疎結合性の確保やらのためにはこれで必要十分だったのだろう。

ここで、前者のテーブルは 

static private Hashtable algorithms;

という static フィールドに保持され、CreateFromName(string) 内部で

lock (lockObject) {
	if (algorithms == null) {
		Initialize ();
	}
}

のようにして初期化されている。ここでも static readonly による singleton を使わない辺り、なにか歴史的事情なりパフォーマンス上の理由なりがあるのだろうが。

こうして algorithms テーブルを得た後の処理は上の流れそのまんまなのだが、見ていて気になるのは、

try {
	// 中略
	return Activator.CreateInstance (algoClass, args);
} catch {
	// method doesn't throw any exception
	return null;
}

のように、どんな例外があっても null を返す点である。対応する型がなかったり、インスタンスを正常に作れなかったらどうするか、の仕様が MSDN にもないし、おそらく .net 側とあわせてあるのだろうけれど・・・。

なお、今回の RandomNumberGenerator.Create() については、"System.Security.Cryptography.RandomNumberGenerator" と型名を決め打ちしているのでテーブルの内容はあまり問題でない*5のだが、テーブルの中身は CryptoConfig の先頭にある沢山の定数を元に、Initialize() メソッド内で構築されている。

ちなみに、その定数の中には

private const string defaultRNG = defaultNamespace + "RNGCryptoServiceProvider";

なんてのもあり、これは "RandomNumberGenerator" というキーでテーブルに登録されているのだが、呼び出し元である RandomNumberGenerator.Create() でも完全限定名を決めうちしているというのはなんだかな、と思わないでもないのであった。RandomNumberGenerator.Create() のデフォルトと CryptoConfig にとっての RNG のデフォルトは別物、という認識なのだろうか。

RNGCryptoServiceProvider と InternalCall

というわけで、mono における NewGuid は要するに RNGCryptoServiceProvider によって生成された乱数を RFC 通り(pseudo-random UUID)にフォーマットしたものになっているのだが、その乱数はどうやって作られているのだろうか。(前置きが長くなったが一応今回の主題である。)

ここで、RNGCryptoServiceProvider のソースコードを見てみると、ずばり

[MethodImplAttribute(MethodImplOptions.InternalCall)]
private static extern bool RngOpen ();

[MethodImplAttribute(MethodImplOptions.InternalCall)]
private static extern IntPtr RngInitialize (byte[] seed);

[MethodImplAttribute(MethodImplOptions.InternalCall)]
private static extern IntPtr RngGetBytes (IntPtr handle, byte[] data);

[MethodImplAttribute(MethodImplOptions.InternalCall)]
private static extern void RngClose (IntPtr handle);

public override void GetBytes (byte[] data) {
	// 中略
	_handle = RngGetBytes (_handle, data);
	// 中略
}

という大変分かりやすい記述がある。

要するに、RNGCryptoServiceProvider は MethodImplOptions.InternalCall な Rngほげほげ 関数群のラッパーなのである。

なお、mono のランタイムライブラリでは、mono 内部の C で書かれた関数を static extern なメソッドとしてリンクする場合には、このように MethodImpl 属性を使うようにしているようだ。

ここで、Rng 用の InternalCall な関数を呼び出すに当たって、RNGCryptoServiceProvider は必要に応じてロックを行うようになっている。具体的には、

private static object _lock;
private IntPtr _handle;

static RNGCryptoServiceProvider (){
	if (RngOpen ()) _lock = new object ();
}

public RNGCryptoServiceProvider (){
	_handle = RngInitialize (null);
	Check ();
}

のように、RngOpen() の戻り値によって、Global lock するかどうかを決定しているのである。つまり、 InternalCall な Rngほげほげ 関数群は、Giant lock を必要とすることもあるしそうでないこともある。

また、興味深いことに、RngOpen() は AppDomain 全体で一回だけ呼ばれ、RngInitialize(byte[]) が RNGCryptoServiceProvider インスタンスごとに呼ばれる造りになっている。なお、この辺は、次に出てくる InternalCall な Rngほげほげ 関数群の実装についての伏線にもなっている。

加えて、もう一つ興味深いのは、RNGCryptoServiceProvider や RandomNumberGenerator は IDisposable でないのだが、Rng のリソースを解放しなくてはならないがために、必ずファイナライザで RngClose(IntPtr) を呼んでいる点である。

~RNGCryptoServiceProvider () {
	if (_handle != IntPtr.Zero) {
		RngClose (_handle);
		_handle = IntPtr.Zero;
	}
}

インターフェースの仕様の問題なのだろうが、リソースの解放をファイナライザだけに頼っているコードは、C++ ならともかく C# としては新鮮に思える。

rand.c と Rngほげほげ 関数群

というわけで、NewGuid は要するに RNGCryptoServiceProvider によって生成された乱数で、その値は InternalCall な Rngほげほげ 関数群によって作られている。のだが、怪しい Giant lock があったりで詳細が気になる所である。

また、ついに extern で InternalCall な関数が出たことで、ここからは # の付かない C で書かれた実装を見てゆくことになる。今回見るべき Rng 系の関数の実体は、rand.c にある
ves_icall_System_Security_Cryptography_RNGCryptoServiceProvider_Rngほげほげ
関数たちである*6。ちなみに mono では、extern で InternalCall な関数の C 言語上での実体は必ず ves_icall_ という接頭辞で始まるので、それを知っていると C# クラスライブラリ実装から C への遷移が見えて雰囲気を味わいやすかったりもする。

ここで、rand.c を読もうとすると、#if プリプロセッサマクロが入り交じっていて、対応がちょっとわかりにくいのでそれを整頓しながら読んでみるた。

rand.c: !defined(PLATFORM_WIN32) の場合(つまり非 Win32 環境)

以下を追加で #include, #define, 定義 する。

#include <sys/socket.h>
#include <sys/un.h>
#include <errno.h>

#ifndef NAME_DEV_URANDOM
#define NAME_DEV_URANDOM "/dev/urandom"
#endif

static gboolean egd = FALSE;
static gint file = -1;

また、get_entropy_from_server という関数を定義する。

static void get_entropy_from_server (const char *path, guchar *buf, int len){
	// ...	
}

この関数は、関数内にある

file = socket (PF_UNIX, SOCK_STREAM, 0);

g_warning ("Entropy problem! Can't create or connect to egd socket %s", path);
mono_raise_exception (mono_get_exception_execution_engine ("Failed to open egd socket"));

といった記述からも察せられるように、EGD (Entropy Gathering Daemon) に Unix ソケットで接続して、乱数を問い合わせるものである。ちなみにソケットは get_entropy_from_server が呼ばれるたびに毎回生成・破棄される。

その上で、ves_icall_(中略)_Rngほげほげ 関数群を以下のように実装する。

  • RngOpen: NAME_DEV_URANDOM, NAME_DEV_RANDOM, EGD ソケット いずれかへの接続*7を開く
    • 優先度は上の順序の通り。先頭から順に試す。
    • 開いた接続は static 変数に覚えておく。ちなみに既に開いてある接続があるなら何もしない。
      • 接続はプロセス(AppDomain にあらず)で一個だけ開かれるのである。
    • 戻り値は必ず TRUE なので、RNGCryptoServiceProvider では必ず Giant lock される。
  • RngInitialize: RngOpen で、候補のうちどれかに接続できたかどうかを確認するだけ
    • どれにも接続できていないなら false を返すので、マネージドなライブラリ側で例外が生起されるはず。
  • RngGetBytes: RngOpen で得た接続から読み取るだけ
    • EGD なら先ほどの get_entropy_from_server を使う。
    • /dev/(u)random なら、そこから read するだけ。
      • 割り込み(EINTR)以外の read エラーがあった場合、エラー扱いになる。

ここで、RngOpen での EGD ソケットの接続先は、

const char *socket_path = g_getenv("MONO_EGD_SOCKET");
egd = (socket_path != NULL);

のように、MONO_EGD_SOCKET 環境変数を使って決定されている。ので、mono に EGD を与えてやりたい場合には、MONO_EGD_SOCKET 環境変数を定義した上で mono を走らせればよい。とはいえ、(u)random が使える場合は無条件でそちらが優先されてしまうので、MONO_EGD_SOCKET は JMPInline: Mono on embedded Linux のように組み込み Linux といった環境以外ではあまり使う機会がないかもしれない。

どうでも良いが、(u)random を fopen した場合、mono の実装ではそれを close しておらず、プロセス終了時に close されるに任せている辺りがいかにもアンマネージドな感じがするものである。というか、RngOpen はあるが対応する処理(RngClose ?)が無い＆無意味*8なのでこうなるのは必然なのだろう。

ちなみに、見ていて気になった点として、RNGCryptoServiceProvider 側の行う lock は AppDomain 単位(のはず)なのに対して、/dev/(u)random のファイルデスクリプタはプロセス内で一つ(のはず)である点が挙げられる。つまり、複数の AppDomain から同時に RNGCryptoServiceProvider を new した場合、

  • うっかり /dev/(u)random へのファイルデスクリプタが複数開かれたり
  • うっかり 一つのファイルデスクリプタを複数スレッドから同時に read したり

することがあるのではあるまいか、という。
pthread な環境で、一つのファイルデスクリプタを複数スレッドから read して大丈夫なのかはちょっと分からないが、ともあれロックの単位がずれているように思えてならないのである。これは機会があったらテストコードでも書いて、結果によっては bugzilla か dev ML にでも流した方が良いかも・・・。

rand.c: defined (PLATFORM_WIN32) の場合(つまり Win32 環境)

以下を追加で #include, #define する。

#include <windows.h>
#include <wincrypt.h>

#ifndef PROV_INTEL_SEC
#define PROV_INTEL_SEC		22
#endif
#ifndef CRYPT_VERIFY_CONTEXT
#define CRYPT_VERIFY_CONTEXT	0xF0000000
#endif

また、ves_icall_(中略)_Rngほげほげ 関数群の実体は、以下のように Windows の CAPI*9 を呼び出すだけの薄いラッパーになっている。

  • RngOpen: false を返すだけ
    • false を返すので、RNGCryptoServiceProvider では Giant lock は発生しない
  • RngInitialize: CryptAcquireContext および CryptGenRandom Win32 CAPI を呼び出す。
    • CryptAcquireContext によって、乱数生成で使うコンテキストを初期化
    • コンテキストは、PROV_INTEL_SEC が使えるならそれを、無理なら PROV_RSA_FULL を使うようにする。
    • seed が与えられた場合のみ、その seed を使って CryptGenRandom することで乱数生成機を初期化する
  • RngGetBytes: 原則的には、CryptGenRandom Win32 CAPI を呼ぶだけ。
  • RngClose: コンテキストを解放するだけ。

ちなみに、RngGetBytes にて以下のように CryptGenRandom でこけて、コンテキストを喪失した場合の処理の記述がちょっと面白かった。"all hope isn't lost yet!" だそうで。

if (!CryptGenRandom (provider, len, buf)) {
	CryptReleaseContext (provider, 0);
	/* we may have lost our context with CryptoAPI, but all hope isn't lost yet! */
	provider = (HCRYPTPROV) ves_icall_System_Security_Cryptography_RNGCryptoServiceProvider_RngInitialize (NULL);
	if (!CryptGenRandom (provider, len, buf)) {
		// 中略
		/* exception will be thrown in managed code */
	}
}

そんなこんなで

  1. NewGuid() による pseudo-random UUID の生成
  2. RNG のディスパッチ
  3. RNGCryptoServiceProvider とその実装

を追いかけてみたのであった。

この RNGCryptoServiceProvider は Guid のみならず暗号周りでも使われているので、mono で Guid なり暗号なりが絡むことをしている裏ではこんなものが走っている、と思いをはせてみるのも面白い・・・かもしれない。

*1:正確には他にもあったりするが、どうでもいいので続きは RFC で。

*2:AppDomain セーフ性？

*3:にしても、パフォーマンス上のオーバーヘッドが小さくない気がするのだがどうなのだろう。

*4:具体的には失念

*5:実際には、RandomNumberGenerator の完全限定名をキーに、RandomNumberGenerator の完全限定名が登録されている。

*6:にしても長い名前だ！

*7:fopen か ソケット

*8:RngClose するのはプロセスが落ちる時しかタイミングが・・・。

*9:暗号化API