Универсальное хеширование: случайность против злого входа

Если ты понимаешь, почему фиксированную хеш-функцию можно атаковать, что такое универсальное семейство (Pr[коллизия] ≤ 1/m по случайному h) и почему это даёт O(1) в ожидании на ЛЮБОМ входе, листай до «Теперь сам».

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

Хеш-таблица даёт O(1) в среднем ПРИ равномерном разбросе ключей. Но «средний» случай считался в предположении, что ключи приходят как попало. А если их подбирает ВРАГ? Хеш- функция обычно известна (она в открытом коде библиотеки). Противник берёт h, находит кучу ключей с одним значением h(k) - например, все дающие остаток 0 по модулю m - и шлёт их твоему серверу. Все они падают в ОДНУ ячейку, цепочка вырастает до n, каждый поиск и вставка становятся O(n), таблица захлёбывается. Это не теория: так реально клали веб- сервисы (атака на хеш-таблицы HTTP-параметров). Раз фиксированную функцию можно вычислить и обмануть, надо лишить противника этой возможности.

На что это похоже

Сейф с одним заводским кодом против сейфа со случайным кодом. Если у ВСЕХ сейфов модели код «0000» (фиксированная функция), взломщик, узнав его однажды, открывает любой. Если каждый сейф при установке получает СВОЙ случайный код из огромного набора, взломщику нечего заучивать: он не знает код именно твоего сейфа. Универсальное хеширование - это случайный код для каждой таблицы: семейство функций как набор возможных кодов, а конкретная таблица тайно выбирает одну. Враг знает СЕМЕЙСТВО (модель сейфа), но не знает, какую функцию выбрала ты, - и не может подобрать ключи под неё.

Механизм: семейство функций и случайный выбор

Вместо одной функции берём целое СЕМЕЙСТВО H = {h₁, h₂, …}. При создании таблицы выбираем из него ОДНУ случайную функцию h и пользуемся ею всё время жизни таблицы.

создать_таблицу():
    h = случайная функция из семейства H     # выбор один раз, при создании
    # дальше все операции используют это h

# пример универсального семейства для целых ключей (метод Картера-Вегмана):
#   выбрать простое p > максимального ключа
#   выбрать случайные a ∈ [1, p−1], b ∈ [0, p−1]
#   h(k) = ((a·k + b) mod p) mod m
# случайность спрятана в a и b - их знает только таблица

Семейство H называют универсальным, если для ЛЮБЫХ двух разных ключей k₁ ≠ k₂ вероятность коллизии по случайному выбору h мала:

Pr[h(k₁) = h(k₂)] ≤ 1/m        (вероятность по выбору h из H)

Это ровно та вероятность, что была бы у идеально случайного разбрасывания. Отсюда: ожидаемая длина цепочки для любого ключа - 1 + α, как при равномерном хеше, но теперь ГАРАНТИРОВАННО на любых данных, а не в предположении «ключи как попало».

Правило

Фиксированная хеш-функция уязвима: зная её, противник подбирает ключи с одним h(k) и превращает O(1) в O(n) (реальная атака). Универсальное хеширование берёт СЕМЕЙСТВО функций и выбирает из него СЛУЧАЙНУЮ при создании таблицы. Семейство универсально, если для любых k₁ ≠ k₂ вероятность Pr[h(k₁) = h(k₂)] ≤ 1/m (по выбору h). Тогда ожидаемая длина цепочки 1 + α ГАРАНТИРОВАНА на ЛЮБОМ входе - враг не знает выбранную функцию и не может подстроить ключи. Источник неудачи переносится с данных на случайный выбор функции.

Разбор: почему это защищает даже от знающего семейство противника

Тонкость: противник ЗНАЕТ семейство H (оно в открытом коде) - разве это не то же, что знать функцию? Нет, и разница решающая. Знать семейство - знать НАБОР возможных функций, но не конкретную, выбранную твоей таблицей (её задают тайные случайные a, b). Чтобы гарантированно устроить коллизию, врагу нужно подобрать ключи, сталкивающиеся при ТВОЁМ h, - а он его не знает. Для любой пары ключей вероятность коллизии по случайному h не больше 1/m - значит какие бы ключи враг ни прислал, в среднем (по нашему случайному выбору) они разбросаются ровно. Он может знать всё про алгоритм и всё равно не сможет надёжно атаковать - потому что не контролирует нашу монетку. Это тот же принцип, что у рандомизированного quickselect из прошлого раздела: случайность ВНУТРИ алгоритма обезоруживает злой вход СНАРУЖИ.

Разбор: почему «в ожидании», а не «гарантированно»

Как и рандомизация опорного, универсальное хеширование даёт ОЖИДАНИЕ, а не железную гарантию на каждый случай. Может не повезти: конкретный случайный выбор a, b окажется неудачным для пришедших ключей, и цепочка выйдет длинной. Но вероятность этого мала и, главное, не управляется противником - она зависит от нашей монетки, а не от его данных. Ожидаемое время O(1 + α) на любом входе - сильная гарантия для практики (веб-сервер защищён от намеренной перегрузки), но это НЕ «O(1) всегда, что бы ни случилось». Железную гарантию O(1) в худшем случае даёт другое - идеальное хеширование (следующий урок), но только для СТАТИЧНОГО, заранее известного набора ключей. Различать «ожидаемо» и «гарантированно» здесь так же важно, как в задаче выбора: рандомизация покупает защиту от врага ценой крошечной вероятности невезения.

Что ломается без этого

Первая ошибка - использовать фиксированную, публично известную хеш-функцию для данных из недоверенного источника (HTTP-параметры, имена файлов от пользователя, ключи из сети): открыт путь к атаке перегрузкой, O(n) на операцию. Современные языки поэтому солят хеш строк случайным семенем при старте (Python с 2012 года - PYTHONHASHSEED) - это и есть универсальное хеширование в действии. Второе - выбирать случайную функцию на КАЖДУЮ операцию, а не один раз при создании: тогда один и тот же ключ будет попадать в разные ячейки, и ты его не найдёшь (нарушен детерминизм в пределах жизни таблицы). Функция выбирается однажды. Третье - думать, что универсальность даёт гарантию в худшем случае: она даёт ОЖИДАНИЕ. Четвёртое - брать «семейство» из двух-трёх функций: чем оно беднее, тем легче врагу перебрать варианты; нужно большое семейство.

Зачем это в работе

Универсальное хеширование - это защита реальных систем от атак на хеш-таблицы. После волны атак «HashDoS» (2011-2012), клавших веб-серверы горстью специально подобранных параметров, языки массово перешли на рандомизированное хеширование строк: Python, Ruby, Perl, JavaScript- движки солят хеш случайным семенем при запуске процесса. Понимать это - значит знать, почему hash("строка") в Python даёт РАЗНЫЕ значения в разных запусках (это не баг, а защита) и почему нельзя закладываться на конкретные хеши между запусками. Шире - это ещё один пример могущества рандомизации: там, где детерминированный алгоритм уязвим к подобранному входу, случайность внутри превращает уязвимость в надёжное ожидание. Тот же приём ты уже видел в выборе k-го элемента; здесь он защищает словари, и узнавание этого паттерна - признак зрелого инженера.

Теперь сам

Противник знает, что твой сервер использует h(k) = k mod 1000, и шлёт ключи 1000, 2000, 3000, … (тысячу штук). Что произойдёт с таблицей и как универсальное хеширование это предотвратило бы?