Etikettarkiv: SHA-256

Wired gräver efter Bitcoins med hårdvara

(Uppdaterad med länk till artikel om KNCminer.)

I en kommentar till en tidigare postning om bitcoins pekade Robert Andersson på en artikel hos Wired. Wired testar just nu en dedikerad Bitcoin-grävare från Butterfly Labs.

Butterfly Labs Bitcoin-grävare
Butterfly Labs Bitcoin-grävare. En snygg liten maskin.

I artikeln sätter Wired fingret på ett viktigt fenomen med Bitcoin – att det blir svårare och svårare att gräva efter bitcoins. I början räckte det med en vanlig dator. I dag krävs det massiva system av datorer, helst utrustade med kraftiga grafikprocessorer.

Därmed går kostnaden för att gräva upp – både att anskaffa utrustningen och att driva utrustningen, i första hand energiförbrukning. Ett sätt att minska den rörliga kostnaden är att använda allt mer effektiv, dvs specialiserad hårdvara. Det finns i dag både FPGA- och ASIC-baserade bitcoingrävare (Wireds maskin från Butterfly Labs är en sådan maskin). Gizmodo har en artikel som visar lite hur Bitcoin-utrustningen har utvecklats på några få år. Den här gamla utrustningen är inte längre speciellt konkurrenskraftig:

Galet stor Bitcoinmaskin
En system för att gräva Bitcoins som borde ge sysadmin magsår.

Några som håller på och utvecklar FPGA-baserade bitcoingrävare är svenska KnCMiner. Daniel Goldberg och Linus Larsson har skrivit en mycket intressant om KnCMiner och deras maskiner.

Men vad göra för att vara mer effektiv än system med specialiserade Bitcoin ASIC:ar? Lägga kostnaden på någon annan. Tyvärr börjar det dyka upp flera tecken på att Botnets används även för att gräva efter Bitcoins. Tidigare i år fick ett Botnet kallat ZeroAccess gräver efter Bitcoins med hjälp kapade datorer. En synnerligen tråkig om än egentligen inte oväntad utveckling med Bitcoins.

Sedan påpekar Wired och Robert att hela systemet med Bitcoins bygger på säkerheten hos hashfunktionen SHA-256. Och så är det, om vi snabbt kan forcera SHA-256 kommer Bitcoin-systemet att kollapsa. Men då har vi troligen större problem med den digitala säkerheten i vårt samhälle och på Internet än att en digital valuta faller samman.

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.

Kollision hittad i MD5-meddelande

(Uppdaterad 2012-01-03 med korrektur)

2010 publicerade säkerhetsforskarna Tao Xie och Dengguo Feng en artikel om att de funnit en kollision hos hasfunktionen MD5 mellan två meddelanden som bara är ett block stort.

En kollision innebär att två olika meddelanden ner dom används som indata till en hashfunktion ger samma hashvärde. MD5, precis som andra kryptografiska hashfunktioner delar upp ett meddelande i ett antal block med en fix storlek. För MD5 är blockstorleken 512 bitar. Innan Xie och Fengs artikel hade det presenterats kollisioner för meddelanden som är större än ett block. Detta är enklare då det ger utrymme för att bygga på ett meddelande med bitmönster som gör att en kollision uppstår. Men för ett meddelande som är exakt ett block finns inte den möjligheten. En kollision på ett block kräver att hashfunktionens förmåga att skydda mot att räkna ut indata från ett givet hashvärde har brutits. Hashfunktionen är inte längre en evägsfunktion.

Xie och Feng presenterade i sin artikel två meddelanden på exakt 512 bitar som gav samma hashvärde:

Xie och Fengs kollision från 2010
Xie och Fengs kollision från 2010

Det Xie och Feng däremot inte gjorde var att berätta hur dom lyckats skapa sin kollision. Författarna hänvisar till att dom av säkerhetsskäl stoppats från att berätta hur dom gjort. Dom skriver:

Today, in the last month (Dec,) of 2010, we have to make public a result of our 1-block collision attacks on MD5 in Table 1 as below, which was actually
obtained at the beginning of 2010, but for security reasons, the techniques are not allowed to be disclosed at the moment.

Intressant nog utmanar istället Xie och Feng sina kollegor i världen att återskapa deras resultat genom att hitta ett annat par av meddelanden ned en storlek på ett block som ger en kollision i MD5:

Here, we are calling for a challenge to the cryptology community that, any one who first gives a new different 1-block collision attack on MD5 will win 10,000 US dollars (about 50,000 RMB in Chinese Yuan) as a reward for his (her) excellent work. This call for challenge will be ended on Jan 1st, 2013. This announcement’s first affiliated unit will be responsible for this amount of reward when a new different 1-block collision attack is received and verified.

Det som hänt nu är att Marc Stevens ser ut att vara den första att möta utmaningen. I en artikel publicerad 29 januari i 2012 presenterar Marc sina meddelanden och den kollision som detta ger:

Marc Stevens meddelanden som ger kollision i MD5
Marc Stevens meddelanden som ger kollision i MD5

Det första man kan lägga märke till är att det är andra meddelanden är de Xie och Feng använt. Notera även att det är två ställen i meddelandena som skiljer. I den första av dessa bytes är det bit två som växlat, 0x00 har blivit 0x02. I den andra byten är det bit åtta som växlat, 0x55 har blivit 0xd5.

Till skillnad från Xie och Feng tvekar inte Marc att berätta hur han gjort och i artikeln finns en redovisning av såväl bakomliggande teori och mekanismer samt den algoritm som Marc använt för att utföra sökningen av kollisionen. Enligt Marc skulle det med hans nya metod krävas 2**49.81, dvs ungefär 987 biljoner MD5-operationer för att hitta en kollision. Marc skattade att detta skulle ta maximalt fem veckors körtid, vilket innebär at han räknade med att kunna göra drygt 300 miljoner MD5-operationer per sekund. Detta var tillräckligt lite tid för att Marc skulle bedöma det som rimligt och startade därför sökningen. Med lite tur fick han träff efter tre veckor.

Skälet till att Marc lyckades och att MD5 är så svag är att lavineffekten hos MD5 är för svag och ojämnt fördelad över bitarna i det genererade hashvärdet. Lavineffekten innebär att en liten förändring av indata snabbt ska påverka många bitar i interntillståndet som i slutändan ger hashvärdet. Eller omvänt, varje bit i det genererade hashvärdet ska bero av många bitar i meddelandet. I fallet att meddelandet är lika stort som hashfunktionen innebär detta att varje bit i hashvärdet ska bero av många bitar i blocket. Tyvärr gäller inte detta för MD5. På grund av att den har så få iterationer sker inte en bra och jämn mixning. Vissa bitar i hashvärdet hos MD5 beror av väldigt få bitar. Detta kallas för en hashtunnel, ett begrepp och fenomen Vlastimil Klima presenterade 2006. Skillnaden i hur lavineffekten förklarar även den större varians jag fick för MD5 när jag gjorde bittester av hashfunktioner.

För den som själv vill pröva på att generera kollisioner hos meddelanden på enstaka block hos MD5 har Marc släppt ett program. Källkoden har Marc ännu inte släppts. Men koden, programmet, artikeln, meddelandena etc finns på Marcs egen sida.

Så vad är kontentan? Det första är att Xie och Fengs tävling har avgjorts och att Marc Stevens är att gratulera till ett bra utfört arbete. Förhoppningsvis får nu Xie och Feng chans att publicera information om hur dom gick tillväga. Att tvinga dom att hålla sin metod hemlig gav ett knappt års fördröjning av en publicerad metod. Att hemlighålla information om svagheter som ändå redan är kända har återigen visat sig inte vara en långsiktigt hållbar. Och någon får dessutom betala 10.000 USD.

För oss alla andra är väl detta bara ännu ett bevis på att MD5 inte skall användas och bör fasas ut till förmån för bättre hashfunktioner (exempelvis SHA-256). SHA-256 har inte bara fler iterationer och en bättre mixningsfunktion, den har även ett hashvärde på fler bitar – 256 bitar gentemot 128 bitar för MD5. Hashvärdet för MD5 är i dag så kort att det är inom gränsen för att praktiskt göra uttömmande sökningar och bygga upp tabeller med meddelanden och deras hashvärden, så kallade regnbågstabeller.