いきなりですが問題です．
MD5のハッシュ値（チェックサム，fingerprint，メッセージダイジェスト）がすべて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になるものを見つける」のは，夢のまた夢です．
