One-time pad
One-time pad, soms ook wel OTP, Vernam-cijfer, eenmalig blokcijfer of het perfecte cijfer genoemd, is een methode in de cryptografie, een methode van encryptie of hetzelfde een cijfer. De eerste die over het cijfer schreef was F. Miller, een bankdirecteur uit de Verenigde Staten, in 1882.[1] Het one-time pad werd als handcijfer voor breed gebruik ontwikkeld gebaseerd op het door G. Vernam en JO. Mauborgnein in 1917 ontwikkelde systeem voor gebruik bij telexverkeer. Het is bewezen dat het, mits correct toegepast, niet kan worden gebroken. Het is het enige cijfer waarvoor dat is bewezen, maar wanneer toegepast moet het cijfer aan veel voorwaarden voldoen, opdat het niet ontcijferbaar is door een buitenstaander.
Ontstaan bewerken
Bij het Vernam-systeem werd elke verstuurde 5-bits ITA (International Telegraph Alphabet) telexcode (een afleiding van de Baudotcode voor telegrafie) modulo 2 opgeteld bij een 5-bits sleutelcode geponst in een geluste papieren strook (telexband), de one-time-sleutelband. Elk teken van de tekst werd vercijferd met het volgende teken in de sleutelband. Enige tijd later stelde een kapitein van het US Signal Corps voor de sleutel uit volledig willekeurige tekens te laten bestaan, even lang als het te verzenden bericht. Zowel zender als ontvanger had een lange band met exact dezelfde sleuteltekens. Deze papieren strook liep bij de zender parallel met de telexband met de klare tekst, bij de ontvanger met de band met de cijfertekst. Daar de telexcode in wezen een binair getal van 5 posities is, kon de modulo 2-optelling eenvoudig worden uitgevoerd door de logische functie XOR of exclusieve OF. Vernam bereikte dit door twaalf relais te gebruiken. Door hetzelfde te doen met de cijfertekst en de sleutel, werd de originele klare tekst weer verkregen. De uitvinding van Vernam was de basis voor alle latere pen-en-papierversies, gebaseerd op hetzelfde principe. Hoewel de onbreekbaarheid van one-time pad niet alleen theoretisch bewezen is, maar het systeem ook praktisch toegepast kan worden, zijn de lange sleutel en het sleutelbeheer een groot probleem.
Eigenschappen bewerken
Om de theoretische onbreekbaarheid van one-time pad te verwezenlijken dient aan verschillende voorwaarden voldaan te zijn.
- De lengte van de sleutel moet minstens even lang als de te versleutelen gegevens zijn.
- De sleutel mag alleen bestaan uit werkelijk willekeurige tekens.
- Een sleutel mag slechts één keer worden gebruikt om één bericht te vercijferen en moet daarna worden vernietigd.
- Van een sleutel mogen slechts twee kopieën bestaan, een voor de verzender en een voor de ontvanger van de gegevens.
Enkel indien een cijfer aan al deze voorwaarden voldoet is deze onbreekbaar. Elke letter van een bericht kan immers vercijferd worden door elke willekeurige letter, met elke willekeurige letter als resultaat. Men kan hier ook niet alle mogelijkheden van de sleutel uitproberen, de zogenaamde brute force attack, omdat iedere mogelijke sleutel in een andere oplossing kan resulteren. Zo kan men een bericht op zodanige wijze ontcijferen dat het resultaat een totaal ander bericht is. Wanneer we bijvoorbeeld het woord HALLO vercijferen met de sleutel XTOVB krijgen we ETZGP. Indien we ETZGP echter ontcijferen met de foutieve sleutel EEKCR, krijgen we als klaartekst het woord APPEL. Zo kan men elk vercijferd bericht in eender welke gewenste klare tekst ontcijferen, zolang men maar de "juiste" verkeerde sleutel gebruikt. Er is dus geen mogelijkheid om te weten of het bericht correct ontcijferd werd.
In de praktijk is one-time pad enkel bruikbaar voor het veilig overbrengen van gegevens indien verzender en ontvanger vooraf op een absoluut veilige manier, meestal door de betrokkenen zelf of een koerier, een sleutel ter beschikking gesteld werd. Bij correct gebruik en toepassing van de voorwaarden is one-time pad de enige bestaande bewezen perfect veilige vercijfering, bestand tegen elke mogelijke cryptoanalytische aanval. Dit werd bewezen in Claude Shannons verhandeling 'Communication theory of secrecy systems'. Het systeem is onder andere in gebruik geweest tijdens de Koude Oorlog, voor een veilige communicatie tussen Washington en Moskou, de zogeheten Hotline Washington-Moskou.
Praktische voorbeelden bewerken
De logische XOR kan alleen toegepast worden bij binaire tekens. Er wordt daarom gebruikgemaakt van een modulus- (of modulo-) berekening. Hiertoe wordt de uitkomst van een berekening gedeeld door het modulusgetal, de overgebleven rest is de gewenste uitkomst.
Voorbeeld: 24×26(mod9)=624/9=69, rest 3. De rest 3 is dus de uitkomst van de berekening. Dit soort eenweg-berekeningen produceert, vooral met berekeningen met machtsverheffen, een uitkomst die niet is te herleiden tot de oorspronkelijke getallen; ze worden onder andere (tezamen met XOR-bewerkingen) veel gebruikt in moderne vercijferingssystemen. Een alledaags voorbeeld van een modulusberekening is het bepalen van de tijd na een bepaald aantal uren. Het is nu 3 uur in de middag, hoe laat is het na 59 uur? Berekening:
15+59(mod24)=74/24=3, rest 2. Het is dan dus 2 uur in de morgen (op de derde dag na vandaag).
In het eerste voorbeeld gebruiken we een one-time pad op basis van getallen. We kiezen als sleutel een reeks totaal willekeurige getallen van 00 tot 99. We geven elke letter een waarde waarbij A=00, B=01 enzovoort tot Z=25. Bij het vercijferen rekenen we met de afzonderlijke cijfers: de overeenkomstige cijfers van de "waarde" van de letters van de klare tekst en die van de sleutel worden modulo 10 (mod10) opgeteld; dit is eenvoudig te verwezenlijken door de positieve overdracht achterwege te laten, dat heeft hier hetzelfde effect als delen. Bijvoorbeeld: 09+05=04 en niet 14! en 24+98=12. Merk op dat de twee cijfers van elke "waarde" afzonderlijk worden opgeteld; dat kan hier dus ook van links naar rechts.
Om het bericht te ontcijferen trekken we de sleutel af van de cijfertekst, ook hier weer modulo 10, dus zonder eventuele negatieve overdracht (vb. 25-59=76) en zetten vervolgens de getallen weer om in letters.
| Tekst: | D | I | T | I | S | G | E | H | E | I | M | |
| 03 | 08 | 19 | 08 | 18 | 06 | 04 | 07 | 04 | 08 | 12 | (opzoeken in tabel) | |
| Sleutel: + | 15 | 84 | 78 | 39 | 66 | 95 | 20 | 16 | 33 | 57 | 48 | |
|
| ||||||||||||
| Resultaat: | 18 | 82 | 87 | 37 | 74 | 91 | 24 | 13 | 37 | 55 | 50 | |
| Cijfertekst: | 18828 73774 91241 33755 50 | |||||||||||
Als voorbeeld van de ontcijfering nemen we de tweede positie: het cijferteken is 82, daar trekken we de bijbehorende sleutelwaarde 84 mod10 (weer voor elke positie apart) van af:
82-84(mod10)=08, en dat is precies de waarde van de tweede letter in de klare tekst.
In volgend voorbeeld maken we gebruik van sleutelletters in plaats van getallen. De sleutel bestaat hier dus uit een reeks willekeurige letters. Ook hier geven we elke letter een waarde waarbij A=00, B=01 enzovoort tot Z=25. Tekst- en sleutelwaarden worden weer opgeteld, deze keer modulus 26 (hier de gehele waarde, de cijfers dus niet afzonderlijk) en wél met overdracht (als het resultaat groter is dan 25 trekken we 26 af, dat heeft hier hetzelfde effect als delen). Ten slotte zetten we de getallen om in letters. Om het bericht te ontcijferen zetten we cijfertekst en sleutel om in getallen en trekken we de sleutel af van de cijfertekst, ook hier weer met modulo 26 (als het resultaat kleiner is dan 0 tellen we er 26 bij).
| Tekst: | D | I | T | I | S | G | E | H | E | I | M | |
| 03 | 08 | 19 | 08 | 18 | 06 | 04 | 07 | 04 | 08 | 12 | ||
| Sleutel: | X | V | H | E | U | W | N | O | P | G | D | |
| + | 23 | 21 | 07 | 04 | 20 | 22 | 13 | 14 | 15 | 06 | 03 | |
|
| ||||||||||||
| Resultaat: | 26 | 29 | 26 | 12 | 38 | 28 | 17 | 21 | 19 | 14 | 15 | (in tabel opzoeken) |
| Mod 26 = | 00 | 03 | 00 | 12 | 12 | 02 | 17 | 21 | 19 | 14 | 15 | (facultatief) |
|
| ||||||||||||
| Cijfertekst: | A | D | A | M | M | C | R | V | T | O | P | |
| Cijfertekst: | ADAMM CRVTO P | |||||||||||
Om het werk te vereenvoudigen kunnen we een tabula recta gebruiken om de letters op te zoeken, dat is behoorlijk omslachtig. Het kan veel eenvoudiger: we maken onderstaande hulptabel, dan hoeven we ook de modulus 26 niet te berekenen door 26 af te trekken resp. op te tellen, we kunnen de letter namelijk direct in de tabel aflezen. De tabel is zowel bij het versleutelen als het ontsleutelen te gebruiken.
| Letter | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
|
| ||||||||||||||||||||||||||
| Waarde | 00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
| Mod - | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 |
| Mod + | -26 | -25 | -24 | -23 | -22 | -21 | -20 | -19 | -18 | -17 | -16 | -15 | -14 | -13 | -12 | -11 | -10 | -09 | -08 | -07 | -06 | -05 | -04 | -03 | -02 | -01 |
Er zijn nog vele andere manieren om one-time pad toe te passen, maar deze zijn altijd gebaseerd op een willekeurige sleutel die bij de te versleutelen gegevens wordt opgeteld.
Problemen bij gebruik bewerken
Om one-time pad toe te passen zijn er twee belangrijke problemen die het gebruik ervan bemoeilijken en zeer duur maken:
- Een eerste probleem is van technische aard en betreft het produceren van grote aantallen willekeurige getallen of tekens voor de sleutel. Om absolute willekeurigheid te maken kan men deze reeksen niet creëren met behulp van eenvoudige mechanische of elektronische middelen. Het produceren van grote aantallen van deze willekeurige gegevens is dan ook een dure onderneming.
- Het tweede probleem is van praktische aard. Aangezien elke sleutel even groot als de te vercijferen gegevens dient te zijn en slechts eenmalig gebruikt mag worden is er een groot aantal verschillende sleutels nodig en dienen deze op veilige wijze ter beschikking gesteld te worden van verzender en ontvanger van een bericht. Dit heeft enorme logistieke en veiligheidsproblemen tot gevolg, indien er veel communicatie beveiligd dient te worden.
In de praktijk werd dit grotendeels opgelost door meerdere genummerde, lange banden, resp. grote aantallen pagina's met sleutelcodes te gebruiken. Bij de telexband ging men voor het volgende bericht gewoon verder met de sleuteltekst op het punt waar het vorige bericht opgehouden was. Dit werd geforceerd door bijvoorbeeld de lezer die de band met de sleutels las, te voorzien van een mesje dat de transportponsing doorsneed nadat een positie gelezen was. Dit teken en alle voorgaande tekens konden dus automatisch niet meer gebruikt worden. Bij de "pads" werden alle reeds gebruikte pagina's (ze waren soms tevens als werkpagina's ingericht) vernietigd; men begon dus bij een volgende pagina. In beide gevallen had men dus de beschikking over een flinke voorraad sleutels.
Toepassingen bewerken
Vanwege de praktische bezwaren om een one-time-pad correct toe te passen is het gebruik ervan zeer beperkt. Zij worden onder andere gebruikt voor communicatie tussen inlichtingendiensten en hun veldagenten. De one-time pad-sleutels, dikwijls zeer kleine boekjes of blaadjes met getallenreeksen, soms op microfilms, kunnen gemakkelijk verborgen worden.
Tot begin jaren 80 werden zij ook gebruikt om militair en diplomatiek telex-verkeer te beveiligen. De telexen gebruikten daarbij het originele principe van Vernam met de one-time-banden. Later volgden elektronische systemen zoals computer- en telefoonverbindingen die gebruik maakten van een elektronisch opgeslagen one-time pad-sleutel.
De enorme kosten voor veilige productie, verspreiding, beheer en vernietiging van enorme aantallen one-time-tapes en pads konden enkel gedragen worden door overheidsinstanties zoals leger, inlichtingendiensten en diplomatie. Door het exponentieel toenemen van communicatie werd grootschalig gebruik van one-time pads onhoudbaar en schakelde men over op de meer praktische, maar weliswaar minder veilige, cryptografische apparaten en computeralgoritmes.
Een vervangend alternatief voor one-time pad zijn de "stream ciphers" of stroomvercijfering, waarbij via een algoritme een pseudo-willekeurige getallenreeks geproduceerd wordt. Beginnen beide partijen met eenzelfde parameter in dit algoritme (en dat moet dus weer gecommuniceerd worden), dan zal het resultaat exact hetzelfde zijn. Deze stromen benaderen slechts de werkelijke willekeurigheid en voldoen dus nooit aan de voorwaarden om onbreekbaar te zijn. De gebruikte algoritmen hiervoor voorzien dan ook vaak in een methode om dit bijna 100% te bereiken. Dikwijls wordt ten onrechte aangenomen dat men een one-time pad kan creëren met de random-functie op computers, terwijl deze vaak gebruikmaken van een algoritme dat niet bedoeld is om grote series willekeurige getallen te produceren. Moderne computersystemen beschikken overigens over verbeterde algoritmen. De enige tot nu toe bekende manier is de sleutels te maken via een elektronische ruisgenerator met nog wat elektronica. Hiervan neemt men aan dat de output volkomen willekeurig is, mits de schakeling en de bouw ervan aan een serie voorwaarden voldoet.
Vanwege zijn absolute veiligheid blijft one-time pad echter nog steeds in gebruik bij communicatie waar veiligheid en geheimhouding absolute voorrang hebben. De toepassingen zijn echter zeer beperkt. Dit is onder meer het geval bij de zogenaamde hotlines van belangrijke wereldleiders en topgeheime communicatie bij inlichtingendiensten en legers. Tijdens de Koude Oorlog werd het systeem nog gebruikt voor communicatie tussen Washington en Moskou.
Snake Oil bewerken
Er zijn in de praktijk veel voorbeelden van cijfers, waarvan wordt beweerd dat ze niet zijn te breken, maar die niet voldoen aan de nodige vereisten. Zo is er veel software op de markt waarvan de makers beweren het onbreekbare one-time pad of Vernam-systeem toe te passen, maar in werkelijkheid geen echt willekeurige gegevens genereren, een te kleine sleutel gebruiken of meermaals vercijferen met dezelfde sleutel. Bovendien heeft het geen zin om bestanden eenmalig te vercijferen met een eenmalige sleutel die even groot is, en veilig dient bewaard te worden, respectievelijk overgebracht te worden naar de ontvanger. Men kan evengoed het bestand zelf op veilige wijze bewaren of overbrengen.
Zo is er het fantastisch klinkende verhaal van de oplossing van het sleutelbeheer door middel van twee sleutels. Alice zendt haar bericht, vercijferd met sleutel A. Bob kan dit niet ontcijferen, maar vercijfert dit nogmaals met zijn eigen sleutel B, en stuurt dit terug naar Alice. Die ontcijfert het bericht met haar sleutel A en zendt dit nogmaals naar Bob. Aangezien het bericht nu enkel nog vercijferd is met sleutel B kan Bob het toch ontcijferen, en dit zonder uitwisseling van de geheime sleutels. Hoewel hier op het eerste gezicht one-time pad is toegepast zonder het probleem van sleuteldistributie, gaat de vlieger echter niet op. Alice verstuurt het bericht één keer met haar sleutel en één keer met Bobs sleutel, én het wordt door Bob, met beide sleutels vercijferd, teruggestuurd. Elke sleutel werd tweemaal gebruikt, voldoet dus niet meer aan de verplichte voorwaarden, en het bericht kan gebroken worden:
Sleutel B = bericht(A+B) - bericht(A)
Sleutel A = bericht(A+B) - bericht(B)
Maar er is nog iets anders: het zogenaamde "ontcijferde" bericht bevat vaak louter onzin, want er is een klassiek symmetrisch vercijfersysteem gebruikt. Dat zit zo: bij symmetrische systemen wordt wat het laatste is gedaan bij het vercijferen, als eerste teruggedraaid bij het ontcijferen. Het is als met aan- en uitkleden: bij het aankleden worden eerst de sokken aangetrokken, vervolgens de schoenen; bij het uitkleden worden eerst de schoenen uitgetrokken, daarna de sokken. Zoals duidelijk te zien is, is dat hierboven niet het geval. NB. Wordt een van bovengenoemde one-time pad-systemen met moduloberekeningen gebruikt, waarbij A en B ongelijke sleutels hebben, het maakt namelijk niet uit in welke volgorde je de verschillende optellingen en aftrekkingen doet. Het ontcijferde bericht is dan wel correct; het tweemaal gebruiken van een sleutel blijft natuurlijk fout.
Er zijn nog vele variaties op dit thema en voorbeelden van ronduit slechte cryptografische systemen en software die al dan niet goedbedoelde "onbreekbare" veiligheid aanbieden, maar daarbij minstens een van de verplichte voorwaarden negeren. Deze programma's zijn bekend onder de naam snake-oil, of slangenolie, genoemd naar de producten van kwakzalvers.
|