メディア・キーの仕組み

2018/1/7


ブロードキャスト暗号法

これまで述べてきたようにBlu-rayなどの暗号化キーは不特定多数の人に配布する必要がありますが、この不特定多数に配布、いわばばら撒くことをブロードキャストすると言います。そのためこのような場合に適した暗号化方式をブロードキャスト暗号法と言います。

ブロードキャスト暗号法には様々な方式がありますが、イスラエル人コンピュータ科学者Moni Naorらによって提案された代表的な2つの方式があります。Complete Subtree Method(CS法)Subset Difference Method(SD法)です。AACSではメディア・キーの運用に後者のSD法を採用しているのですが、いきなりSD法の解説をしても、まず理解できません。

最初に両法共通の基本的な考え方から説明します。

まず話を簡単にするため、ユーザが8人だとしましょう。この8人に正規のキー(正しくコンテンツを復号化できるキー)を配布し、その後一人に配布したキーが漏れてしまった(不正者が現れた)場合にそのキーをリボークする方法を考えてみましょう。どうするといいでしょうか。

これを可能にする一番簡単な方法は、8人のユーザに別々の正規キーを配布するのです。コンテンツ提供者、所謂プロバイダはこの8個のキーいずれでも復号化できるようコンテンツを暗号化して提供します。この時点では8人のユーザ全員が復号化できる訳です。

不正者が現れた(キーが漏れた)ことを知ったプロバイダは今後、そのキーでは復号化できないよう、残りの7つのキーであれば復号化できるようコンテンツを暗号化して提供します。

こうすれば確実に不正者のみ、漏れたキーのみ無効に(リボーク)することができます。

しかしこれは8人だからいいですが、実際はユーザは非常に多いと前述しました。例えば何千、何万、何十万となりうるので、プロバイダは最初から何十万個のキーで復号化できるよう暗号化して提供しないといけなくなります。これは厳しいです。

そこで考案されたのが、ツリー構造でキー(鍵)を管理する方法です。CS法もSD法もこのツリー構造で管理するという基本的な考え方は一緒です。ツリー構造はコンピュータの世界では様々な場面に利用します。検索を早めるために2分木が使われるのは典型的な例です。

では具体的にどのようにツリー構造で管理するのかの解説に入りますが、より直感的で分かりやすいCS法から解説します。その方がSD法の理解もしやすいはずです。


CS法(Complete Subtree Method)

やはり話を分かりやすくするため、8人のユーザで考えてみます。以下のような2分木のツリー構造を作ります。

各節点鍵(キー)を割り当てます。全て異なったキーです。キーは全部で15個あるのがわかりますね。次にツリーのリーフ(枝葉)に各ユーザを割り当てます。そして各ユーザには自分のリーフからルートまでのパス上のキーを配布します。

一人のユーザあたりに配布されたキーは4個になります。まだ不正者がいない時を考えてみましょう。プロバイダはどのキーで暗号化すればいいでしょうか。そうです、一番上のルートの赤色のキーだけを使って暗号化すればいいのです。このキーは8人のユーザ全員が持っているからです。

ではここで左から4番目のユーザ不正者になったとしましょう。このユーザ(の持っていたキー)をリボークするにはどうしたらいいでしょうか。

プロバイダは図のように不正者の保持するキーを含まない集合(ツリー)のルートのキーのいずれでも復号化できるように暗号化するのです。暗号化キーは3つに増えますが、前述したツリー構造でない時よりはずっと減ってます。右側の4人のユーザを見てください。ツリー構造でない場合はこの4人にそれぞれ復号化できるキーを用意しなければなりませんでしたが、この例では1つで済む訳です。これがツリー構造の最大のメリットです。更にこれがユーザが数万と増えた時(ツリーが巨大になった時)にその差が歴然としてくるのです。

更に不正者が増えた場合はどうなるか解説します。

この例だともう一人不正者が増えることで、暗号化キーが4つに増えました。しかし不正者が増えれば増えるほど暗号化キーが増えるのでしょうか。実はそういう訳でもありません。例えばこれに左から3番目のユーザをリボークしたら、薄紫のキーは使わなくて済むので逆に減るのです。

つまり不正者の片寄り方バラけ方によって左右される訳ですね。それではそろそろ本題のSD法に参りましょう。

ところで誤解のないように言っておきますが、ここでユーザに配布するキーがデバイス・キーです。それによって最終的に取り出したい、見つけ出したい暗号化キーがメディア・キーです。


SD法(Subset Difference Method)の構造

構造はCS法より遥かに複雑ですが、似たような考え方の部分があるので、よく読んでください。

ツリーはCS法と同じ形で作ります。各リーフにユーザを割り当てるのも一緒です。

しかしCS法と違って、各15箇所の節点にいきなりキー(鍵)を割り当てず、まずラベルだけ割り当てます。ラベルは全部異なった数値です。尚、今後説明の便宜上、各リーフに割り当てられたユーザはそのリーフに割り当てらたラベルで呼称します。例えば一番左のユーザは、ユーザ8と呼びます。

さてキー生成ですが、それは上位(ルート)のラベルから順に右演算左演算を使って生成していきます。

ここがいきなり分かりにくいと思うのですが、まず右演算と左演算って何って話ですよね。

演算なので、例えば「5を掛ける」とか「3で割る」といった感じのものと考えて下さい。まずルートにあるラベル1右演算して生成した数値をキー(鍵)として、ラベル3のある節点(便宜上これを「節点3」と呼びます)に置きます。

この場合、1 × 5 = 5 がキーとして節点3に置かれます。

またラベル1を左演算して生成したキー(鍵)を節点2に置きます。

ここでは 1 ÷ 3 = 0.3333.... がキーとして節点2に置かれました。

そして更に大事な点として、演算はリーフまで続けるのです。例えばラベル1を右演算して生成したキーを節点3に置きましたが、更にそれ(生成したキー)を右演算して節点7に、更にそれを右演算して節点15へと、キー(鍵)生成を繰り返して各節点に置いていきます。

 

節点3のキーの値は「5」でしたから、節点7に置かれるキーの値は 5 × 5 = 25 ということになりますね。同様に節点15に置かれるキーの値は、25 × 5 = 125 ということです。

同様に左演算も繰り返します。例えば節点3のキーを左演算して節点6へ、更に左演算して節点12へ。左右交互も繰り返します。ラベル1を左演算して節点2へ、それを右演算して節点5へ、更にそれを左演算して節点10へ、などなど。

これを繰り返すと、ラベル1から右演算や左演算を繰り返して生成したキーが節点2から節点15まで置かれるはずです。キーの数は14個になりました。

しかしこれで終わりではありません。更にまだあります。ここまではラベル1から生成した訳ですが、これをラベル2からも同じことを繰り返します。つまりラベル2を頂点として、その配下の全てのリーフまでキー生成を繰り返すのです。

こうすると例えば節点4や節点5にはキーが2つ配置されることになります。節点5で言うと、1つはラベル1から左演算1回、右演算1回で生成したもの。もう1つはラベル2から右演算1回で生成したもの。

いずれも別のラベルからスタートし、演算の回数も違うので当然異なった値のキーとなります。

そしてこれをラベル3を頂点としても行います。更にはリーフ以外のラベル7まで下位がいるものは全て頂点として行うことを繰り返します。

ここでこれまで図上のキーの意味(ラベルタグや色)をあえて説明していませんでした。察しのいい方はもう分かっていると思いますが、一応説明しておきます。キーについているラベルタグはそのキー生成の大元(ルート)となったラベルを表します。キーの色はそれが配置される節点の色。これでルートからの位置関係から右演算と左演算を繰り返してきた回数と順番が分かるのです。

置き場は色で表していますが、言葉だと返って分かりにくいので、今後はラベル1から生成して、節点3に置いたキーをキー1-3と呼ぶようにします。ラベル3から生成して、節点15に置かれたキーは、キー3-15ということになります。

節点2と節点3の層(レイヤー)は1つのキーが置かれますが、前述のようにその下のレイヤー(節点4から節点7)はそれぞれ2つのキーが置かれます。そしてその下のレイヤー(節点8から節点15)は3つのキーがそれぞれ置かれることになります。

ここまで理解が着いてきたでしょうか。ここまで分からないと先に進みませんので、よく読んで図と見比べて理解をして下さい。結果としてキーの数は以下となるはずです。

2 + 2 × 4 + 3 × 8 = 34個

尚、右演算と左演算は決まっていて公開されています。ここもとても重要です。

これがどういうことを示すかというと、例えば最初のキー1-3(ラベル1から右演算で生成し、節点3に置いたキー)をあなたが持っているとします。このキーからは、それに公開され決まっている演算を繰り返して生成した下位のキーは全て生成できるため、そのキーを持っているあなたは、下位のキー(キー1-7やキー1-6、キー1-14などなど)は持ってなくても持っているのと同じことになります。ここは極めて重要なのでよく覚えておいて下さい。

ここでもう一つ演算について重要な話をしておきます。先ほどは分かりにくくしないよう「5を掛ける」などと極簡単な演算例を示しましたが、実際に使われている演算はずっと複雑なものです。少し専門的な用語を使うと「一方向ハッシュ関数」というものを使います。「一方向」は極めて重要です。「不可逆」と言ってもいいかもしれません。また「ハッシュ」という点も重要です。

例示した「5を掛ける」という演算は一方向(不可逆)ではありません。「5で割る」をすれば戻れるからです。いわば「双方向」「可逆」な訳です。しかし演算には一方向だけで戻れない演算というものが存在します。こういう演算を使うと、どういう効果があるのでしょうか。

先ほど上位のキーから下位を生成できるので、持っているのも同じだと言いましたが、もしこの演算が「双方向」「可逆」なら、下位のキーからも上位が生成できることになります。しかし「一方向」「不可逆」なので、下位からは上位のキーを作ることはできないようになっているのです。

上位からは作れるが、下位からは作れない。この関係はよく覚えておいて下さい。

それと「ハッシュ」であることの意味を説明します。「ハッシュ関数」というのはそれを説明するだけで一冊の本になるくらいなのです。非常に便利な関数で様々な場面で使われますが、今回の場合で重要になるハッシュの特徴だけ説明します。

ハッシュは数値を「要約」する性質があります。例えば文章を要約する時どうしますか? 一部情報を端折ったり、意味が変わらないようより簡単な別の言葉にしたり(簡易化)しますよね。ハッシュにはこの情報を端折る、簡易化する性質があるので、前述の不可逆にも繋がりますが、内容の異なった2つのハッシュ演算を順番を変えて行うと違う値が導き出されるという効果があります。

例えば「5を掛ける」と「3で割る」をある値に対して、先に「5を掛けて」次に「3で割った」場合と、先に「3で割って」次に「5を掛けた」場合、この演算では同じ結果になりますよね。

ハッシュ演算だとこれが違うのです。単純な演算でも、例えば「3で割る」を「3で割って小数点以下は捨てる」に変えたら、順番によって結果が変わりますよね。例えば元の値と「8」とします。

8 × 5 ÷ 3(小数点以下捨て) = 13

8 ÷ 3(小数点以下捨て) × 5 = 10

このように結果が変わります。この「小数点以下を捨てる」が前述の「情報を端折る」に該当する訳です。元の値によって端折る値が変わります。順番を変えるとこの演算をする時の元値が違ってくるので、違った結果が導き出されるのです。まあ極簡単に言うとこんなところです。本当はもっともっと複雑ですが。

つまりこれまで右演算と左演算を繰り返して、キーを生成していると説明していますが、同じラベルからで、かつ右演算と左演算の実施回数が同じでも順番が違うと生成されるキーが変わるということになります。

上図の例だと、節点5と節点6にあるキー(キー1-5とキー1-6)は同じラベル1から右演算1回、左演算1回をやって生成したキーですが、演算の順序が違うので異なった値のキーとなるのです。

後、何気に誤解しがちなので、覚えておいてほしいことがあります。それは各節点のラベルからキーを生成しますが、各節点にはその節点のラベルから生成したキーは置いてないということです。ラベルから演算してキーを生成し下位に置くので当たり前ではあるのですが、例えば節点2にラベル2から生成したキーが置いてあると誤解しがちなので、あえて言及しました。

さてここでこれまでのことを纏めましょう。ユーザが8人の場合ですが、

  1. 34個のキーが存在し、値は全て異なっている
  2. リーフにいくに従って各節点に置かれたキーの数は増える
  3. 同じラベルから作ったものなら、上位のキーから下位は作れる。
  4. しかしその逆(下位から上位)は作れない。
  5. 各節点にはその節点のラベルから生成したキーは置いてない。

さてキー生成までの話が随分長くなりました。CS法と全然違いますよね。ここからやっとこのキーをどうユーザに配布するかの話と不正者リボークの話です。


SD法のキー配布とリボーク方法

CS法では自分のリーフからルートまでのパス上の節点にあるキーが配られましたが、SD法ではパス上の節点の対称にある節点のキーが配布されます。節点によって沢山のキーが置いてあるので、当然ユーザ一人あたりのキーの総数CS法より多くなります。

例えばユーザ11の場合、図のようにラベル1から生成したキー1-3、キー1-4、キー1-10、ラベル2から生成したキー2-4、キー2-10、及びラベル5から生成したキー5-10の計6個のキーが配布されます。

このユーザ11が不正者として、そのリボークを考えます。まず不正者のみを含んだ集合(ツリー)を見つけます。これを今後「不正者集合」と呼びます。この場合不正者が一人なので、不正者のリーフがそれにあたります。

そしてその不正者集合を一つだけ含んだ一番大きい集合(ツリー)を見つけます。これを「外側集合」と呼びます。この例だと不正者集合が一つしかないので、外側集合も全体集合一つとなります。

この集合という概念がSD法ではCS法以上に重要なので、よく覚えていて下さい。

そしてプロバイダが、外側集合ルート(頂上節点)のラベルから生成した、不正者集合ルートに置かれたキーで暗号化することで、この不正者をリボークすることができます。

図でいうとグレーの集合が外側集合。ブルーの集合が不正者集合です。

もう少し具体的にリボークの様子を見てみましょう。よく前述のキーの配布方法を確認しながら見てください。

キー1-11を復号化できるのは勿論そのキーそのものを持っているユーザ10です。これは簡単ですね。彼女は対称の節点11のキーを持っているからです。

またユーザ8ユーザ9のお二人は自分のパス上の節点4の対称にある節点5のキーを持ってます。これは節点11の上位なのでこのキーで節点11のキーを作れる訳です。同じラベルから生成した上位キーを持っていれば下位が作れるという性質を思い出して下さい。

右半分のユーザ12からユーザ15は節点2のキーを持っていることが分かるでしょうか。節点2のキーを持っていれば、節点11の錠を開けられるのはもうお分かりですよね。

では改めて不正者ユーザ11が復号化できないのを見てみましょう。彼はラベル1から生成したキーを3つ持ってますね。それぞれキー1-3キー1-4キー1-10です。これらがいずれも節点11の上位ではないことが分かるでしょう。また別のラベルから作られたキーは全く使えません。彼が持っているどのキーでもキー1-11は復号化できないのです。

こうして不正者ユーザ11はリボークされました。しかしこの例では前述の集合という概念の重要性が今一分かりませんね。

では次に不正者が2人になった場合です。ユーザ11の他、ユーザ13を不正者として考えます。この例では外側集合が2つになるので、暗号化キーも2つ必要になり、集合という概念が意味を持ってきます。

左側の節点2を頂点とした集合を便宜上その節点のラベルを付けて「集合2」と呼ぶようにします。従って右側の節点3を頂点とした集合は集合3になります。

集合2の中で、ラベル2から生成して節点11に置いたキーを不正者ユーザ11が復号化できなくて、ユーザ8からユーザ10が復号化できるのは先ほどの例と全く一緒なので、説明するまでもないでしょう。自分で確認してみて下さい。

一方集合3のユーザはいずれもこのキーを復号ができません。彼らはそもそもラベル2から生成したキーは一つも持ってないからです。彼らは上位節点である節点3対称にある節点2に置かれたキーを持っているはずですが、節点2にはラベル2から生成したキーは置いてないという条件、性質がありましたね。

そこでこの集合3の中の正規者を救うためにもう一つ復号可能なキーを用意したのが、キー3-13です。こちらでもう一人の不正者ユーザ13が復号化できなくて、この集合3の中の他のユーザが復号化できるのは、集合2の場合と同じなので説明は不要でしょう。

このように不正者を取り囲む集合を作って、個別にリボークできるように工夫されたのがSD法なのです。

SD法のSubsetとは部分集合という意味ですが、集合2も集合3も集合1の部分集合です。しかし部分集合というと全体集合の一部のであって、お互い関連しているようなニュアンスがありますが、これが部分集合でありながら、全体集合とは全く独立した異なった(differenceな)集合体です。これがまさにSubset Difference法と呼ばれる所以なのです。

下の図を見て下さい。三角形が沢山あるのが分かるでしょうか。「え?四角ばっかりじゃん」なんて言わないで下さい。部分集合である三角形が幾重にも手前に重なっているのです。グレーの三角形の手前に黄緑の三角形。その手前に黄色、その手前に青といった感じです。この三角形一つ一つが集合なのです。そしてそれらの集合はそれぞれ完全に独立しているのです。

この三次元的なツリーの構造がSD法の特徴であり、CS法と最も異なった部分です。これがSD法の理解を難しくしている一方で、この構造が分かったら、あっと言う間にSD法の全容が分かってくるのです。

もう少し話を進めると、CS法同様、不正者が増えれば増えるほど暗号化キーが増える訳ではありません。やはり不正者の片寄方ばらけ方によって違います。

不正者集合という言葉を使っていますが、これまでの例では実際は複数という意味での不正者の集合という例はありませんでした。不正者が纏まると不正者を集合として扱えるので、纏めてリボークできます。

この図の左側の外側集合には不正者が2人いますが、文字通り不正者集合として扱えるのでこの外側集合では2人を纏めてリボークできます。

また一番右側の外側集合は、不正者集合と一致しているので、考慮する必要がなくなります。考慮する必要がないというのは、もうこの外側集合用に復号化可能なキーを用意する必要がないということです。外側集合毎に復号化可能キーを用意するのは、その集合の中の正規ユーザを救うためです。もはや救うべき正規ユーザがいない外側集合は無視してしまえばいいのです。

これまで見てきたようにSD法は、CS法に比べ暗号化の回数が少ないことが分かるでしょうか。まさにこれがSD法の最大のメリットであります。

一方でユーザに配布するキーは増えます。しかしそれでもこのSD法の複雑なキー構造はまさに配布キーを減らすために行っているのです。あるキーを持っていると、その下位のキーは持っているのと同じだという説明をしています。もう一度配布の図を見て下さい。

このユーザ11はキー1-3を持っていますが、その下位にあるキー1-6、キー1-7、キー1-12、キー1-13、キー1-14、キー1-15を持っているのと同じ訳です。所持キーであるキー1-4やキー2-4も同じことで、結局実際に所持しているキーは6個ですが、事実上14個持っている(配布した)のと同じなのです。

従って実質的なキー配布数はCS法よりも格段に多いので、これが暗号化回数を減らすことに貢献しているのです。

Blu-rayなどでの想定配布対象ユーザ数や想定リボークユーザ数を考慮した場合、SD法のこの特徴がより合っているとAACSでは判断したのでしょう。

それにしてもよくこんな仕組みを考え出しましたよね。頭がいい人っているもんです。


AACSでの実装

これまで説明のためにユーザ8人の場合で見てきましたが、勿論Blu-rayの場合そんなに少ないはずはないので、AACSでの実情、実装はどうなっているかというと、何とツリーの段数が22段もあります。AACSではこの巨大なツリーをメディア・キー・デルタと呼んでいます。

尚、誤解されがちなので申し上げておくと、このメディア・キー・デルタは概念として存在しているだけであって、例えばMKBの中に物理的に存在しているようなものではありません。

これだけあるのでユーザ数も、2の22乗ということで 4,194,304 まで許容しています。これなら相当数リボークされても1000年以上大丈夫そうです。

一方1ユーザに配布されるキーの数は、

1 + 2 + 3 + ... + .... + 20 + 21 + 22 = 22 * (22+1) / 2 = 253個

に及びます。これがユーザにデバイス・キーとして実際配布される訳ですが、前述した実質持っているのと同じと言った算出可能なキー数は(計算が複雑なので式は示しませんが)、16,776,915個 に達します。実に実際配布されるキーの6万倍以上あるのです。

この各ユーザが実質持っているのと同じ16,776,915個のキーのどれかがメディア・キー・デルタの中の目的であるプロセス・キーに直接繋がります。実際はこのキーからもう一度プロセス・キー生成用の一方向ハッシュ関数をかけて算出するので、言わば目的のプロセス・キーが隠れている部屋の鍵のようなものです。

しかしこの隠れ部屋の鍵は正規ユーザなら実質持っているとは言え、これまで説明してきた論理に従って、ユーザが実際に持っているデバイス・キー253個のキーうち、どれかから演算を繰り返して算出しないといけないのは言うまでもありません。それを総当りで探していたら大変です。

そこでMKBの中にUV NumberU-Maskと呼ばれる値が用意してあります。これは言わばプロセス・キーの隠れ部屋への道しるべのようなものです。UV NumberとU-Maskはユーザにもデバイス・キーと一緒に配布されます。それらとMKBのUV NumberとU-Maskを演算すると今回自分の253個のどのデバイス・キーを使えばいいか、それをどういう順序で何回、右演算と左演算を繰り返せば目的のプロセス・キーに辿りつけるか分かるのです。

ところで説明の比喩として、メディア・キー・デルタのツリーを辿ってあたかもどこかに隠れているプロセス・キーを探しているような表現をしている部分がありますが、お分かりの方も多いように実際はデバイス・キー(という数値)を右演算、左演算を繰り返して計算をして出した結果がプロセス・キー(という数値)です。従って本来は探し出すとか、辿りつくというよりも、「算出する」と言った方が実際の作業イメージとしては近いです。

プロセス・キーが見つかったら(算出されたら)、これを使ってC-Valueを復号化して、やっとメディア・キーに辿りつきます。このC-Valueも沢山あると説明していますが、これもやはりDevice Numberというデバイス・キーと一緒にユーザに配布されている値を使って、簡単にどれが該当するか演算できるようなっています。

C-Valueが沢山あるのは、SD法の説明のところでも暗号化に使った有効なキー(プロセス・キー)が複数あることに対応しています。

   

これでAACSの核心であるプロセスMKBと呼ばれるメディア・キーの仕組みの解説は終わりです。何とか私の解説で理解して頂けたでしょうか。もし分からないことがあるようなら、何なりと何でも掲示板にご質問下さい。結構分かりやすく解説したつもりですが、私もかなり理解には時間がかかりましたので、理解が及ばない部分もあるかと思います。

またAACS、特にSD法の解説はいろいろな方法があります。その一つが、プロセス・キーを世界で最初に発見した伝説のハッカー arnezamiの解説があり、これが私の理解を助けてくれました。英語ですが、Doom9フォーラムでの彼の解説も載せましたので、合わせて読んで頂けると理解しやすいかと思います。トラックが道を辿るという非常にうまい比喩的な表現を使った、分かりやすい解説です。arnezamiのDoom9でのAACSに関する解説


 
Blu-rayの暗号システムのトップページへもどる
デジタル家電のトップページへもどる
ホームページへもどる
inserted by FC2 system