La serializzazione e HashMaps sono sicuri?

Esistono due diversi tipi di funzioni hash:

• funzioni di hash (non crittografiche)
• funzioni di hash crittografiche

Le funzioni di hash crittografiche rendono specifiche promesse di sicurezza, come ad esempio la difficoltà di invertire, la difficile creazione di collisioni e simili.

Le normali funzioni di hash non crittografiche , come quella utilizzata in java.util.HashMap , sono progettate per essere il più veloci possibile, per distribuire gli input nel modo più uniforme possibile nell'intera gamma di bucket hash e di solito non promettono specifiche garanzie di sicurezza.

Ciononostante, questo non vuol dire che non ci siano problemi di sicurezza con le normali funzioni di hash. Ad esempio, attacchi di complessità algoritmica , in cui l'attaccante sceglie le chiavi univoche che conoscono tutte le mappe allo stesso hash valore, consentendo loro di montare un attacco denial of service.

Usa la funzione hashCode (). Una semplice e breve spiegazione di come funziona questa funzione può essere letta qui e un'implementazione pseudo è qui .

Come sempre in sicurezza, quale minaccia stai cercando di proteggere?

Sembra che dalla domanda tu sia preoccupato per la disponibilità. In genere una tabella hash avrà prestazioni limitanti di O (1) per operazioni semplici, ma peggiorerà nel caso peggiore di O (n). (Vedi Linee guida per la codifica sicura per Java SE .) Say, sarà un server web utilizzare le risorse in modo sproporzionato rispetto alle dimensioni di una richiesta nel caso peggiore pericolosa. L'articolo collegato alla questio riguarda Serializzazione Java, che è una cosa diversa dal buco (e in realtà non protegge la disponibilità).

Tutto dipende dall'implementazione.

Da circa un decennio circa, l'implementazione di HashMap di Sun ha generalmente utilizzato solo un modulo di ciò che è uscito da Object.hashCode . Vedi ad esempio la definizione di String.hashCode . Per String è banale generare un testo diverso con lo stesso hash. Dai un vecchio HashMap a un gruppo di chiavi con lo stesso hash, utilizzeranno solo un bucket e le prestazioni saranno terribili.

In seguito l'implementazione del Sun ha mescolato il valore hash in giro prima di prendere il modulo. Tuttavia, se l'hash era lo stesso per iniziare, sarà sempre lo stesso.

TreeMap risolve i problemi, ma le prestazioni benigne del caso non sono le migliori, sebbene siano migliorate.

Più di recente, per placare coloro che non sanno come funzionano le tabelle hash, OpenJDK ha usato varianti di MurmurHash, con un seme casuale per istanza, per String quando ci sono molte collisioni. Questo sostituisce String.hashCode - semplicemente aggiungendo lo stesso numero a un hash fisso non altera le collisioni. Sebbene tecnicamente "non crittografico", è presumibilmente difficile generare collisioni senza conoscere il seme segreto. Ci sono sempre canali secondari.

Ora sostituendo MurmurHash, è l'algoritmo ovvio di usare un albero al posto di un elenco lineare per i bucket quando ci sono state molte collisioni. Siccome HashMap non è mai stato progettato per questo, si tratta di un trucco oltraggioso, ma un trucco in cui la libreria arriva con l'odore delle rose anche se abusato (soprattutto). L'algoritmo alternativo viene utilizzato solo in caso di numerose collisioni (come con Murmur) e solo per le istanze in cui ogni chiave sembra implementare Comparable type-compatible.

HashMaps non sono realmente usati per scopi di sicurezza. Sono solo usati per mappare chiavi univoche per oggetti. Questo dipende dall'oggetto che stai utilizzando in HashMap. Ogni oggetto dovrebbe definire la propria funzione public int hashCode() . Questa funzione viene applicata a ogni oggetto quando put lo inserisce in una HashMap. Spetta allo sviluppatore assicurarsi che il loro hashCode() faccia un lavoro sufficiente per lo scopo dell'oggetto. Ma come vedrai, HashMap aggiunge un hash interno aggiuntivo per aiutarti.

Se osservi il codice sorgente per HashMap::put tu " Vediamo sulla riga 389 che chiama hashCode per l'oggetto come parametro di una funzione statica chiamata hash() .

  374       /**
  375        * Associates the specified value with the specified key in this map.
  376        * If the map previously contained a mapping for the key, the old
  377        * value is replaced.
  378        *
  379        * @param key key with which the specified value is to be associated
  380        * @param value value to be associated with the specified key
  381        * @return the previous value associated with <tt>key</tt>, or
  382        *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
  383        *         (A <tt>null</tt> return can also indicate that the map
  384        *         previously associated <tt>null</tt> with <tt>key</tt>.)
  385        */
  386       public V put(K key, V value) {
  387           if (key == null)
  388               return putForNullKey(value);
  389           int hash = hash(key.hashCode());
  390           int i = indexFor(hash, table.length);
  391           for (Entry<K,V> e = table[i]; e != null; e = e.next) {
  392               Object k;
  393               if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
  394                   V oldValue = e.value;
  395                   e.value = value;
  396                   e.recordAccess(this);
  397                   return oldValue;
  398               }
  399           }
  400   
  401           modCount++;
  402           addEntry(hash, key, value, i);
  403           return null;
  404       }

Ecco come appare la funzione static int hash(int h) .

  257       /**
  258        * Applies a supplemental hash function to a given hashCode, which
  259        * defends against poor quality hash functions.  This is critical
  260        * because HashMap uses power-of-two length hash tables, that
  261        * otherwise encounter collisions for hashCodes that do not differ
  262        * in lower bits. Note: Null keys always map to hash 0, thus index 0.
  263        */
  264       static int hash(int h) {
  265           // This function ensures that hashCodes that differ only by
  266           // constant multiples at each bit position have a bounded
  267           // number of collisions (approximately 8 at default load factor).
  268           h ^= (h >>> 20) ^ (h >>> 12);
  269           return h ^ (h >>> 7) ^ (h >>> 4);
  270       }

I commenti spiegano i motivi per l'applicazione della funzione di hashing supplementare.