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

Ниже выдержки из статьи которая объясняет возможность атаки Denial Of Service (DoS) из-за неслучайных хеш-функций, используемых в Hash Data Structures.

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

Чтобы проверить это, я прошел через ссылочную реализацию 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 постоянно занятый. Если злоумышленник имеет соединение Gigabit, он может поддерживать занятость около 100 000 ядер i7

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

Ответ 1

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

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

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

Логическая структура этого HashMap такая:


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

Но физическая структура отличается. Ключи сначала преобразуются в hashCode, а затем hashCode преобразуется в индекс массива.

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


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" имеют одинаковый хэш-код.

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

Первая итерация: "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 строк с одинаковым хеш-кодом.

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

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

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

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

профилактика

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

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

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

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

Ответ 2

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

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

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

Ответ 3

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

Ответ 4

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

Ответ 5

Вот какой код на 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)