Seadme tühistamine teisi teavitamata

Igas seadmes on võtmed, üks neist lekib ja litsents peab kõigi teiste jaoks edasi toimima. Määrake seadmete koguarv ja kompromiteeritute hulk. Tööriist koostab mõlemad katted, mille Naor, Naor ja Lotspiech 2001. aastal defineerisid. Seejärel joonistab see teie valitud variandi ning loendab, mida päis endas kandma peab.

Näidisarvutus — Seadme tühistamine teisi teavitamata

Võtmeid päises	4
Päise suurus (16 baiti võti)	64 B

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Seadme tühistamine teisi teavitamata

Edastuskrüpteerimise korral jõuab sama krüpteeritud film kõikide seadmeteni ja litsents määrab, kes tohib selle avada. Kujutage seadmeid kahendpuu lehtedena ning andke igale sõlmele isiklik võti; seade saab kõik võtmed teekonnal oma lehest kuni juureni, seega kokku log₂N + 1 võtit. Iga sõlm määratleb niiviisi seadmete hulga ehk kõik temast allpool asuvad seadmed. Litsentsi päises on filmi võti krüpteeritud ühe korra iga hulga jaoks kogumis, mis katab ausad seadmed ja jätab kompromiteeritud välja. Seadme õiguste tühistamine tähendab seega teistsuguse kogumi valimist.

Mida iga sümbol tähendab

N: kui palju seadmeid on olemas, siinses kontekstis alati kahe aste, et puu oleks täielik
r: kui mitu neist on kompromiteeritud ja tuleb blokeerida
S(i,j): alamhulkade vahe: kõik sõlme i all olevad seadmed peale nende, mis asuvad sõlme j all. Just see lubabki ühel päisekirjel üksikust vigasest lehest mööda minna

Eeldab: Eeldatakse, et tühistatud seadet ei saa parandada, vaid ainult välistada, ning see ei unusta kunagi saadud võtmeid. Just seda tähistabki artikli pealkirjas mõiste "olekuta vastuvõtja". Sel põhjusel on lahenduseks katteülesanne ja mitte võtmete uuendamine. Kellelegi ei saa uut võtit saata, sest selle saaks kätte ka seade, mis oma võtmed lekitas.
Ei kehti, kui: Kogu loogika variseb kokku, kui kompromiteeritud seadmed paiknevad ühtlaselt. Mõlemad skeemid on kõige tõhusamad järjestikuste seerianumbrite puhul ning töötavad kõige halvemini siis, kui murtud on iga teine seade. Sellisel juhul pole ükski alampuu puhas ja päis vajab iga säilinud seadme tarvis üht kirjet — just nii suurt hinda tuleks maksta ka ilma igasuguse skeemita.

Päis ei tea seadmete koguarvu 🖖

Määrake kompromiteeritute arvuks 10 ja lohistage seejärel süsteemi suuruse liugurit. Täielik alampuu nõuab 1 024 seadme korral 58 võtit, 16 384 juures 98, 1 048 576 juures 158 ja 16 777 216 juures 198 võtit. Iga süsteemi kahekordistumine lisab ühe võtme kompromiteeritud seadme kohta. Igaüks neist vajab alamhulka kõigi oma teel juureni asuvate sõsarate jaoks. Alamhulkade vahe näitab aga kõigi nelja suuruse korral tulemuseks 13. Mitte 13 ja siis 14. See on seesama 13. Täpselt 13 iga suuruse juures alates 512 seadmest, mis tähendab süsteemi kolmekümne kahe tuhande kordset kasvu ilma ühegi muutuseta. Alamhulkade vahe puhul on alamhulk "kõik sõlme i all peale nende, mis asuvad sõlme j all". Üksainus kirje võib seega anda võtme 1 048 575 seadmele ja keelata selle ühele. Sügavus, milleni see ulatub, ei maksa midagi. Seetõttu ongi ülempiir 2r − 1 ega sisalda üldse muutujat N. Samal põhjusel on Blu-ray plaadi Media Key Block just alamhulkade vahe puu. Stuudiod lisavad seadmeid kakskümmend aastat järjest ja päis ei pane seda tähelegi.

Hinda maksab iga seade ühe korra 🖖

Vaadake tabeli viimast rida. Täielik alampuu küsib igalt seadmelt log₂N + 1 võtit. Miljoni seadme korral on see 21, tähistades sõlmi tema enda teel juureni. Alamhulkade vahe küsib ½log₂²N + ½log₂N + 1 võtit ehk 211. Kümme korda suurem salvestusruum teeb päise kümne hajutatud kompromiteeritud seadme korral kaheteistkümne kordselt väiksemaks. Kuuekümne nelja juures on see üheteistkümne kordne. Selline kompromiss muutub ilmseks alles siis, kui märkate, millist arvu kui tihti makstakse. Võtmed lähevad seadmesse ühe korra tehases. Päis läheb aga iga litsentsiga ja iga teosega igaveseks igasse seadmesse kaasa. 211 võtit võtab 3,4 kB välkmälu. Igaüks neist miljonist seadmest laadib siis litsentsi küsides iga kord alla 13,5 kB päise 1,23 kB asemel. See on sama argument teistpidi.

See, keda te tühistate, on olulisem kui nende arv 🖖

Vajutage nupule Üks partii miljonist ja seejärel 64 hajutatult miljonis. Tühistatakse samad 64 seadet. Alamhulkade vahe päis kasvab 3 võtmelt 77 peale ning täieliku alampuu päis 17 pealt 846 peale. Muutus vaid see, kus vigased seadmed puus asuvad. Lehti jagatakse tootmise järjekorras ja see on tugev hoob. Kompromiteeritud tootmispartii, kloonitud mudel või regioon teevad iga järjestikuse ploki tühistamise peaaegu tasuta. Tuhandest poest ostetud tuhat eraldi murtud seadet aga mitte. Skaala teise otsa nägemiseks vajutage Üle ühe. Pool seadmetest on vaheldumisi tühistatud. Mõlemad skeemid vajavad 32 ellujäänu jaoks 32 võtit, mis on sama hind, mida maksaksite ilma igasuguse skeemita.

Ülesanded täielikult lahendatud

Kust pärineb 2r − 1? Tööriist prindib selle neljandas reas. Kogu skeem toetub just sellele arvule. Olenemata süsteemi suurusest ei vaja alamhulkade vahe päis kunagi rohkem kui kaht kirjet iga kompromiteeritud seadme kohta. Tõestuseks on algoritmil põhinev loendav argument, mis mahub neljale reale.

Ava see ülesanne tööriistas
1. Alustage selgroost, mis on juurest r kompromiteeritud leheni viivate teede ühend. Selle selgroo iga leht on kompromiteeritud seade. See algab r lehega ja algoritmi ainus ülesanne on need ära süüa.
  
  $ST (R) has r leaves$
2. Üks voorudest näeb ette leida sõlm v, mille mõlemas harus on täpselt üks allesjäänud leht. Väljastage üks alamhulk iga haru jaoks, mis on midagi enamat kui paljas leht. See teeb kokku maksimaalselt kaks alamhulka. Seejärel ahendage kogu v all olev osa nii, et sõlmest v endast saab leht.
  
  $v : leaves (v_{l}) = leaves (v_{k}) = 1 ⟹ emit \leq 2 subsets S_{v_{l}, v_{i}}, S_{v_{k}, v_{j}}$
3. Loendage, mida see voor lehtedega tegi. Kaks kadus ja üks ilmus asemele. Selgroog on seega ühe lehe võrra lühem, olenemata puu väljanägemisest.
  
  $ℓ ⟼ ℓ - 2 + 1 = ℓ - 1$
4. Enne kui järele jääb üksainus leht, toimub täpselt r − 1 vooru. Iga voor lisab maksimaalselt 2 alamhulka. Seejärel lisandub üks sulgev alamhulk selle jaoks, mis viimasest lehest ülespoole jääb.
  
  $rounds (r - 1) \times subsets each 2 + closing 1 = 2 r - 1$
5. Selles argumendis ei mainitud kordagi puu sügavust ja selles ongi asja tuum. Vooru hind on sama, olenemata sellest, kas v asub kolm või kolmkümmend taset allpool.
  
  $2 r - 1 contains no N, no lo g_{2} N, no depth$
6. Peaaegu igal pool on see piire ka lõtv, sest see nõuab, et iga voor väljastaks mõlemad oma alamhulgad. Üle 200 juhusliku tühistamishulga puhul 1 048 576 seadme juures on keskmine päis 64 tühistatud seadme korral 1,2513 võtit iga kompromiteeritu kohta. 32 tühistatu korral on see 1,2520 ja 10 korral 1,2580. See vastandub ülempiirile 2. Litsentsivormingu kujundamisel tuleks seega arvestada suurusjärguga 1,25r. Garanteeritud väärtus on aga 2r − 1.
  
  $E [∣ S ∣] \approx 1.25 r against ∣ S ∣ \leq 2 r - 1$
Vastus

Maksimaalselt 2 alamhulka vooru kohta, r − 1 vooru, pluss 1 sulgemiseks teeb kokku 2(r − 1) + 1 = 2r − 1. Selles ei leidu kuskil muutujat N. Täieliku alampuu piire samade tühistamiste puhul on r·log₂(N/r). See log₂(N/r) ongi täpselt see, mille alamhulkade vahe eemaldab. Hinnaks on ½log₂²N + ½log₂N + 1 võtit iga seadme sees log₂N + 1 asemel.

$∣ S_{SD} ∣ \leq 2 r - 1 vs ∣ S_{CS} ∣ \leq r lo g_{2} \frac{N}{r}$
Palju üks tegelik Media Key Block mahtu nõuab? Tööriist arvutab päise suurust kirjetes, mis on puhtalt matemaatika. Blu-ray plaat salvestab selle aga baitides ja igale lugejale arusaadavas vormingus. AACS-i spetsifikatsioon ütleb täpselt, kuidas alamhulkade vahe kirja pannakse. See tähendab, et reaalse plaadi päise mahtu saab täpselt arvutada, mitte ei pea seda pelgalt oletama.

Ava see ülesanne tööriistas
1. AACS tuvastab iga alamhulkade vahe ühebaidise u-maski ja neljabaidise uv-numbri abil ning lisab igaühe kohta kuusteist baiti krüpteeritud võtmeandmeid. Standardi enda sõnadega öeldes: "iga tuvastusosas sisalduva alamhulkade vahe kohta on võtmeandmete osas 16 baiti võtmeandmeid". See teeb kokku kakskümmend üks baiti alamhulga kohta ja ei midagi muud.
  
  $one subset-difference = m_{u} 1 + uv 4 + key data 16 = 21 bytes$
2. Katte enda arvutabki tööriist. Praktikas koguneb iga tühistatud seadme kohta ligikaudu 1,25 kirjet, kuid see arv ei ületa kunagi kahte.
  
  $∣ S ∣ \approx 1.25 r typically, ∣ S ∣ \leq 2 r - 1 always$
3. Seega võtab Media Key Block iga tühistatud seadme kohta enda alla umbes kakskümmend kuus baiti. Sellega kogu mahuarvutus piirdubki. Tulemus kasvab lineaarselt blokeeritavate mängijate arvuga. Süsteemi kogusuurus ei mängi siin aga mingit rolli.
  
  $MKB \approx 21 \times 1.25 r = 26.25 r bytes$
4. Kõrvutame need kaks skeemi identsete tühistamiste juures. Alamhulkade vahe veerg kajastab tegelikult käibele minevat lahendust. Täieliku alampuu veerg näitab aga seda, millist mahtu oleksid samad tühistamised nõudnud lihtsama skeemi puhul.
  
  $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. Teises veerus tuleb mängu puu kõrgus. Võtame näiteks 2³¹ seadmega süsteemi, mis on suurim hulk, mida 32-bitine uv-number suudab adresseerida. Tuhande mängija tühistamine nõuab seal umbes 21 000 täieliku alampuu kirjet võrreldes 1250 alamhulkade vahe kirjega. Põhjus on selles, et log₂(2³¹/1000) on ligikaudu 21 ja see kulu lisandub iga tühistatud seadmega.
  
  $2^{31} devices : lo g_{2} \frac{2 ^{31}}{1 0 ^{3}} \approx 21 ⟹ S_{CS} \approx 21, 000$
Vastus

Media Key Blocki maht püsib umbes 26 baidi juures tühistatud seadme kohta. See teeb 2,6 kB saja mängija, 26 kB tuhande ja 262 kB kümne tuhande puhul. Isegi kõige halvema piirangute lubatud stsenaariumi korral ei ületa see maht kunagi vastavalt 42 kB, 420 kB ja 4,2 MB. Täieliku alampuu meetod nõuaks 442 kB seal, kus alamhulkade vahe vajab 26 kB. Tööriist jätab aga mainimata kaks olulist tõsiasja. Plaat pressitakse korra ja seda loetakse järgmised kakskümmend aastat, mis tähendab, et MKB saab ajas ainult kasvada. Just seetõttu on tuvastusosa pikkuseks viis baiti, mitte terve sõlme aadress. Samuti on see põhjuseks, miks vorming paigutab võtmeandmed eraldi jadasse ega põimi neid omavahel. Teiseks ei tähenda 26 kB suurune päis 25 GB plaadi kõrval sisuliselt mitte midagi. Põhjus, miks alamhulkade vahe peale jäi, ei peitunud kunagi baitides. Määravaks sai hoopis asjaolu, et alternatiivne lahendus kasvab koos süsteemi suurusega, kuid täna pressitud plaat peab suutma teenindada ka seadmeid aastast 2040.

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

Õpitee

Voogedastuse kaitsmine: tühista seade, seejärel tee kindlaks, milline neist

Allikad (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.

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.