Что может пойти не так при использовании hashCode() класса java.lang.String?

В заметке будет рассказано о том, как работает метод 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 аттаки. Перевод статьи: английский оригинал
You can leave a response, or trackback from your own site.

Leave a Reply