Varning: Den här guiden är fortfarande under utveckling, och kan innehålla fel. aliceochbob.se 11 juli 2008.
Bob har läst boken Handbook of Applied Cryptography. Här är en sammanfattning vad Bob har lärt sig.
Teori om kryptering
Eftersom kryptering är något som brottslingar använder i hollywoodfilmer och tv-serier har det spridits en hel del felaktig information om vad som exempelvis går och inte går att knäcka. Organisationer som FRA eller NSA är dock lika begränsade till fysikens lagar som oss andra och det här kapitlet kommer därför att handla om säkerheten hos kryptering.
Det finns två olika typer av krypteringsalgoritmer. Den ena typen kallas för symetrisk. Anledningen är att samma lösenord används både för att kryptera och avkryptera. Detta är vad folk vanligtvis tänker på när de hör ordet kryptering. Algoritmen krånglar till en text så den blir oläslig och enbart den som känner till nyckeln/lösenordet kan läsa texten. Att få en intuitiv förståelse om svårigheten att knäcka symetriska krypton är ganska enkelt.
Den andra typen kallas för asymmetrisk. Två olika lösenord används för att kryptera och avkryptera. Asymmetriska krypton använder svåra matematiska problem för att vara säkert. Att få en intuitiv förståelse om hur svårt dessa krypton är knepigare.
Generellt kan man säga att symetriska krypton används överallt där det finns kryptering, medan asymmetriska krypton används för att inleda säker kommunikation över Internet (när den inledande kommunikationen är igång brukar ett slumpvalt lösenord genereras sedan sker resten av dataöverföringen med ett symetriskt krypto). Asymmetriska krypton används i PGP, SSL, SSH etc.
Knäcka symmetriska krypton
Exempel på symmetriska algoritmer är DES, AES, Twofish, Serpent, Blowfish m.fl. När man pratar om dessa krypton pratar man samtidigt om hur många möjliga lösenord det finns att välja mellan. DES är ett 56 bit-krypto. Det innebär att det finns 2^56 lösenord totalt. Alla dessa lösenord kallas för ett ”key space”. Om en attackerare vill läsa en text krypterad med DES men inte vet lösenordet måste han testa alla 72 057 594 037 927 936 möjliga lösenord tills han hittar rätt. Om lösenordet är slumpmässigt tar det i medel hälften så lång tid att hitta rätt.
Många av de 2^56 lösenorden går dock inte att skriva på vanliga tangentbord. Om lösenordet bara består av tecknena a-z och är 8 tecken långt finns det enbart 26^8 (208 827 064 576) att välja mellan, detta är ett begränsat key space. Attackeraren kanske dessutom antar att den som krypterat är klantig/lat och har använt ett svenskt ord som lösenord. Det finns bara ungefär 90 000 ord i SAOL.
Att knäcka ett krypto genom att successivt testa alla möjliga lösenord kallas för en brute force-attack. Det kan vara bra att veta hur mycket datorkraft som krävs för att gå igenom en viss mängd potentiella lösenord. När man vet det kan man få en bra förståelse hur långt ett lösenord måste vara om det ska vara säkert, och hur många olika typer av tecken (små bokstäver, stora bokstäver, siffror etc) som måste användas.
Symmetriska krypton brute-forcas bäst på specialdesignad hårdvara. FRA har nyligen köpt en superdator som är den femte kraftfullaste i världen. Den datorn består dock av vanliga x86-processorer (fast väldigt många). Närmare bestämt består FRA:s dator av ungefär 4000 Xeonprocessorer, som inte är mycket kraftfullare än Intels konsumentprocessor Core 2 Quad som kan köpas i butik för ungefär 1700 kr styck. Många personer som läser detta har förmodligen speldatorer som är kraftfullare än noderna i FRA:s dator. Men som sagt, FRA har över 4000 stycken sådana, och tillsammans är detta ganska kraftfullt.
Hur bra är då denna dator på att knäcka symmetriska krypton? Nu har ju jag inte några officiella uppgifter från FRA själva men det är inte svårt att uppskatta eftersom burken använder så vanlig hårdvara. Den som är intresserad kan exempelvis skriva ett eget program som brute-forcar AES. Då kan man få en förståelse hur många lösenord per sekund sin dator kan testa.
Jag skrev ett sådant program som jag körde på min Pentium 4 på 2.4 GHz. Med en lättillgänglig AES-implementation kan programmet testa strax över en miljon nycklar per sekund. Nu måste vi dock komma ihåg att detta program inte är optimerat: FRA har förmodligen en snabbare AES-implementation. Programmet är dessutom kört på en dator med Windows installerat: FRA har inte en massa skräp som körs i bakgrunden på sina processorer. Trots detta kan programmet ge en uppskattning hur snabb FRA:s dator är.
För att vara snäll mot FRA kommer jag låssas att deras Xeon är en miljon gånger snabbare än min Pentium 4 att brute-forca AES-nycklar (en Core 2 Quad är fem gånger snabbare med programmet). Med 4000 sådana processorer kan datorn testa 4000*10^12 nycklar per sekund. I så fall gäller följande:
Att brute-forca 2^64 nycklar tar ungefär 1 timme.
Att brute-forca 2^128 nycklar tar ungefär 10^18 dagar.
Det finns en specialdesignad dator som heter COPACOBANA. Den kostar ungefär 10 000 dollar och kan gå igenom 2^56 nycklar på 12.8 dagar. Detta är dock versionen från 2007, det finns en nyare modell från våren 2008 som är mycket snabbare. Den gamla COPACOBANA kan testa ungefär 10^10 nycklar per sekund.
Det är dock ganska enkelt att se, att även om man skulle ta en miljon COPACOBANA skulle det fortfarande ta ungefär 10^17 dagar att gå igenom alla 2^128 nycklar som kan används av AES. Det är med andra ord hopplöst att brute forca 128 bit-krypton som AES (AES finns även i versioner med 192 eller 256 bit).
Vad som däremot inte är lika hopplöst är att endast brute-forcea sådana lösenord som går att skriva på tangentbordet. De flesta personer har förmodligen lösenord som är kortare än 12 tecken och enbart innehåller små bokstäver och siffror. Låt oss fortsätta det något överdrivna antagandet att FRA:s Xeon är en miljon gånger snabbare än min Pentium 4 och datorn totalt därför kan testa 4000*10^12 nycklar per sekund.
Det tar då enbart 25 sekunder att gå igenom alla lösenord från 1 till 12 tecken som enbart innehåller små bokstäver a-z. Om vi inkluderar siffrorna 0-9 tar det strax över 20 minuter. Blandar vi in både stora och små bokstäver är vi nu uppe i 9½ dag. Detta inkluderar även ganska bökiga lösenord som ”ij0wUAP8xhxn”.
Turligt nog blir det snabbt väldigt besvärligt att brute-forca när lösenorden börjar bli längre än 12 tecken. Om vi tar alla lösenord upp till 20 tecken som enbart innehåller a-z och 0-9 tar det plötsligt ungefär 10^10 dagar att gå igenom alla.
Räkna på brute-force
En sofistikerad attackerare vet dock att när personer väljer lösenord längre än ca 10 tecken brukar de ofta innehålla ord, eller meningar. Ett lösenord i stil med elvispresleyisnomore är förmodligen ”mer vanligt” än exempelvis yfirlbmowkmcctmaqkhc. Om attackeraren tror att lösenordet är uppbyggt av ord kan bättre attacker användas än att gå igenom alla möjliga kombinationer av enskilda tecken. Detta kallas för en ordboksattack eller dictionary attack på engelska.
Om vi tar en, två, tre eller fyra slumpmässiga ord från SAOL (90000 ord) och lägger dessa i rad tar det ungefär 4½ timme för FRA:s dator att testa alla. Igen vill jag dock poängtera att vår förutsättning om datorns prestanda är något överdriven, men detta duger ändå eftersom vi mest är intresserad av storleksordningar: eftersom detta exempel tar minuter och inte miljarder år bör dessa typer av lösenord undvikas.
Det kan tyckas vara väldigt besvärligt för en vanlig människa att hitta på ett bra lösenord som inte kan knäckas enkelt av snabba datorer. Turligt nog brukar program hjälpa en på traven för att motverka ordboksattacker. Programmet TrueCrypt gör detta. Lösenordet som man matar in i TrueCrypt används inte direkt utan transformeras på ett beräkningsintensivt vis till den riktiga nyckeln. För varje lösenord från ordlistan som testas måste tusentals extra beräkningar göras. Den som är mer intresserad av detta steg kan läsa en annan artikel jag skrivit som finns här: blog.bjrn.se. Den artikeln förklarar tekniskt hur TrueCrypt fungerar.
TrueCrypt har dessutom ett annat hjälpmedel och det är så kallade keyfiles. En keyfile är en vanlig fil som används som extra lösenord, som krävs för att avkryptera TrueCrypt-volymen. Attackeraren måste då testa inte bara lösenord utan även alla möjliga filer som skulle kunna användas som keyfile. Mer info om detta i TrueCrypt-dokumentationen.
Min rekommendation på lösenord är därför runt 20 tecken långa och innehåller så många olika typer av tecken (små bokstäver, stora bokstäver, siffror, ”specialtecken” som !”#¤%& och punkter, komman och annat).
Bortsett från brute force-attracker och ordboksattacker finns det andra metoder ett symmetrisk krypto kan attackeras. Det kanske finns en svaghet i algoritmen som gör att lösenordet kan listas ut utan att gå igenom alla möjligheter. Att hitta sådana svagheter är dock väldigt svårt: nästan alla svagheter som upptäckts om populära krypton som DES har involverat att attackeraren måste känna till väldigt mycket klartext (och motsvarande krypterad text).
Ett exempel är det gamla kryptot DES. Alla personer som studerat kryptering på högskola har lärt sig hur DES fungerar. DES har attackerats sedan 70-talet. Den bästa attacken hittills som är känd kräver 16 terabyte data i form av klartext och motsvarande krypterad text (krypterad med den hemliga nyckeln) för att lista ut nyckeln. Och om attackeraren har så mycket data behöver nog inte nyckeln listas ut ens, det finns tillräckligt mycket hemligheter att gå igenom som det är.
Den bästa metoden att gardera sig mot defekta kryptoalgoritmer är att använda välkända, publicerade algoritmer som många matematiker och krypteringsexperter försökt hitta problem med. Bra sådana algoritmer är AES, Serpent, Twofish. Undvik DES, den är för gammal och har för få nycklar, och kan därför brute forcas utan att själva algoritmen attackeras.
Knäcka asymmetriska krypton
Asymmetriska krypton är svårare att få en intuitiv förståelse om. Här snackar man inte om hur många möjliga lösenord det finns utan hur svårt det är att lösa olika matematiska problem.
Ett vanligt problem som många asymmetriska krypton baseras på är faktoriseringsproblemet. Detta kräver att vi repeterar lite högstadiematte: alla heltal kan konstrueras av mindre tal som multipliceras ihop. De minsta talen kallas för primtal och dessa kan inte konstrueras av mindre tal. En annan formulering är att ett primtal är sådana tal som inte är jämt delbara med andra tal (förutom 1 och sig själv).
Som exempel kan vi ta talet 200. Vi kan exempelvis skriva det som 2*100 och 100 kan vi skriva som 10*10 och 10 kan vi skriva som 2*5. 200 är därför 2*2*2*5*5. Vi kan inte bryta ner talet 200 mer än så. Vi säger att vi har faktoriserat 200 till faktorerna 2, 2, 2, 5 och 5.
Att faktorisera tal är ett så kallat ”svårt” matematiskt problem. Små tal som 200 är visserligen inte så svåra att faktorisera, det kan vi göra i huvudet. Det finns dock vissa typer av väldigt stora tal, som består av två väldigt stora faktorer, som är besvärliga. Detta kan utnyttjas på smarta vis för att skapa ett asymmetriskt krypto.
Om man pratar om symmetriska krypton och säger 128 bit menar man att det finns 2^128 möjliga lösenord. Om man pratar om asymmetriska krypton baserade på faktoriseringsproblemet menar man dock storleken på talet som ska faktoriseras. År 2005 lyckades ett gäng matematiker faktorisera följande tal:
27997833911221327870829467638722601621070
44678695542853756000992932612840010760934
56710529553608560618223519109513657886371
05954482006576775098580557613579098734950
144178863178946295187237869221823983
Det talet är 200 siffror långt, eller 663 bits. Vanligtvis (exempelvis RSA) används 1024 bit stora tal i krypteringssammanhang. Så hur säkert är 1024 bit tal? Hur faktoriserar man sådana snabbt?
Att multiplicera ihop två tal är enkelt, exempelvis är 727*997 = 724819. Att bryta upp ett tal i faktorer är väldigt mycket svårare. Om du enbart har talet 724819, vad ska du göra? Om du har väldigt mycket tid kan du börja med faktorn 2 och se om den jämt delar det stora talet N. Sedan testar du 3, 5, 7 etc. Den här metoden kallas för trial division och kräver om man har otur att man testar alla faktorer upp till och inklusive rotenur(N). Detta är för att i värsta fall är talet på formen p^2 och har därför faktorerna p och p. Trial division fungerar inte om talet är väldigt stort, och givetvis är talen väldigt stora i krypteringssammanhang.
Attackerare med mycket datorkraft faktoriserar inte med trial division utan med en algoritm som heter general number field sieve. Generellt kan man säga att det krävs minst en magisterexamen i matematik för att över huvud taget begripa hur den fungerar, men det gör den och snabbt. Jag tror att organisationer som FRA/NSA är mycket bättre på att faktorisera än vad som är känt inom allmänheten och akademiska kretsar. Det är för att dessa organisationer har råd att anställa matematiker som kan jobba heltid att förbättra gnfs, och det finns en del utrymme för förbättringar.
Matematikerna som faktoriserade det 200 siffror långa talet ovan använde gnfs på 80 stycken Opterondatorer @ 2,2 GHz och det tog ungefär 3 månader. Detta är dock tillräcklig information vi behöver för att uppskatta hur bra FRA är.
Nu kommer jag göra en hel del handvevande här, men som vanligt är vi enbart ute efter en uppskattning i magnituder (tar det dagar eller tar det längre tid än universums livslängd?).
Teoretiskt så krävs det ungefär 2.3*10^32 antal operationer för att faktorisera ett 663-bit tal med gnfs. Ett 1024-bit tal kräver 5 miljoner så många operationer. Med 4000 Opterons skulle det ta strax under 2 dagar istället för 3 månader att faktorisera talet. Opteronburkarna är dock långsammare än FRA:s Xeon, så vi säger att deras dator kan faktorisera talet på 1 timme. 1024-bit tal tar dock ändå 5 miljoner gånger så lång tid, eller två hundra tusen dagar. (Förresten: om du är bra på komplexitetsteori och har studerat gnfs närmre kan du slänga iväg ett epost till mig?)
Innebär detta att 1024 bit-tal är säkra mot FRA? Njae. Mattegänget som gav sig an det 200-siffriga talet är visserligen ambitiösa men de har begränsade resurser. Det finns en teoretisk maskin som heter TWIRL som skaparna (samma som skapade det asymmetriska kryptot RSA) uppskattar kan faktorisera 1024 bit stora tal på ett år. Maskinen skulle dock kosta några miljoner dollar att bygga.
Min rekommendation här är att 1024 bit-tal är tveksamt okej än så länge, men om du är paranoid kan du lika gärna köra 2048 bit. Det skadar ingen.
Bortsett från faktorseringsproblemet finns det många andra svåra matematiska problem som kan användas i krypteringsändamål. Några exempel är diskreta logaritmen och diffie-hellmanproblemet. Dessa problem är dock ganska ”lika” faktoriseringsproblemet. Gnfs kan exempelvis användas för diskreta logaritm-problemet och diffie-hellman kan göras om till diskreta logaritm-problemet.