Search code examples
javaphphashmapdenial-of-service

Decorating a HashMap adding randomness to prevent (D)DoS


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?


Solution

  • 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.