Cookies op Tweakers

Tweakers maakt gebruik van cookies, onder andere om de website te analyseren, het gebruiksgemak te vergroten en advertenties te tonen. Door gebruik te maken van deze website, of door op 'Ga verder' te klikken, geef je toestemming voor het gebruik van cookies. Wil je meer informatie over cookies en hoe ze worden gebruikt, bekijk dan ons cookiebeleid.

Meer informatie

Nederlander kraakt oud maar nog veelgebruikt sha-1-algoritme

Door , 100 reacties

De Nederlandse cryptanalist Marc Stevens en het beveiligingsteam van Google zijn erin geslaagd een succesvolle collision-aanval op het sha-1-hashingalgoritme uit te voeren. De aanval toont aan dat sha-1 in de praktijk niet meer veilig is en zo snel mogelijk uitgefaseerd moet worden.

Dat sha-1 niet meer voldoet voor verificatie en ondertekening was al bekend, maar tot nu toe ging het om theoretische of gedeeltelijke aanvallen. De drijvende kracht daarachter was Marc Stevens van het Centrum Wiskunde & Informatica, of CWI, die zijn eerdere werk nu heeft gebruikt bij de eerste volledige collisionaanval op sha-1, die hij Shattered heeft genoemd.

Stevens toont zich tegenover Tweakers verheugd. "Ik ben al zeker zeven jaar bezig om tot een zo praktisch mogelijke aanval te komen. Ik denk dat het gelukt is om een methode te ontwikkelen met een zo laag mogelijke complexiteit en door gebruik te maken van zeer geavanceerde cryptanalyse. Het is mooi om dat nu in de praktijk te zien." Naast Stevens waren Pierre Karpman van het CWI en Googles Security, Privacy and Anti-Abuse-team bij de aanval betrokken. Op de site Shattered.io geven ze details over de aanval.

Met de methode slaagden ze erin identieke sha-vingerafdrukken te maken op basis van twee verschillende pdf-documenten, iets wat niet mag gebeuren bij hashingalgoritmes die ingezet worden voor beveiliging. Die beveiliging berust er juist op dat bepaalde invoer tot een enkele specifieke uitvoer, de hash, leidt. Die koppeling wordt gebruikt om bijvoorbeeld te verifiëren dat een contract ook echt het authentieke document is zoals partijen dat hebben afgesloten. Door de aanval van Stevens vervalt de garantie die de sha1-hash moet bieden; de hash kan nu ook de uitvoer zijn van een ander contract met bijvoorbeeld andere bedragen.


Stevens brengt een pdf-generator uit die gebruikmaakt van zijn collisionaanval om iedereen de mogelijkheid te geven nep-pdf's met identieke hashes te maken. Die generator brengt hij over 90 dagen uit om partijen de mogelijkheid te geven sha-1 in de komende tijd uit te faseren. Bang voor misbruik is Stevens niet. "Het toont vooral iets aan. Bovendien publiceren we een tool waarmee op misbruik met nep-pdf's te controleren is. Als er twijfel is over de authenticiteit, kunnen mensen documenten daarmee scannen." De werking van die tool is gebaseerd op Stevens' eerdere onderzoek naar de detectie van bestanden die met een collisionaanval gegenereerd zijn. Google integreert die tool in Gmail en Drive ter bescherming tegen misbruik.

De impact ligt volgens de CWI-onderzoeker veel meer bij software. "Git is bijvoorbeeld compleet gebaseerd op sha-1 voor het identificeren van file-objecten, revisies en data-integriteit. Hierbij is de collisionaanval ook makkelijker uit te voeren. Voor de pdf's moesten we allerlei trucs uithalen", zegt Stevens. De onveiligheid betreft nu ook vooral digitale handtekeningen; misbruik voor certificaten is minder voor de hand liggend. "Maar we hopen dat het de hele industrie nu duidelijk wordt dat sha-1 gedateerd is."

Om zijn aanval in de praktijk te brengen kreeg Stevens de helpende hand van Google. "Ze benaderden me met de melding dat ze het belangrijk vinden om aan te tonen dat sha-1 onveilig is. De hulp van Google bestond onder andere uit het beschikbaar stellen van rekenkracht van de datacenters. Volgens Elie Bursztein van Googles anti-abuse-onderzoeksteam kostte het 9.223.372.036.854.775.808 sha-1-verwerkingen om de botsing te vinden.

Volgens Stevens verliep het project in twee fasen. "De eerste was simpel en voerden we uit op cpu's van de honderdduizenden computers van Google. Een enkele cpu zou daar 6500 jaar over gedaan hebben. De tweede fase was complexer, maar deden we op de gpu-architectuur waar ook AlphaGo van DeepMind op draait. Een enkele gpu zou honderd jaar doen over die fase, terwijl die zes keer zo moeilijk was als de eerste. In de praktijk duurde het met de infrastructuur van Google acht dagen."


De geslaagde aanval komt op een moment dat de markt nog in de transitie van sha-1 naar sha-2 en sha-3 zit. Sha-1 stamt uit 1995 en is een 160bit-hashfunctie. Onderdeel van de sha-2-familie zijn onder andere sha-256 en sha-512. Sha-2 en sha-3 bevatten significante verbeteringen waardoor die standaarden nog aanzienlijke tijd meekunnen.

Het probleem is dat sha-1 nog altijd veel gebruikt wordt voor het ondertekenen van software en voor de verificatie van de ssl/tls-beveiliging van onder andere online transacties en inlogverbindingen. Wel zijn browsers als Chrome, Edge en Firefox er inmiddels toe overgegaan waarschuwingen te tonen bij het openen van https-verbindingen die beveiligd zijn met een sha-1-certificaat. Het CA-browserforum heeft bepaald dat in 2017 geen sha-1-certificaten meer uitgegeven mogen worden.

Reacties (100)

Wijzig sortering
Het artikel wekt de indruk dat de veiligheid van Git hierdoor gecompromitteerd is, dat is niet echt waar gezien zelfs Linus Torvalds de SHA-1 hashes in Git niet als een securityfeature ziet maar een consistency check. Security leg je in de layers eromheen met SSH/HTTPS, gezien iemand die daardoorheen is met afdoende rechten toch al malicious code kan pushen. En een forged commit force-pushen valt net zo hard op in reviewprocessen als gewoon foute code pushen, of harder.

Om een oude opmerking te citeren op HackerNews:
So, the weaknesses in SHA-1 probably mean that exploiting those weaknesses in the context of git still requires a mole in the development team. Though, I wouldn't want to bet my life on nobody noticing a big nonsense comment in the middle of a C file or someone figuring out how to construct a reasonably reviewable C file as the carefully crafted benign file.

In any case, the weaknesses in SHA-1 still likely pose a significant difficulty in forging a git history without planting a mole in the dev team. It's much better than no cryptographic barriers to forgery.
Er is niet eens een gevaar in git, want je kunt wel een blob met duplicate hash toevoegen, maar niet uitchecken.
Je krijgt altijd de oudste terug.

Dus mocht je ook een blob maken met een hash die al bestaat, dan krijg je een dangling blob.
Lastig, maar niet gevaarlijk.

Er was wel gevaar geweest als je blobs kon overschrijven. Maar dat kan niet.

[Reactie gewijzigd door jeroen3 op 23 februari 2017 14:28]

Dat is wel de bedoeling ja - dat je de oudste terug krijgt. Maar dat is een situatie die niet getest is, en nooit door gebruikers zelfs uitgeprobeerd wordt. En conceptuele maar ongeteste features in software hebben zo de neiging niet geheel waterdicht te zijn. Er hoeft maar een stukje caching of een special case uitzondering ergens te zijn die de aanname maakt dat de oude blob net zo goed is als de nieuwe (geheel redelijk zonder attacker die sha-1 collisies kan maken), en er kan een data verschil zijn. Iemand probeerde dit soort problemen eens te simuleren hier: http://stackoverflow.com/...sha-1-collision-on-a-blob en ik kan niet zeggen dat ik daarna het vertrouwen heb dat alle consequenties van een sha-1 collisie nou makkelijk te voorspellen zijn.

Verder is het gebruik van de oudste blob niet echt een bescherming; meer een soort degelijke conservatieve default. Een attacker kan de verwarring met enige creativiteit alsnog vermoedelijk misbruiken. Stel je maakt een PR naar een open source project en je PR wordt goedgekeurd - de diff je goedgekeurd is zou dus kunnen afwijken van wat er aangeboden is. Stel nou dat je iemand anders zover krijgt om jou branch ook in een andere repo te mergen (want hij was toch al goedgekeurd!), bijv. een andere fork.

Of stel je vind een repo die ook hun node_modules of ander dergelijke dependencies meecomitten, en stel dat je dat de situatie kunt creeren dat de module die je PR refereerd zo gemaakt is dat ie conflicteerd met een *toekomstige* blob die je nog zult releasen...

Er zijn veel attacks op de wereld, en het is lastig te overzien of iets echt waterdicht is nadat blijkt dat je wel een voet tussen de deur kan krijgen. Iedere open source repo die publieke PRs accepteerd (oftewel: zeer veel!) is hier potentieel een doelwit, want iedereen maakt de aanname dat wat je in zo'n PR ziet ook echt is wat er in de repo komt en wat er in de branch staat. Maar met een sha-1 collisie zijn dat soort aannames ineens soms niet meer valide.

Dit is wel degelijk op termijn een risico voor git.

[Reactie gewijzigd door emn13 op 23 februari 2017 23:00]

Maar dan kan je toch de eerste blob herschrijven (rewrite history / force push)? Als iemand daarna de repository binnenhaalt zijn de hashes niet verandert, maar de daadwerkelijke inhoud wel.
Volgens mij kan dat alleen op filesystem level. Niet via git.
Hier mis je iets heel essentieels: zowel signed commits als signed tags vertrouwen op de integriteit van de SHA1 hashes.

Linus Torvalds kan wel honderd keer zeggen dat 'ie het niet als een security feature ziet, maar dit haalt signed commits/tags gewoon keihard onderuit; Git is gebaseerd op een Merkle tree en gebruikt daarin SHA1 hashes.

Als je dus een commit ergens in de history kunt falsificeren, kun je beinvloeden wat de inhoud van ieder punt daarna in de commit history is, zonder daarbij de signature ongeldig te maken. Dit is dus de doodsteek voor signed commits/tags.

(En ja, uiteraard zitten er beperkingen aan hoe je deze aanval effectief kunt uitvoeren, maar vergeet niet dat Git fundamenteel een gedecentraliseerd version control systeem is, en je dus niet je hele security model om een gecentraliseerde host heen kunt bouwen, zonder daarbij features kwijt te raken.)
Je mist zelf het hele essentiele punt: om deze aanval uit te kunnen voeren heb je al rechten nodig om dezelfde schade zonder collision te kunnen doen.

Dat is nu net het hele punt - de toegangsrechten zitten al voor het punt dat je deze aanval zou kunnen misbruiken. Wie historie kan falsificeren door een collision te force pushen kon ook al een manually rebased history force pushen, met hetzelfde resultaat. Probeer je het via een PR ga je daarmee hetzelfde reviewproces door als een reguliere PR die malware injecteert, waar het in de diffs in koeienletters zichtbaar is omdat je de master niet hebt aangevallen.

Het gecompromitteerd zijn van SHA1 verandert dus netto geen bal voor het risico.
Precies... sha-1 wordt helemaal niet gebruikt voor security-gerelateerde features in Git.
Bedankt ik kreeg inderdaad de indruk dat GIT gecompromitteerd was. +3
Dus ze hadden 8 dagen nodig op een van de grootste GPU clusters ter wereld om hun zin te krijgen?

Ja, nee, ja, zo lek als een mandje inderdaad.
Acht dagen is niets, zeker niet vergeleken bij de huidige, theoretische aanvallen. Jouw lakse houding is precies het probleem. De verwachting is denk ik niet dat CPU's langzamer worden, die worden alleen maar sneller. Rekenkracht wordt ook nog eens goedkoper.

Als je je door deze methode niet kan laten overtuigen dat SHA-1 uitgefaseerd moet worden ben je een onderdeel van het probleem.

Men zal deze aanval optimaliseren, uitbreiden, verbeteren, net zoals dat met MD5 gegaan is. En ik wil wedden dat half Tweakers tegen die tijd hoog in de boom zit als er een website is die nog SHA1 gebruikt. "Wat onveilig!" "Wat dom!"

De houding die je nu tentoonspreidt is bijzonder nalatig.
Tja, maar afhankelijk van waar je naar op zoek bent is 8 dagen natuurlijk te overzien, en de investering ook. Reken maar dat onze vrienden van de NSA iets identieks hebben staan.
Zou eigenlijk verwachten dat de NSA wat sterkers heeft, hadden die niet toen e.a. aan Cray supercomputers ingeslagen?
Verder kan een hacker prima Amazons cloud/Azure/Botnet oid inhuren voor capaciteit.
[...] Verder kan een hacker prima Amazons cloud/Azure/Botnet oid inhuren voor capaciteit.
Dat kan de NSA natuurlijk ook gewoon doen. En als het belang maar groot genoeg is, mag de cloud-provider daar ook niets over naar buiten brengen.
Precies. Als je bedenkt wat er te verdienen valt met het breken van encrytie c.q. wat overheden er voor over hebben en aan uitgeven, is de hardware (betalen) het probleem niet.

Komt bij dat, als je dit op je gemak kunt opzetten, optimalisatie het waarschijnlijk nog een stuk sneller kan maken.
Dat is wat kort door de bocht. Rekenkracht wordt steeds groter, steeds makkelijker beschikbaar en steeds goedkoper. En deze aanval kan ook weer verbeterd worden waardoor het met minder rekenkracht te doen is, of dient als inspiratie voor nieuwe methodes.

Het is ook voor de toekomst. Zaken die je vandaag ondertekent wil je over een paar jaar ook nog betrouwbaar kunnen verifieren. Als je nu gebruik blijft maken van een inmiddels gekraakt algoritme kan je over een paar jaar dus niet meer verifieren dat iets inderdaad waar is.

Wat als iemand an aankomt met contract ondertekent met iets dat matched met jouw signature, omdat diegene een collision heeft weten te generen? Of, als over een paar jaar een lading eerder opgeslagen SSL verkeer ineens gedecrypt kan worden waardoor een berg dissidenten achter de tralies verdwijnen?

Daarom, overstappen naar iets veiligers zodra het kan. :)
Dat betekent dat een beetje botnet het ook kan in een paar weken, en dus de Russische en Chinese mafia.

Het gaat niet om de tijd maar om dat de theorie bewezen is dat een collision attack haalbaar is. Vanaf hier is het enkel wachten tot de volgende haarscheurtjes in het algoritme tot het over 1 jaar, of 2, of 3, ineens 2 uur is op een Geforce van 400 euro.

De complexiteit van MD5 collision attacks ging ook van 2^112 naar 2^64 in een handjevol jaren tussen 2005 en 2012. Dat is precies het verschil tussen "supercomputer" en "thuis avondje laten stampen".
Vergeet ook niet dat Google gedurende die 8 dagen ook nog gewoon opereerde :-).

Ben blij dat er wat aandacht aan besteed wordt zodat er wat meer druk op de ketel staat om certificaten te veranderen.

Voor tweakers.net geldt trouwens: SHA256withRSA :-)
Kijk anders even naar het plaatje in het artikel: "MD5: 1 smartphone, 30 sec". Denk eens terug hoe lang het soms kostte om over te stappen op nieuwe (aantoonbaar nodige en betere!) technologie. Het duidelijkste voorbeeld was misschien wel de overstap van IPv4 naar IPv6 (al is die vergelijking niet helemaal eerlijk; dat is geen drop-in replacement, wat bij encryptie-algorithmes wel zo is), maar ook het uitfaseren van MD5 heeft jaren geduurd. Je moet je serieus afvragen hoeveel rekentijd het vinden van een collision nog kost op het moment dat we SHA-1 eindelijk naar het museum sturen. En vergeet niet dat de twee groepen waar je je het meest zorgen over misbruik moet maken overheden en criminelen zijn; de ene heeft die rekenkracht gewoon staan, de ander heeft toegang tot ofwel botnets, ofwel clouds (betaald met gestolen creditcards).

Het vinden van collisions zou X keer de leeftijd van het heelal moeten kosten; als een algorithme dat niet voor elkaar krijgt, dan hebben we iets beters nodig. Niet omdat het een practisch probleem is als je in duizend jaar een collision kunt genereren, maar omdat er altijd iemand als Marc Stevens langs kan komen (SHA-1 is niet zijn eerste "slachtoffer") die, bijvoorbeeld, tien bits optimaliseert en een groot bedrijf er duizend keer zoveel machines tegenaan gooit en dan is van die duizend jaar opeens nog maar een paar uur over. Dus de, op het eerste gezicht absurde, marges heb je gewoon nodig. Iets wat oorspronkelijk miljarden jaren kostte zal in zo'n geval nog steeds duizenden jaar kosten.

Tenzij je een manier bedenkt om de hele wereldwijde infrastructuur van de ene dag op de andere te migreren naar een ander encryptie-algorithme is "acht dagen op Google's cluster" dus inderdaad hoog tijd om actie te ondernemen (iets waar we gelukkig allang mee bezig waren).
Het gaat erom dat ze er doorheen zijn gekomen.
Ze weten nu hoe het moet.
Dus vanaf dat moment wordt het alleen maar makkelijker en gaat dit sneller.
Aiiiiii Niet alleen Git heeft dus er problemen mee. Ook Fossil en Mercurial. Dat gaat leuk worden.
Waarom is mij niet duidelijk want SHA-2 kwam uit in 2001 en Git & Mercurial kwamen uit in 2005 en Fossil een jaar later. 3 projecten met andere devvers die dezelfde fout maken.
https://news.ycombinator.com/item?id=7627377:
Linus Torvalds: "the point is the SHA-1, as far as Git is concerned, isn't even a security feature. It's purely a consistency check. The security parts are elsewhere, so a lot of people assume that since Git uses SHA-1 and SHA-1 is used for cryptographically secure stuff, they think that, OK, it's a huge security feature. It has nothing at all to do with security, it's just the best hash you can get."
Mijn punt is eerder dat er voor een oud ding gekozen is waarvan al signalen kwamen dat het problemen gaat opleveren terwijl de nieuwe al voorhanden was.
En ik zeg dat je punt fout is omdat het geen security feature is. Voor consistency checks voldoet zelfs MD5 nog prima - je maakt precies de denkfout die Linus aangeeft dat omdat SHA-1 ook voor security wordt gebruikt het overal voor security wordt gebruikt.

Het enige wat de hashes in Git nodig hebben zijn genoeg keyspace om binnen miljoenen commits de kans op een autonome collision minimaal te maken. Op dat gebied kunnen ze nog jaren met SHA-1 vooruit.
Linus gaat hier echt te snel door de bocht. Security is niet een ding, het bestaat o.a. uit een boel aannames en afspraken met mensen onderling. Als je daar ineens verandering in brengt gaat dat wel degelijk potentieel security risico's met zich mee brengen.

Dat is beetje als beweren dat Java geen memory leaks kan hebben ivm een GC, of Rust geen race conditions. Sure, als je de juiste definitie kiest klopt dat ergens op een formele wijze wel. Maar ook met een GC kun je prima objecten permanent in level houden die toch nooit meer gebruikt kunnen worden en dus unbounded memory gebruiken; en bijv. data-races zijn niet (normaliter) mogelijk in Rust, maar niet alle races zijn data-races.

Evenzo: Git mag wel per "definitie" commit hashes niet als veiligheids feature beschouwen, maar die definitie kan niet voorkomen dan mensen en processen dat toch wel doen. Mensen gaan er nu vanuit dat bijv. pull requests van onbekenden niet in zichzelf gevaarlijk zijn, en dat jij in die PR ziet ook wat de rest van de wereld ziet als ze die PR zouden mergen - maar met een collisie is dat niet meer zomaar waar.

EDIT: inmiddels heeft ook Linus hierop gereageerd, zie http://marc.info/?l=git&m=148787047422954 En hier is zijn standpunt veel redelijker: in praktijk zal die allemall nu nog reuze meevallen vanwege een aantal details, maar ook hij zou graag van sha1 af willen.

[Reactie gewijzigd door emn13 op 24 februari 2017 09:34]

Waarom levert het problemen op? Het wordt gebruikt voor de berekening van een hash, meer niet.

EDIT: Typo

[Reactie gewijzigd door raugustinus op 23 februari 2017 14:49]

Als je de Telegraaf moet geloven dan is 'Het Internet' nu gekraakt:
http://www.telegraaf.nl/d...gsmethode_gekraakt__.html

Treurig staaltje journalistiek
Tsja, die wisten een tijdje geleden ook te melden dat Whatsapp was gekraakt...
Ken je iemand die het al gebruikt? Wat mij betreft is het de hoogste tijd maar de meeste software ondersteunt het niet.
Momenteel hebben we eigenlijk alleen SHA2. Als daar een fout in wordt gevonden, en dat kan altijd, dan hebben we eigenlijk geen alternatieven meer om naar over te stappen.

Er bestaan wel alternatieven maar de ondersteuning daarvoor is zo beperkt dat we er niet op kunnen vertrouwen als we het nodig hebben.

[Reactie gewijzigd door CAPSLOCK2000 op 23 februari 2017 17:26]

In de cryptocurrency wereld in ieder geval wel.

SHA3 is gebaseerd op het Keccak algoritme en er zijn diverse cryptocoins zoals MaxCoin, Slothcoin en Cryptometh voor handen.
Ik denk dat toendertijd de rekenkracht nog zo laag was dat het gebruik van sha-2 teveel zou vertragen met commits pushen.
Je moet niet vergeten dat sinds toen er een heleboel gespecialiseerde instructies aan processoren zijn toegevoegd die dat werk veel sneller kunnen dan de algemene instructies van toen.
Ik snap iets niet. In het artikel staat dat Stevens een PDF-generator uitbrengt zodat iedereen er gebruik van kan maken. Maar heb je dan dat hele rekencluster van Google nodig of niet, als je 10 miljard aan hardware moet uitgeven is het niet echt haalbaar voor "iedereen".
Ik snap iets niet. In het artikel staat dat Stevens een PDF-generator uitbrengt zodat iedereen er gebruik van kan maken. Maar heb je dan dat hele rekencluster van Google nodig of niet, als je 10 miljard aan hardware moet uitgeven is het niet echt haalbaar voor "iedereen".
Niet wanneer je een voorspelbaar patroon in de collisions vindt, waardoor je daarvan gebruik kan maken en binnen no-time elke SHA1 handtekening kan vervalsen.
Niet wanneer je een voorspelbaar patroon in de collisions vindt, waardoor je daarvan gebruik kan maken en binnen no-time elke SHA1 handtekening kan vervalsen.
Maar waar is dat enorme rekencluster dan voor gebruikt? Is het patroon dan door de computer gevonden? Dat kan maar het zou een doorbraak in AI betekenen die nog wel groter nieuws is dan SHA1 zelf. Dat lijkt me dus niet wat er aan de hand is.

In principe zijn alle aanvallen op cryptografie anders dan brute-force zijn op zoek naar een patroon, maar tot nu toe is het altijd zo geweest dat het patroon de versleuteling zwakker maakt tot het punt is bereikt dat het zo zwak is dat je het met een groot cluster kan brute forcen. Het slimme deel van de aanval wordt dan nog steeds door mensen gedaan. Ik ga er van uit dat het hier ook zo is gegaan.

In dat geval heb je nog steeds dat enorme cluster nodig voor iedere volgende colission, en dat strookt weer niet met zo'n generator.
Ik weet niet of het hier al om een patroon gaat, maar het is best voorstelbaar dat een patroon door een boel rekenkracht wordt gevonden zonder enige vorm van AI.

Al dit soort hashes hebben niet alleen een vaste output grootte (voor sha1 bijv. 160bits, sha2-384 bijv 384 bits) maar ook een interne state space tijdens het doorreken (sha1 heeft ook 160 bits intern, maar sha2-384 bijv 512). Een soort accumulation buffer.

Dit soort attacks maken gebruik van inzichten in hoe deze interne buffer zich ontwikkeld als je over een stream heen loopt. In het bijzonder, als je dus voor een bepaalde state space 2 streams hebt kunnen vinden die tot die state space leiden, dan kun je heel makkelijk veel meer dan een duplicaat vinden: plak er gewoon meer identieke data achter!

Afhankelijk van wat voor soort patronen je kunt vinden kun een collision ook op andere wijze uitbreiden tot meer collisions. Maar het vinden van zo'n "pad" kost wel veel pogingen - maar is toch geen AI.
Je kunt gewoon computing tijd inkopen bij een Google/Amazone/Microsoft.

Zal je nog steeds geld kosten en je moet je identiteit prijsgeven.
Maar als ze met een generator komen is dat een ander verhaal.

Maar zoals ik al elders schreef waarschijnlijk zal niemand hier ooit SHA1 van een document gecontroleerd hebben in zijn leven.
Ze hadden de rekenkracht alleen maar nodig om het patroon en de collision te vinden. Toen ze deze hadden gevonden kunnen ze deze vrij eenvoudig gebruiken om pdfs te vervalsen.
Met de methode slaagden ze erin identieke sha-vingerafdrukken te maken op basis van twee verschillende pdf-documenten, iets wat niet mag gebeuren bij hashingalgoritmes die ingezet worden voor beveiliging. Die beveiliging berust er juist op dat bepaalde invoer tot een enkele specifieke uitvoer, de hash, leidt.
Is dat wel correct? Een hash is toch niet per definitie niet uniek?
Meerdere documenten kunnen tot dezelfde hash leiden.
Echter je wil niet zomaar een document kunnen generen wat leidt tot een specifieke hash.
Een hash is toch niet per definitie niet uniek?
Meerdere documenten kunnen tot dezelfde hash leiden.
Dat klopt. Echter de kracht van een hashing-algoritme zou moeten zijn dat wanneer ik een document heb met hash 'abcde' ik niet een ander document mag kunnen uitrekenen dat dezelfde hash oplevert, en dat is dus precies wat ze hier gedaan hebben :)

[Reactie gewijzigd door Iknik op 23 februari 2017 18:01]

Het gaat om de tekst in de quote.
Dat 2 verschillende bestanden niet dezelfde hash mogen opleveren en dat is incorrect.
Dit klopt wel. De kans op een identieke hash is heel erg klein, en het kunnen genereren is een ernstige zwakte van de hashfunctie.
Ik begrijp het deels niet, iemand die mij wellicht het een en ander kan uitleggen maar er is niet zomaar iemand die dit zou overwegen naar mijn idee, gezien (buiten overheidsinstsanties en/of bedrijven zoals Google) niemand deze rekenkracht heeft, ook met een flink botnet lijkt mij de kans nihil dat iemand door een SHA-1 encryptie heen komt tenzij het hem duizenden uren/ euros kost.

Is het dan niet deels onterecht om te zeggen dat SHA-1 onveilig is, ja je kan er doorheen komen maar je kan ook bij wijze van naar de maan vliegen, als je maar genoeg centen hebt, idem dito voor dit, je kan het wel kraken maar alleen met een bepaalde capaciteit die niet wijd beschikbaar is.

Off-topic:

Zal er nooit een manier zijn om encryptie van tevoren al mee te bekijken en of te kraken door te weten wat het is en waar het naartoe leidt. Ik bedoel als je iets gebruikt om die key te genereren dan zal er ondanks dat daar een beveiliging op zit toch wel iets zijn om te kijken naar een log ofzo van wat die als key gegenereerd heeft, een programma moet het lijkt mij zelf ook tijdelijk onthouden om een bevestiging te kunnen ontvangen
Ik begrijp het deels niet, iemand die mij wellicht het een en ander kan uitleggen maar er is niet zomaar iemand die dit zou overwegen naar mijn idee, gezien (buiten overheidsinstsanties en/of bedrijven zoals Google) niemand deze rekenkracht heeft, ook met een flink botnet lijkt mij de kans nihil dat iemand door een SHA-1 encryptie heen komt tenzij het hem duizenden uren/ euros kost.
Je hebt gelijkt, maar zie het als het startschot. De meesten hebben nog niks te vrezen, maar er zijn partijen die wel rekening moeten houden met geheime diensten en bedrijven zo rijk als Google (bv het leger). Die paar grote jongens die zich wel zorgen moeten maken die moeten nú in actie komen, eigenlijk hadden ze al klaar moeten zijn.

Met de wet van Moore in de hand kun je uitrekenen hoe lang het nog duurt voor het wel betaalbaar wordt om een aanval te doen op jouw organisatie. Dat gaat er dan nog van uit dat er geen betere aanvallen meer gevonden worden. De geschiedenis leert dat je daar wel van uit moet gaan.

Hoe dan ook, vanaf nu gaat het alleen maar slechter worden met SHA1 en nooit meer beter. Als je nog niet was overgestapt dan kun je nu voorspellen hoe lang je nog hebt voor het echt een probleem wordt.
Dat is zeker waar, maar anders dan derde wereldlanden is het grote deel als de wet van moore aanhoudt mag ik hopen echt wel over gestapt.

(Alhoewel veel ziekenhuizen toch nog op xp leunen)
Ik begrijp het deels niet, iemand die mij wellicht het een en ander kan uitleggen maar er is niet zomaar iemand die dit zou overwegen naar mijn idee, gezien (buiten overheidsinstsanties en/of bedrijven zoals Google) niemand deze rekenkracht heeft, ook met een flink botnet lijkt mij de kans nihil dat iemand door een SHA-1 encryptie heen komt tenzij het hem duizenden uren/ euros kost.
Dat ligt eraan. Oudere OS'en zoals Windows XP en Vista vertrouwen nog steeds met SHA1 gesignede code, dus daar kun je met een valse (maar wel 'geldige') hash kwaadaardige code naar binnen fietsen. Dan heb je het nog steeds over een paar honderd miljoen gebruikers wereldwijd, als je die allemaal een tientje afhandig kunt maken op deze manier wordt het toch wel snel lucratieve business :)
Met de methode slaagden ze erin identieke sha-vingerafdrukken te maken op basis van twee verschillende pdf-documenten, iets wat niet mag gebeuren bij hashingalgoritmes die ingezet worden voor beveiliging. Die beveiliging berust er juist op dat bepaalde invoer tot een enkele specifieke uitvoer, de hash, leidt.
Nou ben ik geen wiskundige, maar hoe zit het precies met de aanname dat een bepaalde invoer tot een enkele specifieke uitvoer, of hash, leidt. Een hash heeft toch een beperkt aantal bits dus een beperkt aantal mogelijke hashes. In theorie met een oneindig aantal mogelijkheden aan invoeren dan kom je toch eens met verschillende invoeren toch op dezelfde hashes uit? Collisions bestaan dan toch? Hoe zit dit dan precies? Zoals ik al zei ben ik geen wiskundige, laat staan dat ik iets weet van hoe cryptografie precies in elkaar zit. :)
In theorie met een oneindig aantal mogelijkheden aan invoeren dan kom je toch eens met verschillende invoeren toch op dezelfde hashes uit? Collisions bestaan dan toch?
Klopt. Een oneindig aantal inputs mappen op een eindig aantal outputs levert een oneindig aantal collisions op. Dat is ook in principe het probleem niet. Het idee is, net als bij encryptie, dat het onpraktisch lang duurt om zo'n collision te vinden. Normaal moet je dus, als je een bepaalde hash hebt, in de oneindige poel van mogelijke inputs gaan zoeken naar iets anders dat dezelfde hash oplevert. Dat is wel een paar avondjes werk, zeg maar :) Nu is het bij SHA-1 wel zo dat de input maximaal 264 bits is, dus dat is niet helemaal oneindig, maar nog steeds wel zo veel dat je ongeveer 257 collisions verwacht.

[Reactie gewijzigd door Iknik op 23 februari 2017 18:31]

Dankje! Ik verwachtte al dat er logischerwijs een softwarelimiet op de input zou zijn en dat dat het aantal collisions zou beperken. Dat het er nog steeds zoveel zijn had ik nog even niet bij stil gestaan, maar als je het aantal mogelijke invoeren deeltje door het aantal mogelijke hashes dan kom je op het aantal collisions uit (denk ik dan).
Nou ben ik geen wiskundige, maar hoe zit het precies met de aanname dat een bepaalde invoer tot een enkele specifieke uitvoer, of hash, leidt. Een hash heeft toch een beperkt aantal bits dus een beperkt aantal mogelijke hashes. In theorie met een oneindig aantal mogelijkheden aan invoeren dan kom je toch eens met verschillende invoeren toch op dezelfde hashes uit? Collisions bestaan dan toch? Hoe zit dit dan precies? Zoals ik al zei ben ik geen wiskundige, laat staan dat ik iets weet van hoe cryptografie precies in elkaar zit. :)
Je hebt gelijk, collisions zijn altijd aanwezig en een fundamenteel kenmerk van vrijwel* iedere hash-functie. Het gaat er om dat ze erg moeilijk te vinden zijn en dat het helemaal moeilijk is om een bestaand document zo aan te passen dat er een bepaalde hash uit komt.

*In theorie kun je een hash-functie maken die meer bits output dan er aan input in gaan. Dan is het in principe mogelijk om een colission vrije hash-functie te maken, maar vraag niet wat het nut is van zo'n functie ;)

[Reactie gewijzigd door CAPSLOCK2000 op 23 februari 2017 21:13]

In dat laatste stukje beschrijf je feitelijk encryptie. Redelijk nuttig dus ;)
Respect voor het feit dat ze nu al een praktische aanval hebben, namelijk een collision met een geldig PDF document (in plaats van een willekeurige binary met dezelfde hash dat geen PDF bestand meer is). Afgezien van de benodigde rekencapaciteit (een probleem dat alleen maar kleiner wordt) zal het nu wel snel gaan met SHA1 aanvallen.
Respect voor het feit dat ze nu al een praktische aanval hebben, namelijk een collision met een geldig PDF document (in plaats van een willekeurige binary met dezelfde hash dat geen PDF bestand meer is).
De truc is dat je ergens in het PDF-bestand een blob binary data neerplempt die PDF-viewers negeren. Dan kun je daar alles neerzetten wat je wilt (dus ook de "magische code" om de hash op de gewenste waarde te krijgen) en het ding blijft geldig.

Het goede nieuws is dat je, als je de truc kent, redelijk eenvoudig kunt controleren of een PDF-bestand een blok "ongebruikte" informatie bevat waar "random" data in staat. Een blok ongebruikte informatie, zeker als het maar een paar byte is en gevuld met nullen, is simpelweg padding en geen reden tot zorgen. Hoe je het aan reguliere gebruikers meldt weet ik zo snel niet, maar de melding voor ICT'ers is dan "dit bestand is verdacht; het lijkt erop dat de hash kunstmatig een specifieke waarde heeft gekregen".

Let op dat deze truc niet alleen voor PDFs werkt; vrijwel elk bestandsformaat is vatbaar. Het enige formaat dat mij zo snel te binnen schiet waarop het niet werkt is plain text en zelfs dan alleen als je het bestand leest in een fatsoenlijke editor (Notepad stopt bijvoorbeeld met lezen bij de eerste ASCII NULL, dus dan kun je de extra data die je nodig hebt om de hash te laten kloppen aan het eind van het bestand "verbergen").
Doet me denken aan hoe fansubgroepen soms de MD5 hash die vroeger altijd onderdeel van de bestandsnaam waren 'doctorden' zodat het bijvoorbeeld allemaal 0'en waren. Idd niet zo'n punt als je allemaal maar wilt checken dat het bestand tijdens de DL (in de tijd van IRC fservs) niet gecorrumpeerd waren. Het kan nu dus ook voor SHA-1, maar zolang dat je doel is (of iets vergelijkbaars als commits onderscheiden), nog steeds geen big deal voor GiT.

Maar los daarvan wel duidelijk dat het voor security toepassingen liever vandaag dan morgen vervangen dient te worden...
Zou je in het geval van document signatures niet meerder hash algoritmes moeten gebruiken? Het lijkt mij sterk dat je een weakness vind die bij wijze van spreken en de SHA1 hash en de MD5 hash gelijk houd.
Als dit praktijk zou zijn, dan is het omzeilen van zo'n simpele combinatie denk ik een relatief kleine stap nadat beide individuele hashes gespoofed kunnen worden. Niet triviaal, maar wel een veel kleinere stap dan wat je zou willen met het oog op de toekomst. (Of schat ik dat verkeerd in?)
https://shattered.io/ doet het wel
https://www.shattered.io/ doet het niet..

#sha1 #link #incorrect

Op dit item kan niet meer gereageerd worden.


Nintendo Switch Google Pixel XL 2 LG W7 Samsung Galaxy S8 Google Pixel 2 Sony Bravia A1 OLED Microsoft Xbox One X Apple iPhone 8

© 1998 - 2017 de Persgroep Online Services B.V. Tweakers vormt samen met o.a. Autotrack en Hardware.Info de Persgroep Online Services B.V. Hosting door True

*