今年の6月に「DES がたった3日半で解けた」と、大ニュースになったが、これの意義は、原理的には分かっていたこと – 実質鍵長をうまく減らしてやれば、Brute Force Effort でもかなり効率よく鍵を見つけ出すことができる – を、実際にやってみせたことにある。この実験の意味することは、DESが危ないというのではなく、どのような暗号を使うときにも、必ず実質鍵長を考えて使わなくてはならないということである。
暗号の強度を上げる方法はさまざまだが、それには費用がかかる。暗号化を含むセキュリティは、情報の重要度をクラス分け(Classify) するところから始まると言える。
EFFのDES Cracker
今年の6月に「DES がたった3日半で解けた」と、大ニュースになりました。解いたのは、Electronic Freedom Foundation (EFF)と呼ばれる団体で、1年半かけて専用チップを多数搭載したマシンを作り、3日半で RSA の DES Challenge を破りました。
これには、Plain Text Attack という方法がとられました。費用は $250,000 と言われており、そのうち人件費は $80,000 とされていますが、もちろん、これではパートタイムとは言え10人の人を1年半働かせることはできないので、 この他に1年半分の人件費がかかっているといえます。
とはいえ、おそらく $1,000,000 もあれば、数日で DES の Key を発見することができるマシンは十分作ることができるでしょう。これは、たまたま DES ですが、実は他の暗号化に関しても同様のことが言えます。 ちなみに、彼らの試算によると、金に糸目をつけなければ、数秒で鍵を一つ解くマシンを作ることは比較的容易だそうです。昔から、DESは政府が解きやすいような特別な仕掛けがしてあると言われてきましたが、何もそんなことをせずとも、金で解決できているはずであることを、彼らは証明しました。
DES（および他のブロック暗号）の解き方
まずは、DES（及び他の暗号）の解き方です。なお、ここではDESを例に取りますが、他の block 暗号でも同様です。（ちなみに、ストリーム暗号の方が解きやすいらしいです。）
基本的には2段階で解きます。
第一段階はハードウェアで、明らかに違うと思われるキーを除外します。
その上で、第二段階として、ソフトウェアで残りのキーを捜します。
明らかに違うキーを除外する方法は以下のようです。
まず、テキストを 16byte づつに切り分けます。それを、8byteづつに2分割します。作業は、最初の8 byte から始めます。
まず、最初の1 byte を与えられたキーで decrypt します。それが “interesting” であれば、次の 1 byte を decode します。ここで、”interesting” というのは、予想される文字コードスペースに decode した結果が入っていると言うことです。たとえば、元のテキストが [A-Z][a-z][0-9]と、2つの句読点しか含まないと仮定すれば、decode した結果がinteresting である確率は、62/256=1/4しかないことになります。（間違ったキーであれば、256の文字がランダムに現れると考えられます。）これが、interestingであれば、次の1byteについて同じ作業を行います。これも interesting であれば、次も同じことをやります。8byte 検査したときに interesting とレポートされるのは、わずかに 1/(48) になります。次の8 byte についても同じことを行います。両方とも interesting である確率は、(1/(48))2 になります。これで、software がチェックしなければならない key の数は、224 になりました。256に比べると、格段の進歩です。
あとは、この 224 について、出てきた text を辞書と比べて、正しいと思われる text かどうかを割り出すことになります。これが第二段階です。この処理がボトルネックになりますから、ここを如何に少なく押さえられるかが、一つの勝負どころです。
これによって、DES Cracker は、3日ちょいで全テキストの解読に成功しました。 これが、Plain Text Attack と呼ばれる方法です。
更に効果的な方法に Known Plain Text Attack というものがあります。 これは、その暗号化されたブロックの中のある場所に、あらかじめ分かっているtext がある場合です。この場合、上記の 62/256 は、1/256 になります。すると、software がチェックしなければならない Key の数は、
((1/28)2)8*2128 = 1
になります。つまり、ソフトでチェックする必要はたとえ key が 128bit でも無くなるのです。
(Known) Plain Text Attack の持つ意味
この (Known) Plain Text Attack の持つ意味は重大です。なぜならば、多くの場合、あらかじめどこに特定のテキストが入っているか分かっている場合が多いからです。たとえば、MS Word のドキュメントは特定の文字列から始まりますし、Web などでも、リクエストは GET から始まります。Mail だったら、From で始まっている場合が多いですし、このような例は枚挙にいとまがありません。つまり、メッセージごとの暗号化は実はあまり意味が無い可能性があると言うことです。
更に、単純なトンネリングしたような場合、IP header がデータ部に暗号化して入っているので、そこに対して Plain Text Attack をかけることができます。したがって、トンネリングをすると、暗号の強度が下がることになります。IP Address が見えなくなるからトンネリングをした方が良いような気がしますが、暗号の仕組みを考えると、全く逆であることがわかります。
つまり、暗号化はやれば良いと言う物ではないのです。 Key の長さが長くても、実質的な Key Space が狭ければ意味がありません。だから、Key の長さだけで暗号化の強度を云々するのはナンセンスなのです。ちなみに、実質的なKey Space は、上記のようなことに加えて、暗号化のアルゴリズムにも依存します。たとえばRSA暗号は、因数分解の困難さに依存していますが、現在 100桁程度の数は正しく因数分解されています。2128 は39桁の数字ですから、RSA暗号における128bit key というのは、全く不十分と言えます。（これに対し、IDEAなどの128bitは、かなり安全です。）
いずれにせよ、暗号化でセキュリティを守ると言うのは、きちんとしたデザインが必要な分野です。
どのように対応すべきか
さて、上記から、データを守るのは実はなかなか難しいことだと言うことが分かりました。もちろん、実際に自分のデータがクラックされるかと言うと、その確率はかなり低いと言えます。その辺にいるクラッカーには100万ドルもお金をこういうことに投資しません。したがって、インターネット上のクラッカーに破られる可能性は限りなく低いと言えましょう。
実際にクラックしてくる人として想定されるのは、次のような人たちです。
- 企業スパイ
- 政府（軍）
政府はどっちにしろクラックしてきます。それが専用線だろうと何だろうと関係ありません。基本的に、米国で許されている方式は、いつでも国防総省がモニターできる状態にあると考えるべきでしょうから、これは置いておくとしましょう。次は企業スパイですが、彼らが DES Cracker のようなものを作る可能性はなくはありません。これを検出するのは比較的困難です。というのは、クラッカーと違って、彼らは決して解けたなどと発表はしないだろうからです。しかし、ならば公衆網を通さなければ安全かと言うとそんなこともありません。100万ドルかけてマシンを作ってクラックするような会社ならば、それ以前に、相手の会社の中に内部供応者を作るでしょう。そして、彼を使って情報を取ろうとするでしょうから、暗号化はするに越したことはないと言うことになります。情報を取るのにかかるコストが、内部供応者に支払うコストだけから、それ＋暗号を解くコストになるからです。
暗号自体を解きにくくする方法もあります。基本的には Key 長を大きくすることが一つですが、その変形として Super Encryption という方法もあります。これは、Plain Text Attack をできなくする方法で、2段階の暗号化を施す物です。2段階の暗号化をしていると、1段階目を解いたときに出て来る text は Random text で、全くフィルタリングすることができません。DESを2回かけていると、少なくとも 80bit 位の実質キー長は確保できていることになります。したがって、3日半で解くことは到底できません。Plain Text Attack の場合に比べて1024倍位大変になりますから、まぁ、そんなに簡単に解ける物ではありません。これを解くくらいだったら、退任間近の役員あたりに、コンサルの仕事を出した方がマシでしょう。
そこまでやるかどうかは、その情報を得た人間が、その情報によってどれだけ得をできるかにかかっています。例え、その情報がその企業にとって非常に重要でも（たとえば、漏れたりすると、信用的にダメージを受けるなど）、他人の儲けになら無ければ、だれもお金をかけてとろうとはしません。その意味で、暗号化を含むセキュリティは、情報の重要度をクラス分け(Classify) するところから始まると言えるでしょう。