Цифровой отпечаток документа: хеш

Хеш, но не браун

Шеф-функция, ой, простите: хеш!

Представьте два договора. Они выглядят одинаково, называются одинаково и занимают примерно одинаковый объём. Но в одном из них срок оплаты — 15 дней, а в другом — 45.

Как компьютеру быстро определить, что документы различаются?

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

Для этого используется хеш-функция, чем-то похожа по сути своей на сложение: можно записать длинный набор цифр, типа 1, 3, 7, 16, а потом взять и сложить все. Вот и получится короткая запись этих чисел. Только тут математики так все устроили, что суммы у разных слагаемых никогда не повторятся, даже если вы их поменяете местами.

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

Документ любого размера
          ↓
      Хеш-функция
          ↓
Хеш фиксированной длины

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

Один короткий результат для данных любого размера

Хеш-функция может обработать:

• одно слово;

• электронное письмо;

• фотографию;

• PDF-документ;

• видеозапись;

• архив на несколько гигабайт.

Размер входных данных может отличаться в миллиарды раз, но длина цифрового отпечатка (или хеша) для выбранного алгоритма остаётся одинаковой.

Например, хеш-функция с результатом длиной 256 бит всегда выдаёт 256 бит, сколько бы ей не скормили длины начального документа:

Слово
  ↓
Хеш-функция
  ↓
256 бит


PDF-файл на 20 МБ
  ↓
Та же хеш-функция
  ↓
256 бит


Архив на 5 ГБ
  ↓
Та же хеш-функция
  ↓
256 бит

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

Условный пример:

9f4a2c7e1b8d...5a91

Это не зашифрованный фрагмент документа и не его сокращённая копия. По хешу нельзя просто «распаковать» исходный файл.

Хеш — результат математического преобразования всего содержимого.

Одинаковые данные дают одинаковый хеш

Хеш-функция работает детерминированно:

Это позволяет проверять целостность файлов.

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

Хеш, опубликованный организацией
                =
Хеш скачанного файла

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

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

Поэтому хеш сам по себе не подтверждает автора и не заменяет электронную подпись.

Маленькое изменение — другой отпечаток

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

Рассмотрим две строки:

Оплатить счёт до 15 августа.

и

Оплатить счёт до 16 августа.

Для человека изменилось только одно число. Но хеши должны выглядеть как два несвязанных значения.

Такое поведение называют лавинным эффектом: изменение одного бита на входе влияет на множество битов результата.

Упрощённо:

Документ A
    ↓
7A 19 C4 82 0F ...


Изменён один символ
    ↓
D3 E8 51 6B A7 ...

По новому хешу нельзя определить, где именно изменился документ. Хеш сообщает только одно: набор входных данных теперь другой.

Это важно для электронной подписи. Если после подписания изменить:

• одну букву;

• сумму;

• дату;

• пробел;

• служебные данные внутри файла;

• хотя бы один байт,

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

Компьютер видит байты, а не внешний вид документа

Пользователь смотрит на страницы, текст и изображения. Хеш-функция получает последовательность байтов.

Из-за этого два документа могут выглядеть одинаково, но иметь разные хеши.

Например, PDF-файлы могут различаться:

• встроенными шрифтами;

• порядком внутренних объектов;

• метаданными;

• версией программы, которая создала файл;

• датой сохранения внутри структуры;

• способом сжатия;

• невидимыми служебными полями.

На экране страницы будут одинаковыми, но байты — разными.

PDF № 1
Внешне: одинаковый документ
Байты:  ... A4 19 7C ...
Хеш:    81F2...


PDF № 2
Внешне: одинаковый документ
Байты:  ... B8 03 D1 ...
Хеш:    C507...

И наоборот: обычное переименование файла без изменения его содержимого обычно не меняет хеш самих данных.

dogovor.pdf
     ↓ переименование
dogovor-final.pdf

Содержимое не изменилось
Хеш содержимого тот же

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

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

Хеширование — не шифрование

Хеширование и шифрование иногда путают, потому что в обоих случаях исходные данные превращаются в непонятную последовательность символов.

Но задачи у них разные.

Шифрование

Шифрование должно позволять восстановить исходные данные при наличии ключа.

Документ
    +
Ключ
    ↓
Шифртекст
    +
Ключ
    ↓
Документ

Главная задача — скрыть содержание от посторонних.

Хеширование

Хеширование не предназначено для восстановления документа.

Документ
    ↓
Хеш-функция
    ↓
Хеш

Обратного штатного преобразования нет

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

Почему хеш нельзя обратить

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

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

Упрощённо:

Документ
    ↓ легко
Хеш


Документ
    ← вычислительно неосуществимо
Хеш

Но важно правильно понимать слово «необратимость».

Хеш-функция не обязана хранить внутри себя зашифрованный документ. Она сжимает огромное множество возможных входов в намного меньшее множество результатов.

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

При этом для коротких и предсказуемых данных возможен перебор.

Например, если известно, что хеш вычислен от четырёхзначного PIN-кода, злоумышленник может:

1. перебрать значения от 0000 до 9999;

2. вычислить хеш каждого;

3. найти совпадение.

Это не означает, что хеш-функцию «расшифровали». Просто пространство возможных исходных значений оказалось слишком маленьким.

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

Три важных свойства криптографического хеша

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

1. Стойкость к нахождению прообраза

Дан хеш:

H = хеш(?)

Нужно найти любые данные, которые дают H.

Для стойкой функции такая задача должна быть вычислительно неосуществимой.

2. Стойкость к нахождению второго прообраза

Дан конкретный документ:

Документ A → хеш H

Нужно найти другой документ:

Документ B → тот же хеш H

Причём:

Документ A ≠ Документ B

Такая задача тоже должна быть вычислительно неосуществимой.

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

3. Стойкость к коллизиям

Нужно найти любую пару разных входных данных с одинаковым хешем:

Документ X ≠ Документ Y

но

хеш(X) = хеш(Y)

Здесь заранее не задан ни один из документов. Можно искать любую подходящую пару.

Эта задача отличается от поиска второго прообраза и обычно имеет другую сложность.

Коллизии существуют. Почему это не ломает хеш-функцию?

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

Например, 256-битный хеш может принимать:

2²⁵⁶

разных значений.

Это колоссальное число, но количество возможных файлов всё равно больше. Значит, по принципу Дирихле какие-то разные входные данные неизбежно имеют одинаковый хеш.

Такое совпадение называется коллизией.

На первый взгляд кажется, что из-за этого хеширование ненадёжно. Но криптографическое требование звучит не так:

Оно звучит так:

Для идеальной n-битной хеш-функции поиск произвольной коллизии в среднем требует порядка 2^(n/2) операций из-за так называемого парадокса дней рождения.

Поэтому длина хеша влияет на запас стойкости.

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

Именно поэтому нельзя выбирать хеш-функцию только по принципу «она выдаёт длинную строку».

Хеш и контрольная сумма — не одно и то же

Контрольные суммы применяются давно. Например, CRC помогает обнаруживать случайные ошибки при передаче или хранении данных.

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

Но случайная ошибка и намеренная подмена — разные угрозы.

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

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

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

Как хеш используется в электронной подписи

Документ может быть очень большим, а алгоритм электронной подписи работает с числами определённого размера.

Поэтому сначала вычисляется хеш документа:

Документ
    ↓
Криптографическая хеш-функция
    ↓
Хеш документа

Затем значение, полученное из хеша, участвует в формировании подписи вместе с закрытым ключом и другими параметрами алгоритма.

Упрощённо:

Документ
    ↓
Хеш-функция
    ↓
Хеш
    +
Закрытый ключ
    +
Дополнительные параметры
    ↓
Электронная подпись

При проверке программа снова вычисляет хеш полученного документа:

Полученный документ
          ↓
      Хеш-функция
          ↓
Вычисленный хеш
          +
Электронная подпись
          +
Открытый ключ
          ↓
Криптографическая проверка
          ↓
Подпись верна / проверка не пройдена

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

Важно: подпись обычно не содержит копию документа. Поэтому при проверке отсоединённой подписи нужен сам исходный файл.

Почему нельзя подписать один файл, а проверить другой

Допустим, был подписан документ:

Сумма договора: 100 000 рублей.

После подписания кто-то изменил его:

Сумма договора: 900 000 рублей.

Хеш изменённого файла будет другим.

Исходный документ
        ↓
      Хеш A
        ↓
Электронная подпись


Изменённый документ
        ↓
      Хеш B

Хеш A ≠ Хеш B

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

Даже если:

• имя файла осталось прежним;

• подпись лежит рядом;

• сертификат действителен;

• подписант тот же,

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

Что хеш сам по себе не доказывает

Предположим, у нас есть:

Документ
    +
Его хеш

Можно проверить, соответствуют ли они друг другу. Но нельзя автоматически установить:

• кто вычислил хеш;

• когда он был вычислен;

• кому принадлежит документ;

• не заменил ли злоумышленник одновременно документ и хеш.

Для подтверждения связи с владельцем ключа используется электронная подпись.

Документ
    ↓
Хеш
    +
Закрытый ключ подписанта
    ↓
Электронная подпись

А для связи открытого ключа с человеком или организацией используется сертификат.

Получается цепочка:

Хеш
Связывает подпись с конкретными данными

Электронная подпись
Связывает данные с закрытым ключом

Сертификат
Связывает открытый ключ с владельцем

Каждый элемент решает свою задачу.

ГОСТ Р 34.11-2012

В российских криптографических средствах используется функция хеширования, определённая ГОСТ Р 34.11-2012.

Стандарт описывает вычисление хеша для произвольной последовательности двоичных данных и предусматривает результаты длиной:

• 256 бит;

• 512 бит.

Эту хеш-функцию часто называют «Стрибог».

ГОСТ Р 34.11-2012 используется совместно с алгоритмом электронной подписи ГОСТ Р 34.10-2012. В варианте подписи с 256-битными параметрами применяется 256-битный хеш, а в варианте с 512-битными параметрами — 512-битный.

Сам хеш не является электронной подписью. Он только создаёт компактное криптографическое представление документа, которое затем используется алгоритмом формирования подписи.

Нужно ли пользователю вычислять хеш вручную

Обычно нет.

При создании электронной подписи криптографическое средство выполняет необходимые операции автоматически:

Вы выбрали документ
          ↓
Программа вычислила хеш
          ↓
Криптографическое средство создало подпись
          ↓
Получен подписанный документ
или отдельный файл подписи

При проверке процесс также выполняется автоматически.

Но понимание роли хеша помогает объяснить многие ситуации:

• почему изменение одного символа нарушает подпись;

• почему визуально одинаковые файлы могут иметь разные подписи;

• почему для отсоединённой подписи нужен именно исходный файл;

• почему переименование неизменённого файла обычно не мешает проверке;

• почему нельзя «перенести» подпись с одного документа на другой.

Резюме

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

Криптографический хеш должен обладать важными свойствами:

• одинаковые данные дают одинаковый результат;

• небольшое изменение данных существенно меняет хеш;

• по хешу должно быть вычислительно неосуществимо найти подходящий исходный документ;

• должно быть вычислительно неосуществимо подобрать другой документ с тем же хешем;

• поиск произвольных коллизий должен быть непрактичным.

В электронной подписи хеш связывает подпись со всем содержимым документа. Но для создания подписи нужен ещё один важный компонент — секретный закрытый ключ. А надёжность этого ключа начинается со случайности.

В следующей статье: «Зачем электронной подписи нужны случайные числа».

Нормативная и дополнительная информация

• ГОСТ Р 34.11-2012. Функция хеширования

• RFC 6986. GOST R 34.11-2012: Hash Function

• ГОСТ Р 34.10-2012. Процессы формирования и проверки электронной цифровой подписи

• RFC 7091. GOST R 34.10-2012: Digital Signature Algorithm

• NIST Cryptographic Standards and Guidelines: Hash Functions