distributed.net戦記

(注)このテキストは2015年12月に開催されたコミックマーケット89にて頒布した同人誌(書いたのは私です)を転載したものです。文体や内容がサイトの他のコンテンツと馴染まないのはそのためです。

はじめに

コンピュータはとても計算がとても得意です。1秒間に何億回もの計算が出来ますのでそれは事実ですね。なのですが、世の中にある問題はコンピュータでも一筋縄でいかないものがたくさんあります。何兆回とか何京回もの計算が必要になることもあり、そうすると計算が終わるのに何ヶ月も何年もかかってしまいます。

何ヶ月くらいなら待つこともできますが、何年もとなるとちょっと待っていられません。問題によっては、何ヶ月でも待てません。明日の天気予報が1ヶ月後に計算できても意味がないですよね。ではどうしたらいいかというので考え出されたのが、複数のコンピュータを並べて分担して計算させることです。身近なところでは、PCやスマホのCPUのマルチコア。他にもクラスタとか並列コンピュータとかいろいろありますが、これらはみんな複数のコンピュータを並べて計算させているという点では違いはありません。スパコンも今ではこうした方式が主流ですね。

ではこれらの方式はなにが違うかというと、一つは結合の密度です。コンピュータ間の通信がどれくらいの速度で行えるか。どれくらい頻繁に通信が出来るか。マルチコアCPUは非常に高速に通信が行えます。スパコンなどもプロセッサ間の通信は専用の高速ネットワークが使われているそうです。クラスタなどになると通常のイーサネットが用いられることもあります。更に低速なインターネットが用いる場合、これを分散コンピュータと呼びます（厳密な定義ではありませんがとりあえず）。

頻繁に通信が出来るならお互いの計算結果に依存して次の計算を行うことが容易です。例えば天気予報では大気全体を一定の大きさの空間に区切って気温や湿度などを求めるのですが、その際に周囲の空間の気温や湿度の計算結果が必要になります。通信速度が遅いと、計算自体の速度よりも他のコンピュータからのデータ転送待ち時間の方が長くなってしまって、並列計算のメリットが打ち消されてしまいます。なので、天気予報の計算では高速な通信が出来るスパコンなどが用いられることになります。では通信速度の遅い分散コンピュータは役に立たないかというと、そんなことはありません。他の計算結果への依存が少ない命題なら通信速度が遅くてもそれほど問題になりません。

分散コンピュータはインターネット経由で接続されるわけですが、この接続されるコンピュータをボランティアで募集しようというアイデアがあります。これをグリッドコンピュータと言います（こちらもあまり厳密な定義ではありませんがとりあえず）。インターネットが広く普及するようになった1990年代後半頃から広まってきたアイデアです。自分で行いたい計算を行うのですから、そのためのコンピュータは自分で用意するのが通常です。そこをボランティアの提供するコンピュータに頼るというのは、当時のCPUの省電力技術の未熟さに一つの要因がありました。稼働しているコンピュータは実は大半の時間は待機中で、CPUはほとんど使われていません。当時は省電力技術がそれほど発達していませんでしたので、稼働中でも待機中でも消費電力に大きな違いはなかったのです。ならば遊ばせておくよりも何か別のことをさせた方が有効活用になるのではないだろうか。この余剰のコンピュータパワーを寄せ集めれば大きな計算力になるのではないか、というわけです。

ただし、この考え方は現代では通用しません。省電力技術の進歩により、待機中の消費電力を抑えることが出来るようになりました。また、仮想化技術の進歩により、稼働率に合わせて動的にコンピュータリソースを割り当てることも出来るようになってきました。つまり、現代においては余剰のコンピュータパワーというのはほとんど存在しません。なのでグリッドコンピュータ自体も過去の話になりつつあります。付け加えると、セキュリティ上の問題もあります。サーバが蓄えているデータが他者に漏洩すると大問題です。そのサーバ上で他者の作成した分散コンピュータ用のプログラムを動作させると、データが盗まれる可能性があります。

ということで、すっかり過去のものになってしまったグリッドコンピュータですが、現在でも続いているプロジェクトはいくつかあり、なかには顕著な成果をあげているものもあります。例によってとても長い前置きになってしまいましたが、この本はそうしたグリッドコンピュータ・プロジェクトの一つであるdistributed.netの歴史について語ってみようというものになります。ぜいぜい。だれか私に短くまとめる文章力をくれー

RC5

RSA社の暗号製品であるRC5暗号の解読を行うプロジェクトです。

きっかけはRSA社の主催する暗号解読コンテストです。暗号解読コンテストとは、自社の提供する暗号製品の強度を宣伝するために、賞金をかけた上で「解読できるものならやってみろ」とするコンテストです。ですが、このときのRSA社の目的は違いました。強度を誇るのではなく、逆に強度が不足することを証明して欲しかったのです。自社のRSA暗号は脆弱であるので実用に耐えないということを客観的に示したかったのです。

なぜ自社の製品が脆弱であると証明したかったのか。それは当時のアメリカが暗号製品に対して輸出規制を行っていたからです。強固な暗号技術は軍事にも利用されるため、アメリカとしては敵対国にそのような製品を使わせないように制限をかけていました。それはそれで一理ある話のなのですが、輸出制限があるためにRSA社は自社の強固な暗号製品をアメリカ国内でしか販売出来ません。RSA社としては商売の機会をより広げるために世界中に販売したいわけです。また、RSA社の暗号製品がアメリカ国内に留まっている間に、輸出制限の無い国の企業が開発した暗号製品が世界に広まって標準になることを恐れていたということもあるでしょう。ともかく、RSA社としては輸出制限を撤廃して欲しかった。そのために、当時輸出が許可されていた暗号製品では十分な強度がないということを示したかった。そのための暗号解読コンテストというわけです。

そのRSA社の呼びかけに応えたのがdistributed.netです。暗号解読の方法にはいろいろあるのですが、その一つがブルートフォースアタック＝総当たり法です。キャッシュカードの暗証番号を0000から9999まで全て試すような方法です。ブルートフォースアタックには強大な計算力が必要で、distributed.netはそこにグリッドコンピュータを用いたというわけです。

RC5プロジェクトの開始は1997年1月28日のことです。対象はRC5-56でした。56というのは暗号化に使用されている鍵のデータ長です。暗号では一般に鍵のデータ長が長いほど強固になります。計算は順調に進み、1997年10月22日に見事正解鍵を発見することが出来ました。ここまでの参加者は16,738人。全体の36.533%を計算したところでの発見でした。

RC5-56の次はRC5-64です。鍵長が8bit分長くなっていますので、解析対象の鍵は256倍に増えました。RC5-56の時の計算速度から単純計算すると、解読まで135年かかるということになります。もっとも、RC5解読では正解鍵を発見するのがどのタイミングかは運次第です。解読をスタートした直後に正解鍵を引き当てるという可能性もあり得ます。実際には、宝くじを当てるよりもあり得ない確率ですけれども。

RC5-56には多くの参加者がいましたので、当然にその中には日本人も居ました。しかし、日本でdistributed.netのことが広く知られていたわけではなかったのではないかと思います。というか、私は知りませんでした。私がdistributed.netのことを知ったのはRC5-64が始まってからのことで、1997年11月頃のFreeBSD-users-jpメーリングリストにおいてでした。FreeBSDユーザコミュニティでRC5-64に参加するチームが結成されましたので、私も最初はそちらに参加しました。

ちなみにですが、distributed.netにおけるチームへの参加は簡単です。チームメンバーの承認などは特に必要ありません。そのチームに入りたいと思ったら勝手に参加できるようになっています。このあたりの緩さもdistributed.netのチーム戦を盛り上げた一因ではないかと思います。

FreeBSD以外にも日本ではLinux、Windows NT、OS/2などのOSコミュニティが多くチームを作って参加しました。それ以外には、メールソフトコミュニティも多かったです。Becky、AL-mail、電信八号などなど。当時はOSとメールソフトがユーザコミュニティとして強かったということなのでしょうかね。

64ビットという複雑な鍵のため、RC5-64の解読には年月が掛かりました。参加者も飽き始めて、途中で離脱する人も多く現れるようになりました。もちろん、新規に参加する人もありますので、全体としてはそれなりの盛り上がりをみせていたと思います。

もう一つ、RC5-64解読では引きの悪さもありました。およそ1800京個の候補の鍵のうち、正解はたった一つです。その正解の鍵がどこに入っているかはわかりませんが、平均的には全体の半分を解読する頃には見つかってもおかしくありません。それが、全体の50%を過ぎても60%を過ぎても70%を過ぎても見つかりません。もしかしてプログラムにバグがあって正解を見過ごしてしまったのではないかという不安にも包まれる日々のなか、ついに正解鍵が発見されました。2002年7月14日のことです。全体の82.770%まで解析した時点でした。ただ、このときは正解鍵の確認に手間取ってしまったため、さらに2か月ほど解析は進み89.132%まで達してしまったのですけれど。

RC5-64が完了したら、次はRC5-72です。計算対象の鍵空間は更に256倍です。RC5-64の解読に1,726日掛かりましたので、RC5-72は単純に計算すると1200年かかることになります。ムーアの法則に期待するとしても非現実的な期間なので、個人的にはRC5-72はやらないんじゃないかなぁと思っていました。しかし、distributed.netのメンバーは平然とプロジェクトをスタートさせました。俺たちに出来ないことを平然とやってのける！そこにしびれる！あこがれる！！

RC5-72解読プロジェクトはスタートしましたが、当然ながら解読は遅々として進みません。いや、実際には進んでいるのですが全体に対する進捗としては非常に遅いということです。実際、プロジェクト開始から1年経った時点でも解析率は0.1%程度。このままでは本当に1000年掛かってしまいます。

それでも黙々と皆でRC5-72の解析を進めていたのですが、2007年に衝撃的なニュースが飛び込んできました。暗号解読コンテストの主催者であるRSA社がコンテストの中止を発表したのです。そもそもRSA社がコンテストを開催した目的は、アメリカ政府の暗号輸出規制の解除を訴えかけるものでした。distributed.netをはじめとした人々の努力の結果もあり、輸出規制は2000年には大幅に緩和されました。つまり、RSA社としてはコンテストの目的を果たしたので、これ以上続ける必要がなくなったわけです。

これに対してdistributed.netはどうするのか。暗号を解読して賞金を得るというのは大きなモチベーションではありましたが、実際の所として1万ドルという賞金額はプロジェクトの目的とするには少なすぎました。何万人もの参加者の人件費、使用するコンピュータリソースの構築・運用の費用などを考えると、全く持って見合っていません。それらの貢献は全てボランティアということで無償としても、distributed.netのスタッフの人件費やサーバ費用などもあります。何年ものプロジェクトの継続に対して報酬が1万ドルでは全く見合っていませんね。それに、distributed.netの目的自体が変質してきた点もあります。設立当初は賞金目当てであったかもしれませんが、現在はグリッドコンピューティングの構築・運用の検証プロジェクト的な性格が強くなってきました。そう考えると、賞金が出ないこと自体はdistributed.netにとっては問題ではないということです。その結果、RC5-72の解読プロジェクトはそのまま継続されることになりました。

次に飛び込んできた大きなニュースは2009年01月のGPUクライアントリリースです。GPUはスパコンでも使用されているように、比較的単純な演算を高速にこなすことが出来ます。出来ることが違いがありますからGPUがCPUより偉いというわけではありませんが、単純な計算に限って言えばGPUの方が偉いとは言えるでしょう。そして、GPUへの対応はRC5-72プロジェクトにおいても顕著な効果を表しました。それまでCPUでの解読は毎秒数百万鍵程度しか行えなかったのですが、GPUでは数千万から数十億程度の解読が行えるようになったのです。distributed.netの参加者コミュニティは大興奮です。毎日のように誰かが新しいビデオカードを購入して解析レートを報告するという、一種の祭りのような状態になりました。こうして、distributed.netは大きく加速をすることが出来たのです。

そうして迎えたのが2010年8月26日。この日にようやく全鍵空間の1%の解析が完了しました。プロジェクト開始から2824日、約8年掛かってのマイルストーンでした。その後はGPUによる加速効果が大きく、2%の到達は2011年11月21日、3%の到達は2013年10月29日のことです。この原稿を書いている2015年12月14日時点では全体の3.839%の解析が完了しています。1%から2%のときの解析速度に比べると、それ以降の速度は低下していますが、これは参加者の減少のためだと思われます。過去に一度でも参加したことのある人は110､854アカウントに上るのですが、昨日に解析結果を返却したアカウントはわずか1967です。distributed.net自体がスタートしてから18年も経過したわけです。当初から継続して参加している人はごくわずかでしょう。では新規に参加するという人は居なくはないのでしょうが、冒頭で書きましたとおりグリッドコンピューティング自体が下火になりましたから、その数はわずかだと思われます。そのような状況ではありますが、distributed.netの主催者はそんなことはどこ吹く風で運営を続けています。おそらくは今後も同じような調子で、ずっと運営が続いていき、いつかはRC5-72の解読がなされるのではないかと思います。

DES/CSC

distributed.netではRC5以外の暗号解読コンテストにも参加しています。これまでに行われたのは、DESとCSCです。

DES＝Data Encryption Standardはその名の通り、標準化された暗号アルゴリズムです。多くの環境で実装されており広く使われているのですが、いかんせん設計されたのが1970年代と古い。その当時のコンピュータの性能を基準に設計されていますので、現代のコンピュータであれば容易に解読が出来てしまいます。実際、AESが2001年に策定され、DESは標準の座からは降りています。

そんなDESが実際にどれくらい危険であるかを実証する解読コンテストというわけです。1回目の挑戦は1997年6月17日にDESCHALLによって完了しています。解析には96日掛かっています。

2回目からはdistributed.netも挑戦しています。1998年1月13日に開始され、2月23日に解読に成功しました。3回目の挑戦は1998年7月13日に開始され、わずか3日後に解読されています。ただ、このときに解読に成功したのはdistributed.netではなく電子フロンティア財団の開発したDeep Crackという「にやっ」としてしまう名前のDES解読専用コンピュータでした。

蛇足ではありますがDeep Crackがなぜ「にやっ」とする名前かというのを解説しておきますと、1997年にチェスの世界チャンピオンを破ったシステムの名前がDeep Blueというのですね。

DES解読コンテストは更に開催されまして3回目です。このときはdistributed.netと電子フロンティア財団のDeep Crackが共闘することになりました。最強タッグの誕生ですね。前回が3日間で解読されていますので、今度は更に短期間で終了することが予想されます。グリッドコンピューティングではサーバから解析空間をクライアントに割り当てるのですが、重複を避けるために一度割り当てられた解析空間は他のクライアントには割り振られません。この状態でクライアントが計算完了まで長時間掛かってしまうと、全体の解析がその遅いクライアントに律速してしまうという問題が起こります。そこで、ボランティアによるプロジェクトとしては異例ですが、計算速度の遅いクライアントはDES解析に参加しないで欲しいという要望まで出されました。

そしていよいよ1998年1月18日、コンテストが開始されました。とにかく時間勝負です。解析空間を割り当てられたクライアントは出来るだけ早く計算結果を返さなければなりません。手に汗握る緊張の時間が経過し、コンテスト開始から22時間後に正解鍵が発見されたのでした。

22時間でDESが解読されたといっても、専用コンピュータとグリッドシステムを組み合わせてようやく行われたに過ぎません。しかし、日進月歩で進化するコンピュータにおいては、それが容易に手に入れられる時代はそれほど遠いことではないでしょう。コンテストから16年が経過した2015年において、DES解読に必要なシステムは個人レベルでも頑張れば構築可能ではないかと思われます。個人でも可能ということは、大企業や国家機関などにとってはDESは平文と変わらないということです。一時代を築いたDESですが、その役割を終え、表舞台から立ち去るときがやってきたのです。

CSCはCS Communications and Systems社の暗号製品です。こちらの会社が暗号解読コンテストを開催したために、distributed.netが挑戦。1999年11月16日に開始し、2000年1月15日に解読に成功しています。

OGR

数論上の問題であるOGRを求めるプロジェクトです。RC5/DES/CSCとは違い、こちらは正解をまだ誰も知らない、未解決の問題を解くプロジェクトになります。

OGR＝最適ゴロム定規とは、ゴロム定規のうちのもっとも短いものを言います。ではゴロム定規とは何かというと、構成する数の差がすべて異なる数列のことを言います。例えば、0-1-2という数列は、0と1の差と1と2の差が同じなのでゴロム定規ではありません。0-1-3だと、0と1の差、0と3の差、1と3の差の全てが違いますからゴロム定規です。差が違えばいいので、0-1-4も0-1-5もゴロム定規です。実際の所、ゴロム定規が無限に存在するのですが、そのうちもっとも短いものを最適ゴロム定規と呼びます。0-1-3は長さ3の最適ゴロム定規です。

ゴロム定規であるかどうかを確かめるには数列を構成する全ての数の差を比較しないといけませんので、総当たり法になります。候補となる数列の列挙も総当たり法に近くなります。なぜなら、どういう条件であればGRになるかという数学的な法則が見つかっていないので、あり得るパターンを全て検証するしか方法がないのです。長さが長くなるほど候補となる数列は増えますので計算量が膨大になり求めるのが困難になります。OGRプロジェクトが開始された時点においてはOGR-23までしか求まっておらず、それ以上は未知の領域でした。

ということで、OGR-24の探索がスタートしたのは2000年2月15日のことでした。暗号解読では探索対象のなかから偶然にでも正解鍵を発見すれば解読終了ですが、OGRの場合は全候補を検証しなければならないため、運の良さに期待することは出来ません。とにかく全探索を行うしかないのです。

OGR-24は開始から4年強が経過した2004年10月13日にようやく全探索が完了し、確定することが出来ました。ちなみに確定した結果は0-9-33-37-38-97-122-129-140-142-152-191-205-208-252-278-286-326-332-353-368-384-403-425というものでした。

OGR-24と平行してOGR-25の探索も行われました。こちらは当然のことながらOGR-24よりも時間が掛かりまして、探索が開始されてから約8年後の2008年10月24日に探索が完了しています。確定したOGR-25は0-12-29-39-72-91-146-157-160-161-166-191-207-214-258-290-316-354-372-394-396-431-459-467-480というものでした。

このままいくとOGR-26はとんでもない時間が必要になってしまうところだったのですが、ここで救世主が登場します。計算するクライアントソフトが改良され、速度が劇的に向上したのです。具体的になにがどのように改良されたのかは定かではありませんが、メモリが潤沢に使用できるようになったので、メモリ使用量を増やして高速化したとのことです。確かにOGRのスタートした頃に比べればメモリは圧倒的に低価格化大容量化が進みましたからね。

このクライアントの改良の効果が素晴らしく、OGR-26の探索はわずか121日で完了しました。2009年2月24日のことです。確定したOGR-26は0-1-33-83-104-110-124-163-185-200-203-249-251-258-314-318-343-356-386-430-440-456-464-475-487-492というものでした。

引き続きOGR-27の探索が開始されましたが、改良されたクライアントでもてこずる計算量で、完了したのはプロジェクト開始から約5年が経過した2014年2月19日のことです。OGR-27は0-3-15-41-66-95-97-106-142-152-220-221-225-242-295-330-338-354-382-388-402-415-486-504-523-546-553というものでした。OGR-27の次はOGR-28ということで、現在はこちらが探索対象になっています。探索完了は2030年頃になると予測されています。

OGR自体には直接関係がないのですが、主に日本のコミュニティで「ちびすた・でかすた」というお遊びが誕生したこともご紹介しておきます。

グリッドコンピューティングでは全計算対象を分割して各クライアントに割り振ります。このとき、割り振られたブロックによって計算量が変わってくることがあります。OGRの場合、最初の数個の数列が固定されてブロックが作られるのですが、そのブロックで候補の数列がいくつ存在するかは実際に計算してみないとわからないのです。その違いが多少ならいいのですが、時には何万倍もの違いがありました。つまり、同じマシンで計算しても、あるブロックは数分で完了するのに、別のブロックだと何日もかかったりということがあるのです。この違いが面白いということで、自分の処理したブロックの大小を比較するという遊びが流行りました。OGRではブロックのことをスタブと呼びますので、大きなスタブを「でかすた」、小さなスタブを「ちびすた」と呼ぶのです。熱心な方になると偶然による引き当てでは飽き足らず、スタブサイズの傾向とスタブ配布サーバの配布傾向を調べ、特定のスタブが配信されるタイミングで集中的にスタブを取得したりもしていたそうです。

その他のグリッドコンピューティングプロジェクト

distributed.net以外にもグリッドコンピューティングプロジェクトは多数存在します。ここではそのうちのいくつかを紹介したいと思います。

GIMPSは1996年とグリッドコンピューティングの歴史のなかでもかなり初期から存在するプロジェクトです。

distributed.net戦記

はじめに

RC5

DES/CSC

OGR

その他のグリッドコンピューティングプロジェクト

SETI@home

BOINC

GIMPS