Hemlig delning

Hemlig delning (även kallad hemlig splittring ) syftar på metoder för att distribuera en hemlighet bland en grupp, på ett sådant sätt att ingen individ har någon begriplig information om hemligheten, men när ett tillräckligt antal individer kombinerar sina "andelar" kan hemligheten rekonstrueras. Medan osäker hemlig delning tillåter en angripare att få mer information med varje delning, är säker hemlig delning "allt eller ingenting" (där "alla" betyder det nödvändiga antalet delningar).

I en typ av hemligt delningsschema finns det en dealer och n spelare . Dealern ger en del av hemligheten till spelarna, men endast när specifika villkor är uppfyllda kommer spelarna att kunna rekonstruera hemligheten från sina aktier. Dealern åstadkommer detta genom att ge varje spelare en andel på ett sådant sätt att vilken grupp som helst av t (för tröskelvärde ) eller fler spelare tillsammans kan rekonstruera hemligheten men ingen grupp på färre än t spelare kan. Ett sådant system kallas ett ( t , n ) -tröskelschema (ibland skrivs det som ett ( n , t ) -tröskelschema).

Hemlig delning uppfanns oberoende av Adi Shamir och George Blakley 1979.

Betydelse

Hemliga delningssystem är idealiska för att lagra information som är mycket känslig och mycket viktig. Exempel inkluderar: krypteringsnycklar , missiluppskjutningskoder och numrerade bankkonton . Var och en av dessa uppgifter måste hållas mycket konfidentiella, eftersom deras exponering kan vara katastrofal; men det är också viktigt att de inte går förlorade. Traditionella metoder för kryptering är illa lämpade för att samtidigt uppnå höga nivåer av konfidentialitet och tillförlitlighet. Detta beror på att när man lagrar krypteringsnyckeln måste man välja mellan att hålla en enda kopia av nyckeln på en plats för maximal sekretess, eller att hålla flera kopior av nyckeln på olika platser för större tillförlitlighet. Att öka tillförlitligheten för nyckeln genom att lagra flera kopior minskar konfidentialitet genom att skapa ytterligare attackvektorer; det finns fler möjligheter för en kopia att hamna i orätta händer. System för hemlig delning tar itu med detta problem och tillåter att godtyckligt höga nivåer av konfidentialitet och tillförlitlighet uppnås.

Hemlig delning gör det också möjligt för distributören av hemligheten att lita på en grupp "sammanlagt". Traditionellt sett skulle det krävas att distributören fullständigt litar på alla medlemmar i gruppen för att ge en grupp en hemlighet för förvaring. Hemliga delningssystem tillåter distributören att säkert lagra hemligheten hos gruppen även om inte alla medlemmar kan lita på hela tiden. Så länge antalet förrädare aldrig är mer än det kritiska antal som behövs för att rekonstruera hemligheten, är hemligheten säker.

Hemliga delningsscheman är viktiga i molnmiljöer . Således kan en nyckel distribueras över många servrar genom en tröskelhemlig delningsmekanism. Nyckeln rekonstrueras sedan vid behov. Hemlig delning har också föreslagits för sensornätverk där länkarna kan avlyssnas genom att skicka data i delningar, vilket gör avlyssnarens uppgift svårare. Säkerheten i sådana miljöer kan göras större genom att ständigt förändra hur aktierna är uppbyggda.

"Säker" kontra "osäker" hemlighetsdelning

Ett säkert hemlighetsdelningssystem distribuerar aktier så att alla med färre än t aktier inte har mer information om hemligheten än någon med 0 aktier.

Tänk till exempel det hemliga delningsschemat där den hemliga frasen "lösenord" är uppdelad i delarna "pa––––––", "––ss––––", "––––wo––", och "––––––rd". En person med 0 andelar vet bara att lösenordet består av åtta bokstäver och skulle därför behöva gissa lösenordet från 26 ⁸ = 208 miljarder möjliga kombinationer. En person med en aktie skulle dock bara behöva gissa de sex bokstäverna, från 26 ⁶ = 308 miljoner kombinationer, och så vidare när fler personer samarbetar. Följaktligen är detta system inte ett "säkert" hemlighetsdelningssystem, eftersom en spelare med färre än t hemliga andelar kan minska problemet med att erhålla den inre hemligheten utan att först behöva skaffa alla nödvändiga andelar.

Betrakta däremot hemlighetsdelningsschemat där X är hemligheten som ska delas, Pi _är offentliga asymmetriska krypteringsnycklar och Qi _deras motsvarande privata nycklar. Varje spelare J är försedd med { P ₁ ( P ₂ (...( PN _Q ( X )))), j _} . I detta schema kan vilken spelare som helst med privat nyckel 1 ta bort det yttre lagret av kryptering, en spelare med nycklar 1 och 2 kan ta bort det första och andra lagret, och så vidare. En spelare med färre än N nycklar kan aldrig helt nå det hemliga X utan att först behöva dekryptera en publik-nyckel-krypterad blob för vilken han inte har motsvarande privata nyckel – ett problem som för närvarande tros vara beräkningsmässigt omöjligt. Dessutom kan vi se att alla användare med alla N privata nycklar kan dekryptera alla de yttre lagren för att erhålla X , hemligheten, och följaktligen är detta system ett säkert hemligt distributionssystem.

Begränsningar

Flera system för hemlighetsdelning sägs vara informationsteoretiskt säkra och kan bevisas vara det, medan andra ger upp denna ovillkorliga säkerhet för förbättrad effektivitet samtidigt som de upprätthåller tillräckligt med säkerhet för att anses vara lika säkra som andra vanliga kryptografiska primitiver. Till exempel kan de tillåta att hemligheter skyddas av andelar med entropi på 128 bitar vardera, eftersom varje del skulle anses tillräckligt för att hindra alla tänkbara nutida motståndare, vilket kräver en brute force attack av genomsnittlig storlek 2 ¹²⁷ .

Gemensamt för alla ovillkorligt säkra hemlighetsdelningssystem finns det begränsningar:

Varje andel av hemligheten måste vara minst lika stor som själva hemligheten. Detta resultat är baserat på informationsteori , men kan förstås intuitivt. Givet t − 1 andelar kan ingen som helst information fastställas om hemligheten. Den slutliga aktien måste alltså innehålla lika mycket information som själva hemligheten. Det finns ibland en lösning för denna begränsning genom att först komprimera hemligheten innan den delas, men detta är ofta inte möjligt eftersom många hemligheter (till exempel nycklar) ser ut som slumpmässiga data av hög kvalitet och därför är svåra att komprimera.
Alla hemliga delningsscheman använder slumpmässiga bitar för att konstruera delarna. För att distribuera en enbits hemlig andel med en tröskel på t andelar behövs t − 1 slumpmässiga bitar. För att distribuera en hemlighet av b bitar är entropi av ( t − 1) × b bitar nödvändig.

Trivial hemlighetsdelning

t = 1

t = 1 hemlig delning är trivialt. Hemligheten kan enkelt delas ut till alla n deltagare.

t = n

Det finns flera ( t , n ) system för hemlighetsdelning för t = n , när alla aktier är nödvändiga för att återställa hemligheten:

Koda hemligheten som ett binärt tal s av valfri längd. Ge till varje spelare i förutom den sista ett slumpmässigt binärt tal p _i av samma längd som s . Ge den sista spelaren andelen beräknad som p _n = s ⊕ p ₁ ⊕ p ₂ ⊕ ... ⊕ p _{n −1} , där ⊕ anger bitvis exklusiv eller . Hemligheten är det bitvis exklusiva-eller av alla spelarnas nummer ( pi , för 1 ≤ i ≤ n ) _.
Istället kan (1) utföras med den binära operationen i vilken grupp som helst . Ta till exempel den cykliska gruppen av heltal med addition modulo 2 ³² , vilket motsvarar 32-bitars heltal med addition definierad med det binära överflödet som kasseras. Hemligheten s kan delas in i en vektor av M 32-bitars heltal, som vi kallar v _secret . Sedan ( n − 1) av spelarna ges var och en en vektor av M 32-bitars heltal som ritas oberoende av en enhetlig sannolikhetsfördelning, med spelare i som tar emot v _i . Den återstående spelaren ges v _n = v _hemlighet − v ₁ − v ₂ − ... − v _{n −1} . Den hemliga vektorn kan sedan återställas genom att summera över alla spelarnas vektorer.

1 < t < n , och, mer allmänt, vilken önskad delmängd som helst av {1, 2, ..., n }

Svårigheten ligger i att skapa system som fortfarande är säkra, men som inte kräver alla n andelar. Föreställ dig till exempel att ett företags styrelse skulle vilja skydda deras hemliga formel. Företagets VD bör kunna komma åt formeln när det behövs, men i en nödsituation skulle tre av de 12 styrelsemedlemmarna kunna låsa upp den hemliga formeln tillsammans. Detta kan åstadkommas genom ett hemligt aktieprogram med t = 3 och n = 15 , där 3 aktier ges till presidenten och 1 ges till varje styrelseledamot.

När utrymmeseffektivitet inte är ett problem kan triviala t = n -scheman användas för att avslöja en hemlighet för alla önskade delmängder av spelarna helt enkelt genom att tillämpa schemat för varje delmängd. Till exempel, för att avslöja en hemlighet för två av de tre spelarna Alice, Bob och Carol, skapa tre ( ${\binom {3}{2}}$ ) olika t = n = 2 hemlighet aktier för s , vilket ger de tre uppsättningarna av två aktier till Alice och Bob, Alice och Carol och Bob och Carol.

Effektiv hemlighetsdelning

Det triviala tillvägagångssättet blir snabbt opraktiskt när antalet delmängder ökar, till exempel när man avslöjar en hemlighet för 50 av 100 spelare, vilket skulle kräva ( $\displaystyle {\binom {100}{50} }\approx 1,009\times 10^{29}}$ scheman som ska skapas och varje spelare att underhålla ${\binom {\binom {99}{49}}\approx 5,04\times 10^ {28}$ distinkta uppsättningar aktier för varje system. I värsta fall är ökningen exponentiell. Detta har lett till sökandet efter system som tillåter att hemligheter delas effektivt med en tröskel av spelare.

Shamirs plan

I detta schema kan valfri t av n aktier användas för att återställa hemligheten. Systemet bygger på idén att du kan anpassa ett unikt polynom med graden t − 1 till vilken uppsättning t punkter som helst som ligger på polynomet. Det krävs två punkter för att definiera en rät linje, tre punkter för att helt definiera en kvadratisk, fyra punkter för att definiera en kubisk kurva, och så vidare. Det vill säga att det krävs t punkter för att definiera ett polynom med graden t − 1 . Metoden är att skapa ett polynom av grad t − 1 med hemligheten som första koefficient och de återstående koefficienterna plockade slumpmässigt. Hitta sedan n punkter på kurvan och ge en till var och en av spelarna. När åtminstone t av de n spelarna avslöjar sina poäng, finns det tillräcklig information för att passa ett ( t − 1): e grads polynom till dem, den första koefficienten är hemligheten.

Blakleys plan

Två icke-parallella linjer i samma plan skär varandra vid exakt en punkt. Tre icke-parallella plan i rymden skär varandra vid exakt en punkt. Mer generellt skär alla n icke-parallella ( n − 1) -dimensionella hyperplan vid en specifik punkt. Hemligheten kan kodas som vilken enskild koordinat som helst för skärningspunkten. Om hemligheten är kodad med alla koordinater, även om de är slumpmässiga, så får en insider (någon som har ett eller flera av de ( n − 1) -dimensionella hyperplanen ) information om hemligheten eftersom han vet att den måste ligga på hans plan. Om en insider kan få mer kunskap om hemligheten än en utomstående kan, då har systemet inte längre informationsteoretisk säkerhet . Om bara en av de n koordinaterna används, så vet insidern inte mer än en outsider (dvs att hemligheten måste ligga på x -axeln för ett 2-dimensionellt system). Varje spelare får tillräckligt med information för att definiera ett hyperplan; hemligheten återvinns genom att beräkna planens skärningspunkt och sedan ta en specificerad koordinat för den skärningspunkten.


Blakleys schema i tre dimensioner: varje aktie är ett plan , och hemligheten är punkten där tre aktier skär varandra. Två andelar är otillräckliga för att fastställa hemligheten, även om de ger tillräckligt med information för att begränsa den till linjen där båda plan skär varandra.

Blakleys upplägg är mindre utrymmeseffektivt än Shamirs; medan Shamirs aktier bara är lika stora som den ursprungliga hemligheten, är Blakleys aktier t gånger större, där t är tröskelvärdet för antalet spelare. Blakleys system kan skärpas genom att lägga till begränsningar för vilka flygplan som kan användas som aktier. Det resulterande schemat är ekvivalent med Shamirs polynomsystem.

Använder den kinesiska restsatsen

Den kinesiska restsatsen kan också användas i hemlig delning, för den ger oss en metod för att unikt bestämma ett tal S modulo k många parvisa coprime heltal $m_{1},m_{2},...,m_{k}$ , givet att $S<\prod _{i=1} ^{k}m_{i}}$ . Det finns två hemliga delningsscheman som använder sig av den kinesiska restsatsen, Mignottes och Asmuth-Blooms scheman. De är tröskelhemlighetsdelningsscheman, där andelarna genereras genom reduktion modulo heltal $m_{i}$ och hemligheten återvinns genom att i huvudsak lösa systemet med kongruenser med hjälp av den kinesiska restsatsen.

Proaktiv hemlighetsdelning

Om spelarna lagrar sina andelar på osäkra datorservrar kan en angripare ta sig in och stjäla andelarna. Om det inte är praktiskt att ändra hemligheten kan de kompromisslösa (Shamir-stil) aktierna förnyas. Dealern genererar ett nytt slumpmässigt polynom med konstant term noll och beräknar för varje återstående spelare ett nytt ordnat par, där x-koordinaterna för det gamla och nya paret är desamma. Varje spelare lägger sedan till de gamla och nya y-koordinaterna till varandra och behåller resultatet som den nya y-koordinaten för hemligheten.

Alla ouppdaterade delningar som angriparen samlade blir värdelösa. En angripare kan bara återställa hemligheten om han kan hitta tillräckligt många andra ouppdaterade aktier för att nå tröskeln. Denna situation bör inte inträffa eftersom spelarna raderade sina gamla aktier. Dessutom kan en angripare inte återställa någon information om den ursprungliga hemligheten från uppdateringsfilerna eftersom de bara innehåller slumpmässig information.

Dealern kan ändra tröskelnumret medan han distribuerar uppdateringar, men måste alltid vara vaksam på spelare som behåller utgångna andelar.

Verifierbar hemlighetsdelning

En spelare kan ljuga om sin egen andel för att få tillgång till andra aktier. Ett verifierbart hemligt delningssystem (VSS) tillåter spelare att vara säkra på att inga andra spelare ljuger om innehållet i deras andelar, upp till en rimlig sannolikhet för fel. Sådana scheman kan inte beräknas på konventionellt sätt; spelarna måste kollektivt addera och multiplicera tal utan att någon individ vet exakt vad som adderas och multipliceras. Tal Rabin och Michael Ben-Or utvecklade ett multiparty computing- system (MPC) som gör det möjligt för spelare att upptäcka oärlighet från dealerns sida eller på en del av upp till en tredjedel av tröskelantalet spelare, även om dessa spelare samordnas av en "adaptiv" angripare som kan ändra strategier i realtid beroende på vilken information som har avslöjats.

Beräkningssäker hemlig delning

Nackdelen med ovillkorligt säkra hemliga delningsscheman är att lagring och överföring av andelarna kräver en mängd lagrings- och bandbreddsresurser som motsvarar storleken på hemligheten gånger antalet andelar. Om storleken på hemligheten var betydande, säg 1 GB, och antalet aktier var 10, måste 10 GB data lagras av aktieägarna. Alternativa tekniker har föreslagits för att kraftigt öka effektiviteten hos hemliga delningsscheman, genom att avstå från kravet på ovillkorlig säkerhet.

En av dessa tekniker, känd som hemlig delning gjort kort , kombinerar Rabins informationsspridningsalgoritm (IDA) med Shamirs hemliga delning. Data krypteras först med en slumpmässigt genererad nyckel, med hjälp av en symmetrisk krypteringsalgoritm. Därefter delas denna data upp i N bitar med hjälp av Rabins IDA. Denna IDA är konfigurerad med ett tröskelvärde, på ett sätt som liknar hemliga delningsscheman, men till skillnad från hemliga delningsscheman växer storleken på den resulterande datan med en faktor på (antal fragment/tröskelvärde). Till exempel, om tröskeln var 10 och antalet IDA-producerade fragment var 15, skulle den totala storleken på alla fragment vara (15/10) eller 1,5 gånger storleken på den ursprungliga inmatningen. I det här fallet är detta schema 10 gånger mer effektivt än om Shamirs schema hade tillämpats direkt på data. Det sista steget i hemlig delning är att använda Shamirs hemliga delning för att producera andelar av den slumpmässigt genererade symmetriska nyckeln (som vanligtvis är i storleksordningen 16–32 byte) och sedan ge en aktie och ett fragment till varje aktieägare.

Ett relaterat tillvägagångssätt, känd som AONT-RS, tillämpar en Allt-eller-inget-transformation på data som ett förbearbetningssteg till en IDA. Allt-eller-inget-transformationen garanterar att ett valfritt antal andelar som är mindre än tröskeln är otillräckligt för att dekryptera data.

Multi-hemlig och utrymmeseffektiv (batchad) hemlighetsdelning

Ett informationsteoretiskt säkert k -of -n hemlighetsdelningsschema genererar n andelar, var och en av storleken på åtminstone hemligheten själv, vilket leder till att den totala nödvändiga lagringen är åtminstone n - gånger större än hemligheten. I multi-hemlig delning designad av Matthew K. Franklin och Moti Yung , flera punkter i polynomets värdhemligheter; metoden visade sig vara användbar i många tillämpningar från kodning till flerpartsberäkningar. I rymdeffektiv hemlighetsdelning, utarbetad av Abhishek Parakh och Subhash Kak , är varje andel ungefär lika stor som hemligheten dividerad med k − 1 .

Detta schema använder sig av upprepad polynominterpolation och har potentiella tillämpningar för säker informationsspridning på webben och i sensornätverk . Denna metod är baserad på datapartitionering som involverar rötterna till ett polynom i ändligt fält. Vissa sårbarheter i relaterade rymdeffektiva hemlighetsdelningssystem påpekades senare. De visar att ett schema baserat på interpolationsmetod inte kan användas för att implementera ett ( k , n ) -schema när de k hemligheterna som ska distribueras genereras från ett polynom med grad mindre än k −1 , och schemat inte fungerar om alla av hemligheterna som ska delas är desamma osv.

Andra användningsområden och tillämpningar

Ett hemligt delningsschema kan säkra en hemlighet över flera servrar och förbli återställningsbar trots flera serverfel. Återförsäljaren kan agera som flera distinkta deltagare och fördela aktierna mellan deltagarna. Varje aktie kan lagras på en annan server, men dealern kan återställa hemligheten även om flera servrar går sönder så länge de kan återställa minst t aktier ; Knäckare som bryter sig in på en server skulle dock fortfarande inte veta hemligheten så länge som färre än t aktier lagras på varje server.

Detta är ett av huvudkoncepten bakom datorprojektet Vanish vid University of Washington , där en slumpmässig nyckel används för att kryptera data, och nyckeln distribueras som en hemlighet över flera noder i ett P2P -nätverk. För att dekryptera meddelandet måste åtminstone t noder på nätverket vara tillgängliga; principen för detta specifika projekt är att antalet hemliga delningsnoder på nätverket kommer att minska naturligt över tiden, vilket gör att hemligheten så småningom försvinner . Nätverket är dock sårbart för en Sybil-attack , vilket gör Vanish osäkert.

Varje aktieägare som någon gång har tillräckligt med information för att dekryptera innehållet när som helst kan ta och lagra en kopia av X. Följaktligen, även om verktyg och tekniker som Vanish kan göra data omöjlig att återställa inom sitt eget system efter en tid, är det inte möjligt att tvinga bort data när en illvillig användare har sett den. Detta är en av de ledande gåtorna inom Digital Rights Management .

En återförsäljare kan skicka t aktier, som alla är nödvändiga för att återställa den ursprungliga hemligheten, till en enda mottagare. En angripare skulle behöva avlyssna alla t delningar för att återställa hemligheten, en uppgift som är svårare än att fånga upp en enskild fil, särskilt om delningarna skickas med olika media (t.ex. en del över Internet, en del skickas på CD-skivor ).

För stora hemligheter kan det vara mer effektivt att kryptera hemligheten och sedan distribuera nyckeln med hjälp av hemlig delning.

Hemlig delning är en viktig primitiv i flera protokoll för säker flerpartsberäkning . Hemlig delning kan också användas för användarautentisering i ett system.

Se även

Åtkomststruktur
Bysantinsk feltolerans
Raderingskod – När data som ska rekonstrueras inte är en hemlighet
Homomorf hemlighetsdelning – Ett förenklat decentraliserat röstningsprotokoll.
Ortogonal array – Används för att konstruera några tröskelscheman.
Hemlig delning med den kinesiska restsatsen
Säker flerpartsberäkning
Shamirs hemlighetsdelning
Visuell kryptografi

externa länkar

Ubuntu Manpage: gfshare – förklaring av Shamir Secret Sharing i GF(2 ⁸ )
Beskrivning av Shamirs och Blakleys planer
Patent för användning av hemlig delning för att återställa PGP (och andra?) lösenordsfraser US Patent 6,662,299
En bibliografi om system för hemlighetsdelning
Kodsigneringssystem som använder Shared Secret at the Wayback Machine (arkiverad 14 februari 2008)
Beimel, Amos (2011). "Secret-Sharing Schemes: A Survey" (PDF) .