Приложений.

Энциклопедичный YouTube

• 1 / 5

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

  Данные требования не являются независимыми:

  • Обратимая функция нестойка к коллизиям первого и второго рода.
  • Функция, нестойкая к коллизиям первого рода, нестойка к коллизиям второго рода; обратное неверно.

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

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

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

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

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

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

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

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

  Применения

  Электронная подпись

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

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

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

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

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

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

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

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

  Требования

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

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

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

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

  Доказуемо безопасные хеш-функции

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

  Криптографическая хеш-функция является доказуемо защищённой от коллизий, если задача нахождения коллизий может быть средуцирована за полиномиальное время от задачи P {\displaystyle P} , которая считается неразрешимой за полиномиальное время . Иначе говоря, если алгоритм A {\displaystyle A} позволял бы за полиномиальное время решить задачу нахождения коллизий при существовании редуцирующего алгоритма R {\displaystyle R} , работающего также за полиномиальное время, то последний позволил бы алгоритму A {\displaystyle A} решить задачу P {\displaystyle P} за полиномиальное время, что противоречит её сложности, а значит задача нахождения коллизий не легче задачи P {\displaystyle P} .

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

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

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

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

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

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

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

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

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

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

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

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

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

  «Атака дней рождения»

  Атака «дней рождения» - используемое в криптоанализе название для метода поиска коллизий хеш-функций на основе парадокса дней рождения. Суть парадокса в том, что в группе, состоящей из 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
  SHA-3 (Keccak)	Хеш-функция SHA-3 (также называемая Keccak) является функцией переменной разрядности, разработанная группой авторов во главе с Йоаном Дайменом . 2 октября 2012 года Keccak стала победителем конкурса криптографических алгоритмов , проводимым . 5 августа 2015 года алгоритм функции был утверждён и опубликован в качестве стандарта FIPS 202 . Алгоритм функции SHA-3 построен по принципу криптографической губки .

  Задания

  Написать программу хэширования, использующую метод согласно полученному варианту задания:

  1. MD2 (RFC1319)

  2. MD4 (RFC1320)

  3. MD5 (RFC1321)

  4. SHA1(FIPS 180-1)

  5. SHA2 (FIPS PUB 180-2)

  6. ГОСТ Р 34.11-94

  11. Adler32 (RFC 1950)

  17. Хеширование паролей в Unix

  20. MAC на основе алгоритма симметричного шифрования из 3-ей лабораторной работы

  21. HMAC (RFC 2104)

  Общие сведения о функциях хэширования

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

  h = H(M),

  где М – сообщение произвольной длины;

  h – хэш-код фиксированной длины.

  Требования к хэш-функциям

  Хэш-функция Н должна обладать следующими свойствами:

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

  2. Хэш-функция Н создает выход фиксированной длины.

  3. Н (М ) относительно легко (за полиномиальное время) вычисляется для любого значения М .

  4. Для любого данного значения хэш-кода h M такое, что Н (M ) = h .

  5. Для любого данного х вычислительно невозможно найти y ≠ x , что H (y ) = H (x ).

  6. Вычислительно невозможно найти произвольную пару (х, y) такую, что H (y) = H (x).

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

  Четвертое свойство определяет требование односторонности хэш-функции: легко создать хэш-код по данному сообщению, но невозможно восстановить сообщение по данному хэш-коду. Это свойство важно, если аутентификация с использованием хэш-функции включает секретное значение. Само секретное значение может не посылаться, тем не менее, если хэш-функция не является односторонней, противник может легко раскрыть секретное значение следующим образом. При перехвате передачи атакующий получает сообщение М и хэш-код С = Н (S AB || M). Если атакующий может инвертировать хэш-функцию, то, следовательно, он может получить S AB || M = H -1 (C). Так как атакующий теперь знает и М, и S AB || M, получить S AB совсем просто.

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

  
  

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

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

  Описание

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

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

  Коллизия хеш-функции

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

  В хеш-таблицах

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

  Метод цепочек (метод прямого связывания)

  Метод открытой адресации

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

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

  Криптографическая соль

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

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

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

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

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

  Данные требования не являются независимыми:

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

  Функция, нестойкая к коллизиям первого рода, нестойка к коллизиям второго рода; обратное неверно.

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

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

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

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

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

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

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

  Применение криптографических хеш-функций в создании электронной подписи

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

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

  • повышение криптостойкости;
  • снижение сложности процесса;
  • обеспечение совместимости.

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

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

  Наиболее распространенные криптографические хеш-функции

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

  • MD5 - один из самых распространённых алгоритмов, являющийся криптографической хеш-функцией, размер которой составляет 128 бит. В ближайшее время готовится обновление версии, так как она уже не соответствует высоким стандартам криптоустойчивости.
  • ГОСТ Р 34.11-94 - отечественная криптографическая хеш-функция, генерирующая дайджест длиной 256 бит.
  • ГОСТ Р 34.11-2012 - обновлённая версия, отличающаяся высокой стойкостью к попыткам взлома и стабильностью в работе. Объем выдаваемого хеша может быть как 512, так и 256 бит. Как правило, применяется в системе государственного документооборота, создавая электронные подписи.
  • SHA-1 - криптографическая хеш-функция, преобразующая информацию в строку, длина которой равняется 160 битам. Не обладает достаточным уровнем криптоустойчивости.
  • SHA-2 - криптографическая хеш-функция, созданная на основе алгоритмов SHA: 224; 256; 384; 512; 512/256; 512/224. Несмотря на высокую стойкость к взлому, данный алгоритм используется крайне редко. Причина - неудачный результат одного из криптоанализов, во время которого было выявлено критическое количество коллизий (повторений хеша). Разработчики намерены создать новую криптографическую хеш-функцию SHA-3, которая будет основана на алгоритме Keccak.

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