Hatena::ブログ(Diary)

わさっき RSSフィード

2012年08月06日

[] MD5ハッシュ値オールゼロに挑戦

いきなりですが問題です.

MD5ハッシュ値チェックサム,fingerprint,メッセージダイジェスト)がすべて0となるような,入力メッセージを答えなさい.

さっそくですが解答…いや,答えは知りません.もし,そんな入力メッセージを得ていたら,弱衝突耐性を破ったってことになります.そんな入力があるかどうかも,分かっていません.

そこで,もっと簡単な問題にします.

MD5ハッシュ値の先頭32ビット(16進出力では最初の8桁)がすべて0となるような,入力メッセージを答えなさい.

これくらいだと,計算機をぶん回せば,答えが出てきそうです.情報セキュリティの試験も終わったことですし,Rubyスクリプトを書いてみました.

少し気をつかったことが2つ,あります.一つは,入力メッセージをどのように生成するかです.乱数を使うと,周期の問題があります.毎回必ず異なる文字列にしたいのですが…幸いにも,String#succが「次の」文字列を作ってくれるので,これを採用します.

もう一つは,途中経過をどう出力させるかです.これですが,「先頭から連続する0の数」が記録を更新したときと,Ctrl+Cを押したときに,出力することにしました.後者は,「begin〜rescue Interrupt〜end」を使えばできます(class Interrupt).Ctrl+Cでプログラムを終了させないよう*1,外にwhile trueを置きました.

今のところ出力はこんな感じ:

$ ruby hash-all-zero.rb 1
02e74f10e0327ad868d138f2b4fdd6f0 (1) 27
006f52e9102a8d3be2fe5614f42ba989 (2) 168
0004d0b59e19461ff126e3a08a814c33 (3) 1970
00003e3b9e5336685200ae85d21b4f5e (4) 5329
00000f7264c27ba6fea0c837ed6aa0aa (5) 1803305
0000002760a7f6313eb52ef22f47137a (6) 20412333
0000000c91b7d0459d6b0e0ea163b149 (7) 220455692
000000004d08923509d394d55084bc01 (8) 6262635619

Rubyを使わなくても,echo -n 6262635619 | md5sumで検算できます.

ちなみに最初の文字列を別にして,1つのマルチコアCPUで2つのプロセスを動かしているのですが,先頭36ビット(16進出力では最初の9桁)がすべて0になるものが見つかっています.「@amjhjeyq」で,echo -n @amjhjeyq | md5sumを実行すると「000000000e66f91563d2ac2f79e654e4」と出ます.

とはいえ,このプログラムで,ハッシュ値がオールゼロのものが出たらびっくりです.計算時間を予測してみると,

  • 最初の8桁がすべて0になるものを見つけるのに,1時間かかったとすると,
  • 最初の9桁がすべて0になるものを見つけるのに要する時間の期待値は,その16倍なので,16時間
  • 最初の10桁がすべて0になるものを見つけるのに要する時間の期待値は,その16倍なので,256時間=10日強
  • 最初の11桁がすべて0になるものを見つけるのに要する時間の期待値は,その16倍なので,約160日=5か月強
  • 最初の12桁がすべて0になるものを見つけるのに要する時間の期待値は,その16倍なので,約80か月=6年半強
  • 最初の13桁がすべて0になるものを見つけるのに要する時間の期待値は,その16倍なので,100年以上

となりまして,「32桁すべて0になるものを見つける」のは,夢のまた夢です.

*1:その分,一つのシェルで,このプログラムを終了するには,少々手間がかかります.実行中にCtrl+Zで,停止させます.bgを実行して,バックグラウンドで動かします.ps | grep rubyで,動いているRubyスクリプトを見つけ,kill -9 プロセス番号で有無を言わさず終了させます.