Fingeravtryck dina filer

Tre kryptografer vid Stanford University kom nyligen med en smart lösning på det ihållande problemet med identitetsstöld på Internet. Slug hackare i Ryssland, Kina och andra länder skickar ut högar med e-postmeddelanden som ser ut som om de kom från någon finansiell institution som Citibank eller Paypal. Miljontals konsumenter får dessa meddelanden, som har inbäddade HTML-länkar i dem som tar den intet ont anande mottagaren till liknande webbplatser som körs på avlägsna platser. Du uppmanas att ange ett användarnamn och lösenord och sedan har hackaren nycklarna till ditt bankkonto.

Men bra användarnamn och lösenord som skrivs på dåliga webbplatser är inte det enda hotet som konsumenter möter. Ett potentiellt större problem är att många människor använder samma användarnamn och lösenordskombination på flera webbplatser. Detta gör det enklare att memorera, men det betyder att en skrupelfri webbplatsoperatör kan ta en lista med användarnamn och lösenord från till exempel en webbplats för utlottningar på Internet och använda den för att försöka bryta sig in på bankkonton online.

Så Stanfords kryptografer Blake Ross, Dan Boneh och John Mitchell har designat ett smart plug-in för Internet Explorer som löser det här problemet genom att förvränga det du skriver i lösenordsfältet så att varje webbplats ser ett annat lösenord och lösenord som både baseras på vad du skriver och på själva webbplatsens domän.

Nu använder många människor någon variant på denna strategi. Deras Hotmail-lösenord kan vara nosmis-hotmail medan deras Yahoo! Personals lösenord är nosmis-Yahoo! Men vilken strategi som helst som denna är ganska enkel att tyda. Lösenordskrypteringsmetoden som Stanford-trion har tagit fram är baserad på en matematisk funktion som kallas en kryptografisk hasha-typ av envägsfunktion som omvandlar det användaren skriver till ett virrvarr av siffror och bokstäver på ett sätt som inte går att vända om. Eftersom Stanford-systemet beräknar den kryptografiska hashen för både webbplatsens domän och användarens lösenord, får hackaren andra lösenord än de legitima. (Klick här för att hitta detaljer om denna smarta lösning.)

Ett företag som använder kryptografiska hash på ett mycket offentligt sätt är Yahoo! Förra året, Yahoo! designade om inloggningsprocessen till sin webbplats för att göra den sniffsäker. Det vanliga sättet att göra detta är att använda kryptering. Men kryptering kan vara långsam, särskilt när du kör en av de mest populära webbplatserna på Internet.

Så vad Yahoo! gjorde istället var att modifiera sin inloggningssida för att använda ett så kallat challenge-response-system baserat på en kryptografisk hash. När du försöker logga in laddar Yahoo!s server ner en kryptografisk hashfunktion skriven i JavaScript till din webbläsare. Tillsammans med denna funktion finns en utmaning en kort sekvens av bokstäver och siffror. När du skriver ditt lösenord på inloggningsskärmen tar din webbläsare ditt lösenord, lägger till dessa tecken från Yahoo! och beräknar den kryptografiska hashen för den resulterande strängen. Webbläsaren skickar sedan det resulterande värdet tillbaka till Yahoo!, ingen kryptering behövs. Även om du är på ett cybercafé och får din webbtrafik sniffad av belgiska hackare, finns det inget sätt för skurkarna att ta det resulterande hashvärdet och härleda ditt ursprungliga lösenord.

Detta smarta utmaning-svar-system ligger också till grund för Mobil Speedpass-systemet: det är det som gör Speedpass-taggen för radiofrekvensidentifiering (RFID) så svår att klona. Andra RFID-system använder inte utmaningssvar, vilket gör det relativt enkelt att attackera dem.

Men vad är den här kryptografiska hashfunktionen egentligen?

Den otroligt användbara hashen

Kryptografiska hashfunktioner är en av de grundläggande byggstenarna i dagens digitala ekonomi. Ändå förblir de på många sätt ett mysterium både för kryptograferna som skapar dem och för allmänheten som använder dem varje dag.

Hash-funktioner kallas ibland fingeravtrycksfunktioner eftersom de kan användas för att skapa ett unikt fingeravtryck av en digital fil. Fingeravtrycken är vanligtvis 128-bitars eller 160-bitars nummer som visas som en sekvens av hexadecimala siffror. Fingeravtrycket för mitt namn som använder MD5-systemet, till exempel, är c55bbe0f3ba258f5b1cb6d5b62b0b360. Hash-funktioner är utformade så att åtminstone i teorin inte två filer någonsin kommer att hasha till samma värde.

Så att du kan få en uppfattning om hur dessa fingeravtrycksfunktioner fungerar, har vi bäddat in en JavaScript-baserad MD5-kalkylator nedan. Skriv bara in lite text så kan du se MD5-hash. Lägg märke till hur det förändras helt varje gång du lägger till, tar bort eller ändrar en bokstav. Sättet som fingeravtrycket ändras på är faktiskt oförutsägbart, om vi kunde förutsäga hur det förändras, så skulle filfingeravtryck inte vara särskilt användbara.

Skriv in din text nedan:

MD5 är:

De flesta hashfunktioner som används idag är baserade på en teknik som utvecklades av MIT-professorn Ron Rivest på 1980-talet. (Rivest är förmodligen mest känt för att vara R:et i RSA-krypteringsalgoritmen, den offentliga nyckelkrypteringsalgoritmen som är inbyggd i praktiskt taget alla webbläsare.) Vid den tiden arbetade Rivest och andra matematiker på detaljerna för de grundläggande kryptografiska operationerna som vi nu ta för givet. Hash-funktionerna föreställdes som ett slags kryptografiskt komprimeringssystem, ett sätt att ta en stor fil och krossa den till en kort sträng av bokstäver och siffror.

Tanken var att använda dessa fingeravtryck som ett slags surrogat för själva filerna. Istället för att digitalt signera hela filen, resonerade Rivest med flera, så kunde man digitalt signera hashen. Eftersom kryptografi med publik nyckel involverar mycket tung matematik, gör hashfunktioner det nästan lika snabbt att signera en extremt lång fil som att signera en kort fil.

En av de mest grundläggande sakerna du kan göra med en hashfunktion är att ta reda på om en fil har ändrats: beräkna bara hash för en fil och skriv ner den. Senare beräknar du hash igen. Om hashen inte har ändrats är oddsen överväldigande att filen inte heller har ändrats.

Säg till exempel att du håller ekonomin för ditt lilla företag med QuickBooks och att du vill åka på semester i några dagar: folk måste använda din dator men du vill se till att ingen ändrar QuickBooks-data. En enkel sak du kan göra är att beräkna filens kryptografiska hash innan du går och skriva numret på ett registerkort. När du kommer tillbaka från semestern är det bara att räkna om hashen. Om de två värdena inte stämmer överens vet du att filen har manipulerats.

Naturligtvis behöver du inte sluta med bara en fil. Du kan beräkna den kryptografiska hashen för varje fil på din dator och lägga in dem alla i ett nytt filecall som filen hashes.txt. Du kan sedan beräkna hashen för hashes.txt och skriva detta fingeravtryck på ditt anteckningskort. Upprepa processen när du kommer tillbaka från semestern så har du ett snabbt sätt att veta om någon fil på hela din dator har ändrats. (Du kommer inte att ha något sätt att veta vilken fil som har ändrats, men det är ett annat problem.)

Denna idé att beräkna hash för en hash är grunden för ett intrångsdetekteringssystem kallat Tripwire som Purdue Universitys datavetenskapsprofessor Gene Spafford och hans doktorand Gene Kim uppfann redan i början av 1990-talet. (Spafford och jag har varit medförfattare till fem böcker om datavetenskap.) Idag använder många olika program denna Tripwire-metod för att säkerställa integriteten hos datorfiler och databaser.

Att beräkna hash-haschar är också grunden för en säker tidsstämpeltjänst som uppfanns av Stuart Haber och Scott Stornetta medan de två var på Bellcore 1990. Tjänsten, kallad Surety, gör det möjligt att generera ett kryptografiskt säkert och oförglömligt bevis på att ett visst dokument , fotografi eller annan fil fanns vid en viss tidpunkt på ett visst datum och att den inte har ändrats sedan dess.

Säkerhetstekniken fungerar genom att beräkna ett hashträd baserat på hashkoderna för varje dokument som tidsstämplas. Trädets rot publiceras sedan på en välkänd plats, den kan till exempel skrivas ut i en hemlig annons i New York Times . Du kan bevisa att ditt dokument fanns den aktuella dagen genom att visa att ditt dokuments fingeravtryck behövdes för att generera det fingeravtryck-av-fingeravtryck som förekom i tidningen.

Andra företag och till och med US Postal Service har sedan dess skapat sin egen elektroniska tidsstämpeltjänst. Men alla dessa system är beroende av en organisation som fungerar som en pålitlig tredje part som i praktiken signerar ditt dokument med sin privata nyckel. Problemet med detta tillvägagångssätt är att tredje part måste vara helt pålitlig: om den tredje parten bestämmer sig för att skapa en signatur med fel datum, eller om någon hackare lyckas stjäla tredje parts privata nyckel, finns det inget sätt att berätta för en bedräglig signatur från en giltig. Det är naturligtvis också möjligt att skapa falska borgenssignaturer, men du måste antingen gå tillbaka i tiden och ändra det som skrevs ut i New York Times , eller res över hela världen, hitta varje kopia som har skrivits ut och ändra det gamla fingeravtrycket-av-fingeravtryck till det nya.

Hur hashfunktioner fungerar

Så det är därför hashfunktioner är användbara. Nu ska vi se hur de faktiskt ser ut.

Bland de mest använda hashfunktionerna idag är den så kallade MD5 (för Message Digest #5). MD5 producerar en hash som är 128 bitar lång och som vanligtvis skrivs som en sekvens av 32 hexadecimala (bas 16) siffror. Om du skulle ta mitt namn och bearbeta det med MD5, skulle du få denna till synes slumpmässiga sträng:

c55bbe0f3ba258f5b1cb6d5b62b0b360

Eller, för att uttrycka det med mer matematisk formalitet:

MD5(Simson Garfinkel)= c55bbe0f3ba258f5b1cb6d5b62b0b360

Vart och ett av dessa hexadecimala tecken representerar 4 bitar; MD5-värdet för mitt namn är faktiskt:

1100010101011011101111100000111100111011101
000100101100011110101011011000111001011011011
0101011011101100010101100001011001101100000

De flesta människor arbetar med den hexadecimala representationen eftersom det är ganska lätt att se två hashar och se om de är lika eller olika.

MD5 fungerar genom att dela upp filen i massor av små bitar och sedan ta var och en av dessa bitar och utföra hundratals matematiska operationer som blandar, inverterar, transponerar och på annat sätt bearbetar bitarna till en oigenkännlig röra. Ordet oigenkännlig i denna beskrivning är nyckeln. Det grundläggande kravet för en bra hashfunktion är att det ska vara omöjligt att förutsäga fingeravtrycket för en fil utan att faktiskt anstränga sig för att beräkna att fingeravtrycket inte får finnas några genvägar. Om det fanns, kanske du kan köra hash-funktionen baklänges och skapa en fil som hade en specifik hash, till exempel hash för en annan fil. Faktum är att hela säkerheten för hashfunktioner faller isär totalt om det är möjligt att generera två filer som har samma hash.

Det fina med hash-funktionen är att även en liten modifiering av ingången ger en dramatisk förändring i utdata. Matematiskt är funktionerna utformade så att varje bit i utgången kommer att ha 50 procents chans att ändras för varje enskild bit som ändras i ingången.

Låt oss titta på en annan MD5-hash, den här av en lite annorlunda representation av mitt namn:

MD5(Simson L. Garfinkel)= df876e8e6f548d5be698fab7f06dd278

Att bara lägga till L. ger en helt annan hash. Om du jämför de två hasharna bit för bit kommer du att upptäcka att 63 av de 128 positionerna har ändrats från en 0-till-1 eller en 1-till-0, och de andra 65 har förblivit oförändrade.

Tyvärr har hela teorin om kryptografiska hashfunktioner ett stort problem. Användningen av dessa funktioner kräver att det inte förekommer så kallade kollisioner. Antingen av misstag eller med avsikt bör det inte finnas två filer som har samma kryptografiska fingeravtryck. Och som det visar sig är detta ett omöjligt krav.

Anledningen är ganska enkel. Filfingeravtryck har en fast storlek, vilket innebär att det finns ett begränsat antal möjliga fingeravtryck. Filer, å andra sidan, kan ha vilken storlek som helst. Det finns alltså fler möjliga filer än fingeravtryck, och därför måste det finnas minst ett fingeravtryck som är fingeravtrycket för flera filer. Den matematiska termen för detta är duvhålsprincipen. Faktum är att även om du begränsar dig till filer som bara är nio tecken långa, finns det fortfarande 256 gånger antalet möjliga filer som antalet möjliga fingeravtryck.

Anledningen till att duvhålsprincipen inte gör hashfunktioner helt meningslösa är att det finns ett häpnadsväckande antal möjliga fingeravtryck, faktiskt, mycket fler än antalet filer på planeten. (Med MD5 finns det 2128 möjliga fingeravtryck. Nu är det totala antalet datorhårddiskar som någonsin har tillverkats bara runt 229. Om varje hårddisk hade en miljon unika filer en grov överskattning skulle det fortfarande bara finnas 249 enskilda filer. Det är mycket , mycket, mycket mindre antal än 2128.)

SHA-1-kontroversen

I handledningssyfte har jag använt hashfunktionen MD5. Men nu för tiden övervägs MD5 passera istället går större delen av världen över till de amerikanska regeringarnas Secure Hash Algorithm, känd som SHA-1, en standard som antogs av National Institutes of Standards and Technology (NIST) i början av 1990-talet.

Idag är SHA-1 en allmänt respekterad algoritm, men den har en orolig historia. Redan 1993 försökte den amerikanska regeringen få industrin att anta det så kallade hemliga krypteringssystemet Clipper Chipa designat av National Security Agency. Under de så kallade kryptokrigen som rasade kring Clipper föreslog NIST att den amerikanska regeringen skulle anta sin egen Secure Hash Algorithm som en del av Federal Information Processing Standards. Av tekniska skäl bör hashfunktioner ha dubbelt så många bitar som de krypteringsalgoritmer som de arbetar med. Clipper var en 80-bitars krypteringsalgoritm, så standarden designades för att producera ett 160-bitars fingeravtryck.

Man kan tro att regeringens standard, med sitt 160-bitars fingeravtryck, skulle vara säkrare än 128-bitars MD5. Men precis som Clipper själv designades SHA av National Security Agency och både NIST och NSA avböjde att förklara principerna som användes i dess design. Vissa människor undrade om NSA kan ha gömt någon form av bakdörr inuti algoritmen så att byrån kunde generera kollisioner på begäran. En sådan bakdörr kan till exempel användas för att producera falska digitala signaturer, något som Central Intelligence Agency kan ha nytta av. En falsk digital signatur kan till exempel användas för att underteckna en elektronisk order som ger en amerikansk spion tillgång till en databas i ett främmande land.

Massor av kryptografer och andra akademiker analyserade SHA-algoritmen och kunde inte hitta något fel med den. Den 11 maj 1993 utropade NIST SHA som nationens Secure Hash Algorithm. Men bläcket var knappt torrt på detta dekret när NIST meddelade att det hade gjort ett misstag. Av skäl som inte skulle avslöjas vid den tidpunkten publicerade NIST en modifierad version av Secure Hash Algorithm, algoritmen som vi nu kallar SHA-1.

Konspirationsteoretikerna i kryptografigemenskapen (och det finns många) hade en fältdag. Var SHA så mäktig att NSA hade bestämt att den måste fördummas? Eller hade NSA kanske planterat en bakdörr i SHA och någon på NIST hade fått reda på det? Var båda algoritmerna lika säkra och kryptograferna på NSA bara bråkade med folks sinnen?

I augusti 1998 lärde världen sig mer eller mindre svaret på mysteriet SHA vs SHA-1. Florent Chabaud och Antoine Joux, två franska kryptografer, kom med en teoretisk attack mot den första versionen av SHAan-attacken mot vilken SHA-1 bara råkade vara säker. Nästan säkert visste folket på NSA om denna attack och föreslog SHA-1 som en motåtgärd. Det som är intressant här är att NSAs kryptografer förmodligen inte visste om attacken när SHA först föreslogs 1993, vilket betyder att världens främsta kryptografiska byrå bara var fem år före kryptograferna i den akademiska världen.

Idag används hashfunktioner också ofta för att generera repeterbara men oförutsägbara slumptal, för att konvertera inskrivna lösenord till värden som är lämpliga att använda som krypteringsnycklar. Istället för att lagra lösenord direkt, lagrar många datorsystem hash för ett lösenord. Detta hindrar någon som bryter sig in i en dator från att lära sig allas lösenord.

Hash-funktioner har föreslagits som ett sätt att bekämpa spam och som grund för digitala kontantsystem. Matematikern Peter Wayner publicerade en bok som heter Genomskinliga databaser för några år sedan där han visade hur hashfunktioner kunde användas för att lagra information i en databas på ett sätt som skyddas av organisationen som driver databasen. En högskoleantagningsavdelning kan till exempel lagra studentpersonnummer i databasen så att dessa nummer fortfarande kan användas som identifierare på ansökningar, men så att ingen på antagningskontoret kan sätta sig vid en terminal och få en lista över studenter och deras antal. Än så länge har dock ingen av dessa tillvägagångssätt riktigt kommit igång.

Allt som allt är kryptografiska hash en av de mest intressanta och användbara matematiska teknikerna som kryptografer har kommit på under de senaste 20 åren och fortfarande hittade nya användningsområden för dem hela tiden.

Dölj