Etikettarkiv: optimering

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.