Уязвимость приложения из-за неслучайных хэш-функций

Question

Ниже приводится выдержка из статьи , в которой объясняется возможность атаки DoS из-за неслучайных хэш-функций, используемых в структурах хэш-данных.

[…] условие можно использовать, используя предсказуемые коллизии в базовых алгоритмах хеширования.

Чтобы проверить это, я прошел эталонную реализацию Java HashMap из Oracle и действительно нашел статические хеш-функции, используемые:

    static int hash(int h) {
       h ^= (h >>> 20) ^ (h >>> 12);
       return h ^ (h >>> 7) ^ (h >>> 4);
    }

Другая статья по теме рассказывает:

Сервер Tomcat 6.0.32 анализирует строку конфликтующих ключей размером 2 МБ примерно 44 минуты процессорного времени i7, поэтому злоумышленник со скоростью около 6 кбит / с может постоянно держать одно ядро ​​i7 занятый. Если у злоумышленника есть гигабитное соединение, он может поддерживать около 100 000 ядер i7

Как мы можем защитить от этой уязвимости. Более того, с таким количеством программного обеспечения мы используем открытый исходный код (Tomcat и т. Д.), Которые полагаются на эту реализацию.

Answer 1

Понимание вектора атаки

Как работают HashMaps

Скажем, форма комментария в блоге принимает параметры - first_name, last_name, comment - в качестве параметров публикации.Внутри Tomcat сохраняет эти параметры в виде HashMap.

Логическая структура этого HashMap выглядит следующим образом -

"first_name" --> "Sripathi"
"last_name" --> "Krishnan"
"comment" ---> "DoS using poor Hashes"

Но физическая структура это отличается.Сначала ключи преобразуются в хеш-код, а затем хэш-код преобразуется в индекс массива.

Идеальная физическая структура , таким образом, становится -

0 --> "Sripathi"
1 --> "Krishnan"
2 --> "DoS using poor Hashes"

Новозможные ключи бесконечны.Так что в какой-то момент два ключа будут иметь одинаковый хеш-код.Это становится столкновением хэшей.

При столкновениях физическая структура становится:

0 --> "Sripathi", "Krishnan"
1 --> Empty
2 --> "DoS using poor hashes"

Коллизии хэширования и влияние на производительность

Если у вас есть коллизии хэшей, вставьте новуюЗапись означает перебор всех элементов в одном «хэше» хэша последовательно только для того, чтобы выяснить, существует ли он уже на карте.Вставка одного элемента может приблизить сложность O (n), если все элементы хешируют к одному значению.Вставка n элементов в этом наихудшем случае усложняет O (n * n).

Вкратце: если вы вставите тысячи ключей с одинаковым hashCode , серверу потребуется много циклов ЦП.

Как генерировать ключи с помощьютот же хэш?

В Java "Aa" и "BB" имеют одинаковый хэш-код.

Из-за свойства, называемого "Эквивалентные подстроки", мы можем сгенерировать несколько других строк с одинаковымихэш-код, просто начиная с этих двух строк.

Первая итерация: «AAAA», «AABb», «BbAA», «BbBb» имеют одинаковый хеш-код

Теперь у нас есть 4строки с одинаковым хеш-кодом.Мы можем переставить их для генерации 16 строк, которые будут иметь одинаковый хэш-код.Например:

"AaAaAaAa", "AaAaBBBB", "AaAaAaBB", "AaAaBBAa",
"BBBBAaAa", "BBBBBBBB", "BBBBAaBB", "BBBBBBAa",
"AaBBAaAa", "AaBBBBBB", "AaBBAaBB", "AaBBBBAa",
"BBAaAaAa", "BBAaBBBB", "BBAaAaBB", "BBAaBBAa",

Все эти 16 строк имеют одинаковый хеш-код.

Теперь вы можете взять эти 16 строк и сгенерировать 256 строк с одинаковым хеш-кодом.

Короче говоря: очень легко создать большой набор строк, которые будут иметь точный хеш-код.

Как вы атакуете сервер?

1. Создайте тысячи строк с одинаковым хеш-кодом (см. Выше)
2. Создайте запрос POST следующим образом - AaAa = & AaBB = & BBAa = & BBBB = ....
3. Отправьте форму
4. Повторите в цикле и создайте несколько потоков, чтобы все ресурсы сервера были использованы

Поскольку это всего лишь POST-запрос, злоумышленник может также использовать невинные браузеры для атаки на сервер.Просто найдите веб-сайт с уязвимостью межсайтового скриптинга, вставьте код для отправки запроса POST, а затем используйте социальную инженерию, чтобы распространить ссылку как можно большему числу пользователей.

Предотвращение

ВВ общем, базовая платформа не может это исправить.Это считается проблемой структуры приложения.Другими словами, Tomcat должен это исправить, а не Oracle / Sun.

Возможные исправления включают в себя:

1. Ограничение количества параметров POST -У Tomcat 6.0.35+ появился новый параметр maxParameterCount .Значение по умолчанию составляет 10000.Чем ниже, тем лучше, если это не нарушает вашу функциональность.

2. Ограничить размер запроса POST - Чтобы атака работала, полезная нагрузка должна быть огромной.POST по умолчанию, разрешенный Tomcat, составляет 2 МБ.Сокращение этого до 200КБ снизит эффективность этой атаки.Параметр в tomcat: maxPostSize

3. Брандмауэр веб-приложения - Если у вас есть брандмауэр веб-приложения, вы можете настроить его для блокировки запросоввыглядеть подозрительноЭто реактивная мера, но ее приятно иметь в случае, если вы не можете использовать одно из вышеуказанных решений.

К вашему сведению - документация Tomcat находится здесь - http://tomcat.apache.org/tomcat-6.0-doc/config/http.html

Answer 2

Самым простым решением является обновление до фиксированной версии Tomcat. Тем не менее, я подозреваю, что вы хотите знать подробности того, что люди из кота должны были бы изменить.

Эта атака работает за счет использования общих деталей реализации структур данных хеша - использование связанных списков для хранения всех значений, хеш которых одинаков. Добавление значений в этот связанный список неэффективно, так как размер списка становится большим. Злоумышленник может создать список значений, которые, как известно, генерируют сталкивающиеся хэши, заставляя это неэффективное поведение. Чтобы защититься от этого, у вас есть несколько вариантов:

• Предотвращение коллизий - не позволяет злоумышленнику генерировать коллизионные значения, используя некоторый (псевдо) случайный коэффициент в вашей хэш-функции. Perl делал это долгое время.

• Используйте что-то кроме связанных списков для своих групп - атака работает, потому что вставка N элементов в связанный список приводит к росту N ^ 2. Если при вставке вы используете сбалансированное дерево или какую-либо другую структуру, которая имеет рост N logN, проблема должна быть смягчена. Это может принести в жертву некоторую производительность в лучшем / среднем случае, чтобы ограничить, насколько плохим является худший случай.

Answer 3

Версия Tomcat затрагивает Apache Tomcat <= 5.5.34, <= 6.0.34, <= 7.0.22 по предоставленной вами ссылке.На странице перечислены Apache Tomcat> = 5.5.35,> = 6.0.35,> = 7.0.23 в качестве фиксированных версий.

Answer 4

Вот некоторый код на Python для генерации этих ключей ... Еще не тестировал его, но был бы заинтересован получить отзыв о нем:

#!/usr/bin/python
import sys
alphabet = ["Aa","BB"]

def func(str, length):
                global alphabet
                if(length != 0):
                                for x in alphabet:
                                                new_str = str+x
                                                func(new_str, length-1)
                else:
                                sys.stdout.write(str+"=&")


for x in range(1,16):
        func("",x)

Answer 5

Java HashMap / HashTable может выполнять операцию «изменения размера», когда заполненная запись достигает порога. Трудно сказать, что вас ждет фиксированная корзина HashMap. Из-за операции по выбору сегмента есть два шага: один - принять значение хеша указанного ключа; Другой основной шаг - операция с оставшимся размером с общим размером сегмента (размер был изменен с помощью «resize»).