英語でセキュリティ#2 - 実装を措いて鍵長を語ることなかれ

 KBIZ小熊です。 数年前から、英語の勉強とセキュリティの情報収集を兼ねて、鎌倉から東京までの通勤時間に「Security Now!」というPodCastを聞いています。ここでは、その中で小熊が面白いと思った内容(一部)について、原文を交えて紹介していきたいと思います。英語をちゃんと訳す時間もありませんし、原文を読んだり、PodCastを聞いて欲しいという思いもあるので、訳はいい加減な上に脚色が入っています。悪しからず。

 今回は、その第2回目です。  だいぶ古いエピソードなんですが、Blu-rayの暗号がどうやって解読されたかについてです。Blu-rayは暗号には世界標準のAESを使っており、この暗号を解読するのは実質的に不可能と言われていました。ところが、それが解読されてしまったのです。さて、どうやって解読に成功したのでしょうか。PodCastリスナーからの質問への回答コーナーの中での会話です。

「実装を措いて鍵長を語ることなかれ」

Security Now! Episode #76 "Listener Feedback Q&A #15" January, 25 2007


Steve: I don't know if you picked up the news that our friend muslix64 has not only cracked HD, but now Blu-ray.

Steve: そういや、ぼくらの仲間のmuslix64が、HD-DVDだけじゃなくてBlu-rayもクラックした話ってしたかな?


Leo: And that's because it's still AACS. It makes sense; right?

Leo: それもAACSを使っていたんだろう?


Steve: Well, but what's interesting is he didn't even have a Blu-ray disk. Somebody who bought a Blu-ray disk was playing the Blu-ray movie in Windows using the PowerDVD player, or I think it might have been WinDVD, in fact. That guy took a snapshot of the memory image of the process, that is, the WinDVD process, while it was playing the movie, presuming that if it was playing the movie...

Steve: うん、でも面白いことに、彼はBlu-rayディスクを持ってすらいなかったんだよ。誰かがBlu-rayディスクを買って、WindowsでPowerDVDを使って映画を再生してたんだ、あ、いや、WinDVDだったかな。そいつは再生中のメモリイメージのスナップショットを取ったのさ。そう、映画を再生しているWinDVDのプロセスだよ。その中には多分...


Leo: It would have the key.

Leo: 鍵がある!!


Steve: ...the key had to be in memory. And what muslix then did was well, so this guy packaged up the memory image and a couple chunks of the encrypted content, which are just files, after all, on his Blu-ray disk, sent them to muslix64. Muslix64, first of all, his decryption, he's continued to work on this since we first talked about it around the turn of the year, around Christmastime was when this news came out that, quote, HD-DVD had been cracked, which is not the case. But it is the case that it is possible to find the keys. So what muslix did was, and the reason I'm bringing this up is it's some fun true crypto technology that we've talked about in the past. He did a chosen plain text attack, meaning that the keys are 128 bits. So you cannot just try every possible key. That would be a brute-force attack where you start with all zeroes and then all zeroes and a one, all zeroes and a one zero, all zeroes and a one one, and you just go through every possibility. Well, a 128-bit key you cannot brute force in any reasonable amount of time, as we've discussed in the past. But you don't have to try every possible key. You just have to try every possible candidate key. And the candidate keys are the ones that were in memory, that is, you don't know, in the memory image, you don't...

Steve: そうさ、メモリにあるはずなのさ。そしてmuslixが何をしたかというと、まぁ、さっきの誰かがメモリイメージと暗号化されたコンテンツ、つまり、Blu-rayディスクのいくつかのファイルをmuslix64に送ったわけさ。年初の頃にこのことを話してから彼が解読作業を始めて、クリスマスの頃にmuslix64から「HD-DVDをクラックした」っていうニュースが飛び込んできたのさ。でも違ったんだけどね。まぁでも、鍵を見つけることができるってことはわかったんだ。なんでこれを取り上げるかっていうと、彼がしたことは、面白いことに今まで話してきた本当の暗号技術を使っているのさ。彼は128ビットの鍵に対してchosen plain text attack(選択平文攻撃)をしたんだ。(注: chosen plain text attackの意味間違えて言ってると思われる)。そう、全部の鍵を試すわけにはいかないからね。全部を試すのはbrute-force attack(総当たり攻撃)で、全部0から、全部0と1、全部0と10...と調べていくってことさ。でもね、128bitの鍵じゃ、全部のパターンを試すなんてことは現実的じゃないのさ。むかし言ったことがあるだろう? ところがだよ、全部試す必要なんてないんだ。やればいいのは「Candidate key(候補となる鍵)」だけでいいんだよ。そしてそれは、メモリにのどっかにあるって段取りさ。


Leo: So you don't know where the key is. Leo: でもいったい鍵はメモリのどこにあるんだい?

Steve: Yeah, but it doesn't matter because the memory image is much smaller than all the possible keys.

Steve: そこさ。いいかい? It doesn't matterなのさ。そんなことはどうでもいいんだよ。メモリイメージなんてのは、128bitの鍵の数に比べたら遥かに小さいのさ。


Leo: Right. So you just do a rolling slide through the memory.

Leo: なるほど。ってことは、メモリを全部試してみりゃいいってことかい?


Steve: Yes. And it works.

Steve: そういうことさ。そして、うまくいったんだ。


Leo: Oh, baby.

Leo: オーベイビー。

Steve: It completely works. So all you do is you take the first four bytes and assume that they're the decryption key, try to decrypt a piece of encrypted content. And you know what the beginning of the encrypted content looks like because it's a standard MPEG frame. So if that doesn't work, you take bytes two, three, four, and five. Then you take bytes three, four, five, and six. Then four, five, six, and seven. You just slide along through memory. And our PCs are all fast enough, in a very short time basically you've searched the image, the software image of this thing playing, for the key. You find it, and then you can decrypt all the content of the disk.

Steve: 完璧にうまくいったんだよ。最初の4バイトを取ってきて、それを鍵と思って暗号化されたコンテンツを復号してみるのさ。(注: 128ビットだから、本当は16バイトと思われ)。そしてそれがコンテンツの最初の部分か見るのさ。だって、それは標準的なMPEGのフレームのはずなんだからね。もし違ったら、次のバイトを試していくんだ。メモリの上をずっとなぞっていけばいい。PCがそれなりに速ければ、再生中のソフトウェアのメモリイメージを全部調べるなんて、そんなに時間はかからない。そして鍵があれば全部のコンテンツを復号できちゃうんだ。


Leo: Let's put it this way. It's probably faster to do that than it is for the DVD player to decrypt the AACS, given the speed of your computer's processor. Leo: つまりこういうことかい? PCが速かったら、DVDプレイヤー(注: 正確にはBlu-rayプレイヤー)がAACSを解いて再生するよりも速いかもしれない、ってことだね。

Steve: Yes. And so here again I think we're going to be seeing these kinds of things now coming out from time to time about AACS. And what it really means is that software players are a huge vulnerability for this entire class of new encryption. If the software is decrypting and you have access to the software, then you can't protect it. And this is fundamentally what I keep saying, is the reason this can't ever work the way the content providers want it to is something in the user's control, over which they have control, is displaying, one way or another, an unencrypted result. Which means all the information to do the decryption has to be right there in order for it to be delivered to the end user. So anyway...

Steve: そういうことさ。今回の件もそうだけど、AACSについてのこういった話はどんどん出てくるのさ。これが何を意味しているかって言うと、結局のところ、こういう新しい種類の暗号にとって、ソフトウェアのプレイヤーってやつはとんでもない脆弱性だってことなんだ。ソフトウェアが復号処理をしていて、ユーザがそのソフトウェアにアクセスすることができる以上、それを守ることはできないのさ。これはずっと僕が言っていることだけど、基本的に、映画を再生するとか、とにかくコンテンツを復号するものがユーザの手に渡ってしまった以上、コンテンツプロバイダが思う通りにはならないってことなんだよ。そして、エンドユーザにコンテンツを配信するためには、復号に関する情報はエンドユーザのところに無きゃいけないってことなのさ。とにかく...


Leo: Sure, yeah. That's the flaw. People often say we might even have a question in our questions today. But they often say, well, wait a minute, you say you can never crack an encrypted email. How come you can crack a DVD? That's precisely the reason. The key has to exist somewhere. Very, very, amazing, just I love that kind of stuff.

Leo: なるほど。それが問題なんだな。Podcastのリスナーは、ぼくらは質問の中にまた新たな疑問を見つけるっていうけど...そうそう、君は、暗号化されたメールはクラックできない、って言ったよね? なんでDVDはクラックできるのか? それがまさに理由ってことなんだな。鍵はどこかに無ければならない。いや、amazingだよ。こういうのって大好きだなぁ。


Steve: Isn't that a perfect hack? I mean, it's just a beautiful hack.

Steve: 完璧なhackさ。っていうか、これはビューティフルなhackだよ。

 この話を聞き始めたとき、小熊がまず想像した解読方法はリバースエンジニアリングでした。メモリイメージをデバッガにかけて、ソフトウェアBlu-rayプレイヤーの動きを解析して、鍵がどこにあるかを発見した、という流れかと思いました。ところが、実際には、ちからわざでメモリ全部に対して鍵の可能性試して、MPEGフレームっぽいものが出てきたら正解、という流れ。いやはや、コロンブスの卵だな、と思いました。

 今回訳していて思いましたが、PodCastを聞いている方が分かりやすいときがあります。特に下のようなところ。

And this is fundamentally what I keep saying, is the reason this can't ever work the way the content providers want it to is something in the user's control, over which they have control, is displaying, one way or another, an unencrypted result. Which means all the information to do the decryption has to be right there in order for it to be delivered to the end user.

 この文章、どういう構造になっているのか、文字だけだと理解するのに時間がかかります。ところが、しゃべっているのを聞くと、イントネーションや言葉を切るタイミングで、どの言葉がどこにかかっているのかが分かるので、理解しやすいのです。これはPodCastをそのまま文章にしているので、英語としてはだいぶ読みづらい部類に入ると思います。是非オリジナルを聞いてみて下さいね。

 今回は、AACSの鍵は128bit AESなので、16バイトのはずのところを4バイトと言っていたり(実際には、鍵は少なくとも32ビットバウンダリに配置されているだろう、ということから、4バイト(32ビット)ずつデータをとって、それを16バイト(128ビット)に順次構築してテストしていた、ということを言いたかったんだと思います)、候補鍵を試していく方法をchosen plain text attackと言っていたり(本当の「chosen plain text attack」は、攻撃者が任意の平文を入力して、それを暗号化させることが可能な環境において暗号鍵を解読する方法)、若干間違いがありましたね。このPodCastでは、こういう間違いをリスナーが指摘して、その後修正したりするんです。

 ちなみに、128bit長の鍵のパターンは全部でいくつあるでしょうか。今ちょっとGoogleで探して書こうかと思ったんですが、簡単に見つけることができなかったのでざっくり10進数で表現してみましょう。まず、2進数で表現するのはそのままですね。2の128乗個です。1の後に0が128個続く数です。ただ2進数はイメージが掴みづらいので10進数にしてみましょう。さて、2進数を10進数にするときに便利な方法があります。2の10乗って、だいたい1000なんです。覚えやすいですね。正確に言うと2の10乗は1024です。まぁだいたい1000でいいでしょう。2の4乗は2×2×2×2で16ですね。8乗なら16×16で256。これにもう2回2を掛けると、512→1024になります。では、128乗は? 120bitだったら10×12で簡単に計算できますね。1000に対して0の数が12倍ってことですから、1の後に0が3個×12回続くってことですね。0が36個。1,000,000,000,000,000,000,000,000,000,000,000,000個ってことですね。小熊は、中学の時に億の上の単位を覚えたので、無量大数まで全部言えますよ。ちなみに1の下(1割、1分、1毛ってやつです)も全部言えます。今度会ったら言ってください。その場で言いますから。  で、1澗ってことですね。なんかかえって少なく見える...。昔、RSA Conferenceに行ったときに、AESの説明がされていて、DESの56bitの鍵の数がティースプーン一杯の分子量とすると、128bitの鍵の数は地球の分子量に相当する、と説明されました。今改めて調べてみると、地球上の水分子の数が10の45乗ってなってますね。だいぶ違いますね。ちなみに、AESでは256bitの鍵も使えますが、こうなると鍵の数は単純に0の数が倍になって10の72乗個になりますね。1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000個ってことですね。ここまで来ると無量大数も超えちゃって、宇宙に存在する全陽子の数に近くなってくるようです。  さて、これに対して、メモリの大きさってどれぐらいでしょう。今回のエピソードを見てみると、「ソフトウェアのメモリイメージ」と書いてあります。つまり、WinDVDが動作しているときに使っているメモリ部分のイメージを使っていたわけです。そこで、WinDVDのシステム要件を見てみると、「1Gバイト以上のメモリ」と書いてあります。なるほど、1Gバイトですね。そうなると、大きさは1,000,000,000バイト。いやぁ、だいぶ0の数が少なくなっちゃいましたね。いえ、もうちょっと減りますよ。これはバイト数なので、4バイト境界毎に鍵の可能性をあたっていくのであれば、1/4でいいってことです。つまり、250,000,000個の可能性を試すってことです。2億5千万個。PCでどうにかなりそうな数字ですね。

 「セキュリティは一つの鎖である。引っ張ると、一番弱い輪っかが切れる。鎖全体の強さは、一番弱い輪っかの強さでしかない。」とは良く言いますが、まさにそういうことです。暗号方式がいくら強力なものであっても、鍵長が128bitであっても、しょせん実装が甘ければそこをやられてしまう、ということです。

 是非みなさんもこのPodCast、聞いてみて下さい。楽しいですよ。しゃべったことが全て文字になってWebに載っていますので、聞き取れないところもそれを見れば大丈夫です!! Androidの人は、BeyondPodを使ってはいかがでしょうか。500円するアプリですが、夜中に自動で新しいエピソードをダウンロードしてくれるので便利ですよ。小熊はそれを使っています。

 それでは、また。


小熊