Хэш-функция (collision-resistant hash-function)

Хэш-функция (collision-resistant hash-function) — это функция, отображающая строки бит в строки бит фиксированной длины и удовлетворяющая следующим свойствам:

1. По данному значению функции сложно вычислить исходные данные, отображаемые в это значение (предобразная стойкость).
2. Для заданных исходных данных сложно вычислить другие исходные данные, отображаемые в то же значение функции (слабая стойкость к коллизиям).
3. Сложно вычислить какую-либо пару исходных данных, отображаемых в одно и то же значение (сильная стойкость к коллизиям) (ГОСТ Р 34.10-2012).

Назначение

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

• Защита данных: Хэш-функции предотвращают подделку сообщений или документов, используемых в цифровых подписях.
• Проверка целостности: Позволяют убедиться, что данные не были изменены, например, при передаче файлов или сообщений.
• Безопасное хранение: Хэширование паролей защищает их от кражи, сохраняя только хэш-коды.
• Ускорение обработки: Хэш-функции применяются в хэш-таблицах для быстрого поиска и управления данными.
• Идентификация: Создают уникальные идентификаторы для данных, упрощая поиск дубликатов или сравнение файлов.

Хэш-функции используются в веб-приложениях, базах данных, сетевых протоколах и устройствах Интернета вещей.

Как работает

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

1. Ввод данных: Данные любого размера (от нескольких байт до гигабайт) передаются в функцию.
2. Обработка: Алгоритм разбивает данные на блоки, применяет математические операции (например, побитовые сдвиги, умножение) и сжимает их в строку бит.
3. Вывод хэш-кода: Результат — строка фиксированной длины (например, 256 бит для SHA-256), называемая хэш-кодом.

Ключевые свойства хэш-функции:

• Необратимость: Вычислительно сложно восстановить исходные данные из хэш-кода.
• Слабая стойкость к коллизиям: Для заданного входа трудно найти другой вход с тем же хэш-кодом.
• Сильная стойкость к коллизиям: Трудно найти любые два входа с одинаковым хэш-кодом.
• Лавинный эффект: Небольшое изменение входных данных радикально меняет хэш-код.

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

Хэш-функции, стойкие к коллизиям, обладают следующими характеристиками:

• Фиксированная длина вывода: Хэш-код имеет определенную длину (например, 128, 256 или 512 бит), независимо от размера входных данных.
• Скорость вычисления: Алгоритм должен быть достаточно быстрым для практического применения, но сложным для атак.
• Криптографическая стойкость: Устойчивость к предобразным атакам и коллизиям, обеспечивающая безопасность.
• Минимизация коллизий: Коллизия — это случай, когда разные входные данные дают одинаковый хэш-код. Стойкие хэш-функции делают такие случаи вычислительно сложными.

Типы хэш-функций

Хэш-функции делятся на несколько типов в зависимости от их применения и свойств:

• Криптографические хэш-функции:
  • Используются в системах безопасности, таких как цифровые подписи и хранение паролей.
  • Примеры: SHA-256, SHA-3, BLAKE2.
  • Свойства: стойкость к коллизиям, необратимость, высокая вычислительная сложность для атак.
• Некриптографические хэш-функции:
  • Применяются для хэш-таблиц и контрольных сумм.
  • Примеры: CRC32, MurmurHash.
  • Свойства: высокая скорость, но низкая защита от преднамеренных атак.
• Идеальные хэш-функции:
  • Исключают коллизии для заданного набора данных.
  • Используются в специализированных структурах данных, например, в маршрутизаторах.
• Универсальные хэш-функции:
  • Выбираются случайным образом из семейства функций для минимизации коллизий.
  • Применяются в хэш-таблицах и криптографии.

Коллизии и стойкость к ним

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

• Слабая стойкость: Для заданного входа x трудно найти другой вход x’, чтобы H(x) = H(x’).
• Сильная стойкость: Трудно найти любые два входа x и x’, чтобы H(x) = H(x’).

Парадокс дней рождения показывает, что для хэш-функции с N-битным выводом вероятность коллизии возникает после примерно 2^(N/2) вычислений. Например, для 256-битного хэш-кода это около 2^128 операций, что считается безопасным.

Методы борьбы с коллизиями:

• Криптографическая соль: Добавление случайных данных к входу для усложнения атак.
• Метод цепочек: Хранение списка ключей для каждого хэш-кода в хэш-таблицах.
• Открытая адресация: Поиск следующей свободной ячейки при коллизии в хэш-таблицах.

Применение

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

• Криптография:
  • Создание цифровых подписей, где хэш-код сообщения подписывается для подтверждения подлинности.
  • Хранение паролей в виде хэш-кодов с добавлением соли для защиты от атак по словарям.
• Проверка целостности:
  • Сравнение хэш-кодов файлов или сообщений для проверки их неизменности.
  • Использование в сетевых протоколах, таких как TCP/IP, для обнаружения ошибок передачи.
• Хэш-таблицы:
  • Ускорение поиска данных в базах данных или структурах, таких как словари.
  • Применение в алгоритмах для идентификации дубликатов.
• Геометрическое хэширование:
  • Обработка многомерных данных в компьютерной графике и телекоммуникациях.

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

Безопасность

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

• Подделка цифровых подписей: Два документа с одинаковым хэш-кодом позволяют злоумышленнику подменить один документ другим.
• Манипуляция данными: В распределенных системах одинаковые хэш-коды могут ввести пользователей в заблуждение относительно версии файла.

Известные уязвимости:

• Алгоритмы MD5 и SHA-1 утратили стойкость из-за найденных методов, более эффективных, чем перебор.
• Современные алгоритмы, такие как SHA-256 и SHA-3, обеспечивают высокую стойкость к коллизиям.

Для повышения безопасности:

• Используйте длинные хэш-коды (256 бит и более).
• Добавляйте криптографическую соль для защиты от атак.
• Регулярно обновляйте алгоритмы, избегая устаревших, таких как MD5.

Замечания

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