hashcash - DOS ベースのアンチスパム技術
世の中にはいろんな人たちがいる。 その中でも、あなたにとってコミュニケーションをとる価値のある人と、 あなたの意思に関わりなくメッセージを読ませたがる人がいるのではないかと思う。
もちろん、あなたが必要としているのは前者であって、後者ではない。
それを振り分ける技術が、 メールだったらホワイトリスト/ブラックリストだったりベイジアンフィルタだったりするわけだ。
でも、こういった技術はかなり広汎に試されているので、ここで説明するのは置いておいて、 今回はもう少し変わり種の手法である hashcash を紹介しよう。
ここで、突然ちょっとした数学の話になる。 まあそんなに難しくはないので、最後までお付き合い願いたい。
ある文字列 S が与えられたとき、もうひとつの文字列 s と連結した文字列(トークン) S + s の ハッシュ値 H の 左 n bit がすべて 0 になる、そのような s はどんな文字列だろうか。
計算してみないとわからないって？ そう。実際に s を 0 から順に H を計算して、 実際にそうなっているのかどうか確かめてみなければわからない。ここがミソ。
あなたがスパムメールにうんざりさせられているのなら、 この条件を満たす H のスタンプの入ったメールのみ読めばいい。 とうぜん、あなたの友人の同意も必要だけど。
久しぶりにメールのやりとりをしたいと思い立ったあなたの友人も、 毎週メッセージを替えて送ってくるスパマーも、 誰もが衝突するハッシュを発見するまで計算しなければならない。 「私と会話したいなら、ちょっとだけあなたの電力と時間をください」というのが、 hashcash なわけ。 個人の間でメッセージをやりとりするなら計算は 1 回きりだけど、 スパマーは大量にメッセージをまき散らさないといけないから、 それこそ何度も何度も違うハッシュを計算しないといけなくなる、というしかけだ。
それでは、実際どうなっているのか hashcash の公式ページからダウンロードして試してみよう。
コンパイルできただろうか？ それではさっそく n = 20 で s を検索してみよう。
$ hashcash -mb20 foo hashcash token: 1:20:050303:foo::kN687vWdyW8jUw3+:0000000000000072LM
しばらく計算した後、上のようなトークンが出力される。 実行するごとに乱数でかき混ぜるのでトークンのエントリの真ん中より右側は毎回違う値が出力されるはずだ。 ちなみに、いちばん右の 0000000000000072LM が s に相当する文字列である。
foo は他の人のトークンとぶつからないように、 実際に使用するときはユニークな文字列の方がいいだろう。 例えばメールアドレスのような。
本当にこれが正しいトークンなのか確かめてみよう。
$ echo -n "1:20:050303:foo::kN687vWdyW8jUw3+:0000000000000072LM" | \ openssl sha1 000004a5a3839d2d4e696d2ec4af01cf6340cfba
左 20 bit が 0 になっているのがわかるだろうか。
以上で原理が理解できたと思う。
次に応用なのだが、 javascript で実装してみたのがこれ。
javascript は実行速度が遅いので n = 10 である。
これを使って、 このページの くっつき BBS と連携させてみたので試していただきたい。
検索空間は 0 から 210 なので、 もしかすると衝突を発見できないかもしれない。 そのときは発見するまで計算ボタンを気が済むまで連打してほしい。
確認しておくけど、計算結果であるトークンは一回きりしか使えないことに注意。 なぜだかわかるよね？ それを実現するためには毎回データベースへ使用済みトークンを登録していけばいい。
最後に、ここまで読んでくれた人への宿題。
- hashcash を組み込むと有効なアプリケーションにはどのようなものがあるか。
- hashcash をすり抜けるような攻撃にはどのようなものが考えられるか。
- hashcash は 1996 年に発表された比較的古い手法であるにもかかわらず、 なぜいままで使われてこなかったのか、理由を考えてみよう。
- 手元のマシンで $ openssl speed sha1 を実行したところ、 64 byte のブロック(hashcash トークンの文字列長はこれくらいかやや大きい)をおよそ 300 kblocks/s の速度で SHA-1 ハッシュの算出ができることがわかった。 このマシンは n = 20 の hashcash 利用者へ 1 時間あたり平均何通スパムメールを送信できるだろうか。
- n をどれくらい信用できるかどうかの指標にしたとする。例えば最も信用できる相手ならば n = 0、 よくわからない相手ならば n = 20、疑わしい相手ならば n = 25 といった具合に(n が 1 増えるごとに計算すべき空間が倍になる点に注意せよ)。 これを認証に利用したウェブアプリケーションにはどのような問題があるか。
リンク
