Kraken sha-1 kan veel goedkoper dan gedacht met gpu's

Een team van cryptologen, waaronder de Nederlander Marc Stevens van het CWI, heeft aangetoond dat de sha-1-standaard efficiënt gebroken kan worden met gpu's. Voor een geslaagde collision-aanval zou een relatief laag bedrag van zo'n 100.000 euro volstaan, schatten ze.

Dat is aanzienlijk lager dan een paar jaar geleden werd voorspeld en de cryptoanalisten dringen er dan ook op aan de standaard versneld uit te faseren. "We hebben de binnenste laag van sha-1, de compressiefunctie, gebroken met gpu's", vertelt Stevens van de Cryptology Group Centrum Wiskunde & Informatica aan Tweakers.

Hoewel dat geen volledige aanval is, is het fundament nu onder de standaard vandaan. "Als je een collision voor sha-1 wilt vinden, moet je ook een collision voor de compressiefunctie vinden. Het is nog net iets moeilijker maar we kunnen met deze bouwstenen een volledige aanval uitwerken", zegt Stevens. De cryptoloog voerde zijn freestart collision-aanval uit in samenwerking met Pierre Karpman van Inria uit Frankrijk en Thomas Peyrin van NTU Singapore.

Sha-1 is een hashing-algoritme uit 1995 dat nog altijd veel gebruikt wordt voor de verificatie van de ssl/tls-beveiliging van onder andere online transacties en inlogverbindingen en voor het ondertekenen van software. De beveiliging berust erop dat een invoer tot een enkele specifieke uitvoer, de hash, leidt en dat het extreem lastig is een tweede invoer te vinden die tot dezelfde uitkomt leidt. De mogelijkheid tot een collision of botsing ondermijnt dat: een aanvaller kan dan de digitale handtekening op basis van zijn eigen invoer vervalsen, waardoor de integriteit van een verbinding of code niet meer gegarandeerd kan worden.

Om een botsing te berekenen is veel rekenkracht en daarmee geld nodig, maar het onderzoek van Stevens toont aan dat de kosten relatief laag kunnen blijven. Bij collision-aanvallen werden tot nu toe vooral cpu's aan het werk gezet: het rekenwerk leunde sterk op bijvoorbeeld branche instructions en andere taken waar cpu's goed in zijn. Stevens heeft echter zijn eigen aanvalsmethode uit 2013 zo geoptimaliseerd dat nu ook efficiënt van de parallelle rekenkracht van gpu's gebruikgemaakt kan worden.

Hij gebruikte bij zijn onderzoek het Kraken-cluster met 16 nodes, elk bestaande uit vier Nvidia GTX 970-kaarten, een Core i5-4460 van de Haswell-generatie en 16GB ram. "Met 512 grafische kaarten is een volledige aanval in enkele maanden uit te voeren, bij 1000 kaarten daalt dat tot enkele weken", zegt Stevens. "Zoveel onderdelen zijn nog steeds erg duur maar je kunt ook online rekenkracht van Amazons EC2 huren. Volgens onze berekening ben je dan tussen 75.000 en 120.000 dollar kwijt om de standaard in enkele maanden te kraken."

Beveiligingsexpert Bruce Schneier kwam in 2012 tot de schatting dat de kosten van een volledige sha-1 aanval dit jaar op ongeveer 700.000 dollar en in 2018 op 173.000 dollar zouden uitkomen. Dit laatste bedrag was toen volgens hem laag genoeg voor criminelen om daadwerkelijk in te zetten. 

Stevens en de andere leden van het internationale team doen daarom een dringend beroep op het CA / Browser Forum om de uitgifte van sha-1-certificaten niet met nog een jaar te verlengen. Het forum stemt daar volgende week over en de discussie hierover sluit op 9 oktober. Volgens Stevens is de sfeer door zijn onderzoek al omgeslagen en is in ieder geval Google voorstander van het vervroegd staken van de ondersteuning. 

Sha-1 is een 160bit-hashfunctie. Onderdeel van de sha-2-familie zijn onder andere sha-256 en sha-512. Met opvolgers sha-2 en de net nieuwe standaard sha-3 kunnen we nog jaren vooruit, verwacht Stevens: "Die bevatten fundamentele wijzigingen, respectievelijk een volledig ander ontwerp. Die standaarden bieden meer dan genoeg weerstand tegen de huidige aanvallen."