@@ -1,70 +1,135 @@
-- Криптографические xэш - функции
+= Хеш-функции
 
+В данной статье описаны принципы построения хеш-функций.  Описана  конструкция Меркла - Дамгарда и ее развитие в схемах Рабина,  Девиса-Мейера,  Миагучи-Пренеля, выделены их различия.
+Приведены  результаты криптоанализа SHA-2, SHA-3, Whirlpool, позволяющие сделать вывод о дальнейшем развитии хеш-функций.
 
-	Хэширование : преобразование исходного информационного массива произвольной длины в битовую строку фиксированной длины.
+'''Ключевые слова''': хеш-функции,  cхема Меркла ­- Дамгарда, SHA-2, SHA-3, Whirlpool
+ 
+- 1. Введение
+	''Хэширование'' : преобразование исходного информационного массива произвольной длины в битовую строку фиксированной длины.
 	
-	Криптографическая хэш-функция : хэш-функция, являющаяся криптографически стойкой, то есть удовлетворяющая ряду требований, специфичных для криптографических приложений.
+	''Криптографическая хэш-функция'' : хэш-функция, являющаяся криптографически стойкой, то есть удовлетворяющая ряду требований, специфичных для криптографических приложений.
 	
 
-	Требования к криптографически стойким хэш-функциям :
+	Требования к криптографически стойким хэш-функциям:
 
 	* Для заданного значения хэш-функции $$X$$ должно быть невозможно вычислить блок данных $$M$$, для которого $$H(M) = X$$.
-	* Стойкость к коллизиям первого рода: для заданного сообщения $$M$$ должно быть вычислительно невозможно подобрать другое сообщение $$N$$, для которого $$H(M) = H(N)$$.
-	* Стойкость к коллизиям второго рода: должно быть вычислительно невозможно подобрать пару сообщений $$(M, M  prime  )$$, имеющих одинаковый хэш.
+	* Стойкость к коллизиям первого рода: для заданного сообщения $$M$$ должно быть невозможно подобрать другое сообщение $$N$$, для которого $$H(M) = H(N)$$.
+	* Стойкость к коллизиям второго рода: должно быть  невозможно подобрать пару сообщений $$(M, M  prime  )$$, имеющих одинаковый хэш.
+	* Для криптографических хэш-функций также важно, чтобы при малейшем изменении аргумента значение функции сильно изменялось (лавинный эффект).
 
 	Математически хэш функцию можно записать в виде:
 	
-	$$H(M) = X$$,
+	$$H(M) = X$$, где $$M$$ – исходное сообщение, $$X$$ – значение хэш-функции.
 
-	где $$M$$ – исходное сообщение, $$X$$ – значение хеш-функции.
+	Функции хеширования могут применяться в качестве криптографических генераторов псевдослучайных чисел для создания нескольких ключей на основе одного секретного ключа. Криптографические хеш-функции используют для защиты информации от несанкционированного доступа. Примером таких функций являются MD5, SHA-1 и SHA-2. Также хеш-функции применяют в базах данных для хранения паролей и организации хеш-таблиц. 
 
+Несмотря на повсеместное применение функций хеширования, мы знаем о них гораздо меньше, чем о блочных шифрах. По сравнению с блочными шифрами функции хеширования крайне мало исследованы. 
+-2. Структура хеш-функций
 
-	Для криптографических хэш-функций также важно, чтобы при малейшем изменении аргумента значение функции сильно изменялось (лавинный эффект).
+--2.1 Итеративная последовательная схема
+Схема Меркла-Дамгарда является основанием для многих функций криптографического хэширования. 
+Cжимающая функция $$f$$  преобразует $$k$$ блоков, размер каждого состоит из $$n$$ бит. В качестве начального значения переменной  $$H sub 0$$   используется вектор инициализации IV. Каждый следующий блок данных объединяется с выходным значением сжимающей функции на предыдущей итерации.  Если длина блока $$H sub m < n$$,  блок дополняется длиной сообщения и «0» битами. Значением хеш-функции являются выходные n бит последней итерации. Схема приведена на Рис. 1.
 
---Итеративная последовательная схема
-Схема Меркеля-Дамгарда сегодня - основание для многих функций криптографического хэширования. 
-Для построения хэш-функций используется cтруктура Меркля-Дамгарда. Cжимающая функция $$f$$ преобразует $$m$$ блоков,размер каждого состоит из $$n$$ бит.
+http://www.intuit.ru/EDI/18_11_15_6/1447798956-19904/tutorial/577/objects/2/files/02_01.gif
 
-В качестве начального значения переменной $$H sub 0$$  используется произвольное вектор инициализации $$IV$$. Каждый следующий блок данных объединяется с выходным значением сжимающей функции на предыдущей итерации.
-Если длина блока $$H sub m$$ < $$n$$,  $$Hm$$ дополняется длиной сообщения и $$0$$. Значением хэш-функции являются выходные $$n$$ бит последней итерации. 
+Алгоритм хеширования намного легче реализовать по сравнению с функциями, которые напрямую работают со значениями переменной длины. Итеративная структура позволяет начинать вычисление хеша сообщения, как только у нас появится часть этого cообщения. Благодаря этому в приложениях, работающих с поточными данными, можно хешировать сообщение не сохраняя данные в буфере. 
+Несмотря на популярность схемы Меркеля-Дамгарда, ряд работ показал недостатки данной конструкции, связанные с множественными коллизиями [2], дополнением сообщения до нужной длины, нахождением второго прообраза [3].
 
-http://www.intuit.ru/EDI/18_11_15_6/1447798956-19904/tutorial/577/objects/2/files/02_01.gif
+--2.2 Функция сжатия
+
+	''Односторонняя функция сжатия'' : функция для преобразования двух входных блоков фиксированной длины в выходной блок фиксированной длины.
+	В настоящее время популярны два подхода для создания хэш-функций. В первом подходе  создается  "специальная" функция сжатия: она разработана только для этой цели. Во втором подходе блочный шифр с симметричными ключами служит функцией сжатия.
+
+-3. Примеры хеш-функций
+--3.1 "Специальные" хеш-функции
+---3.1.1  SHA-2
+
+В 1993 году  национальный Институт Стандартов и Технологии (NIST - National Institute of Standards and Technology) разработал алгоритм безопасного хеширования SHA-0. В 1995 г. он был пересмотрен и опубликован под названием FIP 180-1 (SHA-1). С публикацией в 2001 году FIPS PUB 180-2, NIST добавил дополнительные хэш-функции в семейство SHA:SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/256 и SHA-512/224. Алгоритмы известны под общим названием SHA-2.
+
+Основой для SHA-2 является структура Меркла — Дамгарда.
+Входное сообщение разбивается на блоки длины $$L$$. Для SHA-224 и SHA-256 $$L = 512$$ бит, для SHA-384,-512,-512/256, -512/224 $$L = 1024$$ бит.
+На каждом раунде в функцию сжатия поступают входной блок  сообщения и выход предыдущего блока. Хэш блока $$M sub i$$ равен $$H sub i$$ = $$f(M sub i, H sub {i-1})$$. Хэш-значением всего сообщения является выход последнего блока. Для SHA-224 и SHA-256 $$0 <=i <=60$$, для SHA-384,-512,-512/256, -512/224 $$0 <=i <= 80$$.
+
+Ниже приведена схема одной иттерации для SHA-2:
+
+https://upload.wikimedia.org/wikipedia/commons/thumb/7/7d/SHA-2.svg/836px-SHA-2.svg.png
+
+Сравнение SHA-1 и SHA-2 приведено в таблице
+
+{| center
+|hc! Алгоритм |hc! Длина сообщения (в битах) |hc! Длина блока (в битах) |hc! Длина слова (в битах)
+|hc! Длина дайджеста сообщения (в битах) |hc! Безопасность (в битах)
+|--
+| SHA-1 |c! $$< 2 sup 64$$ |c! 512 |c! 32 |c! 160 |c! 80
+|--
+| SHA-256 |c! $$< 2 sup 64$$ |c! 512 |c! 32 |c! 256 |c! 128
+|--
+| SHA-384 |c! $$< 2 sup 128$$ |c! 1024 |c! 64 |c! 384 |c! 192
+|--
+| SHA-512 |c! $$< 2 sup 128$$ |c! 1024 |c! 64 |c! 512 |c! 256
+|}
+
+В марте 2008 года индийские исследователи Сомитра Кумар Санадия и Палаш Саркар опубликовали найденные ими коллизии для 22 итераций SHA-256 и SHA-512. В сентябре 2008 года они представили метод конструирования коллизий для 21 итерации SHA-2.
+Было принято решение отказаться от SHA-2,и 2 октября 2012 года NIST утвердил в качестве стандарта SHA-3 алгоритм Keccak.
+
+---3.1.2 SHA-3
+
+Алгоритм хеширования, разработанный группой авторов во главе с Йоаном Дайменом. 2 октября 2012 года Keccak стал победителем конкурса NIST. 5 августа 2015 года алгоритм утверждён и опубликован в качестве стандарта FIPS 202. Алгоритм SHA-3 построен по принципу криптографической губки.
+	
+
+На начальной стадии задаётся исходное состояние из нулевого вектора размером до 1600 бит. Затем производится операция xor фрагмента исходного сообщения $$P sub 0$$ с фрагментом исходного состояния размером $$r$$, оставшаяся часть состояния остаётся незатронутой. Результат обрабатывается функцией $$f$$, и так повторяется до исчерпания блоков исходного сообщения. 
+Функция $$f$$ выполняет перемешивание внутреннего состояния алгоритма. Состояние представляется в виде массива $$5×5$$, элементами которого являются 64-битные слова, инициализированные нулевыми битами. Функция $$f$$ выполняет 24 раунда, выход функции $$f$$ - хэш произвольной длины.
+
+https://upload.wikimedia.org/wikipedia/commons/thumb/7/70/SpongeConstruction.svg/512px-SpongeConstruction.svg.png
 
---Функция сжатия
+Keccak – стойкая хеш-функция. Сложность атаки на все 24 раунда в 2010 году составила $$2 sup 1590$$ и была улучшена в 2011 до $$2 sup 1579$$. 
 
-	Односторонняя функция сжатия : функция для преобразования двух входных блоков фиксированной длины в выходной блок фиксированной длины.
- В настоящее время популярны два подхода для создания хэш-функций. В первом подходе функция сжатия сделана на "пустом месте": она разработана только для этой цели. Во втором подходе блочный шифр с симметричными ключами служит функцией сжатия.
+--3.2 Хэш-функции, основанные на блочных шифрах
 
+В качестве функции сжатия можно использовать блочный шифр с симметричными ключами, например трехкратный DES или AES. Рассмотрим несколько схем для построения сжимающей функции
 
----Хэш-функции, сделанные на "пустом месте"
+---3.2.1 Сxема Рабина
+Сxема Рабина базируется на схеме Меркеля-Дамгарда. Функция сжатия заменяется любым алгоритмом шифрования.  Входами функции сжатия являются блок сообщения  и выход предыдущего блока. Выход представляет собой дайджест сообщения. Иными словами дайджест сообщения $$M sub i$$ равен $$H sub i$$ = $$E(M sub i, H sub {i-1})$$. Хэш-значением всего сообщения является выход последнего блока. Размер дайджеста совпадает с размером блочного шифра данных в основной криптографической системе.
 
-	MD5 : один из серии алгоритмов по построению дайджеста сообщения, разработанный профессором Рональдом Л. Ривестом из Массачусетского технологического института. Был разработан в 1991 году как более надёжный вариант предыдущего алгоритма MD4. Позже Гансом Доббертином(Hans Dobbertin)  были найдены недостатки алгоритма MD4.
-В 1996 году Ганс Доббертин объявил о коллизии в алгоритме, и было предложено использовать другие алгоритмы хеширования, такие как Whirlpool, и SHA-1.
-	SHA-1 :
-В 1993 году  национальный Институт Стандартов и Технологии (NIST - National Institute of Standards and Technology) разработал алгоритм безопасного хеширования SHA-0. В 1995 г. он был пересмотрен и опубликован под названием FIP 180-1 (SHA-1). Позже были оперделены четыре новые версии: SHA-224, SHA-256, SHA-384 и SHA-512. Сравнение этих версий приведено в таблице:
+http://www.intuit.ru/EDI/18_11_15_6/1447798956-19904/tutorial/577/objects/2/files/02_02.gif
 
-http://www.intuit.ru/EDI/02_08_15_9/1438467644-3097/tutorial/1335/objects/3/files/pic3_11.jpg
+---3.2.2 Схема Девиса-Мейера (Davies-Mayer)
+В схеме Девиса-Мейера, в отличии от схемы Рабина блок $$H sub i$$ и зашифрованый текст складываются с помощью XOR и создается новый блок $$H sub {i+1}$$.
 
- В качестве функции сжатия можно использовать блочный шифр с симметричными ключами, например трехкратный DES или AES. 
+http://www.intuit.ru/EDI/18_11_15_6/1447798956-19904/tutorial/577/objects/2/files/02_03.gif
 
-В качестве сжимающей функции можно расмотреть одностороннюю функцию сжатия Миагучи-Пренеля (Miyaguchi–Preneel). Чтобы сделать алгоритм более устойчивым к атаке, исходный текст $$M sub i$$, блок $$H sub i$$ и зашифрованный текст складываются с помощью $$XOR$$ и создают новый блок $$H sub {i+1}$$. Эта схема используется в Whirlpool для создания хэш-функции.
+---3.2.3 Схема Миагучи-Пренеля (Miyaguchi–Preneel)
+Чтобы сделать алгоритм более устойчивым к атаке, исходный текст $$M sub i$$, блок $$H sub i$$ и зашифрованный текст складываются с помощью $$XOR$$ и создают новый блок $$H sub {i+1}$$. Эта схема используется в Whirlpool для создания хэш-функции.
 
 http://mipt1.ru/7_infosafe/26/02_05.gif
 
---Криптогафическая хэш-функция Whirlpool
-	Whirlpool : криптографическая хэш-функция, разработанная Vincent Rijmen и Paulo S. L. M. Barreto . Впервые опубликована в ноябре 2000 года. Осуществляет хэширование входного сообщения с длиной до $$2 sup {256}$$ бит. 
+---3.2.4 Криптогафическая хэш-функция Whirlpool
+	Whirlpool: криптографическая хеш-функция, разработанная Винсентом Риджменом и Пауло Баретто. Впервые опубликована в ноябре 2000 года. Осуществляет хэширование входного сообщения с длиной до 2256 бит. Ообрена европейской организацией NESSIE (New European Schemes for Signature, Integrity and Encryption - Новые европейские схемы подписей, целостности и шифрования).
 
-Whirlpool использует структуру Меркля-Дамгарда и  одностороннюю функцию сжатия Миагучи-Пренеля
-для формирования 512-блока зашифрованого текста $$W$$. Поскольку внутренний блок шифрования $$W$$ работает с 512-битными входными сообщениями, то исходное сообщение необходимо разбить на блоки по 512 бит. При этом последний блок, который содержит конец сообщения, может оказаться неполным.
+	С момента создания в 2000 году Whirlpool дважды подвергалась модификации. Первая версия, WHIRLPOOL-0, была представлена в качестве кандидата в проекте NESSIE в 2000 году.
 
-Для решения данной задачи в Whirlpool используется дополнение входного сообщения. Результатом дополнения сообщения $$M$$ является сообщение $$M  prime$$, длина которого кратна 512. Пусть $$L$$ — длина исходного сообщения. Для того, чтобы получить $$M  prime$$, необходимо сделать 3 операции:
-	1 К концу сообщения $$M$$ приписать бит «1» ; 
-	1 Приписать x битов «0» так, чтобы длина полученной строки $$L+1+x$$ была кратна 256 нечетное число раз;
-	1  Приписать 256-битное представление числа $$L$$.
+	Модификация WHIRLPOOL-0, названная WHIRLPOOL-T, в 2003 году была добавлена в перечень рекомендованных к использованию криптографических функций NESSIE. Изменения касались блока подстановки S-Box: в первой версии структура S-Box не была описана, и он генерировался совершенно произвольно. В новой версии S-Box приобрёл чёткую структуру.
+	В 2004 году был обнаружен  дефект в диффузных матрицах WHIRLPOOL-T [7] После его исправления была принята  конечная версия Whirlpool.
 
-Полученная строка разбивается на 512-битовые блоки $$M sub 1$$, $$M sub 2$$, $$M sub t$$, которые используются для генерации последовательности хэш-значений $$H sub 1$$, $$H sub 2$$, $$H sub t$$.
-$$H sub 0$$ - строка из 512 «0» битов. Для вычисления $$H sub i$$, W  шифрует $$M sub i$$, используя в качестве ключа $$H sub {i-1}$$, и выполняет $$XOR$$ между $$H sub {i-1}$$ и $$M sub i$$. Значением хэш-функции является $$H sub t$$. 
+	В 2009 году был опубликован новый способ атаки на хеш-функции - The Rebound Attack [8].Удалось сгенерировать коллизию для 4.5 раундoв Whirlpool со сложностью 2120. Однако, данная атака не сильно повлияла на криптостойкость Whirlpool, сложность вычислений оказалась достаточно высока. На сегодняшний день  хеш-функция Whirlpool  устойчива ко всем видам криптоанализа. 
+Для построения Whirlpool используется структура Меркла - Дамгарда и  односторонняя функция сжатия Миагучи-Пренеля.
+
+-4. Заключение
+
+Коллизии существуют для большинства хеш-функций, но для криптографически стойких хеш-функций частота их возникновения минимальна. Если для некоторой хеш-функции находится способ получения коллизий существенно более быстрый, чем полный перебор, то эта хеш-функция перестаёт считаться криптостойкой и использоваться для передачи и хранения секретной информации.
+В заключение отметим, большинство хеш-функций основывается на итеративных блочных шифрах, взлом шифра ведет к взлому хеш-алгоритма. Появление в 2014 году атак на алгоритм Keecak позволяет сделать вывод о том, что в скором времени появятся новые, усовершенствованные криптографические алгоритмы.
+ 
+-5. Список литературы
+
+	1 Schneier Bruce, Ferguson Niels, «Practical cryptography» - Inc, Wiley Publishing, p 432 ,2003.
+	1 Antoine Joux, «Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions», In M. Franklin, Advances in Cryptology - CRYPTO 2004, Vol. 3152 of Lecture Notes in Computer Science, pp. 306–316, Springer, 2004.
+	1 Ueli Maurer, Renato Renner, Clemens Holenstein, «Indiff erentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology», In M. Naor , Theory of Cryptography, First Theory of Cryptography Conference, Vol. 2951 of Lecture Notes in Computer Science, pp. 21-39, Springer, 2004.
+	1 Somitra Kumar Sanadhya, Palash Sarkar, «Deterministic Constructions of 21-Step Collisions for the SHA-2 Hash Family», Information Security, 11th International Conference, ISC 2008, Taipei, Taiwan
+	1 Ming Duan, Xuejia Lai, «Improved Zero-Sum Distinguisher for Full Round Keccak-f Permutation»,  editors, Chinese Science Bulletin, Vol. 57, Issue 6, pp. 694-697, SP Science China Press, 2012.
+	1 Itai Dinur, Pawe Morawiecki, Josef Pieprzyk, Marian Srebrny, and Micha Straus, «Practical Complexity Cube Attacks on Round-Reduced Keccak Sponge Function», Cryptology ePrint Archive, 2014.
+	1 Taizo Shirai, Kyoji Shibutani, «On the diffusion matrix employed in the Whirlpool hashing function» - NESSIE public report, 2003
+	1 Florian Mendel, Christian Rechberger, Martin Schlaffer, Soren S. Thomsen, «The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grostl»,  Unpublished Manuscript
 
-http://www.larc.usp.br/~pbarreto/MiyaguchiPreneel.gif
 
 #КатегорияКриптография