SHA-0

SHA-0 — это криптографическая хеш-функция, разработанная Агентством национальной безопасности США (АНБ) и опубликованная в 1993 году как стандарт Федерального правительства США под названием Secure Hash Algorithm (SHA). Она является предшественницей более известных алгоритмов семейства SHA-1 и SHA-2, но была отозвана вскоре после публикации из-за обнаруженной уязвимости, которая делала её небезопасной для использования. SHA-0 не следует путать с SHA-1, который является исправленной версией и также в настоящее время считается небезопасным.

История

Разработка SHA-0 началась в конце 1980-х годов как часть усилий АНБ по созданию криптографических стандартов для правительственных и коммерческих нужд. Алгоритм был опубликован в 1993 году в Федеральном регистре США как проект стандарта. В отличие от своего предшественника, MD5, SHA-0 имел более длинный хеш (160 бит против 128 бит), что должно было повысить устойчивость к коллизиям.

Однако вскоре после публикации, в 1994 году, группа исследователей из Национального института стандартов и технологий (NIST) и АНБ обнаружила в алгоритме недокументированную уязвимость. Точная природа дефекта долгое время оставалась засекреченной, но известно, что он был связан с недостаточной нелинейностью в функции сжатия. В результате NIST отозвал SHA-0 и заменил его на SHA-1, который содержал одно небольшое, но критическое изменение: в функции сжатия была добавлена дополнительная операция поворота битов (ротация), что значительно усложнило поиск коллизий. SHA-1 был опубликован в 1995 году и стал стандартом.

Алгоритм

SHA-0, как и SHA-1, относится к классу хеш-функций семейства MD4/MD5. Он принимает на вход сообщение произвольной длины и выдает 160-битный (20-байтовый) хеш-код. Алгоритм состоит из нескольких этапов:

1. Дополнение сообщения

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

2. Инициализация

Используется 160-битный буфер, состоящий из пяти 32-битных регистров (A, B, C, D, E). Начальные значения этих регистров фиксированы и являются константами, полученными из шестнадцатеричной записи квадратных корней из первых пяти простых чисел.

3. Обработка блоков

Каждый 512-битный блок сообщения обрабатывается в 80 раундов. Для каждого раунда используется:

• Функция сжатия: В зависимости от номера раунда (0–19, 20–39, 40–59, 60–79) применяется одна из четырёх нелинейных булевых функций (f1, f2, f3, f4). В SHA-0, в отличие от SHA-1, в раундах 16–79 не выполнялась операция циклического сдвига (ротации) на один бит для значений, полученных из предыдущих раундов. Это и было ключевым недостатком.
• Константы: Для каждого раунда используется фиксированная 32-битная константа (Kt).
• Расширение сообщения: Из 512-битного блока генерируется 80 32-битных слов (Wt). Процедура расширения в SHA-0 была более прямолинейной, чем в SHA-1.

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

Уязвимость и криптоанализ

Основная уязвимость SHA-0 была обнаружена вскоре после его публикации. В 1998 году французские криптоаналитики Флоран Шабо и Антуан Жу опубликовали работу, в которой показали, что SHA-0 значительно слабее SHA-1. Они продемонстрировали, что для нахождения коллизий (двух разных сообщений с одинаковым хешем) в SHA-0 требуется около 2^61 операций, что было значительно меньше теоретической стойкости в 2^80 операций (поскольку 160-битный хеш должен обеспечивать стойкость 2^80 к коллизиям).

В 2004 году группа исследователей под руководством Сяоюня Ван (Wang Xiaoyun) из Шаньдунского университета (Китай) объявила о полном взломе SHA-0. Они нашли практический метод нахождения коллизий, требующий всего около 2^39 операций. Этот результат был подтверждён на практике: была найдена пара 512-битных сообщений, дающих одинаковый хеш SHA-0. Позднее, в 2005 году, та же группа исследователей продемонстрировала коллизии для SHA-1, что привело к постепенному отказу от SHA-1 в пользу SHA-2.

Применение

Из-за быстрого отзыва и замены на SHA-1, SHA-0 практически не использовался в реальных системах. Некоторые ранние реализации протоколов безопасности, такие как ранние версии SSL (Secure Sockets Layer) или некоторые реализации PGP (Pretty Good Privacy), могли включать SHA-0 в качестве опции, но это было крайне редко. Основное применение SHA-0 сегодня — это учебные цели и криптоаналитические исследования. Он используется для демонстрации принципов работы хеш-функций и для изучения методов поиска коллизий.

Сравнение с SHA-1

Основное отличие SHA-0 от SHA-1 заключается в одном бите в алгоритме расширения сообщения. В SHA-1, в раундах 16–79, перед использованием в функции сжатия, каждое слово Wt подвергается циклическому сдвигу на один бит влево. В SHA-0 этого сдвига не было. Это небольшое изменение сделало SHA-1 значительно более устойчивым к коллизиям, хотя впоследствии и SHA-1 был взломан.

Интересные факты

• Название «SHA-0» не является официальным. В оригинальной публикации 1993 года алгоритм назывался просто SHA. Термин «SHA-0» был введён позднее криптоаналитиками для обозначения именно первой, отозванной версии, чтобы отличать её от SHA-1.
• Дефект в SHA-0 был обнаружен случайно в ходе внутреннего аудита АНБ. Агентство не раскрыло публично точную природу уязвимости, но NIST оперативно отозвал стандарт.
• Отзыв SHA-0 стал одним из первых публичных случаев, когда криптографический стандарт был отозван из-за обнаруженной уязвимости до его широкого внедрения.
• В 2004 году, после взлома SHA-0, группа Ван показала, что коллизии для SHA-0 можно найти на обычном персональном компьютере за несколько часов.

Источники

1. Federal Register, Vol. 58, No. 106, June 4, 1993 (публикация SHA).
2. Chabaud, F., Joux, A. (1998). "Differential Collisions in SHA-0". Advances in Cryptology — CRYPTO'98.
3. Wang, X., et al. (2004). "Collisions for SHA-0 and SHA-1". Advances in Cryptology — CRYPTO'04.
4. National Institute of Standards and Technology (NIST). "Secure Hash Standard (SHS)" (FIPS PUB 180-1, 1995).
5. Schneier, B. (1996). "Applied Cryptography", 2nd ed.