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

Ниже выдержки из статьи которая объясняет возможность атаки 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 и т.д.), Которые полагаются на эту реализацию.

4b9b3361

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

Как работает HashMap

Скажем, что форма комментариев в блоге принимает параметры - first_name, last_name, комментарии как параметры сообщения. Внутри 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"

Конфликты Hash и влияние на производительность

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

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

Как вы создаете ключи с тем же Hash?

В 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 строк, имеющих один и тот же хэш-код.

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

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

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

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

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

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

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

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

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

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

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

47
ответ дан 29 дек. '12 в 20:55
источник

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

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

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

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

3
ответ дан 29 дек. '12 в 19:44
источник

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

1
ответ дан 29 дек. '12 в 19:14
источник

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

0
ответ дан 06 янв. '12 в 9:16
источник

Вот какой код на 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)
0
ответ дан 29 мая '12 в 20:31
источник