Anti-spamprotocol Microsoft met brute force omzeild

Beveiligingsonderzoeker Dumitru Codreanu van BitDefender is erin geslaagd om, met goedkope hardware, een anti-spam-protocol van Microsoft te omzeilen door middel van een brute force-attack. Voor het kraken wordt nVidia Cuda gebruikt.

Het Postmark-protocol van Microsoft is bedoeld om de authenticiteit van een e-mailbericht te bevestigen. Het genereert een hash voor de titel en de geadresseerde van een nieuwsbericht. Daarvoor wordt een door Microsoft ontwikkeld algoritme gebruikt dat op Sha-1 is gebaseerd.

De authenticatie neemt enige tijd in beslag, tussen de tien en twintig seconden, en die tijd hebben spammers niet, zo redeneert Microsoft; het is voor hen slechts interessant om spam te verzenden als ze binnen korte tijd grote hoeveelheden e-mails de deur uit kunnen doen. Postmark werd in 2008 geïntroduceerd en wordt op dit moment alleen nog door Outlook, Outlook Express en Hotmail gebruikt.

Onderzoeker Codreanu stelt echter dat hij met relatief goedkope hardware in korte tijd geldige hashes kan generen. Daarvoor gebruikt hij een gpu in combinatie met het Cuda-framework van nVidia. Met een Geforce 8800 GT, een gpu voor de consumentenmarkt, slaagde hij erin vijf hashes per seconde na te bootsen, wat neerkomt op 432.000 hashes per dag. Daarbij is wel circa 6 procent van de gegenereerde hashes ongeldig.

Met duurdere hardware zouden nog veel betere resultaten worden bereikt. Met de Spartan 605-kit van Xilinx slaagde Codreanu erin om 34 Postmark-hashes per seconde te produceren, wat neerkomt op drie miljoen hashes per dag. Met de nagebootste hashes hebben spamberichten meer kans om het spamfilter te overleven; de spamfilters van Microsoft kennen berichten met geldige hashes een hogere authenticiteitsscore toe.

Codreanu acht de kans klein dat viagra- en cialis-spammers de onvolkomendheid in Postmark zullen gebruiken; de methode zou echter wel interessant zijn voor verspreiders van malware en phishers. Volgens de onderzoeker is het idee achter het Postmark-protocol niet in orde en moet Microsoft de methode voor het genereren van hashes omgooien. Hij zegt niet te kunnen schatten hoe eenvoudig dat voor Microsoft zou zijn.

QFT

Reacties (42)

[Lampuhkap]

Nu zie je maar weer waar Cuda goed voor is

Vind t wel knap overigens, dat ze t zo voor mekaar krijgen

[Reactie gewijzigd door Lampuhkap op 22 juli 2024 15:08]

[roy-t]

Tsja, ik vind dit ook wel een beetje naief algoritme van MS. "Maak een hash algoritme wat lang duurt, dan wordt spammen lastiger"

Als om de zoveeltijd computers sneller worden wordt dit algoritme dus elke dag minder waard, leuk dat ze nu met cuda al zo snel kunnen zijn, maar dit was slechts een kwestie van tijd.

Overigens klopt de titel niet, de beveiling is niet omzeild, als in dat nogsteeds een geldige hash nodig is (er is geen lek gevonden in het algoritme). Ze gaan nergens om heen. Het hele algoritme is gewoon overbodig gemaakt.

[Gomez12]

Tsja, ik vind dit ook wel een beetje naief algoritme van MS. "Maak een hash algoritme wat lang duurt, dan wordt spammen lastiger"

Waarom? Het principe lijkt me vrij goed als je bedenkt dat de meeste spam effectief is door de hoeveelheden, maak de hoeveelheden minder en spammen wordt weer duurder...

Als om de zoveeltijd computers sneller worden wordt dit algoritme dus elke dag minder waard, leuk dat ze nu met cuda al zo snel kunnen zijn, maar dit was slechts een kwestie van tijd.

Ach, elke maatregel tot nu toe is slechts een kwestie van tijd geweest, ik zie MS nergens zeggen dat dit the end of all spam is, het is slechts een verbetering...

5 spams per seconde met minder grote zombienetwerken is toch wel een forse afname van de hoeveelheid spam imho.

[MsG]

Dat geldt toch uiteindelijk voor nagenoeg alle encrypties? ; de tijd hoelang het duurt om het te kraken, want onkraakbaar is het uiteindelijk nooit.

[Guru Evi]

Nee, dit is geen encryptie, dit is een one-way hash zoals MD5. Echter Microsoft heeft een enorm slechte implementatie van de SHA1 hash (wat enkele ms op hedendaagse hardware is) vervolgens als 'anti-spam' functie verkocht.

Je kunt zelf ook zien dat die hashes binnen enkele jaren net zo snel als SHA1's kunnen worden gegenereerd en dan zit je vast met een protocol dat niets waard is en moet je een nieuw protocol bedenken die incompatibel is met het oude. SMTP is met minieme veranderingen al meer dan 25 jaren oud. Bedenk ook eens de impact op het milieu als ieder berichtje in de wereld, een CPU voor 20s 100% in beslag neemt. Als je dan nog steeds een doorvoer wilt van 100'en berichtjes per seconde (wat veel servers ondertussen wel kunnen) moet je een computerpark draaien enkel om de berichtjes te controleren.

Die persoon heeft een enorm parallelle methode gebruikt (CUDA) waar je eenvoudig en enorm goedkoop (~$50-150 voor een gemiddelde nVIDIA kaart die CUDA aankan) enkele 100'en cores hebt. Het probleem met CUDA is de precisie, hij kon evengoed een gemiddeld clustertje of botnet gebruikt hebben.

Een goede encryptie (zoals RSA, DSA, ...) met een degelijke sleutel (2048-bits) heeft op dit moment nog steeds 1000'en jaren nodig om een berichtje te kraken zelfs al neem je de wet van Moore mee in je berekening.

[Reactie gewijzigd door Guru Evi op 22 juli 2024 15:08]

[merlijn85]

1000'en jaren valt nogal tegen, en het is voor RSA statistisch aangetoont dat er elke 5 jaar ongeveer 128-bits meer gekraakt kunnen worden:

August 22, 1999 - RSA 512-bits gekraakt
November 2, 2005 - RSA 640-bits gekraakt
December 12, 2009 - RSA 768-bits gekraakt

Dat betekend dat 2048 bits RSA echt gekraakt zal zijn rond 2060, en er wordt al aangeraden om 2048 bits RSA niet meer te gebruiken na 2020.

[LuckY]

Ten eerste de bestanden en de bron: http://conference.hitb.or...Postmark%20Validation.zip
Het gaat hier niet om het kraken van berichten, het gaat hier om de hashes van de emails waarmee de integriteit geverifieerd wordt.
Encryptie op de email is leuk (PGP/GPG ) maar je hebt er weinig aan als de andere kant jou email niet kan lezen omdat jij zijn keys nog niet hebt.

Dus jij haalt nu zelf het hashen en encryptie door elkaar
En zoals Gomez12 zegt het is een tijdelijke patch die verdomde goed werkt, er is nog geen 1 protocol wat stand heeft gehouden als veilig naar al die jaren alles moet worden aangepakt om veiliger gemaakt de worden.

Ze kunnen bijvoorbeeld wel naar SHA2 implementaties die gebruik van van (SHA 256/384/512) zie bron:

Echter het zijn tijdelijke solutions

[Reactie gewijzigd door LuckY op 22 juli 2024 15:08]

[the_stickie]

Zo zie je maar dat de alsmaar krachtigere hardware een groeiend security probleem met zich meebrengt: bruteforcing kan alsmaar sneller. Daardoor worden beveiligingsprotocollen die tot voor kort nog als veilig tot zeer veilig beschouwd werden gereduceerd tot een kleine hindernis.
Dat betekent dat encryptie en authenticatie-beveiliging in een snel tempo krachtiger moet worden en dus ook steeds krachtigere hardware nodig heeft. Dat is natuurlijk een wedloop zonder einde!

[High-Voltage2]

Binnen afzienbare tijd ga je een co-processor in je PC zien die speciaal dienst doet voor encryptie. Ofwel krijgen de processoren een aparte pipeline voor encryptie instructies zoals de nieuwe Intel processor. Die heeft speciale encryptie instructies en waarschijnlijk een blokje in HW om het snel af te handelen.
Is nog een artikeltje van verschenen hier op T.net over de eerste (onofficiële) benchmarks. Overige prestaties waren gelijklopend, maar in encryptie blonk ie uit.

[flippy]

cuda is hier inderdaad heel goed in, dat kan je nvidia niet op afschrijven. ze hebben juist een product gemaakt wat bijzonder goed schaalbaar is met zulke lompe berekeningen, iets waar het ook voor gemaakt is. dat een ferrari 250+ kan rijden vind iedereen ook gaaf, totdat DE BESTUURDER van de ferrari dat ding door een lading van die amateurwierenners ploegt. (al zou dat niet eens zo slecht zijn )

[altaria1993]

Dit vind ik wel erg knap dan, en dat met een 8800GT, die ondertussen toch wel oud is, moet je voorstellen wat je met zo'n GTX480 OID kan doen, dat zou voor spammers waarschijnlijk een vrij goedkope investering zijn.

[Gomez12]

Ze verliezen wel een zooi zombiecomputers door dit soort dingen ( of verwacht je dat ze gewoon GTX480's naar zombiecomputers op gaan sturen en dan hopen dat die mensen het gaan installeren )

Afaik gaat er relatief weinig spam weg via 1 computer ( te makkelijk te traceren en af te sluiten )

[ILUsion]

Maar ze zouden bv. wel enkele van hun eigen computers kunnen inzetten om die hashes te genereren; of zoals aangetoond: gewoon via een FPGA die hashes berekenen. Bij het verzenden, stuurt de zombie eerst data naar de server, die stuurt de hash terug en voila.

[thegve]

Volgens mij proberen die botnets altijd zo weinig mogelijk zichzelf 'bekend' te maken, ze werken behoorlijk p2p, dit om het opsporingsinstanties zo lastig mogelijk te maken. Als ze dan consequent naar een beperkt aantal systemen requests gaan sturen word het veel makkelijker die netwerken op te doeken.

[p0st]

Vrij eenvoudige hardware, maar als ik die formule zo zie x'D
Is die formule trouwens de encryptie van MS of de formule die de encryptie doorbroken heeft??

[ingdas]

Die formule (afleiding) is een beetje basic kansrekenen.
Waarschijnlijk proberen ze met heuristieken en kansen de hashes met grote kans te produceren. (vandaar de 6% missers bij het omzeilen).

De werkelijke methode zal heel wat complexer zijn dan wat op die foto staat.

[cosmo_roel]

meeste spam komt van botnets voor zover ik weet. die hebben bij elkaar toch genoeg rekenkracht.

[altaria1993]

Hebben deze ook echter CUDA is dan de vraag, want nvidia heeft een erg klein marktaandeel met de CUDA-capable kaarten, (8 serie en hoger) en dan is alsnog de vraag dat als ze dat hebben, hoe veel het is.

[Niosus]

formule valt goed mee. Als je kijkt zie je er overal = tekens tussen staan. Er wordt dus gewoon iets uitgewerkt. De onderste regel is de volledige formule

[ciro-bonano]

Kwestie van de hash-lengte verdubbelen zodat het exponentieel moeilijk wordt om ze te bruteforcen lijkt me

[Verwijderd]

Die foto is toch gewoon een voorbeeld van kansbereking, wat later in digitale algoritmen word omgezet? Dit staat volgens mij buiten de functie om als voorbeeld te dienen, verder los van het verhaal.
Voor de rest wel leuk verhaal. Dan wachten we toch even wat langer op een mailtje, was vroeger ook....

[Oentje13]

Die formule wordt gebruikt om hashes te maken, noch te kraken. Als je goed kijkt zie je namelijk onderaan staan: P(x<2^ey)=(2^(e+1)-1)/(2^(e+1))
P staat voor een kans. De kans dat x<2^e*y is dus 0.924. Dit komt neer op 92.4%, en dus een kans van ca. 7.6%, rond de 6 dus, waarschijnlijk de kans dat een hash niet klopt.

[Reactie gewijzigd door Oentje13 op 22 juli 2024 15:08]

[High-Voltage2]

Die formule wordt gebruikt om hashes te maken, noch te kraken. Als je goed kijkt zie je namelijk onderaan staan: P(x<2^ey)=(2^(e+1)-1)/(2^(e+1))
P staat voor een kans. De kans dat x<2^e*y is dus 0.924. Dit komt neer op 92.4%, en dus een kans van ca. 7.6%, rond de 6 dus, waarschijnlijk de kans dat een hash niet klopt.

Je uitleg over kans ed klopt inderdaad, maar er is geen enkele verwijzing om aan te nemen dat de kans die daar berekend wordt effectief handelt over die 6% foutmarge. Tijdens die presentatie zijn misschien honderd kansberekeningen getoond en heeft de redactie er gewoon ééntje uitgenomen. Zelfs door afronden van e kom je niet aan 6%.
Zonder de betekenis van X, Y en v te weten is het zinloos hier uitspraken over te doen.

[Verwijderd]

Dat staat boven de slide. x en y zijn twee uniforme variable en v vertegenwoordigt het bereik. x en y zullen waarschijnlijk twee seeds zijn en v zal het bereik van getallen (dus 64bit = 18446744073709551616) zijn.

Wat hij doet is alle mogelijkheden relativeren naar een uniform bereik en dan op een interval kijken of deze kloppen. Als je zou kijken over een full bereik dan kom je uit op die 7,6 maar hij sluit al een hoop uit en hij werkt ook nog eens op een uniform interval dus dan kan het wel eens kloppen dat het allemaal terug wordt gedrongen naar 6%. Er zijn dus al een hoop oplossingen waarvan hij voorhand weet dat die niet kloppen en die sluit hij al uit.

Als men het fijne wil weten dan moet men het proefschrift inzien om te kijken of het allemaal wel echt klopt. Een slide opzicht zegt niet veel, er moet nog een onderbouwing bij.

Maar iets interessanter. Die Spartan en de Nvidia Cuda processoren zijn in principe eigenlijk hetzelfde. De techniek die er achter zit enzo en de manier van werken wijken niet veel van elkaar af. Ik weet niet meer zeker of het Nvidia of ATI was maar een van de twee gebruikt Xilinx spullen om alles te ontwerpen. Het ding is dat in die Nvidia er uiteindelijk een chip synthesizer overheen gaat welke het allemaal omzet naar silicium.

Dus wat hij nou eigenlijk zegt is ipv 300 euro te investeren in een high-end video kaart kun je beter een spartan kitje en een hoop gespeciliseerde software kopen ben je sneller ook.

[Reactie gewijzigd door Verwijderd op 22 juli 2024 15:08]

[High-Voltage2]

Als men het fijne wil weten dan moet men het proefschrift inzien om te kijken of het allemaal wel echt klopt. Een slide opzicht zegt niet veel, er moet nog een onderbouwing bij.

Dat is net wat ik probeer te zeggen...

Maar iets interessanter. Die Spartan en de Nvidia Cuda processoren zijn in principe eigenlijk hetzelfde. De techniek die er achter zit enzo en de manier van werken wijken niet veel van elkaar af. Ik weet niet meer zeker of het Nvidia of ATI was maar een van de twee gebruikt Xilinx spullen om alles te ontwerpen. Het ding is dat in die Nvidia er uiteindelijk een chip synthesizer overheen gaat welke het allemaal omzet naar silicium.

Whut?!? Die CUDA processoren zijn echt geen FPGA's. Wat je in een FPGA steekt is zuiver hardwarematig, bij die CUDA heb je nog altijd een software laag. Daarom dat die relatief goedkope Spartan zeven keer meer hashes blaast dan de CUDA.
Je kan die CUDA processoren wel ontwikkelen met behulp van een Xilinx tool en met behulp van een HDL (Verilog of VHDL bv), maar daarom is een CUDA processor nog geen FPGA zoals Xilinx die ook ontwikkelt/verkoopt.

[Verwijderd]

Mwah je hoeft het proefschrift niet in ze zien om bedenken wat er hier aan de hand is ik had het meer over het verhaal als geheel terwijl jij vast zat op dit specifiek probleem.

Ik zeg ook niet dat het FPGA's zijn ik zeg dat het verijdelde FPGA's zijn welke veel gemeen hebben met de echte, dat had je ook kunnen halen uit het woorden "silicium synthesiser".

[Xthemes.us]

Daarbij is wel circa 6 procent van de gegenereerde hashes ongeldig.

Staat in het artikel zelf.

Alhoewel ik het nog een keer lees verwijs je hier zelf waarschijnlijk al naar..

[Reactie gewijzigd door Xthemes.us op 22 juli 2024 15:08]

[bartvb]

We zouden het na kunnen kijken als er een bron in het artikel stond

[Oentje13]

Ik gok niet maar wat. Als er een vergelijking staat met P(x=y) dan is P de kans en X de zogeheten stochast. Het is dus in ieder geval om een kans te berekenen. Degene die dit heeft bedacht wil het natuurlijk ook een beetje goed uit de verf laten komen, en met een beetje goede wil kan je bij e ook zeggen dat e 2.7 is i.p.v. een getal met oneindig cijfers achter de komma. En met een beetje goede wil kan je zo 7.6 'afronden' naar 6.

[Verwijderd]

Ja, je hebt vast wel eens een uurtje statistiek gehad op de middelbare school. Je moet niet overschatten wat je daar geleerd hebt.

Er staat inderdaad 'iets' met een kans. Maar e afronden op 2.7? Kom op! Je blijft gewoon analytisch werken tot op het allerlaatste moment. Je hebt gewoon geen flauw idee waar het over gaat. Waarschijnlijk weet je niet eens de eigenschappen van 'independent random variables'. Het heeft vast iets te maken met kansen, maar je hebt geen flauw idee wat het interval is, welke variabelen X en Y zijn en of dit een tussen- of eindberekening is.

Ik weet dat de gemiddelde persoon op deze site niet bepaald goed is onderlegd in kansrekening, maar pretendeer er in ieder geval dan niet iets zinnigs over te kunnen zeggen doordat je weet waar de P voor staat.

Dit is een minder aardige versie van wat high-voltage2 hieronder zegt.

[Reactie gewijzigd door Verwijderd op 22 juli 2024 15:08]

[mark184]

de formule op de foto lijkt me duidelijk.....

[taeke18]

Hmm, als je mij het zou kunnen uitleggen vind ik het persoonlijk heel erg knap... Wat ik er van zie is het zeer hoge wiskunde wiskunde van het allerhoogste niveau en ik snap er geen ruk van. Zelfs niet van die kleine uitleg er boven.

Respect voor het persoon die dit bedacht heeft, maar eigenlijk ook weer niet omdat dit niet fijn is voor mensen met ene hotmail account.

Edit:

Klopt het dat ik 2n-1/2n zie??

zo ja dan is dit wel een hele simpele berekening dat ik dat niet eerde zag xD

[Reactie gewijzigd door taeke18 op 22 juli 2024 15:08]

[Xirt]

Het heeft iets met kansberekening te maken en het zou best kunnen dat dat dus te maken heeft met het aantal gegenereerde hashes of de kans dat deze hashes als 'correct' gezien worden. Verder zal er waarschijnlijk extra informatie beschikbaar zijn geweest in de slides die deze formule ondersteunt / verduidelijkt.

[High-Voltage2]

Hmm, als je mij het zou kunnen uitleggen vind ik het persoonlijk heel erg knap... Wat ik er van zie is het zeer hoge wiskunde wiskunde van het allerhoogste niveau en ik snap er geen ruk van. Zelfs niet van die kleine uitleg er boven.

Het enige wat ik zie is een integraaltje^*... De voorwaarde voor x en y is dat ze uniform verdeeld zijn, onafhankelijk van elkaar zijn en binnen het interval [0, v] liggen.

Dat is echt geen super hoge wiskunde zoals jij doet uitschijnen.



<sub>Edit:
* Integraal over een interval om de kans te berekenen van een continu uniform verdeelde variabele.</sub>

[Reactie gewijzigd door High-Voltage2 op 22 juli 2024 15:08]

[kozue]

Wat ik daar zie, ziet er niet super moeilijk uit. Die integraaltjes en delingen heb ik ook ooit gehad in m'n eerstejaars informatica, en als ik me nog iets van dat vak kon herinneren zou ik precies weten wat die formule doet. Helaas is dat voor mij te lang geleden, dus verder dan het herkennen van notaties kom ik niet, maar "zeer hoge wiskunde" zou ik het niet noemen...