IT блог

В заметке будет рассказано о том, как работает метод hashCode(), как происходят коллизии и об опасности некорректного использования строк в качестве ключей.

При выборе хеш-функции самым важным критерием является вероятность коллизии. Встроенные функции JDK не являются исключением. При атаке с использованием коллизии злоумышленник подбирает два сообщения m1 и m2 такие, что hash(m1) = hash(m2). В этой заметке я покажу, что данная проблема может воспроизведена в любой программе на Java и расскажу, как обойти ее.

Для начала рассмотрим метод hashcode класса java.lang.String:

    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;
 
            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

Как мы видим, хэш вычисляется по формуле:
s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1]

И это ничто иное, как полиномиальный метод вычисления. Множителем является число 31 и его выбор вполне оправдан — Joshua Bloch объясняет его так в Effective Java: «Значение 31 выбрано из-за того, что это нечётное простое число. Если бы оно было четным и произошло переполнение, информация была бы потеряна, т.к. умножение на 2 эквивалентно сдвигу. Преимущество использования простого числа менее понятно, но оно уже стало традиционным. Хорошим качеством числа 31 как множителя является то, что операцию умножения можно представить как композицию сдвига и вычитания для увеличения производительности: 31*i == (i<<5)-i. Современные виртуальные машины делают такую оптимизацию автоматически." (Chapter 3, Item 9: Always override hashcode when you override equals, page 48). Коллизию при вычислении хэша можно воспроизвести элементарно: Если строка a и строка и имеют одинаковый префикс (который может быть пустым) и одинаковую длину n >= 2 и выполняется условие 31*(b[n-2] — a[n-2]) == (a[n-1] — b[n-1]), то хэш будет совпадать.

Рассмотрим код:

        String a = "Aa";
        String b = "BB";
 
        System.out.println(a.hashCode());
        System.out.println(b.hashCode());
 
        System.out.println(31 * ('C' - 'D') == ('B' - 'a'));
        System.out.println(31 * ('B' - 'A') == ('a' - 'B'));
 
        System.out.println("common_prefixDB".hashCode());
        System.out.println("common_prefixCa".hashCode());

Вывод:

2112
2112
true
true
-1027514780
-1027514780

Как видим, у строк «Aa» and «BB» (пустой префикс) хеш код 2112. У строк (непустой префикс) «common_prefixDB» «common_prefixCa» код -1027514780. Читатель сам может смоделировать подобные ситуации.

Можно сделать вывод о том, что использование строк в качестве ключей в HashMap опасно — если разработчик хранит в ней HTTP заголовки, то злоумышленник может использовать это свойство для DoS аттаки.

Перевод статьи: английский оригинал