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.

3 reaktioner på ”Nytt sätt att optimera SHA-1

  1. Visst är det fräckt. Grejen är att det inte är första gången någon gjort liknande saker. Tunnlarna i MD5 som gjorde attackerna mot den algoritmen mycket mer effektiva är ungefär samma sak, men där var det dominerande värden i logiska operationer (typ nolla som en operand i AND gör andra operanden irrelevant).

    Att göra operationanalys på utrullad algoritm borde vara självklart. Kan man tycka.

  2. I somras när det framkom att MS-CHAPv2 inte ger 128 bitars säkerhet som alla trodde utan bara 56 bitar (https://www.cloudcracker.com/blog/2012/07/29/cracking-ms-chap-v2/), då hade jag svårt att förstå varför ingen hade kommit på en så uppenbar grej tidigare. Jag tänkte att alla kryptologer kanske hade avfärdat MS-CHAPv2 sedan länge och inte brydde sig om att analysera algoritmen mer eftersom den hade nog så allvarliga kända svagheter. Någon sådan förklaring håller inte i det här fallet. SHA-1 måste väl kryptologerna ändå ta på allvar.

    Man undrar vilka andra svagheter i våra populäraste kryptoalgoritmer som ligger och väntar på att någon ska komma på tanken att titta efter dem – och kanske redan är kända inom diverse spionorganisationer.

Kommentera

E-postadressen publiceras inte. Obligatoriska fält är märkta *