О необычном свойстве строки
Сегодня исполняется пятнадцатая годовщина мой работы здесь, в компании Microsoft. Сложно поверить, что я уже полтора десятилетия занимаюсь разработкой инструментов для разработчиков. Я невероятно счастлив работать в такой замечательной команде, над такими замечательными инструментами для таких замечательных пользователей. И я с радостью смотрю в будущее на следующие полтора десятилетия!
А теперь давайте вернемся к рассмотренной ранее загадке.
В прошлый раз я упомянул о двух интересных особенностях строки. Первой довольно любопытной особенностью является то, что хеш-код этой строки совпадает с хеш-кодом пустой строки. Один из читателей упомянул об этом в комментариях через полтора часа после публикации прошлой заметки.
Конечно, существует всего лишь четыре миллиарда возможных хеш-значений, и значительно больше четырех миллиардов возможных строк, поэтому коллизии неизбежны. Существует бесконечное множество строк, обладающих подобным свойством; но эта коллизия произошла для удивительно коротких строк.
Но значительно более интересной особенностью является то, что любое количество конкатенаций этой строки приводит к появлению строк, чье хеш-значение также равно хеш-значению пустой строки! На эту особенность обратили внимание ряд читателей.
Я намекнул на то, что любопытное свойство этой строки существует и у другой, распространенной строки. И, действительно, такое свойство, что при любом количестве конкатенаций хеш-значение не изменится присуще также и пустой строке. Ха-ха!
В первой подсказке я также обратил внимание, что одно из интересных свойств проявляется только на определенных платформах; оно проявляется только в выпуске 32-разрядной версии CLR v4. Как указано в документации, алгоритм расчета хеш-значения строки может изменяться с течением времени, и, действительно, недавно он изменился. В отладочной версии CLR алгоритм расчета хеш-значения строк изменяется каждый день для того, чтобы убедиться в том, что наш внутренний код не зависит от него.
Что приводит к появлению столь странной особенности у этой строки?
Алгоритм хеширования устроен довольно просто; в целом он заключается в том, что мы устанавливаем определенное начальное значение двум целым числам, а затем изменяем их на основе двоичного представления этой строки. Ради эффективности анализируется два символа строки (т.е. 4 байта) одновременно. Преобразование заключается в некоторой манипуляции битами типа сдвигов, сложения и тому подобном.
Алгоритм расчета хеш-значения можно рассматривать как конечный автомат с 64-разрядным состоянием. Каждые четыре байта строки изменяют 64 бита состояния. Окончательное значение получается на основе этого 64 разрядного состояния, полученного при обработке всех данных строки.
Эта конкретная последовательность четырех байт – A0 A2 A0 A2, преобразует начальное состояние в само себя. Если такая последовательность битов будет продолжать поступать на вход алгоритма расчета хеш-значения, то получаемое значение никогда не изменится, что приведет к тому, что результирующее хеш-значение будет равно хеш-коду пустой строки.
Если у вас есть функция f и значение x, такое, чтобы f(x) = x, то такое значение x называется «неподвижной точкой» функции f. То, что я нашел в этом случае, технически не является неподвижной точкой функции изменения состояния, но обладает подобным поведением. В математике и информатике неподвижные точки встречаются в разных вариантах; они обладают многими интересными и полезным свойствами, о которых я расскажу как-нибудь позднее. Сегодня же я хочу порассуждать немного о безопасности.
По сути, здесь мы получили способ создания произвольно большого количества строк с одинаковым хеш-кодом (*). Если злоумышленник сможет отправить множество подобных строк на сервер, который сохранит их в хеш-таблице, то атакующий может осуществить атаку типа отказ в обслуживании. Поскольку хеш-таблица не сможет хешировать строки в разные ячейки (buckets), то это добавление будет происходить все медленнее, медленнее и медленнее.
Не слишком серьезно для атаки, но это, все же, будет атакой (**).
Всегда, при обдумывании вариантов защиты от атак, нужно думать о «глубокой защите». Если ваше приложение может быть подвержено определенному типу атаки, предположите такой вариант, когда нападающий, для успешной атаки воспользуется несколькими маловероятными способами. Поступать, например, нужно следующим образом:
* Анализировать входные данные для гарантии того, что один пользователь не будет присылать огромные объемы данных для обработки; регулировать входной поток данных в случае необходимости.
* Отфильтровывать необычные символы из входного потока данных; для атаки на хеш-таблицы будут использоваться специальным образом подобранные данные. Маловероятно, что реальные пользователи будут отправлять строки с большим количеством символов китайской письменности носу.
* Анализировать производительности системы в поисках ее падения, что может означать наличие DoS-атаки.
* Создавать хеш-таблицы, использующие собственный алгоритм хеширования строк. При написании собственной хеш-таблицы сделайте начальное значение состояния и процесс преобразования случайным.
И так далее. Конечно же, это лишь набросок некоторых идей; если вы серьезно обеспокоены подобными атаками, то на самом деле будет довольно не просто спроектировать и реализовать хеш-таблицу, устойчивую к ним. Проконсультируйтесь с экспертом. (Я, кстати, не эксперт в этой области!)
----------
(*) Конечно, существует множество способов добиться коллизии хеш-значений; как я уже сказал ранее, существует бесконечное множество коллизий, поскольку существует всего лишь 4 миллиарда хеш-значений. Это лишь наиболее простой и дешевый способ нахождения коллизий.
(**) И, конечно же, как я убедился на собственном горьком опыте, атака злоумышленника на медленную хеш-таблицу является лишь частным случаем «атаки», которая из-за ошибок проектирования ведет к выполнению медленных участков кода.