[ANNOUNCE] hash cash postage implementation
部分ハッシュ衝突に基づく郵便料金方式
この数日、暗号のメーリングリストで、部分ハッシュ衝突に基づく郵便料金方式の話をしてきた。部分ハッシュを使う発想は、（衝突させるビット数を選ぶことで）計算の費用をいくらでも高くできる一方、検証は一瞬で済む、という点にある。
この考えを最初に形にした実装は、ここから取得できる。
- hashcash.tgz
- hashcash.tgzのPGP署名
この実装で何ができるかを、プログラムを使いながら例で説明する。よければ手元で試しながら読んでほしい。
部分ハッシュ衝突の生成器（hashcash mint）とリメーラーのプラグインを一体にしてある。リメーラーのプラグインは、タイプIのリメーラーには簡単につなげられるはずだ。タイプIIや仮名サーバーでは、mixmasterのクライアントとリメーラーに手を入れる必要があるが、それが比較的簡単にできるようにコードを設計してあり、mixmasterやalpha、newnymに直接組み込める。
コンパイル
% gcc -O6 -c *.c
% gcc -o hashcash hashcash.o sha1.o
% gcc -o sha1 sha1file.o sha1.o
% gcc -o sha1test sha1test.o sha1.o
%プログラムが提供する機能は次のとおり。
引数なしで実行すると、フラグの一覧と短い使い方を表示する。
速度の測定：
% hashcash -t
speed: 7218 hashes per sec
%1秒間に探索できるハッシュの数がわかる。（注：使っているsha1の実装は最適化していない、私の参照実装だ。速さを追求したsha1の実装がもう一つあり、あと30分ほどの作業で同じインターフェースになるので、あとで差し替える。sha1.cにコメントとして入れてある。）
17ビットの部分ハッシュ衝突を見つけるのにかかる時間の見積もり：
% hashcash -t -17
speed: 7274 hashes per sec
find: 17 bit partial sha1 collision
estimate: 9 seconds
%（実際にかかる時間は見積もりからかなりばらつく）
文字列「flame」で17ビットの衝突を計算する
（flameは、いまはもう動いていないリメーラーだ）：
% hashcash -17 flame
speed: 7274 hashes per sec
find: 17 bit partial sha1 collision
collision: 09948flame356018443
tries: 57450
%衝突は実際には、1970年1月1日からの日数（先頭をゼロで埋めた5桁）と、与えた文字列を並べたもののハッシュに対して探す。
つまり、次のものとの衝突を探している。
% echo -n 09948flame | sha1
fbbea210abafe3e72afe7849eaea2052e309e017
%衝突はダイジェストの上位ビットに限っているので、見つかった衝突は手で確かめられる。
% echo -n 09948flame356018443 | sha1
fbbead76da651cf856f7466fed9624d3ada061d9
%先頭の20ビットが一致しているのが手で確かめられる。（17ビットを求めたが、生成されるのは17ビット以上の衝突だ。たまたま運よく3ビット余分に一致した。これはおよそ8回に1回起きる。）
hashcashのクライアントは、衝突を報告することもできる。
% hashcash flame 09948flame356018443
collision: 20 bits
%今日の日付と比べて、有効期間を確かめることもできる。
% hashcash flame 09948flame356018443 28
validity: 28 days remaining
collision: 20 bits
%ハッシュが求めたビット数を満たしているかを確かめることもできる。
% hashcash -25 flame 09948flame356018443
collision: 20 bits
required: 25 bits
rejected: too few bits
%どれかの検査に通らなければ、終了コードは失敗になる。つまり、ビット数が足りない場合、あるいは有効期間を確かめてハッシュが期限切れかまだ有効期間に入っていない場合だ。
二重支払いの防止
選んだ有効期間のあいだ、衝突を覚えておくようhashcashのクライアントに頼むこともできる。
% hashcash -d -25 flame 09948flame356018443 28
validity: 28 days remaining
collision: 20 bits
required: 20 bits
database: not double spent
adding: 28 09948flame356018443
%衝突が追加されるのは、すべての検査（有効期間内であること、求めたビット数を満たすこと）に通った場合だけだ。終了コードでも、ハッシュが問題なかったかがわかる。
メールの受け手が新しい支払いを受け付けるたびに、データベースは際限なく大きくなってしまう。そこで有効期間をデータベースに記録しておき、有効期間が切れたあとの次の利用のときに、その衝突を捨てる。期限の切れた衝突を取っておく必要はない。期限切れのものはどのみち受け付けないのだから、前に受け付けたかどうかは関係ない。有効期間0は無期限の意味で、データベースから捨てられることはない。
二重支払いの例
新しく加わった検査は、そのハッシュが前に提示されたことがあるかどうかだ。そこで上と同じコマンドを実行すると、データベースに入っているので、使用済みとして拒否されるはずだ。
% hashcash -d -25 flame 09948flame356018443 28
validity: 28 days remaining
collision: 20 bits
required: 25 bits
rejected: too few bits
database: double spent
%（二重に使われた支払いなので、終了コードは失敗になる）
以上
ごく軽くしか試していないので、何か壊れたら知らせてほしい。
ところどころ効率の悪いところがあるが、まず動くコード、効率はあとだ。
（それから、私のSHA1の実装はビッグエンディアンのマシンで試していない。理屈の上では、バイトの並びを自動で判定する。）
これまでに話に出たリメーラーでの使い道
- 出口のリメーラーでの、投稿ごとの郵便料金
- 受け取るメールのスパムの選り分け。20ビットのハッシュも1セントのdigicashも付いていなければ、必要な郵便料金と、ソフトウェアの入手先を説明する通知を付けて突き返すプログラムを用意しておく。100万通×20で100 MIPS年になり、スパム業者が持っている計算力を超えるうえ、100万通×1セントで1万ドルは、スパムで得られそうな売り上げを超えるだろうから、スパム業者は一晩で商売にならなくなる。
- 仮名サーバーの利用者の行儀のよさを担保する保証金。仮名サーバーの利用者は、返信のできる仮名サーバーのアカウントのために、仮名サーバーに（大きめのハッシュ衝突、または25ドルのdigicashで）支払う。契約を破れば、仮名サーバーがそのdigicashや衝突を没収してアカウントを止める、という罰則の条項の付いた契約に同意する。利用者の身元はわからないが、もう一度参加するには、また大きなハッシュ衝突か、さらにdigicashを払わなければならない。
- ほかにも試せる考えはたくさんある。
これはdigicashとどう関係するか
リメーラーやメールにdigicashの郵便料金を使えれば便利だが、digicashには問題がいくつかある。
- アカウントを作るのが面倒だ（書類の記入など）
- アカウントを持っている人が少ない
- 匿名になるのは支払う側だけで、売る側は匿名にならない
そこで提案したいのは、ハッシュ衝突の郵便料金とdigicashの郵便料金のどちらでも受け付けるリメーラーだ。このやり方には次の利点がある。
- digicashがもっと広く使われるようになるまで、Hashcashがつなぎの役を果たせる
- Hashcashは無料で、PCのCPUをいくらか回すだけで使える。誰もが自由に発言するネットの文化にも合っていて、懐の寂しい者でも、百万長者や引退した政府の役人などと対等に渡り合える。
- digicashがだめになったとき（違法にされたり、利用者の身元の預託を義務づけられたりしたとき）にも、Hashcashがあればスパムを抑える予備の手段が残る。
コメント、コードなど、何でもありがたく受け取る。いくつかのリメーラーでアルファ版を試してもらえると、なおありがたい。
アダム
--
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`
アダムへ
バーンスタイン博士が、Pentiumで数時間かけてmd5の56ビットの衝突を見つけたと発表したが、これはこの方式にどう影響するだろう。彼の投稿からは、既知のハッシュとの衝突を探していたのか、それとも指定した長さで衝突する二つの異なる文字列を探していただけなのか、はっきりしなかった。
アダム・バックの投稿（1997年3月28日16:52 UTC）（それから、私のSHA1の実装はビッグエンディアンのマシンで試していない。理屈の上では、バイトの並びを自動で判定する。）
ここでは問題なく動く。ビッグエンディアンのMips R10Kだ。
% ./sha1test
test 1
SHA1("abc") =
a9993e364706816aba3e25717850c26c9cd0d89d test ok
test 2
SHA1("abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq") =
84983e441c3bd26ebaae4aa1f95129e5e54670f1 test ok
test 3
SHA1("a" x 1,000,000) =
34aa973cd4c4daa4f61eeb2bdbad27316534016f test ok
% ./hashcash -t -22
speed: 70921 hashes per sec
find: 22 bit partial sha1 collision
estimate: 30 seconds— アニル・ダス
バーンスタイン博士が、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`