Что такое хеширование данных

Хэширование: Просто и наглядно

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Это будет: ef3c82303f3896044125616982c715e7757d4cd1f84c34c6b2e64167d2fde766

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

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

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

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

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

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

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

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

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

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

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

Источник

Что такое хеширование?

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

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

Как работает хэш-функция?

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

Чтобы проиллюстрировать это, давайте пропустим слова “Binance“ и “binance” через алгоритм хеширования SHA-256 (тот, который используется в биткоин).

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

Таким же образом, если мы пропустим одни и те же входные данные с помощью алгоритма хеширования SHA-1, мы получим следующие результаты:

Стоит отметить, что акроним SHA расшифровывается как Secure Hash Algorithms (безопасный алгоритм хеширования). Он относится к набору криптографических хэш-функций, который включает такие алгоритмы как SHA-0 и SHA-1 вместе с группами SHA-2 и SHA-3. SHA-256 является частью группы SHA-2, наряду с SHA-512 и другими аналогами. В настоящее время, только группы SHA-2 и SHA-3 считаются безопасными.

Почему это имеет значение?

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

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

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

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

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

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

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

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

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

Устойчивость к коллизии

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

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

Устойчивость к поиску первого прообраза

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

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

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

Устойчивость к поиску второго прообраза

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

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

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

Майнинг

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

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

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

Заключение

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

Источник

Чудеса хеширования

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

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

Что такое хеш?

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

Как работает хеш?

Например, мое имя — Brian — после преобразования хеш-функцией SHA-1 (одной из самых распространенных наряду с MD5 и SHA-2) при помощи онлайн-генератора будет выглядеть так: 75c450c3f963befb912ee79f0b63e563652780f0. Как вам скажет, наверное, любой другой Брайан, данное имя нередко пишут с ошибкой, что в итоге превращает его в слово brain (мозг). Это настолько частая опечатка, что однажды я даже получил настоящие водительские права, на которых вместо моего имени красовалось Brain Donohue. Впрочем, это уже другая история. Так вот, если снова воспользоваться алгоритмом SHA-1, то слово Brain трансформируется в строку 97fb724268c2de1e6432d3816239463a6aaf8450. Как видите, результаты значительно отличаются друг от друга, даже несмотря на то, что разница между моим именем и названием органа центральной нервной системы заключается лишь в последовательности написания двух гласных. Более того, если я преобразую тем же алгоритмом собственное имя, но написанное уже со строчной буквы, то результат все равно не будет иметь ничего общего с двумя предыдущими: 760e7dab2836853c63805033e514668301fa9c47.

Впрочем, кое-что общее у них все же есть: каждая строка имеет длину ровно 40 символов. Казалось бы, ничего удивительного, ведь все введенные мною слова также имели одинаковую длину — 5 букв. Однако если вы захешируете весь предыдущий абзац целиком, то все равно получите последовательность, состоящую ровно из 40 символов: c5e7346089419bb4ab47aaa61ef3755d122826e2. То есть 1128 символов, включая пробелы, были ужаты до строки той же длины, что и пятибуквенное слово. То же самое произойдет даже с полным собранием сочинений Уильяма Шекспира: на выходе вы получите строку из 40 букв и цифр. При всем этом не может существовать двух разных массивов данных, которые преобразовывались бы в одинаковый хеш.

Вот как это выглядит, если изобразить все вышесказанное в виде схемы:

Для чего используется хеш?

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

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

Вы даже можете провести простой эксперимент: попробуйте при помощи специального сайта произвести преобразование какого-нибудь простого пароля вроде «123456» или «password» из их хеш-значений (созданных алгоритмом MD5) обратно в текст. Вероятность того, что в базе хешей найдутся данные о введенных вами простых паролях, очень высока. В моем случае хеши слов «brain» (8b373710bcf876edd91f281e50ed58ab) и «Brian» (4d236810821e8e83a025f2a83ea31820) успешно распознались, а вот хеш предыдущего абзаца — нет. Отличный пример, как раз для тех, кто все еще использует простые пароли.

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

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

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

Как при помощи хеша ловить вирусы?

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

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

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

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

Свойства

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

Pre-image resistance

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

Second pre-image resistance

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

Collision resistance

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

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

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

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

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

Pre-image 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.

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

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

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

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

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

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

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

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

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

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

Шаг

Шаг

Шаг

Шаг

Шаг

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

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

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

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

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

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

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

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

Шаг

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

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

Шаг

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

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

Шаг

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

Шаг

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

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

Шаг

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

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

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

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

Итоги

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

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

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

Источник