Хеш-функция, что это такое? / Хабр

Приветствую уважаемого читателя!

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

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

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

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

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

а) хеш-функция является детерминированной, то есть одно и то же сообщение приводит к одному и тому же хеш-значению
b) значение хеш-функции быстро вычисляется для любого сообщения
c) невозможно найти сообщение, которое дает заданное хеш-значение
d) невозможно найти два разных сообщения с одинаковым хеш-значением
e) небольшое изменение в сообщении изменяет хеш настолько сильно, что новое и старое значения кажутся некоррелирующими

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

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

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

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

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

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

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

Свойства

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

Pre-image resistance

Имея заданное значение h, должно быть сложно найти любое сообщение m такое, что

Second pre-image resistance

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

Collision resistance

Должно быть сложно найти два различных сообщения и таких, что

Такая пара сообщений и называется коллизией хеш-функции

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

SHA-3

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

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

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

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

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

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

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

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

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

• BLAKE

• Grøstl

• JH

• Keccak

• Skein

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

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

Keccak

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

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

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

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

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

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

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

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

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

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

• С помощью функции дополнения исходное сообщение M дополняется до строки P длины кратной r

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

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

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

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

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

В SHA-3 используется следующий шаблон дополнения 10…1: к сообщению добавляется 1, после него от 0 до r — 1 нулевых бит и в конце добавляется 1.

r — 1 нулевых бит может быть добавлено, когда последний блок сообщения имеет длину r — 1 бит. В этом случае последний блок дополняется единицей и к нему добавляется блок, состоящий из r — 1 нулевых бит и единицы в конце.

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

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

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

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

1. Шаг

2. Шаг

3. Шаг

4. Шаг

5. Шаг

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

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

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

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

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

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

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

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

Шаг

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

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

Псевдокод шага:

Шаг

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

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

Шаг

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

Шаг

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

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

Шаг

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

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

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

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

Итоги

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

Надеюсь, все было понятно и интересно

Всем спасибо за внимание!

Что такое криптографическая хеш-функция? — SSL.

com

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

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

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

1. Одно и то же сообщение всегда приводит к одному и тому же хеш-значению (т.е. детерминистический).
2. Хеш-значение вычисляется быстро.
3. Невозможно иметь два сообщения с одинаковым значением хеш-функции (так называемое «столкновение»).

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

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

Схемы цифровой подписи (например, для подписание документа, подпись кода или S/MIME e-mail) обычно требуют, чтобы криптографический хеш вычислялся для сообщения и включался в подпись. Программное обеспечение получателя затем независимо вычисляет хеш для проверки целостности сообщения. 

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

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

Криптографические хеш-функции широко используются в таких протоколах безопасности, как SSL /TLS и SSH, и в других приложениях, которые полагаются на целостность данных. Криптовалюты используют алгоритмы хеширования для обновления блокчейна новыми блоками защищенных и проверяемых данных транзакций. (Например, BitCoin использует SHA-2 для подтверждения транзакции.)

Что такое SHA-1?

SHA-1 (безопасный алгоритм хеширования 1) — это криптографическая хеш-функция, которая может преобразовывать произвольно длинную строку данных в дайджест с фиксированным размером 160 бит. Этот дайджест обычно отображается в виде шестнадцатеричного числа из 40 символов.

Алгоритм SHA-1 теперь считается небезопасным, Сертификаты SHA-1 больше не соответствуют базовым требованиям форума CA / B или поддерживаются текущими версиями основных веб-браузеров.

Серия хэш-функций алгоритма безопасного хеширования (SHA) состоит из различных наборов (SHA-0, SHA-1, SHA-2, SHA-3).

Что такое SHA-2?

SHA-2 (безопасный алгоритм хеширования 2) относится к семейству криптографических хеш-функций, которые могут преобразовывать произвольно длинные строки данных в дайджесты фиксированного размера (224, 256, 384 или 512 бит). 256-битный SHA-2, также известный как

SHA-256, является наиболее часто используемой версией. Дайджест обычно отображается как шестнадцатеричное число с фиксированным значением. (Например, SHA-256 возвращает код из 64 символов.)

SHA-2 вытеснил SHA-1 в протоколах безопасности, таких как SSL /TLS.

Связанные часто задаваемые вопросы

Просмотреть все часто задаваемые вопросы

Подписывайтесь на Нас

Обрабатывать @sslcorp

Facebook Twitter Youtube Github

Что такое SSL /TLS?

Воспроизвести видео

Эл. адрес

Не пропустите новые статьи и обновления с SSL.com

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

Опубликовано редакцией Synopsys в четверг, 10 декабря 2015 г.

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

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

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

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

Хороший

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

Плохой

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

• Злоумышленники, оснащенные быстрым оборудованием, могут легко «взломать» хешированные учетные данные.
• Хорошие алгоритмы хеширования спроектированы так, чтобы быть устойчивыми к коллизиям, но полностью исключить коллизии невозможно. Было доказано, что MD5 и SHA-1 содержат известные коллизии, то есть создают одно и то же значение хеш-функции из разных учетных данных.
• Радужные таблицы — это «оптимизированные справочные таблицы», которые можно использовать для обратного проектирования однонаправленных хэш-функций. Радужная таблица — это предварительно вычисленный набор строк открытого текста и соответствующих им хэшей. Большие радужные таблицы общедоступны, и злоумышленники могут использовать одну из этих таблиц для извлечения данных в открытом виде, которые были хешированы.

Усильте свои криптографические хэши

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

Посоленные хэши

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

Хеш-функции с ключом

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

Адаптивные хеш-функции

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

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

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

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

Узнайте о лучших в отрасли инструментах для каждого этапа вашего SDLC.

Это сообщение находится в разделе Создание безопасного программного обеспечения.

 

Сообщение от

Редакция Synopsys

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

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

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

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

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

Ключевые выводы

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

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

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

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

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

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

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

Примеры криптографических хеш-функций

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

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

Проверка пароля

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

Создание и проверка подписи

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