Открыть главное меню

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

Принципы построенияПравить

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

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

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

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

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

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

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

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

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

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

Основным недостатком хеш-функций, спроектированных на основе блочных алгоритмов, является низкая скорость работы. Необходимую криптостойкость можно обеспечить и за меньшее количество операций над входными данными. Существуют более быстрые алгоритмы хеширования, спроектированных самостоятельно, с нуля, исходя из требований криптостойкости. Наиболее распространенные из них — 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]

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

Аналогично определяется доказуемая защищённость от поиска первого и второго прообраза.

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

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

Недостатки доказательного подходаПравить

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

  • Текущие доказуемо безопасные алгоритмы хеширования слишком вычислительно сложны для того, чтобы использоваться на практике. По сравнению с обычными хеш функциями они достаточно медленные.
  • Создание доказуемо безопасных хеш функций значительно более трудоёмко, чем классические подходы.
  • Само доказательство безопасности часто основывается на задаче, имеющей требуемую сложность в среднем или в худшем случае. Сложность в худшем случае чаще всего описывает патологические ситуации, а не типичные для этой задачи. Даже редукция к задаче со сложностью в среднем обеспечивает ограниченную защищённость, так как может быть найден алгоритм, который легко решает проблему для определённого подмножества данных задачи. Так, например, было показано, что для двух из трёх предложенных в оригинальной статье для функции Fast Syndrome-Based hash параметров существуют более оптимальные атаки, чем предложенные создателями для доказательства безопасности.[3]

SWIFFT является примером хеш функции, которая несколько обходит описанную проблему безопасности. Может быть показано, что для любого алгоритма, который взламывает SWIFFT с вероятностью   за время   найдётся алгоритм, который решает определённую математическую задачу в худшем случае за время   в зависимости от   и  .[4]

Примеры доказуемо безопасных хеш-функцииПравить

  • VSH - Very Smooth Hash function - доказуемо безопасная устойчивая к коллизиям функция, опирающаяся на сложность нахождения нетривиальных квадратных корней по модулю составного числа n (что является настолько же сложным, насколько разложение n на множители).
  • MuHASH
  • ECOH - Elliptic curve only hash[en] - основанная на идее эллиптических кривых, задаче о сумме подмножеств и суммировании полиномов хеш функция. Доказательство безопасности опиралось на предположение о NP-полноте лежащей в основе математической задачи, однако была найдена уязвимость к обобщённой атаке "дней рождения" Вагнера, связанной с поиском второго прообраза.[5]
  • FSB - Fast Syndrome-Based hash function - может быть показано, что взломать FSB по меньшей мере настолько же трудно, насколько решить NP-полную задачу, известную как регулярное синдромное декодирование.[6]
  • SWIFFT - SWIFFT основан на БПФ и доказуемо безопасен при довольно слабом предположении о сложности нахождения коротких векторов в циклической/идеальной решетке в худшем случае.[7]
  • Chaum, van Heijst, Pfitzmann hash function - функция, в которой нахождение коллизий так же трудоёмко, как и при нахождении дискретного логарифма в конечной группе  .
  • Knapsack-based hash functions - семейство хеш-функций, основанное на задаче о рюкзаке.
  • Существует общий подход к построению доказуемо безопасных алгоритмов хеширования на основе любого подходящего сигма протокола[en]. Более быстрая версия VSH (называющаяся VSH*) может быть получена таким способом.

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

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

  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 итерация). Как показали исследования[8], алгоритмы SHA-2 работают в 2—3 раза медленнее хеш-алгоритмов MD5SHA-1.

SHA-3 (Keccak) Хеш-функция SHA-3 (также называемая Keccak) является функцией переменной разрядности, разработанная группой авторов во главе с Йоаном Дайменом. 2 октября 2012 года Keccak стала победителем конкурса криптографических алгоритмов, проводимым Национальным институтом стандартов и технологий США[9]. 5 августа 2015 года алгоритм функции был утверждён и опубликован в качестве стандарта FIPS 202[10][11]. Алгоритм функции 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. Daniel Augot, Matthieu Finiasz, Nicolas Sendrier. A Fast Provably Secure Cryptographic Hash Function. — 2003. — № 230. — С. 3-4.
  2. Daniel Augot, Matthieu Finiasz, Nicolas Sendrier. A Fast Provably Secure Cryptographic Hash Function. — 2003. — № 230. — С. 3.
  3. Jean-Sebastien Coron, Antoine Joux. Cryptanalysis of a Provably Secure Cryptographic Hash Function. — 2004. — № 013. — С. 1,3.
  4. Alon Rosen, Chris Peikert, Daniele Micciancio, Vadim Lyubashevsky. SWIFFT: A Modest Proposal for FFT Hashing (англ.) // Fast Software Encryption. — Springer, Berlin, Heidelberg, 2008-02-10. — P. 65. — ISBN 9783540710387, 9783540710394. — DOI:10.1007/978-3-540-71039-4_4.
  5. Michael A. Halcrow, Niels Ferguson. A Second Pre-image Attack Against Elliptic Curve Only Hash (ECOH). — 2009. — № 168.
  6. Daniel Augot, Matthieu Finiasz, Nicolas Sendrier. A Fast Provably Secure Cryptographic Hash Function. — 2003. — № 230.
  7. Alon Rosen, Chris Peikert, Daniele Micciancio, Vadim Lyubashevsky. SWIFFT: A Modest Proposal for FFT Hashing (англ.) // Fast Software Encryption. — Springer, Berlin, Heidelberg, 2008-02-10. — P. 54–72. — ISBN 9783540710387, 9783540710394. — DOI:10.1007/978-3-540-71039-4_4.
  8. Speed Comparison of Popular Crypto Algorithms (англ.). www.cryptopp.com. Дата обращения 22 декабря 2017.
  9. Swenson, Gayle. NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition (англ.), NIST (2 October 2012). Дата обращения 23 декабря 2017.
  10. Hernandez, Paul. NIST Releases SHA-3 Cryptographic Hash Standard (англ.), NIST (5 August 2015). Дата обращения 23 декабря 2017.
  11. Morris J. Dworkin. SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions (англ.) // Federal Inf. Process. Stds. (NIST FIPS) - 202. — 2015-08-04.

ЛитератураПравить

СсылкиПравить

См. такжеПравить