バーンスタイン博士が、Pentiumで数時間かけてmd5の56ビットの衝突を見つけたと発表したが、これはこの方式にどう影響するだろう。彼の投稿からは、既知のハッシュとの衝突を探していたのか、それとも指定した長さで衝突する二つの異なる文字列を探していただけなのか、はっきりしなかった。
数日前のダン・バーンスタインのsci.cryptへの投稿を挙げてくれたのは興味深い。匿名性を保つスパム対策の郵便料金として部分ハッシュ衝突を使うことを考え始めたのは、まさに彼の投稿がきっかけだったからだ。リベストとシャミアにも「MicroMint」という仕組みがあり、私はそれを知っていた。k個のハッシュの衝突を、もっと複雑な形で、完全な少額決済の仕組みの土台に使っている。数日前、ハル・フィニーがサイファーパンクでその仕組みの概略を説明し、似ていることを指摘していた。
リメーラーとスパム対策に必要なのは、計算するのは高くつくが、検証するのは簡単な関数だ。部分ハッシュ衝突はこれを満たし、いくらでも高くつくようにできる（100分の1秒から、数百MIPS年まで）のに、検証は一瞬で済む。hashcashの提案は、この関数を土台にして、従量制でないインターネットの資源の乱用を減らす分散型のやり方を取る。
匿名の通信の郵便料金に使っても、潰されたり、身元の預託を加えるよう強いられたりする銀行も仲介業者も、そのほか法的に狙える存在も何もない。その結果、この現金の受け取り手（匿名リメーラー、あるいは個人の利用者）は、ほかの通貨に換えられる価値を何も得ない。その代わりに、送り手がメッセージの準備に、受け手がそのメールの要求を処理するより多くの計算資源を費やした、という保証を得る。
ダン・バーンスタインが話していたのは誕生日攻撃のことだと、かなり確信している。記憶容量の要求を抑えるある技法を使ったことに触れ、誕生日攻撃には大きな記憶容量が要ると主張していた人たちは間違っていた、と示唆していたからだ。
彼が見つけたのは、任意の2方向の衝突だと思う。
「任意」というのは、衝突するビットがハッシュの出力のどこにあってもかまわない、という意味だ。
「2方向」というのは、どんなメッセージの文字列（何でもいい）でもハッシュの衝突を探している、という意味だ。つまり次の式で、
X = H( M )
Y = H( N )nビットの衝突なら、XとYのビットがn個の位置で同じになるようなMとNを探している。
任意の衝突を認めれば、仕事は楽になる（衝突するビットの位置に制限を付けるなら、見つかる任意の衝突のうち、選んだ位置にビットがあるものはほとんどない）。
Hashcashは任意の衝突を認めない。クライアントが受け付けるとみなす衝突は、上位のnビットでなければならない。
Hashcashは特定の文字列との衝突を探しているので、誕生日攻撃を見つけるときの記憶容量の複雑さも、処理の負担を増やす代わりに記憶容量の要求を減らしてそれを見つける方法も、関わってこない。
具体的には、hashcashのクライアントは、Mのハッシュとの上位nビットの衝突を探している。
M = day | resource-name
X = H( M ) = H( day | resource-name )クライアントは、次の形の文字列で衝突を探す。
M' = M | counter = day | resource-name | counter
X' = H( M' ) = H( day | resource-name | counter )だから、ハッシュの衝突を見つけるアルゴリズムは、驚くほど単純だ。
1. calculate X = H( day | resource-name )
2. counter = random-start-point
3. calculate X' = H( day | resource-name | counter )
4. if the first n-bits of X and X' are equal STOP
5. counter = counter + 1
6. goto 3.ハッシュの衝突による郵便料金は、M’ = day | resource-name | counterだ。
ハッシュ関数Hが一方向で衝突に強いなら、衝突を見つけるもっと簡単な方法はない。ここでの目的では、出力のビットは、それぞれ50%の確率で0か1の値を取る独立した確率変数とみなせるからだ。要するに、n枚の硬貨を続けて投げて、全部が選んだ出力（表＝0、裏＝1）と一致するかを見るようなものだ。
hashcashの実装での関数HはSHA1だ。実際に使われるハッシュは、事実上、160ビットのSHA1の出力の残り160 - nビットを捨てた短いハッシュになる。
hashcashのクライアントには、1970年1月1日からの日数である「day」が入っている。ecashの受け取り手が有効期間を決めたり、hashcashで料金を払うサービスの期限を決めたりできるようにするためだ。
dayの欄をハッシュに入れるいちばんの目的は、hashcashの受け取り手が二重支払いのデータベースの大きさを抑えられるようにすることだ。
「resource-name」の目的は、別のリメーラーや別のメールの受け手で使うことで、現金が二重に使われないようにすることだ。資源には名前があり（メールアドレス、リメーラーの短い名前、何でもいい）、ほかと重なる名前を選べば、二重支払いの危険に身をさらすことになる。つまり、この現金は受け手ごとに決まっている。
望むなら、hashcashのクライアントを使って、中央の二重支払いのデータベースを作り、サービスを提供する側が二重支払いをオンラインで確かめられるようにすることもできる。
そうすれば、利用者は、誰に使うかを前もって決めずに、衝突をいくつか作っておける、という利点がある。
メールについては、そこまでする価値はないと思う。主な狙いは、スパム業者に、巻き添えを食う人たち（リメーラーや、一方的な大量メールの受け手）より大きな計算資源の負担を負わせることだからだ。
アニル・ダスアダム・バックの投稿（1997年3月28日16:52 UTC）（それから、私のSHA1の実装はビッグエンディアンのマシンで試していない。理屈の上では、バイトの並びを自動で判定する。）
% ./sha1test test 1
よし、ビッグエンディアンの判定はちゃんと動いている。
アニル・ダスSHA1(“abc”) = a9993e364706816aba3e25717850c26c9cd0d89d test ok
% ./hashcash -t -22 speed: 70921 hashes per sec find: 22 bit partial sha1 collision estimate: 30 seconds
きみの計算力がうらやましい。私の120MHzの486のLinuxのマシンの10倍くらいだ :-)
アダム
--
Have *you* exported RSA today? --> http://www.dcs.ex.ac.uk/~aba/rsa/
print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`