Eingongslykel

Utdrag frå ei eingongslykelblokk.

Eingongslykel eller one-time pad (OTP) innan kryptografi er ein krypteringsalgoritme der klarteksta vert sett saman med ein tilfeldig lykel eller «pad» som er like lang som klarteksta, og vert nytta berre ein gong. Ein nyttar modulær addering for å setja saman klarteksta med lykelen (for binære data gjer operasjonen XOR det same). Lykelen er som regel samansett av ein tilfeldig straum av tal, der kvart av tala indikerer kor mange plassar i alfabetet (eller talrekkja, viss klarteksta er i numerisk form) ein skal skifta tilsvarande bokstav eller tal til i klarteksta. For meldingar i det norske alfabetet vil lykelen vera samansett av ei tilfeldig rekkje av tal mellom 0 og 29, for binære meldingar vil lykelen vera samansett av ei tilfeldig rekkje av 0-arar og 1-arar, og så vidare.

Eingongslykelen vart fyrst skildra av Frank Miller i 1882, gjenoppfunnen i 1917 og patentert i 1919. Viss lykelen er verkeleg tilfeldig, aldri nytta om att, og halden løynleg, så er eingongslykelen perfekt for å halda informasjon løynd. Det har òg vorte prova at kvart og eit chiffer som skal ha perfekt tryggleik, må bruka lyklar med dei same krava som eingongslyklar.

Til å byrja med vart eingongslyklar distribuerte på papir, ofte som ei blokk med ark, slik at det øvste arket kunne rivast av og øydeleggjast etter bruk. For enkelt å kunna skjula ei slik blokk, kunne ein laga henna så liten at det kunne vera naudsynt å bruka forstørringsglas for å bruka henne. Det finst døme på blokker frå KGB som er så små at dei får plass i handflata, eller i eit valnøttskal. For å auka tryggleiken vart blokkene i blant laga av brannfarleg materiale som nitrocellulose.

Eingongslykelen kjem av Vernam sine chiffer, namngjeven etter ein av oppfinnarane, Gilbert Vernam. Vernam sitt system var eit chiffer som sette saman ei melding med ein lykel som vart lesen av ei papirremse som stod i ei løkke. I den opphavlege forma si var ikkje systemet til Vernam uknekkbart, fordi lykelen kunne brukast opp att. Eingangsbruken kom litt seinare, då Joseph Mauborgne forstod at om lykel-remsa var totalt vilkårleg, så ville den kryptoanalytiske vanskegraden auka så mykje at dekryptering var umogleg.

Det finst tvitydige nemningar som er grunna i at nokre forfattarar brukar uttrykket «Vernam-chiffer» som eit synonym for «eingongslykel», der andre viser til kvart og eit additiv flytchiffer som eit «Vernam-chiffer», inkludert dei som er baserte på kryptografiske sikre pseudovilkårlege nummergeneratorar.

Perfekt tryggleik

Vernam-Mauborgnes eingongslykel vart tidleg anerkjent som vanskeleg å knekka, men den spesielle statusen som umogleg å knekka vart ikkje etablert før 25 år etter, av Claude Shannon. Han beviste, ved å bruka informasjonsteoretiske synspunkt, at eingongslykelen har ein eigenskap han kalla «perfekt tryggleik». Denne eigenskapen bestod i at chifferteksta C ikkje gjev nokon som helst tilleggsinformasjon om klarteksta. Difor er den a priori sannsynet for ei klartekst M den same som den a posteriori-sannsynet for klartekst M, gjeve den korresponderande chifferteksta. Mateatisk kan dette uttrykkjast $H(M)=H(M|C)$, der $H(M)$ er den entropiske versjonen av klarteksta, og $H(M|C)$ er den kondisjonelle entropiske varianten av klarteksta gjeve chifferteksta C. Perfekt tryggleik er ei sterk angjeving av kryptoanalytisk vanskegrad.

Til trass for Shannons bevis på tryggleiken, så har eingongslykelen endel praktiske ulemper:

• krev verkeleg tilfeldig eingongslykel
• krev sikker generering og distribusjon av lykelmaterialen, som må vera minst like langt som sjølve meldinga
• krev omhyggeleg handsaming for å sikra at han vert verande løynleg overfor kvar og ein motstandar, og at den vert avhenda på korrekt måte for å unngå gjenbruk av heile eller delar av lykelen (derav ordet eingongs-)

Fordi eingongslykel må distribuerast og takast vare på på sikkert vis, og lykelen må vera minst like lang som meldinga, så er det ofte inkje poeng i å bruka eingongslykelen og heller senda klarteksta i seg sjølv (sidan dei er same storleik og må sendast sikkert). Om ein veldig lang eingongslykel derimot har vorte distribuert på sikkert vis (til dømes ein harddisk full av tilfeldige data), så kan han brukast for framtidige meldingar, fram til summen av storleiken til meldingane er like stor som eingongslykelen.

Eingongslykel har ikkje vorte brukt i utbreidd forstand innan informasjonstryggleik, då utfordringane ved å implementera dette er så store og vanskelege å ivareta, at mange system har vorte knokke på grunn av dette. Det er særleg viktig å understreka at kravet til å bruka ein lykel berre ein gong er absolutt. Viss ein eingongslykel vert brukt to gonger, så kan enkle matematiske operasjonar redusera lykelen til eit kontinuerleg lykelchiffer. Viss begge klartekstene er skriven i vanleg språk (til dømes engelsk, russisk eller portugisisk), så kan dei med stor grad av sannsyn, sjølv om begge er løynlege, hentast fram igjen ved hjelp av heuristisk kryptoanalyse, med enkelte tvitydigheiter. Om meldingane er av ulik lengd, så kan bara dei delane som har felles lykelbruk analyserast og dekrypterast. Den mest kjende utnyttinga av denne sårbarheita er VENONA-prosjektet.

Eingongslyklar gjev ingen funksjonalitet for å sikra at meldinga ikkje har vorte kompromittert, slik at i teorien så kan eit angrep frå ein mellommann som kjenner den eksakte klarteksta, erstatta heile eller deler av teksta med si eiga tekst, så lenge ho er av lik lengd. Standard teknikkar for å hindra dette, slik som å bruka ein kode for meldingsautentisering, men denne teknikken har ikkje den perfekte tryggleiken som eingongslykel.

Historie

Soga til eingongslykelen er prega av fleire ulike, men tett forbundne oppdagingar.

Kryptografen Frank Miller]] var den fyrste til å skildra eit system med eingongslyklar for å verna om telegrafmeldingar i 1882.

Det første eingongslykelsystemet var elektronisk. I 1917 fann Gilbert Vernam hos AT&T opp eit chiffer basert på teletype maskinteknologi. Dette vart seinare patentert i 1919. Kvar karakter i ei melding vart elektronisk sett saman med ein karakter frå ei papirremse (lykel). Kaptein Joseph Mauborgne forstod at om sekvensen av karakterar på lykelremsa kunne vera totalt vilkårleg, så ville ein kryptoanalyse av resultatet vera særs vanskeleg. Saman fann dei opp det første eingongslykel-remsesystemet.

Den andre utviklinga var papirblokksystemet. Diplomatar hadde lenge brukt kodar og chiffer for konfidensialitet og for å minimera telegrafikostnader. Som kodar vart ofte ord eller frasar konverterte til nummergrupper (typisk 4 eller 5 siffer) ved å bruka ei slags ordliste, eller kodebok. For å auka tryggleiken så kunne eit hemmeleghalde nummer setjast saman med (vanlegvis modulær addisjon) kvar kodegruppe før sending. Det hemmelege nummeret vart endra ved jamne mellomrom (dette kallast dobbeltkryptering). På byrjinga av 1920-talet innsåg tre tyske kryptografar, Werner Kunze, Rudolf Shauffler og Erich Langlotz, som var involvert i oppgåva med å knekka slike system, at om kvar kodegruppe vart dobbeltkryptert med eit heilt tilfeldig nummer så kunne meldinga aldri dekrypterast. Dei brukte eit par identiske papirblokker som hadde påtrykt linjer med tilfeldige nummergrupper. Kvar side hadde eit serienummer og 8 linjer. Kvar linje hadde 6 femsifra nummer. Ei side vart brukt som eit arbeidsark for å kryptera ei melding, og deretter tilinkjegjord. Serienummeret vart sendt saman med den krypterte meldinga. Mottakaren ville så reversera prosedyren, og deretter øydeleggja hans versjon av sida. Det tyske utanriksdepartementet hadde sett systemet i drift i 1923.

Ein tredje variant var å bruka ei blokk eingongslykel basert på bokstavar, som vart brukt til å kryptera klartekst direkte, slik som neste døme vil visa. Leo Mark si har skildra korleis ein slikt system vart oppfunnen for dei britiske Special Operations Executive (SOE) under den andre verdskrigen, sjølv om han på det tidspunktet mistenkte at metoden allereie var kjend i den lukka verda av kryptografi, som til dømes ved Bletchley Park.

Det siste dømet på oppdaging vart gjort av Claude Shannon på 1940-talet. Han innsåg og beviste den teoretiske tydinga av eit eingongslykelsystem. Shannon leverte sina funn og resultatet i ein hemmelegstempla rapport i 1945, og publiserte desse offentleg i 1949. På same tid, men heilt uavhengig, hadde Vladimir Kotelnikov bevist absolutt tryggleik hos eingongslyklar. Hans resultatet vart levert i ein rapport i 1941 som tydelegvis framleis er hemmelegstempla.

Døme

Gjeve at Kari ynskjer å senda meldinga «HELLO» til Ola. Gå frå ut at to arkblokker med identiske vilkårlege sekvensar av bokstavar har vorte laga på førehand, og at Kari og Ola har fått kvart sitt eksemplar av dette arket. Kari vel ut eit ubrukt ark frå blokka. Metoden for å gjera dette er ofte avtalt på førehand, eksempelvis «bruk det tolvte arket på skjærtorsdag» eller «bruk det neste tigjengelige arket for neste melding». Teksta på det valde arket er lykelen for denne meldinga. Kvar bokstav frå arket vil setjast saman på ein førehandsvald måte med kvar bokstav i meldinga. Det er vanleg, men ikkje påkravd, å gje kvar bokstav ein numerisk verdi: til dømes kan «A» vera 0, «B» vera 1 og så vidare til alfabetet er slutt. I dette dømet så vil metoden i bruk vera å setja saman lykelen og meldinga ved å bruka modulær addisjon. Dei numeriske verdiane av bokstavane i meldinga og bokstavane i lykelen vert lagt saman, modulus 26 (utgangspunktet her er eit engelsk alfabet). Om lykelmaterialet byrjar med

X M C K L

og meldinga er «HELLO», så kan krypteringa gjerast som følgjer:

   7 (H)   4 (E)  11 (L)  11 (L)  14 (O) melding
+ 23 (X)  12 (M)   2 (C)  10 (K)  11 (L) lykel
= 30      16      13      21      25     melding + lykel
=  4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z) melding + lykel (mod 26) >> chiffertekst

Merk at om eit nummer er større enn 25, så vil ein, i modulær aritmetikk, bruka det som er igjen etter at ein har trekt frå 26. Enkelt sagt så vil den si at viss du går forbi «Z», byrj på «A» igjen.

Chifferteksta som skal sendast til Ola er «EQNVZ». Ola vert brukt sin kopi av tilsvarande ark på blokka, og gjennomfører den same prosedyren, berre omvendt, for å finna klarteksta. Her vert lykelen subtrahert frå chifferteksta, igjen ved å bruka modulær aritmetikk:

    4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z) ciffertekst
–  23 (X)  12 (M)   2 (C)  10 (K)  11 (L) lykel
= -19       4      11      11      14     chiffertekst – lykel
=   7 (H)   4 (E)  11 (L)  11 (L)  14 (O) chiffertekst – lykel (mod 26) >> melding

På same måte som over, om eit tal vert negativt, legg til 26 for å gjera talet positivt.

På denne måten så får Ola fram Kari si melding «HELLO». Både Kari og Ola øydelegg arket like etter bruk, slik at det ikkje skal brukast att og dermed forhindra eit angrep på chifferet.

Tryggleik

Engangslyklar er informasjonsteoretisk sikre, basert på at den krypterte meldinga (chifferteksta) ikkje gjev ein kryptoanalytikar nokon informasjon om den opphavlege meldinga bortsett frå lengda på meldinga. Dette er ein veldig sterk indikator på tryggleiken, som først vart utvikla under den andre verdskrigen av Claude Shannon, og matematisk bevist av han ved bruk av eingongslyklar omtrent på same tid. Hans resultat vart publisert i Bell Labs Technical Journal i 1949. Ved korrekt bruk så vil eingongsnlyklar vera informasjonsteoretisk sikre sjølv mot åtakarar med uavgrensa prosesseringskraft. For å halda fram dømet ovanfor: Gjeve at Eva har fått tak i Kari si krypterte melding «ENQVZ». Om Eva hadde hatt uavgrensa prosesseringskraft, så ville ho raskt ha funne at lykelen «XMCKL» ville produsert klarteksta «HELLO», men ho ville òg finna at lykelen «TQURI» ville produsert klarteksta «LATER», som er ein like sannsynleg klartekst:

    4 (E)  16 (Q)  13 (N)  21 (V)  25 (Z) chiffertekst
−  19 (T)  16 (Q)  20 (U)  17 (R)   8 (I) mogleg lykel
= −15       0      −7       4      17     chiffertekst-lykel
=  11 (L)   0 (A)  19 (T)   4 (E)  17 (R) chiffertekst-lykel (mod 26)

Det er mogleg å «dekryptere» chifferteksta kva for ein som helst melding med det same mengd bokstavar ved å bruka ulike lyklar, og det finst ingen informasjon i chifferteksta som set Eva i stand til å velja blant dei ulike moglege resultata.

Konvensjonelle symmetriske krypteringsalgoritmar brukar komplekse mønstra av substitusjon og transponeringar. For dei beste av desse som er bruk i dag så er det ikkje kjent om det finst ein kryptoanalytisk prosedyre som kan reversera helt eller delvis desse mønstera utan å kjenna lykelen som vart brukt under krypteringa. Asymmetriske krypteringsalgoritmer brukar matematiske utfordringar som er sett på som umoglege å løysa, slik som heiltalsfaktorisering eller diskrete logaritmar. Det finst endå ikkje bevis på at desse utfordringane er uløyselege, og matematiske gjennombrot kan gjera eksisterande system sårbare for angrep.

Kjelder

• Erskine, Ralph, "Enigma's Security: What the Germans Really Knew", in "Action this Day", edited by Ralph Erskine and Michael Smith, pp 370–386, 2001.
• Denne artikkelen bygger på «Engangslykel» frå Wikipedia på bokmål, den 23. november 2017, og opphavleg på «One-time pad» frå Wikipedia på engelsk.

Bakgrunnsstoff

• Marcus Ranums Eingongslykel-FAQ
• FreeS/WAN ordbokinnlegg med diskusjon om veikskapane til eingongslykelen

Vidare lesnad

• Robert Wallace og H. Keith Melton,med Henry R. Schlesinger, Spycraft: The Secret History of the CIA's Spytechs, from Communism to al-Qaeda, New York, Dutton, 2008 . ISBN 0525949801