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

Как работают хэш-карты

Скажем, форма комментариев в блоге принимает параметры — 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).

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

Как вы генерируете ключи с одним и тем же хэшем?

В 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. Значение по умолчанию — 10 000. Чем ниже, тем лучше, если это не нарушает вашу функциональность.

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

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

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

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

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

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

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

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

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

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