1年ぐらい前からぼちぼちといろんなハッシュ関数を実装してきて、つい先日、SHA-{0, 1, 2, 3}が全部揃ったので一旦振り返ってみることにした。
ソースコードはここにある。
なんでハッシュ関数を実装したの?
おもしろそうだったから
やってみてどうだった?
たのしかった
遭遇したバグ
テストケースが違う
これに何度も遭遇して毎度頭を抱えていた。原因は、仕様が書かれているPDFやRFCやWebページからのコピペの失敗・テストの入力と出力の対応ズレなど。
コード本体は合っているためそこには存在しないバグを探して彷徨うことになる。未だにやらかす。
非64bit環境で動かない
一部のハッシュ関数にある長さ付与の処理がバグの発生箇所。MD5やSHA-1、SHA-2などでは入力データの長さをパディング(長さを整える処理)時に64bit若しくは128bit分のスペースに書き込む処理がある。入力データの長さを取得するときはdata.len()のような形で取得するのだが、このとき帰ってくる数字の型がusizeという環境によって64bitだったり32bitだったり16bitだったりと大きさが変わる型になっている。問題の実装ではこれを考慮していなかったため、手元の64bit環境では動くがWebAssemblyなどの32bit環境では動かないと言うことが発生した。as u64のような形で型をキャストしてやることで対応した。
前より早くなったよ！
このコミットから、一部のハッシュ関数が入力データを丸ごとコピーしたものを生成しないようになった *1。副作用として、MD2を除いたハッシュ関数で処理速度がそこそこ向上した。詳細はここ
MD2がびっくりするぐらい遅い
前項の修正が入る前になるが、criterionというライブラリを使ってベンチマーク結果をグラフに表示してみた。その結果が下の図で、この図に1本ある明らかにおかしい線がMD2のものだ。SHA-3(Keccak)よりずっと遅い。ぶっちぎりで遅い。他の実装と比べても速度に差はなく、わたしの実装が特別遅いということでもない。というのもMD2は32bitや64bitのワードを最小単位として処理するのではなく、8bitのバイト列のまま全ての処理を行う。そのため、ループ回数が他のハッシュ関数に比べてかなり多くなる。おそらくこれがMD2だけがここまで遅い理由だろう。
WebAssemblyターゲットでビルドしてみた
Yewというライブラリとwasm-packとその他いくつかのライブラリを使い、WebページでGhashを使ったアプリケーションを公開してみた。このページで公開してある。驚くことにこのWebアプリケーションを作るにあたって、私はJavaScriptを(設定ファイル等を除き)1文字も書いていない。全てライブラリが自動で生成してくれている。ソースコードはここで公開してある。
*1 これ以前(KeccakとBLAKEは記事執筆時点でも)は入力データを丸ごとコピーしたものが構造体内部に保持されるようになっていた。つまり1GBのデータを与えると、もう1つ1GBのデータがメモリ上に確保されるという状態だった。ちなみにもっと前の実装ではさらにもう1つコピーがあって、入力の3倍メモリが消費されていた。