他の端末に知らせずに対象端末を無効化する

端末はそれぞれ鍵を保持しています。その中の一つが漏洩した場合でも、他のすべての端末に対してはライセンスが有効であり続けなければなりません。全体の端末数と、侵害された端末の数を設定してみてください。ツールは、Naor、Naor、Lotspiechが2001年に提唱した二種類の被覆を構築し、選ばれた方式を図示して、ヘッダに含めるべき鍵の数を算出します。

計算例 — 他の端末に知らせずに対象端末を無効化する

ヘッダ内の鍵の数	4
ヘッダサイズ（鍵一つあたり16バイト）	64 B

ページを開いたときに計算機が表示する値です。上の入力を変えると再計算されます。

インタラクティブシミュレーションを読み込んでいます...

レッスン

理論 — 他の端末に知らせずに対象端末を無効化する

ブロードキャスト暗号では、暗号化された同じ映像がすべての端末に届けられ、それを開く権限はライセンスによって管理されます。まず、端末を二分木の葉に見立てて配置し、すべてのノードに固有の鍵を与えてみましょう。各端末には自身の葉から根へと辿る経路上の鍵が渡されるため、手元には log₂N + 1 個の鍵が残ります。これにより、あるノードはその配下にある全端末の集合を指し示すようになります。ライセンスのヘッダには、正規の端末を過不足なく覆いつつ侵害されたものを避けるような集合の組み合わせに対して、それぞれ暗号化された映像の鍵が格納されます。つまり端末を排除するということは、この集合の選び方を変えるという操作なのです。

各記号の意味

N: 存在する端末の総数。ここでは木を完全に満たすため、常に2の冪乗を前提とします
r: そのうち侵害されており、アクセスを遮断すべき端末の数
S(i,j): サブセット・ディファレンス（部分集合の差）。ノード i の配下からノード j の配下を除いたすべての端末を指します。ヘッダのひとつの項目だけで不良な葉をひとつ飛び越えられるのは、この概念のおかげです

前提: 排除対象となった端末は修復できず除外するしかないこと、そして一度与えられた鍵を端末が決して忘れないことを前提としています。論文のタイトルにある「ステートレスな受信者」とはまさにこの状態を指しています。また、この問題が単なる鍵の更新ではなく、被覆問題として扱われる理由もここにあります。新しい鍵を送信したとしても、鍵を漏洩した張本人までそれを受け取ってしまうからです。
成り立たない場合: 破綻するのは、侵害された端末が均等に散らばっている場合です。どちらの方式も、連続したシリアル番号のまとまりに対しては最高の効率を発揮しますが、端末がひとつおきに侵害されているような状況では最悪の結果を招きます。そのような配置では清浄な部分木がひとつも残らず、無事な端末ひとつにつきヘッダの項目がひとつ必要になってしまいます。これは、何の仕組みも導入しなかった場合に支払うコストと同じです。

ヘッダは全体の端末数を関知しない 🖖

侵害された端末の数を10に設定し、システムのサイズを動かしてみてください。完全部分木方式では、端末数が1,024台のときに58個、16,384台で98個、1,048,576台で158個、16,777,216台では198個と推移します。システム規模が倍になるごとに、侵害された端末一台につき鍵が一つ追加される計算です。これは、それぞれの端末が根に至る経路上のすべての兄弟ノードに対して、部分集合を一つずつ必要とするためです。対照的に、部分集合差分方式ではこれら四つのサイズすべてにおいて13個のままです。13個の後に14個になるわけではなく、まったく同じ13個です。システムが512台以上であれば、規模が三万二千倍に拡大しようと全く変化しません。部分集合差分方式における部分集合は、「ノード i の配下にある全端末から、ノード j の配下にあるものを除外した残りすべて」と定義されます。そのため、単一のエントリで1,048,575台に鍵を渡しつつ、特定の一台からは鍵を隠すことができ、しかも深く掘り下げたとしてもコストは一切かかりません。これが、上限値が 2r − 1 となり、そこに N が全く含まれない理由です。Blu-rayディスクのメディアキーブロックに部分集合差分木が採用されている理由もここにあります。映画スタジオが二十年にわたって端末を追加し続けても、ヘッダはそれにすら気づかないのです。

その代償はすべての端末が一度だけ支払う 🖖

表の最終行を見てください。完全部分木方式は、各端末に log₂N + 1 個の鍵を要求します。百万台のシステムであれば21個であり、これは端末自身から根に至る経路上のノード数に相当します。一方、部分集合差分方式が要求するのは ½log₂²N + ½log₂N + 1 個、すなわち211個です。分散して侵害された十台の端末に対してヘッダサイズを十二分の一に、また六十四台の場合で十一分の一に抑えるために、十倍のストレージを費やしていることになります。どの数字がどの頻度で支払われるかに気づいたとき、初めてこのトレードオフの意義が明確になります。端末への鍵の保存は工場出荷時のたった一度きりですが、ヘッダはすべてのタイトルの、すべてのライセンスに付随して、すべての端末へ永遠に送られ続けるのです。211個の鍵はフラッシュメモリ上で 3.4 kB にすぎません。この百万台の端末は、ライセンスを要求するたびに 1.23 kB ではなく 13.5 kB のヘッダを取得することになります。これは先ほどの議論を逆の視点から捉え直したものと言えます。

どれだけ無効化するかより、どれを無効化するかが鍵になる 🖖

百万台中の一つのロットを押し、次に百万台の中に64台が分散を押してみてください。無効化されるのは同じ64台の端末です。それなのに、部分集合差分方式のヘッダは3個から77個へ、完全部分木方式のヘッダは17個から846個へと跳ね上がります。木の中で不良端末がどこに位置しているか以外、何も変わっていません。そして端末（葉）は製造順に割り当てられるため、これが大きな意味を持ちます。侵害された製造ロット、クローン化されたモデル、特定の地域など、連続したブロックを無効化する場合はコストがほとんどかかりません。一方で、一千の店舗で一つずつ購入され、個別にクラックされた一千台の端末を無効化する場合にはそうはいかないのです。もう一方の極端な例を見るには、一台おきの侵害を押してみてください。全体の半数の端末が一つおきに無効化され、どちらの方式でも生き残った32台のために32個の鍵が必要になります。これは、そもそも何の方式も採用しなかった場合に支払うコストと同じです。

全プロセスの詳細解説

2r − 1 はどこから導かれるのでしょうか。 ツールでは4行目に表示されていますが、これはこの仕組み全体の基盤となる数値です。システムの規模がどれほどであっても、Subset-Difference方式のヘッダにおいて、危殆化したデバイス一台につき必要となるエントリが 2 つを超えることは決してありません。その証明はアルゴリズムの手順を数え上げるだけで済み、わずか四行で完結します。

この問題をツールで開く
1. まずはスパイン（主幹）から見ていきましょう。これは根から r 個の危殆化した葉へと至る経路の和集合です。このスパインの葉はすべて危殆化したデバイスを表しているため、最初は r 個の葉が存在します。アルゴリズムの唯一の目的は、これらをすべて処理して消し去ることです。
  
  $ST (R) has r leaves$
2. 一回のラウンドでは、二つの枝にそれぞれ未処理の葉が一つずつ残っているようなノード v を見つけます。単なる葉ではない枝に対してそれぞれ一つずつ（つまり最大で 2 つ）部分集合を出力し、その後 v 以下の部分をすべて畳み込んで、v 自身を一つの葉として扱います。
  
  $v : leaves (v_{l}) = leaves (v_{k}) = 1 ⟹ emit \leq 2 subsets S_{v_{l}, v_{i}}, S_{v_{k}, v_{j}}$
3. このラウンドで葉の数がどう変化したか数えてみてください。二つが消え、新たに一つが生まれました。つまり、元の木がどのような形をしていようと、スパインの葉は必ず一つ減ることになります。
  
  $ℓ ⟼ ℓ - 2 + 1 = ℓ - 1$
4. したがって、葉が最後に一つだけ残るまでには正確に r − 1 回のラウンドが行われます。各ラウンドで追加される部分集合は最大 2 つであり、最後に残った葉の上の部分に対して締めくくりとなる部分集合が 1 つ追加されます。
  
  $rounds (r - 1) \times subsets each 2 + closing 1 = 2 r - 1$
5. ここで重要なのは、今お話しした証明には木の深さが一切登場しないという事実です。ノード v が三階層下にあろうと三十階層下にあろうと、一回のラウンドにかかるコストは変わりません。
  
  $2 r - 1 contains no N, no lo g_{2} N, no depth$
6. さらに、この上限値はほとんどの場合においてかなり余裕があります。上限に達するのは、すべてのラウンドで両方の部分集合が出力される時だけだからです。1,048,576 台のデバイスに対してランダムに生成した 200 個の無効化セットを用いた検証では、危殆化したデバイス一台あたりのヘッダ内の平均キー数は、上限が 2 であるのに対し、64 台無効化時で 1.2513、32 台で 1.2520、10 台で 1.2580 となります。つまり、ライセンスフォーマットを設計する際の目安となる数値はおよそ 1.25r であり、システムとして保証すべき上限値が 2r − 1 なのです。
  
  $E [∣ S ∣] \approx 1.25 r against ∣ S ∣ \leq 2 r - 1$
解答

一ラウンドあたり最大 2 つの部分集合、それが r − 1 ラウンド、さらに締めくくりの 1 を足して 2(r − 1) + 1 = 2r − 1 となります。この式のどこにも N は含まれていません。Complete-Subtree方式で同じ無効化を行った場合の上限は r·log₂(N/r) であり、Subset-Difference方式はまさにこの log₂(N/r) の部分を削ぎ落としたものだと言えます。その代償として、各デバイスに保持させるキーの数は log₂N + 1 から ½log₂²N + ½log₂N + 1 へと増加します。

$∣ S_{SD} ∣ \leq 2 r - 1 vs ∣ S_{CS} ∣ \leq r lo g_{2} \frac{N}{r}$
実際のMedia Key Blockのコストはどの程度でしょうか。 ツールではヘッダのサイズをエントリ数で計算していますが、これはあくまで数学上の理論値です。実際のBlu-rayディスクでは、誰もが読み解けるフォーマットに従ってバイト単位で記録されています。AACSの仕様書にはSubset-Differenceがどのように記述されるかが明確に定められているため、実際のディスク上のヘッダサイズは推測ではなく正確に算出できます。

この問題をツールで開く
1. AACSでは、各Subset-Differenceを 1 バイトの u マスクと 4 バイトの uv 番号で識別し、それに対して 16 バイトの暗号化されたキーデータを保持します。仕様書の言葉をそのまま借りれば、「識別部に含まれる各Subset-Differenceにつき、キーデータ部には 16 バイトのキーデータが存在する」のです。一つの部分集合につき合計 21 バイト。それ以外には一切何も付加されません。
  
  $one subset-difference = m_{u} 1 + uv 4 + key data 16 = 21 bytes$
2. このカバー（被覆）のサイズこそが、ツールの計算対象です。実際には無効化されたデバイス一台につき約 1.25 エントリとなり、2 エントリを超えることは決してありません。
  
  $∣ S ∣ \approx 1.25 r typically, ∣ S ∣ \leq 2 r - 1 always$
3. つまりMedia Key Blockのサイズは、無効化されたデバイス一台あたり約 26 バイトとなります。サイズの計算はこれですべてです。排除されるプレイヤーの数にのみ正比例し、システムの総数は式のどこにも現れません。
  
  $MKB \approx 21 \times 1.25 r = 26.25 r bytes$
4. 同じ条件で無効化を行った場合について、二つの方式を並べて比較してみましょう。Subset-Differenceの列が実際に製品化されている姿であり、Complete-Subtreeの列は、このより単純な方式を採用した場合に同じ無効化処理にかかっていたであろうコストを示しています。
  
  $r 100 1, 000 10, 000 S_{SD} 125 1, 250 12, 500 bytes 2, 625 26, 250 262, 500 S_{CS} 2, 436 21, 034 177, 123 bytes 51, 156 441, 714 3, 719, 583$
5. この二つ目の列に、木の高さが影響を及ぼしてきます。2³¹ 台のデバイス（32 ビットの uv 番号で指定できる最大数）を持つシステムにおいて、1,000 台のプレイヤーを無効化するとします。この時、Subset-Differenceの約 1,250 エントリに対し、Complete-Subtreeでは約 21,000 エントリを消費します。なぜなら log₂(2³¹/1000) は約 21 であり、無効化されたすべてのデバイスがこのコストを負担するからです。
  
  $2^{31} devices : lo g_{2} \frac{2 ^{31}}{1 0 ^{3}} \approx 21 ⟹ S_{CS} \approx 21, 000$
解答

Media Key Blockのサイズは、無効化デバイス一台あたりおよそ 26 バイトで推移します。100 台で 2.6 kB、1,000 台で 26 kB、10,000 台で 262 kB となり、理論上の最悪ケースであっても 42 kB、420 kB、4.2 MB を超えることはありません。Subset-Differenceが 26 kB で済むところを、Complete-Subtreeでは 442 kB も要求されます。ここから、ツールには表示されない二つの事柄が導かれます。一つ目は、ディスクは一度プレスされると二十年間読み取られ続けるため、MKBはひたすら大きくなる一方だということです。識別部が完全なノードアドレスではなく 5 バイトに抑えられている理由も、フォーマットがキーデータを交互に配置せず独立したブロックにまとめている理由も、すべてここにあります。二つ目は、25 GB のディスク容量からすれば 26 kB のヘッダなど無に等しいという事実です。Subset-Difference方式が勝利した理由は、決してそのバイト数ではありませんでした。競合する方式ではシステムの規模に比例してサイズが肥大化してしまうのに対し、今日プレスされた一枚のディスクが 2040 年のデバイスにも対応し続けなければならないという現実こそが決め手だったのです。

$MKB \approx 26.25 r bytes vs 21 r lo g_{2} \frac{N}{r} bytes$

学習の道すじ

映像配信の保護：デバイスを無効化し、出所を突き止める

参考文献 (3)

Both schemes on this page, the two bounds, and the algorithm the worked problem follows: D. Naor, M. Naor and J. Lotspiech, "Revocation and Tracing Schemes for Stateless Receivers." Advances in Cryptology — CRYPTO 2001, LNCS 2139, pp. 41–62.
Why this scheme rather than a nicer one: the Media Key Block on a Blu-ray disc is a subset-difference tree, and the specification says so in as many words. AACS LA, Advanced Access Content System (AACS): Introduction and Common Cryptographic Elements, Revision 0.91, 17 February 2006, §3.2.1 "Subset-Difference Tree Overview".
The problem before either scheme existed, and the source of the term: A. Fiat and M. Naor, "Broadcast Encryption." Advances in Cryptology — CRYPTO '93, LNCS 773, pp. 480–491.

42Math チーム · 公表された資料と照合しています。訂正のご指摘を歓迎します。