На проходящей в Берлине конференции Chaos Communication Congress (28c3) обнародован новый способ нарушения работоспособности web-сервисов, основанный на особенности реализации структур хэшей, используемых для организации хранения наборов данных в представлении ключ/значение, в широком спектре языков программирования. Манипулируя используемыми в качестве ключей данными, атакующий может затратив минимальные ресурсы инициировать возникновение предсказуемых коллизий в алгоритме хэширования, разрешение которых требует дополнительных значительных процессорных ресурсов.

Большинство web-фреймворков и web-приложений на этапе разбора HTTP POST-запроса автоматически размещают передаваемые пользователем параметры в хэше, что позволяет атакующему контролировать наполнение хэша. В зависимости от языка программирования для достижение 100% загрузки CPU достаточно сформировать поток запросов интенсивностью всего в несколько килобит в секунду. При этом степень создаваемой нагрузки пропорциональна размеру передаваемого в хэш числа ключей с коллизиями. Хэш-функция генерирует на основании строки 64- или 32-разрядное целое число, при возникновении коллизии две разные входные строки дают одинаковое итоговое число. При обнаружении коллизии в хэш-функциях используются различные методы для обеспечения хранения вызывающих коллизии значений, как правило требующие дополнительного перебора и сверки значений (совпадающие значения сохраняются в виде дерева или линейного списка). Трудоёмкость добавления "n" проблемных ключей составляет O(n**2), т.е. на разбор большого числа вызывающих коллизии ключей современному CPU могут потребоваться часы.

Например, при лимите на размер POST запроса в 1 Мб, Python фреймворк Plone тратит около 7 минут процессорного времени на запись в хэш 1 Мб данных (набор специально оформленных ключей), вызывающих коллизии (для успешной DoS-атаки на CPU Core Duo достаточно потока в 20 kbit/s). Для фреймворков на языке Ruby 1.8.7 при лимите на размер POST-запроса в 2 Мб на парсинг двухмегабайтного блока данных на CPU i7 будет потрачено около 6 часов (!), т.е. для поддержания постоянной 100% нагрузки достаточно потока в 850 бит в секунду. Для PHP разбор POST-запроса размером 300 Кб занимает примерно 30 секунд процессорного времени, 500 Кб - минуту, 8 Мб - около 5 часов.

Проблеме подвержены все языки программирования и фреймворки, в которых не используется дополнительная рандомизация значений в функциях хэширования, например, уязвимы Java (Tomcat, Geronimо, Jetty, Glassfish), JRuby, PHP, Python, Rubinius, Ruby 1.8.7, V8 JavaScript Engine и ASP.NET. Проблема не затрагивает язык Perl и ветку Ruby 1.9.x, так как в этих языках уже используется внесение случайных изменений при формировании хэшей. В Perl проблема была устранена ещё в 2003 году, после публикации отчёта о возможности совершения подобной атаки. В PHP уязвимость исправлена в версии 5.4.0RC4, также планируется выпустить корректирующий релиз PHP 5.3.9. Проблема также исправлена в CRuby 1.8.7-p357, JRuby 1.6.5.1, Apache Tomcat 5.5.34/6.0.34/7.0.22, Rack 1.4.0/1.3.6/1.2.5/1.1.3. Эксплуатация проблемы в Python и Ruby имеет дополнительные нюансы, отличающиеся для 64- и 32-разрядных сборок.

Предсказать вызывающие коллизии значения не представляет труда, так как в вышеупомянутых языках как правило используются две реализации хэш-функций DJBX33A и DJBX33X, разработанные Дэниэлом Бернштейном (Daniel Bernstein, автор qmail и djbdns). Хэш-функция DJBX33A используется в PHP5, Ruby 1.8 и Java. DJBX33X в PHP4, ASP.NET, Python и JavaScript (v8). Кроме языков программирования данные хэш-функции применяются в широком спектре проектов, от ядра Linux до социальной сети Facebook, а также в таких языках, как Lua, Erlang и Objective-C, что открывает возможные новые векторы для атак.

В качестве мер для минимизации влияния представленной атаки называется ограничение максимального процессорного времени, затрачиваемого на выполнение скрипта (RLimitCPU в Apache или max_input_time в настройках PHP), ограничение максимального размера POST-запроса (для PHP - post_max_size) и ограничение максимального числа разбираемых параметров (в php 5.4 или suhosin-сборке PHP - suhosin.post.max_vars и suhosin.request.max_vars).