RC5 Crackingとは

これは RSA Data Security 社(日本法人のページもあります。)が開催したもので、 RC5 という暗号を破るコンテストです。暗号破りコンテストというと なんだかヤバそうですが、 もちろん道義的な面でも法律的な面でもまったく問題ありません。 RSA 社が用意したコンテスト用の問題を、 だれがどれだけ早く解けるかを競うだけです。いままで何回も開かれています。

そもそもなぜこんなコンテストを RSA が開いているかというと、 短い鍵の危険性を訴えるためです。現に、 いままで解かれた暗号はぜんぶ鍵が短いものばかりで、 長い鍵の問題はまだ解かれていません。 じゃあ、なんで長い鍵を使わないの? と思うのですが、 使わないのではなく使えないのです。
アメリカは、暗号は武器だと見なしているので、 長い鍵長の暗号を輸出すると武器輸出管理法などにひっかかってしまいます。

目的なんか人それぞれで、ここで書いているのは RSA 社の目的です。 実際に参加している人の目的はさまざまです。輸出規制に反対したい人から、 ベンチマークがわりにしている人もいますね。それで十分だと思います。
ふつーの Linux ユーザにとっては、Linux 関係のプロジェクトに ごく簡単に協力できるのが魅力ですね。

そのためアメリカから輸出される製品の暗号は、 わざと弱くなっています。たとえば Netscape Navigator は、 クレジットカードの番号を送信するなどのために通信を暗号化できますが、 その暗号も弱いもので、強力な演算能力を持つコンピュータや たくさんのコンピュータを使えば、すぐに解けてしまいます。
(アメリカ国内版だと強力な暗号が使えますが、日本に持ち出すのは違法。)

というわけで、RSA 社はコンテストの暗号をさっさと解読してもらって、 長い鍵の必要性をアメリカ政府に訴えたいわけですね。

で、暗号を解く方法というのは、鍵を総当たりで調べるだけという、

単純でかなり力技な方法

です。

これはどういうことかというと、たとえば、 暗証番号のわからないカードを持っているとしましょう。
このカードで金を下ろしたくてしょうがありません。
そこで ATM (銀行にあるマシンのほうです。取り違えないように :) ) の前まで行ってみましたが、やっぱり暗証番号は分かりません。
カードを入れてみました。スピーカから「暗証番号を押してください」 と声がします。
そうだ! 暗証番号は4ケタだから、0000 から 9999 まで 10000回試せば金を引き出せるはず。

これが「総当たりで暗号を解く」ということです。
(実際には、何回も間違えると、ATM がカードを受けつけなくなりますけどね。)

この例で、なぜ短い鍵が危険かもすぐ分かります。暗証番号が 1ケタだと、0 から 9までたった10通り試すだけで解けてしまいます。 逆に10 ケタにすると 0,000,000,000から 9,999,999,999まで 10,000,000,000通り試す必要があるので、もう解くのはほとんど無理です。

このコンテストで使われる暗号は鍵長 64bit ですから、鍵のパターンは 2 の 64乗 = 18,446,744,073,709,551,616 もあります。 その中に正解は一つだけです。 これを現実で例えると、
「地球上のどこかに落ちた直径6mmのコンタクトレンズを探すくらいの困難さ」 です。地球の表面積とコンタクトレンズの面積の比が、 だいたい 2⁶⁴ : 1 に等しいです。
コンタクトレンズなんて足元に落ちていても見つかりゃしないのに、 地球の全表面だなんてどーしていいもんだか...。

ところが、 膨大な数のコンピュータを使えばまったく不可能というわけでもありません。 全パターン鍵を一定の範囲ごとに区切って、 みんなで分担して調べればなんとかなるのです。

われわれはみんなで、 地球のどこかに落ちているコンタクトレンズを探そうとしているのです。
# と、カッコつけてみる :)

この方法で暗号を解くには、鍵を次々に試してくれるプログラムがいりますね。 distributed.netという組織 がプログラムを用意しています。 プログラムはサーバとクライアントに分かれていて、 クライアントはサーバから一定の鍵の範囲を割り振ってもらい、 そのなかに正しい鍵があるかどうかを調べてから、結果をサーバに送ります。 もちろん、ほぼすべてハズレです。

クライアントの台数を増やしていけば、それだけ早くとけます。

いちばん肝心なところは、distributed.net はチーム制を取っているというところでしょう。 参加者はチームに参加します (どこにも参加せずに一匹狼でもかまいませんけど ;) )。
チームは、それぞれの順位 (いままでに調べた鍵の数) を競っています。 これが結構たのしいので、JLUG チームなるものを作って参加したら、 あれよあれよというまにだいたい2000チームあるなかで 2位までいってしまいました。

今はちょっと順位が下がりましたが、まだまだ上位です。がんばりましょう。

ちなみに、もっと違ったチームもたくさんあります。 Chandra ユーザが集まったチームとか、飲み屋仲間で作ったチームとか...

実際には何をするのか

鍵解読用のクライアントをインストールして、ちょっと設定します。 人間がするのはこれだけです :)

このクライアントが行うことは、鍵サーバから鍵を割りあててもらい、 その範囲内の鍵を総当たりで調べたあとに、鍵サーバに結果を報告します。 クライアントがやってることもこれだけです。

だから、鍵をやりとりするときだけInternetに接続していればいいのです。 また取得した鍵をためておけますから、たとえば500ブロック鍵サーバから もらえば、僕のマシンだと2週間はもちます。すくなくとも 2週間おきに接続すればいいということです。
メールのやりとりと一緒に鍵をもらえばいいでしょう。 そうすれば余計な電話代はかかりません。

しかもこのクライアントは最低の優先度で動くので、マシンが 空いてるときだけ動作します。 つまり、他のプログラムが動いている時は、その邪魔をしないようにできています。 この文章もクライアントが 動いているマシンで書いていますが、べつに遅くなっていません。
というか、動かしているのを忘れていました:)

むしろこのコンテストは「余って捨てているCPU時間を有効活用できる」 と言えるでしょう。どんなマシンでも、「CPU使用率 100%の瞬間」 ほぼすなわち 「マシンを完全活用している瞬間」はごくわずかです。 ふつうの状態では、使用率はほとんど 0% ですからねえ。 これはもったいない。さあ、もっとマシンを有効に使いませう :-)。

完全自動で動くようにクライアントを設定すると、 まさにどうでもよくなります。これは楽です。

参加するには

設定は簡単です。どんな OS で参加してもかまいません。 Internetに常時接続している必要もありません。 このページを見れるマシンと環境を持っているということは、あなたは 参加できるということです。

クライアントを動かす方法はここをご覧ください。

メイリングリスト

JLUG の RC5 攻撃用メイリングリストができました。参加するには、 rc5-ml-ctl@linux.or.jp へ本文を # guide としたメールを送ってください。返信メールの指示に従っ てメイリングリストに参加することになります。 メイリングリスト本体は rc5-ml@linux.or.jp です。

コンテストの賞金は

RSAからの全体の賞金は$10,000です。そのうち、発見したグループに $1,000、 JLUGチームが使っているクライアントは distributed.net が作ったので distributed.net に$2,000、 非営利団体への寄付が $6,000、そ、そ、そしてなんと、発見者個人に $1,000 もらえます。

JLUG チームが発見した場合は、もらった$1,000を JLUG に寄付します。 JLUG チームはかなり大きいので、発見の可能性はそれなりに高いでしょう。 こんなにランクが上にいるのはみなさんのおかげです。 どうもありがとうございます。