Etikettarkiv: SHA-1

Nytt sätt att optimera SHA-1

I december anordnades i norge en konferens om lösenordsknäckning. På konferensen visades bland annat en maskin med 25 GPU:er som kan pröva nästan 400 miljarder NTLM-lösenord per sekund.

GPU-monstret.
Racklåda med 25 AMD Radeon-GPU:er.

Än mer intressant anser jag dock är den presentation som lösenordsknäckaren Hashcats skapare Jens Steube höll om optimering av hashfunktionen SHA-1 (PDF). Jens har analyserat hur de resultaten från de operationer som SHA-1 består av faktiskt används genom algoritmens 80 iterationerna. Det han insett är att flera av XOR-operationerna som sker vid expansion av indatablocket tar ut varandra. Genom att rulla ut iterationerna och eliminera de operationer som tar ut varandra lyckas Jens minska totala antalet operationer i SHA-1 med 21%(!).

Bilden visar hur Jens optimerat SHA-1
Optimerad expansion i SHA-1

Naturligtvis innebär det att Hashcat och andra lösenordsknäckare nu kan attackera SHA-1-baserade lösenord mycket snabbare, vilket är det som uppmärksammats i media (se ex den här artikeln eller den här artikeln). Men jag tycker resultatet är intressant i sig. SHA-1 publicerades 1995 och har implementerats, använts och analyserats intensivt genom åren. Att ingen innan 2012 insett att det finns en redundans på 21% är förvånande och nästan osannolikt.

Resultatet innebär att implementationer av SHA-1 kan göras mer kompakta och snabbare. Samtidigt innebär resultatet att SHA-1 blir lättare att attackera och NIST med flera organisationer rekommenderar sedan tidigare att inte använda SHA-1 för nya produkter och tjänster, utan att istället byta ut SHA-1 mot algoritmer som SHA-256 som ger bättre säkerhet. Dock blir skillnaden i prestanda mellan SHA-1 och SHA-256 i och med Jens resultat än större.

För den som vill testa finns Jens kod för att skapa optimerade operationer att ladda ner.

Testa lösenord via Twitter

Twitter är på många sätt en fantastisk tjänst. En av de bättre är hur enkelt det är att via Twitters programmeringsgränssnitt koppla program och maskiner som kan lyssna på tweets, skicka status och reagera på kommandon.

En sådan tjänst är Hash Cracking Robot. Detta är en tjänst som lyssnar på tweets riktade till sig som innehåller ett kryptografiskt kondensat skapat med olika typer av algoritmer såsom MD5, SHA-1, RIPEMD-160, WHIRLPOOL m.m.

Så här ser det ut när jag testar tjänsten genom att generera kondensat med MD5 för två olika strängar med OpenSSL.

Strängar för test av PlzCrack
Strängar för test av PlzCrack

Sedan postar jag strängarna riktade till @PlzCrack på Twitter (notera att postningarna är i omvändning ordning.):

Test av hashknäckning med Twitter
Test av hashknäckning med Twitter

Lägg märke till vad som händer. PlzCrack svarar mycket snabbt. Men det är bara strängar den känner till den kan knäcka rapportera. Egentligen är tjänsten en Twitterkoppling till regnbågstabeller. Detta innebär att det bara är strängar den känner till och har kondensat för som den kan hitta. Att skicka något till PlzCrack startar inte ett automatiskt försök att uttömmande söka efter en sträng som ger kondensatet, utan det är ren uppslagning i en tabell.

Twitter begränsar hur många tweets man kan göra inom en viss tidsperiod så att använda tjänsten för att testa en stor mängd kondensat går inte. Tjänsten är mer skoj och har nog ett rätt begränsat värde, men en fördel med PlzCrack är att du slipper att själv ha gigantiska regnbågstabeller eller att generera dessa tabeller. Sedan kan man fundera på hur bra det är att på ett bublikt forum leta efter strängar till kondensat…

Prestandatester av hashfunktioner

Den senaste tiden har jag tittat en del på prestanda och beteende hos olika kryptografiska hashfunktioner. OpenSSL innehåller funktioner och kommandon (kommandot speed) för att utföra prestandatester på den plattform dom körs. Maskinen jag kör på är utrustad med en 2.7 GHz Intel Core i7 och kör ett 64-bitars operativsystem. Den testade versionen av OpenSSL är 0.9.8r. När jag testar på min huvudmaskin får jag följande resultat:

Resultat från prestandatest av OpenSSL
Resultat från prestandatest av OpenSSL

Som förväntat är MD5 snabbast, tätt följt av SHA-1. Men en sak värd att lägga märke till är prestandan för SHA-2-funktionerna SHA-256 och SHA-512. För alla andra testfall än 16 Bytes data är SHA-512 snabbare. Detta kan tyckas underligt, om man tänker sig att göra avvägning mellan prestanda och säkerhet – att SHA-512 ger högre säkerhet till priset av prestanda. SHA-512 utför även 80 iterationer för att bearbeta ett datablock, och SHA-256 bara 64 iterationer. Men SHA-512 använder 64-bitarsoperationer och arbetar på större block än SHA-256 – 128 Bytes kontra 64 Bytes. Detta gör att SHA-512 på en maskin som min blir effektivare.

NIST, organisationen som specificerat SHA-2 (och SHA-1 samt arbetar med att ta fram SHA-3) har insett detta och presenterade i början av 2011 en ny version av specifikationen FIPS 180. Detta dokument specificerar SHA-1 och SHA-2. I den nya versionen finns det två nya funktioner – SHA-512/224 och SHA-512/256. Precis som SHA-384 är dessa funktioner SHA-512, men där det genererade hashvärdet kapas av till den bitstorlek som önskas. Använder du SHA-256 och har prestandaproblem kan det därför vara värt att titta SHA-512/256 på dessa funktioner.

Notera att SHA-384, SHA-512/224 och SHA-512/256 inte är exakt samma funktion som SHA-512. Det som skiljer är initialvärdena i interntillståndet. Dvs att implementera SHA-512/256 kräver lite mer än att köra med SHA-512 och kasta bort den högra halvan av hashvärdet. Koden i implementationen måste ändras, om än i liten grad.

För den som vill titta närmare på prestandan hos många olika hashfunktioner inklusive finalisterna i SHA-3-tävlingen finns det massor med data hos EU-projektet eBASH.