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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Принципы построения[править | править код]

Итеративная последовательная схема[править | править код]

Интерактивная последовательная схема.jpg

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

Входной поток разбивается на блоки по (k − n) бит. Алгоритм использует вре́менную переменную размером в n бит, в качестве начального значения которой берется некое общеизвестное число. Каждый следующий блок данных объединяется с выходным значением сжимающей функции на предыдущей итерации. Значением хеш-функции являются выходные n бит последней итерации. Каждый бит выходного значения хеш-функции зависит от всего входного потока данных и начального значения. Таким образом достигается лавинный эффект.

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

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

Сжимающая функция на основе симметричного блочного алгоритма[править | править код]

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

A, B и C могут принимать значения или быть константой, где  — i-й блок входного потока,  — сложение по модулю 2,  — результат i-й итерации.

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

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

Схемы безопасного хеширования.jpg

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

Требования[править | править код]

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

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

2. Стойкость к поиску второго прообраза — вычислительно невозможно, зная сообщение m и его свертку H(m), найти такое другое сообщение m′ ≠ m , чтобы H(m) = H(m′).

3. Стойкость к коллизиям

Коллизией для хеш-функции называется такая пара значений m и m′, m ≠ m′, для которой H(m) = H (m′). Так как количество возможных открытых текстов больше числа возможных значений свертки, то для некоторой свертки найдется много прообразов, а следовательно, коллизии для хеш-функций обязательно существуют. Например, пусть длина хеш-прообраза 6 битов, длина свертки 4 бита. Тогда число различных сверток – , а число хеш-прообразов – , т.е. в 4 раза больше, значит хотя бы одна свертка из всех соответствует 4 прообразам.

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

Стоит отметить, что данные свойства не являются независимыми:

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

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

При разработке современного российского стандарта ГОСТ Р 34.11-2012 (Стрибог) к криптографическим хеш-функциям были сформулированы следующие требования: 

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

Идеальная криптографическая хеш-функция[править | править код]

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

  1. Детерминированность. При одинаковых входных данных результат выполнения хеш-функции будет одинаковым (одно и то же сообщение всегда приводит к одному и тому же хешу);
  2. Высокая скорость вычисления значения хеш-функции для любого заданного сообщения;
  3. Невозможность сгенерировать сообщение из его хеш-значения, за исключением попыток создания всех возможных сообщений;
  4. Наличие лавинного эффекта. Небольшое изменение в сообщениях должно изменить хэш-значения, так широко, что новые хэш-значения не совпадают со старыми хэш-значениями;
  5. Невозможность найти два разных сообщения с одинаковыми хеш-значениями.

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

Злоумышленник будет искать прообраз для идеальной хеш-функции следующим образом: у него есть число h, и ему надо найти такое m, что H(m) = h. Если это идеальная хеш-функция, то злоумышленнику остается лишь перебирать все возможные M и проверять, чему равна хеш-функция от этого сообщения. Результат вычисления, если m перебирается полностью, есть фактически случайное число. Если число h лежит в диапазоне от 0 до , то тогда в среднем на поиски нужного h злоумышленник будет тратить итераций. Таким образом, вычисление прообраза займёт в два раза меньше итераций, чем в идеальном случае.

Вычисление второго прообраза останется . В поиске коллизий оценка даст , причём это не совсем точный результат. Данная оценка идет из оценки так называемого «Парадокса дней рождения».

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

«Атака дней рождения»[править | править код]

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

Для 60 и более человек вероятность такого совпадения превышает 99 %, хотя 100 % она достигает, согласно принципу Дирихле, только тогда, когда в группе не менее 367 человек (ровно на 1 больше, чем число дней в високосном году; с учётом високосных лет).

Семейство хеш-функций MD и SHA[править | править код]

На сегодняшний день подавляющую долю применений хеш-функций «берут на себя» алгоритмы MD5, SHA-1, SHA-256, а в России еще и  ГОСТ Р 34.11-2012 (Стрибог). Конечно, существует и множество других менее известных, или распространенных только в узких сообществах алгоритмов (например, RIPEMD, TIGER, Panama и др.), однако эти алгоритмы не так распространены. Ниже представлен анализ хэш-функций MD4, которая была предшественником MD5, а также хеш-функции SHA. 

Тип Описание
MD4 Самая быстрая, оптимизирована для 32-битных машин среди семейства MD-функций.

Хэш-функция, разработанная профессором Массачусетского университета Рональдом Ривестом в 1990 году и впервые описанная в RFC 1186. Содержит три цикла по 16 шагов каждый. В 1993 году был описан алгоритм взлома MD4, поэтому на сегодняшний день данная функция не рекомендована для использования с реальными приложениями.

MD5 Наиболее распространенная из семейства MD-функций. Похожа на MD4, но средства повышения безопасности делают ее на 33% медленнее, чем MD4. Содержит четыре цикла по 16 шагов каждый. Обеспечивает контроль целостности данных.

Первые успешные попытки взлома данной хеш-функции датируются 1993: исследователи Берт ден Боер и Антон Боссиларис показали, что в алгоритме возможны псевдоколлизии. В 1996 году Ганс Доббертин показал наличие возможности коллизий и теоретически описал алгоритм взлома. 24 августа 2004 года четыре независимых исследователя — Ван Сяоюнь, Фэн Дэнгуо, Лай Сюэцзя и Юй Хунбо — обнаружили уязвимость алгоритма, позволяющую найти коллизии аналитическим методом за более-менее приемлемое время. В 2005 году Властимил Клима опубликовал алгоритм, позволяющий обнаруживать коллизии за несколько часов. Восемнадцатого марта 2006 года исследователь обнародовал алгоритм, находящий коллизии за одну минуту, который позднее получил название «туннелирование». На сегодняшний день MD5 не рекомендована для использования в реальных приложениях. 

SHA-1 

(Secure 

Hash 

Algorithm 1)

В 1993 году NSA совместно с NIST разработали алгоритм безопасного хеширования (сейчас известный как SHA-0) (опубликован в документе FIPS PUB 180) для стандарта безопасного хеширования. Однако вскоре NSA отозвало данную версию, сославшись на обнаруженную ими ошибку, которая так и не была раскрыта. И заменило его исправленной версией, опубликованной в 1995 году в документе FIPS PUB 180-1. Эта версия и считается тем, что называют SHA-1.

Позже, на конференции CRYPTO в 1998 году два французских исследователя представили атаку на алгоритм SHA-0, которая не работала на алгоритме SHA-1. Возможно, это и была ошибка, открытая NSA.

SHA-1 создает 160-битное значение, называемое также дайджестом сообщения. Содержит четыре этапа. И MD5, и SHA-1 являются, по сути, улучшенными продолжениями MD4. Различия:

  1. В SHA-1 на четвертом этапе используется та же функция, что и на втором этапе.
  2. В MD5 в каждом действии используется уникальная прибавляемая константа. В SHA-1 константы используются повторно для каждой из четырех групп.
  3. В SHA-1 добавлена пятая переменная.
  4. SHA-1 использует циклический код исправления ошибок.
  5. В MD5 четыре различных элементарных логических функции, в SHA-1 — три.
  6. В MD5 длина дайджеста составляет 128 бит, в SHA-1 — 160 бит.
  7. SHA-1 содержит больше раундов (80 вместо 64) и выполняется на 160-битном буфере по сравнению со 128-битным буфером MD5. Таким образом, SHA-1 должен выполняться приблизительно на 25 % медленнее, чем MD5 на той же аппаратуре.
SHA-2 Семейство криптографических алгоритмов — хеш-функций, включающее в себя алгоритмы SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/256 и SHA-512/224.

В 2003 году Гилберт и Хандшух провели исследование SHA-2, но не нашли каких-либо уязвимостей.  Однако в марте 2008 года индийские исследователи Сомитра Кумар Санадия и Палаш Саркар опубликовали найденные ими коллизии для 22 итераций SHA-256 и SHA-512. В сентябре того же года они представили метод конструирования коллизий для усечённых вариантов SHA-2 (21 итерация). Как показали исследования[1], алгоритмы SHA-2 работают в 2—3 раза медленнее хеш-алгоритмов MD5SHA-1.

SHA-3 (Keccak) Хеш-функция SHA-3 (также называемая Keccak) является функцией переменной разрядности, разработанная группой авторов во главе с Йоаном Дайменом. 2 октября 2012 года Keccak стала победителем конкурса криптографических алгоритмов, проводимым Национальным институтом стандартов и технологий США[2]. 5 августа 2015 года алгоритм функции был утверждён и опубликован в качестве стандарта FIPS 202[3][4]. Алгоритм функции SHA-3 построен по принципу криптографической губки.

Применения[править | править код]

Электронная подпись[править | править код]

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

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

Проверка парольной фразы[править | править код]

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

Примером в данном случае могут служить ОС GNU/Linux и Microsoft Windows XP. В них хранятся лишь хеш-значения парольных фраз из учётных записей пользователей.

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

Пусть некий клиент, с именем name, производит аутентификацию по парольной фразе, pass, на некоем сервере. На сервере хранится значение хеш-функции H(pass, R2), где R2 — псевдослучайное, заранее выбранное число. Клиент посылает запрос (name, R1), где R1 — псевдослучайное, каждый раз новое число. В ответ сервер посылает значение R2. Клиент вычисляет значение хеш-функции H(R1, H(pass, R2)) и посылает его на сервер. Сервер также вычисляет значение H(R1, H(pass, R2)) и сверяет его с полученным. Если значения совпадают — аутентификация верна.

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

Примечания[править | править код]

  1. Speed Comparison of Popular Crypto Algorithms (англ.). www.cryptopp.com. Проверено 22 декабря 2017.
  2. Swenson, Gayle. NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition (англ.), NIST (2 October 2012). Проверено 23 декабря 2017.
  3. Hernandez, Paul. NIST Releases SHA-3 Cryptographic Hash Standard (англ.), NIST (5 August 2015). Проверено 23 декабря 2017.
  4. Morris J. Dworkin. SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions (англ.) // Federal Inf. Process. Stds. (NIST FIPS) - 202. — 2015-08-04.

Литература[править | править код]

Ссылки[править | править код]

См. также[править | править код]