Decorating a HashMap adding randomness to prevent (D)DoS

Question

EDIT by the way the point of the workaround here is to reuse all the existing HashMap (like the ConcurrentHashMap etc.) instead of re-inventing entirely the wheel. Languages using randomized hash functions (like Perl) are protected against this attack.

In the light of the very recent and devastating DDoS using known flaw in several hashmap implementations (known to affect Java webservers, but also PHP and others), Apache Tomcat just came out with a "fix" in the form of a patch allowing to put a cap on the maximum allowed numbers of parameters in a POST request (patch your Tomcat to 6.0.35+ or 7.0.23+ btw).

The (D)DoS is apparently basically using the fact that strings can be crafted so that they do collide when hashed and that a lot of webservers "stupidly" put key/value parameters in (broken) hashmaps.

I was wondering if it would be possible to write a decorator around a HashMap{String,String} so that to every String added a random (random from the point of view of an attacked) value was added to the String, like this:

... get( String s ) {
    return wrappedBrokenMap.get( s + crunch(s );
}

... put( String key, String value ) {


  wrappedBrokenMap.put( s + crunch(s), value );
}

And here would be one implementation of crunch(...) (it is just an example, the point is: the attacker doesn't know the implementation):

private static final int MY_MAGICAL_NUMBER = 0x42BABE;  // attacker doesn't know that number

private static String crunch( String s ) {
    return s.length + "" + MY_MAGICAL_NUMBER;
}

If for any String s crunch(s) returns a reproducible String that the attacker cannot guess, the DDoS attack has effectively been prevented right?

Would that work?

Answer 1

If for any String s crunch(s) returns a reproducible String that the attacker cannot guess, the DDoS attack has effectively been prevented right?

Basically, this is what you do when you salt password hashes (although for slightly different reasons). It doesn't prevent collision attacks entirely (if you have a hash function mapping arbitrary-length input to a fixed-length output, hashes can always collide), but using a secret salt should make such attacks harder.

A quick'n'dirty implementation could look something like this:

public class SaltedHashMap<V> {
    private final Map<String, V> map = new HashMap<>();
    private final String salt;
    public SaltedHashMap(String salt) {
        this.salt = salt;
    }
    public V get(String key){
        return map.get(key + salt);
    }
    public void put(String key, V value) {
        map.put(key + salt, value);
    }
}

Using a web server as an example, we could use a SecureRandom to randomize a new salt for every incoming request, meaning that even if you managed to figure out a collision-generating input for one request, it would be extremely unlikely to work for other requests.

Answer 2

The alternative String hash function added in 7u6 has been removed from JDK 8, along with the jdk.map.althashing.threshold system property. Instead, hash bins containing a large number of colliding keys improve performance by storing their entries in a balanced tree instead of a linked list. This JDK 8 change applies only to HashMap, LinkedHashMap, and ConcurrentHashMap.

Please refer: https://docs.oracle.com/javase/8/docs/technotes/guides/collections/changes8.html

Answer 3

I think by the time it gets to your code (where you could make the above changes), the hashing has already been done by the underlying libraries that handle the POST request. So, no, I don't think it would work.

Answer 4

To guarantee the change is global, I would create a patched String like with a method like this

// from java.lang.String
public int hashCode() {
    int h = hash;
    if (h == 0 && count > 0) {
        h = MY_STARTING_VALUE;
        int off = offset;
        char val[] = value;
        int len = count;

        for (int i = 0; i < len; i++) {
            h = MY_PRIME*h + val[off++];
        }
        hash = h;
    }
    return h;
}

The problem with this is that some libraries rely on the implementation of hashCode being a particular way. If you are not using such a library, this guarantees that every piece of code using Strings will be patched.

---

The problem with using a "crush" or seed is that you need to know its value to perform the lookup in the first place. If you use a random value, you have to poll every possible key to get out a value which doesn't sound very efficient.

If you are worried about the worst case performance, you can use TreeMap. It's typical and worst case performance is O(log n) to perform an insert/lookup.

---

If you are really worried about this you could use a String class with your own hashCode() or you could override the built in hashCode for String or the value used by HashMap.