Attacchi al consumo di risorse contro algoritmi

Questo attacco è noto come Hash DoS o, più in generale, come Algorithmic Complexity Attack.

Esistono diversi modi per implementare le tabelle di ricerca:

1. Alberi equilibrati
   Le operazioni rilevanti hanno prestazioni logaritmiche, indipendentemente dai dati. Questi sono naturalmente immuni da questo attacco, ma sono più lenti.
2. Hashtables
   Se gli hash sono ben distribuiti, le operazioni rilevanti sono O (1) e molto veloci, ma se sono mal distribuite diventano O (n).

Esistono due strategie comuni per evitare Hash DoS: puoi passare agli alberi, oppure puoi usare gli hash con chiave.

Per gli hash con chiave, il server sceglie una chiave segreta casuale. A seconda della situazione, questa chiave può essere per processo, per tabella, per richiesta, ... Le durate più lunghe possono consentire attacchi adattivi su più richieste, ma non sono sicuro di quale sia un problema nella pratica.

Quindi usa un hash con chiave per determinare il bucket, invece di un hash non cifrato. Se l'hash con chiave è buono, questo impedisce all'aggressore di produrre rapidamente collisioni. Gli hash con chiave precedente spesso soffrivano di collisioni indipendenti dalla chiave, e quindi non impedivano l'attacco una volta che questi erano stati trovati. Attualmente SipHash sta guadagnando popolarità, dal momento che è veloce, ma comunque crittograficamente sicuro.

La mia raccomandazione sta utilizzando SipHash e per evitare il riutilizzo delle chiavi tra le richieste ove possibile.

• Breaking Murmur: Hash-flooding DoS Reloaded (sul blog di Martin Boßlet)

• SipHash / Attacchi

  Attacks
  Jointly with Martin Boßlet, we demonstrated weaknesses in MurmurHash (used in Ruby, Java, etc.), CityHash (used in Google), and in Python's hash. Some of the technologies affected have switched to SipHash. See this oCERT advisory, and the following resources:

  • Slides of the presentation "Hash-flooding DoS reloaded: attacks and defenses" at Application Security Forum Western Switzerland 2012 (Aumasson, Boßlet)

• Hash DoS contro BTRFS

• Molti linguaggi di programmazione stanno aggiornando le loro librerie standard per evitare Hash DoS. Questi attacchi colpiscono molto dinamicamente le lingue dattilografate, dato che tipicamente usano gli hashtables quasi ovunque (nomi dei membri per valori, ecc.)

  Alcuni grandi progetti che aggiornano i loro hashtables:

  • Ruby , JRuby - SipHash
  • Perl - SipHash
  • Haskell - SipHash ,
  • .net - Personalizzato, probabilmente ispirato a SipHash ma sembra molto più debole
  • Redis - SipHash

Il bug specifico dell'esaurimento delle risorse è causato da buffer di trasmissione replicati per ogni blocco richiesto. Di conseguenza, una configurazione con un buffer di invio da 16kB consumerebbe effettivamente 1 MB di memoria se vengono inviati 64 intervalli di lunghezza intera o 10 MB se si inviano intestazioni di 640 intervalli. Finché la connessione viene mantenuta aperta, i buffer non inviati rimangono in memoria. Ovviamente questo può essere utilizzato per eseguire un DoS efficace, dal momento che solo 10 connessioni aperte con intestazioni della gamma 640 possono consumare fino a 100 MB. Il tuo chilometraggio può variare in base alle diverse impostazioni di configurazione.

Non conosco documenti sull'analisi della sicurezza dell'algoritmo, ma uno dei modi migliori per cercare i bug di esaurimento delle risorse è identificare qualsiasi punto nell'algoritmo in cui un input non limitato può modificare la quantità di memoria allocata, o dove il client ha lavorato molto meno del server.