Теперь пришло время глубже изучить сложность атаки и взглянуть на источники. Я вполне полагаю, что java.util.HashMap и java.util.Hashtable являются наиболее распространенными структурами данных Java, на которые влияет эта атака, поэтому в этой статье будет сосредоточен только код этих типов.
Краткое начало для хэш-функций и индексированных структур данных
Структуры данных с хэш-индексированием очень популярны из-за их простого использования и преимуществ:
- нет необходимости работать с индексными таблицами, чтобы найти правильную позицию нужных данных
- доступ к данным с использованием ключевых слов вместо индексов
- почти постоянное время для операций добавления или удаления
Для достижения этих преимуществ структуры данных с хеш-индексированием следуют умной идее, как индексировать данные. Индекс вычисляется путем хеширования ключевого слова, связанного с данными за ним. Рассмотрим следующий пример для простого кода-подобного примера:
Звучит идеально, но у него есть один существенный недостаток: используемые хеш-функции в большинстве случаев не являются криптографическими.
Согласно Википедии, единственной обязательной характеристикой для функции, вызывающей саму хеш-функцию, является
В отличие от того, чтобы называть себя криптографической хеш-функцией (опять же, определение взято из Википедии ), она должна удовлетворять дополнительным, даже гораздо более строгим требованиям:
»
- легко (но не обязательно быстро) вычислить значение хеша для любого данного сообщения
- невозможно создать сообщение с заданным хешем
- невозможно изменить сообщение без изменения хеша
- невозможно найти два разных сообщения с одним и тем же хешем
»
Короче говоря, давайте подведем итог тому, что мы узнали и что следует сделать с этими знаниями:
- структуры данных с хэш-индексом используют хэш-функции
- хеш-функции не обязательно устойчивы к коллизиям, если они не криптографические
- Отсутствие сопротивления столкновению подразумевает возможность легко вычислять несколько значений с одним и тем же хеш-значением.
В случае коллизии ключевых слов структура данных с хэш-индексом нуждается в некотором плане b) — запасном алгоритме — о том, как обрабатывать несколько наборов данных с одинаковыми значениями хэш-значений ключевых слов.
На практике возможны несколько подходов:
- зондирование (переход к фиксированным или вычисляемым интервалам)
- множественное хеширование
- цепочка записей (создание списков встречных записей)
- переопределение существующих записей
Какая из этих стратегий использует Java? Сначала мы проверим код java.util. Hashtable (представлены только интересные части, остальная часть кода оставлена для ясности:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
|
public synchronized V put(K key, V value) { ... // Makes sure the key is not already in the hashtable. Entry tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) %tab.length; for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) { if((e.hash == hash) && e.key.equals(key)) { V old = e.value; e.value = value; return old; } } ... // Creates the new entry. Entry<K,V> e = tab[index]; tab[index] = new Entry<>(hash, key, value, e); count++; return null; } |
Как видно, этот класс использует функцию hashCode () ключевого объекта ( ключевое слово ) для вычисления значения хеш-функции. Он следует за ANDing (& оператор), для правильного представления в виде Integer, MODULO (оператор%) размер таблицы (построение циклической кольцевой структуры: (table.length + 1) mod table.length? 1, деление с остатками) всегда адрес записи во вкладке [].
После этого все Entry (-ies) рассматриваются и проверяются, идентичны ли значения хеш-функции и идентичен ли сам объект. Условие if предотвращает сохранение нескольких экземпляров одного и того же объекта — более старый заменяется новым.
Если в текущей позиции, идентифицированной key.hashCode (), не было найдено идентичного объекта (относительно хеш-значения и метода equals ()), будет создана новая запись , помещенная в текущую позицию и обработанная старым объектом записи в этой позиции.
Пока что похоже, что java.util.Hashtable использует какой-то список в качестве структуры данных за каждой вкладкой [].
Это предположение подтверждается при просмотре кода для java.util.Hashtable.Entry <K, V>, который является закрытым внутренним классом.
|
1
2
3
4
5
|
private static class Entry<K,V> implements Map.Entry<K,V> { int hash; K key; V value; Entry<K,V> next; |
Следующий объект Entry просто указывает на следующую запись . Это представляет собой специально созданный связанный список.
Код java.util.HashMap более сложен и ведет себя частично иначе (допускаются нулевые значения,! Несинхронизирован!), Но основан на той же идее. Исследование кода здесь не обнаружит ничего нового, кроме того факта, что Entry снова реализован…).
Обе реализации полагаются на связанные списки за каждой записью массива индексированного хэша.
Идея атаки
Теперь, когда мы знаем подробности реализации java.util.Hashtable и java.util.HashMap, мы можем вернуться к атаке, называемой HashDoS . Атака реализует идею Crosby, SA, Wallach, DS .: Отказ в обслуживании посредством атак алгоритмической сложности. В: Материалы 12-й конференции по USENIX Security Symposium — Том 12, Ассоциация USENIX (2003)
Подводя итог, можно сказать, что структура данных с хэш-индексированием может быть чрезвычайно замедлена из-за неблагоприятного состояния. Идеальная структура данных с хеш-индексом выглядит так:
|
1
2
3
4
5
6
|
... table[hash(keyA)] = dataA table[hash(keyB)] = dataB table[hash(keyC)] = dataC table[hash(keyD)] = dataD ... |
В этом случае время для изменения, удаления или добавления данных с ключевым словом с другим значением хеш-функции практически не меняется. Положение можно легко найти, используя хеш-значение ключевого слова в качестве индекса, и данные мгновенно отображаются без повторения списка.
Давайте посмотрим на другое, неблагоприятное состояние структуры данных с хэш-индексом:
|
1
2
3
4
5
6
|
... hash(keyA) == hash(keyB) == hash(keyC) == hash(keyD) = k table[k] = dataA -> dataB -> dataC -> dataD ... |
С такой структурой времена постоянного времени для CRUD-операций закончились …
- вычислить значение хеша для ключевого слова
- перебирать связанный список
- сравнить ключевое слово каждой записи, если оно совпадает с тем, которое ищет приложение
Это значительно замедляет поток обработки. Очень быстрая структура данных превратилась в связанный список с дополнительными издержками (вычисление хеш-значения). Все преимущества структуры данных с хеш-индексами уничтожены. Как будто это не так уж плохо, большинство структур данных с хеш-индексированием включают функцию, называемую перефразировкой. Когда структура данных превышает определенную нагрузку (в Java, например, на 75%), таблица перезаписывается по причинам оптимизации . В большинстве случаев эта функция абсолютно желательна, но в этом особом случае она еще более замедляет весь процесс.
Использование проблемы
Чтобы использовать это поведение, необходимо вычислить целую кучу сталкивающихся ключевых слов. Если мы предположим, что ключевое слово имеет тип java.lang.String, например, мы можем взглянуть на его функцию hashCode ():
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
|
public int hashCode() { int h = hash; if (h == 0) { int off = offset; char val[] = value; int len = count; for (int i = 0; i < len; i++) { h = 31*h + val[off++]; } hash = h; } return h; } |
Похоже, это настраиваемая версия функции под названием DJBX33A, разработанная DJ Bernstein, где легко можно обнаружить столкновения.
Функция обладает интересным свойством, которое будет продемонстрировано на следующем примере:
|
01
02
03
04
05
06
07
08
09
10
|
"0w".hashCode() = 1607 "1X".hashCode() = 1607 "29".hashCode() = 1607 "0w1X".hashCode() = 1545934 "0w29".hashCode() = 1545934 "1X0w".hashCode() = 1545934 "1X29".hashCode() = 1545934 "290w".hashCode() = 1545934 "291X".hashCode() = 1545934 ... |
Мы видим, что объединение конфликтующих значений снова приводит к конфликтующим значениям. Мы можем сделать это дальше и получить огромную коллекцию сталкивающихся ключевых слов. Это делает обнаружение столкновений еще более простым, чем просто грубое обращение.
Мы проверили это на локальном веб-сервисе и могли значительно замедлить работу сервера веб-приложений, используя сталкивающиеся ключевые слова в качестве атрибутов тега.
Я не уверен, можно ли на самом деле сломать машину или есть какой-то неочевидный механизм, предотвращающий самоконтроль сервера (мы не исследовали код обработки на стороне сервера), но однозначно можно предотвратить его действуя правильно в приемлемый период времени. Запросы к веб-сервису могут быть легко отложены.
Возможно, я приложу некоторые усилия для сбора данных измерений (#colliding keys — время реакции системы) в ближайшем будущем. Если я это сделаю, вы найдете данные в этом блоге …
Угловые очки взять с собой
- никогда не полагайтесь только на
hashCode()— он может быть подвержен ошибкам- избегать таких вещей, как
if(password.hashCode() == referencePassword.hashCode()) {
return godMode;
} else {
return simpleMode;
}- потратьте несколько секунд на детали реализации при принятии решения за / против типа / структуры данных
- фильтровать входящие данные — обрезать их размер, отклонять слишком длинные параметры и т. д.
- Будьте осторожны и всегда обращайте внимание на лучшие практики кодирования!
Другие интересные моменты, на которые стоит посмотреть
В этом примере мы использовали java.lang.String в качестве ключевых объектов. Было бы интересно, что еще можно было бы использовать и где в коде JRE или при интенсивно используемых проектах встречные хеш-значения используются для структурирования данных или даже в худших целях.
Можно было бы взглянуть на то, как реализован Object.hashCode () (это нативный код) — это было бы отличной целью, поскольку все другие объекты расширяют этот базовый класс. Если расширяющий класс не переопределяет функцию hashCode () и полагается на правильный вывод без столкновений, это может быть полезно для более сложных атак. Посмотрим, что произойдет, если сериализация опирается на соответствующий код …
Если кто-нибудь уже знает уязвимые места, пожалуйста, сообщите нам! Мы очень заинтересованы, но не можем смотреть так глубоко, как хотелось бы, из-за нехватки времени.
Спасибо
Еще раз хочу поблагодарить Юрая Соморовского за плодотворную совместную исследовательскую работу! Далее мы благодарим Андреа Барисани из команды oCERT и Винсента Данена из команды реагирования Red Hat Security, которые обсуждали эту проблему с нами!
Справка: расследование проблемы HashDoS от нашего партнера JCG