Назовите две наиболее распространенные хеш функции выберите два варианта

Обновлено: 07.07.2024

Но, что это такое? Как наглядно представить сущность хэша?

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

Из этого следует, что для любого объема информации, будь-то одна буква или роман Льва Толстого «Война и мир» (или даже всё Полное собрание сочинений этого атвора) существует уникальный и неповторимый хэш — короткая символьная строка. Причем, если в той же «Войне и мире» изменить хотя бы один символ, добавить один лишь знак, — хэш изменится кардинально.

Как такое может быть? Целый многотомный роман и коротокая строчка, которая отражает его!

В этом смысле хэш подобен отпечатку пальца человека.

Как известно, отпечаток пальца уникален и в природе не существует людей с одинаковыми отпечатками. Даже у близнецов отпечатки пальцев разные.

То же касается и структуры ДНК человека. Она уникальна! Нет людей с одинаковым набором ДНК.

Но, ведь, ДНК, а тем более отпечаток пальцев — относительно короткие наборы информации. И, тем не менее, они являются неким кодом, присущим конкретному человеку. Можно считать, что это и есть «хэши» этого человека. С тем лишь отличием, что эти «хэши» не меняются с возрастом человека.

Итак, первое свойство хэша — его уникальность :

Каждому набору (массиву) информации присущ строго определенный, уникальный хэш.

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

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

Следует отметить, что функций, которые вычисляют хэш, существует множество. Но, наиболее распространена (в частности, используется в протоколе блокчейна биткоина) хэш-функция под названием SHA-256 (от Secure Hash Algorithm — безопасный алгоритм хеширования). Эта хэш-функция формирует хэш в виде строки из 64 символов (длина — 256 бит или 32 байта).

Попробуем при помощи SHA-256 hash калькулятора получить хэш для заголовка этой статьи (« Хэширование: Просто и наглядно »).

Это будет: ef3c82303f3896044125616982c715e7757d4cd1f84c34c6b2e64167d2fde766

А теперь изменим заголовок всего лишь на один символ — добавим знак восклицания в конце (« Хэширование: Просто и наглядно ! »).

Получилось: a6123e137d1d7f0aad800cdbc0918a65bb7a778a607cb993043d99718ec5a9e1

Как видите, изменение всего лишь на один знак исходного массива информации привело к кардинальному изменению его хэша!

И это второе важное свойство хэша:

При самом незначительном изменении входной информации её хэш меняется кардинально.

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

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

Не существует обратной функции, которая из хэша может восстановить исходный массив информации.

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

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

Еще одно важное свойство хэш-функций — это высокая скорость работы.

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

Этим хэширование существенно отличается от кодирования (шифрования) и декодирования (дешифрования).

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

Просто и наглядно, как это делается, я расскажу в следующих статьях.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обычно для любой хеш-функции 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 трудно найти любые два различных входа x и y, для которых h (x) = h (y).

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

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

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

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

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

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

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

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

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

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

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

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

Сегодня я хотел бы рассказать о том, что из себя представляет хеш-функция, коснуться её основных свойств, привести примеры использования и в общих чертах разобрать современный алгоритм хеширования SHA-3, который был опубликован в качестве Федерального Стандарта Обработки Информации США в 2015 году.

Общие сведения

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

Для идеальной хеш-функции выполняются следующие условия:

Давайте сразу рассмотрим пример воздействия хеш-функции SHA3-256.

Число 256 в названии алгоритма означает, что на выходе мы получим строку фиксированной длины 256 бит независимо от того, какие данные поступят на вход.

На рисунке ниже видно, что на выходе функции мы имеем 64 цифры шестнадцатеричной системы счисления. Переводя это в двоичную систему, получаем желанные 256 бит.

Любой заинтересованный читатель задаст себе вопрос: "А что будет, если на вход подать данные, бинарный код которых во много раз превосходит 256 бит?"

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

Надеюсь, теперь нет сомнений в том, что это очень внушительное число!

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

Свойства

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

Pre-image resistance

Second pre-image resistance

Имея заданное входное значение , должно быть сложно найти другое входное значение такое, что

Collision resistance

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

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

Second pre-image resistance. Это свойство называют сопротивлением второму прообразу. Для упрощения можно сказать, что это свойство находится где-то посередине между двумя предыдущими. Атака по нахождению второго прообраза происходит, когда злоумышленник находит определенный вход, который генерирует тот же хеш, что и другой вход, который ему уже известен. Другими словами, злоумышленник, зная, что пытается найти такое, что

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

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

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

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

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

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

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

Предлагаю также рассмотреть следующий бытовой пример:

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

Теперь давайте поговорим о SHA-3.

Национальный институт стандартов и технологий (NIST) в течение 2007—2012 провёл конкурс на новую криптографическую хеш-функцию, предназначенную для замены SHA-1 и SHA-2.

Организаторами были опубликованы некоторые критерии, на которых основывался выбор финалистов:

Способность противостоять атакам злоумышленников

• Производительность и стоимость

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

• Гибкость и простота дизайна

Гибкость в эффективной работе на самых разных платформах, гибкость в использовании параллелизма или расширений ISA для достижения более высокой производительности

В финальный тур попали всего 5 алгоритмов:

Победителем и новым SHA-3 стал алгоритм Keccak.

Давайте рассмотрим Keccak более подробно.

Keccak

Хеш-функции семейства Keccak построены на основе конструкции криптографической губки, в которой данные сначала «впитываются» в губку, а затем результат Z «отжимается» из губки.

Любая губчатая функция Keccak использует одну из семи перестановок которая обозначается , где

перестановки представляют собой итерационные конструкции, состоящие из последовательности почти одинаковых раундов. Число раундов зависит от ширины перестановки и задаётся как где

В качестве стандарта SHA-3 была выбрана перестановка Keccak-f[1600], для неё количество раундов

Далее будем рассматривать

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

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

Соотношение деления зависит от конкретного алгоритма семейства, например, для SHA3-256

В SHA-3 строка состояния S представлена в виде массива слов длины бит, всего бит. В Keccak также могут использоваться слова длины , равные меньшим степеням 2.

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

• Строка P делится на n блоков длины

• «Впитывание»: каждый блок дополняется нулями до строки длиной бит (b = r+c) и суммируется по модулю 2 со строкой состояния , далее результат суммирования подаётся в функцию перестановки и получается новая строка состояния , которая опять суммируется по модулю 2 с блоком и дальше опять подаётся в функцию перестановки . Перед началом работы криптографической губки все элементыравны 0.

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

Все сразу станет понятно, когда вы посмотрите на картинку ниже:

Функция дополнения

Функция перестановок

Базовая функция перестановки состоит из раундов по пять шагов:

Тета, Ро, Пи, Хи, Йота

Далее будем использовать следующие обозначения:

Так как состояние имеет форму массива , то мы можем обозначить каждый бит состояния как

Обозначим результат преобразования состояния функцией перестановки

Также обозначим функцию, которая выполняет следующее соответствие:

- обычная функция трансляции, которая сопоставляет биту бит ,

где - длина слова (64 бит в нашем случае)

Я хочу вкратце описать каждый шаг функции перестановок, не вдаваясь в математические свойства каждого.

Шаг

Эффект отображения можно описать следующим образом: оно добавляет к каждому биту побитовую сумму двух столбцов и

Схематическое представление функции:

Шаг

Отображение направлено на трансляции внутри слов (вдоль оси z).

Проще всего его описать псевдокодом и схематическим рисунком:

Шаг

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

Шаг

Шаг является единственный нелинейным преобразованием в

Псевдокод и схематическое представление:

Шаг

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

Ниже приведена таблица раундовых констант для бит

Все шаги можно объединить вместе и тогда мы получим следующее:

Где константы являются циклическими сдвигами и задаются таблицей:

Итоги

В данной статье я постарался объяснить, что такое хеш-функция и зачем она нужна
Также в общих чертах мной был разобран принцип работы алгоритма SHA-3 Keccak, который является последним стандартизированным алгоритмом семейства Secure Hash Algorithm

Цель лекции: познакомиться с понятием "хеш- функция ", а также с принципами работы таких функций.

Понятие хеш-функции

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

Хеш-функции широко применяются в современной криптографии.

Результат ( 0110 0101₍₂₎ или 65₍₁₆₎ ) и будет значением хеш-функции.

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

Сформулируем основные требования, предъявляемые к криптографическим хеш-функциям:

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

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

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

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

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

В качестве начального хеш-кода h₀ берут некоторую константу. Шифрование производится в режиме простой замены. При использовании указанного способа размер блока совпадает с длиной ключа и размером хеш-значения будет длина блока .

$h_i=f(M_i,h_</p> ) \oplus M_i,\\ h_i=f(M_i,h_) \oplus h_ \oplus M_i,\\ h_i=f(h_,M_i) \oplus h_i,\\ h_i=f(h_\oplus M_i,M_i) \oplus h_i\\$

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

Основным недостатком хеш-функций, спроектированных на основе блочных алгоритмов, является относительно низкая скорость работы. Необходимую криптостойкость можно обеспечить и за меньшее количество операций над входными данными. Существуют более быстрые алгоритмы хеширования, спроектированных самостоятельно, с нуля, исходя из требований криптостойкости (наиболее распространенные из них – MD5 , SHA-1 , SHA -2 и ГОСТ Р 34.11-94).

Читайте также:

Назовите две наиболее распространенные хеш функции выберите два варианта

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

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

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

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

RIPEMD

джакузи

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

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

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

Общие сведения

Свойства

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

Keccak

Функция перестановок

Итоги

Понятие хеш-функции

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