Когда понимаешь, что каждый сервер в мире под угрозой

Хеш-таблицы. Словари. Ассоциативные массивы. Как бы вы их ни называли, в программном обеспечении они везде. Они — основа. И когда кто-то находит уязвимость в столь низкоуровневой структуре данных, почти всё программное обеспечение попадает под удар.

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

Хеш-таблицы 101

Хеш-таблицы невероятно удобны и быстры. Они дают возможность устанавливать метки на различные данные и бросать их в «блоки памяти», чтобы затем вытащить их обратно и использовать. Хеш-таблицы были изобретены в 1950-е, и принцип их работы с тех пор особо не изменился.

Создадим хеш-таблицу и что-нибудь в неё положим:

			h = {}
h['a'] = 6
h['b'] = 3
h['f'] = 9
print(h['a'])  # 6
		

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

В какой блок должен попасть ключ a при добавлении, учитывая, что нам нужно иметь возможность быстро его найти? Здесь на помощь приходит хеш-функция. Каждая хеш-таблица основана на детерминированной хеширующей функции, которая превращает любой ключ в большое число фиксированной длины, называемое хешем. Хешем a может быть, например, число 12416037344.

Если мы применим хеш-функцию к а ещё раз, мы всё равно получим 12416037344 благодаря её детерминированности. Получив хеш ключа, мы должны уменьшить его до номера блока (0–4 в нашем случае). Самый простой способ сделать это — вычислить остаток от деления хеша на количество блоков:

Отлично. Значит, a отправляется в блок номер 4.

Проделаем то же самое для b. Вычислим хеш, равный 1254403773, и получим остаток от деления, равный 1. Поэтому b пойдёт в блок номер 1.

А теперь добавим в таблицу f.

Хеш f равен 13056039271, а (13056039271 % 5) = 1. Но в блоке под таким номером уже что-то есть. Что теперь?

Мы столкнулись с коллизией. Коллизии в хеш-таблицах случаются довольно часто. Один из самых простых способов обойти их — сделать каждый блок списком и добавлять в него ключ каждый раз при возникновении коллизии. Это называется методом цепочек:

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

Почему бы просто не добавить больше блоков в таблицу? Со временем нам придётся это сделать, однако для этого необходимо пересчитать все хеши, поэтому не стоит выполнять такую операцию часто. Добавлять элементы в список гораздо быстрее.

Как правило.

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

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

1. Производительность. Само собой, она должна работать очень быстро.
2. Получение равномерной плотности. Хорошая хеш-функция должна равномерно распределять произвольные ключи по хеш-таблице, чтобы избегать коллизий как можно дольше.

Вот и всё. Про безопасность и не думали. С годами было разработано несколько очень простых и очень быстрых хеш-функций, которые хорошо работали несколько десятилетий.

Обнаружение уязвимости

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

В 2003 году в докладе, написанном Скоттом Кросби и Дэном Уаллахом из университета Райса, была описана такая уязвимость. Был обнаружен теоретический класс атак — атака на алгоритмическую сложность.

Читайте также: Оценка сложности алгоритмов, или Что такое О(log n).

Идея проста: если у нас есть алгоритм, обычно работающий с высокой скоростью O(1), где с малой вероятностью может произойти огромный O(n²) вложенный цикл, то алгоритм уязвим. В частности, если злоумышленник сможет привести приложение к такому циклу путём правильно подобранных входных данных, то он сможет перегрузить процессор.

Доклад описывает хеш-таблицы как возможный вектор атаки и даже воспроизводит атаки на несколько open-source проектов. Но, похоже, никто не обращал внимания на эту проблему, затрагивающую почти все реализации хеш-таблиц, вплоть до 2011 года, когда на 28-м Chaos Communication Congress Александр Клинк и Джулиан Уэлд продемонстрировали атаку на широком наборе языков программирования и серверов.

Атака на алгоритмическую сложность известна как атака на переполнение буфера, и Клинк с Уэлдом показали, что почти каждое веб-приложение, написанное на PHP, Ruby, Python, Java, ASP.NET и v8, было под ударом. Атакующие использовали обычную функцию платформы веб-приложений, которая преобразует параметры HTTP POST в хеш. Как Клинк с Уэлдом показали в демонстрации, эта функция присутствует даже в самой простой PHP-программе «Hello World»:

			<html>
  <body>
    <?php echo '<p>Hello World</p>'; ?> 
  </body>
</html>
		

Это было катастрофой. Атака могла положить сервер, на котором запущен любой, даже элементарный, вроде «Hello World», PHP-скрипт.

Суть атаки состоит в том, чтобы заранее выяснить, какие ключи могут привести к коллизии. Хеш-функции, которые тогда использовались, было легко инвертировать и создать тонну ключей для атаки. Для большинства веб-приложений атака включала в себя отправку большого (1 МБ) HTTP POST-запроса, который бы создал на сервере хеш-таблицу с 10 000 или даже с 100 000 коллизий. По мере роста количества коллизий время вставки каждого дополнительного элемента увеличивается до O(n²) и процессор загружается на 99%.

Ответные меры

Это был 2011 год. В ответ на находку Клинка и Уэлда большинство языков начали применять seed-значение — секретные случайные данные, используемые для инициализации хеш-функции. Без seed-значения атакующий не может просто инвертировать общую хеш-функцию на своей машине и получить список ключей для коллизии.

И это сработало.

Правда, на год или около того.

Затем в 2012, на конференции 29c3, этот метод обошли более сложной коллизионной атакой, использующей дифференциальный криптоанализ. Не вдаваясь в подробности, можно сказать, что случайное seed-значение на самом деле не сильно меняет выход хеш-функции, и её снова можно атаковать с помощью специально подобранных значений.

Все распространённые хеш-функции общего назначения были уязвимы к этой атаке.

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

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

На конференции 29c3 Бернштейн и Аумассон представили SipHash — криптографическую хеш-функцию, которая была гораздо быстрее предыдущих алгоритмов. В ней был найден необходимый баланс между безопасностью, производительностью и равномерностью выходных значений. На самом деле, существуют различные версии SipHash, позволяющие разработчикам найти свой баланс между безопасностью и производительностью. В конце концов, безопасность — лишь вопрос сложности атаки. Ничто не является поистине защищённым.

SipHash — отличное изобретение и всего лишь один из примеров неустанной закулисной работы, которую выполняет сообщество безопасности для защиты серверов от атак. Бернштейн и Аумассон не только нашли уязвимость и продемонстрировали её опасность, но и придумали элегантное решение проблемы. К 2013 множество языков программирования сделали SipHash основной хеш-функцией.

SipHash безопасна. По крайней мере, пока.  И хотя никто ещё не нашёл способ быстро сгенерировать много коллизий с SipHash, никто не доказал, что это невозможно.