Fingeraftryk af dine filer

Tre kryptografer ved Stanford University kom for nylig med en smart løsning på det vedvarende problem med identitetstyveri på internettet. Sløve hackere i Rusland, Kina og andre lande sender bunker af e-mails, der ser ud som om de kom fra en finansiel institution som Citibank eller Paypal. Millioner af forbrugere får disse beskeder, som har indlejret HTML-links i dem, der fører den intetanende modtager til lignende websteder, der kører i fjerne steder. Du bliver bedt om at indtaste et brugernavn og en adgangskode, og så har hackeren nøglerne til din bankkonto.

Men gode brugernavne og adgangskoder indtastet på dårlige websteder er ikke den eneste trussel, som forbrugerne står over for. Et potentielt større problem er, at mange mennesker bruger den samme brugernavn og adgangskodekombination på flere websteder. Dette gør det nemmere at huske, men det betyder, at en skruppelløs webstedsoperatør kan tage en liste over brugernavne og adgangskoder fra f.eks. et websted med konkurrencer på internettet og bruge det til at forsøge at bryde ind på online bankkonti.

Så Stanfords kryptografer Blake Ross, Dan Boneh og John Mitchell har designet et smart plug-in til Internet Explorer, der løser dette problem ved at kryptere, hvad du indtaster i adgangskodefeltet, så hvert websted ser en anden adgangskode en adgangskode, der både er baseret på, hvad du skriver og på selve webstedets domæne.

Nu bruger mange mennesker en eller anden variant på denne strategi. Deres Hotmail-adgangskode kan være nosmis-hotmail, mens deres Yahoo! Personals adgangskode er nosmis-Yahoo! Men enhver strategi som denne er ret enkel at tyde. Password scrambling-metoden, som Stanford-trioen har udtænkt, er baseret på en matematisk funktion kaldet en kryptografisk hasha-form af envejsfunktion, der omdanner det, brugeren skriver, til et virvar af tal og bogstaver på en måde, der ikke kan vendes. Fordi Stanford-systemet beregner den kryptografiske hash for både webstedets domæne og brugerens adgangskode, får hackeren andre adgangskoder end de legitime. (Klik her for at finde detaljer om denne smarte løsning.)

Et firma, der bruger kryptografiske hashes på en meget offentlig måde, er Yahoo! Sidste år, Yahoo! redesignet login-processen til sin hjemmeside for at gøre den sniffesikker. Standardmåden at gøre dette på er at bruge kryptering. Men kryptering kan være langsom, især når du kører et af de mest populære websteder på internettet.

Så hvad Yahoo! gjorde i stedet var at ændre sin login-side til at bruge et såkaldt challenge-response system baseret på en kryptografisk hash. Når du prøver at logge ind, downloader Yahoo!s server en kryptografisk hashfunktion skrevet i JavaScript til din browser. Sammen med denne funktion er en udfordring en kort række af bogstaver og tal. Når du indtaster din adgangskode på login-skærmen, tager din browser din adgangskode, tilføjer disse tegn leveret af Yahoo! og beregner den kryptografiske hash for den resulterende streng. Browseren sender derefter den resulterende værdi tilbage til Yahoo!, ingen kryptering nødvendig. Selvom du er på en cybercafe og får din webtrafik opsnuset af belgiske hackere, er der ingen måde for de onde at tage den resulterende hashværdi og udlede din originale adgangskode.

Dette smarte challenge-response-system er også i bunden af ​​Mobil Speedpass-systemet: det er det, der gør Speedpass-radiofrekvensidentifikationsmærket (RFID) så svært at klone. Andre RFID-systemer bruger ikke challenge-response, hvilket gør det forholdsvis nemt at angribe dem.

Men hvad er denne kryptografiske hash-funktion?

Den utroligt nyttige hash

Kryptografiske hash-funktioner er en af ​​de grundlæggende byggesten i nutidens digitale økonomi. Ikke desto mindre forbliver de på mange måder et mysterium både for kryptograferne, der skaber dem, og for den brede offentlighed, der bruger dem hver dag.

Hash-funktioner kaldes nogle gange fingeraftryksfunktioner, fordi de kan bruges til at skabe et unikt fingeraftryk af en digital fil. Fingeraftrykkene er normalt 128-bit eller 160-bit tal, der vises som en sekvens af hexadecimale cifre. Fingeraftrykket på mit navn ved hjælp af MD5-systemet er for eksempel c55bbe0f3ba258f5b1cb6d5b62b0b360. Hash-funktioner er designet således, at i det mindste i teorien ikke to filer nogensinde vil hash til samme værdi.

For at du kan få en idé om, hvordan disse fingeraftryksfunktioner fungerer, har vi indlejret en JavaScript-baseret MD5-beregner nedenfor. Indtast bare noget tekst, og du kan se MD5-hashen. Læg mærke til, hvordan det ændrer sig fuldstændigt, hver gang du tilføjer, fjerner eller ændrer et bogstav. Den måde, fingeraftrykket ændrer sig på, er faktisk uforudsigeligt, hvis vi kunne forudsige, hvordan det ændrer sig, så ville filfingeraftryk ikke være særlig nyttigt.

Indtast din tekst nedenfor:

MD5 er:

De fleste af de hash-funktioner, der bruges i dag, er baseret på en teknik udviklet af MIT-professor Ron Rivest i 1980'erne. (Rivest er nok bedst kendt for at være R i RSA-krypteringsalgoritmen, den offentlige nøglekrypteringsalgoritme, der er indbygget i praktisk talt alle webbrowsere.) På det tidspunkt arbejdede Rivest og andre matematikere på detaljerne i de grundlæggende kryptografiske operationer, som vi nu tage for givet. Hash-funktionerne blev forestillet som en slags kryptografisk komprimeringssystem en måde at tage en stor fil og knuse den ned til en kort række af bogstaver og tal.

Tanken var at bruge disse fingeraftryk som en slags surrogat for selve filerne. I stedet for at underskrive hele filen digitalt, ræsonnerede Rivest og andre, kunne man underskrive hashen digitalt. Fordi public-key kryptografi involverer en masse tung matematik, gør hash-funktioner det næsten lige så hurtigt at signere en ekstremt lang fil som at signere en kort fil.

En af de mest basale ting, du kan gøre med en hash-funktion, er at finde ud af, om en fil har ændret sig: Beregn bare hashen af ​​en fil og skriv den ned. Senere beregner du hashen igen. Hvis hashen ikke har ændret sig, så er oddsene overvældende for, at filen heller ikke har ændret sig.

Sig for eksempel, at du holder økonomien i din lille virksomhed ved at bruge QuickBooks, og du vil tage på ferie i et par dage: folk skal bruge din computer, men du vil sikre dig, at ingen ændrer QuickBooks-dataene. En simpel ting, du kan gøre, er at beregne filens kryptografiske hash, før du går, og skrive nummeret på et kartotekskort. Når du kommer tilbage fra ferie, skal du bare genberegne hashen. Hvis de to værdier ikke stemmer overens, ved du, at filen er blevet manipuleret.

Selvfølgelig behøver du ikke at stoppe med kun én fil. Du kan beregne den kryptografiske hash for hver fil på din computer og lægge dem alle ind i et nyt filecall, der filen hashes.txt. Du kan derefter beregne hashen af ​​hashes.txt og skrive dette fingeraftryk på dit notekort. Gentag processen, når du kommer tilbage fra ferie, og du har en hurtig måde at vide, om en fil på hele din computer har ændret sig. (Du vil ikke have nogen måde at vide, hvilken fil der er ændret, men det er et andet problem.)

Denne idé om at beregne hashen af ​​en hash er grundlaget for et indtrængen detektionssystem kaldet Tripwire, som Purdue University datalogi professor Gene Spafford og hans kandidatstuderende Gene Kim opfandt tilbage i begyndelsen af ​​1990'erne. (Spafford og jeg har været medforfatter på fem bøger om datalogi.) I dag bruger mange forskellige programmer denne Tripwire-tilgang til at sikre integriteten af ​​computerfiler og databaser.

Beregning af hashes af hashes er også grundlaget for en sikker tidsstempeltjeneste opfundet af Stuart Haber og Scott Stornetta, mens de to var hos Bellcore i 1990. Tjenesten, kaldet Surety, gør det muligt at generere et kryptografisk sikkert og uforglemmeligt bevis på, at et givet dokument , fotografi eller anden fil eksisterede på et bestemt tidspunkt på en bestemt dato, og at den ikke er blevet ændret siden.

Kautionsteknikken fungerer ved at beregne et hash-træ baseret på hash-koderne for hvert dokument, der er tidsstemplet. Træets rod offentliggøres derefter på et velkendt sted, det kunne f.eks. udskrives i en rubrikannonce i New York Times . Du kan bevise, at dit dokument eksisterede på den pågældende dag ved at vise, at dit dokuments fingeraftryk var nødvendigt for at generere det fingeraftryk-af-fingeraftryk, der stod i avisen.

Andre virksomheder og endda US Postal Service har siden oprettet deres egen elektroniske tidsstempeltjeneste. Men alle disse systemer er afhængige af en organisation, der fungerer som en betroet tredjepart, der i realiteten signerer dit dokument ved hjælp af deres private nøgle. Problemet med denne tilgang er, at tredjeparten skal være fuldstændig troværdig: hvis denne tredjepart beslutter sig for at oprette en signatur med den forkerte dato, eller en hacker formår at stjæle tredjepartens private nøgle, er der ingen måde at fortælle en svigagtig signatur fra en gyldig. Det er selvfølgelig også muligt at oprette svigagtige kautionssignaturer, men du skal enten gå tilbage i tiden og ændre det, der blev udskrevet i New York Times , ellers rejs over hele verden, find hver kopi, der blev udskrevet, og skift det gamle fingeraftryk-af-fingeraftryk til det nye.

Sådan fungerer Hash-funktioner

Så derfor er hash-funktioner nyttige. Lad os nu se, hvordan de rent faktisk ser ud.

Blandt de mest udbredte hash-funktioner i dag er den såkaldte MD5 (til Message Digest #5). MD5 producerer en hash, der er 128 bit lang, og som almindeligvis skrives som en sekvens af 32 hexadecimale (base 16) cifre. Hvis du skulle tage mit navn og behandle det med MD5, ville du få denne tilsyneladende tilfældige streng:

c55bbe0f3ba258f5b1cb6d5b62b0b360

Eller for at sige det med mere matematisk formalitet:

MD5(Simson Garfinkel)= c55bbe0f3ba258f5b1cb6d5b62b0b360

Hvert af disse hexadecimale tegn repræsenterer 4 bit; MD5-værdien af ​​mit navn er faktisk:

1100010101011011101111100001111100111011101
000100101100011110101011011000111001011011011
0101011011101100010101100001011001101100000

De fleste mennesker arbejder med den hexadecimale repræsentation, fordi det er ret nemt at se to hashes og fortælle, om de er ens eller forskellige.

MD5 fungerer ved at dele filen op i masser af små stykker, og derefter tage hver af disse bidder og udføre hundredvis af matematiske operationer, der blander, inverterer, transponerer og på anden måde behandler bitsene til et uigenkendeligt rod. Ordet uigenkendeligt i denne beskrivelse er nøglen. Det grundlæggende krav til en god hash-funktion er, at det skal være umuligt at forudsige fingeraftrykket af en fil uden faktisk at gøre en indsats for at beregne, at fingeraftrykket ikke må være genveje. Hvis der var, kunne du muligvis køre hash-funktionen baglæns og oprette en fil, der havde en bestemt hash, for eksempel hash af en anden fil. Faktisk falder hele sikkerheden af ​​hash-funktioner fuldstændig fra hinanden, hvis det er muligt at generere to filer, der har samme hash.

Det smukke ved hash-funktionen er, at selv en lille ændring af inputtet producerer en dramatisk ændring i outputtet. Matematisk er funktionerne designet således, at hver bit i outputtet vil have 50 procents chance for at ændre sig for hver eneste bit, der ændres i inputtet.

Lad os se på en anden MD5-hash, denne af en lidt anderledes repræsentation af mit navn:

MD5(Simson L. Garfinkel)= df876e8e6f548d5be698fab7f06dd278

Blot at tilføje L. giver en helt anden hash. Hvis du sammenligner de to hashes bit-for-bit, vil du opdage, at 63 ud af de 128 positioner er ændret fra en 0-til-1 eller en 1-til-0, og de andre 65 er forblevet uændrede.

Desværre har hele teorien om kryptografiske hashfunktioner et kæmpe problem. Brugen af ​​disse funktioner kræver, at der ikke er såkaldte kollisioner. Enten ved et uheld eller med vilje, bør der ikke være to filer, der har det samme kryptografiske fingeraftryk. Og som det viser sig, er dette et umuligt krav.

Årsagen er ret simpel. Filfingeraftryk er en fast størrelse, hvilket betyder, at der er et begrænset antal mulige fingeraftryk. Filer, på den anden side, kan være enhver størrelse. Der er således flere mulige filer end fingeraftryk, og der skal derfor være mindst ét ​​fingeraftryk, der er fingeraftrykket af flere filer. Den matematiske betegnelse for dette er duehulsprincippet. Faktisk, selvom du begrænser dig til filer, der kun er ni tegn lange, er der stadig 256 gange antallet af mulige filer som antallet af mulige fingeraftryk.

Grunden til, at duehulsprincippet ikke gør hash-funktioner fuldstændig meningsløse, er, at der faktisk er et forbløffende antal mulige fingeraftryk langt flere end antallet af filer på planeten. (Med MD5 er der 2128 mulige fingeraftryk. Nu er det samlede antal computerharddiske, der nogensinde er blevet fremstillet, kun omkring 229. Hvis hver harddisk havde en million unikke filer en grov overvurdering, ville der stadig kun være 249 individuelle filer. Det er meget , meget, meget mindre tal end 2128.)

SHA-1-kontroversen

Til vejledningsformål har jeg brugt MD5 hash-funktionen. Men i disse dage overvejes MD5 passere i stedet flytter det meste af verden over til de amerikanske regeringers Secure Hash Algorithm, kendt som SHA-1, en standard vedtaget af National Institutes of Standards and Technology (NIST) tilbage i begyndelsen af ​​1990'erne.

I dag er SHA-1 en bredt respekteret algoritme, men den har en problematisk historie. Tilbage i 1993 forsøgte den amerikanske regering at få industrien til at vedtage det såkaldte Clipper Chipa hemmelige krypteringssystem designet af National Security Agency. Under de såkaldte kryptokrige, der rasede omkring Clipper, foreslog NIST, at den amerikanske regering skulle vedtage sin egen Secure Hash Algorithm som en del af Federal Information Processing Standards. Af tekniske årsager bør hash-funktioner have dobbelt så mange bits som de krypteringsalgoritmer, de arbejder med. Clipper var en 80-bit krypteringsalgoritme, så standarden blev designet til at producere et 160-bit fingeraftryk.

Man kunne tro, at regeringens standard med sit 160-bit fingeraftryk ville være mere sikker end 128-bit MD5. Men ligesom Clipper selv, blev SHA designet af National Security Agency, og både NIST og NSA afviste at forklare de principper, der blev brugt i dets design. Nogle mennesker spekulerede på, om NSA kunne have gemt en slags bagdør inde i algoritmen, så agenturet kunne generere kollisioner efter behov. Sådan en bagdør kunne for eksempel bruges til at producere falske digitale signaturer, noget som Central Intelligence Agency kan finde nyttigt. En falsk digital signatur kan for eksempel bruges til at underskrive en elektronisk ordre, der giver en amerikansk spion adgang til en database i et fremmed land.

Masser af kryptografer og andre akademikere analyserede SHA-algoritmen og kunne ikke finde noget galt med den. Den 11. maj 1993 proklamerede NIST SHA som nationens Secure Hash Algorithm. Men blækket var knap tørt på dette dekret, da NIST meddelte, at det havde begået en fejl. Af årsager, der ikke ville blive afsløret på det tidspunkt, udgav NIST en modificeret version af Secure Hash Algorithm, algoritmen, som vi nu kalder SHA-1.

Konspirationsteoretikerne i kryptografisamfundet (og der er mange) havde en feltdag. Var SHA så magtfuld, at NSA havde besluttet, at den skulle dæmpes? Eller havde NSA måske plantet en bagdør i SHA, og nogen på NIST havde fundet ud af det? Var begge algoritmer lige sikre, og kryptograferne hos NSA rodede bare med folks sind?

I august 1998 lærte verden mere eller mindre svaret på SHA vs. SHA-1 mysteriet. Florent Chabaud og Antoine Joux, to franske kryptografer, kom med et teoretisk angreb mod den første version af SHAan-angrebet, som SHA-1 tilfældigvis var sikker mod. Næsten helt sikkert vidste folk hos NSA om dette angreb og foreslog SHA-1 som en modforanstaltning. Det interessante her er, at NSAs kryptografer sandsynligvis ikke vidste om angrebet, da SHA først blev foreslået i 1993, hvilket betyder, at verdens førende kryptografiske agentur kun var fem år foran kryptograferne i den akademiske verden.

I dag bruges hash-funktioner også almindeligvis til at generere gentagelige, men uforudsigelige tilfældige tal, til at konvertere indtastede adgangskoder til værdier, der er egnede til brug som krypteringsnøgler. I stedet for at gemme adgangskoder direkte, gemmer mange computersystemer hashen af ​​en adgangskode. Dette forhindrer nogen, der bryder ind på en computer, i at lære alles adgangskode.

Hash-funktioner er blevet foreslået som en måde at bekæmpe spam på og som grundlag for digitale pengesystemer. Matematiker Peter Wayner udgav en bog kaldet Gennemsigtige databaser for et par år siden, hvor han viste, hvordan hash-funktioner kunne bruges til at gemme information i en database på en måde, der er beskyttet af den organisation, der kører databasen. En optagelsesafdeling kan for eksempel gemme studerendes cpr-numre i databasen, så disse numre stadig kan bruges som identifikatorer på ansøgninger, men så ingen på optagelseskontoret kunne sætte sig ned ved en terminal og få en liste over studerende og deres numre. Indtil videre er ingen af ​​disse tilgange dog rigtig kommet i gang.

Alt i alt er kryptografiske hashes en af ​​de mest interessante og nyttige matematiske teknikker, som kryptografer har fundet på i løbet af de sidste 20 år og stadig fandt nye anvendelser for dem hele tiden.

skjule