ビットコイン・インスティテュート

Mixmaster and remailers — ランス・コットレル​(1995年1月)

これは、Mixmasterとリメーラー全般についての論考の、テキスト版だ。これをHTMLにして自分のホームページに載せるつもりだ。今日のサンディエゴのサイファーパンクの集まりで配ったMac版の原本(Word 5.0)が欲しければ、知らせてほしい。メーリングリストのソフトウェアが、MIMEエンコードして投稿しようとすると何度もはねつけてくる。図はHTML版に載せるほか、Mac版にも入っている。


**サイファーパンクのリメーラー。

現在のリメーラーのメッセージは、暗号化されたメッセージが入れ子になった構造をしている。それぞれのメッセージはリメーラー宛てに暗号化される。メッセージには各リメーラーへの指示(次にどこへ送るかなど)と、転送するメッセージが入っている。各リメーラーは暗号化の層と、それに付随する指示を一つ取り除き、指定された処理を行ってから、次の宛先へメッセージを送る。

Figure 1

上の図は、3つのリメーラー(A、B、C)を経由し、最後にボブへ送られるメッセージを図にしたものだ。箱は暗号化を表し、誰宛てに暗号化されているかは箱の左上の外側に記されている。この図からすぐに分かる重要な点がある。メッセージは中継のたびに小さくなる。

サイファーパンクのリメーラーには、次のような機能がある。

  • 別のメールアドレスへメッセージを送るか、新しいグループへ投稿する。
  • 暗号化されたメッセージを受け取り、暗号化された封筒の中に隠された処理指示に従う。
  • メールヘッダーをすべて(または少なくとも一部)取り除く。
  • 件名行などの新しいヘッダーを加える。
  • メッセージ末尾の情報を一部取り除く。
  • メッセージの一部を、メッセージで指定された鍵を使って暗号化する。

リメーラーによっては、さらに次の処理もできる。

  • メッセージを一定時間、またはランダムな時間だけ保留する(遅延)。
  • リメーラー内に常に一定数以上のメッセージがある状態を保ちながら、メッセージの順序を入れ替える。

**サイファーパンクのリメーラーへの攻撃。

匿名リメーラーは通信解析を防ぐよう設計されている。その弱点を理解するには、攻撃者がどんな攻撃を仕掛けるかを調べるのが一番だ。最悪の状況を示すため、また第二世代のリメーラーならこうした攻撃に対抗できるため、ここでは非常に強力な攻撃者を想定する。

*脅威モデル。

攻撃者は、すべてのリメーラーに出入りするメッセージの内容と、到着・出発時刻を記録できるとする。送信者のマシンから出るときも、宛先に届くときも、すべてのメッセージが監視される。攻撃者は、傍受したメッセージを含め、リメーラーを通るメッセージを無制限に送れる。メッセージを宛先に届かないよう妨害することもできる(サービス妨害)。攻撃者は一部のリメーラーを侵害しているが、すべてではない。侵害したリメーラーを通るメッセージについては、攻撃者は送信元も宛先も内容もすべて知っている。攻撃者が持つ能力と資源の組み合わせを、脅威モデルと呼ぶ。

*単純な攻撃。

脅威モデルを踏まえれば、暗号化されていないメッセージを追跡できるのは言うまでもない。そこで、暗号化された通信だけを考える。リメーラーを一つしか使わない場合も安全ではない。そのリメーラーが侵害されれば、運営者には送信元と最終宛先の両方が分かるため、何の安全も得られない。

*順序の入れ替え。

暗号化したメッセージを複数のリメーラーに通せば改善するが、それでも弱点は残る。受信したメッセージは処理の直後に転送されるため、経路をたどられてしまう。メッセージが届くと、別のメッセージがすぐに出ていく。ほかに何の情報がなくても、また送り手がどんな用心をしていても、攻撃者には、届いたメッセージと出ていったメッセージが同じものだと分かる。メールの記録が残っていれば、あとから遡って調べることさえできる。

これが標準的なサイファーパンクのリメーラーにとって最大の問題だ。最初に提案された対策は、受け取ったメッセージをランダムな時間だけ遅らせることだった。遅延時間がメッセージの到着間隔より長ければ、どの受信メッセージがどの送信メッセージに対応するのか、確実には分からなくなる。しかし、この提案には弱点がいくつかある。遅延でどれほど守れるのかは、はっきりしない。そのときどきにリメーラーを通る通信量によって変わるからだ。平均保留時間のあいだに多くのメッセージが届けば、どれが対象かはかなり分かりにくくなる。一方、通常の変動、ネットワーク障害、サービス妨害攻撃などで通信量がごく少なければ、ほとんど、あるいはまったく守れない。通常の通信量の変動だけを考えて最低限の保護を確保するにも、最大通信量のときに必要な時間より、はるかに長く遅らせなければならない。

順序を入れ替えればこの問題は解決するが、別の攻撃を招く。順序を入れ替えるには、リメーラー内に一定数のメッセージを常に保管しておく必要がある。これをメッセージの「プール」と呼ぶ。最も効率のよい方式は、プールにN件を保ち、新しいメッセージが届くたびに、今届いた分も含むN+1件の中から一件をランダムに選んで送る方法だ。残念ながら、この方式は「スパム」攻撃に弱い。

攻撃者は、N件を大きく上回るメッセージをリメーラーへ送る。するとプール内の本物のメッセージはすべて押し出され、攻撃者が見分けられるメッセージだけが残る。N件を大きく上回るメッセージを送れば、プールは攻撃者が仕込んだメッセージだけになる(攻撃者はそれらを見分けられる)。あなたのメッセージが届いたあと、攻撃者がさらにメッセージをまとめて送れば、あなたのメッセージはプールから押し出される。攻撃者は自分のメッセージを見分けられるので、あなたのメッセージだけが明らかになる。

遅延と順序の入れ替えを組み合わせれば、この攻撃への耐性が得られる。新しいメッセージが届くたびにプールから一件を送るのではなく、定期的に、N件を除くすべてのメッセージを送る。送り出しから次の送り出しまでのあいだに、平均して本物のメッセージがいくつか届いていれば、攻撃者にプールの中身を全部押し出されても、攻撃者のメッセージに混ざって出ていくのは、あなたのメッセージだけではない。

攻撃者がスパムとサービス妨害攻撃を組み合わせれば、あなたのメッセージだけが、再び攻撃者のものではない唯一のメッセージになる。あなたのメッセージだけがリメーラーのネットワーク全体を通るよう攻撃者が仕向けられるなら、打つ手はない。理想的なリメーラーなら、同じ時刻にどこかのリメーラーを通っているメッセージのどれもが、あなたのメッセージでありうる。しかし、あなたのメッセージだけがリメーラーのネットワークを通っているなら、もうおしまいだ。

*サイズと見分けやすさ。

では、あなたのメッセージが、中継のたびに遅延と順序の入れ替えを行うリメーラーを順に通っていくとしよう。それでもサイズから追跡できる。通常、メッセージは中継のたびに、少しずつ小さくなる。その減少量はおおよそ分かっている。あなたのメッセージがリメーラーの中でほかのメッセージとよく混ざっていても、そしてほかのメッセージのサイズがまちまちであっても、あなたのメッセージはやはり見分けられる。リメーラーが中継ごとにメッセージのパディングを取り除くことはできるが、そうするとサイズが小さくなるだけで、実際に送りたいメッセージの長さより小さくはできない。制約はもう一つある。見分けにくさを最大にするには、中継のたびに、メッセージのサイズを、元のサイズの何割も変えなければならない。そのため、極端に大きなメッセージは目立ってしまう。各段階でパディングを取り除けば通信解析はずっと難しくなるが、情報は漏れる。リメーラーから出ていくメッセージのうち、到着時のあなたのメッセージより大きいものは、どれもあなたのものではないと分かる。また、この機能を使う人が少なければ、サイズの変わり方がほかと違うただ一つのメッセージとして目立ってしまう。解決策は明らかだ。すべてのメッセージをまったく同じサイズにすればよい。

*再送攻撃。

残念ながら、順序を入れ替えて見分けにくくしたメッセージでも追跡される。この攻撃を使えば、メッセージを最終宛先まで追うことも、末端から元の送信者へ遡ることもできる。どちらの手法も、一種のスパム攻撃を使う。メッセージをリメーラーの連鎖に沿って先へ追うには、攻撃者があなたのメッセージを捕まえ、そのコピーを大量に最初のリメーラーへ送る。すると同一のメッセージが大量にリメーラーから出て、次のリメーラーへ進む。リメーラーの通信量に現れるこの急増から、メッセージの経路が分かる。順序の入れ替えでコピーが散らばりすぎたら、2つのリメーラーのあいだでメッセージを捕まえ、その地点から大量のコピーをもう一度送り込めばよい。

この攻撃を防ぐには、リメーラーが同じメッセージを二度以上送らないようにしなければならない。それには、中継のたびに使うランダムな識別番号をメッセージに入れておき、リメーラーにその番号を記録させればよい。だが、リメーラーの記憶領域を大きく消費する。古い識別番号を一覧から削除したり、リメーラーの鍵を定期的に変更して(その時点で一覧を消去できる)影響を抑えることはできる。もっとよい方法は、各層に匿名の電子キャッシュの切手を付けることだ。メッセージが再送されれば、その電子キャッシュは二重支払いされたことになり、リメーラーは送信を拒否する。これならスパムにも費用がかかり、リメーラーの運営者が質の高いサービスを提供する動機にもなる。

**Mixmaster。

タイプ2のリメーラーはMixmasterだけだ。その設計思想は、チャウムのデジタルミックスについての論文から大きな影響を受けている(名前の由来でもある)。以下はMixmasterパケットの構造を図にしたものだ。ヘッダーは4つではなく、実際には20個ある。メッセージは1個以上のパケットとして送る(複数のパケットからなるメッセージをマルチパートメッセージと呼ぶ)。

Figure 2

リメーラーAはこのメッセージを受け取ると、最上部のPGP暗号化パケットを復号し、その識別番号を以前に見たことがあるか調べる。見覚えがあれば、メッセージを破棄する。復号前の最初のヘッダーをヘッダー一覧の末尾に加え、ほかのヘッダーを一つずつ上へずらす。すべてのヘッダーと本文パケット(末尾にある、送信するテキストの部分)を、ヘッダー内のIDEA鍵で復号する。すると最上部に、次のリメーラー宛てのPGP暗号化ヘッダーが現れ、古い最上部のヘッダーは(スタックの一番下へ移ったので)見えなくなる。

連鎖の最後のリメーラー向けのヘッダーには、これが最後の中継地点であることを示すフラグと、このパケットがマルチパートメッセージの一部かどうかを示すフラグが入っている。パケットにメッセージ全体が含まれていれば(マルチパートメッセージではなければ)、本文を復号して平文を順序入れ替え用のプールに入れ、送信できる状態にする。一部のパケットだけなら、他の部分が届くたびにメッセージIDで照合する。すべてそろうとメッセージを組み立て、プールに入れる。制限時間内にそろわなければ、メッセージは破棄される。複数のリメーラーパケットが一つのメッセージの一部だと分かるのは、連鎖の最後のリメーラーだけだ。それ以外のリメーラーには、それぞれが完全に独立したパケットに見える。

Mixmasterのパケットはすべてまったく同じ長さで、すべてのビットが中継のたびにIDEA鍵で暗号化される。そのため、監視する者は、どれがどのメッセージなのかを知る手がかりを何も得られない。リメーラーが侵害されていても、そのリメーラーが分かるのは前後の接続先だけだ。最終中継地点でない限り、何段を経てきたかも、このあと何段進むかも分からない。

パケットはかなり大きい。20個のヘッダーはそれぞれ512バイトで、本文は10キロバイトある。マルチパートメッセージが必要になる頻度を抑えるため、平文は圧縮される。マルチパートメッセージはすべての部分が同じリメーラーの経路を通るため、いくらか安全性が低い。

*今後の機能。

近いうちに、Mixmasterの利用者向け画面から、マルチパートメッセージの各パケットを別々の経路に送れるようになる。ソケット接続を受け付けると示したMixmasterリメーラー同士は、メッセージを直接やり取りする。メッセージはディフィー・ヘルマン鍵交換から導いたIDEA鍵でさらに暗号化される。これにより、傍受されたメッセージの復号をリメーラー運営者に求められても、過去の通信を守れる。

**完璧なものはない。

完璧なリメーラーネットワークを使っていても、追跡されることはある。リメーラーのネットワークを一日に通るメッセージの数には、限りがある。アリスがメッセージを送る時刻とボブが受け取る時刻が重なるなら、アリスがボブに送っている可能性は高い。この問題は、ハルとルイス・サイファーが何通かの投稿でかなり詳しく論じていた。対策の一つは、リメーラーの「ブランブル」にダミーのメッセージを送り込み、自分の送信がどの受信とも時刻が重なるようにしておくことだ。本物のメッセージが目立たないよう、ダミーはランダムな時刻に送らなければならない。

--------------------------------------------------
Lance Cottrell  who does not speak for CASS/UCSD
loki@nately.ucsd.edu
PGP 2.6 key available by finger or server. Encrypted mail welcome.
Home page http://nately.ucsd.edu/~loki/
Home of "chain" the remailer chaining script.
For anon remailer info, mail remailer@nately.ucsd.edu Subject: remailer-help

"Love is a snowmobile racing across the tundra.  Suddenly
it flips over, pinning you underneath.  At night the ice
weasels come."
                        --Nietzsche

原典の外部ソース

https://mailing-list-archive.cryptoanarchy.wiki/archive/1995/01/271e1e09ac5a7290a402216001b4e5dea3e944c5901b5da8d520726e9253ad15/
1995年1月27日金曜01:14:42 PST(09:14:42 UTC)のサイファーパンクメーリングリストへの投稿。本文は2026年11月20日にcryptoanarchy.wikiの保管庫から取得した。文字だけの版のため、Figure 1とFigure 2の図そのものは含まれていない。