Engangsnøkkel

Engangsnøkkel (engelsk: one-time pad, OTP) eller kodepapir er innen kryptografi en krypteringsalgoritme hvor klarteksten blir satt sammen med en tilfeldig nøkkel eller «pad» som er like lang som klarteksten, og blir benyttet kun en gang. En modulær addering blir brukt for å sette sammen klarteksten med nøkkelen. (For binære data, så gjør operasjonen XOR det samme.) Engangsnøkkelen ble oppfunnet i 1917 og ble patentert i 1919. Hvis nøkkelen er virkelig tilfeldig, aldri benyttet om igjen, og holdt hemmelig, så er engangsnøkkelen perfekt for å hemmeligholde informasjon. Det har også blitt bevist at ethvert chiffer som skal ha perfekt sikkerhet, må bruke nøkler med samme krav som engangsnøkler. Nøkkelen består som regel av en tilfeldig strøm av tall, hvor hvert av tallene indikerer hvor mange plasser i alfabetet (eller tallrekken, hvis klarteksten er i numerisk form) man skal skifte tilsvarende bokstav eller tall i klarteksten. For meldinger i det norske alfabetet, så vil nøkkelen bestå av en tilfeldig rekke av tall mellom 0 og 29; for binære meldinger vil nøkkelen bestå av en tilfeldig rekke av 0-er og 1-ere, og så videre.

Utdrag fra en engangsnøkkelblokk.

Til å begynne med ble engangsnøkler distribuert på papir, ofte som en blokk med ark, slik at det øverste arket kunne rives av og ødelegges etter bruk. For enkelt å kunne skjule en slik blokk, så kunne den lages så liten at det kunne være nødvendig å bruke forstørrelsesglass for å lese den. Bilder tilgjengelig på internett viser blokker som har blitt tatt fra KGB som er så små at de får plass i håndflaten, eller i et valnøttskall. For å øke sikkerheten ble blokkene i blant laget av brannfarlig materiale slik som nitrocellulose.

Engangsnøkkelen er derivert av Vernams chiffer, navngitt etter Gilbert Vernam, en av oppfinnerne. Vernams system var et chiffer som satt sammen en melding med en nøkkel som ble lest av en papirremse som sto i en løkke. I den originale formen var ikke Vernams system uknekkbart fordi nøkkelen kunne bli gjenbrukt. Engangsbruken kom litt senere når Joseph Mauborgne forsto at om nøkkelremsen var totalt vilkårlig, så ville den kryptoanalytiske vanskelighetsgraden øke.

Det eksisterer tvetydige betegnelser som er grunnet i at noen forfattere bruker uttrykket «Vernam chiffer» som et synonym for «engangsnøkkel», der hvor andre viser til enhver additiv flytchiffer som et «Vernam chiffer», inkludert de som er basert på kryptografisk sikre pseudovilkårlige nummergeneratorer.

Perfekt sikkerhet

Vernam-Mauborgnes engangsnøkkel ble tidlig anerkjent som vanskelig å knekke, men den spesielle statusen som umulig å knekke ble ikke etablert før 25 år etter, av Claude Shannon. Han beviste, ved å bruke informasjonsteoretiske synspunkter, at engangsnøkkelen har en egenskap han kalte perfekt sikkerhet. Denne egenskapen bestod i at chifferteksten C ikke gir noen som helst tilleggsinformasjon om klarteksten. Derfor er den a priori sannsynligheten for en klartekst M den samme som den a posteriori sannsynligheten for klartekst M, gitt den korresponderende chiffertekst. Matematisk kan dette uttrykkes $H(M)=H(M|C)$, hvor $H(M)$ er den entropiske versjonen av klarteksten, og $H(M|C)$ er den kondisjonelle entropiske varianten av klarteksten gitt chifferteksten C. Perfekt sikkerhet er en sterk angivelse av kryptoanalytisk vanskelighetsgrad.

Til tross for Shannons bevis på sikkerheten, så har engangsnøkkelen en del praktiske ulemper:

• krever virkelig tilfeldige engansnøkler
• krever sikker generering og distribusjon av nøkkelmaterialet, som må være minst like langt som selve meldingen
• krever omhyggelig behandling for å sikre at den forblir hemmelig overfor enhver motstander, og at den blir avhendet på korrekt måte for å unngå gjenbruk av hele eller deler av nøkkelen (derav ordet engangs-)

Fordi engangsnøkkelen må distribueres og bli oppbevart på sikkert vis, og nøkkelen må være minst like lang som meldingen, så er det ofte intet poeng i å bruke engangsnøkkelen og heller sende klarteksten i seg selv (siden de er av samme størrelse og må sendes sikkert). Derimot, om en veldig lang engangsnøkkel har blitt distribuert på sikkert vis (for eksempel en harddisk full av tilfeldige data), så kan den brukes for fremtidige meldinger, inntil summen av meldingenes størrelse er like stor som engangsnøkkelen.

Engangsnøkler har ikke blitt brukt i utbredt forstand innen informasjonssikkerhet, da utfordringene ved å implementere dette er så store og vanskelige å ivareta at mange systemer har blitt knekket på grunn av dette. Det er særlig viktig å understreke at kravet til å bruke en nøkkel kun en gang er absolutt. Hvis en engangsnøkkel brukes to ganger, så kan enkle matematiske operasjoner redusere nøkkelen til et kontinuerlig nøkkelchiffer. Hvis begge klartekstene er skrevet i vanlig språk (for eksempel engelsk, russisk eller portugisisk for den saks skyld), så kan de med stor grad av sannsynlighet, selv om begge er hemmelige, bli hentet frem igjen ved hjelp av heuristisk kryptoanalyse, med enkelte tvetydigheter. Om meldingene er av forskjellig lengde, så kan bare de deler som har felles nøkkelbruk bli analysert og dekryptert. Den mest kjente utnyttelsen av denne sårbarheten er VENONA-prosjektet.

Engangsnøkler gir ingen funksjonalitet for å sikre at meldingen ikke har blitt kompromittert, slik at i teorien så kan et angrep fra en mellommann som kjenner den eksakte klarteksten, erstatte hele eller deler av teksten med sin egen tekst, sålenge den er av lik lengde. Standard teknikker for å forhindre dette, slik som å bruke en kode for meldingsautentisering, men denne teknikken har ikke den perfekte sikkerhet som engangsnøklene i seg selv har.

Historie

Engangsnøkkelens historie er preget av fire forskjellige, men tett forbundete oppdagelser.

Det første engangsnøkkelsystemet var elektronisk. I 1917 oppfant Gilbert Vernam hos AT&T et chiffer basert på teletype maskinteknologi. Dette ble senere patentert i 1919. Hver karakter i en melding ble elektronisk satt sammen med en karakter fra en papirremse (nøkkel). Kaptein Joseph Mauborgne forstod at om sekvensen av karakterer på nøkkelremsen kunne være totalt vilkårlig, så ville en kryptoanalyse av resultatet være meget vanskelig. Sammen fant de opp det første engangsnøkkel remsesystemet.

Den andre utviklingen var papirblokksystemet. Diplomater hadde lenge brukt koder og chiffer for konfidensialitet og for å minimere telegrafikostnader. Som koder ble ofte ord eller fraser konvertert til nummergrupper (typisk 4 eller 5 siffer) ved å bruke en slags ordliste, eller kodebok. For å øke sikkerheten så kunne et hemmeligholdt nummer bli satt sammen med (vanligvis modulær addisjon) hver kodegruppe før forsendelse. Det hemmelige nummeret ble endret ved jevne mellomrom (dette kalles dobbeltkryptering). På begynnelsen av 1920-tallet så innså tre tyske kryptografer, Werner Kunze, Rudolf Shauffler og Erich Langlotz, som var involvert i oppgaven med å knekke slike systemer, at om hver kodegruppe ble dobbeltkrytpert med et helt tilfeldig nummer så kunne meldingen aldri dekrypteres. De brukte et par identiske papirblokker som hadde bli påtrykt linjer med tilfeldige nummergrupper. Hver side hadde et serienummer og 8 linjer. Hver linje hadde 6 femsifrede nummer. En side ble brukt som et arbeidsark for å kryptere en melding, og deretter tilintetgjort. Serienummeret ble sendt sammen med den krypterte meldingen. Mottageren ville så reversere prosedyren, og deretter ødelegge hans versjon av siden. Det tyske utenriksdepartementet satt systemet i drift i 1921.

En tredje variant var å bruke en blokk engangsnøkler basert på bokstaver, som ble brukt til å kryptere klartekst direkte, slik som neste eksempel vil vise. Leo Marks har beskrevet hvordan en slikt system ble oppfunnet for de britiske Special Operations Executive (SOE) under den andre verdenskrig, selv om han på det tidspunktet mistenkte at metoden allerede var kjent i den lukkede verden av kryptografi, som for eksempel på Bletchley Park.

Den siste eksempelet på oppdagelse ble gjort av Claude Shannon på 1940-tallet. Han innså og beviste den teoretiske betydningen av et engangsnøkkelsystem. Shannon leverte sine funn og resultaet i en hememligstemplet rapport i 1945, og publiserte disse offentlig i 1949. På samme tid, men helt uavhengig, hadde Vladimir Kotelnikov bevist absolutt sikkerhet hos engangsnøkler. Hans resultatet ble levert i en rapport i 1941 som tydeligvis fremdeles er hemmeligstemplet.

Eksempel

Gitt at Kari ønsker å sende meldingen «HELLO» til Ola. Gå ut fra at to arkblokker med identiske vilkårlige sekvenser av bokstaver har blitt laget forut for dette, og at Kari og Ola har fått hvert sitt eksemplar av dette arket. Kari velger ut et ubrukt ark fra blokken. Metoden for å gjøre dette er ofte avtalt på forhånd, eksempelvis «bruk det tolvte arket på skjærtorsdag» eller «bruk det neste tigjengelige arket for neste melding». Teksten på det valgte arket er nøkkelen for denne meldingen. Hver bokstav fra arket vil bli satt sammen på en forhåndsbestem måte med hver bokstav i meldingen. Det er vanlig, men ikke påkrevet, å gi hver bokstav en numerisk verdi: eksempelvis så kan «A» være 0, «B» være 1 og så videre til alfabetet er slutt. I dette eksempelet så vil metoden i bruk være å sette sammen nøkkelen og meldingen ved å bruke modulær addisjon. De numeriske verdiene av bokstavene i meldignen og bokstavene i nøkkelen blir lagt sammen, modulus 26 (utgangspunktet her er et engelsk alfabet). Om nøkkelmaterialet begynner med

X M C K L

og meldingen er «HELLO», så kan krypteringen bli gjort som følger:

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

Merk at om et nummer er større enn 25, så vil man, i modulær aritmetikk, bruke det som er igjen etter at man har trukket fra 26. Enkelt sagt så vil det si at hvis du går forbi «Z», begynn på «A» igjen.

Chifferteksten som skal sendes til Ola er «EQNVZ». Ola brukes sin kopi av tilsvarende ark på blokka, og gjennomfører den samme prosedyren, bare omvendt, for å finne klarteksten. Her blir nøkkelen subtrahert fra chifferteksten, igjen ved å bruke modulær aritmetikk:

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

På samme måte som over, om et tall blir negativt, legg til 26 for å gjøre tallet positivt.

På denne måten så får Ola frem Karis melding «HELLO». Både Kari og Ola ødelegger arket umiddelbart etter bruk, slik at det ikke skal bli gjenbrukt og dermed forhindre et angrep på chifferet.

Sikkerhet

Engangsnøkler er informasjonsteoretisk sikre, basert på at den krypterte meldingen (chifferteksten) ikke gir en kryptoanalytiker noen informasjon om den opprinnelige meldingen bortsett fra lengden på meldingen. Dette er en veldig sterk indikator på sikkerheten, som først ble utviklet under den annen verdenskrig av Claude Shannon, og matematisk bevist av ham ved bruk av engangsnøkler omtrent på samme tid. Hans resultater ble publisert i Bell Labs Technical Journal i 1949. Ved korrekt bruk så vil engangsnøkler være informasjonsteoretisk sikre selv mot angripere med ubegrenset prosesseringskraft. For å fortsette eksemplet ovenfor: Gitt at Eva har fått tak i Karis krypterte melding «ENQVZ». Om Eva hadde hatt ubegrenset prosesseringskraft, så ville hun raskt ha funnet at nøkkelen «XMCKL» ville produsert klarteksten «HELLO», men hun ville også finne at nøkkelen «TQURI» ville produsert klarteksten «LATER», som er en like sannsynlig klartekst:

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

Det er mulig å «dekryptere» chifferteksten hvilken som helst melding med det samme antall bokstaver ved å bruke forskjellige nøkler, og det finnes ingen informasjon i chifferteksten som setter Eva i stand til å velge blant de forskjellige mulige resultatene.

Konvensjonelle symmetriske krypteringsalgoritmer bruker komplekse mønstre av substitusjon og transponeringer. For de beste av disse som er bruk i dag så er det ikke kjent om det finnes en kryptoanalytisk prosedyre som kan reversere helt eller delvis disse mønstrene uten å kjenne nøkkelen som ble brukt under krypteringen. Asymmetriske krypteringsalgoritmer bruker matematiske utfordringer som er ansett som umulige å løse, slik som heltallsfaktorisering eller diskrete logaritmer. Det finnes dog ikke bevis på at disse utfordringene er uløselige, og matematiske gjennombrudd kan gjøre eksisterende systemer sårbare for angrep.

Videre lesing

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

Referanser

• 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.

Eksterne lenker

• Detaljert beskrivelse av engangsnøkkel med eksempler og bilder Cipher Machines and Cryptology
• Marcus Ranums engangsnøkkel FAQ
• FreeS/WAN ordboksinnlegg med diskusjon om engangsnøkkelens svakheter
• Engangsnøkkel-basert program [3] Arkivert 13. september 2017 hos Wayback Machine.