MD5-Ring その２
これは、ずっと前に書いた MD5-Ring という記事の続きです：
- MD5-Ring - peanutsjamjamの日記
- http://d.hatena.ne.jp/peanutsjamjam/20060218/p2
その３もあります：
- MD5-Ring その３ - peanutsjamjamの日記
- http://d.hatena.ne.jp/peanutsjamjam/20080902/p1
Perl で MD5 を計算させてみる
Perl で、00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 という 16 バイトのデータの MD5 を表示するプログラムを書くとこうなる。（計算された md5 の値だけじゃなくて、どんな値を md5 関数に入力しているのかも一応表示。）
#! /usr/bin/perl use Digest::MD5 qw ( md5 ); $data = pack("H*", "00" x 16); print unpack("H*", $data), "\n"; $digest = md5($data); print unpack("H*", $digest), "\n";
実行結果
00000000000000000000000000000000 4ae71336e44bf9bf79d2752e234818a5
別な 16 バイトのデータで試したい場合はこう書く。
#! /usr/bin/perl use Digest::MD5 qw ( md5 ); $data = pack("H*", "4ae71336e44bf9bf79d2752e234818a5"); print unpack("H*", $data), "\n"; $digest = md5($data); print unpack("H*", $digest), "\n";
実行結果
4ae71336e44bf9bf79d2752e234818a5 398d01fdf7934d1292c263d374778e1a
計算されたダイジェスト値をさらに md5 の入力として与えてやって、また計算させる･･････ってのを 10 回繰り返すと、こんな感じ。
#! /usr/bin/perl use Digest::MD5 qw ( md5 ); $data = pack("H*", "00" x 16); print unpack("H*", $data), " <= start\n"; for (1 .. 10) { $data = md5($data); print unpack("H*", $data), "\n"; }
上のほうのプログラムで使っていた $digest っていう変数は消えて、$data っていう変数だけを使っている。
実行結果
00000000000000000000000000000000 <= start 4ae71336e44bf9bf79d2752e234818a5 398d01fdf7934d1292c263d374778e1a 7995886059df6dd8a1cef4338aa4118e 543a5cb14988ac60d7068649d34434f8 fbfdd8ae19dd5a531f729e8ec0ab66aa d55f8f0ee335d18a55e983b568a9bb05 33105995009f4b777dbe84d4801e56ae 23841eed0995d10e3b9def2e79a6fcb8 73562a1e09d18bb2ff2b9445c70b4bb8 4892033e755650213415bbd6535a04cb
これをずーっと続けて行ったら
これをずーっと続けて行ったら、どこかで、既に一度出力した値をふたたび出力するだろう、ってことは自明だ。だって、
- どんな 16 バイトを与えても、md5 関数は何らかの 16 バイトを返す
- 16 バイトで表現できる値の種類は有限だ
という 2 つの命題が真だもの。*1
どこかで「既に一度出力した値」を md5 関数が吐いたら、そこから先は当然、以前と同じ道をたどることになる。そしてまた、先の「既に一度出力した値」を吐いて、以下ぐるぐる回る。これが「MD5 Ring」。
どうやって調べたらいいのか
どこで「既に一度出力した値」を吐くのかを調べるために、どういう方法を採ったらいいんだろう。
たとえば、上の例でいちばん最初に md5 関数が返してきた値 4ae71336e44bf9bf79d2752e234818a5 をハードコードで記録しておいて、md5 関数が値を返すたびに、それと比較するっていうのを考えてみる。
#! /usr/bin/perl use strict; use Digest::MD5 qw ( md5 ); my $search = pack("H*", "4ae71336e44bf9bf79d2752e234818a5"); my $data = pack("H*", "00" x 16); print unpack("H*", $data), " <= start\n"; $data = md5($data); print unpack("H*", $data), "\n"; # => 4ae71336e44bf9bf79d2752e234818a5 # だけど、最初の一回はノーチェック while (1) { $data = md5($data); print unpack("H*", $data), "\n"; die "Found!!" if ($data eq $search); # 見つけたら終了（死ぬことはないかｗ }
これを実行しながら、「はやく Found!! って表示されないかなぁ」と、上へ上へと流れていく数多（あまた）の 16 進数をボーッと眺めていて思ったことは、「このプログラムは終了しないかもしれない」ということ。
どこでループするのか。どこにループするのか。
なぜかというと 4ae71336e44bf9bf79d2752e234818a5 という値が MD5 Ring の内部に存在しているという確証がないから。
たとえば、これは、私が勝手に捏造した実行結果。
00000000000000000000000000000000 <= start 4ae71336e44bf9bf79d2752e234818a5 <= search 398d01fdf7934d1292c263d374778e1a 7995886059df6dd8a1cef4338aa4118e 543a5cb14988ac60d7068649d34434f8 fbfdd8ae19dd5a531f729e8ec0ab66aa d55f8f0ee335d18a55e983b568a9bb05 33105995009f4b777dbe84d4801e56ae 23841eed0995d10e3b9def2e79a6fcb8 73562a1e09d18bb2ff2b9445c70b4bb8 4892033e755650213415bbd6535a04cb 73562a1e09d18bb2ff2b9445c70b4bb8 4892033e755650213415bbd6535a04cb 73562a1e09d18bb2ff2b9445c70b4bb8 4892033e755650213415bbd6535a04cb 73562a1e09d18bb2ff2b9445c70b4bb8 4892033e755650213415bbd6535a04cb
これの下のほうを見てみると 73562a1e09d18bb2ff2b9445c70b4bb8 という値の md5 ダイジェストが 4892033e755650213415bbd6535a04cb で、4892033e755650213415bbd6535a04cb という値の md5 ダイジェストが 73562a1e09d18bb2ff2b9445c70b4bb8 となっている。たった 2 つの値の間を行ったり来たり、パタパタしているという状態。（＝Ring の大きさが 2。）
これは捏造だけれど、実際のデータでもこんな風にならないとは限らない。もしこれが実際に起こっていたとしたら、"<= search" で示している値で待ち続けても、永遠にその値はやってこない。
輪とヒゲ
図にしてみるとこんな感じ。
Ring は存在していても、その Ring の内部のどれかの値で待っていないと、永遠に Ring は見つけられない。Ring が見つかるまでは、その値が Ring の内部にあるのか否かもわからない。
Ring 外部の、ヒゲの部分の長さも分からないし、或る Ring に対してヒゲがいくつ存在するのかもわからない。
こういう場合、どうやって Ring を探せばいいのだろう。
