Qual è il vantaggio di avere un algoritmo hash crittograficamente sicuro in hashmaps?

A volte le applicazioni usano dati non fidati come chiave in una mappa hash. Una semplice implementazione può consentire ai dati non attendibili di provocare un attacco denial of service.

Le mappe hash sono veloci - O (1) - nel migliore dei casi, ma lente - O (n) - nel peggiore dei casi. Questo perché le chiavi sono normalmente in bucket separati, ma alcuni valori possono provocare lo stesso hash - una collisione - che viene gestito da una lista collegata più lenta. Con dati casuali, le collisioni saranno rare. Tuttavia, alcune implementazioni presentano una vulnerabilità in cui i dati dannosi possono causare numerose collisioni, il che rende la mappa hash lenta. Alcuni anni fa a causa di questo c'era un kernel Linux DoS .

La causa principale della vulnerabilità di Linux era che l'hashing era prevedibile. È stato corretto introducendo una chiave nella funzione di hash che un utente remoto non avrebbe saputo. Non so esattamente come funzionano le mappe di hash di Rust, ma mi aspetto che usino un tipo simile di hash con chiave.

Dovresti optare per un hash più sicuro ogni volta che utilizzi dati non attendibili come chiave.

Le operazioni di inserimento, ricerca e rimozione sulle tabelle hash hanno il comportamento nel caso peggiore O (n). Se un utente malintenzionato può scegliere le chiavi da inserire in una tabella hash e può calcolare autonomamente la funzione hash, allora crea un'opportunità per negare il servizio. Tutto quello che devono fare è scegliere le chiavi che si associano allo stesso bucket.

La citazione suggerisce che l'uso di un algoritmo di hash crittografico (SHA, MD5, Blake, Skein, ecc.) risolve il problema. Quella interpretazione è totalmente errata . L'algoritmo utilizzato da Rash's HashMap è chiamato SipHash . È un algoritmo di hash. Ed è un algoritmo crittografico. Ma non è una funzione hash crittografica . Il termine corretto per SipHash nel mondo della crittografia è PRF .

La differenza principale è che (in crittografia) tutti i dettagli di una funzione di hash possono essere di dominio pubblico. Un PRF, d'altra parte, richiede una chiave segreta. Senza le informazioni segrete non c'è modo di prevedere, per ogni input, quale sarà l'output. (Tutti gli altri dettagli sono pubblici.)

Qualcosa come SHA-2 non impedirà la negazione del servizio. Sarà totalmente imparziale per gli input non contraddittori. (Poiché le funzioni di hash crittografiche possono essere modellate come oracoli casuali .) Tuttavia, chiunque può valutare SHA-2, quindi qualcuno può trovare collisioni tavolo hash per forza bruta.

Il fatto che una funzione di hash crittografica sia resistente alla collisione (con almeno 256 bit di output) non si traduce in una mancanza di collisioni nel caso di tabelle hash. In definitiva la tua funzione di hash, per una tabella con bucket n , verrà ridotta a uno dei n valori possibili. Per tentativi ed errori è possibile trovare un input che esegue il mapping su un bucket specifico circa una volta ogni tentativo n . Nessuna tabella hash utilizza bucket sufficienti per renderlo impossibile.

L'uso di una funzione di hash senza chiave è intrinsecamente vulnerabile alla negazione del servizio, a prescindere da quanto sia buona la funzione di hash. Il fatto che l'autore dell'attacco e server-with-a-hash-map interrogino entrambi lo stesso oracolo consente a un DOSer di utilizzare input appositamente selezionati per legare la CPU.

I PRF come SipHash non hanno questa vulnerabilità se usati correttamente. Il server utilizza una funzione oracle / scelta da un pool di 2 ¹²⁸ possibili funzioni. Per sfruttare una funzione hash basata su PRF (hash-table-), l'attacker deve indovinare quale delle 2 ¹²⁸ funzioni che dovrebbe usare (un "key recovery") o trovare un bias in il PRF indipendente dalla chiave (un modo per distinguere il PRF da un oracolo casuale).

Infine, esistono altre sfumature confuse che coinvolgono algoritmi di hash. Ma riassunto semplicemente:

• Le funzioni hash crittografiche sono un sottoinsieme di tutte le funzioni hash ordinarie
• Secondo la definizione classica di funzione hash crittografica, la casualità non è richiesta. Comunque la casualità è una caratteristica di tutte le funzioni hash crittografiche di grande nome comunque.
• Non tutti i PRF sono funzioni hash crittografiche
• Non tutte le funzioni di hash crittografiche sono PRF
• Un algoritmo può avere le proprietà di un PRF e una funzione hash crittografica.
  • Blake2, Skein e KMAC hanno entrambi i set di proprietà
  • Le famiglie SHA-2 e SHA-3 sono esempi di funzioni hash crittografiche (non cifrate)
  • SipHash è solo un PRF (e una funzione di hash ordinaria, ma non crittografica)
• Un PRF può essere costruito utilizzando le tipiche funzioni di hash crittografico, ma la funzione di hash non è necessariamente un PRF.
• "hashing randomizzato" e "hashing universale" sono in qualche modo simili ai PRF, ma non hanno gli stessi requisiti di sicurezza.
  • Le collisioni possono essere create anche se i semi di MurmurHash3 sono randomizzati

Sono d'accordo che è un po 'vago e dipenderà molto da come vengono usate le hashmap.

Ecco la mia ipotesi: dì che stai prendendo alcuni input dagli utenti, diciamo [Firstname.Lastname] e utilizzalo come valore di ricerca nella tua tabella hash. Supponiamo che tu stia costruendo la tua tabella hash usando la semplice funzione di hash che prende le iniziali in modo che [Firstname.Lastname] --> FL , quindi sarebbe facile per un utente malintenzionato inviare un sacco di valori che hanno tutti hash alla stessa cosa. Ciò trasformerebbe essenzialmente il tuo hashtable in un elenco che nega tutti i vantaggi in termini di prestazioni dell'utilizzo di un hashtable. Ricerche lente = negazione del servizio.

AA -> [ ]
AB -> [ ]
...
FK -> [ ]
FL -> [First.Last, F1.F2, F1.F2, Fanotheu.Lonteuh, ...]
FM -> [ ]
...
ZZ -> [ ]

Le funzioni hash crittografiche sono progettate specificamente per evitare ciò perché è molto difficile costruire due input diversi con lo stesso valore hash (chiamati collisioni).

When should I opt for a more secure hash over a faster one?

La risposta è semplice: optare per un hash crittografico ogni volta che il valore di ricerca viene fornito dagli utenti e potrebbe essere pericoloso. Se i valori di ricerca provengono da una fonte interna che consideri non dannosa e uniformemente distribuita, puoi utilizzare un hash più veloce.