@@ -1,119 +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:
 
----MD5
+https://upload.wikimedia.org/wikipedia/commons/thumb/7/7d/SHA-2.svg/836px-SHA-2.svg.png
 
-Серия алгоритмов по построению дайджеста сообщения, была разработанна профессором Рональдом Л. Ривестом из Массачусетского технологического института. MD5 был выпущен в 1991 году для замены предыдущего алгоритма, MD4. Позже Гансом Доббертином(Hans Dobbertin)  были найдены недостатки алгоритма MD4.В 1996 году Ганс Доббертин объявил о коллизии в алгоритме, и было предложено использовать другие алгоритмы хэширования, такие как Whirlpool, и SHA-1.
+Сравнение SHA-1 и SHA-2 приведено в таблице
 
----SHA-1
+{| 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
+|}
 
- В 1993 году  национальный Институт Стандартов и Технологии (NIST - National Institute of Standards and Technology) разработал алгоритм безопасного хеширования SHA-0. В 1995 г. он был пересмотрен и опубликован под названием FIP 180-1 (SHA-1). Позже были оперделены четыре новые версии: SHA-224, SHA-256, SHA-384 и SHA-512. Сравнерние различных версий SHA приведено в таблице:
+В марте 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 построен по принципу криптографической губки.
+	
 
-http://www.intuit.ru/EDI/02_08_15_9/1438467644-3097/tutorial/1335/objects/3/files/pic3_11.jpg
+На начальной стадии задаётся исходное состояние из нулевого вектора размером до 1600 бит. Затем производится операция xor фрагмента исходного сообщения $$P sub 0$$ с фрагментом исходного состояния размером $$r$$, оставшаяся часть состояния остаётся незатронутой. Результат обрабатывается функцией $$f$$, и так повторяется до исчерпания блоков исходного сообщения. 
+Функция $$f$$ выполняет перемешивание внутреннего состояния алгоритма. Состояние представляется в виде массива $$5×5$$, элементами которого являются 64-битные слова, инициализированные нулевыми битами. Функция $$f$$ выполняет 24 раунда, выход функции $$f$$ - хэш произвольной длины.
 
-SHA-1 является безопасным алгоритмом, поскольку в вычислительном отношении невозможно найти сообщение, которое соответствует данному дайджесу сообщения, или найти два разных сообщения, которые производят один и тот же дайджест.
-Любое изменение сообщения, с очень высокой вероятностью, приведет к изменению дайджеста сообщения.
+https://upload.wikimedia.org/wikipedia/commons/thumb/7/70/SpongeConstruction.svg/512px-SpongeConstruction.svg.png
 
----Сравнение MD5 и SHA-1:
-SHA-1 содержит больше шагов (80 вместо 64) и выполняется на 160-битном буфере по сравнению со 128-битным буфером MD5. Таким образом, SHA-1 должен выполняться приблизительно на 25% медленнее, чем MD5 на той же аппаратуре. Оба алгоритма просты и в описании, и в реализации, не требуют больших программ или подстановочных таблиц. Сравнение этих версий приведено в таблице:
+Keccak – стойкая хеш-функция. Сложность атаки на все 24 раунда в 2010 году составила $$2 sup 1590$$ и была улучшена в 2011 до $$2 sup 1579$$. 
 
-http://www.intuit.ru/EDI/02_08_15_9/1438467644-3097/tutorial/1335/objects/3/files/pic3_10.jpg
---Хэш-функции, основанные на блочных шифрах
+--3.2 Хэш-функции, основанные на блочных шифрах
 
 В качестве функции сжатия можно использовать блочный шифр с симметричными ключами, например трехкратный DES или AES. Рассмотрим несколько схем для построения сжимающей функции
 
----Сxема Рабина
-Сxема Рабина базируется на схеме Меркеля-Дамгарда. Функция сжатия заменяется любым алгоритмом шифрования. Блок сообщения используется как ключ; предварительно созданный дайджест используется как исходный текст. Зашифрованный текст - новый дайджест сообщения. Размер дайджеста совпадает с размером блочного шифра данных в основной криптографической системе.
+---3.2.1 Сxема Рабина
+Сxема Рабина базируется на схеме Меркеля-Дамгарда. Функция сжатия заменяется любым алгоритмом шифрования.  Входами функции сжатия являются блок сообщения  и выход предыдущего блока. Выход представляет собой дайджест сообщения. Иными словами дайджест сообщения $$M sub i$$ равен $$H sub i$$ = $$E(M sub i, H sub {i-1})$$. Хэш-значением всего сообщения является выход последнего блока. Размер дайджеста совпадает с размером блочного шифра данных в основной криптографической системе.
 
 http://www.intuit.ru/EDI/18_11_15_6/1447798956-19904/tutorial/577/objects/2/files/02_02.gif
 
----Схема Девиса-Мейера (Davies-Mayer)
-В отличии от схемы Рабина использует прямую связь для защиты от атаки "сведения в середину".
+---3.2.2 Схема Девиса-Мейера (Davies-Mayer)
+В схеме Девиса-Мейера, в отличии от схемы Рабина блок $$H sub i$$ и зашифрованый текст складываются с помощью XOR и создается новый блок $$H sub {i+1}$$.
 
 http://www.intuit.ru/EDI/18_11_15_6/1447798956-19904/tutorial/577/objects/2/files/02_03.gif
 
----Схема Матиса-Мейера-Осеаса (Metyas-Mayer-Oseas)
-Это версия схемы Девиса-Мейера: блоки сообщения применяются как ключи криптосистемы. Схема может быть использована, если блоки данных и ключ шифрования имеют один и тот же размер. AES хорошо подходит для этой цели.
-
-http://www.intuit.ru/EDI/18_11_15_6/1447798956-19904/tutorial/577/objects/2/files/02_04.gif
----Схема Миагучи-Пренеля (Miyaguchi–Preneel)
+---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
 
---Коллизия хэш-функций
-	Коллизия хэш-функций : Коллизией хэш-функций $$H$$ называется два различных входных блока данных $$X$$ и $$Y$$ таких, что $$ H(X) = H(Y)$$.
+---3.2.4 Криптогафическая хэш-функция Whirlpool
+	Whirlpool: криптографическая хеш-функция, разработанная Винсентом Риджменом и Пауло Баретто. Впервые опубликована в ноябре 2000 года. Осуществляет хэширование входного сообщения с длиной до 2256 бит. Ообрена европейской организацией NESSIE (New European Schemes for Signature, Integrity and Encryption - Новые европейские схемы подписей, целостности и шифрования).
+
+	С момента создания в 2000 году Whirlpool дважды подвергалась модификации. Первая версия, WHIRLPOOL-0, была представлена в качестве кандидата в проекте NESSIE в 2000 году.
+
+	Модификация WHIRLPOOL-0, названная WHIRLPOOL-T, в 2003 году была добавлена в перечень рекомендованных к использованию криптографических функций NESSIE. Изменения касались блока подстановки S-Box: в первой версии структура S-Box не была описана, и он генерировался совершенно произвольно. В новой версии S-Box приобрёл чёткую структуру.
+	В 2004 году был обнаружен  дефект в диффузных матрицах WHIRLPOOL-T [7] После его исправления была принята  конечная версия Whirlpool.
 
-	Коллизии существуют для большинства хэш-функций, но для криптографически стойких хэш-функций частота их возникновения минимальна. Если множество различных входных данных конечно, можно задать инъективную хэш-функцию, по определению не имеющую коллизий. Однако для хэш-функций, принимающих вход переменной длины и возвращающих хеш постоянной длины (таких как MD5), коллизии обязаны существовать, поскольку хотя бы для одного значения хэш-функции соответствующее ему множество входных данных будет бесконечно — и любые два набора данных из этого множества образуют коллизию.
+	В 2009 году был опубликован новый способ атаки на хеш-функции - The Rebound Attack [8].Удалось сгенерировать коллизию для 4.5 раундoв Whirlpool со сложностью 2120. Однако, данная атака не сильно повлияла на криптостойкость Whirlpool, сложность вычислений оказалась достаточно высока. На сегодняшний день  хеш-функция Whirlpool  устойчива ко всем видам криптоанализа. 
+Для построения Whirlpool используется структура Меркла - Дамгарда и  односторонняя функция сжатия Миагучи-Пренеля.
 
-Мерой криптостойкости хэш-функции является вычислительная сложность нахождения коллизии. В идеале не должно существовать способа отыскания коллизий более быстрого, чем полный перебор. Если для некоторой хэш-функции находится способ получения коллизий существенно более быстрый, чем полный перебор, то эта хэш-функция перестаёт считаться криптостойкой и использоваться для передачи и хранения секретной информации. 
-Литература
+-4. Заключение
 
- %R(
-
- %A Scott Contini 
- %A Ron Steinfeld
- %A Josef Pieprzyk 
- %A Krystian Matusiewicz
- %T A Critical Look at Cryptographic Hash Function Literature
- %I     New Jersey, USA : World Scientific Publishing
- %P 22
- %D 2008
- %U http://events.iaik.tugraz.at/HashWorkshop07/papers/Pieprzyk_CriticalLook.pdf
+Коллизии существуют для большинства хеш-функций, но для криптографически стойких хеш-функций частота их возникновения минимальна. Если для некоторой хеш-функции находится способ получения коллизий существенно более быстрый, чем полный перебор, то эта хеш-функция перестаёт считаться криптостойкой и использоваться для передачи и хранения секретной информации.
+В заключение отметим, большинство хеш-функций основывается на итеративных блочных шифрах, взлом шифра ведет к взлому хеш-алгоритма. Появление в 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
+
 
- %A Norman Matloff
- %T The Art of R Programming
- %D 2009
-
- %A Lipin B. R.
- %A Sitkarev G. A.
- %B AM&P Lab reports
- %T The Beginner's Guide to Art of Bad Code and Ugly Style
- %D 2015
- %R)
-
-Centre for Advanced Computing, Algorithms and Cryptograph
-y,
-Department of Computing, Macquarie University
-Hans Dobbertin. The Status of MD5 After a Recent Attack
-RFC 3174
 #КатегорияКриптография