2

I've done some reading in this area and there is very little information about the security of a HashMap. The only article I could find was on IBM's Developer Works site.

What hashing function is used for HashMap in Java. That's really the most important question regarding the security of HashMaps, right?

4 Answers 4

4

There are two different types of hash functions:

The cryptographic hash functions make specific security promises, such as being hard to invert, hard to create collisions, and such.

Regular non-cryptographic hash functions, such as the one used in java.util.HashMap, are designed to be as fast as possible, to distribute inputs as evenly as possible into the full range of hash buckets, and do not usually make specific security promises.

Nonetheless, that's not to say there aren't any security concerns with regular hash functions. For example, algorithmic complexity attacks, where the attacker chooses unique keys that they know all map to the same hashed value, allowing them to mount a denial of service attack.

2
  • Cryptographic hash functions are no better in the context of something like HashMap. You don't need full collisions. Bucket level collisions are all that's required for a DOS attack. The effective strength of the hash function is inherently limited to log2(numBuckets), even if you implement hashCode using a 512-bit cryptographic hash. The number of buckets stays quite small, so the reduced security level is always low enough for even brute force collision searches to work. Feb 16, 2020 at 16:43
  • One good solution is to use a PRF instead of a plain hash function. (SipHash is a lightweight example of a PRF.) But that requires a (symmetric) cryptographic key, which hash table implementations would need to keep secret. Java's hashCode API specifically isn't friendly to that kind of thing. (You can't just do PRF(k, obj.hashCode())That's no better than just using obj,hashCode().) Feb 16, 2020 at 16:56
1

It uses hashCode() function. A plain and short explanation of how this function works can be read here and a pseudo implementation is here.

1

As in always in security, what threat are you attempting to protect against?

It seems from the question you are worried about availability. Typically a hash table will have limiting performance of O(1) for simple operations, but degrade to worst case of O(n). (See Secure Coding Guidelines for Java SE .) Say, will a web server use resources disproportionate to the size of a maliciously-crafted worst-case request. The linked article in the questio is about Java Serialisation, which is a hole different thing (and really doesn't protect availability).

It's all very much up to the implementation.

Going back a decade or so, the Sun implementation of HashMap did generally just use a modulus of whatever came out of Object.hashCode. See for instance, the definition of String.hashCode. For String it is trivial to generate different text with the same hash. Give an old HashMap a bunch of keys with the same hash, they'll only use one bucket, and the performance will be terrible.

Later the Sun implementation mixed the hash value around before taking the modulus. However, if the hash was the same to start with, it'll still be the same.

TreeMap solves the issues, but the benign case performance isn't the best, though has improved.

More recently, to placate those who don't know how hash tables work, OpenJDK used variants of MurmurHash, with a per-instance random seed, for String when there are many collisions. This replaces String.hashCode - simply adding the same number to a fixed hash wont alter collisions. Although technically "non-cryptographic", it is supposedly difficult to generate collisions without knowing the secret seed. There are always side-channels.

Now replacing MurmurHash, is the obvious algorithm of using a tree in place of a linear list for buckets when there have been many collisions. As HashMap was never designed to this, it's an outrageous hack, but a hack where the library comes up smelling of roses even when abused (mostly). The alternate algorithm only comes into use when there are many collisions (as with Murmur) and only for instances where every key appears to be implementing Comparable type-compatibly.

1
  • 1
    "It is supposedly difficult to generate collisions without knowing the secret seed" You can create full Murmur3 collisions with 100% success rate without ever learning the seed. You only get a little more "accidental" collision resistance, no protection from malicious input. Feb 16, 2020 at 17:57
0

HashMaps aren't really used for security purposes. They're just used for mapping unique keys to objects. This depends on the object that you're using in your HashMap. Each object should define it's own public int hashCode() function. This function is applied to each object when putting it into a HashMap. It's up to the developer to ensure that their hashCode() does a sufficient job for the object's purpose. But as you'll see HashMap does add an additional internal hash to help with this.

If you look at the source code for HashMap::put you'll see on line 389 that it calls the hashCode for the object as a parameter to a static function called 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       }

Here's what the static int hash(int h) function looks like.

  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       }

The comments explain the reasons for applying the supplemental hashing function.

1
  • Looks like an old version of the OpenJDK source code you have there. Mar 25, 2015 at 12:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .