Хеширование SHA-1

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

История

Разработка и стандартизация

SHA-1 был создан как преемник SHA-0, опубликованной в 1993 году. В 1995 году NIST выпустил обновлённую версию (FIPS PUB 180-1), которая отличалась от SHA-0 незначительным изменением в алгоритме сжатия — добавлением одного циклического сдвига. Это изменение было внесено для устранения неизвестной на тот момент уязвимости, которая, как позже выяснилось, действительно существовала в SHA-0. В 2002 году SHA-1 был утверждён в качестве федерального стандарта США (FIPS 180-2) и широко внедрён в протоколы безопасности, такие как SSL/TLS, SSH, PGP, а также в системы контроля версий (Git) и цифровые подписи.

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

Первые признаки нестойкости SHA-1 появились в 2004 году, когда группа китайских криптоаналитиков (Ван Сяоюнь, Ли Сюэцзя и др.) объявила о нахождении коллизий для SHA-0. В 2005 году они же продемонстрировали атаку на SHA-1, требующую 2⁶⁹ операций, что значительно меньше теоретической стойкости в 2⁸⁰. В 2011 году NIST официально рекомендовал перейти на SHA-2 (SHA-256, SHA-512) и SHA-3. В 2017 году консорциум Google и CWI Amsterdam опубликовал первую практическую коллизию для SHA-1 (атака SHAttered), показав, что два разных PDF-файла дают одинаковый хеш. В 2020 году атака была улучшена до стоимости около 45 000 долларов США (аренда облачных вычислений). С 2017 года основные браузеры (Chrome, Firefox, Edge) перестали доверять сертификатам, подписанным с использованием SHA-1. В 2022 году NIST полностью исключил SHA-1 из стандарта FIPS 180-4, оставив только SHA-2 и SHA-3.

Алгоритм работы

Общая схема

SHA-1 обрабатывает сообщение блоками по 512 бит (64 байта). Алгоритм состоит из следующих этапов:

1. Дополнение сообщения: к исходному сообщению добавляется бит '1', затем нулевые биты до тех пор, пока длина сообщения не станет на 64 бита меньше кратной 512. Последние 64 бита резервируются для хранения исходной длины сообщения в битах (в виде 64-битного целого числа big-endian). Таким образом, итоговая длина всегда кратна 512 битам.

1. Инициализация: задаётся начальное состояние из пяти 32-битных регистров (A, B, C, D, E) с константами:

• A = 0x67452301
• B = 0xEFCDAB89
• C = 0x98BADCFE
• D = 0x10325476
• E = 0xC3D2E1F0

1. Обработка блоков: каждый 512-битный блок проходит через 80 раундов сжатия. На каждом раунде используются:

• 4 нелинейные функции (f₀–f₃), меняющиеся каждые 20 раундов;
• 4 константы (K₀–K₃);
• 80 32-битных слов W[t], полученных из исходного блока путём расширения (циклические сдвиги и XOR).

1. Формирование дайджеста: после обработки всех блоков значения регистров A–E конкатенируются в 160-битное число (порядок big-endian), которое и является хешем.

Детали раундов

Для каждого раунда t (0..79) выполняются:

• T = (A <<< 5) + f_t(B, C, D) + E + W[t] + K_t
• E = D, D = C, C = B <<< 30, B = A, A = T

где <<< — циклический сдвиг влево, + — сложение по модулю 2³².

Нелинейные функции:

• f₀ (t=0..19): (B & C) | (~B & D) — выбор битов
• f₁ (t=20..39): B XOR C XOR D — чётность
• f₂ (t=40..59): (B & C) | (B & D) | (C & D) — мажоритарная
• f₃ (t=60..79): B XOR C XOR D — чётность

Константы:

• K₀ = 0x5A827999 (√2/4)
• K₁ = 0x6ED9EBA1 (√3/4)
• K₂ = 0x8F1BBCDC (√5/4)
• K₃ = 0xCA62C1D6 (√10/4)

Характеристики

Размеры и производительность

• Длина хеша: 160 бит (20 байт).
• Размер блока: 512 бит (64 байта).
• Максимальная длина входного сообщения: 2⁶⁴ − 1 бит (≈ 2 эксабайта).
• Скорость: на современных процессорах (x86-64 с поддержкой SSE/AVX) — около 200–500 МБ/с в программной реализации; аппаратные ускорители (Intel SHA Extensions) достигают 1–2 ГБ/с.

Стойкость

Теоретическая стойкость SHA-1:

• Коллизионная стойкость: 2⁸⁰ операций (из-за парадокса дней рождения). Практически с 2017 года — 2⁶³–2⁶⁹ операций.
• Стойкость к прообразу: 2¹⁶⁰ (для заданного хеша найти сообщение) — остаётся высокой, но не используется из-за слабой коллизионной стойкости.
• Стойкость ко второму прообразу: 2¹⁶⁰ (для заданного сообщения найти другое с тем же хешем).

Применение

Историческое использование

• Цифровые подписи: SHA-1 применялся в алгоритмах RSA и DSA для подписи сертификатов X.509. До 2017 года большинство SSL-сертификатов использовали SHA-1.
• Протоколы безопасности: TLS 1.0/1.1, SSH-1, IPsec, S/MIME, PGP.
• Системы контроля версий: Git использует SHA-1 для идентификации коммитов и объектов (с 2005 года). В 2023 году Git перешёл на SHA-256 как опциональный алгоритм.
• Проверка целостности файлов: утилиты sha1sum (Linux), Get-FileHash (PowerShell), CertUtil -hashfile (Windows).
• Хранение паролей: изредка, но не рекомендуется из-за высокой скорости вычисления.

Современный статус

По состоянию на 2024 год SHA-1 не рекомендуется для использования в новых системах. NIST и другие организации (IETF, CA/Browser Forum) запретили его для цифровых подписей и сертификатов. Однако он всё ещё встречается в:

• Устаревших системах: встроенное ПО, старые протоколы, где обновление невозможно.
• Git: для обратной совместимости с существующими репозиториями (новые коммиты могут использовать SHA-256).
• Контрольные суммы: в некоторых дистрибутивах Linux (например, Debian) для проверки целостности пакетов (хотя рекомендуется SHA-256).

Критика и атаки

Основные атаки

• 2005 — атака Ван Сяоюнь: коллизия за 2⁶⁹ операций, позже улучшена до 2⁶³.
• 2017 — SHAttered (Google/CWI): первая публичная коллизия — два разных PDF-файла с одинаковым хешем. Стоимость: 110 GPU-лет (≈ 110 000 долларов).
• 2020 — атака Leurent-Peyrin (выбор свободного старта): коллизия за 2⁵⁷.5 операций, стоимость около 45 000 долларов.
• 2020 — атака на прообраз (Leurent-Peyrin): для 52 из 80 раундов — 2¹⁵⁹.3, для полного SHA-1 — 2¹⁵⁹.9 (не практично, но теоретически значимо).

Проблемы безопасности

• Коллизии позволяют подделать цифровые подписи: злоумышленник может создать два документа с одинаковым хешем, один из которых подписывается, а другой используется для мошенничества.
• Высокая скорость вычисления SHA-1 (до 10 ГХ/с на GPU) делает его непригодным для хранения паролей — атаки перебором (brute force) эффективны.
• Отсутствие криптографической соли и медленных итераций (в отличие от bcrypt, scrypt, Argon2).

Альтернативы

SHA-2 (SHA-256, SHA-512)

• Разработан NIST в 2001 году.
• Длина хеша: 256 или 512 бит.
• Стойкость: коллизионная — 2¹²⁸ (SHA-256) и 2²⁵⁶ (SHA-512).
• Рекомендован для всех новых применений.

SHA-3 (Keccak)

• Победитель конкурса NIST (2012), стандарт FIPS 202.
• Длина хеша: 224, 256, 384, 512 бит.
• Отличается от SHA-2 архитектурой (губка, а не Меркла-Дамгорда), что даёт устойчивость к некоторым атакам.

BLAKE2, BLAKE3

• Высокоскоростные хеш-функции, не являющиеся стандартами NIST.
• BLAKE3: скорость до 1 ГБ/с на одном ядре, поддержка параллелизма.

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

• SHA-1 использовался в системе электронных паспортов РФ (до 2019 года), но после выявления коллизий был заменён на SHA-256.
• В 2019 году исследователи из Университета Лёвена (Бельгия) показали, что можно создать коллизию SHA-1 для двух разных PDF-файлов всего за 10 минут на обычном ноутбуке, используя предвычисленные данные (атака SHAttered + улучшения).
• В Git до 2023 года SHA-1 был единственным алгоритмом, и коллизия могла бы привести к слиянию разных коммитов в один, что теоретически позволяло подменить код. Однако на практике Git использует не только хеш, но и метаданные (дата, автор), что усложняет атаку.

Источники

• FIPS PUB 180-1: Secure Hash Standard (1995)
• FIPS PUB 180-4: Secure Hash Standard (2015, отозван в 2022)
• Wang, X., et al. "Finding Collisions in the Full SHA-1" (2005)
• Stevens, M., et al. "The First Collision for Full SHA-1" (2017)
• Leurent, G., Peyrin, T. "From Collisions to Chosen-Prefix Collisions: Application to Full SHA-1" (2020)
• NIST SP 800-107: Recommendation for Applications Using Approved Hash Algorithms (2012)
• CA/Browser Forum Baseline Requirements (2023)