Java Map keys should always be Comparable

This article is inspired by the discovery years ago that an attacker could manipulate query parameters to turn the map data structure in many web servers into a linked list, by making all the parameter names end up in the same hash bucket, which CVE-2018-0875 reminded me of. You can read about the original discovery in CERT VU#903934 and the original post in the Full Disclosure list archives, or on YouTube from 28c3.

In Java, for example, the strings "fg", "gH" and "h)" all have a hash code of 3265, so an attacker can build query strings like fgfg=0&fggH=0&fgh)=0&gHfg=0 and so on to waste the server’s time and mount an effective denial of service. It’s not that hard to defend against; I know Jetty still limits form content to 200KB and 1,000 keys, and other servers have similar limits.

Java itself implemented a defense in the String class early in the Java 7 releases, described in the Collections Framework Enhancements in Java 7. The String class gained a new hash32 method and field which used MurmurHash3 with a random seed. This is fine for strings and HashMaps, but not so good for custom keys.

A better approach was implemented in JEP 180 for Java 8. Now, if too many hash codes map to the same bucket in the map, the list of entries can be changed into a balanced binary tree, sorted first by hash code and then by each key’s compareTo method, as long as the keys are Comparable. This is obviously the case for strings (and is special-cased in HashMap), but it should also be the case for every class used as a map key, especially if the data is potentially supplied by a hostile user.

Implementing Comparable

It’s straightforward to implement equals() and hashCode() correctly for a data class, if a bit verbose:

public final class SearchKey {
    private final String site;
    private final long userId;
    private final String query;

    public SearchKey(String site, long userId, String query) {
        this.site = Objects.requireNonNull(site);
        this.userId = userId;
        this.query = Objects.requireNonNull(query);
    }

    // getters ...

    @Override
    public int hashCode() {
        return (site.hashCode() * 31 + Long.hashCode(userId)) * 31 + query.hashCode();
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (!(obj instanceof SearchKey)) {
            return false;
        }
        SearchKey other = (SearchKey) obj;
        return userId == other.userId && site.equals(other.site) && query.equals(other.query);
    }
}

(I use 31 as the multiplier in the hash code because it’s prime, and x * 31 can be optimised to (x << 5) - x to be much faster on some platforms.)

As above, the same hash code can be generated for different values, like new SearchKey("fg", 12345, "fg"), new SearchKey("fg", 12345, "gH") and new SearchKey("gH", 12345, "fg"), which all hash to 3,523,625. If we used these as keys in a map-based cache, an attacker could mount a denial-of-service attack by making many queries to our service that use the same hash.

The compareTo method can be implemented by tediously comparing fields one by one:

public final class SearchKey implements Comparable<SearchKey> {
    // ...

    @Override
    public int compareTo(SearchKey o) {
        int c = site.compareTo(o.site);
        if (c != 0) {
            return c;
        }
        c = Long.compare(userId, o.userId);
        if (c != 0) {
            return c;
        }
        return query.compareTo(o.query);
    }
}

But from Java 8, it can be implemented more concisely:

public final class SearchKey implements Comparable<SearchKey> {
    private static final Comparator<SearchKey> COMPARATOR =
        Comparator.comparing(SearchKey::getSite)
            .thenComparingLong(SearchKey::getUserId)
            .thenComparing(SearchKey::getQuery);

    // ...

    @Override
    public int compareTo(SearchKey o) {
        return COMPARATOR.compare(this, o);
    }