Succesvolle collisionaanval SHA-1 in zicht

Volgens een ruwe schatting van Intel Labs-medewerker Jesse Walker is het in 2018 haalbaar om betaalbaar een collisionaanval uit te voeren op SHA-1 hashes. Dat zou betekenen dat het tijd is om over te stappen op nieuwere hashing-algoritmes.

Beveiligingsonderzoeker Bruce Schneier meldt op zijn blog dat het niet lang meer zal duren voor het haalbaar wordt om met succes een aanval uit te voeren op het SHA-1-hashalgoritme. Hij citeert hierbij een mail van Jesse Walker, Principal Engineer bij de security-afdeling van Intel Labs. Zijn bericht verscheen op een mailinglijst van het National Institute of Standards and Technology.

Volgens een ruwe schatting van Walker kost de apparatuur voor een dergelijke aanval in 2012 nog zo'n 2,77 miljoen dollar. In 2018 zal dit afgenomen zijn tot 173.000 dollar, waardoor het voor criminele organisaties mogelijk zou moeten worden een dergelijke aanval uit te voeren. In 2021 zou het bedrag afnemen tot 43.000 waardoor ook onderzoekers bij universiteiten een dergelijke aanval zouden kunnen uitvoeren.

Bij bovenstaande berekening is de aanname gedaan dat 2⁶⁰ pogingen nodig zijn voor een aanval. Ook neemt Walker aan dat de wet van Moore nog blijft gelden en dat de kosten van servers gelijk zullen blijven. In 2009 publiceerden onderzoekers een aanval waar slechts 2⁵² pogingen nodig zouden zijn. Per poging zijn ongeveer 2¹⁴ berekeningen nodig. Verdere verbeteringen in hardware en kraakmethodes zullen het vinden van botsingen versnellen.

Hashes worden gebruikt om de authenticiteit van bestanden en datastromen te waarborgen. Ze worden onder andere toegepast in beveiligd webverkeer via het webprotocol https. Het algoritme berekent op basis van de sleutel een tekenreeks, de hash, die uniek zou moeten zijn. Bij een aanval wordt een botsing gezocht: een sleutel die dezelfde hash oplevert als de echte sleutel.

Bruce Schneier concludeert dat het tijd is om over te stappen op nieuwere hashing-algoritmes, zoals SHA-2 en SHA-3. Eerder deze week koos het NIST uit 64 voorstellen een algoritme voor de SHA-3-standaard.

Reacties (82)

Om alles even in het juiste perspectief te plaatsen: er zijn op dit moment nog nul SHA-1 collisions bekend, en iedereen die veiligheid ook maar een beetje serieus neemt gebruikt al lang en breed SHA-2.

Daarnaast is er nog een probleem, als je al een andere bitreeks vind die dezelfde hash oplevert dan is de vraag wat je daar in vredesnaam aan hebt. Die bitreeks zal onmogelijk een juist bericht kunnen bevatten of kwaadaardige code. Het is gewoon een willekreurige reeks bits met toevallig dezelfde sha1 hash.

Neem bijvoorbeeld een ZIP file. Allereerst zal de vervangende bitreeks dezelfde orde grootte moeten hebben en als je op lengte controleerd zelfs exact. Is de vervangende reeks veel langer of korter dan valt het al op. Maar stel het lukt je op een bitreeks te vinden die net zo lang is als het originele bestand en dezelfde sha1 hash heeft. Vervolgens gaat het bij het uitpakken mis want die reeks zal geen geldig ZIP bestand meer zijn en zelfs als het dat ook nog is zal de CRC niet kloppen en al helemaal zal het geen bruikbare tekst of code opleveren in het uiterst onwaarschijnlijkengeval dat het wel uit te pakken zou zijn...

Kortom, bestand met dezelfde sha1 code zal meteen door de mand vallen en heeft dus praktisch nauwelijks nut. Het enige wat ik kan bedenken is als je een bestand ongemerkt wil vervangen door een dummy zonder dat het met een sha1 check gevonden wordt. Maar de dummy valt meteen door de mand als iemand het probeert te gebruiken. En eigen code er in verstoppen zal onmogelijk zijn met dezelfde sha1 hash.

Kortom, leuk voor thoretici maar praktische waarde van nagenoeg 0. Ben je helemaal paranoide dan gebruike je naast de sha1 hash bijvoorbeeld ook nog een md5 hash. Om beide goed te krijgen kun je nog heel veel jaren verder....

Als je je hashes gebruikt om een bepaalde integriteit te garanderen dan zal je hier niet zo veel aan hebben nee. Maar als je wachtwoorden opslaat met sha1, dan is dit wel leuk voor iemand die een lijst met hashes weet te bemachtigen.

Bij md5 zijn er methodes bekend om dezelfde hash te maken door slechts enkele bytes te veranderen (voor bv. hashes van een downloadbaar bestand), en als het juist die bytes zijn die een "goed" programma "slecht" kan maken heb je een probleem, tenminste als iemand er echt misbruik wil van maken en de moeite in steekt, en de nodige kennis voor heeft.

Ik zou het een slechte zaak vinden moest hetzelfde ook mogelijk zijn met sha1 met een relatief efficiënt algorithme weliswaar, eerlijk gezegd, vooral als sha1 nog veel toegepast wordt. Gelukkig dat er vandaag zover ik weet geen bekend zijn in het openbaar.

Het is niet dat ik hierover zorgen maak, ik spreek hier natuurlijk over wat mogelijk is in het slechtste geval ;-)

[Reactie gewijzigd door avdg-BE op 8 oktober 2012 09:35]

ff de nadruk op een ander woord leggen:
er zijn op dit moment nog nul SHA-1 collisions bekend

er zijn genoeg overheden/overheidsdiensten die deze som geld zonder verpinken in een operatie pompen

Sterker nog dat geld is er allang ingepompt in veel gevallen, elke overheid die ggenoeg rekenkracht tot haar beschikking heeft kan het uitvoeren, zijn genoeg landen die supercomputer hebben en dit allang en breed kunnen uitvoeren zonder extra kosten. ook universiteiten hebben in sommige gevallen al de mogelijkheid.

Het gaat hier om crimenelen/groepen die geen toegang hebben tot die faciliteiten.

En wat nou als criminelen cloud oplossingen gebruiken. Bijvoorbeeld webcl of native client. dan gaat het hele model ook niet meer op. dan zouden ze via bijvoorbeeld piratebay ofzo iedereen een beetje werk kunnen laten doen . Waarom maken ze die hashing-algoritmes niet een biljoen keer moeilijker. (O jah door wat jij al zij, Dan kunnen ze het zelf niet meer kraken )

[Reactie gewijzigd door Anoniem: 109989 op 6 oktober 2012 17:45]

En wat nou als criminelen cloud oplossingen gebruiken. Bijvoorbeeld webcl of native client. dan gaat het hele model ook niet meer op.

Toch wel. In deze blog van Bruce Schneier beschrijft hij dat er niet eens genoeg energie in de zon zit om 256-bit te brute forcen. Dus met een paar clouds of botnets ga je het zeker niet redden.

En dat ging dan nog over 256 bit. De veiligste SHA-2 en SHA-3 varianten zijn 512 bit. Dat zijn nog héél erg veel meer mogelijkheden

Ik zou die blog maar bewaren als ik jou was - dit klinkt als een typische "famous last words" zoals het citaat aan Bill Gates toegeschreven (maar altijd ontkend) over de 640 k geheugen.

Als het brute-forcen van een 256 bits encryptie alle energie van de zon vergt - zou het brute-forcen van een 128 bits key dan niet ook enorm veel energie vragen? Maar zijn we niet al een heel eind op weg om DES (56 bits) en 3DES uit te rangeren omdat ze niet langer veilig zijn?

Edit: Wikipedia heeft er ook een stukje over -de Landauer limit - en een opmerking:

However, this argument assumes that the register values are changed using conventional set and clear operations which inevitably generate entropy. It has been shown that computational hardware can be designed not to encounter this theoretical obstruction (see reversible computing), though no such computers are known to have been constructed

http://en.wikipedia.org/wiki/Brute-force_attack

[Reactie gewijzigd door Tukkertje-RaH op 8 oktober 2012 14:32]

256 bits heeft 2^256 mogelijkheden
128 bits heeft 2^128 mogelijkheden

2 ^ 256 = 2^128 * 2^128
en
2 ^ 128 = 3.4028237 *10^ 38

Maw, 256 bits encryptie heeft ruim 10 ^ 38 keer zo veel tijd (en energie) nodig om te brute forcen dan 128 bits encryptie.

Dus nee, als je voor 256 bits encryptie zoveel energie nodig hebt als er in de zon zit, wil dat niet automatisch zeggen dat 128 bits encrypte ook ondoenlijke hoeveelheden energie nodig hebt.

Maar ik vind dat vergelijkingen in energie nogal omslachtig. Stel dat een brute force attack op een 128 bits encryptie een seconde zou duren. Dan zou een brute force aanval op een 256 bits encryptie alsnog 10^31 jaar (10 000 000 000 000 000 000 000 000 000 000) duren:

https://www.google.nl/#hl...cbc45462&biw=1243&bih=650

Maar ik vind dat vergelijkingen in energie nogal omslachtig.

Is inderdaad een beetje omslachtig, maar bedoeld om aan te geven dat scenario's als "ja maar wat nou als je een botnet hebt of een Amazon cloud gebruikt" echt in de verste verte niet toereikend zijn.

Als het brute-forcen van een 256 bits encryptie alle energie van de zon vergt - zou het brute-forcen van een 128 bits key dan niet ook enorm veel energie vragen?

Ja, maar niet de helft (zoals A Lurker al uitlegt).

Bovendien is het brute-forcen van 128-bits vandaag de dag nog steeds absoluut onmogelijk in de praktijk. Met alle computercapaciteit op aarde red je dat in de verste verte nog niet.

De reden waarom MD5 (128-bits), DES, en SHA-0 zijn uitgerangeerd, en inmiddels ook SHA-1, is omdat er bepaalde shortcuts zijn ontdekt in het algoritme waardoor je nog maar 2⁵² (of in die orde van grootte) pogingen hoeft te doen voor een brute-force.

Als je nu gewoon de functie twee keer aanroept is het vast een biljoen keer moeilijker te kraken

Twee keer hashen is statistisch gezien minder veilig. Je beperkt namelijk de input van de hash tot het aantal mogelijke hashes.

Twee keer hashen is statistisch gezien minder veilig. Je beperkt namelijk de input van de hash tot het aantal mogelijke hashes.

Niet als je de originele input er telkens opnieuw bij in stopt.

Dus hash(hash(input)+input), dan ben je in feite aan het hashen met een complexe salt die afhangt van je input.

Het probleem is dat zodra ik weet dat jij deze methode gebruikt ik dat ook weer kan brute forcen, met als enige nadeel dat het meer tijd kost dankzij het 2 keer hashen..

Beter is hash(hash(input)+RandomPerUserKey) of iets in die trant.

Het probleem is dat zodra ik weet dat jij deze methode gebruikt ik dat ook weer kan brute forcen, met als enige nadeel dat het meer tijd kost dankzij het 2 keer hashen..

Brute-forcen is juist geen enkel probleem (vanuit veiligheidsoogpunt bedoel ik dan). Want zelfs met 128-bit is dat al ondoenlijk. En dan niet ondoenlijk als in "duurt onhandig lang" maar zelfs met 100 triljoen pogingen per seconde (en daar kom je met de huidige technologie niet eens in de buurt) duurt het nog steeds langer dan dat het universum bestaat.

Laat staan 256-bit. Om over 512-bit nog maar helemaal te zwijgen

Het probleem is dat er bepaalde correlaties in het algoritme worden gevonden, waardoor je exponentieel minder pogingen hoeft te doen voor een brute-force aanval. Als je dit kunt reduceren tot 2⁵² pogingen zoals nu bij SHA-1 het geval lijkt, dan heb je een probleem want dit wordt binnen afzienbare tijd praktisch haalbaar.

Door die dubbele hashing gaan die correlaties niet meer op. Het is juist de bedoeling dat je de gebruikte hashing alleen kunt kraken met brute-force, want dan zit je volkomen veilig

[Reactie gewijzigd door Anoniem: 204567 op 8 oktober 2012 16:39]

Met bruteforce kost het 2 keer zoveel tijd om te kraken als we de pure berekening als tijdseenheid berekenen en als die persoon weet dat het om een dubbele hash gaat ;-)

Op zich geen slecht idee maar het kan nog gemakkelijker, gebruik naast SHA1 (of 2) ook iets als MD5.

Beiden hebben zwakheden maar samen nog prima te gebruiken

Dit dus, voor zo'n 60e per uur heb je 80x8x1.6ghz cores tot je beschikking bij Azure.

Dat staat min of meer ook in het bericht:

Bruce Schneier concludeert dat het tijd is om over te stappen op nieuwere hashing-algoritmes, zoals SHA-2 en SHA-3. Eerder deze week koos het NIST uit 64 voorstellen een algoritme voor de SHA-3-standaard.

Op zich niet dat bedrijven het gebruiken, maar wel dat het bestaat.

[Reactie gewijzigd door Nas T op 6 oktober 2012 15:16]

In the SDK van OSX 10.7 is SHA-1 ook al deprecated, echter moet ik het nog gebruiken omdat ik het protocol wat ik wrap erg verouderd is en ik niet zelf daar aan kan sleutelen.

Lees vooral dit even
http://www.troyhunt.com/2...shing-has-no-clothes.html

Dank je, dit is interessant.

Leuke leesvoer over hoe wachtwoorden worden beheerd:
http://throwingfire.com/s...curely/#notpasswordhashes

Ok, dus met 2,3 miljoen euro aan computerapparatuur kan je vandaag al zo'n hash breken. Hmm, is dat niet net wat het NSA aan het doen is? Allerhande gigantische computercentra bouwen? Het lukt ze alvast om MD5 collisions te zoeken, zie oa. http://threatpost.com/en_...h-collision-attack-060612

[Reactie gewijzigd door uip op 6 oktober 2012 14:28]

Als jij ergens voor 2,77 miljoen euro aan servers kan huren binnen een tijd die kort genoeg is dat je er iets aan hebt, dan ja. De maker van het artikel rekent 4 cent per octocore-serveruur, dus stel je wil een collision binnen een maand dan moet je 2,77e6 / (0,04 * 24 * 31) = ongeveer 800 duizend octocore-servers een maand lang kunnen afhuren. Niet haalbaar dus, want zelfs Amazon heeft denk ik niet zoveel servers te huur.

[Reactie gewijzigd door wjvds op 6 oktober 2012 15:24]

Ten eerste is 2,77e6 / (0,04 * 24 * 31) = 93000, ten tweede meldt het artikel ook niet dat het nu mogelijk is maar over 6 jaar als de rekenkracht met een factor 16 toe is genomen. Dan worden het dus 93000/16=5813 servers. En je hoeft ze ook niet per definitie allemaal bij 1 partij te huren, je kan ze ook bij 10 verschillende aanbieders huren. Valt ook een beetje minder op.

Met alle respect maar dan zou het nog steeds opvallen.

Ik denk dat het financiële vergelijk mank gaat: een criminele organisatie rekent dit niet aan de kassa van de computerwinkel af. De relevante vraag is: wat kost het vandaag de dag en anno 2018 om een botnet van dergelijke capaciteit op te zetten?

Opzetten is 1. Dat zal niet zo moeilijk zijn. Vraag is meer het controleren zodat alles dezelfde werking heeft en efficient werkt. Niet dat pc 1 en pc 100 en pc3 toevallig dezelfde berekening doen. Daarvoor heb je snel internet nodig. En bij welke consument je dit ook gaat doen. Je kan ervanuitgaan dat ome Joop achter de keukentafel de stekker eruit trekt als zijn pc niet reageerd omdat hij 100% CPU loopt te trekken.

Dit zijn cijfermatige getallen een normale cpu hiervoor in zetten is niet waardeloos maar niet aan te raden. SPU´s daarentegen zijn weer een ander verhaal.

Zo ken ik een bank die alle Unix systemen eruit wilde doen en de boel over wilde gooien op een linux kernel. Of andere Unixen. Punt was kwa cijfer berekeningen was er niets snellers dan IBM AIX systeem.

Ook de NSA en de Cia enz. hebben allang geen hele grote datacentres meer zoals vroeger. Deze huren gewoon een cloud van een uni onder een cover project of maken hier afspraken mee. Dit omdat ook zij moeten bezuinigen en het onderhouden van die shit en rendement gewoon onbetaalbaar werd. Naatuurlijk staat er nog wel wat maar veel mensen denken dat de NSA honderderden server parken heeft terwijl ze er 3 hebben en de rest uitbesteden aan bijvoorbeeld onderzoekers op universiteiten met stricte voorwaarden. En zelfs Universiteiten krijgen hun supercomputer vaak voor de helft of 3/4 van het geld doordat de hardware fabrikant zelf meebetaald

De NSA is op dit moment een heel groot datacentre aan het bouwen in Utah. Waar het precies voor dient is uiteraard geheim. Volgens Wired zou het breken van encryptie een belangrijk doel zijn.

http://www.wired.com/threatlevel/2012/03/ff_nsadatacenter/

De NSA is op dit moment een heel groot datacentre aan het bouwen in Utah. Waar het precies voor dient is uiteraard geheim. Volgens Wired zou het breken van encryptie een belangrijk doel zijn.

http://www.wired.com/threatlevel/2012/03/ff_nsadatacenter/

De NSA breekt al jaren en jaren encryptie, dat is waar ze voor zijn. Echter, met de huidige sterke crypto die iedereen heeft, is het zelfs niet mogelijk om met de gebundelde supercomputers op de planeet echt zware encryptie te kraken.

NSA wordt er echter van verdacht (bewijzen zijn er niet) dat ze in ieder commercieel stuk software dat met crypto werkt, inclusief ieder commercieel OS een backdoor heeft voor de encryptie.

Of dat zo is is moeilijk te zeggen, en past ook niet erg in het mandaat van de NSA: ze moeten namelijk de ciphers van buitenlandse mogendheden kraken. Dat is andere crypto dan in commercieele OS'en zit.

Je moet even het verschil zien tussen de NSA, die alleen afluistert en op papier met wiskunde rommelt en de NCSA - de supercomputerafdeling - dat zijn maar paar honderd figuren, overwegend nerds.

Vergis je niet dat alle publieke crypto op het internet, dat die een security level heeft die welhaast lachwekkend is invergelijking met waartoe de NSA in staat is.

Om jezelf wat beter te beveiligen dien je toch fiks wat one-way hardware aante schaffen. elk onderdeeltje is al snel 5000+ euro of meer.

Pas dan kom je in de buurt waar ook de NSA moeite mee heeft.

Wat mij interesseert is niet me te beveiligen tegen de NSA - vergeet het - ze verzinnen wel wat - bovendien moet je dan een dikke bunker onder de grond hebben anders scannen ze wel dwars door je huis heen van buitenaf en hacken je machine op die manier desnoods - maar interessanter is je beveiligen tegen pottekijkers van consultants die ook enorm handig zijn en in principe veel expertise van experts gebruiken, met name gebruiken ze ingekochte militaire apparatuur (en geen goedkope) om het voor BEDRIJVEN of belanghebbende organisaties voor elkaar krijgen om je tent te kraken.

Let wel - een zwakte in linux is en blijft natuurlijk dat weliswaar het verkrijgen van 'schrijfpermissie' lastig is - maar het verkrijgen van READ permissie, wat genoeg is voor de bedrijfdsspionage van die consultants - DAT is relatief slecht geregeld in linux.

NSA zit zoveel leveltjes daarboven - dat valt niet te vergelijken hoor - ook niet qua budget.

Dit is echt totale nonsens. Kennelijk geloof je dat de N(C)SA niet alleen boven Amerikaanse wetten staat, maar ook boven wiskundige. Nou, nee dus

Een willekeurig mobiel telefoontje kan encryptie toepassen die krachtiger is dan waar de N(C)SA met al haar huidige capaciteit in nog geen miljoen miljard jaar doorheen komt.

Als je denkt dat publieke crypto op het internet (zoals bijvoorbeeld AES-256) van een 'lachwekkend' niveau is, dan sla je de plank ernstig mis en denk ik niet dat je enig besef hebt hoe ontzagwekkend veel meer rekencapaciteit het vergt om dat te brute force ten opzichte van bijvoorbeeld 128 bits alternatieven.

Ter aanvulling:
Vind ook maar eens een partij die schimmige zaken wil doen met jouw botnet in de dop. Zonder dat hoef je eigenlijk niets te controleren.
En ome Joop is maar 1 figurant. Een botnet kan er miljoenen hebben, dan moet je niet te kieskeurig zijn.

Helaas hebben ze voorloopig redelijk weinig kans om SHA2 hashes te kunnen breken. Zelfs met een boel geld gaat dat je niet binnen redelijke tijd lukken.

Die 2.3 miljoen is als je dus algoritme overpent van het INTERNET.
Dat is niet bijster hoogstaand.
Men houdt in die wereld veel achter.

Met andere woorden iets sophisticated software + hardware combinatie lukt het wel op een laptopje dan.

Het is overigens weer glashelder: alle beveiligingsprotocollen beveiligen je mogelijk wel voor 'domme' criminelen, maar voor BEDRIJVEN met fiks hardware, die breken er dwars doorheen.

Ook Shell heeft naturlijk wel genoeg hardware hiervoor.

Vind je het plezierig dat in feite elk groot bedrijf op de markt bij een consultant gewoon het kan KOPEN dat iemand door de security heenbreekt van deze of gene al dan niet potentiele klant en/of lastig persoon waar ze vanaf willen?

Want dat is nu dus de aanname: namelijk dat wat PUBLIEK OP STRAAT ligt qua software, dat het daarmee 2.3 miljoen euro kost op dit moment.

Dat is als je wat meer realistischere scenario's hanteert zoals dat die consultant dat echt niet gaat 'inslaan' bij idioten, maar bij ter zake deskundige organisaties, al dan niet in het buitenland - onder die aanname ben je nergens veilig als er fiks wat geld op het spel staat.

Dan is al die communicatie dus direct gebroken en weten ze je op deze manier direct te hacken.

Het is overigens weer glashelder: alle beveiligingsprotocollen beveiligen je mogelijk wel voor 'domme' criminelen, maar voor BEDRIJVEN met fiks hardware, die breken er dwars doorheen.

Ehm, nee. Als ik een mailtje verstuur met 2048+ bit RSA-versleuteling dan gaat geen enkel bedrijf daar doorheen komen, hoeveel geld dat bedrijf er ook tegenaan gooit. In geen 10000 jaar (oke, als quantum-computers dan gangbaar zijn, maar dan neem ik lekker een algoritme wat niet sneller gekraakt wordt door een quantum-computer en dan komen ze er alsnog niet doorheen). Ook de Amerikaanse inlichtingendiensten, die altijd graag een backdoor hadden, maken geen schijn van kans tegen een goede versleuteling.

Dat er vaak crappy protocollen gebruikt worden, of communicatie vaak uberhaupt niet goed doordacht is opgezet, wil niet zeggen dat de protocollen onveilig zijn.

[Reactie gewijzigd door bwerg op 8 oktober 2012 22:51]

Het algoritme berekent op basis van de sleutel een tekenreeks, de hash, die uniek zou moeten zijn.

Uit het duivenhokprincipe volgt dat een hash die kleiner is dan de originele sleutel, niet uniek kan zijn.

Je snapt het duivenhokprincipe niet. Die zegt dat er tenminste één hash is waarvoor een collission bestaat. Je kunt geluk hebben en een hash hebben waarvoor de sleutel wel uniek is.

Dan nog klopt die zin in het artikel niet. Collisions komen nou eenmaal voor, bij hashes met beperkte lengte, dus voor een hashfunctie is het nooit de bedoeling dat die unieke resultaten geeft voor een bepaalde invoer, dat zou puur toeval zijn. Een hash waarvoor de sleutel uniek is noem ik geen geluk, want dat betekent dat de rest van de sleutels juist weer wat extra collisions hebben. Dan heb je de hoeveelheid collisions liever uniform verdeeld.

je wil juist zo weinig mogelijk collisions hebben, waarom denk je dat de cryptografische industrie zoveel onderzoek doet naar/gebruik maakt van priemgetallen

Collisions komen altijd voor bij beperkte lengte van de sleutel, omdat er minder sleutels zijn (namelijk 2ⁿ bij n bits) dan mogelijke invoer (simpelweg oneindig). Dus dat er collisions zijn is bij hashing gewoon een feit, dat is niet iets wat voorkomen kan worden of zo. Ik zeg nergens dat je collisions wil hebben of dat ze positief zijn om te hebben. Maar het is positief om hashes te gebruiken voor bepaalde toepassingen en collisions krijg je er gratis bij. Unieke sleutels zijn bij een hash-functie dus helemaal niet waar naar gezocht wordt, want je hebt er niets aan, en dat bedoel ik met "nooit de bedoeling dat die unieke resultaten geeft".

Je wil slechts dat je collisions zo onvoorspelbaar mogelijk zijn, zodat de waardes van een hash uniek lijken. Maar écht unieke waardes zouden duiden op een niet-uniforme verdeling, wat bij een secure hashfunctie een slechte eigenschap is.

[Reactie gewijzigd door bwerg op 6 oktober 2012 19:18]

Je wil slechts dat je collisions zo onvoorspelbaar mogelijk zijn, zodat de waardes van een hash uniek lijken. Maar écht unieke waardes zouden duiden op een niet-uniforme verdeling, wat bij een secure hashfunctie een slechte eigenschap is.

Je wil eigenlijk controleren of een bericht of gegeven juist is overgekomen. Dus niet corrupt is geraakt tijdens transport of is veranderd. De kans dat een corruptie of verandering exact dezelfde hash geeft is ook 1 op 2ⁿ en bij grotere waardes van n uiterst onwaarschrijnlijk. Een 32 bit CRC is al vaak genoeg en dat is een kans van 1 op 4 miljard.

Zelfs al zo je een bericht kunnen maken met dezelfde hash dan zou het bericht zelf door de mand vallen doordat het geen correcte inhoud meer heeft. Wat je wil is niet alleen een ander bericht met dezelfde hash maar ook nog dat een bericht nog steeds autenthiek lijkt maar met aanpassingen van een onbevoegde. Dat zo'n bericht ook nog dezelde sha1 hash zou hebben is bijna onvoorstelbaar.

Met een ISO bestand kan ik me het nog voorstellen door naast de bestanden 1 bestand met random troep toe te voegen die er voor zorgt dat de hash weer klopt. Maar dan zoek je niet een willekeurige collision maar een heel specifieke. En dat zal nog factoren meer rekenkracht vergen dan simpel 1 willekeurige collision vinden.

Je wil eigenlijk controleren of een bericht of gegeven juist is overgekomen. Dus niet corrupt is geraakt tijdens transport of is veranderd.

Dat is niet het (voornaamste) doel van een secure hash, controleren op corruptie kan ook met een checksum maar dat is voor cryptografische doeleinden niet voldoende. Een CRC is dan ook géén secure hash en dat heeft niet hetzelfde doel als SHA.

Checksums zijn bijvoorbeeld helemaal niet aan de orde als het gaat om wachtwoorden, daarbij worden gewoon de hashes vergeleken. Één collision met een bestaand wachtwoord en je valt helemaal niet door de mand (niet dat dat nou zo simpel is, maar toch ).

En een checksum naast de hash maakt het inderdaad wel nóg veiliger (want je moet dan twee collisions tegelijk vinden) maar dan kun je net zo goed gewoon een sterkere hash-functie nemen, veel eenvoudiger.

[Reactie gewijzigd door bwerg op 7 oktober 2012 00:44]

Priemgetallen hebben hier geen reet mee te maken.

En hoe bedoel je "zo weinig mogelijk" collisions. Er zijn een eindig aantal hashes (2⁵¹²) en een oneindig aantal mogelijke inputs, dus er zijn per definitie ook altijd oneindig veel collisions.

Wat bwerg zegt, je wilt dat ze het liefst zo uniform mogelijk zijn verdeeld.

Uniform mogelijk verdeeld? Dat behoeft een goede definitie.

Uniform mogelijk verdeeld? Dat behoeft een goede definitie.

Dat het aantal verschillende inputs van N bits die een bepaalde hash H hebben, ongeveer (liefst: exact) gelijk is voor alle mogelijke hash waarden H, voor iedere N.

Dus als er 2⁵¹² mogelijke hashes zijn, dan wil je dat van alle mogelijk inputs van 513 bits, het liefst dat er telkens 2 inputs dezelfde hash hebben. En niet dat er 2⁵¹²-1 inputs zijn met allemaal een unieke hash en de overige 2⁵¹²+1 allemaal dezelfde. En idem voor inputs van 514 bits (idealiter steeds vier verschillende inputs per hash dan), enzovoort.

Met andere woorden: dat de collisions zo gelijkmatig mogelijk verdeeld zijn.

Da's wel een erg lage standaard. Dan kun je (voor N>512) de laatste 512 bits nemen. Ik ben het wel met KaptKoek eens, een goede definitie is best lastig.

Ik denk dat je't eerder moet zoeken in statistiek; de kans dat twee random strings dezelfde hash value H hebben hoort onafhankelijk te zijn van de exacte waarde van H.

Dat het uniform verdeeld moet zijn wil niet zeggen dat dat de enige eis is natuurlijk. Het is één van de eisen. Ook niet zo'n precieze trouwens, want voor kleinere N kan dat natuurlijk sowieso niet en dat het voor soms niet exact uitkomt maakt ook niet zo uit, als er maar geen waardes structureel veel of weinig voorkomen.

De andere eisen zijn gewoon een standaard lijstje, zoals bijvoorbeeld op wikipedia te lezen is. Uniforme verdeling valt eigenlijk onder de andere eisen, een functie wordt zwakker in de hash-eisen als die sterk van een uniforme verdeling afwijkt. Dat komt inderdaad neer op jouw stelling over statistiek.

[Reactie gewijzigd door bwerg op 7 oktober 2012 00:32]

Da's wel een erg lage standaard. Dan kun je (voor N>512) de laatste 512 bits nemen. Ik ben het wel met KaptKoek eens, een goede definitie is best lastig.

Dit sloeg alleen op de uniforme verdeling, een goede hash voldoet natuurlijk aan nog meer eisen.

Vandaar ook de volgende zin dat er een botsing gezocht wordt: een sleutel die dezelfde hash oplevert, en waardoor de hash dus niet meer uniek is.

Nee, een collision in crypografisch hash algoritmen gaat over data aanpassen zonder dat de hash veranderd.

Dat is één soort aanval, het kan wel degelijk ook nuttig zijn om een bepaalde sleutel (of meer algemeen: random data) te genereren die een bepaalde gewenste hash oplevert.

Als jij ergens wilt inbreken, en je weet dat het login systeem met password hashes werkt, en je kent iemands password niet maar weet wel dat diens hash 123456789 is, dan ben je dus binnen als je willekeurige data kunt genereren waarvan de hash 123456789 is. Die data is dan hoogstwaarschijnlijk niet hetzelfde als het password, maar dat maakt voor dit doeleinde niet uit. De originele data (het echte password) komt hier dus niet aan te pas.

Maar zo'n aanval is volgens mij nog veel lastiger dan een collision genereren.

Hiervoor heb je alleen een collision nodig, dus dit ís een collision aanval. Dat het doel hier iets anders is maakt daar niks voor uit.
Overigens is zo'n aanval in een goed beveiligd systeem wél heel moeilijk, want daar worden salts gebruikt om te zorgen dat een input niet direct gehasht wordt maar eerst nog op een andere (voor een hacker waarschijnlijk onbekende, tenzij hij de broncode van de software heeft) manier bewerkt wordt.

Maar een salt helpt niet tegen een brute-force aanval.
Als hash(X) = hash(Origineel + salt) maakt het nog steeds niet uit dat je Origineel en salt niet weet.
Een salt helpt alleen tegen rainbow tables:
hash('mijnpassword') <> hash('mijnpassword' + salt)

Het enige wat helpt tegen een brute-force aanval is en een goed doordachte lockoutpolicy. Jammer genoeg biedt zo'n lockout policy ook een prima denial of service mogelijkheid.

Hashes worden niet alleen gebruikt voor wachtwoorden, maar voor nog veel meer, zoals het verifieren van data. Het scenario waar het hier oa om gaat is dat er bijvoorbeeld een nieuwe update voor Windows is, en dat een crimineel graag een trojan aan die update wilt toevoegen. Maar dat werkt niet, omdat de hash van de originele update anders is dan de hash van de trojan versie, en dus weigert de client de update.

De bedoeling van een collision is dat je een variant van de trojan bouwt die zo in elkaar zit, dat de hash gelijk blijft aan het origineel. Dan kun je dus de internet verbinding van de client onderscheppen, jouw variant van de update aanbieden, en dus je trojan op de computer krijgen.

Maar voor het uitrekenen van die collision, daar komt helemaal geen derde partij aan te pas die een lockoutpolicy kan hebben. Die collision reken je gewoon offline uit. Vandaar dat die hashes ook gewoon tegen een brute force aanval moeten kunnen.

Jammer genoeg biedt zo'n lockout policy ook een prima denial of service mogelijkheid.

Is dat zo? Lockout gebaseerd op source IP adres werkt toch goed?

hoezo helpt een salt niet? Als je een collision weet dan moet je dus je collision invoeren om dus van een service misbruik te kunnen maken, maar omdat die salt er bij komt en je die salt niet weet kan je toch nooit gemakkeliijk zorgen dat het eind resultaat hetzelfde is?

Tenzij je astronomisch veel geluk hebt? Het blijft mogelijk, maar in dit geval is het ofwel gokken met extreem geluk (met een sterk wachtwoord) ofwel de db hacken ;-)

Jawel, want tijdens het inloggen plakt de server er nog een salt aanvast. Dus jij weet wel dat jouw random data dezelfde hash heeft als het echte wachtwoord + salt, maar de server zal hash(random data + salt) doen en zo concluderen dat je een ongeldig wachtwoord hebt.

Hiervoor heb je alleen een collision nodig, dus dit ís een collision aanval.

Nee, bij een willekeurige collission heb je H(A) = H(B) met A != B. Wat je hier echter wilt is A met H(A) = B voor een gegeven B.

[Reactie gewijzigd door Olaf van der Spek op 6 oktober 2012 17:39]

Of je nu gaat proberen om H(A) gelijk te krijgen met H( of met B maakt niet echt uit (nouja, in het laatste geval moet B dus wel een resultaat van een hash zijn).

Jawel, want in het voorbeeld van kumquat heb je H(B ) wel maar B zelf niet, en bij een willekeurige collision heb je juist geen specifieke hash die je probeert te krijgen. In beiden gevallen faalt de secure hash-functie, maar op een andere manier.

Met een collision kom je niet door de beveiliging in het voorbeeld van kumquat, en met een pre-image-attack heb je nog geen succesvolle collision attack.

Zo'n aanval waarbij H(A) = B wordt inderdaad geen collision-aanval genoemd, maar een pre-image-aanval. Die twee aanvallen zijn verschillend, als je een aanval op de éne manier hebt gevonden kan het nog niet op de andere manier, en andersom.

Ik heb verder de ballen verstand van hashes. Maar duivenhokprincipe slaat nergens op. Als je met SHA-1 bijvoorbeeld 10 verschillende unieke hashes kan creeeren, en je houd jou SHA-1 hash naast die van 10 andere (10+1), zegt het duivenhokprincipe alleen dat er tenminste 1 dubbele zal zijn. Gewoon super logisch, niets boeiends.

Als ik naar een winkel ga met 50 verschillende paren schoenen, dan zullen 51 kopers naast elkaar in ieder geval 1 dubbel paar schoenen hebben. Dat is duivenhokprincipe. Gewoon stating the obvious. Heeft niets te maken met de grootte van de sleutel vs. de grootte van de hash. Enkel met het aantal unieke mogelijke hashes (duivenhokken) vs de beschikbare hashes (duiven). Als jij genoeg hashes aanmaakt, zal je ongetwijfeld een gelijke tegenkomen.

[Reactie gewijzigd door chimnino op 7 oktober 2012 10:44]

Maar is het niet zo dat je voor elk certificaat/bestand, een nieuwe collision moet berekenen?

Niet helemaal. Je kunt een precomputed table van alle hashes opslaan. Dit verbruikt natuurlijk wel veel geheugen, vandaar dat er bijvoorbeeld http://en.wikipedia.org/wiki/Rainbow_table rainbow tables gerbruikt kunnen worden.

En om die reden moet je altijd met salt werken. Per hash een random salt opslaan, zodat het maken van een rainbow table onhaalbaar wordt.

Ja, maar het is natuurlijk niet zo dat je na elke aanval al je computers weggooit en voor $2,77 nieuwe apparatuur aanschaft.

Die 2,77 miljoen was gebaseerd op gehuurde cloud-capaciteit. Dus ja, dat geld is na 1 aanval weg.

Vreemd, hier en ook hier staat dat Bruce Schneier vind dat geen van de SHA-3 kandidaten beter is dan SHA-512:
"Even worse, none of the SHA-3 candidates is significantly better."
En hij zegt dat we nu geen opvolger nodig hebben.
(Inmiddels ook bij geachte redactie geplaatst.)

[Reactie gewijzigd door Xubby op 6 oktober 2012 14:46]

Dat gaat over SHA-512, wat onder de SHA-2 standaard valt.

Dit artikel gaat over SHA-1, wat slechts 160 bits is en al veel ouder.

Dat kan wel zijn, maar in tegenstelling tot de SHA-2 varianten (waar SHA-512 ook onder valt) is SHA-3 *niet* gebaseerd op een van de eerdere varianten. Een eventuele aanval in SHA-3 maakt SHA-2 niet onbruikbaar, net als andersom. Diversiteit lijkt me eigenlijk ook wel een verstandig voornemen

Er is een groot verschil tussen niet beter en niet significant beter.
In het artikel waar jij naar linkt zegt Bruce weldegelijk dat SHA-3 kandidaten beter zijn dan SHA-2 alleen is een opvolger nog niet nodig omdat net name SHA-512 voorlopig nog voldoet.

Hoewel ik niet weet of het zo maar kan, maar dan zou ik meteen de overstap maken naar SHA-3 zodat voorlopig weer en veilig algoritme gebruikt wordt.

Waarom? Tussen SHA-1 (wat over 6 jaar in gevaar komt) en SHA-3 zit ook nog SHA-2. Er zijn nog geen voorzienbare aanvallen op SHA-2, ook als je de wet van Moore meerekent.

"Volgens een ruwe schatting van Walker kost de apparatuur voor een dergelijke aanval in 2012 nog zo'n 2,77 miljoen dollar. In 2018 zal dit afgenomen zijn tot 173.000 dollar, waardoor het door criminele organisaties mogelijk zou moeten worden een dergelijke aanval uit te voeren"

dus ze gaan ervan uit dat een crimineel rond de 173.000 euro heeft / overheeft ervoor.

Grote bedrijven die al voor paar miljoen hebben staan - die zijn nooit crimineel natuurlijk.

Bedrijfsspionage bestaat tenslotte niet