Криптографические хеш-функции

Хеш-функция сжимает данные произвольной длины в значение фиксированной длины — 256 или 512 бит — и делает это так, чтобы по значению нельзя было восстановить вход. Это самый используемый примитив в криптографии: он нужен для проверки целостности файлов, для электронной подписи (подписывается хеш, а не сообщение), для кодов аутентификации, для деревьев Меркла в Git и Certificate Transparency, для хранения паролей и для доказательств работы в блокчейне.

Требования к хеш-функции формулируются иначе, чем к шифру. Шифр должен скрывать содержимое; хеш ничего не скрывает, потому что он необратим, — но он должен быть стойким к трём видам атак: к нахождению прообраза, к нахождению второго прообраза и к нахождению коллизий. Эти три требования дают разные оценки сложности (2^n, 2^n и 2^(n/2)), и путать их — типичная ошибка. Именно из-за коллизий, а не из-за обращения, пали MD5 и SHA-1: их прообраз остаётся трудным, а коллизии нашлись.

Тема разбирает устройство хеш-функций от конструкции Меркла — Дамгора до губки Keccak, историю взломов MD5 и SHA-1, современные функции (SHA-2, SHA-3, BLAKE2, Стрибог) и применения, где хеш необходим, но недостаточен. Последний раздел — о том, чего хеш не даёт: он не обеспечивает аутентичность (для этого нужен MAC), он не годится для хранения паролей (для этого нужны медленные функции, тема 10) и он не защищает от подмены, если используется как «хеш вместо MAC».

Паспорт темы. Нужно знать: темы 0, 2. Освоите: формулировать три свойства хеш-функции и оценки 2^n и 2^(n/2); объяснять конструкцию Меркла — Дамгора и атаку удлинения; различать SHA-2, SHA-3 и XOF; строить дерево Меркла; указывать, чего хеш не даёт. Проверяет: ЛР 8. Минимум: разделы 1–4. Углубление: разделы 5–6.

Определение и свойства

Три требования стойкости

Криптографическая хеш-функция H отображает строки произвольной длины в строки фиксированной длины n и должна удовлетворять трём свойствам.

Стойкость к нахождению прообраза (англ. preimage resistance): по заданному значению h вычислительно невозможно найти такой m, что H(m) = h. Лучший известный метод — перебор, сложность 2^n. Это свойство нужно, когда хеш используется как обязательство: показав h, сторона позже раскрывает m, и никто не может подобрать другое m' с тем же хешем.

Стойкость к нахождению второго прообраза (англ. second preimage resistance): по заданному m невозможно найти m' ≠ m с H(m') = H(m). Сложность тоже 2^n для идеальной функции. Это свойство нужно для целостности: если злоумышленник может подменить файл, сохранив хеш, проверка контрольных сумм бесполезна.

Стойкость к коллизиям (англ. collision resistance): невозможно найти пару m ≠ m' с H(m) = H(m'). Здесь сложность падает до 2^(n/2) из-за парадокса дней рождения. Это свойство нужно для подписи: если можно найти две разные документы с одинаковым хешем, подпись под одним переносится на другой.

Соотношения между свойствами несимметричны. Стойкость к коллизиям влечёт стойкость ко второму прообразу (если можно найти второй прообраз, то и коллизию — с этим m), но не наоборот. Стойкость к прообразу не следует из стойкости к коллизиям. Поэтому для подписи требуется именно стойкость к коллизиям, и именно она определяет требования к длине: 128-битный хеш даёт только 64 бита стойкости к коллизиям, что недостаточно.

Парадокс дней рождения

Парадокс дней рождения — не парадокс, а свойство вероятностей. Если в комнате 23 человека, вероятность совпадения дней рождения больше 50 %. Причина в том, что сравниваются не дни рождения с фиксированной датой, а все пары: при 23 людях пар 253.

Формально вероятность отсутствия коллизии при k случайных значениях из множества размера N равна

P(\text{нет коллизии}) \approx \exp\left(-\frac{k(k-1)}{2N}\right)

При k \approx 1{,}18 \sqrt{N} вероятность коллизии достигает 50 %, а ожидаемое число значений до первой коллизии — около 1{,}25 \sqrt{N}. Для N = 2^n это 2^{n/2}.

Практическое следствие для хеш-функций: 128-битный хеш (MD5) даёт коллизию за 2^64 операций, что для хорошо финансируемого противника достижимо; 160-битный (SHA-1) — за 2^80, что тоже стало достижимым; 256-битный — за 2^128, что нет.

Схема ниже показывает, как растёт вероятность коллизии с числом значений и почему порог наступает задолго до исчерпания пространства.

Числовой пример: для усечённого до 24 бит SHA-256 среднее число попыток до коллизии, измеренное на 200 испытаниях, составило около 5 тысяч, что близко к теоретическому 1,25·2^12 ≈ 5100. Для 32 бит измеренное среднее на 12 испытаниях — около 66 тысяч при теоретическом 1,25·2^16 ≈ 82 000; разброс велик, потому что распределение времени до коллизии имеет тяжёлый хвост.

Стоимость атак и уровни стойкости

Из требований следуют уровни стойкости, которые нужно сопоставлять с длиной выхода.

Отсюда практическое правило: для электронной подписи нужен хеш с выходом не меньше 256 бит, потому что 128 бит стойкости к коллизиям — минимальный приемлемый уровень. SHA-256 в этом смысле стоит на нижней границе: его 128-битная стойкость к коллизиям соответствует уровню AES-128.

Отдельно стоит отметить атаку на длинные сообщения: для конструкций Меркла — Дамгора существует атака второго прообраза сложности 2^(n/2) вместо 2^n, если сообщение очень длинное ¹³. Это не ломает SHA-256 практически, но показывает, что «идеальные» оценки выполняются не для всех конструкций.

Конструкция Меркла — Дамгора

Функция сжатия и дополнение

Хешировать сообщение произвольной длины одной функцией неудобно, поэтому конструкция разбивает задачу на две: функция сжатия (англ. compression function) обрабатывает блок фиксированной длины и текущее состояние, а режим обхода (англ. mode of operation) связывает блоки.

В конструкции Меркла — Дамгора ⁴³ состояние h обновляется блок за блоком:

h₀ = IV
hᵢ = f(hᵢ₋₁, Mᵢ)
H(M) = h_k

Функция f называется функцией сжатия; она принимает состояние и блок, а возвращает новое состояние. IV — фиксированные константы, определённые стандартом.

Чтобы конструкция была корректной, сообщение нужно дополнить до кратности длине блока и включить в дополнение длину исходного сообщения. Иначе два сообщения разной длины с одинаковым «хвостом» могли бы дать одинаковый хеш. Стандартное дополнение: бит 1, затем нули, затем 64 или 128 бит длины.

Схема ниже показывает цепочку сжатия и место дополнения.

Главное достоинство конструкции — возможность доказать стойкость: если функция сжатия стойка к коллизиям, то и вся хеш-функция стойка к коллизиям. Это теорема Меркла — Дамгора, и именно она объясняет, почему такие функции так популярны: безопасность сводится к свойствам небольшого компонента.

Главный недостаток — атака удлинения сообщения, о которой ниже.

Атака удлинения сообщения

Атака удлинения (англ. length extension attack) следует прямо из устройства: состояние после обработки M и есть H(M). Значит, зная H(M) и длину M, но не зная M, противник может продолжить вычисление с этого состояния, добавив дополнение и новый блок. Формально он может вычислить H(M || pad || X) для произвольного X, не зная M.

def length_extension(digest, original_len, suffix):
    state = state_from_digest(digest)          # восемь 32-битных слов из хеша
    glue = padding(original_len)               # дополнение, которое уже «съел» оригинал
    forged_len = original_len + len(glue)
    return sha256(suffix, state=state, prefix_len=forged_len), glue + suffix

Для криптографической хеш-функции это не уязвимость: свойство «хеш от M совпадает с состоянием» не считается недостатком. Уязвимость возникает, когда хеш используют как код аутентификации: tag = SHA256(key || message). Противник получает tag, применяет удлинение и получает валидный тег для message || pad || suffix, не зная ключа. Именно так ломаются самодельные MAC на основе SHA-256 и SHA-1, и именно поэтому существует HMAC — конструкция, специально устойчивая к удлинению (тема 9).

Защита бывает трёх видов: использовать HMAC, использовать хеш с губкой (SHA-3, BLAKE2), где удлинение невозможно по построению, или ставить ключ в конец сообщения (менее удачно, потому что требует другого анализа и плохо сочетается с потоковой обработкой).

Почему губка устроена иначе

Губка (англ. sponge construction) применяет к состоянию две функции: перестановку f и выборку. Состояние делится на две части — скорость (rate) r и ёмкость (capacity) c, — и данные поглощаются по r бит за раз.

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

Схема ниже показывает обе фазы.

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

Параметры: для SHA3-256 состояние 1600 бит, скорость 1088, ёмкость 512. Стойкость к коллизиям ограничена 2^(c/2) = 2^256, что соответствует 256-битному выходу; стойкость к прообразу — 2^c = 2^512 для полного состояния, но не меньше 2^n по выходу.

История взломов: MD5 и SHA-1

MD5

MD5 (1992) — 128-битная хеш-функция Рона Ривеста, наследник MD4. Долгое время считалась надёжной, и в 1990-х её использовали для подписи, контрольных сумм и хранения паролей.

В 2004 году Ван Сяоюнь, Фэн Дэнгуо и Лай Хуэйвэй объявили о нахождении коллизий MD5, а в 2005 году вышла работа «How to Break MD5 and Other Hash Functions» с полным описанием метода ⁷. Атака использовала дифференциальные характеристики и находила коллизии за часы на обычном компьютере, а позже — за секунды.

Практические последствия не заставили себя ждать. В 2008 году был создан поддельный центр сертификации с помощью коллизии MD5. В 2012 году вредонос Flame использовал выбранно-префиксную коллизию MD5, чтобы подделать подпись обновления Microsoft — это была атака на целую цепочку доверия, а не на отдельный файл.

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

SHA-1

SHA-1 (1995) — 160-битная функция, наследник SHA-0. Её 80-битная стойкость к коллизиям долго считалась достаточной.

В 2005 году Ван, Инь и Юй описали теоретическую атаку сложности 2^69 вместо 2^80 ⁵. Это ещё не была практическая коллизия, но запас сократился и стало ясно, что нужно переходить на SHA-2.

В 2017 году группа SHAttered нашла первую реальную коллизию SHA-1: два разных PDF-файла с одинаковым SHA-1 ⁶. Стоимость — около 2^63,1 вычислений SHA-1, что эквивалентно 6500 годам работы одного процессора и 110 годам работы видеокарты. Это была демонстрация, а не повседневная атака, но она показала, что 80-битная стойкость исчерпана.

В 2019–2020 годах Леран и Пейрен построили выбранно-префиксную коллизию SHA-1 (проект «SHA-1 is a Shambles») ⁸, которая позволяет подделать документ с заданным префиксом — например, сертификат или ключ PGP. Сложность около 2^63,4, стоимость — десятки тысяч долларов на арендованных GPU.

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

Что из этого следует

Общий вывод из истории MD5 и SHA-1: запас стойкости должен быть больше, чем кажется достаточным на момент проектирования. 128 бит считались избыточными в 1992 году, 160 — в 1995-м. Оба алгоритма пали не из-за обращения, а из-за коллизий, и оба — из-за конструкции, а не из-за длины выхода как таковой: SHA-1 с 160 битами имел 80-битную стойкость к коллизиям, и именно она оказалась недостаточной.

Второй вывод: практические атаки приходят позже теоретических. Теоретическая атака SHA-1 была опубликована в 2005 году, практическая коллизия — в 2017-м. Двенадцать лет — типичный разрыв между «сломано в теории» и «сломано в жизни», и всё это время алгоритм оставался в протоколах.

Третий вывод: выбранно-префиксные коллизии опаснее обычных. Обычная коллизия даёт два «мусорных» файла с одинаковым хешем; выбранно-префиксная позволяет взять осмысленный документ и подобрать к нему другой осмысленный с тем же хешем. Именно она делает атаку применимой к сертификатам и подписям.

Современные функции

SHA-2 и SHA-256 по шагам

SHA-2 — семейство, опубликованное в 2001 году и стандартизованное в FIPS 180-4 ¹. В него входят SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224 и SHA-512/256. Все построены по конструкции Меркла — Дамгора с функцией сжатия на основе схемы, похожей на ARX.

SHA-256: блок 512 бит, состояние 8 слов по 32 бита, 64 раунда, длина выхода 256 бит. В каждом раунде используются:

• сумма по модулю 2^32 с вращениями (Σ₀, Σ₁);
• функция выбора Ch(x, y, z) = (x & y) ^ (~x & z);
• функция большинства Maj(x, y, z) = (x & y) ^ (x & z) ^ (y & z);
• константы Kᵢ — первые 32 бита дробных частей кубических корней первых 64 простых чисел.

Начальные значения H₀…H₇ — первые 32 бита дробных частей квадратных корней первых восьми простых чисел. Происхождение констант проверяемо (их можно пересчитать), что и является аргументом «nothing up my sleeve».

def compress(state, block):
    w = list(struct.unpack(">16I", block)) + [0] * 48
    for i in range(16, 64):
        s0 = rotr(w[i - 15], 7) ^ rotr(w[i - 15], 18) ^ (w[i - 15] >> 3)
        s1 = rotr(w[i - 2], 17) ^ rotr(w[i - 2], 19) ^ (w[i - 2] >> 10)
        w[i] = (w[i - 16] + s0 + w[i - 7] + s1) & 0xFFFFFFFF
    a, b, c, d, e, f, g, h = state
    for i in range(64):
        S1 = rotr(e, 6) ^ rotr(e, 11) ^ rotr(e, 25)
        ch = (e & f) ^ (~e & g)
        t1 = (h + S1 + ch + K[i] + w[i]) & 0xFFFFFFFF
        S0 = rotr(a, 2) ^ rotr(a, 13) ^ rotr(a, 22)
        maj = (a & b) ^ (a & c) ^ (b & c)
        t2 = (S0 + maj) & 0xFFFFFFFF
        h, g, f, e, d, c, b, a = g, f, e, (d + t1) & 0xFFFFFFFF, c, b, a, (t1 + t2) & 0xFFFFFFFF
    return tuple((x + y) & 0xFFFFFFFF for x, y in zip(state, (a, b, c, d, e, f, g, h)))

Проверка: SHA256("abc") = ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad, SHA256("") = e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855. Первый вектор — из стандарта, второй полезен тем, что проверяет обработку пустого сообщения: дополнение всё равно добавляет блок.

printf 'abc' | sha256sum
printf 'abc' | openssl dgst -sha256

Обе команды дают одно и то же значение. Разница в выводе: sha256sum печатает хеш, пробел и имя файла, openssl dgst — имя алгоритма и хеш.

SHA-3 и губка Keccak

SHA-3 появился не потому, что SHA-2 сломали, а потому что нужен был запасной вариант с другой конструкцией. Конкурс NIST (2007–2012) выиграл Keccak, стандартизованный в FIPS 202 ²⁹.

Keccak использует состояние 1600 бит (5×5 слов по 64 бита) и перестановку из 24 раундов, каждый из которых состоит из пяти шагов: θ, ρ, π, χ, ι. Нелинейность даёт χ — единственный нелинейный шаг; остальные обеспечивают диффузию.

Параметры вариантов: для SHA3-256 скорость 1088 бит, ёмкость 512; для SHA3-512 скорость 576, ёмкость 1024. Чем больше ёмкость, тем выше стойкость и тем меньше скорость — данных за одну перестановку обрабатывается меньше.

Отдельное достоинство семейства — XOF (англ. extendable output function): SHAKE128 и SHAKE256 могут выдать выход любой длины из одного входа. Это удобно для выработки ключей и для схем, где нужно много псевдослучайных байт.

Практически SHA-3 медленнее SHA-2 на большинстве процессоров (нет аппаратных инструкций, кроме специализированных), но даёт независимую конструкцию: если завтра найдут атаку на Меркла — Дамгора, SHA-3 останется.

BLAKE2, BLAKE3 и Стрибог

BLAKE2 (2013) — оптимизированная замена MD5 и SHA-1: быстрее SHA-2 на программных платформах, с поддержкой ключа и персонализации ¹⁰. BLAKE2b даёт 512 бит, BLAKE2s — 256. BLAKE3 (2020) — дальнейшее развитие с древовидным режимом и параллелизмом; она используется там, где скорость важнее консерватизма стандарта.

Стрибог — российский стандарт ГОСТ Р 34.11-2012, с выходами 256 и 512 бит ¹¹. Построен по той же идее «сжатие плюс итерация», но с нелинейным преобразованием LPS (подстановки, перестановка, линейное преобразование) и 12 раундами. Стандарт определяет и функцию сжатия, и процедуру дополнения.

Применения

Целостность файлов и дедупликация

Простейшее применение — контрольная сумма: sha256sum file даёт значение, которое можно сверить после передачи. Это защищает от случайных повреждений и от подмены только в том случае, если значение получено по независимому каналу. Если противник может подменить и файл, и контрольную сумму, проверка бесполезна — именно поэтому дистрибутивы публикуют хеши и подписи отдельно, а пакетные менеджеры проверяют подпись репозитория, а не только хеш пакета.

Дедупликация в системах резервного копирования и в контентных хранилищах (Git, Docker) использует хеш как адрес объекта: одинаковое содержимое даёт одинаковый адрес, и объект хранится один раз. Это работает, пока хеш стойкий к коллизиям: при коллизии два разных объекта получили бы один адрес, и содержимое подменилось бы. Практически Git использует SHA-1 и уже переходит на SHA-256 именно из-за этого риска.

Дерево Меркла

Дерево Меркла (англ. Merkle tree) решает задачу доказательства включения: как убедить проверяющего, что элемент входит в набор, не передавая весь набор.

Листья — хеши элементов, узлы — хеши конкатенации двух дочерних хешей, корень — хеш всего набора. Чтобы доказать включение элемента, достаточно передать путь от листа до корня — log₂ N хешей вместо N элементов.

Схема ниже показывает дерево и путь доказательства.

Применения: Git (каждый коммит — дерево объектов), Certificate Transparency (лог сертификатов с деревом Меркла и доказательствами включения, RFC 6962 ¹²), блокчейн (корень дерева транзакций в заголовке блока), системы обновлений (проверка, что файл входит в подписанный набор).

def merkle_root(leaves):
    level = [leaf_hash(x) for x in leaves]
    while len(level) > 1:
        if len(level) % 2:
            level.append(level[-1])       # нечётный узел дублируется
        level = [node_hash(level[i], level[i + 1]) for i in range(0, len(level), 2)]
    return level[0]

Тонкость с дублированием нечётного узла: если дублировать последний элемент, возникает уязвимость «второго прообраза» для дерева — два разных набора могут дать один корень. Поэтому в серьёзных реализациях (Certificate Transparency) дублирование заменяют подъёмом узла на уровень выше либо добавляют в хеш длину и позицию. Это хороший пример того, что дерево Меркла — не «просто хеши», а конструкция с собственными тонкостями.

Обязательства и доказательства работы

Обязательство (англ. commitment) — схема, позволяющая «запечатать» значение: commit = H(value || nonce). Позже сторона раскрывает value и nonce, и все могут проверить, что обязательство было дано именно для этого значения. Свойства — сокрытие (по commit нельзя узнать value) и связывание (нельзя найти другое value с тем же commit).

Доказательство работы (англ. proof of work) — поиск такого nonce, чтобы H(block || nonce) начиналось с заданного числа нулевых бит. Это задача поиска частичного прообраза: сложность 2^k для k ведущих нулей, проверка — один хеш. Используется в блокчейне для согласования и в антиспам-системах как «вычислительный налог».

def solve(data, k):
    nonce = 0
    while True:
        digest = hashlib.sha256(data + nonce.to_bytes(8, "big")).digest()
        if int.from_bytes(digest, "big") >> (256 - k) == 0:
            return nonce, digest
        nonce += 1

Ожидаемое число попыток — 2^k. Для k = 20 это около миллиона хешей, для k = 32 — около четырёх миллиардов.

Чего хеш не даёт

Аутентичность и MAC

Хеш не обеспечивает аутентичность. Если злоумышленник может изменить и сообщение, и хеш, проверка пройдёт. Более того, даже если хеш передан по защищённому каналу, конструкция SHA256(key || message) уязвима к удлинению, как показано выше.

Для аутентичности нужен код аутентификации сообщения (MAC), который использует ключ и не позволяет вычислить тег без него. Стандартный выбор — HMAC: HMAC(K, m) = H((K ⊕ opad) || H((K ⊕ ipad) || m)), конструкция, устойчивая к удлинению по построению (тема 9).

Хранение паролей

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

Правильное решение — медленные функции с солью: PBKDF2 с большим числом итераций, scrypt, Argon2id (тема 10). Они специально спроектированы так, чтобы каждая попытка перебора стоила дорого.

Другие типичные ошибки

Ещё несколько ошибок встречаются регулярно. Использование усечённого хеша (например, первых 8 байт) без понимания, что стойкость к коллизиям падает до 2^32. Сравнение хешей не в постоянном времени — утечка через время сравнения. Хеширование вместе с данными, которые противник контролирует (что позволяет подобрать коллизию). Использование MD5 или SHA-1 «для совместимости» в системе, где безопасность важна.

Итоги темы

Хеш-функция сжимает данные произвольной длины в значение фиксированной длины и должна быть стойкой к трём видам атак: к прообразу, ко второму прообразу и к коллизиям. Оценки сложности различаются — 2^n для первых двух и 2^(n/2) для коллизий, — и именно коллизии определяют требования к длине выхода: для подписи нужен хеш не короче 256 бит.

Конструкция Меркла — Дамгора сводит стойкость всей функции к стойкости функции сжатия, но порождает атаку удлинения сообщения, из-за которой SHA256(key || message) не является MAC. Губка Keccak решает проблему иначе: состояние никогда не выдаётся целиком, ёмкость скрыта, и удлинение невозможно по построению.

История MD5 и SHA-1 показывает, как быстро исчерпывается запас: MD5 пал в 2004–2005 годах, SHA-1 — в 2017-м, причём оба — из-за коллизий, а не из-за обращения. Практические атаки приходят через годы после теоретических, и всё это время алгоритмы остаются в протоколах.

Современный выбор: SHA-256 или SHA-512 для совместимости, SHA-3 как независимая конструкция, BLAKE2/BLAKE3 для скорости, Стрибог для соответствия ГОСТ. Деревья Меркла дают эффективные доказательства включения и лежат в основе Git, Certificate Transparency и блокчейна.

Но хеш не решает задачу аутентичности, и это ключевой вывод. Следующая тема переходит к кодам аутентификации сообщений и аутентифицированному шифрованию — механизмам, которые отвечают именно на вопрос «данные подлинные?», и разбирает, почему HMAC устроен так, чтобы не повторить ошибку с удлинением.

Литература

1. NIST. Secure Hash Standard (SHS). — FIPS 180-4, 2015. https://doi.org/10.6028/NIST.FIPS.180-4
2. NIST. SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions. — FIPS 202, 2015. https://doi.org/10.6028/NIST.FIPS.202
3. Merkle R. C. A Certified Digital Signature. — Advances in Cryptology — CRYPTO '89, Springer, 1990, С. 218–238. DOI: 10.1007/0-387-34805-0_21
4. Damgård I. B. A Design Principle for Hash Functions. — Advances in Cryptology — CRYPTO '89, Springer, 1990, С. 416–427. DOI: 10.1007/0-387-34805-0_17
5. Wang X., Yin Y. L., Yu H. Finding Collisions in the Full SHA-1. — Advances in Cryptology — CRYPTO 2005, Springer, 2005, С. 17–36. DOI: 10.1007/11535218_2
6. Stevens M., Bursztein E., Karpman P., Albertini A., Markov Y. The First Collision for Full SHA-1. — Advances in Cryptology — CRYPTO 2017, Springer, 2017, С. 570–596. DOI: 10.1007/978-3-319-63688-7_19
7. Wang X., Yu H. How to Break MD5 and Other Hash Functions. — Advances in Cryptology — EUROCRYPT 2005, Springer, 2005, С. 19–35. DOI: 10.1007/11426639_2
8. Leurent G., Peyrin T. From Collisions to Chosen-Prefix Collisions: Application to Full SHA-1. — Advances in Cryptology — EUROCRYPT 2019, Springer, 2019, С. 527–555. DOI: 10.1007/978-3-030-17659-4_18
9. Bertoni G., Daemen J., Peeters M., Van Assche G. Cryptographic Sponge Functions. — Keccak reference, 2011. https://keccak.team/files/SpongeFunctions.pdf
10. Aumasson J.-P., Neves S., Wilcox-O'Hearn Z., Winnerlein C. BLAKE2: Simpler, Smaller, Fast as MD5. — Applied Cryptography and Network Security (ACNS 2013), Springer, 2013, С. 119–135. DOI: 10.1007/978-3-642-38980-1_8
11. ГОСТ Р 34.11-2012. Информационная технология. Криптографическая защита информации. Функция хеширования. — Стандартинформ, 2013.
12. Laurie B., Langley A., Kasper E. Certificate Transparency. — RFC 6962, IETF, 2013. https://www.rfc-editor.org/rfc/rfc6962
13. Kelsey J., Schneier B. Second Preimages on n-Bit Hash Functions for Much Less than 2ⁿ Work. — Advances in Cryptology — EUROCRYPT 2005, Springer, 2005, С. 474–490. DOI: 10.1007/11426639_28

Дополнительные материалы

Вопросы для самопроверки

1. Чем криптографическая хеш-функция отличается от контрольной суммы вроде CRC32 по требованиям к стойкости?
2. Почему из стойкости к коллизиям следует стойкость ко второму прообразу, но не наоборот?
3. Почему для подписи важнее стойкость к коллизиям, чем к прообразу?
4. Как выводится оценка 1,25·√N для ожидаемого числа значений до коллизии?
5. Какая длина выхода нужна, чтобы получить 128 бит стойкости к коллизиям?
6. Почему дополнение включает длину сообщения и что сломается без неё?
7. Что такое функция сжатия и почему стойкость всей функции сводится к её стойкости?
8. Почему SHA256(key || msg) уязвим к удлинению, а SHA256(msg || key) — нет, но тоже плох?
9. Почему губка не позволяет вычислить продолжение хеша, зная выход?
10. Что такое XOF и зачем нужны SHAKE128 и SHAKE256?
11. Чем выбранно-префиксная коллизия отличается от обычной и почему она важнее для практики?
12. Почему SHA-256 медленнее SHA-512 на 64-битных процессорах при вдвое меньшем выходе?
13. Почему в дереве Меркла доказательство включения имеет длину log₂N?
14. Почему дублирование нечётного узла создаёт уязвимость и как от неё защищаются?
15. Почему хеш нельзя использовать для хранения паролей и что используют вместо него?

Глоссарий темы

Шпаргалка по инструментам

# контрольные суммы и сверка
sha256sum file.bin
printf 'abc' | sha256sum
printf 'abc' | openssl dgst -sha256
openssl dgst -sha512 file.bin

# список поддерживаемых алгоритмов хеширования
openssl list -digest-algorithms

import hashlib

hashlib.sha256(b"abc").hexdigest()
hashlib.sha3_256(b"abc").hexdigest()
hashlib.shake_256(b"abc").hexdigest(64)      # XOF: 64 байта
hashlib.blake2b(b"abc").hexdigest()
hashlib.file_digest(open("file.bin", "rb"), "sha256").hexdigest()   # Python 3.11+

усечение           int.from_bytes(d, "big") >> (256 - bits)
ведущие нули       bits = 256 - int.from_bytes(d, "big").bit_length()
длина дополнения   pad = 1 + ((55 - len(msg)) % 64) + 8

Типичные ошибки:

Что почитать и посмотреть

• FIPS 180-4. Стандарт SHA-2: константы, раунды, процедура дополнения. При реализации сверяйтесь только с ним, а не с описаниями в блогах: константы легко перепутать. https://doi.org/10.6028/NIST.FIPS.180-4
• FIPS 202. Стандарт SHA-3 и SHAKE: шаги перестановки Keccak, параметры скорости и ёмкости. Читается тяжелее SHA-2, но описывает принципиально другую конструкцию. https://doi.org/10.6028/NIST.FIPS.202
• Wang X., Yu H. How to Break MD5 and Other Hash Functions (2005). Первоисточник взлома MD5. Технически сложно, но стоит посмотреть на структуру атаки: дифференциальные характеристики и «тоннели» — красивая инженерия.
• Stevens M. et al. The First Collision for Full SHA-1 (2017). Описание SHAttered: как считали коллизию, сколько это стоило и что это значит для практики. https://shattered.io/
• Leurent G., Peyrin T. SHA-1 is a Shambles (2019). Выбранно-префиксные коллизии SHA-1 и подделка PGP-ключей. Показывает, что «дорого» и «невозможно» — разные вещи. https://sha-mbles.github.io/
• Bertoni G., Daemen J., Peeters M., Van Assche G. Cryptographic Sponge Functions (2011). Теория губки от авторов Keccak: почему конструкция даёт стойкость и как считаются границы. https://keccak.team/files/SpongeFunctions.pdf
• Kelsey J., Schneier B. Second Preimages on n-Bit Hash Functions (2005). Атака второго прообраза сложности 2^(n/2) для длинных сообщений в конструкциях Меркла — Дамгора. Важный контрпример к «идеальным» оценкам.
• RFC 6962. Certificate Transparency. Как дерево Меркла применяется в реальной инфраструктуре: формат лога, доказательства включения и согласованности. https://www.rfc-editor.org/rfc/rfc6962
• Cryptopals, Set 4 (задачи 28–32) и Set 7 (задачи 49–51). Реализация HMAC, атака удлинения и подделка на основе MAC. Прямое продолжение частей 4–5.

Углубление (по желанию)

Почему MD5 жил ещё десять лет после взлома. Коллизии MD5 нашли в 2004 году, а в 2008-м уже существовал поддельный центр сертификации, построенный на них. Тем не менее MD5 оставался в списках алгоритмов подписи ещё несколько лет: системы обновлялись медленно, а совместимость требовала поддержки старых сертификатов. Здесь работает общий закон: криптографический алгоритм выводится из эксплуатации не тогда, когда его сломали, а когда стоимость поддержки превышает стоимость перехода. Для инженера это означает необходимость собственного реестра криптографических зависимостей: какой алгоритм, в каком компоненте, до какого срока.

Скорость против консерватизма. BLAKE3 быстрее SHA-256 в разы и поддерживает параллелизм, но стандартом де-факто остаётся SHA-256. Причина не в стойкости: обе функции считаются стойкими. Причина в том, что SHA-256 реализован в железе, проверен двадцатью годами атак и поддерживается везде. Новая быстрая функция выигрывает в задачах, где скорость критична (контрольные суммы, дедупликация, сборка), и проигрывает в задачах, где важна институциональная уверенность (сертификаты, подписи). Понимание этой разницы между «технически лучше» и «принято в инфраструктуре» — часть профессиональной зрелости.

Деревья Меркла: одна идея, много реализаций. Дерево Меркла выглядит тривиально, но его реализации различаются в деталях, и эти детали имеют последствия. Bitcoin дублирует последний узел при нечётном числе — и это работает, потому что формат фиксирован; Certificate Transparency делит набор по степени двойки и добавляет в хеш длину, чтобы избежать атаки на второй прообраз; Git хеширует объекты с заголовком, содержащим тип и длину, что защищает от смешения объектов разных типов. Общий вывод: любая конструкция на хешах должна специфицировать, что именно хешируется, — иначе противник найдёт способ подставить данные другого типа с тем же хешем.

Лабораторная работа 8. Хеш-функции на практике и их атаки

• Раздел курса: тема 8 «Криптографические хеш-функции»

Введение

Тема 8 разобрала три требования к хеш-функции, конструкцию Меркла — Дамгора и причину, по которой SHA256(key || message) не является кодом аутентификации. Лабораторная работа проверяет это на опыте: сначала SHA-256 пишется своими руками и сверяется с hashlib и sha256sum, затем измеряется парадокс дней рождения на усечённом хеше, затем демонстрируется атака удлинения сообщения на наивный MAC, и завершает работу дерево Меркла с доказательством включения.

Работа опирается на темы 2 (модели атак) и 6 (реализация примитива своими руками). Она готовит тему 9: после удлинения сообщения становится очевидно, зачем нужен HMAC, а не «хеш с ключом», и почему AEAD строится на проверенных конструкциях.

Все атаки выполняются против учебных объектов: усечённого хеша в собственной программе и локального сервиса на 127.0.0.1, который создаётся в этой же работе. Собственная реализация SHA-256 учебная и не годится для реального применения — она не защищена от атак по времени и работает в сотни раз медленнее библиотечной.

Цель работы

Реализовать SHA-256, измерить стойкость усечённой хеш-функции к коллизиям, провести атаку удлинения сообщения на наивный MAC и построить дерево Меркла с доказательством включения.

После выполнения работы можно будет:

• реализовать SHA-256 по FIPS 180-4 и сверить результат с hashlib и sha256sum;
• измерить лавинный эффект хеш-функции при изменении одного бита входа;
• найти коллизию для усечённого до 24–40 бит SHA-256 двумя методами и сравнить число попыток с 2^(n/2);
• найти частичный прообраз с заданным числом ведущих нулей и оценить сложность;
• провести атаку удлинения сообщения на SHA256(key || message), не зная ключа;
• построить дерево Меркла и доказать включение элемента, проверив путь независимо.

Уровни работы

• Минимум (обязательно): части 1–4. Выполняется без внешней сети, только с пакетами из перечня оснащения.
• Практический уровень: 5.
• Углубление (по желанию): нет.

Теоретический минимум

Нужны разделы «Определение и свойства», «Конструкция Меркла — Дамгора» (особенно «Атака удлинения сообщения») и «Современные функции». Ниже — справка.

SHA-256     блок 512 бит, состояние 8×32 бита, 64 раунда, выход 256 бит
дополнение  бит 1, нули, затем 64 бита длины сообщения
сжатие      hᵢ = f(hᵢ₋₁, Mᵢ); итоговое состояние — хеш
удлинение   зная H(M) и len(M), можно вычислить H(M || pad || X)
коллизии    ожидаемое число попыток ≈ 1,25·2^(n/2)

Эталонные значения, которые понадобятся для проверки:

SHA256("abc")  ba7816bf8f01cfea414140de5dae2223b00361a396177a9cb410ff61f20015ad
SHA256("")     e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
SHA1("abc")    a9993e364706816aba3e25717850c26c9cd0d89d
MD5("")        d41d8cd98f00b204e9800998ecf8427e

Перечень оснащения

• Ubuntu 24.04 (или WSL2), Python 3.10+, стандартная библиотека, openssl, sha256sum. Права root не нужны.
• Архив окружения: lr-env.zip.

Ограничения ресурсов

Коллизия ищется для усечённого до 32–40 бит SHA-256, поэтому память не превышает сотен мегабайт; дерево Меркла — 8–16 файлов. Время выполнения не нормируется: проверяются свойства и совпадение с тестовыми векторами, а не абсолютные секунды. Если на конкретной машине шаг занимает заметно больше ожидаемого, это фиксируется в журнале вместе с параметрами оборудования.

Безопасная область эксперимента

Работа выполняется в отдельном каталоге ~/crypto-lab-08; всё необходимое лежит в архиве окружения. Учебные серверы и оракулы слушают только 127.0.0.1. Внешняя сеть не используется.

Порядок выполнения работы

mkdir -p ~/lab08 && cd ~/lab08
unzip /path/to/lr-env.zip
python3 sha256_template.py
python3 collision_template.py 32
python3 pow_template.py
python3 length_ext_template.py
python3 merkle_template.py

Каждый файл запускается независимо и печатает результат самопроверки. Начинать нужно с части 1: без работающей реализации SHA-256 часть 4 не выполнить, потому что атака удлинения требует задания начального состояния.

Часть 1. SHA-256 своими руками

Задание

1. Заполните rotr, padding, compress и sha256 в заготовке. Функция sha256(msg, state=IV, prefix_len=0) должна принимать необязательное начальное состояние — оно понадобится в части 4.
2. Проверьте на двух векторах: sha256(b"abc") и sha256(b""). Пустое сообщение важно: дополнение всё равно добавляет блок, и ошибка в обработке длины проявляется именно здесь.
3. Сверьте с hashlib на сотне случайных сообщений разной длины, включая длины 55, 56, 63 и 64 байта — на границах блоков чаще всего ломается дополнение.
4. Сверьте с командной строкой:

printf 'abc' | sha256sum
printf 'abc' | openssl dgst -sha256

5. Измерьте лавинный эффект: для 1000 случайных сообщений инвертируйте один бит и посчитайте число различающихся бит хеша. Среднее должно быть около 128 из 256.

Что должно получиться

Работающая реализация, совпадающая с библиотекой на всех длинах, и распределение лавинного эффекта со средним около 128. Если на длине 55–56 байт результат расходится, ошибка в дополнении: длина не помещается в отведённые 64 бита вместе с битом 1.

Часть 2. Коллизии усечённого хеша

Задание

1. Заполните birthday(bits): поиск коллизии среди значений h(x, bits) с сохранением всех встреченных значений в словаре. Функция возвращает число попыток до первой коллизии.
2. Заполните rho(bits): поиск коллизии методом Флойда (черепаха и заяц) без хранения всех значений. Функция тоже возвращает число шагов.
3. Проведите по 200 испытаний для 24 бит и по 20 для 32 бит каждым методом. Запишите среднее и медиану.
4. Сравните с теорией: 1,25·2^(n/2), то есть около 5100 для 24 бит и около 82 000 для 32 бит. На 200 испытаниях при 24 битах среднее получается около 5 тысяч; при 32 битах разброс велик, и на 12 испытаниях среднее может выйти около 66 тысяч.
5. Объясните разницу в памяти: для 32 бит метод дней рождения требует хранить десятки тысяч значений, ро-метод — константу.

Что должно получиться

Две таблицы «метод — биты — среднее — медиана — память» и вывод: число попыток определяется корнем из размера пространства, а не самим размером. Для реального 256-битного хеша это 2^128 — недостижимо, но именно поэтому усечение до 32 бит «для экономии» уничтожает стойкость.

Часть 3. Частичный прообраз и доказательство работы

Задание

1. Заполните leading_zero_bits и solve(data, k): поиск такого nonce, что хеш начинается с k нулевых бит.
2. Измерьте число попыток для k = 8, 12, 16, 20. Сравните с 2^k.
3. Постройте график зависимости времени от k и убедитесь, что каждые четыре бита увеличивают время примерно в 16 раз.
4. Объясните, почему эта задача асимметрична: поиск требует 2^k работы, проверка — одного хеша.
5. Обсудите, почему для доказательства работы используют хеш, а не, например, факторизацию: проверка должна быть дешёвой.

Что должно получиться

Таблица «k — попытки — время» и вывод о линейном росте в логарифмическом масштабе. Ожидание: для k = 16 около 65 тысяч попыток, для k = 20 — около миллиона.

Часть 4. Атака удлинения сообщения

Задание

1. Изучите mac_service.py: сервис выдаёт тег SHA256(key || msg) для произвольного сообщения и проверяет теги. Ключ создаётся случайно, длина ключа неизвестна.
2. Заполните forge(msg, tag, key_len, suffix): из известного тега и предполагаемой длины ключа постройте тег для msg || pad || suffix.
3. Заполните attack(svc, suffix, max_key_len): переберите длину ключа от 0 до 64 и для каждой попробуйте подделку. Правильная длина та, при которой сервис принимает тег.
4. Получите валидный тег для сообщения с суффиксом &role=admin, не зная ключа.
5. Убедитесь, что SHA-3 и HMAC устойчивы: постройте ту же подделку для SHA3-256(key || msg) и для HMAC-SHA256 и покажите, что проверка не проходит.

Что должно получиться

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

Часть 5. Дерево Меркла

Задание

1. Заполните leaf_hash, node_hash, split_point, root, proof, verify. Обратите внимание на split_point: дерево строится не «удвоением нечётного узла», а делением набора на две части, чтобы избежать известной уязвимости с дублированием.
2. Постройте дерево для 7, 8 и 9 листьев и убедитесь, что корень устойчив к порядку вычислений.
3. Постройте доказательство включения для среднего листа и проверьте его функцией verify, не передавая остальные элементы.
4. Измерьте длину доказательства для N = 8, 64, 1024: она должна быть порядка log₂ N.
5. Покажите, что подмена одного листа меняет корень, и объясните, почему для проверки достаточно корня, полученного по доверенному каналу.

Что должно получиться

Работающее дерево, доказательство включения и таблица «N — длина доказательства». Вывод: дерево Меркла превращает проверку включения из O(N) в O(log N), и именно поэтому оно используется в Git, Certificate Transparency и блокчейне.

Журнал работы

По каждой части: предсказание, команда, результат, объяснение. Для части 2 предсказание — число попыток порядка 2^(n/2), для части 3 — 2^k, для части 4 — что подделка удастся без знания ключа, для части 5 — длина доказательства. Полезно сохранить подделанный тег и сообщение: они пригодятся в теме 9 при разборе HMAC и AEAD.

Критерии проверки

Работа считается выполненной, если:

• проверки проверки из окружения для SHA-256 и дерева Меркла завершаются без ошибок;
• SHA-256 совпал с hashlib на тестовых векторах, коллизия найдена за ожидаемое число попыток, удлинение сообщения сработало, включение в дерево доказано;
• измерения и наблюдения записаны в журнал вместе с объяснением расхождений с предсказанием;
• на контрольные вопросы даны ответы своими словами, а не пересказ команд.

Контрольные вопросы

1. Чем стойкость к коллизиям отличается от стойкости ко второму прообразу и почему первое влечёт второе, а не наоборот?
2. Почему для электронной подписи нужна именно стойкость к коллизиям и какая длина выхода минимально приемлема?
3. Как парадокс дней рождения связывает длину выхода хеша со сложностью поиска коллизии?
4. Почему в дополнение Меркла — Дамгора включается длина исходного сообщения?
5. Что именно позволяет атаку удлинения сообщения и почему она не считается уязвимостью самой хеш-функции?
6. Почему HMAC устойчив к удлинению, хотя построен на той же SHA-256?
7. Почему губка Keccak не подвержена удлинению по построению?
8. Чем выбранно-префиксная коллизия опаснее обычной?
9. Почему MD5 остаётся пригодным для контрольных сумм, но не для подписей?
10. Что даёт дерево Меркла по сравнению с хешем конкатенации всех элементов?
11. Почему дублирование нечётного узла в дереве Меркла считается уязвимостью?
12. Почему хеш не обеспечивает аутентичность и что нужно вместо него?