I kryptografi er one-time pad , også kalt one - time pad , en type krypteringsalgoritme der ren tekst kombineres med en tilfeldig nøkkel eller "pad" så lenge ren teksten og bare brukes én gang. Den ble oppfunnet i 1917 . Hvis nøkkelen er virkelig tilfeldig, aldri gjenbrukt og selvfølgelig holdt hemmelig, kan engangsblokkmetoden vise seg å være uslåelig. En av synonymene kan være bærbare .
"Pad"-delen av navnet kommer fra tidlige implementeringer hvor nøkkelen ble distribuert i form av en papirblokk, slik at siden kunne bli ødelagt og ødelagt etter bruk. For å gjøre det lettere å skjule, var notatboken noen ganger fysisk veldig liten. [ 1 ]
Vernam -chifferet tilhører denne typen chiffer, faktisk ble de begge skapt av samme person, Gilbert Vernam . Vernams system var et chiffer som kombinerte en melding med en nøkkel som ble lest fra en løkke med papirbånd. I sin opprinnelige form var ikke Vernams system uknuselig fordi nøkkelen kunne gjenbrukes. Den unike bruken kom litt senere, da Joseph Mauborgne innså at hvis nøkkelbåndet var helt tilfeldig, ville det øke den kryptoanalytiske vanskeligheten . Noen forfattere bruker begrepet "Vernam-chiffer" som et synonym for "engangsblokk", mens andre bruker det for enhver additiv strømchiffer , inkludert de som er basert på en kryptografisk sikker pseudo-tilfeldig tallgenerator ; nedenfor vil vi bruke det i sistnevnte betydning. [ 2 ]
Vernam-Mauborgne engangsputen ble opprinnelig anerkjent som svært vanskelig å bryte, men dens spesielle status ble oppdaget av Claude Shannon rundt 25 år senere. Ved å bruke elementer fra informasjonsteori viste han at engangsblokken hadde en egenskap han kalte perfekt hemmelighold : det vil si at chifferteksten gir absolutt ingen informasjon om klarteksten . Derfor er den tidligere sannsynligheten for en ren melding M lik den bakre sannsynligheten for en ren melding M gitt den tilsvarende chifferteksten. Og faktisk er alle klartekster like sannsynlige. Dette er en kraftig forestilling om kryptoanalytiske vanskeligheter. [ 3 ]
Til tross for Shannons demonstrasjon har engangsputen alvorlige ulemper i praksis:
Disse implementeringsvanskene har ført til tilfeller der noen engangspassboksystemer har blitt ødelagt, og er så alvorlige at de har forhindret engangspassboken fra å bli tatt i bruk som et utbredt datasikkerhetsverktøy.
Spesielt er engangsbruk helt nødvendig. Hvis en engangsblokk bare brukes to ganger, kan enkel matematikk redusere den til et nøkkelkryptering. Hvis begge klartekstene er på naturlig språk (for eksempel på engelsk eller russisk), selv om de begge er hemmelige, er det en god sjanse for at de vil bli gjenfunnet med kryptoanalyse, muligens med noen tvetydigheter. Selvfølgelig, av den lengre av de to meldingene, kan bare den delen som overlapper med den kortere meldingen gjenopprettes, pluss kanskje litt mer ved å fullføre et ord eller en setning. Den mest kjente utnyttelsen av denne sårbarheten er VENONA-prosjektet . [ 4 ]
Engangsblokken gir ingen mekanisme for å sikre meldingsintegritet, og i teorien kan en angriper i midten som kjenner den eksakte meldingen som sendes, enkelt erstatte deler av eller hele meldingen med en tekst etter eget valg som er av samme lengde. Standardteknikker for å unngå dette, for eksempel en meldingsautentiseringskode, kan brukes , men de mangler beviset på sikkerhet som engangsblokker nyter godt av.
Historien til engangsputen er preget av fire separate, men nært beslektede funn.
Det første engangspassboksystemet var elektrisk. I 1917 fant Gilbert Vernam ( fra AT&T ) opp og patenterte senere et chiffer basert på teletypeteknologi . Hvert tegn i meldingen ble elektrisk kombinert med et tegn til en nøkkel på papirbånd. Kaptein Joseph Mauborgne (senere kaptein i USAs hær og senere sjef for Signal Corps ) innså at nøkkelsekvensen kunne være helt tilfeldig, og at i et slikt tilfelle ville krypteringsanalyse være vanskeligere. Sammen oppfant de det første engangstapesystemet. [ 2 ]
Den andre utviklingen var papirboksystemet. Diplomater hadde lenge brukt koder og chiffer for konfidensialitet og for å minimere telegrafavgifter . Når det gjelder koder, ble ord og uttrykk konvertert til grupper med tall (vanligvis 4 eller 5 sifre) ved hjelp av en kodebok av ordbok. For ekstra sikkerhet kunne hemmelige numre (vanligvis modulo-sum) kombineres med hver kryptert gruppe før overføring, og de hemmelige numrene endres med jevne mellomrom (dette ble kalt superkryptering). På begynnelsen av 1920-tallet innså tre tyske kryptografer, Werner Kunze, Rudolf Schauffler og Erich Langlotz, som var dedikert til å bryte slike systemer, at de aldri kunne bli ødelagt hvis et eget tilfeldig valgt additivnummer ble brukt for hver kodet gruppe. De hadde dupliserte papirnotatbøker med linjer med tilfeldige tallgrupper. Hver side hadde et serienummer og åtte linjer. Hver linje hadde seks 5-sifrede tall. En side ble brukt som et regneark for å kode en melding og deretter ødelagt. Serienummeret til siden ble sendt med den krypterte meldingen. Mottakeren ville reversere prosedyren og deretter ødelegge sin kopi av siden. Det tyske utenriksdepartementet satte dette systemet i drift i 1923 . [ 2 ]
Anta at Alice vil sende meldingen "HEI" til Bob. Anta også at tidligere, på en eller annen måte, to papirnotatbøker som inneholder identiske tilfeldige bokstavsekvenser er blitt produsert og sendt sikkert til begge. Alice velger den aktuelle ubrukte siden fra notatboken. Vanligvis bestemmes måten å gjøre dette på på forhånd, for eksempel "bruk ark nummer 12 på Arbeidernes Dag", eller "bruk neste ledige ark til neste melding". Det valgte arkmaterialet er nøkkelen til denne meldingen. Alle bokstaver i notatboken vil som standard bli kombinert med én bokstav i meldingen. Det er vanlig, men ikke obligatorisk, å tildele hver bokstav en numerisk verdi: for eksempel er "A" 0, "B" er 1, og så videre opp til "Z", som er 26. I dette eksemplet er teknikken er å kombinere nøkkelen og meldingen ved hjelp av modulær addisjon . Modulo 27-summen lages (hvis A-en regnes som 0, og dermed er Z=26) av de numeriske verdiene av bokstavene som tilsvarer meldingen og nøkkelen. Hvis nøkkelen starter med:
XMCKog meldingen er "HALLO", så vil krypteringen gjøres som følger:
24 (X) 12 (M) 2 (C) 10 (K) nøkkel + 7 (H) 15 (O) 11 (L) 0 (A) melding = 31 27 13 10 tast + melding = 4 (E) 0 (A) 13 (N) 10 (K) Resultat (mod 27) = chiffertekstMerk at når tallet er større enn 26, avkortes den resulterende verdien ved modulær aritmetikk .
Den krypterte teksten som måtte sendes til Roberto ville da være "EANK". For å få ren tekst bruker Bob den tilsvarende nøkkelsiden og gjør den samme prosessen, men omvendt. Nå trekkes nøkkelen fra chifferteksten, igjen ved å bruke modulær aritmetikk:
27 27 27 27 verdi 27 + 4 (E) 0 (A) 13 (N) 10 (K) chiffertekst - 24 (X) 12 (M) 2 (C) 10 (K) nøkkel = 7 15 38 27 27 + chiffertekst - nøkkel = 7 (H) 15 (O) 11 (L) 0 (A) resultat (mod 27) = dekryptert tekstMerk at 27 tidligere er lagt til hver verdi, og på slutten blir også modulen 27 brukt.
Dermed henter Roberto Alicias klartekst, det livsviktige budskapet "HELLO". Både Alice og Bob ødelegger nøkkelarket umiddelbart etter bruk, og forhindrer dermed gjenbruk og et angrep på krypteringen som i hovedsak ville være trivielt. KGB sendte ofte sine agenter engangsputer trykt på bittesmå ark "flash-papir" - papir som er kjemisk omdannet til nitrocellulose , som brenner nesten øyeblikkelig og ikke etterlater aske.
Den klassiske engangsblokken for spionasje (som pleide å bestå av ekte papirblokker - ofte bittesmå for enkel å skjule - en skarp blyant og bruk av litt mental matematikk ) kan implementeres i programvare ved hjelp av datafiler. som input (ren tekst), utdata (chiffertekst) og nøkkel (den nødvendige tilfeldige sekvensen). XOR- operasjonen brukes ofte til å kombinere klarteksten med nøkkelen, og er spesielt attraktiv i databehandling, siden det vanligvis er en innebygd maskininstruksjon og derfor veldig rask. Det er imidlertid ikke trivielt å sikre at nøkkelen virkelig er tilfeldig, at den bare brukes én gang, at den aldri havner i hendene på motstandere, og at den blir fullstendig ødelagt etter bruk. Tilleggsdelene av en programvareimplementering for engangsblokker byr på reelle utfordringer: sikker håndtering/overføring av ren tekst, virkelig tilfeldige nøkler og unik nøkkelbruk.
Engangsblokker er sikre fra et informasjonsteoretisk synspunkt, i den forstand at den krypterte meldingen ikke gir en kryptoanalytiker noen informasjon om den opprinnelige meldingen. Dette er en kraftig forestilling om sikkerhet, først utviklet under andre verdenskrig av Claude Shannon og matematisk bevist av Shannon rundt samme tid. Resultatene hans ble publisert i Bell Labs Technical Journal i 1949. Riktig brukte engangsputer er sikre i denne forbindelse selv mot motstandere med uendelig regnekraft. For å fortsette med eksemplet ovenfor, anta at Eva fanger opp Alices chiffertekst: "EANK". Hvis Eva hadde uendelig regnekraft, ville hun raskt finne ut at nøkkelen "XMCK" ville produsere klarteksten "HELLO", men hun ville også finne ut at nøkkelen "FCJR" ville produsere klarteksten "ZYES", en like plausibel melding:
27 27 27 27 verdi 27 + 4 (E) 0 (A) 13 (N) 10 (K) chiffertekst − 5 (F) 2 (C) 9 (J) 18 (R) mulig nøkkel = 26 25 31 19 27 + chiffertekst - mulig nøkkel = 26 (Z) 25 (Y) 4 (E) 19 (S) resultat (mod 27) = mulig dekryptert tekstFaktisk er det mulig å "dekryptere" hvilken som helst melding med samme antall tegn fra chifferteksten ganske enkelt ved å bruke en annen nøkkel, og det er ingen informasjon i chifferteksten som lar Eva velge mellom mulige lesninger av chifferteksten.
De fleste konvensjonelle krypteringsalgoritmer, både symmetriske og asymmetriske, bruker komplekse substitusjons- og transposisjonsmønstre. For den beste algoritmen som for tiden er i bruk, er det ikke kjent om det er en kryptoanalytisk prosedyre som kan reversere (eller delvis reversere) disse transformasjonene uten å kjenne til nøkkelen som brukes under kryptering.
Rent praktisk er en slik prosedyre ikke kjent for de beste av dem, selv om det kan være beregningsalgoritmer som kan gjøre det på "rimelig" tid. Et av de viktigste uløste problemene innen beregningsteori er relatert til dette problemet; hvis P=NP , så ville det i det minste være mulig at slike algoritmer kunne bli funnet, og de ville sikkert bli søkt hardere enn de er i dag. Og selv om det viser seg ikke, kan noen nåværende kryptosystemer fortsatt være ødelagt. Engangspassboken ville imidlertid ikke vært mindre sikker hvis det ble vist at P=NP. Det antas for tiden at P≠NP, og derfor er det tvilsomt at dette spørsmålet har praktisk relevans for kryptoanalyse eller utforming av krypteringsalgoritmer.
Selv om engangsputer er beviselig sikre hvis de er riktig generert og brukt, kan en liten feil gjøre vellykket kryptoanalyse mulig:
For å forklare engangspassboken er det nødvendig å skille mellom to begreper om sikkerhet. Den første er den teoretiske sikkerheten til engangspassbook-systemet demonstrert av Shannon. Den andre er sikkerheten som tilbys av de mest avanserte chiffer (for eksempel AES ) designet med prinsippene som er lært i løpet av den lange historien med kodebrudd og utsatt for intensiv testing i en standardiseringsprosess, enten offentlig eller av en tjeneste. sikkerhet (empirisk sikkerhet ). Førstnevnte er matematisk bevist og er underlagt den praktiske tilgjengeligheten av tilfeldige tall. Den andre er uprøvd, men klarert av de fleste regjeringer for å beskytte sine viktigste hemmeligheter.
Hvis nøkkelen er generert av et deterministisk program, er den ikke tilfeldig, og krypteringssystemet kan heller ikke sies å tilby den teoretiske sikkerheten til engangsblokken. Det kalles strømchiffer . Disse bruker vanligvis en liten nøkkel som brukes som et frø for en lang pseudo -tilfeldig strøm , som deretter kombineres med meldingen ved hjelp av en engangs-pad-lignende mekanisme (f.eks. XOR). Strømchiffer kan være sikre i praksis, men de kan ikke være helt sikre i samme påviselige forstand som engangsblokken.
Fish-chifrene som ble brukt av den tyske hæren i andre verdenskrig viste seg å være usikre strømchiffer, ikke nyttige automatiserte engangsblokker slik designerne deres hadde til hensikt. Bletchley Park brøt regelmessig en av disse, Lorenz Cipher Machine .
Imidlertid, hvis en berømt moderne kryptografisk sikker pseudorandom-nummergenerator brukes , kan den danne grunnlaget for en empirisk sikker strømchiffer. Det er mange velprøvde design i det offentlige domene, alt fra enkelheten til RC4 til bruken av et blokkchiffer som AES i tellermodus. Det ser ut til at det er liten grunn til å finne opp nye strømchiffer, men det har lenge vært antatt at NSA og lignende byråer bruker betydelig innsats på strømchiffer for sine offentlige klienter.
Likheten mellom strømchiffer og engangsblokker fører ofte til at de kryptografisk uforsiktige til å finne opp usikre strømchiffer under den falske troen på at de har utviklet en praktisk versjon av engangsblokken. En spesielt usikker versjon er tilfeldige tallgeneratorer som er distribuert i mange (kanskje de fleste) av tilbehørsbibliotekene til programmeringsspråk eller i form av operativsystemanrop . De produserer vanligvis sekvenser som består noen (eller mange) statistiske tester , men som likevel kan brytes av kryptoanalytiske teknikker. For en tid begrenset ANSI C-standarden utdata fra C-språkets tilfeldige tallrutine til et enkeltpresisjons heltall, 16 biter for de fleste implementeringer, og ga 32768 distinkte verdier før iterasjon. Dette er helt usikkert og brytes lett av brute force (for å komme deg rundt, bare vit at en 1 GHz datamaskin som tar 10 000 klokkesykluser for å sjekke en RNG- syklusforskyvning (et latterlig stort antall) vil ta mindre enn en tredjedel av et sekund å sjekke alt mulige forskyvninger). Standard tilfeldige tallgeneratorer er ikke egnet for kryptografiske formål, spesielt for engangsblokken. Spesielt bør den relativt nye Mersenne-tornadoalgoritmen , som er mye beundret, selv om den er "tilfeldig" nok for de fleste simulerings- eller forskningsbruk, bedre enn de fleste generatorer av sitt slag, og også ganske rask, ikke brukes til å generere engangspassboknøkler . Algoritmen er deterministisk og ble ikke designet for kryptografisk sikkerhet.
Videre er offentlig kjente verdier som etterfølgende tall for maratonløpstider , sluttkurs på aksjer, uansett hvor lite kjent, daglige atmosfæriske temperaturer eller trykk osv., selv om de tilsynelatende er tilfeldige, forutsigbare – i ettertid. Faktisk kan virkelig tilfeldige sekvenser som har blitt publisert heller ikke brukes, siden de er forutsigbare hvis de identifiseres. Et eksempel er publiseringen av en tabell med én million tilfeldige tall av Rand Corp i 1950; den har bestått alle statistiske tilfeldighetstester så langt, og antas å være virkelig tilfeldig. Men etter å ha blitt publisert er den fullstendig forutsigbar. Det samme er sifrene til pi, e, fi og andre irrasjonelle eller transcendentale tall; Sekvensene kan være tilfeldige (et åpent spørsmål egentlig), men de er fullstendig forutsigbare.
For å oppnå Shannons sikkerhet er det nødvendig med en perfekt uforutsigbar tilfeldig datakilde. Et teoretisk grunnlag for den fysiske eksistensen av uforutsigbarhet er kvantemekanikk . Hans påstander om uforutsigbarhet er gjenstand for eksperimentell verifisering. Se: Klokkeeksperimenter . Et annet grunnlag er teorien om ustabile dynamiske systemer og kaosteori . Disse teoriene antyder at selv i den deterministiske verden av newtonsk mekanikk , utvikler virkelige systemer seg på måter som ikke kan forutsies i praksis fordi de innledende forholdene må være kjent med en presisjon som vokser eksponentielt over tid.
For å kunne brukes i en engangsblokk, må dataene vise perfekt tilfeldighet. I praksis viser de fleste fonter noen ufullkommenhet eller avvik. Kvaliteten på tilfeldighet måles ved entropi . En helt tilfeldig bit har en entropi på én. En idé fra Von Neumann er å bruke en algoritme for å kombinere flere tilfeldig ufullkomne biter, med entropi mindre enn én, for å produsere en bit med entropi lik én. Denne prosessen kalles entropidestillasjon eller Von Neumann-bleking , og den gjør det praktisk mulig å generere tilfeldige data som er egnet for bruk i en engangspute. Von Neumann-bleking består av følgende: [ 5 ]
| inngangsbiter | Avgang |
|---|---|
| 00 | Ingen utgang |
| 01 | Returbit "1" |
| 10 | Returbit "0" |
| elleve | Ingen utgang |
På Linux (og andre Unix-lignende systemer ) bruker kjernens tilfeldige tallgenerator, /dev/random , omgivelsesstøy for å generere tilfeldige data og er bedre enn mange systemanropsbaserte design. Den prøver å estimere mengden entropi den samler inn og krasjer hvis entropipoolen går tom. Den hevder å være, og antas faktisk å være, bedre enn mange lignende generatorer, og i så fall kommer den veldig nær ved å være tilfredsstillende tilfeldig. Men denne prosessen er treg på systemer som har få brukbare støykilder. Imidlertid kan den mates ytterligere entropi ved å lese fra en støygenererende enhet.
Linux tilbyr også /dev/urandom, som bruker en deterministisk algoritme for å generere data når ingen omgivelsesstøy er tilgjengelig. Det finnes forbedrede design, for eksempel Yarrows algoritme . Engangspassboknøkler generert ved hjelp av denne metoden (dvs. med deterministiske tilfeldige tallgeneratorer) mangler den teoretiske sikkerheten til en engangspassbok. Ryllik tilbyr minst like mye styrke som en Triple DES- basert blokkchiffer .
Hvis en datamaskin som brukes til å generere engangspassbooks blir kompromittert av et datavirus eller annen skadelig programvare , eller av en motstander som får fysisk tilgang, kan programvaren modifiseres for å overføre dataene eller generere tilsynelatende tilfeldige data som faktisk er forutsigbare. En måte å redusere denne risikoen på er å generere bærbare datamaskiner på en maskin som aldri er koblet til et datanettverk og helst ikke brukes til noen annen oppgave. Innsamling av data på ferske, tomme lagringsenheter (for eksempel en diskett eller CD-R ) fjerner en annen kilde til skadelig programvare. Hvis det skal produseres notatbøker i papir, er det bedre at skriveren også er dedikert. Et alternativ kan være å bruke en gammel bærbar datamaskin til å generere bærbare datamaskiner, tørket og installert på nytt med en pålitelig kopi av et åpen kildekode -operativsystem , for eksempel Linux eller BSD . Den lille størrelsen gjør at den enkelt kan oppbevares i en safe når den ikke er i bruk.