Révoquer un appareil sans avertir les autres

Chaque appareil contient des clés. L'une d'elles fuite, et la licence doit continuer à fonctionner pour tous les autres. Définissez le nombre d'appareils existants et le nombre de compromis. L'outil construit les deux couvertures que Naor, Naor et Lotspiech ont définies en 2001, dessine celle que vous choisissez et compte ce que l'en-tête doit inclure.

Exemple résolu — Révoquer un appareil sans avertir les autres

Clés dans l'en-tête	4
Taille (16 octets par clé)	64 B

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

La théorie — Révoquer un appareil sans avertir les autres

Dans le chiffrement par diffusion, le même film chiffré parvient à tous les appareils. La licence décide ensuite qui peut l'ouvrir. Disposez les appareils sur les feuilles d'un arbre binaire. Attribuez une clé propre à chaque nœud. Vous donnez ainsi à un appareil les clés de son propre chemin, depuis sa feuille jusqu'à la racine, ce qui lui en fait log₂N + 1. Un nœud désigne alors un ensemble d'appareils : tous ceux qui dépendent de lui. L'en-tête de la licence transporte la clé du film. Cette clé est chiffrée une fois pour chaque ensemble d'une collection qui couvre les appareils intègres et isole les appareils compromis. Révoquer un appareil revient à choisir une autre collection.

Ce que signifie chaque symbole

N: le nombre total d'appareils. Il s'agit toujours ici d'une puissance de deux, afin de garantir un arbre complet
r: le nombre d'appareils compromis que vous devez bloquer
S(i,j): l'ensemble différence : tous les appareils situés sous le nœud i, moins ceux situés sous le nœud j. C'est ce qui permet à une seule entrée de l'en-tête de contourner une unique feuille compromise

Suppose: Qu'un appareil révoqué ne peut être réparé, mais seulement exclu. Il n'oublie d'ailleurs jamais les clés qu'il a reçues. C'est le sens de l'expression « récepteur sans état » dans le titre de la publication. C'est aussi la raison pour laquelle la solution relève d'un problème de couverture et non de renouvellement de clés. Personne ne peut envoyer de nouvelle clé à un appareil, car la machine qui a divulgué les siennes la recevrait tout autant.
Ne tient plus quand: Lorsque les appareils compromis sont répartis uniformément. Les deux méthodes se révèlent redoutables sur un lot de numéros de série consécutifs. Elles s'effondrent en revanche lorsqu'un appareil sur deux est touché. Dans un tel scénario, aucun sous-arbre n'est préservé. L'en-tête requiert une entrée pour chaque appareil survivant. C'est précisément le prix que vous paieriez sans l'ombre d'un système.

L'en-tête ignore le nombre total d'appareils 🖖

Réglez le nombre d'appareils compromis sur 10, puis faites glisser la taille du système. Le sous-arbre complet passe à 58 clés pour 1 024 appareils, 98 pour 16 384, 158 pour 1 048 576 et 198 pour 16 777 216. Chaque doublement du système ajoute une clé de plus par appareil compromis, car chacun exige un sous-ensemble pour chaque nœud frère sur son chemin vers la racine. La différence de sous-ensembles affiche 13 à ces quatre tailles. Non pas 13 puis 14 ; le même 13. Ce même 13 reste valable à n'importe quelle taille à partir de 512 appareils, soit une multiplication du système par trente-deux mille sans le moindre changement. Dans ce schéma, un sous-ensemble englobe « tout le monde sous le nœud i sauf ceux sous le nœud j ». Une entrée unique peut ainsi distribuer la clé à 1 048 575 appareils et la refuser à un seul, et la profondeur qu'elle atteint ne coûte rien. C'est pourquoi la borne est 2r − 1 sans qu'aucun N n'intervienne. C'est également la raison pour laquelle le bloc de clés média d'un disque Blu-ray est un arbre de différence de sous-ensembles : les studios ajoutent des appareils pendant vingt ans et l'en-tête ne s'en aperçoit pas.

Le prix est payé par chaque appareil, une seule fois 🖖

Regardez la dernière ligne du tableau. Le sous-arbre complet demande à chaque appareil log₂N + 1 clés : 21 pour un million d'appareils, soit les nœuds sur son propre chemin vers la racine. La différence de sous-ensembles en réclame ½log₂²N + ½log₂N + 1, ce qui donne 211. Dix fois plus de stockage pour réduire l'en-tête à un douzième de sa taille avec dix appareils compromis dispersés, et à un onzième avec soixante-quatre. Ce compromis saute aux yeux dès que vous observez quel nombre est payé et à quelle fréquence. Les clés entrent dans l'appareil une seule fois, à l'usine. L'en-tête, lui, part avec chaque licence pour chaque titre vers chaque appareil, pour toujours. 211 clés représentent 3,4 ko de mémoire flash. Chacun de ce million d'appareils récupère ensuite un en-tête de 13,5 ko au lieu de 1,23 ko à chaque demande de licence, ce qui est le même argument pris dans l'autre sens.

L'identité des révoqués compte plus que leur nombre 🖖

Cliquez sur Un lot sur un million, puis sur 64 dispersés sur un million. Les 64 mêmes appareils sont révoqués. L'en-tête de la différence de sous-ensembles passe de 3 clés à 77, et celui du sous-arbre complet de 17 à 846. Rien ne change hormis la position des appareils défectueux dans l'arbre. Les feuilles sont distribuées dans l'ordre de fabrication, ce qui en fait un puissant levier : une série de production compromise, un modèle cloné ou une région entière (bref, tout ce qui révoque un bloc contigu) ne coûte presque rien. En revanche, un millier de boîtiers piratés individuellement et achetés dans un millier de boutiques coûtera très cher. Cliquez sur Un appareil sur deux pour observer l'autre extrême. La moitié des appareils y est révoquée en alternance. Les deux schémas nécessitent alors 32 clés pour 32 survivants. C'est exactement le prix que vous paieriez sans aucun schéma.

Problèmes entièrement résolus

D'où vient 2r − 1 ? L'outil l'affiche sur la quatrième ligne. Tout le système repose sur ce nombre. Quelle que soit la taille du système, un en-tête de différence de sous-ensembles ne requiert jamais plus de deux entrées par appareil compromis. La démonstration s'appuie sur un argument de dénombrement appliqué à l'algorithme, et elle tient en quatre lignes.

Ouvrez ce problème dans l'outil
1. Commencez par le squelette : la réunion des chemins reliant la racine aux r feuilles compromises. Chaque feuille de ce squelette représente un appareil compromis. L'algorithme part donc de r feuilles. Son unique tâche consiste à les éliminer.
  
  $ST (R) has r leaves$
2. Un tour se déroule ainsi : cherchez un nœud v dont les deux branches contiennent chacune exactement une feuille restante. Générez un sous-ensemble pour chaque branche qui ne se réduit pas à une simple feuille, soit au plus deux sous-ensembles. Contractez ensuite tout ce qui se trouve sous v, de sorte que v devienne lui-même une feuille.
  
  $v : leaves (v_{l}) = leaves (v_{k}) = 1 ⟹ emit \leq 2 subsets S_{v_{l}, v_{i}}, S_{v_{k}, v_{j}}$
3. Mesurez l'effet de ce tour sur les feuilles. Deux d'entre elles ont disparu et une nouvelle est apparue. Le squelette compte ainsi une feuille de moins, quelle que soit la forme de l'arbre.
  
  $ℓ ⟼ ℓ - 2 + 1 = ℓ - 1$
4. Il faut donc compter exactement r − 1 tours avant de n'obtenir plus qu'une seule feuille. Chacun de ces tours ajoute au plus 2 sous-ensembles. Un dernier sous-ensemble vient clore ce qui reste au-dessus de cette ultime feuille.
  
  $rounds (r - 1) \times subsets each 2 + closing 1 = 2 r - 1$
5. Rien dans ce raisonnement n'évoque la profondeur de l'arbre, et c'est là tout l'enjeu. Le coût d'un tour reste le même, que le nœud v se trouve à trois ou trente niveaux de profondeur.
  
  $2 r - 1 contains no N, no lo g_{2} N, no depth$
6. Cette borne s'avère par ailleurs large presque partout, car elle suppose que chaque tour génère ses deux sous-ensembles. Sur 200 ensembles de révocation générés pour 1 048 576 appareils, l'en-tête moyen compte 1,2513 clés par appareil compromis pour 64 révocations. Il passe à 1,2520 pour 32 et s'établit à 1,2580 pour 10, contre une borne fixée à 2. La valeur de référence pour concevoir un format de licence se situe donc autour de 1,25r, et la valeur garantie reste de 2r − 1.
  
  $E [∣ S ∣] \approx 1.25 r against ∣ S ∣ \leq 2 r - 1$
Réponse

Au plus 2 sous-ensembles par tour, r − 1 tours, plus 1 pour conclure : 2(r − 1) + 1 = 2r − 1, sans que N n'apparaisse nulle part. La borne du sous-arbre complet s'élève à r·log₂(N/r) pour les mêmes révocations. Ce facteur log₂(N/r) correspond très exactement à ce qu'élimine la différence de sous-ensembles. Le prix de cette opération se traduit par ½log₂²N + ½log₂N + 1 clés stockées dans chaque appareil, au lieu de log₂N + 1.

$∣ S_{SD} ∣ \leq 2 r - 1 vs ∣ S_{CS} ∣ \leq r lo g_{2} \frac{N}{r}$
Combien coûte un véritable Media Key Block ? L'outil compte un en-tête en entrées, ce qui relève des mathématiques. Un disque Blu-ray le stocke en octets, dans un format lisible par tous. La spécification AACS décrit très exactement comment s'écrit une différence de sous-ensembles. La taille de l'en-tête sur un disque physique peut donc être mesurée de façon précise, au lieu d'être simplement estimée.

Ouvrez ce problème dans l'outil
1. L'AACS identifie chaque différence de sous-ensembles par un masque u d'un octet ainsi qu'un nombre uv de quatre octets. Le format transporte seize octets de données de clé chiffrée associées. Pour reprendre les termes exacts de la spécification : « pour chaque différence de sous-ensembles incluse dans la partie d'identification, il y a 16 octets de données de clé dans la partie de données de clé ». Vingt et un octets par sous-ensemble, et absolument rien d'autre.
  
  $one subset-difference = m_{u} 1 + uv 4 + key data 16 = 21 bytes$
2. La couverture elle-même correspond à ce que calcule l'outil. Comptez environ 1,25 entrée par appareil révoqué en pratique, et jamais plus de deux.
  
  $∣ S ∣ \approx 1.25 r typically, ∣ S ∣ \leq 2 r - 1 always$
3. Un Media Key Block pèse donc environ vingt-six octets par appareil révoqué. Le calcul de taille s'arrête là. Sa progression est linéaire par rapport au nombre de lecteurs exclus, sans jamais faire intervenir la taille du système.
  
  $MKB \approx 21 \times 1.25 r = 26.25 r bytes$
4. Comparez les deux schémas pour les mêmes révocations. La colonne de la différence de sous-ensembles indique ce qui est réellement déployé. La colonne du sous-arbre complet montre ce que ces mêmes révocations auraient coûté avec l'approche plus simple.
  
  $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. La hauteur de l'arbre entre en jeu dans la deuxième colonne. Dans un système de 2³¹ appareils, la limite supérieure qu'un nombre uv de 32 bits puisse adresser, la révocation de mille lecteurs exige environ 21 000 entrées de sous-arbre complet. La différence de sous-ensembles n'en demande que 1 250. La valeur de log₂(2³¹/1000) tourne autour de 21, et chaque appareil révoqué en paie le prix.
  
  $2^{31} devices : lo g_{2} \frac{2 ^{31}}{1 0 ^{3}} \approx 21 ⟹ S_{CS} \approx 21, 000$
Réponse

Un Media Key Block s'élève à environ 26 octets par appareil révoqué. Cela représente 2,6 ko pour cent lecteurs, 26 ko pour mille et 262 ko pour dix mille. Il ne dépasse jamais 42 ko, 420 ko et 4,2 Mo dans le pire scénario autorisé par la borne. Le sous-arbre complet exigerait 442 ko là où la différence de sous-ensembles se contente de 26 ko. Il en découle deux conséquences que l'outil n'affiche pas. Le disque est pressé une seule fois et lu pendant vingt ans. Un MKB ne fait donc que croître. C'est pour cette raison que la partie d'identification se limite à cinq octets au lieu d'une adresse de nœud complète, et que le format place les données de clé dans une séquence séparée plutôt que de les entrelacer. Par ailleurs, un en-tête de 26 ko ne représente qu'une goutte d'eau face à un disque de 25 Go. La différence de sous-ensembles ne s'est jamais imposée pour une simple question d'octets. L'approche alternative croît avec la taille du système, or un disque pressé aujourd'hui doit encore servir les appareils de 2040.

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

Parcours

Protéger un flux : révoquer un appareil, puis identifier lequel

Références (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.

Par l’équipe 42Math · Vérifié sur des sources publiées. Corrections bienvenues.