One-time pad

I kryptografi, one-time pad, også kaldet engangsbrug påfyldning er en type krypteringsalgoritmer, som klartekst er kombineret med en tilfældig tast eller "pad" samme længde som alm og kun bruges en gang. Det blev opfundet i 1917. Hvis nøglen er virkelig tilfældigt, aldrig genbruges, og selvfølgelig, holdes hemmeligt, det kan påvises, at fremgangsmåden one-time pad er ubrydelig. En af dens synonymer kan være notesbog.

Den del af navnet på "bogen" kommer fra de indledende implementeringer hvor nøglen blev fordelt som en blok papir, så den side, kunne brydes og destrueres efter brug. For at lette fortielse undertiden bog var fysisk meget lille.

Den ene gang pad kommer fra Vernam cipher, som modtager alle sit navn fra Gilbert Vernam, en af ​​dens opfindere. Vernam system var en cipher, der kombinerede en meddelelse med en nøgle, der læses fra et papir tape loop. I sin oprindelige form, Vernam system ikke var ubrydelig fordi nøglen kunne genbruges. Den eneste brug kom lidt senere, da Joseph Mauborgne erkendte, at hvis nøglen tape var helt tilfældigt, kryptoanalytiske vanskelighed stigningen. Nogle forfattere bruger udtrykket "Vernam cipher" synonymt med "one-time pad", mens andre bruger det til noget kryptering flow tilsætningsstof, herunder på grund af en pseudorandom nummer generator kryptografisk sikker; nedenfor vil vi bruge det i denne forstand.

Secret

Først blev det erkendt, at one-time pad Vernam-Mauborgne var meget svært at bryde, men hans særstatus blev opdaget af Claude Shannon ca. 25 år senere. Brug elementer af information teori, viste han, at den ene gang pad havde en ejendom, som han kaldte perfekt hemmelighed: det vil sige, at ciphertext giver absolut ingen oplysninger om alm. Derfor forudgående sandsynlighed for en meddelelse i klar M er den samme som den bageste sandsynligheden for en meddelelse i klar M givet tilsvarende ciphertext. Og faktisk alle klare tekster er lige sandsynlige. Dette er en stærk begrebet kryptoanalytiske vanskeligheder.

På trods af den demonstration af Shannon, den ene gang pad er i alvorlige praktiske ulemper:

  • notesbøger kræver perfekt tilfældig én anvendelse
  • generering og udveksling af bøger til engangsbrug skal være sikker, og bogen skal være mindst lige så længe som det budskab
  • Det kræver omhyggelig med at sikre, at du altid forblive hemmelige for enhver modstander, og det er nødvendigt bortskaffes korrekt for at undgå delvis eller fuldstændig derfor "engangsbrug" genbrug behandling.

Disse gennemførelsesproblemer vanskeligheder har forårsaget sager, der har brudt nogle systemer af one-time pad, og er så alvorlige, at de har forhindret one-time pad er blevet vedtaget som en generel edb-sikkerhed værktøj.

Navnlig er absolut nødvendigt at engangsbrug. Hvis den ene gang pad bruges lige to gange, kan en simpel matematisk operationer reducere den til at køre krypteringsnøgle. Hvis begge er i klar tekst i naturligt sprog, selv om begge er hemmelige, er der bundet til genvindes med kryptoanalyse, eventuelt med nogle uklarheder. Selvfølgelig er den længste besked både kan genvinde kun den del, der overlapper den kortere besked, plus måske lidt mere ved at udfylde et ord eller en sætning. Den mest berømte bedrifter denne sårbarhed er Venona projektet.

Den ene gang pad giver ingen mekanisme til at sikre besked integritet og i teorien en angriber i midten, der kender den præcise budskab bliver sendt let kunne erstatte en del af eller hele meddelelsesteksten efter eget valg, der er af samme længde. De kan bruge standard teknikker til at undgå dette, som en besked autentifikationskode, men mangler dokumentation for sikkerhed nydes af engangsprodukter notesbøger.

Historie

Teknisk udvikling

Historien om den one-time pad er præget af fire separate, men nært beslægtede opdagelser.

Det første sæt engangs-puden blev elektrisk. I 1917, Gilbert Vernam opfundet og senere patenteret en teknologi-baseret kryptering ticker. Hver karakter af beskeden elektrisk kombineret med en karakter på en tast papirstrimmel. Anfører Joseph Mauborgne indset, at tastesekvens kunne være helt vilkårlig og i givet fald ville kryptoanalyse være vanskeligere. Sammen opfandt den første tape systemet engangsbrug.

Den anden udvikling var papir bog-systemet. Diplomater havde længe brugt koder og ciphers for fortrolighed og for at minimere telegraf udgifter. For de koder, ord og sætninger blev grupper af numre ved hjælp af en kode bog typen ordbog. For at få ekstra sikkerhed, kunne hemmeligt nummer kombineres med hver gruppe krypteret før transmission, og hemmeligt nummer ændres med jævne mellemrum. I de tidlige 20'ere, tre tyske kryptografer, Werner Kunze, Rudolf og Erich Langlotz Schauffler, som blev engageret i at bryde systemer godt, de indså, at de aldrig kunne brydes, hvis en separat additiv nummer blev anvendt, tilfældigt valgt for hver kodet gruppe. Papir pads blev duplikeret med linjer af grupper af tilfældige tal. Hver side havde et serienummer og otte linjer. Hver linje havde seks 5-cifrede numre. En side bruges som et regneark til at kryptere en meddelelse og derefter destrueres. Serienummeret på siden sendes med kodet meddelelse. Modtageren vil vende proceduren og derefter ødelægge hans kopi af siden. Det tyske udenrigsministerium dette system sættes i drift i 1923.

Eksempel

Antag Alice ønsker at sende beskeden 'Hello' til Bob. Antag også, at tidligere, en eller anden måde, der har været to papir notesbøger indeholder identiske sekvenser af tilfældige bogstaver, der blev sendt af både vej sikkert. Alice vælger den passende ubrugte siders bog. Den sædvanlige måde at gøre dette er besluttet på forhånd, for eksempel "brug det 12. ark på Labor Day" eller "brug den næste tilgængelige ark til den næste meddelelse." Materialet valgte ark er nøglen til denne meddelelse. Alle bogstaverne i bogen vil blive kombineret på en forudbestemt måde med et brev af meddelelsen. Det er almindeligt, men kræves ikke, at tildele hvert bogstav en numerisk værdi: for eksempel "A" er 0, "B" er 1, og så videre indtil "Z", som er 25. I dette eksempel er teknikken at kombinere nøglen og meddelelsen ved hjælp af modulære tilføjelse. Summen modul 26 i de numeriske værdier af bogstaverne svarer til beskeden, og nøglen er. Hvis nøglen begynder med:

og budskabet er "Hello" ville da kryptering er som følger:

Bemærk, at når antallet er større end 25, derefter ved modulær aritmetik, den resulterende værdi er afkortet.

Den ciphertext ville have at give Roberto ville derefter "FBNK". For klartekst, bruger Roberto nøglen relevante side og udfører den samme proces, men i omvendt rækkefølge. Nu er nøglen trækkes fra ciphertext, igen under anvendelse af modulær aritmetik:

Bemærk, at alle værdi, der tidligere sum er 26, og endelig modulet 26 også anvendelse.

Så Roberto inddrive klartekst Alice, den vitale meddelelsen "Hello". Både Alicia og Roberto ødelægge nøglen ark straks efter brug, hvilket forhindrer genbrug og et angreb på krypteringen ville være trivielt i naturen. KGB sendte ofte agenter til deres notesbøger bruge en enkelt trykt på bittesmå blade af "Flash papir" kemisk omdannet til nitrocellulose papir, der brænder næsten øjeblikkeligt og efterlader ingen aske.

Bestil en klassisk brug af spionage kan implementeres i software form, ved hjælp af datafiler som input, output og nøgle. Ofte XOR operation til at kombinere klartekst med nøglen, og er især attraktiv computing, da det som regel er en oprindelig maskininstruktionen og er derfor meget hurtigt. Det er imidlertid ikke trivielt at sikre, at nøglen er helt tilfældig, anvendes kun en gang, der aldrig ender i hænderne på modstandere og er fuldstændigt ødelagt efter brug. De ekstra dele af en implementering af one-time pad ved hjælp af software til stede reelle udfordringer: ledelse / sikker overførsel af klartekst, virkelig tilfældige nøgler og den eneste brug af nøglen.

Sikkerhed

De engangsbrug notebooks er sikkert fra synspunkt af information teori, i den forstand, at den krypterede meddelelse ikke giver en cryptanalyst ingen oplysninger om den oprindelige meddelelse. Dette er en kraftfuld forestilling om sikkerhed først udviklet under Anden Verdenskrig af Claude Shannon og matematisk demonstreret af Shannon på samme tid. Deres resultater blev offentliggjort i Bell Labs Tekniske Journal i 1949. De engangsprodukter bøger, anvendes korrekt, er de sikre i denne forstand selv mod modstandere med uendelig beregningskraft. For at fortsætte eksemplet ovenfor, formoder Eva opfanger Alices ciphertext "FBNK". Hvis Eva dispusiera af uendelig computerkraft, ville finde hurtigt, at de "XMCK" tasten producere klartekst "Hello", men også ville finde, at "FCJR" tasten producere klartekst "i går", en besked lige plausibel:

Faktisk er det muligt at "dechifrere" et budskab med det samme antal tegn fra ciphertext blot ved hjælp af en anden nøgle, og der er ingen oplysninger i ciphertext som vil give Eva til at vælge blandt de mulige læsninger af ciphertext.

De fleste konventionelle krypteringsalgoritmer, symmetriske og asymmetriske, anvende komplekse mønstre af substitution og gennemførelse. For den bedste algoritme, der anvendes på nuværende tidspunkt, er det usikkert, om en kryptoanalytiske procedure, der kan vende disse ændringer uden at kende nøglen anvendes under kryptering.

I praksis, ikke til den bedste af dem kendte procedure, selv om der kan være computer-algoritmer til at gøre det på en »rimelig« tid. En af de store uløste problemer i beregnelighed er relateret til dette problem; hvis P = NP, så ville det i det mindste muligt, at de kan finde og algoritmer, og helt sikkert søge hårdere end i dag. Selvom det ikke er bevist, kan nogle af de eksisterende kryptosystemer stadig bryde. Dog ville den ene gang pad være mindre sikker, hvis det blev vist, at P = NP. På nuværende tidspunkt er det menes, at P ≠ NP, og derfor er det tvivlsomt, at dette spørgsmål er af praktisk relevans for kryptoanalyse eller design af krypteringsalgoritmer.

Angreb

Selvom engangsbrug notebooks er påviseligt sikkert, hvis de anvendes og genereres korrekt, kan en lille fejl muliggøre en succesfuld kryptoanalyse:

  • Lykkedes 1944-1945 Signal Security Agency amerikanske hær i at løse et system af engangs-pad, der anvendes af det tyske udenrigsministerium til høj trafik, med kodenavnet GEE. Det GEE var usikker, fordi bøgerne ikke var helt tilfældig maskine bruges til at generere bøgerne produceret en forudsigelig udgang.
  • I 1945 opdagede den amerikanske, at Canberra-Moskva budskaber blev kryptere først ved en kode bog og derefter baseret på en engangs-pad. Men den ene gang pad anvendte var den samme som Moskva for Washington DC-Moskva-meddelelser. Kombineret med, at nogle Canberra-Moskva-meddelelser omfattede britiske regeringsdokumenter, der var kendt, dette tilladt nogle af de krypterede meddelelser, der skal brydes.
  • Sovjetiske spionage bureauer beskæftiger engangsbrug notesbøger til at sikre kommunikation med agenter og agent controllere. Analysen viste, at disse bøger blev genereret af mennesker, der bruger skrivemaskiner. Denne metode er naturligvis ikke "virkelig" tilfældig, fordi den indebærer, at visse praktiske tastesekvenser mere sandsynlige end andre, men generelt vist sig effektive. Ingen kopier af nøglerne kun anvendes tilbudt håb om kryptoanalyse nogle defekter i metoden til generering eller genbrug af nøglerne. I begyndelsen af ​​40'erne, lykkedes den amerikanske og britiske efterretningstjeneste til at bryde trafik fra one-time pad til Moskva under Anden Verdenskrig, som et resultat af visse fejl at generere og distribuere nøgler.

Krav til ægte tilfældighed

For at forklare bogen kun bruge er nødvendigt at skelne mellem to forestillinger om sikkerhed. Den første er den teoretiske systemets sikkerhed Book engangsbrug demonstreret af Shannon. Den anden er den sikkerhed, der tilbydes af de krypterede pointere designet med principperne lært under den lange historie kode bryde og underkastet intensiv test i en standardiseringsproces, enten offentligt eller af en sikkerhed tjenesten første klasse. Den første er matematisk bevist og underlagt den praktiske tilgængelighed af tilfældige tal. Den anden er uprøvede, men får den tillid hos flertallet af regeringer til at beskytte deres mest vitale hemmeligheder.

Empiriske metoder kan stille sikkerhed, men ikke har Shannon sikkerhed

Hvis nøglen er genereret af en deterministisk program, så er det ikke tilfældigt eller vi kan sige, at kryptering system frembyder den teoretiske sikkerhed one-time pad. Det kaldes åen cipher. Generelt er disse bruge en lille nøgle anvendes som frø til en lang pseudotilfældig strøm, som derefter kombineres med meddelelsen ved hjælp af en mekanisme, såsom engangs-pad. Strømmen ciphers kan være sikker i praksis, men kan ikke være helt sikker i den samme følelse af påviselig one-time pad.

Fisken ciphers anvendes af den tyske hær under Anden Verdenskrig viste sig at være usikre stream ciphers ikke nyttige notebooks bruge en enkelt automatiseret som dens designere hensigten. Bletchley Park brød en af ​​dem regelmæssigt, Lorenz cipher maskine.

Men hvis en generator berømte moderne kryptografisk sikker pseudo-tilfældige tal anvendes, kan det danne grundlag for en empirisk sikker enkeltbitskryptografering. Der er mange godt dokumenteret i det offentlige rum design, der spænder fra den enkelhed af RC4 til at bruge en blok cipher som AES i tæller mode. Der synes at være lidt grund til at opfinde nye stream ciphers, men det menes i nogen tid, at NSA og lignende organer beskæftiger en betydelig indsats for at streame ciphers for deres offentlige kunder.

Metoder, der ikke tilbyder empirisk sikkerhed eller Shannon sikkerhed

Ligheden mellem stream ciphers og single-use notebooks ofte fører kryptografisk uforsigtige at opfinde usikre stream ciphers under den fejlagtige tro, at han havde udviklet en praktisk version af one-time pad. En særlig usikker udgave er tilfældige tal generatorer, der distribueres i mange biblioteker af accessoriske programmeringssprog eller som opkald til operativsystemet. Sekvenser, der normalt producerer nogle statistiske tests passere, men er spaltes med kryptoanalytiske teknikker. For en tid, ANSI C-standard begrænset produktionen af ​​tilfældige tal rutine C-sprog til en hel single-præcision, 16 bit for de fleste implementeringer, hvilket giver 32768 forskellige værdier før du gentager. Dette er helt usikker og let kan brydes ved brute force ville tage mindre end en tredjedel af et sekund til at kontrollere alle mulige forskydninger). Standarden tilfældige tal generatorer er ikke egnede til kryptografiske formål, specielt til one-time pad. Især den relativt nylige Mersenne Twister algoritme, beundret, men som er tilstrækkeligt "tilfældig" for de fleste forsknings- eller simulation bruger, bedre end de fleste af generatorer af samme type, og også ganske hurtigt, Det bruges til at generere nøgler one-time pad. Algoritmen er deterministisk og var ikke beregnet til kryptografiske sikkerhed.

Desuden offentligt kendt som den sene gange maratonløb cifre, lukkekurserne for aktier og aktier, men tilslører de kan være, daglige temperaturer eller atmosfæriske tryk osv, men tilsyneladende tilfældigt, værdier forudsigelig efter begivenheden indtræffer. Faktisk har ægte tilfældige sekvenser er blevet offentliggjort, fordi hvis de er forudsigelige identificere enten kan anvendes. Et eksempel er offentliggørelsen af ​​en tabel over tilfældige tal en million af Rand Corp i 1950; Det har bestået alle statistiske tests af tilfældighed hidtil, og menes at være virkelig tilfældigt. Men, der har været offentliggjort, er det helt forudsigeligt. Så er cifrene i pi, e, fi og andre irrationelle eller transcendental numre; sekvenser kan være tilfældig, men de er helt forudsigelig.

Opnåelse Shannon sikkerhed

For at sikre sikkerheden af ​​Shannon en kilde af perfekt uforudsigelige tilfældige data er nødvendig. En teoretisk grundlag for den fysiske eksistens af uforudsigelighed er kvantemekanik. Hans påstande om uforudsigelighed er underlagt eksperimentel verifikation. Se: Forsøg Bell. Andet grundlag er teorien om ustabile dynamiske systemer og kaos teori. Disse teorier tyder på, at selv i den deterministiske verden af ​​Newtons mekanik, udvikler virkelige systemer på måder, der ikke kan forudsiges i praksis, fordi de ville brug for at kende de oprindelige betingelser med en nøjagtighed, der vokser eksponentielt med tiden.

Således at de kan anvendes i en engangs-pad, bør data viser en perfekt tilfældighed. I praksis viser de fleste kilder enhver ufuldkommenhed eller afvigelse. Kvaliteten af ​​tilfældighed måles ved entropi. En perfekt random bit har en entropi. En idé fra Von Neumann er at bruge en algoritme til at kombinere flere ufuldkomne bits tilfældigt, med én mindre entropi at fremstille en smule med entropi lig med en. Denne proces kaldes entropi destillation eller kridtning Von Neumann, og i praksis kan generere tilfældige data egnet til anvendelse i en engangs-pad. Von Neumann kridtning er som følger:

På Linux, det tilfældige tal generator af kernen, / dev / random, bruger ekstern støj til at generere tilfældige data og er bedre end mange designs baseret på systemkald. Prøv at anslå mængden af ​​entropi indsamlet og blokerer, hvis entropi pulje er opbrugt. Det er bestemt til, og troede, at det virkelig er bedre end mange lignende generatorer, og hvis ja, er meget tæt på at være tilfredsstillende tilfældigt. Men denne proces er langsom på systemer med få brugbare støjkilder. Dog kan der tilføres yderligere entropi læsning af en lydgenererende anordning.

Linux giver også / dev / urandom som bruger en deterministisk algoritme til at generere data, når ingen omgivende støj til rådighed. Der forbedret som Yarrow algoritme design. Nøgler genereret bog én anvendelse af denne metode mangler den teoretiske sikkerhed en engangs-pad. Yarrow tilbyder mindst lige så meget kraft som en cipher baseret på Triple DES blokken.

Hvis en computer bruges til at generere engangsbrug bøger er kompromitteret af en computervirus eller anden malware, eller af en modstander, der får fysisk adgang, kan softwaren modificeres at overføre data eller generere tilsyneladende tilfældige data faktisk de er forudsigelige. En måde at reducere denne risiko er at skabe bøger i en maskine, der aldrig er tilsluttet et computernetværk og fortrinsvis ikke anvendes til andre opgaver. Hvis der indsamles data om nye enheder og storage jomfruer, er en anden kilde til malware-infektion elimineret. Hvis de er til at producere papir notesbøger, er det bedre end printeren er også dedikeret. En mulighed kan være at bruge en gammel bærbar computer til at generere bøger, slettede og geninstalleres med en pålidelig kopi af et open source operativsystem som Linux eller BSD. Dens lille størrelse giver mulighed for nem opbevaring i en sikker, når den ikke er i brug.

  0   0
Forrige artikel Diego de Merlo

Kommentarer - 0

Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha