「米国サイバー軍の紋章に隠された暗号」はカンタンだった?

  • Facebook
  • Twitter
  • はてなブックマーク
  • Delicious
  • Evernote
  • Tumblr

昨日のWIRED VISIONに掲載された「『米国サイバー軍の紋章』に隠された暗号」という記事がちょっと面白かったです。

201007090757.jpg

(クリックで拡大、出所:Wikipedia

 

[米国は、サイバースペースで戦い、軍のコンピューターをハッカーたちから守るというサイバー司令部(Cyber Command)を創設、今年10月から本格稼働させようとしている]
サイバー司令部の本拠地は、メリーランド州のフォート・ミード陸軍基地にある[国家安全保障局(NSA)も同地にある]。 ここは、軍の中でも最も秘密主義が徹底されている施設の1つだ。サイバー司令部のミッションは基本的に不透明で、軍内部でも明らかにされていない。だが、この誕生間もない部隊にまつわる謎はもう1つある。それはサイバー司令部の紋章(上の画像)に刻まれている。 紋章には金色の輪が2つあるが、内側のほうの輪の上に、「9ec4c12949a4f31474f299058ce2b22a」というコードが刻まれているのだ。

ということで、紋章に「謎の暗号」が記載されているわけです。

「関係筋」は、

「これは意味のない数字の羅列ではなく、解読することができる」
「デザイン段階ではいくつかの異なる提案が出たが、最終的には、どの部隊にとっても必要なものが選ばれた——つまり、組織のミッションだ」

と大ヒントをくれています。

私も(こういうの好きなので、本格的なものだったら解けるわけもないと知りつつ)解読を試みようとしました。

まず文字が数字とaからfまでの英字しかないので16進数だろうということまではわかりますが、普通に英字を表すASCIIコードの体系は、

201007090806.jpg
(クリックで拡大、出所Wikipedia

 

上記のように(16進数で)最初の文字が7までにしかならないので、ちょっと違いそうだということがわかります。

ヒントが「組織のミッション」だとあるので、このミッションを探しに英語版のWikipediaの「United States Cyber Command」という項を見に行くと、なんともう既にそこに答えが書いてありました

The text “9ec4c12949a4f31474f299058ce2b22a”, which is located in the command’s emblem, is the MD5 hash of their mission statement.

MD5というのは「ハッシュ関数」と呼ばれる関数で、暗号のシステムではよく使われるものです。

ハッシュというのは、「ハッシュドビーフ」のハッシュ(hash)と同じで、ある文字列を一定の長さ(例えば128bit)に要約する関数です。
この際、どんな文章でも元の文章からは必ず1つの値の128bitの文字列が生成されるが、その128bitの文字列からは絶対元の文書が推測できないことが重要です。(一方向性。推測できると、あるハッシュに電子証明をもらって、元の文章を改ざんすることができてしまいますので。)

Wikipediaに書き込んだのはこの方ですが、英語原文のWiredの記事が7日の9:23 amで、8日の10:51に書き込まれています。

記事英語版のコメント欄にも書いてありましたね。
7日の10:23 amにはすでに「MD5じゃね?」という書き込みがあります。32文字で128bitなので、ちょっとシステムをやってる人なら容易にそれが思いつくかも知れません。
その後、12:27 pmにはすでに、いろんなハッシュ関数での値を計算して載せている人がいました。でも値は違っています。

 

Wikipediaに書き込んだ人の変更履歴にも書いてありますが、ハッシュ関数のすごいところは、1文字違っても、関数から吐き出される値が全く違ってしまうところです。

実際、書き込みの前のバージョンでは、このサイバー軍のミッションは、

USCYBERCOM plans, coordinates, integrates, synchronizes, and conducts activities to: direct the operations and defense of specified Department of Defense information networks and; prepare to, and when directed, conduct full-spectrum military cyberspace operations in order to enable actions in all domains, ensure freedom of action in cyberspace for the U.S. and its allies, and deny the same to adversaries.

となっているのですが、書き込んだ方は、

USCYBERCOM plans, coordinates, integrates, synchronizes and conducts activities to: direct the operations and defense of specified Department of Defense information networks and; prepare to, and when directed, conduct full spectrum military cyberspace operations in order to enable actions in all domains, ensure US/Allied freedom of action in cyberspace and deny the same to our adversaries.

としており、コメント欄で、

It is important that the mission statement text is left unmodified to correspond to the command’s emblem.
PLEASE do not edit it! Thanks!

と、「編集しないで!」という注意をしています。

よく見ると、前のバージョンでは「synchronizes」の後に「,」が入ってますが、新しい版には入っていないなど、かなり文章が違っています。

こういうカンマが1字あるかどうかでも、ハッシュ値が全く変わって来てしまうわけです。

(英語版Wiredのコメント欄に書き込んでいた人のMD5の値も「6c9f5a9b016c228f5f22d292e99618d0」と違った値になっています。)

 

このハッシュ関数は、「暗号」の一種ではあるのですが、何かを隠そうというよりは、特定の文字列との対応を付けるのに使うといった使い方の方が多いと思います。

つまり国民総背番号制のようなもので、すべての文章に番号を割当てる、といった使い方です。

そうすると、例えば文章に電子署名をする時に、ものすごく長い文章だと演算時間が非常にかかるところが、16進数で32文字(128bit)に短くされた文字列に電子署名すれば演算の負担も軽いわけですね。

 

容易におわかりになると思いますが、この128bit文字列の集合は、文字数に制約が無いすべての文字列の集合より小さいのは当然です。文字数に制約が無いすべての文字列の集合は128bitの文字列を含んでいますから

だから1つのハッシュ値には無限の文字列が対応していますので、違う文章が同じハッシュ値になるのは当然なわけです。

しかし、128bit(漢字8文字分程度にしか過ぎない)の組み合わせはナメてはいけなくて、それだけで1兆の1兆の1兆倍以上の数の組み合わせがあるわけです。(2^128≒3.4×10^38=340×1兆×1兆×1兆)
1秒に10億くらいの組み合わせを総当たりで検討できたとしても宇宙の寿命内には計算が終わらない。

だから、絶対ダブらない(コリジョン [collision] が発生しない)ハッシュ関数なんかは理論的に作れるわけがないけど、ちょっとだけ違った文章がまったく違う値になるようにして、元の文章をちょっと改ざんしてもバレバレになるようにできれば、実用性はでてくる訳です。

 

以前、ハッシュ関数に関するブログの記事を書いたときには大丈夫だったのですが、@gohsuketさんにツイッターで「MD5はコリジョン指摘が数年前に(既にあった)」ということを教えていただきました。@fukumimiさんご指摘のUS-CERTの記事はこちらで、2008年12月にはもうMD5の脆弱性が指摘されているようです。

日本語版のWikipediaのMD5の項によると、

MD5のハッシュ値については、パソコンレベルで、数10分程度で、同一ハッシュ値の非ユニークなデータ列を生成できる実装が広まっている。

とありますが、

ただし、任意に与えられたハッシュ値に対して、(何らかの別の)データを生成する実装が広まっているわけではない

とのことです。

つまり、同じハッシュ値になる違う文章を見つけることは容易だが、提示されたハッシュ値になる元の文章を見つけるアルゴリズムが見つかっているわけではないということですね。

そのため、直ちにこれらのハッシュアルゴリズムを用いている暗号化通信が盗聴・改竄されたり、電子署名の有効性が無くなると言うわけではない。

とのことですので、一応、ご安心ください。

 

サイバー軍ともあろうものがMD5の脆弱性をご存じないということは無いはずなので、このエンブレムに書かれた「暗号」は、長いミッションを要約するための「しゃれ」なんじゃないかと思います。

むしろ、軍が実際に使ってるハッシュ関数とは別だからこそMD5を選んだということなのかも知れませんね。

 

(ではまた。)

[PR]
メールマガジン週刊isologue(毎週月曜日発行840円/月):
「note」でのお申し込みはこちらから。