Учебники

Криптография Хеш-функции

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

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

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

Хэш-функции

Особенности хеш-функций

Типичные особенности хеш-функций —

  • Выход фиксированной длины (значение хэша)

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

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

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

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

  • Эффективность операции

    • Обычно для любой хеш-функции h с входом x вычисление h (x) является быстрой операцией.

    • Вычислительные хеш-функции намного быстрее, чем симметричное шифрование.

Выход фиксированной длины (значение хэша)

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

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

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

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

Эффективность операции

Обычно для любой хеш-функции h с входом x вычисление h (x) является быстрой операцией.

Вычислительные хеш-функции намного быстрее, чем симметричное шифрование.

Свойства хеш-функций

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

  • Сопротивление до изображения

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

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

    • Это свойство защищает от злоумышленника, который имеет только хэш-значение и пытается найти входные данные.

  • Сопротивление второго изображения

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

    • Другими словами, если хеш-функция h для входа x создает хеш-значение h (x), то должно быть трудно найти любое другое входное значение y такое, что h (y) = h (x).

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

  • Сопротивление столкновению

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

    • Другими словами, для хеш-функции h трудно найти любые два различных входа x и y, для которых h (x) = h (y).

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

    • Это свойство очень мешает злоумышленнику найти два входных значения с одинаковым хешем.

    • Кроме того, если хеш-функция устойчива к столкновениям, она является второй устойчивой к изображениям.

Сопротивление до изображения

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

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

Это свойство защищает от злоумышленника, который имеет только хэш-значение и пытается найти входные данные.

Сопротивление второго изображения

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

Другими словами, если хеш-функция h для входа x создает хеш-значение h (x), то должно быть трудно найти любое другое входное значение y такое, что h (y) = h (x).

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

Сопротивление столкновению

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

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

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

Это свойство очень мешает злоумышленнику найти два входных значения с одинаковым хешем.

Кроме того, если хеш-функция устойчива к столкновениям, она является второй устойчивой к изображениям.

Разработка алгоритмов хеширования

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

Размер каждого блока данных варьируется в зависимости от алгоритма. Обычно размеры блоков составляют от 128 до 512 бит. Следующая иллюстрация демонстрирует хэш-функцию —

Структура хэш-функции

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

Этот процесс повторяется столько раз, сколько требуется для хеширования всего сообщения. Схема алгоритма хеширования изображена на следующей иллюстрации —

Алгоритм хеширования

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

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

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

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

Популярные хэш-функции

Давайте кратко рассмотрим некоторые популярные хеш-функции —

Дайджест сообщения (MD)

MD5 был самой популярной и широко используемой хэш-функцией в течение нескольких лет.

  • Семейство MD состоит из хеш-функций MD2, MD4, MD5 и MD6. Он был принят как Интернет-стандарт RFC 1321. Это 128-битная хеш-функция.

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

  • В 2004 году столкновения были обнаружены в MD5. Сообщалось, что аналитическая атака была успешной только через час с использованием компьютерного кластера. Эта атака столкновения привела к взлому MD5 и, следовательно, больше не рекомендуется для использования.

Семейство MD состоит из хеш-функций MD2, MD4, MD5 и MD6. Он был принят как Интернет-стандарт RFC 1321. Это 128-битная хеш-функция.

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

В 2004 году столкновения были обнаружены в MD5. Сообщалось, что аналитическая атака была успешной только через час с использованием компьютерного кластера. Эта атака столкновения привела к взлому MD5 и, следовательно, больше не рекомендуется для использования.

Безопасная хеш-функция (SHA)

Семейство SHA состоит из четырех алгоритмов SHA; SHA-0, SHA-1, SHA-2 и SHA-3. Хотя из одной семьи, есть структурно разные.

  • Первоначальная версия — SHA-0, 160-битная хеш-функция, была опубликована Национальным институтом стандартов и технологий (NIST) в 1993 году. Она имела несколько слабых мест и не стала очень популярной. Позднее, в 1995 году, SHA-1 был разработан для исправления предполагаемых недостатков SHA-0.

  • SHA-1 является наиболее широко используемым из существующих хеш-функций SHA. Он используется в нескольких широко используемых приложениях и протоколах, включая протокол Secure Socket Layer (SSL).

  • В 2005 году был найден метод для выявления коллизий для SHA-1 в течение практического периода времени, что делает долгосрочную возможность использования SHA-1 сомнительной.

  • Семейство SHA-2 имеет еще четыре варианта SHA: SHA-224, SHA-256, SHA-384 и SHA-512 в зависимости от количества бит в их хэш-значении. О хэш-функции SHA-2 пока не сообщалось об успешных атаках.

  • Хотя SHA-2 — сильная хеш-функция. Хотя существенно отличается, его базовый дизайн все еще следует за дизайном SHA-1. Следовательно, NIST призвал к созданию новых конкурентоспособных конструкций хэш-функций.

  • В октябре 2012 года NIST выбрал алгоритм Keccak в качестве нового стандарта SHA-3. Keccak предлагает множество преимуществ, таких как эффективная производительность и хорошая устойчивость к атакам.

Первоначальная версия — SHA-0, 160-битная хеш-функция, была опубликована Национальным институтом стандартов и технологий (NIST) в 1993 году. Она имела несколько слабых мест и не стала очень популярной. Позднее, в 1995 году, SHA-1 был разработан для исправления предполагаемых недостатков SHA-0.

SHA-1 является наиболее широко используемым из существующих хеш-функций SHA. Он используется в нескольких широко используемых приложениях и протоколах, включая протокол Secure Socket Layer (SSL).

В 2005 году был найден метод для выявления коллизий для SHA-1 в течение практического периода времени, что делает долгосрочную возможность использования SHA-1 сомнительной.

Семейство SHA-2 имеет еще четыре варианта SHA: SHA-224, SHA-256, SHA-384 и SHA-512 в зависимости от количества бит в их хэш-значении. О хэш-функции SHA-2 пока не сообщалось об успешных атаках.

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

В октябре 2012 года NIST выбрал алгоритм Keccak в качестве нового стандарта SHA-3. Keccak предлагает множество преимуществ, таких как эффективная производительность и хорошая устойчивость к атакам.

RIPEMD

RIPEND — это аббревиатура для дайджеста сообщения оценки примитивов RACE. Этот набор хеш-функций был разработан открытым исследовательским сообществом и широко известен как семейство европейских хеш-функций.

  • В комплект входят RIPEND, RIPEMD-128 и RIPEMD-160. Также существуют 256 и 320-битные версии этого алгоритма.

  • Оригинальный RIPEMD (128 бит) основан на принципах проектирования, используемых в MD4 и обеспечивает сомнительную безопасность. 128-разрядная версия RIPEMD пришла в качестве быстрой замены для устранения уязвимостей в оригинальной версии RIPEMD.

  • RIPEMD-160 является улучшенной версией и наиболее широко используемой версией в семействе. 256 и 320-битные версии снижают вероятность случайного столкновения, но не имеют более высокого уровня безопасности по сравнению с RIPEMD-128 и RIPEMD-160 соответственно.

В комплект входят RIPEND, RIPEMD-128 и RIPEMD-160. Также существуют 256 и 320-битные версии этого алгоритма.

Оригинальный RIPEMD (128 бит) основан на принципах проектирования, используемых в MD4 и обеспечивает сомнительную безопасность. 128-разрядная версия RIPEMD пришла в качестве быстрой замены для устранения уязвимостей в оригинальной версии RIPEMD.

RIPEMD-160 является улучшенной версией и наиболее широко используемой версией в семействе. 256 и 320-битные версии снижают вероятность случайного столкновения, но не имеют более высокого уровня безопасности по сравнению с RIPEMD-128 и RIPEMD-160 соответственно.

джакузи

Это 512-битная хеш-функция.

  • Он взят из модифицированной версии Advanced Encryption Standard (AES). Одним из дизайнеров был Винсент Раймен, один из создателей AES.

  • Три версии Whirlpool были выпущены; а именно, WHIRLPOOL-0, WHIRLPOOL-T и WHIRLPOOL.

Он взят из модифицированной версии Advanced Encryption Standard (AES). Одним из дизайнеров был Винсент Раймен, один из создателей AES.

Три версии Whirlpool были выпущены; а именно, WHIRLPOOL-0, WHIRLPOOL-T и WHIRLPOOL.

Применение хеш-функций

Существует два непосредственных применения хеш-функции на основе ее криптографических свойств.

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

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

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

  • Файл паролей состоит из таблицы пар в форме (идентификатор пользователя, h (P)).

  • Процесс входа изображен на следующей иллюстрации —

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

Файл паролей состоит из таблицы пар в форме (идентификатор пользователя, h (P)).

Процесс входа изображен на следующей иллюстрации —

Процесс входа

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

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

Проверка целостности данных

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

Процесс изображен на следующей иллюстрации —

Проверка целостности данных

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