Hash collision maakt dos-aanval op webservers mogelijk

Meerdere programmeertalen zijn kwetsbaar voor een denial of service-aanval door het veroorzaken van hash collisions. Met een post-request kan een webserver offline worden getrokken. Onder meer ASP.NET, PHP en Java zijn kwetsbaar.

Het beveiligingsbedrijf n.runs heeft de kwetsbaarheid naar buiten gebracht. Door misbruik te maken van hash tables in programmeertalen kunnen kwaadwillenden de cpu van een webserver volledig in beslag nemen, waardoor deze geen andere requests meer aankan. Daarvoor moeten hash collisions worden veroorzaakt, waarbij meerdere waarden dezelfde hash krijgen.

PHP5, Java en ASP.NET zijn kwetsbaar, net als de javascript-engine V8, die door node.js wordt gebruikt. In sommige gevallen zijn ook PHP4, Python en Ruby kwetsbaar; dat hangt af van de gebruikte versie en of de taal draait op een 32bit- of 64bit-server.

Omdat veel programmeertalen standaard een maximale uitvoeringstijd aan scripts stellen, is het nodig om constant nieuwe hash collisions te blijven sturen. Volgens n.runs is voor een aanval op een webserver met PHP5 en een Core i7-processor 70 tot 100 kilobit per seconde aan bandbreedte nodig om één core bezig te houden. Met een gigabit-verbinding kan één aanvaller zelfs 10.000 cores in een dergelijke configuratie feitelijk uitschakelen.

Microsoft heeft erkend dat ook ASP.NET kwetsbaar is en heeft een update voor de Forefront-firewall uitgegeven die eventuele aanvallen moet herkennen. Overigens kondigde Microsoft niet veel later een noodpatch aan die een kritiek Windows-probleem moet verhelpen. Daarbij gaat het hoogstwaarschijnlijk echter om een ander probleem, omdat ook desktopversies van Windows zijn getroffen.

Reacties (70)

[TvdW]

The maximal POST request size is typically limited to 8 MB, which when filled with a set of multi-collisions would consume about four hours of CPU time on an i7 core.

Ik hoop toch echt dat hier héél binnenkort een patch voor wordt uitgebracht...

-edit-
Kom dit net tegen bij de PHP 5.4RC4 release notes:
Added max_input_vars directive to prevent attacks based on hash collisions

Gerelateerd, lijkt me?

[Reactie gewijzigd door TvdW op 23 juli 2024 14:27]

[Hadron]

De beschrijving heeft het over het misbruiken van een zwakte in het hash-algoritme, die werkt omdat je precies weet:

• Welk algoritme het is
• Welke constanten worden gebruikt

Op zich is het beperken van de POST-variabelen inderdaad een gedeeltelijke optie, maar als je ziet hoe weinig requests er nodig zijn om de overload te triggeren, weet ik niet of die oplossing afdoende is.

Als je naar de beschrijving kijkt, is er een andere oplossing die veel meer voor de hand ligt: Het instelbaar maken van de constanten. Als je de constanten niet weet, kun je het truukje niet uithalen, en gaat de aanval onderuit.

Maar ja, daar zijn weer een aantal dingen tegen:

• Het algoritme zal, vanwege de performance, waarschijnlijk hard-coded zijn, en het veranderen van de constanten is niet zo makkelijk als het lijkt
• Er zijn mensen die de hashes voor hele andere doeleinden gebruiken, en er vanuit gaan dat ze altijd dezelfde resultaten geven

Het laatste is niet zo'n sterk argument: een beter hash-algoritme zorgt namelijk voor een grote boost in performance, en dus moet je er eigenlijk niet op rekenen dat de hash tussen sessies hetzelfde blijft. Helaas zijn er programmeurs die zich daar niet zoveel van aantrekken

[Verwijderd]

dat is toch de functie van een hash, altijd dezelfde waarde teruggeven, compleet deterministisch. Als jij een wachtwoord opslaat met een hash en een paar sessies later wil je het ingevoerde wachtwoord controleren, moet je wel met dezelfde hash functie werken.

Wat wel kan werken is applicatiespecifieke constanten gebruiken, dat je bijvoorbeeld voor jouw applicatie 1 keer wat constanten random genereerd. Maar ik zie hier ook bergen van problemen bij opduiken.

[Hadron]

Ja en nee... Het hangt een beetje af van welk hash-algoritme je bedoelt.

De in het document genoemde algoritmen (DJBX33A/X) hebben een iets ander doel dan de hash-algoritmen waar jij op doelt (MD5/SHAx). MD5 en SHA zijn bedoeld om een hash te berekenen over grote hoeveelheden data, die bij een kleine wijziging een groot verschil geeft, zodat ze geschikt zijn om te controleren of de data gewijzigd is.
Daarnaast is het de berekening eenrichtingsverkeer: Van data naar hash is eenvoudig, van hash naar data (met name met veel data) is moeilijk.
Het algoritme is redelijk complex, en eet nogal wat processorkracht, maar de voordelen die het met zich meebrengt wegen daar tegen op.

DJBX33A en X zijn bedoeld om over een relatief kleine hoeveelheid data een unieke hash te berekenen, die gebruikt kan worden om te bepalen waar een element in het geheugen geplaatst moet worden. Ze zijn relatief simpel, en gebruiken weinig processorkracht. Als ze dat wel zouden doen, loopt de snelheid van de hashtables erg terug, en verliezen ze hun nut. De afweging is dus anders: Het is een weloverwogen afweging tussen snelheid en uniekheid van het resultaat.

Waar ik op doelde was dat er programmeurs die algoritmen als DJBX33A/X gebruiken in situaties waar MD5/SHAx voor ontworpen zijn. Die (wat mij betreft) foute keuze zorgt ervoor dat DJBX33A/X niet makkelijk ingewisseld kan worden voor een ander algoritme, zelfs niet als alleen de constanten veranderd worden.


Maar toch: I stand corrected. Dank voor het excuus om een extra toelichting te typen

Edit: Wat betreft de constanten: dat lijkt mij meer iets voor een configuratiefile, of iets dat bij het (her)starten van apache/IIS/nginx/lighttpd/etc. bepaald wordt.
Als je dat in je applicatie zelf moet doen, wordt het iets dat je vergeet

[Reactie gewijzigd door Hadron op 23 juli 2024 14:27]

[Gtoniser]

Ja, dat is dus iets wat de suhosin patch al jaren doet trouwens met suhosin.request.max_vars

[wootah]

bedankt voor de tip, die kende ik nog niet.
Meteen maar eens gecompileerd en geïnstalleerd

[Navi]

En de patch die ervoor zorgt dat heel veel code niet meer goed werkt, bv in bepaalde CMS'en.

[geez]

De Debian package van php5 wordt zelfs standaard gebouwd met de Suhosin patch:

http://packages.debian.org/squeeze/php5

edit @ Navi: Lijkt me dus sterk dat er bepaalde code niet meer goed werkt.. Debian is niet bepaald een niche-distributie.

[Reactie gewijzigd door geez op 23 juli 2024 14:27]

[Verwijderd]

Het is wel degelijk zo dat bij een te restrictieve configuratie van de Suhosinpatch veel bestaande systemen niet meer werken.

Het punt met de Suhosinpatch danook is dat het weliswaar een aantal aanvalsvectoren verkleind, maar effectief gezien geen echte oplossing is zolang bijv de CMS systemen zelf kwetsbare code bevatten.

Het is danook geen turnkey beveiligingsoplossing, maar meer een tweakable configurator om je PHP installatie met een minimaal nodige resource-, en featureset te laten werken, en dat op zich is natuurlijk altijd wel verstandig.

Zorg ervoor dat voordat je Suhosin op een productiesysteem loslaat dat je ook echt alle functies van de systemen die je wilt hosten hebt getest, met name met cachingsystemen zorgt Suhosin vaak voor problemen.

[Foamy]

MS heeft al een noodpatch klaarstaan:

http://blogs.technet.com/...sp-net-vulnerability.aspx

[mario963]

Microsoft heeft zojuist voor ASP.NET een security fix uitgebracht tegen deze Hash table exploit.

"The security update we are releasing resolves a publicly disclosed Denial of Service issue present in all versions of ASP.NET. We’re currently unaware of any attacks on ASP.NET customers using this exploit, but we strongly encourage customers to deploy the update as soon as possible.

We are releasing the security update via Windows Update and the Windows Server Update Service. You can also manually download and install it via the Microsoft Download Center. We will release the update on Thursday, December 29th at approximately 10am Pacific Time (US and Canada). We are announcing it ahead of time to ensure that administrators know that the security update is coming, and are prepared to apply it once it is available."

Meer informatie is te vinden op de blog van Scott Gutherie http://weblogs.asp.net/sc...ng-thursday-dec-29th.aspx

[wootah]

klinkt meer als een quick fix dan een echte fix.
Voorlopig is dit dan nog wel steeds de beste manier om dit soort ongein buiten de deur te houden.
Maar ja, misschien dan toch weer terug naar html only pagina's die er zo uit gaan zien: http://www.theworldsworstwebsiteever.com/

PHP4, Python en Ruby kwetsbaar; dat hangt af van de gebruikte versie en of de taal draait op een 32bit- of 64bit-server.

ik heb dan nog het geluk dat ik php 4 heb, en dan niet eens op een x86 gebaseerde architectuur. of dit dan veel veiliger is weet ik ook niet
echt duidelijk daarover zijn ze namelijk niet...

[Reactie gewijzigd door wootah op 23 juli 2024 14:27]

[sfranken]

php4... welcome to the stone age?

[thof]

Ik zou dit graag eens uitproberen op mijn testserver om te zien hoe hard het nou precies gaat. In de advisory (http://www.nruns.com/_downloads/advisory28122011.pdf) kan ik zo niet vinden hoe ik het gemakkelijk met PHP kan reproduceren. Iemand al een scriptje gemaakt om een POST request met collision te maken?

PHP heeft in versie 5.4.0RC al wel een patch gemaakt om het probleem te beperken. Daar hebben ze een max_input_vars geintroduceert. (http://www.php.net/archive/2011.php#id2011-12-25-1)

[Ergomane]

De hashbucket bepaling voor numeric keys is zelfs nog simpeler. Daar maakt het volgende script gebruik van http://nikic.github.com/2...olliding-a-PHP-array.html .

Op een Core i5 750 duurt het inserteren van 65k entries 18 seconden.

[thof]

Interresant, op mijn mobile Core i7 2630QM duurt het:
Inserting 65536 evil elements took 24.965979099274 seconds
Inserting 65536 good elements took 0.022286891937256 seconds
Neemt alleen geen 100% CPU load.

Is het werkelijk dat deze gegenereerde numeric keys dus even in een POST-request gewrapped dienen te worden om deze vulnerability reproduceren?

[Ergomane]

Het neemt geen 100% CPU load omdat het PHP process maar een core gebruikt. Een Core i7 heeft 4 cores dus zou je ~25% belasting moeten zien.

Probeer het script eens 4x parallel te starten.

[Reactie gewijzigd door Ergomane op 23 juli 2024 14:27]

[thof]

Klopt, dat had ik ook begrepen. Het gaat meer om het laatste deel van mijn reactie. Hoe kunnen we het reproduceren om te controleren hoe vatbaar onze systemen zijn? Is het te kort door de bocht om de gegenereerde keys te gebruiken in een postrequest en deze op de testserver af te vuren?

[Ergomane]

Dat kun je idd. doen.

Het lijkt me echter een vrij overbodige exercitie, tenzij je wilt testen of de suhosin patch oid het gewenste resultaat heeft.

[zvbhvb]

Hier bij perlmonks hadden ze het in 2003 ook al over.

http://www.perlmonks.org/?node_id=262191

[bassekeNL]

Dat is een andere vuln. Perl is (als enige?) veilig voor de aanval uit het artikel.

[SKiLLa]

Dat komt omdat Perl tegenwoordig een ander hashing-algo gebruikt dan de 'standaard' DJBX33A. Perl v5.0x en ouder zijn wel kwetsbaar (die gebruiken wel het DJBX33A algo).

[Mr_gadget]

Maar werkt deze aanval nu daadwerkelijk? Je kan niet zomaar de cpu opdrachten geven om hashes te generen toch? Of geef je de post data altijd een hash mee en die wordt vervolgens in een database gestopt? Kan iemand het verduidelijken?

[djexplo]

ALs je naar de website het volgende stuurt:
index.php?abb=12&bb=13&cb=14&dbb=15

Worden de geposte variablen in een POST array gezet
123, abb = 12
132, bb = 13
312, cb = 14
313, dbb = 15

Waar bij de eerste getallen de hash waarde aangeven, die gebruikt word om snel te kunnen zoeken als je b.v. POST("cb") opvraagt

Voor de hash waarde word haast altijd Daniel J. Bernstein, Times 33 with Addition gebruikt.

Dit houd in dat je bij "abc" :
hash=asci(a')
hash=hash*33+asci(b')
hash=hash*33+asci(c')

Waarbij hash een int 32 is die mag overflowen

Maar er zijn natuurlijk strings van 2 letters te bedenken die de zelfde hash waarde opleveren. Maar dat betekend dat als je die combineert tot 4 letters ze weer de zelfde waarden opleveren. Dus je kan een lijst met 1000en woorden maken die de zelfde hash hebben.

Op het moment dat deze hash-collision optreed, kan voor deze entry(getal) geen hash-table search meer worden gebruikt, maar moet echt lettertje voor lettertje worden vergeleken wat eindeloos duurt als er 10000en woorden zijn op die entry. Deze langzame search word bij het toevoegen van elke variable herhaald, om te kijken of er al een variable met die naam bestaat.

[Reactie gewijzigd door djexplo op 23 juli 2024 14:27]

[Verwijderd]

Wordt dat dan niet een GET-array ?
POST-variabelen zitten in de headers geloof ik, en niet in de link

[CyBeR]

Wordt dat dan niet een GET-array ?
POST-variabelen zitten in de headers geloof ik, en niet in de link

Ja, maar daarvoor geldt hetzelfde. POST is alleen wat bruikbaarder omdat 't niet in de headers van de request zit maar in de body, en dus een potentieel veel grotere hoeveelheid data kan bevatten.

[tweakerbee]

De POST-gegevens zitten gewoon in de body, niet in de headers. Bij een GET-request zit het direct in de request line (waar ook het pad staat).

[Verwijderd]

Is de GET ook niet beperkt tot x tekens?

[thof]

GET is inderdaad beperkt tot een bepaald aantal tekens, bij POST is dit ook het geval (vaak serverside pas) maar deze is vele malen groter dan bij een GET.

[Brantje]

Ik denk dat het gaat om het genereren van een hash, bijvoorbeeld wanneer je 2x hoi md5'd. Dan heb je een hash collision.

Voor PHP geld het volgende:

== PHP 5 ==
PHP 5 uses the DJBX33A (Dan Bernstein's times 33, addition) hash function and parses POST form data into the $_POST hash table.
Because of the structure of the hash function, it is vulnerable to an equivalent substring attack.
The maximal POST request size is typically limited to 8 MB, which when filled with a set of
multi-collisions would consume about four hours of CPU time on an i7 core.
Luckily, this time can not be exhausted because it is limited by the max_input_time (default configuration: -1,
unlimited), Ubuntu and several BSDs: 60 seconds) configuration parameter.
If the max_input_time parameter is set to -1 (theoretically: unlimited), it is bound by the max_execution_time configuration parameter (default value: 30).
On an i7 core, the 60 seconds take a string of multi-collisions of about 500k.
30 seconds of CPU time can be generated using a string of about 300k.
This means that an attacker needs about 70-100kbit/s to keep one i7 core constantly busy.
An attacker with a Gigabit connection can keep about 10.000 i7 cores busy.

Gewoon je scripts een timelimit geven en max_input_vars gebruiken dan ben je veilig.

[Pyrus]

Nee, dat is gewoon twee keer dezelfde input hashen en dat dan hetzelfde uitkomt is logisch en de bedoeling. Een botsing is als twee verschillende input strings dezelfde hash opleveren, wat niet de bedoeling is.

[Ergomane]

Hash collisions zijn voor een hashtable niet direct een probleem. Daarom worden relatief simpele hash functies gebruikt. Zie http://en.wikipedia.org/wiki/Hash_table

Het probleem ontstaat als een aanvaller de keuze van sleutels heeft waarbij de data in slechts een of enkele hashbuckets terecht komt. De performance van de hashtable wordt op dat moment gelijk aan zijn worst-case scenario. Voor een paar entries is dat geen probleem, maar wel als je duizenden of miljoenen keys in dezelfde bucket moet verstouwen.

[Reactie gewijzigd door Ergomane op 23 juli 2024 14:27]

[StM]

Hij slaat de POST data van het request op in een hashtable. Het sturen van een 'gemodificeerd' POST request is dus al voldoende om deze aanval uit te voeren. Letterlijk iedere website die 1 van de genoemde talen gebruikt is hier in principe vatbaar voor op dit moment.

[Reactie gewijzigd door StM op 23 juli 2024 14:27]

[Verwijderd]

het eerste gedeelte is denk ik een probleem van backward compatibility, daarnaast, moeten developers niet gewoon altijd rekening mee houden dat iets misbruikt kan worden? ik bedoel als ik een server applicatie zou schrijven zou ik ten alle tijden rekening houden dat alle inkomende data per definitie corrupt zou zijn en *mogelijk* correct is (iedereen is een terrorist totdat gecheckt is zij geen wapen bij te hebben in plaats van, iedereen die mij bereikt gebruikt de applicatie waar het voor bedoeld was. puur omdat de input *een* kans heeft corrupt te zijn) en lijkt mij niet zo zeer een taal probleem. checken op corruptie kost kracht, cache systemen leveren snelheids bevorderingen maar op te grote schaal zal dat tegen werken. voor de client is het makkelijk iets de server te vragen waar de server 1000 keer meer cpu cycles moeite voor moet doen dat te uitvoeren waar je vervolgens niets mee doe.

/mogelijke onzin vanaf hier
ik neem aan dat hash tables gewoon als cache gediend word (value imput combinaties doorgerekend en opgeslagen en een nummer gegeven word met als uitkomst zodat er niet meer gerekend hoeft te worden om de zelfde uitkomst te krijgen met al eerdere opdrachten)? tot de table te groot word (omdat max van integer lang kan zijn om zomaar doorheen te zoeken en de keys dynamic zijn) en de decay table en checken op dubbele uitkomsten van verschillende inputs (om een key te maken) en dat ook zodanig groot worden plus verdeeld meerdere cores dat de overhead van het systeem dat het sneller moest maken najuist een factor word dat het langzamer maakt.

dit is toch geen taal fout maar meer een logica fout (niet eens echt een fout maar een limiet van een systeem)? en hoe is dat "magisch" opgelost? gewoon geen table bijhouden? je kunt een cpu toch niet meer laten doen dan logisch mogelijk is¿ ergens gaat het ene ten koste van het ander, ook de ene speed upgrade ten koste gaat van langdurigheid (hacks misbruiken zo een systeem wat iets sneller moest maken).
/einde mogelijke onzin

oh.... ik les hieronder(djexplo) een uitleg, ik dacht een keer iets logisch gezegd te hebben zonder kennis denk aardig in de buurt te komen met gezond verstand. rondom invoer in een systeem leek mij bijna eindeloos de cache te vullen tot dat meer tijd kost dan de werkelijke bewerking waar het gecacht voor werd.

mini voorbeeld, jij stuurt a=1 en b=2. de bewerking is a*b/a/1.1337*666(gewoon lange bewerking dat tijd kost). dat cache ik met een hash van a*256+b*65536. dat oproepen is sneller dan de berekening. maar als er 10000 hashes zijn word het hash opzoeken langzamer dan de berekening (met voorberekening om die key te krijgen en wat extra overhead die table schoon te houden over tijd)

_{voelt ergens onzin uit te kramen, maar wilt gewoon meedoen}

[Reactie gewijzigd door Verwijderd op 23 juli 2024 14:27]

[afraca]

Overigens gaat het hier om al redelijk oude theorie:

The original theory behind this attack vector is described in the 2003 Usenix Security paper
“Denial of Service via Algorithmic Complexity Attacks” by Scott A. Crosby and Dan S. Wallach,
Rice University

Link naar de betreffende paper:
http://www.cs.rice.edu/~s...Wallach_UsenixSec2003.pdf

Hier word iets meer ingegaan op de technische achtergrond, een leuke introductie in datastructuren voor de leek

[AVee]

Ja, en dan wordt ook duidelijk dan webservers weliswaar een voor de hand liggend doelwit zijn, maar dat potentieel alle externe input die in een hash tabel terecht komt een doelwit is. Soap calls, mail headers, indexes in databases of namen in een adresboek om maar wat zaken te noemen.

[Verwijderd]

De fix in PHP 5.4 RC4 is nog niet strikt genoeg om te voorkomen het het CPU gebruik naar zijn max gaat (is al uitgetest):

* de "max_input time" staat standaard op oneindig. Mijn advies is om deze op 30 seconden te zetten
* de "max_input_vars" staat standaard op 1000. Mijn advies is om deze op 100 of 50 te zetten.

Maar zelfs met deze aanpassingen zijn de standaard PHP instellingen nog niet veilig te noemen. Wij hebben zelfs al een security patch moeten ontwikkelen voor deze PHP versie om deze "acceptabel veilig" te maken.

[AVee]

Die max_input_vars fix is prima toch? Dat is een prima manier om te voorkomen dan PHP tijd verspilt aan het verwerken van een POST met veel te veel velden. En een post met veel velden is de enige manier om dit probleem te triggeren, dus daarmee ben je ruimschoots "acceptabel veilig" volgens mij.

[wiert.tweakers]

Het grappige is: Perl 5.8.1. heeft dit al in 2003 gefixed zie bijvoorbeeld https://www.google.com/se...%2B5.8.1%2B2003%2Bhashdos

[Verwijderd]

70 tot 100 kilobit per seconde lijkt weinig. Kan iemand me uitleggen hoe dit 1 core bezig houdt? Zeker aangezien een enkele computer al dataoverdracht van megabytes per seconde kan bewerkstelligen van en naar een andere computer. (Ja, ik lees het verschil tussen bits en bytes, al zou deze factor 8 hier niet de verklaring zijn lijkt me.)

[Hadron]

Nou ja, de truuk zit'm in het algoritme.

Het doel is om een lijstje bij te houden, waarbij we de items in het lijstje op basis van een index snel terug kunnen vinden. Denk bijvoorbeeld aan een telefoonboek, waar je Hadron onder de H terugvindt, en Senzune onder de S. In dit geval bepaalt eerste letter van de naam waar het item in het lijstje terugkomt, waarbij we ervan uitgaan dat de eerste letter redelijk uniek is.

De uniciteit is belangrijk: Doordat de hash uniek is, kun je items snel op de goede plek neerzetten en snel terugvinden. Tegelijkertijd is dat precies waar deze aanval gebruik van maakt... Een kleine demonstratie

Laten we nu zeggen dat ik alleen maar items met een S toevoeg (Sanne, Senzune, Simon). Het algoritme doet het volgende:

• Pak het eerste element (Sanne)
• Bepaal de eerste letter (S -> de 19e letter)
• Ga naar de 19e plek in het geheugen
• Staat er iets? Nee -> Zet Sanne daar neer
• Pak het volgende element (Senzune)
• Bepaal de eerste letter (S -> 19)
• Ga naar de 19e plek
• Staat er iets? Ja, Sanne staat er al
• Ga naar de 20e plek
• Staat er iets? Nee -> Zet Senzune daar neer
• Pak het volgende element (Simon)
• Bepaal de eerste letter (S -> 19)
• Ga naar de 19e plek
• Staat er iets? Ja, Sanne staat er al
• Ga naar de 20e plek
• Staat er iets? Ja, Senzune staat er al
• Ga naar de 21e plek
• Staat er iets? Nee -> Zet Simon daar neer

Je kunt je voorstellen dat dat lang duurt als je de lijst aanvult met Sanjay, Spanner, Spinlock, Sun-Tzu, Swiffer, enzovoorts. Als daarnaast het berekenen van de plek ook even duurt, heb je een redelijk efficiënte aanval, die met weinig data veel kracht trekt.

Als je 1000 items hebt, zou het ideale hash-algoritme het volgende doen:

• 1000x hash berekenen
• 1000x controleren
• 1000x wegschrijven
• Totaal aantal operaties: 3000

Met deze aanval gebeurt er het volgende:

• 1000x hash berekenen
• 500.500x controleren
• 1000x wegschrijven
• Totaal aantal operaties: 502.500

Om een quote te misbruiken:

"Well, there's your problem..."

Edit: Redenering achter algoritme verduidelijkt

[Reactie gewijzigd door Hadron op 23 juli 2024 14:27]

[Verwijderd]

Het is niet zo zeer het toevoegen dat lang gaat duren, de eerstvolgende lege plaats (voor een hash) kan je gerust bijhouden bij het eerste element waardoor het toevoegen steeds O(1) blijft.

Het is het opzoeken dat véél langer gaat duren. Als je verwacht dat een item op plaats 19 staat en het item op plaats 19 geeft aan dat er eigenlijk meerdere waarden waren die op plaats 19 wouden staan dan wordt het algoritme verplicht om lineair te gaan zoeken door alle collisions en dat gaat net heel traag worden bij een groot aantal collisions.

Ook dit euvel kan je oplossen door je collisions bijvoorbeeld gesorteerd te bewaren (er bestaan nog andere oplossingen), daardoor wordt zoeken O(lg n), maar toevoegen wordt tevens ook O(lg n) en dat wordt dan weer minder interessant omdat het geacht wordt dat collisions zelden voorkomen. Een betere hashfunctie gebruiken is dus de beste oplossing.

[Reactie gewijzigd door Verwijderd op 23 juli 2024 14:27]

[Hadron]

Eens. Een betere hash-functie is een betere oplossing.

Overigens, ik zie nog een reden waarom die zoek-optimalisatie niet echt werkt. Wat je voorstelt is eigenlijk een binaire boom. Op zich lijkt dat wel een oplossing, maar ook daar kan ik een soortgelijke aanval op verzinnen: Als je consequent waarden aangeeft die links terecht moeten komen, krijg je een scheefgroei. Het effect daarvan is vrijwel hetzelfde: Bij elke toevoeging en zoekactie moet de boom volledig doorlopen worden, en zit je nog steeds slecht.

De narigheid is dat je nog steeds precies weet in welke situatie het misgaat, en dat je met een beetje kwaaie wil waarschijnlijk nog steeds dezelfde fout kunt triggeren.

[Verwijderd]

Wat je initieel beschreef is een closed hash table, een tabel waarin de te vinden waarden opgeslagen worden (voor strings zal dat een pointer naar de waarde zijn).

Deze hashtabel vorm is om twee redenen helemaal niet geschikt voor webservers:

1. De tabel moet groeien als er meer inhoud aangeboden word dan de tabel aan pointers/waarden kan vasthouden en 20% of meer overcapaciteit is gewenst, zelfs als alles netjes gespreid wordt door de hashfunctie.

2. Als het aantal waarden toeneemt moet de tabel groeien en dat betekend dat alle hash waarden ook veranderen en alles opnieuw gehashed moet worden.

Om die reden alleen zou ik iemand die zoiets in een webserver of java/.net code plaatst waar het aantal aangeleverde elementen van te voren niet bekend is, gelijk over laten stappen op een ander type hash table.


Die andere meer praktischer vorm is minder kwetsbaar en heet open hash table.

Hier heb je een wat aantal buckets en het hash algoritme bepaald in welke bucket een aangeleverde waarde thuishoort. De buckets zelf kunnen groeien zonder dat er opnieuw gehashed moet worden. Wel is zo dat bij extreme aantallen waarden, het beter is om aan het begin meer buckets te hebben om zo de inhoud per bucket te minimaliseren.

Een bucket zelf, kan op meerdere manieren vorm gegeven worden, het kan een array zijn, een list of een tree. Belangrijk is dat er altijd plek is, ook als je maar 1 bucket hebt en de hash als optimalisatie eigenlijk uitgeschakeld is zoals deze aanval veroorzaakt.

Zo'n aanval als deze zal pas bij het zoeken in de hashtable voor problemen gaan zorgen en die stap kun je voorzijn door eerst te controleren hoeveel items er zijn opgeslagen. Dit wordt doorgaans apart bijgehouden van de opgeslagen waarden.

Zijn het er meer dan reël is, dan ruim je doe boel op en stop de verwerking. Zo kan je server niet in de positie gebracht worden waar om een waarde te vinden alle aangeleverde waarden sequentieel afgelopen en vergeleken moeten worden.

Ik ben het dus niet eens met de mening dat de hash functie verbeterd moet worden. Het probleem zit namelijk niet in de functie maar in wat er daarna gebeurd, namelijk hoe worden de waarden opgeslagen nadat bepaald is waar de te zoeken waarde zou moeten staan.

Nog beter is om tijdens het vullen van de hash tabel al in te grijpen als je weet dat meer dan N items echt niet de bedoeling kan zijn.

[Reactie gewijzigd door Verwijderd op 23 juli 2024 14:27]

[CyBeR]

70 tot 100 kilobit per seconde lijkt weinig. Kan iemand me uitleggen hoe dit 1 core bezig houdt? Zeker aangezien een enkele computer al dataoverdracht van megabytes per seconde kan bewerkstelligen van en naar een andere computer. (Ja, ik lees het verschil tussen bits en bytes, al zou deze factor 8 hier niet de verklaring zijn lijkt me.)

Dat is de gemiddelde snelheid van de verbinding die je nodig hebt om genoeg data te sturen naar een server om 'm lang genoeg bezig te houden dat je in die tijd, met die snelheid, genoeg data stuurt om 'm nog een keer zo lang bezig te houden.

Dus als een server een 8 uur bezig is om 8 megabyte aan POST data te parsen, heb je een verbinding nodig van 1 megabyte per uur of ongeveer 18 kbps.

[TD-er]

Dus als een server een 8 uur bezig is om 8 megabyte aan POST data te parsen, heb je een verbinding nodig van 1 megabyte per uur of ongeveer 18 kbps.

Ik kom op zo'n 2.2 kbps.
1 MByte = 8Mbit
8 Mbit / 60 / 60 = 2.2 kbps.

[CyBeR]

Je hebt gelijk, ik heb per ongeluk 8MiB/uur uitgerekend ipv 1MiB/uur. Even lui gedaan en gewoon '8 megabytes/hour in bits/second' in google getypt ipv het zelf uitgerekend

[Reactie gewijzigd door CyBeR op 23 juli 2024 14:27]

[Brantje]

Genereren van hashes kan gewoon lang duren.
Vergelijk het maar met grote cadeau's inpakken, hoe groter het cadeau, hoelangzamer het gaat

Neem dit
$string = "Test"
$hash = md5(aes(blowfish($string)))

Het werkt niets maar als je dit zou uitvoeren, an weet je wel dat de cpu een tijd bezig is.

[Reactie gewijzigd door Brantje op 23 juli 2024 14:27]

[Twieka]

Ja, maar dat is niet het punt.
Als je goed leest staat in het pdf'je het volgende:

an attacker can degenerate the hash table by sending lots of colliding keys. The algorithmic complexity of inserting n elements into the table then goes to O(n**2),

Bij het optreden van collision zal het inserten van een volgend element steeds langer duren. De hacker maakt dus gebruik van het feit dat als $_POST['abcdef'] gelijk is aan $_POST['abcdeg'] , $_POST['11abcdef'] en $_POST['11abcdeg'] ook aan elkaar gelijk zijn. Zodoende kunnen er dus heel veel collisions gegenereert worden, en zal ook het inserten van een volgend element in de hash table heel lang duren.

[Verwijderd]

Er staat ook dat het maar een POST kost om de server offline te krijgen... hoe verklaar je dat?
Edit: Ehm waarschijnlijk bedoelt men dat de POST gebruikt kan worden om een server offline te krijgen, men verklapt niet in hoeveel POSTs. Ofwel, je hebt gelijk.

[Reactie gewijzigd door Verwijderd op 23 juli 2024 14:27]

[Verwijderd]

het zit hem in wat het algoritme doet als er 2 waardes dezelfde hash hebben, dat kost blijkbaar erg veel CPU tijd.

[Risce]

Ik snap dit soort berichten echt nooit. Kan er niet geprobeerd worden om onder elk van dit soort nieuwsberichten een Noob-alinea te zetten? Nu moet ik elke keer naar Wiki, waar het net zo onduidelijk wordt uitgelegd.

[RobTweaks]

T.net gaat er gewoon vanuit dat de bezoekers een zekere kennis hebben van dit soort onderwerpen.

Maar om je toch even op weg te helpen:

Een string (reeks karakters) is om te zetten in een waarde die de string representeert, een zogenaamde hash. Uit de hashwaarde is vaak zeer moeilijk een oorspronkelijke waarde te vinden, met behulp van de hashtables (een soort tabel met hashes en de gerepresenteerde waardes) is deze waarde sneller terug te vinden.

Als twee hashes overeenkomen noemt men dit een collision (botsing).

Op het moment dat een collision voorkomt, kan voor de betreffende niet meer worden gezocht in de hashtable. De waarde moet dan lettertje voor lettertje worden vergeleken wat vele malen langer duurt dan het opzoeken van de gerepresenteerde waarde in de tabel.

Je kan je voorstellen dat dit bij een of twee hash-collisions geen probleem is, de computers van tegenwoordig zijn best in staat dit te verwerken. Echter, per collision wordt het zoeken naar de waarde van iedere hash herhaald. Dit wordt gedaan om te kijken of er al eenzelfde waarde voorkomt in de database. Bij 1000en collisions is een server/computer te druk bezig met verwerken om nog andere aanvragen te kunnen verwerken.

Ik hoop dat het zo duidelijker is . Voor meer uitleg over de gebruikte termen:

String: http://nl.wikipedia.org/wiki/String_%28informatica%29
Hash table: http://en.wikipedia.org/wiki/Hash_table
Hash collision: http://en.wikipedia.org/wiki/Collision_%28computer_science%29

[Reactie gewijzigd door RobTweaks op 23 juli 2024 14:27]

[frickY]

PHP's bestaande post_max_size convar kan dit probleem toch ook al grotendeels inperken?

[Reactie gewijzigd door frickY op 23 juli 2024 14:27]

[WhatsappHack]

Jawel, maar dan perk je dus wel algemene functionaliteit mogelijk in. Bijvoorbeeld als er veel data verstuurd moet worden (veel tekst, upload, etc.) dan kan POST data al snel oplopen. Als je dan de size laag moet zetten kan het een en ander stuk gaan.