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


'''Криптографической хэш-функцией''' называется всякая [[хэш-функция]], являющаяся [[криптостойкость|криптостойкой]], то есть, удовлетворяющая ряду специфичных требований.
== Постановка задачи ==
Хэш-функции,  долгое  время  использующиеся  в  компьютерных  науках, представляют собой функции, математические или иные, которые получают на вход строку переменной длины (называемую прообразом) и преобразуют ее в строку фиксированной, обычно меньшей, дли-
ны  (называемую  значением  хэш-функции).  В  качестве  простой  хэшфункции можно рассматривать функцию, которая получает прообраз и  возвращает байт, представляющий собой XOR всех входных байтов. Смысл  хэш-функции  состоит  в  получении  характерного  признака, 
прообраза-значения, по которому анализируются различные прообразы при решении обратной задачи. Так как обычно хэш-функция представляет собой соотношение "многие к одному", невозможно со всей деленностью сказать, что две строки совпадают, но их можно использовать, получая приемлемую оценку точности. Однонаправленная хэш-функция – это хэш-функция, которая работает  только  в  одном  направлении.  Легко  вычислить  значение  хэш-функции  по  прообразу,  но  трудно  создать  прообраз,  значение  хэш-функции  которого  равно  заданной  величине.  Упоминавшиеся  ранее хэш-функции,  вообще  говоря,  не  являются  однонаправленными:  задав конкретный  байт,  не  представляет  труда  создать  строку  байтов, XOR которых  дает  заданное  значение.  С  однонаправленной  хэш-функцией  такой  вариант  невозможен.  Хэш-функция  является  открытой,  тайны  ее расчета  не  существует.  Безопасность  однонаправленной  хэш-функции заключается  именно  в  ее  однонаправленности.  У  выхода  нет  видимой зависимости  от  входа.  Изменение  одного  бита  прообраза  приводит  к изменению (в среднем) половины битов значения хэш-функции, что известно также как лавинный эффект. Вычислительно  невозможно  найти  прообраз,  соответствующий  заданному значению хэш-функциию.

== Требования ==
Для того, чтобы хэш-функция <font style="font-size:130%;">''H''</font> считалась криптографически стойкой, она должна удовлетворять трем основным требованиям, на которых основано большинство применений хэш-функций в криптографии:
* ''Необратимость'' или ''стойкость к [[Атака нахождения прообраза|восстановлению прообраза]]'': для заданного значения хэш-функции <font style="font-size:130%">''m''</font> должно быть вычислительно невозможно найти блок данных <font style="font-size:130%">''X''</font>, для которого <font style="font-size:130%">''H(X)=m''</font>.
* Стойкость к ''[[коллизия хэш-функции|коллизиям]] первого рода'' или ''восстановлению вторых прообразов'': для заданного сообщения <font style="font-size:130%">''M''</font> должно быть вычислительно невозможно подобрать другое сообщение <font style="font-size:130%">''N''</font>, для которого <font style="font-size:130%">''H(N)=H(M)''</font>.
* Стойкость к ''коллизиям второго рода'': должно быть вычислительно невозможно подобрать пару сообщений <font style="font-size:130%">''(M, M')''</font>, имеющих одинаковый хэш.
Данные требования не являются независимыми:
* Обратимая функция нестойка к коллизиям первого и второго рода.
* Функция, нестойкая к коллизиям первого рода, нестойка к коллизиям второго рода; обратное неверно.

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

[[Атака «дней рождения»]] позволяет находить коллизии для хэш-функции с длиной значений <font style="font-size:130%">''n''</font> битов в среднем за примерно <font style="font-size:130%">''2<sup> n/2</sup>''</font> вычислений хэш-функции. Поэтому <font style="font-size:130%">''n''</font> – битная хэш-функция считается криптостойкой, если [[вычислительная сложность]] нахождения коллизий для неё близка к <font style="font-size:130%">''2<sup> n/2</sup>''</font>.

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

== Принципы построения ==
[[File:Итеративная последовательная схема.jpg|thumb|500px]]
=== Итеративная последовательная схема ===
В общем случае, в основе построения хэш-функции лежит итеративная последовательная схема. Ядром алгоритма является ''сжимающая функция'' — преобразование <font style="font-size:130%">''k''</font> входных в <font style="font-size:130%">''n''</font> выходных бит, где <font style="font-size:130%">''n''</font> — разрядность хэш-функции, а <font style="font-size:130%">''k''</font> — произвольное число большее <font style="font-size:130%">''n''</font>. При этом сжимающая функция должна удовлетворять всем условиям криптостойкости.

Входной поток разбивается на блоки по <font style="font-size:130%">''(k-n)''</font> бит. Алгоритм использует временную переменную размером в <font style="font-size:130%">''n''</font> бит, в качестве начального значения которой берется некое произвольное число. Каждый следующий блок данных объединяется с выходным значением сжимающей функции на предыдущей итерации. Значением хэш-функции являются выходные <font style="font-size:130%">''n''</font> бит последней итерации. Каждый бит выходного значения хэш-функции зависит от всего входного потока данных и начального значения. Таким образом достигается [[лавинный эффект]].

При проектировании хэш-функций на основе итеративной схемы возникает проблема с размером входного потока данных. Размер входного потока данных должен быть кратен <font style="font-size:130%">''(k-n)''</font>. Как правило, перед началом алгоритма данные расширяются неким, заранее известным, способом.

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

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

[[File:Обобщенная схема формирования хэш-фунции.jpg|thumb|400px|<font style="font-size:130%">''A''</font>, <font style="font-size:130%">''B''</font> и <font style="font-size:130%">''C''</font> могут принимать значения <font style="font-size:130%">''M<sub>j</sub>''</font> , <font style="font-size:130%">''H<sub>j-1</sub>''</font> , <font style="font-size:130%">''M<sub>j</sub>'' ⊕ ''H<sub>j-1</sub>''</font> или быть константой, где <font style="font-size:130%">''M<sub>j</sub>''</font> — <font style="font-size:130%">''j''</font> – ый блок входного потока, <font style="font-size:130%">⊕</font> — [[сложение по модулю 2]], <font style="font-size:130%">''H<sub>j</sub>''</font> — результат <font style="font-size:130%">''j''</font> – ой итерации.]]
Обычно при построении хэш-функции используют более сложную систему. Обобщенная схема симметричного блочного алгоритма шифрования изображена на рис.2

Таким образом, мы получаем 64 варианта построения сжимающей функции. Большинство из них являются либо тривиальными, либо небезопасными. Ниже изображены четыре наиболее безопасные схемы при всех видах атак.
[[File:Схемы безопасного хэширования.jpg|thumb|400px]]

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

== Применения ==

=== Электронная цифровая подпись ===
[[Алгоритмы ЭЦП|Электронная цифровая подпись]] (ЭЦП) - по сути шифрование сообщения алгоритмом с открытым ключом. Текст, зашифрованный секретным ключом, объединяется с исходным сообщением. Тогда проверка подписи — расшифрование открытым ключом, если получившийся текст аналогичен исходному тексту — подпись верна.

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

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

=== Проверка пароля ===
В большинстве случаев парольные фразы не хранятся на целевых объектах, хранятся лишь их хэш-значения. Xранение самих паролей нецелесообразно, так как в случае несанкционированного доступа к файлу с паролями злоумышленник получает их в открытом и сразу готовом к использованию виде, а при хранении хэш-значений он узнает лишь хэши, которые не обратимы в исходные данные.
В ходе процедуры [[Аутентификация|аутентификации]] вычисляется хэш-значение введённого пароля, и сравнивается с хранимым.

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

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

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

В [[CHAP|такой ситуации]] пароль не хранится открыто на сервере и, даже перехватив все сообщения между клиентом и сервером, криптоаналитик не может восстановить пароль, а передаваемое хэш-значение каждый раз разное.
== Случайный оракул ==
Напомним свойство перемешивания, которое присуще функции хэширования: при любом аргументе хэширование неотличимо с вычислительной точки зрения от строки битов, равномерно распределенных в области значений функции. Если заменить последнее выражение фразой "принадлежит генеральной совокупности равномерно распределенных величин", мы получим весьма мощную гипотетическую функцию, называемую случайный оракул (randome oracle). 
Он обладает тремя свойствами: детерминированность, эффективность, равномерность распределения результирующих значений. Однако,все известные вычислительные модели в той или иной степени не соответствуют модели случайного оракула.
Равномерность и детерминированность величин, вычисляемых случайным оракулом, означает, что энтропия его результатов выше, чем энтропия чисел, поступающих на вход. Поскольку свойства перемешивания, которым обладает хэш-функция является лишь предположением вычислительного характера, реальная хэш-функция должна обеспечивать лишь вычислительную неразличимость, то есть результаты должны иметь некое распределение вероятностей в области значений, которое невозможно определить за полиномиальное время. Итак, реальные функции хэширования лишь имитируют поведение случайного оракула, хоть и с высокой точностью.

== Атака на основе парадокса дней рождений ==
Предположим, что функция хэширования h действительно является случайным оракулом. В атаке по методу квадратного корня (атака на основе парадокса дней раждения) предполагается, что для обнаружения коллизий с ненулевой вероятностью достаточно выполнить 2 в степени |h|/2 случайных вычислений значения функции хэширования. Для организации атаки на основе парадокса дней рождений атакующий должен сгенерировать пары "сообщение-хэшированное значение", пока не обнаружаться два сообщения m и m`, удовлетворяющие условиям m не равно m`, h(m)=h(m`).
Такая пара сообщений называется коллизией(collision) функции хэширования h. Например, для функции хэшироания SHA-1 выполняется условие |h|=160, а значит его стойкость на основе парадокса дней рождения оценивается величиной 2<sup>80</sup>.

== Сравнительная характеристика наиболее известных функций ==
Существует длинный перечень криптографических хеш-функций, хотя многие из них были признаны уязвимыми и не должны быть использованы. Даже если хэш-функция никогда не была взломана, успешная атака против ослабленного варианта может подорвать доверие экспертов и привести к отказу от хэш-функции. Например, в августе 2004 года были найдены слаюости в ряде хэш-функций , которые были популярны в то время, в том числе SHA-0, RIPEMD и MD5. Это поставило под сомнение долгосрочную безопасность более поздних алгоритмов, которые являются производными от этих хеш-функций - в частности, SHA-1 ( усиленный вариант SHA-0 ), RIPEMD- 128 , и RIPEMD-160 (оба усиленные версии RIPEMD ). Ни SHA-0 , ни RIPEMD широко не используются, так как они были заменены на более усиленные версии.
По состоянию на 2009, двумя наиболее часто используемыми криптографическими хэш-функциями являются MD5 и SHA-1. Тем не менее, MD5 была взломана, атака против него была также использована для взлома SSL в 2008.
Функции SHA-0 и SHA-1 были разработаны в АНБ. В феврале 2005 года сообщалось, что проведена успешная атака на SHA-1, найдены коллизии за, примерно, 2<sup>69</sup> операций хэширования, а не в 2<sup>80</sup>, которые ожидаются  для 160-битной хэш-функции. В августе 2005 года сообщалось, об еще одном успешном нападении на SHA-1: нахождение коллизии за 2<sup>63</sup> операций. Новые приложения могут избежать этих проблем с безопасностью функции SHA-1 с  помощью более продвинутых членов семьи SHA , например, SHA-2.
Тем не менее, для обеспечения долгосрочной надежности приложений, использующих хэш-функций, был устроен конкурс на лучший проект - замену SHA-2. 2 октября 2012 года, Keccak был выбран в победителем в конкурсе, устроенном NIST. Версия этого алгоритма как ожидается, станет стандартным FIPS в 2014 году под названием SHA-3. 
Некоторые из следующих алгоритмов часто используется в приложениях криптографии.Обратите внимание, что этот список не включает кандидатов в текущем конкурсе NIST.

{| class="wikitable"
|-
! rowspan="2"|Алгоритм
! rowspan="2"|Размер выхода (bits)
! rowspan="2"|Размер внутреннего состояния(т.е. после применения функции сжатия)
! rowspan="2"|Размер блока
! rowspan="2"|Длина
! rowspan="2"|Размер слова
! rowspan="2"|Количество раундов
! colspan="3"|Атаки <br />(сложность:раунды)
|-
! [[Атака дней рождения]]
! [[Нахождение прообраза|Нахождение <br />второго прообраза]]
! [[Нахождение прообраза|Нахождение прообраза]]

|- style="text-align:center;"
| '''[[ГОСТ 34.11-45]]'''
| 256
| 256
| 256
| 256
| 32
| 256
| Yes (2<sup>105</sup>)
| Yes (2<sup>192</sup>])
| Yes (2<sup>192</sup>)

|- style="text-align:center;"
| '''[[HAVAL]]'''
| 256/224/192/160/128
| 256
| 1,024
| 64
| 32
| 160/128/96
| Yes
| No
| No

|- style="text-align:center;"
| MD2
| 128
| 384
| 128
| -
| 32
| 864
| Yes (2<sup>63.3</sup>])
| Yes (2<sup>73</sup>])
| Yes (2sup>73</sup>])

|- style="text-align:center;"
| '''[[MD4]]'''
| 128
| 128
| 512
| 64
| 32
| 48
| {{bad|Yes}} ([http://www.springerlink.com/content/v6526284mu858v37/ 3])
| {{bad|Yes}} ([http://eprint.iacr.org/2010/016.pdf 2<sup>64</sup>])
| {{bad|Yes}} ([http://eprint.iacr.org/2010/016.pdf 2<sup>78.4</sup>])

|- style="text-align:center;"
| '''[[MD5]]'''
| 128
| 128
| 512
| 64
| 32
| 64
| Yes (2<sup>20.96</sup>)
| Yes (2<sup>123.4</sup>)
| Yes (2<sup>123.4</sup>)

|- style="text-align:center;"
| '''[[PANAMA]]'''
| 256
| 8,736
| 256
| -
| 32
| -
| Yes
| No
| No

|- style="text-align:center;"
| '''[[RadioGatún]]'''
| Up to 608/1,216 (19 words)
| 58 words
| 3 words
| -
| 1–64
| -
| With flaws (2<sup>704</sup>)
| No
| No

|- style="text-align:center;"
| '''[[RIPEMD]]'''
| 128
| 128
| 512
| 64
| 32
| 48
| Yes (2<sup>18</sup>)
| No
| No

|- style="text-align:center;"
| '''[[RIPEMD|RIPEMD-128/256]]'''
| 128/256
| 128/256
| 512
| 64
| 32
| 64
| No
| No
| No

|- style="text-align:center;"
| '''[[RIPEMD|RIPEMD-160]]'''
| 160
| 160
| 512
| 64
| 32
| 80
| Да (2<sup>51</sup>)
| Нет
| Нет

|- style="text-align:center;"
| '''[[RIPEMD|RIPEMD-320]]'''
| 320
| 320
| 512
| 64
| 32
| 80
| {{good|No}}
| {{good|No}}
| {{good|No}}

|- style="text-align:center;"
| '''[[SHA-1|SHA-0]]'''
| 160
| 160
| 512
| 64
| 32
| 80
| Да (2<sup>33.6</sup>)
| Нет
| Нет

|- style="text-align:center;"
| '''[[SHA-1]]'''
| 160
| 160
| 512
| 64
| 32
| 80
| Да (2<sup>51</sup>)
| Нет
| Нет

|- style="text-align:center;"
| '''[[SHA-2|SHA-256/224]]'''
| 256/224
| 256
| 512
| 64
| 32
| 64
| Теоретически (28.5</sup>)
| Теоретически (2<sup>248.4</sup>)
| Теоретически (2<sup>248.4</sup>)

|- style="text-align:center;"
| '''[[SHA-2|SHA-512/384]]'''
| 512/384
| 512
| 1,024
| 128
| 64
| 80
| Теоретически 2(<sup>32.5</sup>)
| {{depends|Theoretical}}<ref group="c" name="second_preimage" /> <ref group="c" name="partial_rounds" /> ([http://eprint.iacr.org/2010/016.pdf 2<sup>494.6</sup>:42])
| {{depends|Theoretical}}<ref group="c" name="partial_rounds" /> ([http://eprint.iacr.org/2010/016.pdf 2<sup>494.6</sup>:42])

|- style="text-align:center;"
| '''[[SHA-3]]'''
| 224/256/384/512<ref group="c">Although the underlying algorithm [[Keccak]] has arbitrary hash lengths, the NIST specified 224, 256, 384 and 512 bits output as valid modes for SHA-3.</ref>
| 1600
| 1600-2*bits
| -
| 64
| 24
| {{good|No}}
| {{good|No}}
| {{good|No}}

|- style="text-align:center;"
| '''[[SHA-3]]'''-224
| 224
| 1600
| 1152
| -
| 64
| 24
| {{good|No}}
| {{good|No}}
| {{good|No}}

|- style="text-align:center;"
| '''[[SHA-3]]'''-256
| 256
| 1600
| 1088
| -
| 64
| 24
| {{good|No}}
| {{good|No}}
| {{good|No}}

|- style="text-align:center;"
| '''[[SHA-3]]'''-384
| 384
| 1600
| 832
| -
| 64
| 24
| {{good|No}}
| {{good|No}}
| {{good|No}}

|- style="text-align:center;"
| '''[[SHA-3]]'''-512
| 512
| 1600
| 576
| -
| 64
| 24
| {{good|No}}
| {{good|No}}
| {{good|No}}

|- style="text-align:center;"
| '''[[Tiger (cryptography)|Tiger(2)-192/160/128]]'''
| 192/160/128
| 192
| 512
| 64
| 64
| 24
| {{depends|Yes}}<ref group="c" name="partial_rounds" /> ([http://www.springerlink.com/content/u762587644802p38/ 2<sup>62</sup>:19])
| {{depends|Yes}}<ref group="c" name="second_preimage" /> ([http://eprint.iacr.org/2010/016.pdf 2<sup>184.3</sup>])
| {{bad|Yes}} ([http://eprint.iacr.org/2010/016.pdf 2<sup>184.3</sup>])

|- style="text-align:center;"
| '''[[WHIRLPOOL]]'''
| 512
| 512
| 512
| 256
| 8
| 10
| {{depends|Yes}}<ref group="c" name="partial_rounds" /> ([https://www.cosic.esat.kuleuven.be/fse2009/slides/2402_1150_Schlaeffer.pdf 2<sup>120</sup>:4.5])
| {{good|No}}
| {{good|No}}

|}

== Глоссарий ==

*[[Атака «дней рождения»]]
*[[Аутентификация]]
*[[Бит]]
*[[Атака нахождения прообраза|Восстановление прообраза]]
*[[Вычислительная сложность]]
*[[Ключи в криптографии]]
*[[Коллизия хэш-функции]]
*[[Криптостойкость]]
*[[Лавинный эффект]]
*[[Хэш-функция]]
*[[Алгоритмы ЭЦП|Электронная цифровая подпись]]

== Литература ==

<font style="font-size:145%">Составители</font>
<hr style="margin:-6px 0 5px 0"/>

'''Комаров А.И. / Митцель А.С.'''

<p style="text-align:center">'''[[ Оглавление|Назад к оглавлению ]]'''</p>