CODEERMACHINES EN CRYPTOGRAFIE
Secret Splitting
Home


Wat is Secret Splitting

Secret splitting, ook wel secret sharing genoemd, splitst geheime informatie in verschillende delen (shares) om deze in bewaring te geven bij verschillende personen (shareholders) zonder de geheime informatie zelf te onthullen. De uitdrukkingen splitting en sharing zijn een beetje misleidend aangezien we het geheim niet splitsen maar berekenen en we het niet geheim zelf maar de verantwoordelijkheid delen. Er zijn twee types secret splitting.

Bij het eerste type heb je alle shares nodig om de originele informatie terug te halen. De informatie van één apar share onthult absoluut geen informatie over de geheime informatie en helpt op geen enkele wijze om het geheim te onthullen. Het is wiskundig onmogelijk om de geheime informatie te verkrijgen indien één van de shares niet beschikbaar is. De aparte shares zijn informatie-theoretisch veilig, lees onkraakbaar.

Bij het tweede type heb je niet alle shares nodig om de geheime informatie terug te halen. De veiligheid van deze methode hangt af van wiskundige complexiteit om onthulling van het geheim te voorkomen en garandeert daarom geen informatie-theoretische absolute veiligheid.

Natuurlijk splitsen we de geheime informatie niet simpelweg in twee of meerdere shares aangezien dit minstens een deel van de informatie zou onthullen en aanwijzingen kan geven om de rest van het geheim te vinden. Op deze pagina bespreken we de onkraakbare versie van secret splitting waarbij alle shares nodig zijn.

Waar gebruiken we Secret Splitting

Secret splitting is vooral geschikt in situaties waarbij je een geheime code, wachtwoord of dergelijke moet delen met verschillende personen maar je twijfelt aan de betrouwbaarheid van sommigen onder hen. Je wil niet dat één persoon de informatie misbruikt achter anderen hun rug. Een persoon mag misschien wel recht hebben op de geheime informatie maar dat wil daarom niet zeggen dat je hem de volledige controle wilt geven over die informatie. Met secret splitting is misbruik of ongeoorloofde onthulling van de geheime informatie onmogelijk indien er minstens één betrouwbare persoon is in de groep waarmee u het geheim deelt. En het geweldige is dat meer personen meer veiligheid betekend omdat meer personen moeten toestemmen om hun shares samen te voegen. Dat is net het tegenovergestelde van het geheim zelf delen, waarbij meer personen meer risico betekend.

Dit is bijzonder interessant in situaties waar verschillende personen samen verantwoordelijkheid dienen te nemen voor toegang tot beschermde informatie of materiaal, of tot een apparaat met beperkte toegang. Een voorbeeld is een persoon die gevoelige informatie of waardevolle goederen in een kluis bewaart en twee personen aanduid die in geval van nood de kluis kunnen openen. Beide personen ontvangen een share en kunnen de kluis enkel samen openen. Dit kan bijvoorbeeld een ouder zijn die zijn geld, documenten en waardevolle voorwerpen in een kluis opbergt en de nummercombinatie splitst. Alle kinderen ontvangen een share en in geval van nood of overlijden van de ouder hebben zij enkel toegang tot de kluis indien zij allemaal toestemmen on hun shares samen toe voegen.

Enkele ander toepassingen zijn het delen van een geheim wachtwoord voor toegang tot vertrouwelijke computerdata, vercijferde bestanden, een digitaal slot van een lokaal of om een alarmsysteem in of uit te schakelen. Het meest extreme voorbeeld is de lanceerinrichting van een nucleaire raket, waar tenminste twee personen akkoord moeten zijn om de code in te geven en de Grote Rode Knop te drukken.

Secret splitting maakt ook delegeren vanop afstand via onveilige kanalen mogelijk. Je genereert een share voor jezelf en voor één of meerdere andere personen. Zo kan je aan de andere kant van de wereld verblijven en jouw share versturen naar alle andere personen die ook een share kregen, om hen toegang te geven tot een safe, vercijferd computerbestand of dergelijke. De shareholders kunnen de originele code enkel onthullen op het moment dat jij beslist je share vrij te geven en zij bovendien allen akkoord gaan. Je kunt jouw share versturen via eender welk onveilig kanaal zoals e-mail, chat, telefoon aangezien dat ene share absoluut geen informatie onthult over de originele geheime code.

Secret Splitting kan ook gebruikt worden om het risico op onderschepping bij versturen van codes, sleutels of andere gegevens te verkleinen. Men kan bijvoorbeeld een code via verschillende wegen versturen naar de bestemmeling. Een code, in vier gesplitst, kan via e-mail, post, via SMS met GSM én telefonisch verzonden worden, en dit op verschillende tijdstippen. Dit betekend dat diegene die de code wil bemachtigen zowel e-mail, post, GSM en telefoonverkeer van de verzender gedurende lange tijd dient af te luisteren en te onderscheppen wat enorm veel tijd en middelen vereist. Eén gemist share maakt de reconstructie van de code onmogelijk voor de onderschepper.

Types van Splitting en Sharing

Er zijn twee types van secret splitting, in cryptografie ook wel secret sharing genoemd. De manuele methode, beschreven op deze pagina, vereist alle shares om de geheime informatie te onthullen. De threshold (aantal nodige shares) is gelijk aan het aantal shares, aangeduid als threshold = number of shares of t = n. Het voordeel is dat we hierdoor een onkraakbaar systeem hebben zolang minstens één share geheim bijft. Dit kan problemen veroorzaken indien één share verloren raakt, tenzij je een backup hebt. Een ander voordeel is dat deze methode, gebaseerd op one-time pad encryptie, kan uitgevoerd worden met pen en papier. Je kunt de Secure Code Splitter template downloaden om zelf de combinatie van je kluis or een wachtwoord te splitsen.

Indien je de geheime informatie wilt kunnen terughalen met minder shares dan er gecreëerd werden moet je werken met subsets. Wanneer bijvoorbeeld Alice, Bob en John elk een share hebben en je wilt dat 2 van 3 shares voldoende zijn om het geheim vrij te geven dan heb je drie subsets nodig van twee shares: Alice-Bob, Alice-John en Bob-John. Voor elke subset dienen natuurlijk andere willekeurige shares gegenereerd te worden. Het nadeel van zulke subsets is dat hun aantal al snel onpraktisch worden. Voor 3 van 5 shares heb je 10 subsets nodig en voor 3 van 6 heb je al 19 subsets nodig. Daarom zij subsets enkel geschikt voor een klein aantal shares.

Secret sharing met threshold maakt reconstructie van geheime informatie mogelijk met minder shares dan het totaal aantal shares, aangeduid als t < n. Je hebt geen subsets nodig en elke persoon ontvangt slechts één share. Als je bijvoorbeeld 5 shares hebt met een threshold van 3 dan kan je met eender welke 3 shares de geheime informatie onthullen. Verlies van een share zal onthulling niet onmogelijk maken zolang minsten het threshold aantal shares beschikbaar zijn, dit in tegenstelling tot secret splitting zonder threshold. Alle threshold methodes zijn gebaseerd op polynomiale interpolatie (Adi Shamir) or hypervlakken (George Blake) en garanderen geen absolute veiligheid. Helaas vereisen deze methodes complexe berekeningen en zijn dus niet geschikt voor gebruik met pen en papier.

Hoe werkt Secret Splitting

Het principe van secret splitting met t = n, waarbij alle shares nodig zijn om het geheim te reconstrueren, is gebaseerd op one-time pad vercijfering. Alle berekeningen zijn modulo 10 (optellen zonder overdracht en aftrekken zonder lenen). De geheime informatie word vercijferd met een of meerdere echt willekeurige sleutels en, in tegenstelling tot verzenden van de vercijferde geheime tekst naar de ontvanger, gebruiken we de willekeurige sleutel(s) en vercijferde informatie als shares. Enkel one-time pad biedt de absolute veiligheid die nodig is om de shares te creëren. Alle berekeningen kunnen met de hand gebeuren en secret splitting is daarom door iedereen gemakkelijk uit te voeren zonder speciale kennis van cryptografie. Laat ons het principe verklaren in een voorbeeld:

Charlie splitst de geheime nummercombinatie 21 46 03 88 van zijn kluis. Een willekeurige share wordt getal per getal afgetrokken zonder lenen (modulo 10) van de originele nummercombinatie (bv. 3 - 7 = 13 - 7 = 6).



 Charlie's combinatie     21 46 03 88    
 Willekeurige share     - 27 03 77 61
                          -----------
                          04 43 36 27 


 Alice's share = 27 03 77 61

 Bob's share   = 04 43 36 27

Alice's share bevat enkel willekeurige getallen. Bob's share is Alice's share, afgetrokken van de geheime combinatie, wat een willekeurig resultaat oplevert. Beide shares zijn op zich dus willekeurig en bevatten absoluut geen informatie over de geheime combinatie. Hierdoor zij de shares onkraakbaar zolang de shares apart gehouden worden.

De geheime combinatie kan eenvoudig bekomen worden door de twee shares bij elkaar op te tellen zonder overdracht (bv. 7 + 4 = 1 en niet 11).



 Alice's share   27 03 77 61               
 Bob's share   + 04 43 36 27
 ---------------------------
                 21 46 03 88


 Charlie's combinatie:  21 46 03 88 

Voor elk bijkomende share moeten we een bijkomende willekeurige share aanmaken. Als we de geheime informatie splitsen in 5 delen hebben we dus 4 willekeurige delen en één resultaat-deel nodig. In dit geval moeten alle willekeurige sleutels afgetrokken worden van de originele informatie.

Een voorbeeld met het geheime getal 2 splitsen in vier delen. We creëren drie willekeurige shares 5, 9 en 3. Het resultaat share is dus 2 - 5 - 9 - 3 = 5 want (1)2 - 5 = 7 en (1)7 - 9 = 8 en 8 - 3 = 5. De vier shares zijn dus 5, 9, 3 en 5. Om het origineel te reconstrueren nemen we 5 + 9 + 3 + 5 = (2)2

We kunnen ook tekst splitsen. Dan moeten we eerst de tekst omzetten in getallen. Dit kan gebeuren door elke letter een waarde toe te kennen. Gebruik de nummers 01 tot 26 voor de letters A tot Z, 30 tot 39 voor de cijfers 0 tot 9 en 00 voor een spatie, of ieder ander eenvoudig omzettingssysteem dat aan uw noden voldoet. Deze methode van letter-naar-nummer conversie hoeft niet geheim te zijn! De tekst kan een geheim paswoord, instructies, rekeningnummers, een code of gewoon een hele tekst zijn.



 Geheime tekst               M  O  N  A  L  I  S  A    
 Geconverteerd              13 15 14 01 12 09 19 01
 Willek. share   (deel 1) - 52 71 30 94 52 86 62 13
                            -----------------------
 Resultaat (deel 2)         61 44 84 17 60 23 57 98


 Alice's share = 5271 3094 5286 6213

 Bob's share   = 6144 8417 6023 5798

Om de originele informatie terug te bekomen tellen we gewoon de delen terug samen zonder overdracht en converteren de getallen terug naar letters.

Computer Data Splitsen

We kunnen secret splitting ook toepassen op computerdata. Om gelijk welk type computerbestand te splitsen moeten we eerst een willekeurig share genereren met dezelfde lengte als het bestand. Dit willekeurige bestand zal het eerste share zijn. Het tweede share wordt aangemaakt door het originele bestand te XOR-en met het willekeurig share. Om de originele data terug samen te stellen dient men enkel alle shares met de XOR functie samen te voegen, en dit in eender welke volgorde.

In het volgende voorbeeld splitsen we een byte in twee delen:


 Geheime Data                01011010           XOR Tabel      
 Willek. bits (share 1)  XOR 11101011          -----------
                             --------          0 XOR 0 = 0
 Resultaat    (share 2)      10110001          0 XOR 1 = 1
                                               1 XOR 0 = 1
                                               1 XOR 1 = 0

We kunnen bytes ook splitsen in meer dan twee shares. Voor elk nieuw share voegen we een nieuwe reeks willekeurige bits toe en XOR-en deze met de andere shares:


 Geheime Data                10011100    
 Willek. bits (share 1)  XOR 01001011
 Willek. bits (share 2)  XOR 11010001
 Willek. bits (share 3)  XOR 00101011
                             --------
 Resultaat    (share 4)      00101101

De software, gebruikt voor het secret splitting, moet gebruikt worden op een veilige computer en mag geen sporen nalaten na het aanmaken van de shares. Dit omvat ook het veilig wissen van het originele bestand (de normale verwijder-functie van uw computer is niet voldoende!). De secret splitting software dient aan dezelfde kwaliteitsstandaard te voldoen als degelijke cryptografische software op het gebied van geheugenbeheer, veilige bestandsverwerking en genereren van werkelijk willekeurige getallen (zie vereisten willekeur in volgende sectie). De gesplitste delen dienen ook veilig bewaard te worden op externe media of, minder aan te raden, verschillende computers.

Secret Splitting veilig houden

In de voorbeelden kunnen we zien dat het principe van one-time pad gebruikt is. Het verschil met one-time pad is dat we geen bericht verzenden en dat we de willekeurige sleutel niet vernietigen. Om de absolute veiligheid te garanderen dienen we ons echter te houden aan twee belangrijke veiligheidsregels:

De eerste regel is het genereren van werkelijk willekeurige getallen, net zoals bij one-time pad vercijfering. Om zulke werkelijke willekeur te genereren zijn er verschillende methodes. Een goede bron voor willekeur zijn tien-zijdige dobbelstenen (zie foto). Met vijf zulke stenen kan je snel een groep van 5 cijfers maken.

Gebruik nooit gewone dobbelstenen door twee stenen samen te tellen en twee waarden te negeren. Deze methode is statistisch ongeschikt om de waarden 0 tot 9 te produceren en dus absoluut onveilig (het totaal 7 zal zo'n 6 keer meer voorkomen dan 2 of 12).

Gebruik daarom één zwarte en één witte dobbelsteen en ken een waarde toe aan elk van de 36 combinaties, rekening houdende met de volgorde en kleur van de steen (zie tabel hieronder). Deze methode geeft een 0.277 waarschijnlijkheid (1 op 36) voor elke combinatie. Hiermee kunnen we drie reeksen met de waarden 0 tot 9 produceren. De overige 6 combinaties (met zwarte 6) kunnen eenvoudigweg genegeerd worden, wat statistisch geen effect heeft op de andere combinaties.


 Z   W        Z   W        Z   W       Z   W       Z   W       
 1 + 1 = 0    2 + 1 = 6    3 + 1 = 2   4 + 1 = 8   5 + 1 = 4
 1 + 2 = 1    2 + 2 = 7    3 + 2 = 3   4 + 2 = 9   5 + 2 = 5
 1 + 3 = 2    2 + 3 = 8    3 + 3 = 4   4 + 3 = 0   5 + 3 = 6
 1 + 4 = 3    2 + 4 = 9    3 + 4 = 5   4 + 4 = 1   5 + 4 = 7
 1 + 5 = 4    2 + 5 = 0    3 + 5 = 6   4 + 5 = 2   5 + 5 = 8
 1 + 6 = 5    2 + 6 = 1    3 + 6 = 7   4 + 6 = 3   5 + 6 = 9

             Negeer alle combinaties met zwarte 6 

Een andere methode is een lotto systeem met balletjes, genummerd van 0 tot 9. Na het trekken van een bal dient deze terug met de rest gemixt te worden alvorens de volgende te trekken. Deze methodes zijn geschikt voor kleine hoeveelheden willekeurige getallen, zoals het splitsen van sleutels of paswoorden. Indien grotere hoeveelheden nodig zijn, bijvoorbeeld voor het splitsen van computerbestanden, is de beste oplossing de aankoop van een PC-kaart met hardware ruisgenerator.

De tweede regel voor absoluut veilig splitsen is natuurlijk de fysieke scheiding van de individuele delen. Minstens één van de gesplitte delen mag nooit toegankelijk zijn voor de bezitters van de andere delen. De afzonderlijke delen dienen steeds zo beschermd te worden dat compromittering van een deel opgemerkt kan worden.

Een mogelijke manier om een gesplit deel te bewaren is een kleine verzegelde - gelijmde - plastic container die gebroken dient te worden om toegang te krijgen tot het gesplit deel (wikkel de dicht geplooide tekst in alu-folie). Zegels kunnen mee in de container gelijmd worden. Een beschadigde container, en dus een compromittering van dat deel, zal onmiddellijk opgemerkt worden. Natuurlijk dient de plastic container steeds op een veilige plaats bewaard te worden. De eigenaar van de informatie kan steeds een veiligheidscontrole uitvoeren door de houders van zijn gesplitste delen hun onbeschadigde container te laten tonen. Dit is vergelijkbaar met de beruchte biscuits die je moet breken om de nucleaire codes te onthullen.

Als de regels van willekeur en fysieke scheiding strikt nageleefd worden zal de geheime informatie absoluut veilig zijn. Het is mathematisch bewezen dat er geen enkele manier is om de geheime informatie te onthullen, tenzij men beide gesplitste delen bezit. Indien u echter de code splitst van een vijf-euro-slot, dan zal u ook over vijf-euro-veiligheid beschikken. Het is zinloos een absoluut veilig systeem te gebruiken om de combinatie van een goedkope kluis te beveiligen, als die kluis met een koevoet in een wip open kan. Anderzijds, indien u de combinatie van een bankkluis splitst kunt u er absoluut zeker van zijn dat geen enkele individuele bezitter van een gesplitst deel toegang krijgt tot die kluis in de bank.

Tenslotte heeft secret splitting nog een belangrijke eigenschap. Aangezien het systeem rekenkundig bewezen onbreekbaar is zal het verlies van één van de gesplitste delen het volledige verlies betekenen van de originele informatie, tenzij de eigenaar zelf nog een kopij heeft van die informatie. Er is geen weg terug als een deel verloren of per ongeluk vernietigt is. Het kan nuttig zijn om een extra kopij van uw deel op een veilige plaats te bewaren. Wanneer u zelf geheime informatie splitst dient u de berekende delen meermaals te controleren indien u van plan bent het origineel te vernietigen!

Meer om te lezen


© Copyright 2004 - 2017 Dirk Rijmenants

Home