Denial of Service i light-version: 100 kilobyte overmander serverens CPU

Det er rettet i Ruby 1.9 og jeg ved at der er en opdatering på vej til ruby enterprise 1.8.7 som er den mange ruby on rails ting kører på.

http://php.net/ "Added max_input_vars directive to prevent attacks based on hash collisions"

Journalisten kan finde ud af at skrive PHP med store bogstaver, men ikke ASP.NET eller bare .NET i sig selv, selvom begge dele er akronymer.

Derudover er en "ASP-server" måske bedre kendt som IIS.

Samt resten af artiklen virker noget rodet.

Problemet er langt mere generelt end man måske umiddelbart får indtryk af at læse artiklen.

Ved at skabe tilstrækkeligt mange hash kollisioner "konverterer" man reelt an hash liste til en kædet liste som er meget mere krævende for mange operation (som f.eks. opslag i listen). Det interessante er at tricket generelt virker for alle applikationer der gemmer bruger genereret input i en hash liste på en forudsigelig måde.

Perl har så vidt jeg ved løst det ved at tilføje noget random til hashen (generet under opstart af perl så det er unikt for hver perl session), men flere andre projekter forsøger at løse problemet ved at begrænse mængden af bruger input til mere rimelige mængder.

Som et eksempel på andet end webservere så er der formentligt nogle IRCd daemoner der er sårbare overfor angrebet i et eller andet omfang. De burde dog blive reddet af generelle begrænsninger af antalelt af forbindelser per IP adresser mv., men der er ret meget kode der bør kontrolleres for dette.

Her er nogle bedre forklaringer og et forslag til at løse problem i PHP!
http://www.freeklijten.nl/home/2011/12/29/The-real-problem-of-the-hash-t...
http://arstechnica.com/civis/viewtopic.php?f=16&t=1164260

Synes godt Version2 kan tage sig selv lidt sammen her i det nye år, og holde op med at lave EB artikler!

Ordenlige og informative nyheder tak.

I artiklen står der: Og med Java kan selv en fil på seks kilobyte holde en processorkerne travlt optaget.

Det er ikke korrekt. I beskrivelsen af sårbarheden ( http://www.nruns.com/_downloads/advisory28122011.pdf ) står der

A Tomcat 6.0.32 server parses a 2 MB string of colliding keys in about
44 minutes of i7 CPU time, so an attacker with about 6 kbit/s can keep one i7 core constantly
busy. If the attacker has a Gigabit connection, he can keep about 100.000 i7 cores busy.

Dvs. der skal altså POST på 2MB til for at holde én i7 core beskæftiget i 44 minutter. Det kræver altså en forbindelseshastighed på 6 k[b]bit[/b]/s. Men én request på 6 kbyte kan altså ikke gøre det.

Skræmmende at det ikke er løst efter 8 år, når løsningen er så simpel som at salte hash-funktionen.

Jeg synes at ikke engang "suhosin.post.max_vars = 20" hjælper. Den 21. er godt nok "dropped variable" ifølge loggen, men jeg har stadig DoS i cirka et minut.

Det er ikke en rigtig løsning, mere et workaround, for problemet eksisterer stadigvæk selvom du salter. Det er noget som ligger i sig implementationen af hashlister.

Ved at salte hashlisten, kan du stoppe angrebet, da angriberen forhåbentligt ikke kan gætte, eller for den sags skyld regne sig frem til din salt. Men du er stadigvæk sårbar.

Jeg ved ikke hvilken indflydelse det har på flere servere der snakker med én enkelt klient på tværs af forespørgsler, for så kan det godt være det er derfor det har taget lidt længere tid at fikse.

1. Microsofts nødpatch handler om noget helt andet og meget alvorligere, hash-fixet blev først klistret på senere.

2. Problemet er at folk ikke bruger stærke nok hash-funktioner. Salt'ning er kun et band-aid.

3. I stedet for alle de der "shift+add" type hashs på kun 32 eller 64 bits, bør man bruge en hash med kryptografisk styrke på mindst 128 bits, så er problemet løst en gang for alle.

Som PHK skriver så dækker ms11-100 over 4 CVE hvor det ene er hash delen som er skræmmende læsning.

Sjovt, jeg synes nu det er den her er den mest skræmmende:

> The most severe of these vulnerabilities could allow elevation of privilege if an unauthenticated attacker sends a specially crafted web request to the target site.

I stedet for alle de der "shift+add" type hashs på kun 32 eller 64 bits, bør man bruge en hash med kryptografisk styrke på mindst 128 bits, så er problemet løst en gang for alle.

Hvordan vil du gemme en hashtabel med 128 bit hashes i hukommelsen på en 64-bit server? Den tabel vil da fylde en hel del mere end det tilgængelige adresserum...

Det vil nok heller ikke være det smarteste at bruge hashfunktioner med kryptografisk styrke, da de typisk er noget tungere at beregne i forhold til universelle hashfunktioner baseret på randomisering. Specielt når det nu handler om DOS.

Jeg fik snøvlet , jeg mente de 3 var skræmmende læsning kontra hash delen

Hvordan vil du gemme en hashtabel med 128 bit hashes i hukommelsen på en 64-bit server?

F.eks på samme måde som Varnish gemmer en 256 bit hash i hukommelsen på en server, hvad enten den har 32 eller 64 bit ord: Med et træ.

Deres talk fra den 28. Chaos Communication Congress (28C3) kan findes her: ftp://mirror.fem-net.de/CCC/28C3/mp4-h264-HQ/28c3-4680-en-effective_dos_... (342 MB -- den findes også i lavere kvalitet).

Her er 100.000 longs, der tog min laptop 76s at knække:

Set<Long> set = new HashSet<Long>();  
for (long i = 0; i < 100000; i++)  
    set.add(i<<32|i);  
set.contains(0);

Det svarer vel til ca. 768KiB. Og det er med kun én forspørgsel til tabellen.
Man kunne også bare gå over til at bruge træer med garenteret performance. Måske er de lige så hurtige som en hashmap med kryptografisk hashing.

Interessant læsning: Her tænker jeg primært på kommentarene.
Måske burde man sende artikler i "beta-release" før de blev udsendt til den glubske forsamling af kritiske læsere :)

Man kunne også bare gå over til at bruge træer med garenteret performance. Måske er de lige så hurtige som en hashmap med kryptografisk hashing.

Det afhænger af dine nøgler. Problemet for generel software, som et programmeringssprog, er at du ikke kan lave nogen antagelser om dine nøgler.

Træer er specielt dårlige for leading-prefix nøgler og derfor valgte jeg at bruge SHA256+træ i Varnish, for at sikre god distribution.

@Thomas Dybdahl Ahle: Nej - du har misforstået problemet. Læs de linkede artikler igen.

Det handler ikke om "bare" at lave en masse hash-værdier. Det handler om at generere kollisioner, der gør at du er nød til at teste hver enkelt værdi - hvilket er det som hash-træerne skal undgå til at starte med.

Hvor har du informationen om at de først fixer hash problemet senere?

Den står da nævnt: http://technet.microsoft.com/en-us/security/bulletin/ms11-100 længere nede på siden?

@Klaus Post: Jeg tror du misforstår hvor nemme kollisioner kan være at generere. I java hashes en Long som (int)(value^(value>>>32)). Derfor har alle de tal på formen (i<<32|i) samme hash: 0.

At bruge et træ uden nøgler ville selvfølgelig kræve at man i steddet fandt gode og effektive måder at sammenligne de enkelte elementer. Det ville nok være svært for en hashtable over generelle blobs, men i de tilfælde hvor det er nemt, som her ved longs, kan jeg ikke se nogen grund til ikke at gøre det.

Den første version indeholdt kun priv-esc. Hash kom på senere.

Jesper: Hvordan er det i praksis lettere at gemme en 64-bit hashtabel i hukommelsen? Jeg tror ikke der er mange steder du kan koebe en maskine med 2**64 bytes lager. I stedet for traeer kan man med fordel kigge paa Cuckoo Hashing som faktisk er en dansk opfindelse.

Cuckoo Hashing løser i hvert fald ikke problemet i sig selv, umiddelbart er det sårbart overfor kæder som kan flytte hele stakken af objekter med en enkelt insert, og derefter flytte hele molevitten tilbage igen med den næste insert osv. Hvis man kan gennemtvinge table rebuilds kan det i mange situationer også være et ret grimt angreb. Vi er vel sådan set blot tilbage ved at hash funktionerne skal være ukendte for angriberen.

Pointen var ikke at cuckoo hashing beskytter mod angreb, men at 128 bits ikke er vaerre end 64, da det ikke giver mening at lave hashtabeller til nogen af delene. Cuckoo hashing er bedre en traeer fordi man i visse varianter kan komme over 90% pladsudnyttelse (se fx Manasse og Erlingssons udgave). Naturligvis skal man bruge en sikker hashfunktion, og man kan trivielt seede den med et hemmeligt, tilfaeldigt tal for at forhindre angreb. Endelig boer man jo kun bruge hashtabeller hvor det giver mening, da moderne hardware slet ikke bryder sig om random access.

Det giver såmænd ganske god mening at bruge en del af en stor hash til en hashtabel, man kan så lade hvert punkt i tabellen pege på et søgetræ som anvender hele hash værdien. Man får på den måde den garanterede performance og fleksibiliteten som et søgetræ giver, men man sparer tid ved at bruge et enkelt tabelopslag i stedet for at traversere den første del af et stort søgetræ.

Endelig boer man jo kun bruge hashtabeller hvor det giver mening, da moderne hardware slet ikke bryder sig om random access.

Det er korrekt at random access i hukommelsen er dyrt, men et binært søgetræ hvor hver knude i træet er allokeret separat på heap'en giver en random access for hvert niveau i træet. Så en hashtabel er klart bedre. En hashtabel giver kun O(1) random accesses per opslag, hvilket er optimalt.

Nu er der jo heldigvis andet end binaere soegetraeer til, og en simpel hashtabel kan kun lave opslag i konstant tid naar der ikke er kollisioner, hvilket typisk undgaas ved at fordoble tabellens stoerrelse hver gang der er en kollision. Cuckoo hashing og varianter deraf reducerer risikoen for at maatte fordoble, og udnytter dermed pladsen bedre. Et B-trae har ofte bedre lokalitet, specielt naturligvis naar input ikke allerede er hashet, og tillader bl.a. range queries. Mht. at kombinere en hashtabel med et trae, hedder det vist officielt et Van Emde Boas-trae, og har fordele mht. lokalitet ved bl.a. range queries, men er ofte dyrere mht. pladsforbrug.