Словарные атаки на хэш-функции

Словарные атаки на хэш-функции

© Сергей Панасенко, 2009.

Хэширование информации (криптографическое преобразование информации произвольной длины в хэш-значение фиксированного размера) широко используется в современных компьютерных системах и сетях, в частности:

в различных сетевых протоколах;
в системах электронной подписи;
для хранения аутентифицирующей информации пользователей (например, паролей) и т. д.

Рассмотрим в данной статье словарные атаки – один из наиболее действенных видов атак на хэш-функции. Кроме того, в статье дан обзор других видов атак на алгоритмы хэширования и их реализации. Начнем со структуры типичного алгоритма хэширования.

Структура типичного алгоритма хэширования

Высокоуровневая структура типичного алгоритма хэширования (такую структуру имеют, в частности, широко используемые алгоритмы MD4, MD5, SHA-1 и многие другие) представлена на рис. 1.
Хэшируемое сообщение M разбивается на блоки определенной длины (например, 512 байтов в алгоритме SHA-1) M0…MN. Выполняется (по-разному в различных алгоритмах) дополнение сообщения M до размера, кратного данной длине блока (при этом, количество блоков может увеличиться).
Каждый i-й блок сообщения обрабатывается функцией fb(), являющейся криптографическим ядром алгоритма хэширования, причем данная функция накладывает результат этой обработки на текущее хэш-значение Hi-1 (т. е. результат обработки предыдущих блоков сообщения):

Hi = fb(Hi-1, Mi).

Результатом работы алгоритма хэширования hash() (т. е. хэш-значением сообщения M) является значение HN:

hash(M) = HN.

Начальное значение H-1 обычно является константным и различным в различных алгоритмах хэширования; оно часто обозначается как IV (от Initialization Vector – вектор инициализации).
Данная структура была предложена в 1988-1989 гг. независимо двумя известными криптологами: Ральфом Мерклем (Ralph Merkle) и Айвеном Дамгаардом (Ivan Damgard).

Словарные атаки

Словарная атака (dictionary attack) – это метод вскрытия какой-либо информации путем перебора возможных значений данной информации (здесь и далее для определенности в качестве мишени словарных атак будем рассматривать пароли пользователей, хранящиеся в виде их хэш-значений).
Название атаки произошло благодаря тому, что основу множества перебираемых паролей составляют слова какого-либо языка. Словарные атаки используют присущую большинству пользователей тенденцию к использованию легко запоминаемых паролей, к которым часто относятся различные слова и их варианты (например, замена части букв слова на похожие по написанию цифры или спецсимволы).
Словарные атаки часто классифицируют как один из вариантов атаки методом «грубой силы» (этот метод коротко описан ниже), поскольку здесь также выполняется перебор вариантов пароля или ключа. По сравнению с методом «грубой силы» словарные атаки осуществляют перебор по существенно меньшему множеству возможных значений.
Далее рассмотрим некоторые варианты словарных атак и методы противодействия им.

Словарная атака, основанная на предварительных вычислениях

Смысл данного варианта словарной атаки состоит в предварительном вычислении хэш-значений паролей, принадлежащих какому-либо множеству.
Путем такого вычисления атакующий получает таблицу соответствий входящих в множество паролей и их хэш-значений (см. рис. 2). Для нахождения искомого пароля, соответствующего известному злоумышленнику хэш-значению h, выполняется поиск хэш-значений в таблице, в результате которого делается один из следующих выводов:

если в таблице нашлась запись, соответствующая искомому значению h, то пароль p (для которого h = hash(p)) найден; при этом стоит учитывать, что, поскольку возможно возникновение коллизий (коллизией (collision) является ситуация, при которой два различных сообщения m1 и m2 имеют одно и то же хэш-значение h = hash(m1) = hash(m2)), найденный пароль может быть не искомым паролем, а паролем с эквивалентным искомому хэш-значением;
если записи со значением h в таблице нет, то искомый пароль не принадлежит к множеству, покрываемому данной таблицей; можно продолжить поиск с помощью других таблиц или применением других методов.

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

V(T) = (n + k) * |P|,

где P – множество паролей, покрываемое таблицей T, k – средний размер пароля в битах.

Цепочки хэш-значений

Использование цепочек хэш-значений (hash chains) – это улучшенный метод словарной атаки. Улучшение состоит в том, что при использовании цепочек на хранение таблицы паролей и соответствующих им хэш-значений требуется существенно меньше памяти, чем в случае классической словарной атаки.
Принцип действия цепочек хэш-значений основан на введении дополнительной функции R(), с помощью которой любому хэш-значению h можно псевдослучайным образом сопоставить некий пароль p из множества паролей P:

p = R(h).

С помощью функции R() и функции хэширования hash() можно сформировать цепочки из паролей p1…pN и соответствующих им хэш-значений h1…hN:

p1 h1 p2 h2 … pN hN. (1)

Известен простой пример функции R(): если множеством паролей является множество M-значных десятичных чисел, то выходным значением функции R() могут быть первые M цифр хэш-значения в десятичном представлении.
Исходные значения p1 для каждой цепочки могут выбираться по любому принципу, в том числе, генерироваться случайным образом в пределах покрываемого таблицей множества паролей.
Атакующий объединяет вычисленные таким образом цепочки в таблицу (см. рис. 3). Принципиальным моментом является то, что для уменьшения требуемой для хранения памяти сохраняется не вся таблица, а лишь первое и последнее значения (т. е. p1 и hN) для каждой строки.
При необходимости найти пароль, соответствующий заданному хэш-значению hx, атакующий вычисляет следующую цепочку:

hx px+1 hx+1 … px+N-1 hx+N-1. (2)

Каждое из получаемых в процессе данных вычислений значений hx+N-1 сравнивается с хранящимися в таблице значениями hN каждой строки. Если на каком-либо этапе обнаружены эквивалентные значения hx+N-1 и hN, то дальнейшие вычисления цепочки (2) не выполняются, а поиск требуемого пароля выполняется восстановлением данной строки таблицы, т. е. вычислением цепочки (1) до нахождения некоторого значения hj, равного hx. При нахождении такого значения искомый пароль определяется как значение pj данной цепочки.
Поскольку возможно возникновение коллизий, восстановление строки таблицы может не приводить к нахождению требуемого значения hj (см. пример на рис. 4; данный пример показывает также то, что коллизии уменьшают покрываемое таблицей множество паролей). В этом случае атакующий продолжает вычисления цепочки (2) до нахождения следующего совпадения hx+N-1 и hN. Если вычисления цепочки (2) завершены, а совпадения не найдены, то атакующим делается вывод о том, что данная таблица не содержит искомый пароль.
Значение N является параметром таблицы цепочек, от которого зависят две важные характеристики таблицы:

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

Варианты усиления цепочек хэш-значений

Как показано выше (см. рис. 4), возникновение коллизий может приводить к частичному совмещению строк таблицы, что, в свою очередь, приводит к уменьшению покрытия множества паролей при заданных размерах таблицы.
Вторая проблема – это «зацикленные» строки, возникающие из-за того, что в процессе вычисления строки произошло совпадение паролей (текущего и одного из предыдущих) или хэш-значений (т. е. для неких i и j pi = pj или hi = hj). Стоит отметить, что «зацикленные» строки могут быть обнаружены на этапе вычислений и отброшены.
Широкую известность получили два направления усиления таблиц цепочек хэш-значений. Первое из них – использование нескольких таблиц меньшего размера вместо одной большой таблицы. В каждой из таблиц используется своя функция преобразования из хэш-значения в пароль, т. е. в совокупности таблиц используются несколько функций R1()…RT() (где T – количество таблиц).
В этом случае при возникновении коллизий в разных таблицах не происходит дальнейшего совмещения строк, поскольку в разных таблицах используются различные функции R(). Коллизия в одной таблице приведет к совмещению строк, но вероятность такой коллизии в T раз меньше по сравнению с коллизией в разных таблицах.
Второе направление усиления – использование строк переменной длины (но не превышающей некоего порогового значения L). Строка таблицы завершается при вычислении некоего специфического значения hi. Пример такого специфического значения – хэш-значение, у которого значение первых двух байтов равно нулю (см. рис. 5). Следует, однако, учесть, что пороговое значение L должно быть достаточно большим, чтобы в подавляющем большинстве строк специфическое хэш-значение достигалось. Если же такое значение после вычисления L хэш-значений не достигается, то вычисляемая строка отбрасывается, поскольку считается «зацикленной».
Данный вид таблиц помогает и против совмещения строк при коллизиях, поскольку в этом случае обе строки приведут к одному и тому же специфическому значению. Таким образом, совмещенные строки легко обнаруживаются, после чего одну из таких строк (менее длинную) можно отбросить и пересчитать с другим начальным значением.
Это направление в настоящее время активно развивается наряду с радужными таблицами, подробно описанными далее.

Радужные таблицы

Радужная таблица (rainbow table) – это дальнейшее усиление эффективности цепочек хэш-значений. В радужных таблицах также используется последовательность функций преобразования из хэш-значения в пароль, но каждая функция Ri() используется для преобразования i-го хэш-значения hi в (i + 1)-й пароль pi+1. Таким образом, в таблице последовательно используются функции R1()…RN-1() (см. рис. 6).
Радужные таблицы обеспечивают более высокую скорость поиска паролей по сравнению с описанными выше вариантами при эквивалентных размерах (а также несколько более высокий процент покрытия множества паролей).
Две описанные выше проблемы таблиц цепочек хэш-значений решаются радужными таблицами достаточно элегантно:

«зацикленные» строки невозможны в принципе, поскольку в любой строке используется вся последовательность функций преобразования;
коллизия приводит к совмещению строк только в случае, если она возникает в одном столбце (вероятность чего в N раз меньше вероятности коллизии во всей таблице); следовательно, значения hN у таких строк становятся эквивалентными – лишнюю строку можно отбросить и пересчитать с другим начальным значением.

Поиск требуемого пароля в радужной таблице отличается от описанных выше вариантов; он выполняется следующим образом:

Сначала ищется совпадение заданного хэш-значения hx с каким-либо из значений hN таблицы.
Если совпадение не обнаружено, то предполагается, что hx должно совпадать с каким-либо из hN-1. Следовательно, вычисляется:

hx+1 = hash(RN-1(hx))

и сравнивается со значениями hN.

Если совпадение снова не найдено, предположение о местонахождении hx в таблице «смещается» еще на один столбец влево, т. е. с hN сравнивается уже следующее значение:

hx+2 = hash(RN-1(hash(RN-2(hx)))).

И так далее, до нахождения соответствия. Если соответствие найдено, то расчет искомого пароля выполняется с начала строки, как во всех описанных выше вариантах. Если же соответствие не найдено до завершения обработки предположения, что hx = h1, то искомый пароль в данной таблице отсутствует.

Название радужных таблиц произошло от аналогии каждой функции Ri() с каким-либо цветом, тогда таблица с длинными тонкими разноцветными полосками будет напоминать радугу (см. рис. 6). Радужные таблицы в настоящее время активно используются для атак на реальные криптосистемы. Например, широко известны проекты RainbowCrack (http://project-rainbowcrack.com), OPHCRACK (http://lasecwww.epfl.ch) и Free Rainbow Tables (http://www.freerainbowtables.com). Кроме того, специалистами рассматриваются варианты комбинирования радужных таблиц с таблицами, использующими специфические значения.
Стоит отметить, что все описанные в данной статье словарные атаки изначально предлагались к использованию для нахождения ключа симметричного шифрования, т. е. в качестве паролей (например, в радужной таблице) фигурируют ключи, а в качестве хэш-значений – результаты зашифрования константного блока открытого текста на конкретном ключе. Следовательно, функция R() в данном случае преобразует блок шифртекста в некий возможный ключ.

Противодействие словарным атакам

Известные криптологи Йохан Борст (Johan Borst), Барт Пренел (Bart Preneel) и Йос Вандевалле (Joos Vandewalle), предложившие в 1998 г. описанный выше метод использования цепочек переменной длины, утверждают, что возможность проведения словарных атак на криптосистемы обязательно должна учитываться при разработке систем защиты.
Наиболее действенным методом защиты от радужных таблиц и прочих видов словарных атак является дополнение (например, путем конкатенации) хэшируемого пароля какой-либо случайной величиной (salt), которая впоследствии хранится вместе с хэшированным паролем. Следовательно, для определения пароля атакующий должен рассмотреть также все множество значений данной величины.
Еще один вариант противодействия – многократный прогон пароля через функцию хэширования, что многократно увеличивает требуемое для атаки время. Многократное хэширование может использоваться и вместе с дополнительной случайной величиной, что делает атаку еще более сложно осуществимой. В качестве примера такого решения можно привести один из вариантов хэширования паролей UNIX с использованием модифицированного алгоритма шифрования DES: пароль дополняется 12-битным случайным значением и шифруется 25 раз для получения хэш-значения.
В 1999 г. на конференции USENIX Нильс Провос (Niels Provos) и Дэвид Мазьерес (David Mazieres) предложили аналогичный метод, заключающийся в хэшировании пароля специфическим алгоритмом (bcrypt), в котором многократно выполняется сложное преобразование (процедура расширения ключа известного алгоритма шифрования blowfish). В качестве параметров алгоритм bcrypt использует не только пароль и случайную величину, но и некий параметр, называемый «стоимостью» (cost), который определяет число прогонов процедуры расширения ключа (которое в точности равно 2^cost+1 + 1). Данный дополнительный параметр позволит настраивать систему в зависимости от требований безопасности, а также легко увеличивать требуемые для атаки ресурсы по мере прогресса в развитии вычислительной техники. Как и salt, данное значение хранится вместе с паролем.
Кроме того, хорошо защищают от словарных атак длинные сложные пароли (содержащие различные комбинации символов, спецсимволов и цифр), которые заведомо лежат вне множества паролей, покрываемых предвычисленными таблицами.

Другие виды атак на хэш-функции

Атаки методом грубой силы

Метод грубой силы (brute-force attack) предполагает перебор всех возможных вариантов каких-либо объектов (в частности, хэшируемых сообщений) до нахождения искомого значения (например, сообщения, соответствующего заданному хэш-значению).
Атаки методом грубой силы могут быть применены для достижения всех возможных целей атак на алгоритмы хэширования:

поиска коллизии;
поиска прообраза (прообразом (preimage) является сообщение, хэш-значение которого соответствует заданному; различают первый и второй прообразы: первый прообраз (first preimage) – сообщение m, для которого hash(m) равен заданному значению h; второй прообраз (second preimage) – сообщение m2, хэш которого hash(m2) равен хэшу заданного сообщения m1);
определения секретного ключа (для ключевых алгоритмов хэширования).

Рассмотрим последнюю из рассматриваемых целей. Пусть размер секретного ключа в битах равен b. Соответственно, существует 2^b вариантов ключа. Криптоаналитик должен методично перебрать все возможные ключи, т. е. (если рассматривать b-битную последовательность как число) применить в качестве ключа значение 0, затем 1, 2, 3 и т. д. до максимально возможного (2^b – 1). В результате секретный ключ обязательно будет найден, причем в среднем такой поиск потребует 2^b/2, т. е. 2^b-1 тестовых операций.
В качестве критерия корректности найденного ключа используется N пар сообщений и их хэш-значений. Поскольку при переборе ключей возможны коллизии, известно, что требуемое число пар для определения верного ключа несколько превышает значение b/n для n-битного алгоритма хэширования.
Защита от атак методом грубой силы весьма проста – достаточно лишь увеличить размер ключа: увеличение размера ключа на 1 бит увеличит количество ключей (и среднее время атаки) в 2 раза.
Существуют различные методы усиления эффективности атаки методом грубой силы, в частности:

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

Следует учесть, что с развитием вычислительной техники требования к размеру секретного ключа постоянно возрастают. Например, в конце 1995 г. ряд известных экспертов в области криптографии: Мэт Блейз (Matt Blaze), Уитфилд Диффи (Whitfield Diffie), Рональд Ривест (Ronald Rivest), Брюс Шнайер (Bruce Schneier), Цутому Шимомура (Tsutomu Shimomura), Эрик Томпсон (Eric Thompson) и Майкл Винер (Michael Wiener), – рекомендовали 90-битный размер ключа в качестве абсолютно безопасного с 20-летним запасом. Сейчас считается безопасным с примерно 80-летним запасом использование ключей размером от 128-битов.
В известной работе Даниэля Бернштейна (Daniel Bernstein) сказано, что, несмотря на всю силу параллельных атак методом грубой силы, криптографы уделяют данной проблеме достаточно мало внимания, допуская следующие ошибки при проектировании криптографических алгоритмов и протоколов и их реализации:

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

Атака методом грубой силы является «мерилом» эффективности других атак – атака тем эффективнее, чем быстрее она достигает требуемой цели, чем атака методом грубой силы. При этом, следует учесть, что теоретическая трудоемкость атаки методом грубой силы для n-битного алгоритма хэширования зависит от цели атаки и составляет:

2^n/2 операций хэширования атакуемым алгоритмом для поиска коллизии;
2ⁿ операций для поиска прообраза.

Использование парадокса «дней рождения»

Парадокс «дней рождения» состоит в том, что для получения из множества, содержащего N видов элементов, двух элементов одинакового вида, требуется сделать O( $sqrt$ ) попыток (поэтому атаки, использующие парадокс «дней рождения», называют также «атаками квадратного корня»). Например, в среднестатистической группе из 23 человек у двух человек совпадут дни рождения с вероятностью, превышающей 50%, что выглядит несколько удивительным (именно от этого примера получил название парадокс «дней рождения»). Данный парадокс активно используется в криптоанализе.
Именно благодаря парадоксу «дней рождения» атака методом грубой силы для поиска коллизии требует в 2^n/2 раз меньше операций, чем для поиска прообраза.
Парадокс «дней рождения» может быть напрямую использован для атак на хэш-функции, поскольку от него зависит трудоемкость, требуемая для нахождения коллизии. Еще в 1979 г. Гидеон Юваль (Gideon Yuval) привел пример следующей атаки, которую может выполнить злоумышленник:

Злоумышленнику необходимо выдать поддельный документ за действительный документ, подписанный неким пользователем системы.
Злоумышленник генерирует r вариантов поддельного документа и столько же вариантов оригинального документа (и в том, и в другом случае под «вариантами» подразумеваются документы, идентичные по смыслу, но различные в каких-либо деталях, незначащих в контексте документа, но приводящих к различным хэш-значениям). Значение r может быть вычислено с помощью парадокса «дней рождения»: например, 2^n/2 для n-битного алгоритма хэширования.
Злоумышленник выполняет поиск коллизий между оригинальными и поддельными документами. Если коллизия найдена, т. е. найдены оригинальный документ mx и поддельный документ fy, такие, что hash(mx) = hash(fy), то злоумышленник предлагает пользователю подписать именно вариант оригинального документа mx.
Электронная подпись пользователя вместо документа mx прикрепляется злоумышленником к документу fy. Подпись пользователя под подложным документом будет верна именно благодаря найденной злоумышленником коллизии.

Именно благодаря парадоксу «дней рождения» выходное значение алгоритмов хэширования должно быть достаточно большим – его размер в битах не менее, чем в два раза, должен превышать размер, достаточный для успешного противодействия атакам методом грубой силы, направленным на поиск прообраза. В 2003 г. Барт Пренел выполнил анализ требуемого размера выходного значения хэш-функций, достаточного для противостояния атакам, использующим парадокс «дней рождения», в том числе, для противодействия злоумышленникам, обладающим огромным (до 64 терабайт) объемом памяти и большим количеством атакующих рабочих станций. В результате автор данной работы делает вывод, что 160-битного хэша вполне достаточно с запасом, как минимум, на 20 лет вперед.
Весьма интересную особенность поиска коллизий с использованием парадокса «дней рождения» отметили в 2004 г. Михир Белэр (Mihir Bellare) и Тадайоши Коно (Tadayoshi Kohno). Они ввели понятие «регулярности» (amount of regularity) хэш-функций, которое, фактически, означает равномерность распределения возможных сообщений по множеству выходных значений алгоритма хэширования. Приведенные выше оценки трудоемкости поиска коллизий справедливы только для регулярных хэш-функций (т. е., другими словами, функций, в которых любые возможные хэш-значения встречаются одинаково часто). Для хэш-функций, которые не отличаются регулярностью, трудоемкость поиска коллизии может быть значительно ниже. Авторы данной работы предложили методики количественной оценки регулярности алгоритмов хэширования и оценки нижней границы трудоемкости поиска коллизии в зависимости от регулярности.

Использование специфических значений и параллельный поиск коллизий

Для оценки криптостойкости алгоритмов хэширования криптоаналитики часто используют различные методы поиска коллизий (в отличие от метода, описанного в предыдущем разделе, достаточно найденной коллизии у незначащих (абстрактных) сообщений) и сравнивают криптостойкость алгоритма с указанной выше теоретической. Рассмотрим далее наиболее простые методы поиска коллизий.
«Классический» поиск коллизий выполняется путем выбора некоторых базовых значений хэшируемых сообщений m0…mN, над которыми выполняется вычисление цепочек хэш-значений:

mi hash(mi) hash(hash(mi)) …

Все значения каждой из цепочек записываются и сравниваются с уже записанными. Совпадение значений сигнализирует о нахождении коллизии.
Такой подход требует весьма серьезных ресурсов памяти для хранения всех промежуточных результатов. В 1987 г. было предложено усовершенствование данного метода, заключающееся в том, что хранению в памяти подлежат не все промежуточные результаты вычислений, а только те из них, которые имеют специфические значения (аналогично использованию специфических значений в описанных выше словарных атаках); в качестве примера специфических значений были предложены значения с 20 нулевыми битами слева. При этом, только специфические значения сохраняются и сравниваются (остальные значения отбрасываются), что на несколько порядков снижает требования данного метода к памяти. Как и при классическом подходе, совпадение каких-либо специфических значений сигнализирует о нахождении коллизии. Аналогично вычислению цепочек хэш-значений переменной длины в словарных атаках, в данном методе поиска коллизий также устанавливается некое (весьма большое) пороговое значение максимальной длины цепочки, при достижении которого цепочка считается зацикленной и отбрасывается.
Несмотря на существенно сниженные требования к ресурсам метода со специфическими значениями (по сравнению с классическим подходом), Пол Ван Оорсхот (Paul van Oorschot) и Майкл Винер в 1994 г. утверждали, что «существующая технология поиска коллизий мало применима на практике, пока она не может эффективно распараллеливаться». Они предложили эффективный метод распараллеливания поиска коллизий, суть которого в следующем (см. приведенный в их работе рис. 7):

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

Данный метод распараллеливания был испытан авторами на практике для поиска коллизий в алгоритме хэширования MD5.

Атака «встреча посередине»

Данная атака направлена на вычисление прообраза для некоего хэш-значения. Атака «встреча посередине» считается одним из вариантов атаки, использующей парадокс «дней рождения», хотя она и используется не для поиска коллизий.
Атака применима к алгоритмам хэширования, раздельно обрабатывающим различные фрагменты хэшируемых сообщений, при этом, возможно инвертирование данной обработки. Предположим, алгоритм хэширования hash() можно представить как совокупность алгоритма hash1(), обрабатывающего первую половину сообщения, и алгоритма hash2(), обрабатывающего вторую половину (см. пример на рис. 8). Схема атаки «встреча посередине» на такой алгоритм приведена на рис. 9.
Цель атакующего – получение поддельного сообщения, хэш которого соответствует заданному значению H (предположим, некий документ с таким хэшем подписан субъектом атаки). В описанной выше атаке, использующей парадокс «дней рождения», злоумышленник генерирует множество вариантов корректного и поддельного сообщений, после чего выполняет поиск коллизии. Здесь же злоумышленник генерирует множество вариантов первой половины поддельного сообщения и множество вариантов второй половины. Каждый из вариантов первой половины обрабатывается алгоритмом hash1():

Tx = hash1(M1x, IV),

где M1x – один из вариантов первой половины сообщения;
Tx – промежуточное значение;
IV – начальное значение алгоритма хэширования.

Каждый из вариантов второй половины сообщения обрабатывается алгоритмом, обратным алгоритму hash2():

Ty = hash2^-1(M2y, H),

где M2y – один из вариантов второй половины сообщения.

Атакующий выполняет поиск совпадений значений T; при нахождении совпадения неких Ti = Tj можно считать, что соответствующие им половины сообщений Mi и Mj формируют то самое требуемое злоумышленнику поддельное сообщение.
Таким образом, в процессе этой атаки сравниваются на совпадение не хэш-значения, а промежуточные величины. Атака существенно более эффективна, чем описанный выше поиск коллизий с помощью парадокса «дней рождения». Противодействие подобным атакам состоит в использовании в алгоритмах хэширования неинвертируемых преобразований.

Использование корректирующих блоков

Атака с использованием корректирующих блоков используется, в основном, для поиска прообраза. Атака состоит в том, что атакующий заменяет все блоки исходного сообщения M с хэш-значением H на какие-либо другие, требующиеся ему блоки, за исключением одного или нескольких последних блоков, которые определенным образом заменяются так, чтобы хэш-значение сконструированного таким образом сообщения также было равно H.
Эти последние блоки называются корректирующими (correcting blocks), поскольку они корректируют изменения, вносимые предыдущими блоками, формируя в результате заданное хэш-значение. Наиболее часто используется один корректирующий блок.
Данная атака может использоваться и для поиска коллизий следующим образом:

выбираются произвольные начальные сообщения M и M’;
эти сообщения дополняются корректирующими блоками X и X’, такими, чтобы совпадали хэш-значения результатов конкатенации начальных сообщений и корректирующих блоков M || X и M’ || X’.

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

Использование неподвижных точек

Неподвижные точки (fixed points) возникают, когда промежуточные вычисления хэш-значения сообщения не меняют его текущего значения.
Неподвижная точка возникает в том случае, когда в процессе обработки какого-либо значения блока Mi текущее хэш-значение не изменяется, т. е. Hi остается равным Hi-1. В этом случае атака возможна путем добавления произвольного количества блоков со значением Mi, поскольку они не влияют на результат обработки.
Противодействие неподвижным точкам состоит во внедрении в хэшируемые данные размера сообщения (как это сделано, например, в хэш-функциях семейства SHA) или количества хэшируемых блоков.

Использование манипуляций на уровне блоков

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

Специфические атаки на хэш-функции, построенные на базе блочных шифров

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

наличие эквивалентных ключей;
возможность атаки на связанных ключах.

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

Дифференциальный криптоанализ

Данный метод атак был изобретен в 1990 г. известными израильскими криптологами Эли Бихамом (Eli Biham) и Ади Шамиром (Adi Shamir) и опубликован в ряде их работ. Однако, не менее известный криптолог Брюс Шнайер в своей книге «Прикладная криптография» утверждает, что дифференциальный криптоанализ был открыт существенно раньше, но не появлялся в открытой печати. Тем не менее, именно Бихам и Шамир до сих пор считаются изобретателями дифференциального криптоанализа.
Дифференциальный криптоанализ в равной степени применим как против алгоритмов симметричного шифрования (изначально дифференциальный криптоанализ был предложен для атаки на стандарт шифрования DES), так и против алгоритмов хэширования.
Дифференциальный криптоанализ основан на анализе пар сообщений, между которыми существует определенная разность (difference). Разность может быть определена, например, как результат операции XOR между обрабатываемыми фрагментами данных.
Дифференциальный криптоанализ успешно применялся многими криптологами для анализа различных алгоритмов хэширования, например, алгоритмов MD4, MD5 и SHA-0.

Алгебраический криптоанализ

Алгебраический криптоанализ использует алгебраические свойства анализируемого алгоритма.
Данный метод анализа в настоящее время активно используется против алгоритмов блочного симметричного шифрования. В частности, известно достаточно много работ, посвященных алгебраическому анализу стандарта шифрования AES.
В рамках алгебраического криптоанализа блочный шифр представляется в виде системы уравнений относительно значений битов ключа, решение которых находит искомый ключ или его фрагменты. Возможно использование алгебраического криптоанализа и в контексте других атак.
Есть примеры использования алгебраического криптоанализа и против алгоритмов хэширования – например, Макото Сугита (Makoto Sugita), Мицуру Кавазое (Mitsuru Kawazoe) и Хидеки Имаи (Hideki Imai) в 2006 г. успешно применили в комплексе алгебраический и дифференциальный криптоанализ для атаки на упрощенный вариант алгоритма SHA-1.

Атаки, использующие утечки данных по побочным каналам

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

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

Данную информацию криптоаналитик может использовать при атаке на реализацию алгоритма хэширования, а также в контексте других атак. Такие атаки называются атаками, использующими утечки данных по побочным каналам (side-channel attacks). Стоит, однако, сказать, что более часто эти атаки применяются против алгоритмов симметричного шифрования.

Атаки, использующие особенности протоколов верхнего уровня

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

Рисунки: