Hash Table, Collisioni e attacchi (D)DoS

Rischia di passare sotto silenzio questa vulnerabilità incredibilmente longeva e, almeno dalle prime valutazioni, assai pericolosa. 

Pericolosa, perché con delle semplici REQUEST POST si riesce a provocare un consumo di CPU del 100%, per un tempo che può arrivare anche a delle ore. Quindi DoS o peggio DDoS.

Pericolosa, perché non è relativa a questa o quella piattaforma, ma a come i diversi linguaggi implementano la funzione di hashing per  la gestione delle strutture dati chiamate "Hash Table" (da non confondere con gli hash crittografici che, sebbene siano pur sempre degli hash, hanno altre finalità e caratteristiche).

Longeva, perché il primo lavoro su di essa fu presentato nel 2003 in una conferenza USENIX e solo oggi, dopo la presentazione al CCC (congresso del Chaos Computer Club), ci si è forse resi conto dell'impatto che può avere un attacco che sfrutta tale vulnerabilità.

La sostanza: inserire nelle hash table dei nuovi valori che generano collisioni con un degradamento "quadratico" del tempo di computazione. 

Le hash table vengono utilizzate normalmente in tutti i linguaggi per realizzare i cosiddetti "array associativi", ovvero array che indicizzano i valori contenuti attraverso delle chiavi alfanumeriche:

arrayAssoc["pippo"] = "paperino";

print arrayAssoc["pippo"] ==> "paperino"

Il principio su cui si basano le hash table è semplice: calcolare una funzione H(x) (dove H sta per Hash e x è la chiave), la quale restituisce un intero che è l'indice dell'array sottostante: 

H("pippo") = 3

array[H("pippo)] = array[3] = "paperino"

Tendenzialmente la funzione H presenta delle collisioni, ossia a chiavi diverse corrisponde lo stesso indice numerico ed in questo caso i valori sono organizzati in una lista collegata all'indice stesso. Nel caso di collisioni, la lista viene scorsa ad ogni inserimento. 

E' questo il punto "debole" dell'algoritmo, perché l'inserimento di n elementi costa nel caso medio O(n), ovvero O(1) per ogni elemento inserito (tempo costante per ogni inserimento). Nel caso peggiore invece, diventa O(n^2), perché ogni elemento inserito ha la stessa chiave e quindi bisogna scansionare la linked-list del bucket corrispondente.

Quindi, per ritornare al dominio dei Web App Server, inviare dei POST che generano collisioni nelle hash table, implica in alcuni casi un tempo O(n^2), ovvero un carico della CPU fuori della norma.

Non c'è però da demonizzare le funzioni hash perché, se usate in un contesto chiuso, ovvero in un'applicazione client, questa "caratteristica" non crea grossi problemi ma solo inefficienze che possono essere anche accettate. Quando invece vengono utilizzate da codice Web che processa POST data, allora l'impatto dell'attacco è di una magnitudo superiore.

La vulnerabilità è assai pervasiva, perché di fatto quasi tutti i linguaggi hanno delle implementazioni non sicure di tale funzione: PHP, ASP.NET (e quindi C#, VB.NET, etc.), Java (Tomcat, JBoss, GlassFish), Ruby e Perl (ma sembra che questi abbiano già provveduto...), etc. O meglio, quasi tutti i Web Application Server basati su questi linguaggi!

Cosa fare?

Aspettare il rilascio della nuova versione del linguaggio di programmazione o dell'ambiente non è forse la cosa migliore nel breve periodo. Gli stessi autori dello speech al CCC suggeriscono di limitare il POST size e il numero dei parametri POST nei Web App Server come workaround. 

Nel lungo periodo, non "scordarsi" di aggiornare i Web App Server. Ma questo vale un po' per tutto! :)

Ecco il video della presentazione al CCC:

Se non avete un'ora a disposizione, fate prima a guardarvi le slide in formato PDF scaricabili qui. Sono ben fatte e si capiscono!