Безопасность криптографических хэш-функций

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

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

Виды безопасности хеш-функций

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

Сопротивление прообразу : с учетом хеша $h$ должно быть трудно найти какое-либо сообщение $m$ такой, что $h=hash(m)$ . Это понятие связано с понятием односторонней функции . Функции, у которых отсутствует это свойство, уязвимы для атак на прообраз .
Второе сопротивление прообразу : учитывая ввод $m_{1}$ , должно быть трудно найти другой вход, $m_{2}$ (не равно $m_{1}$ ) такой, что $hash(m_{1})=hash(m_{2})$ . Это свойство иногда называют слабым сопротивлением столкновению. Функции, у которых отсутствует это свойство, уязвимы для атак второго прообраза .
Устойчивость к столкновениям : должно быть сложно найти два разных сообщения. $m_{1}$ и $m_{2}$ такой, что $hash(m_{1})=hash(m_{2})$ . Такая пара называется (криптографической) коллизией хешей. Это свойство иногда называют сильным сопротивлением столкновению. Для этого требуется хэш-значение как минимум в два раза длиннее, чем требуется для сопротивления прообразу, в противном случае коллизии могут быть обнаружены с помощью атаки на день рождения .
Псевдослучайность : должно быть сложно отличить генератор псевдослучайных чисел, основанный на хеш-функции, от генератора случайных чисел, например, он проходит обычные тесты на случайность .

Значение слова «жесткий»

Основной вопрос заключается в значении слова « жесткий ». Есть два подхода к ответу на этот вопрос. Во-первых, это интуитивный/практический подход: «жесткий» означает, что он почти наверняка недосягаем для любого противника, которому необходимо не допустить взлома системы до тех пор, пока безопасность системы считается важной».

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

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

Случай пароля

Кроме того, если набор входных данных для хеша относительно невелик или каким-то образом упорядочен по вероятности, то поиск методом перебора может оказаться практичным, независимо от теоретической безопасности. Вероятность восстановления прообраза зависит от размера входного набора и скорости или стоимости вычисления хеш-функции. Типичным примером является использование хешей для хранения данных проверки пароля . Вместо того, чтобы хранить открытый текст паролей пользователей, система контроля доступа обычно хранит хэш пароля. Когда человек запрашивает доступ, отправленный им пароль хешируется и сравнивается с сохраненным значением. Если сохраненные данные проверки будут украдены, у вора будут только хеш-значения, а не пароли. Однако большинство пользователей выбирают пароли предсказуемым образом, и часто пароли достаточно короткие, чтобы можно было протестировать все возможные комбинации при использовании быстрых хэшей. ^[1] специальные хеши, называемые функциями получения ключей Для замедления поиска были созданы . См. раздел «Взлом пароля» .

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

Большинство хэш-функций строятся по принципу ad hoc, когда биты сообщения тщательно смешиваются для получения хеша. Различные побитовые операции (например, повороты), модульные сложения и функции сжатия используются в итеративном режиме для обеспечения высокой сложности и псевдослучайности выходных данных. Таким образом, безопасность очень трудно доказать, и доказательство обычно не проводится. Всего несколько лет назад было показано, что одна из самых популярных хеш-функций, SHA-1 , менее безопасна, чем предполагает ее длина: коллизии можно было обнаружить только в двух ⁵¹^[2] тесты, а не перебор числа 2 ⁸⁰.

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

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

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

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

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

Это означает, что если бы обнаружение коллизий было бы осуществимо за полиномиальное время с помощью алгоритма A, мы могли бы найти и использовать алгоритм R (алгоритм редукции) с полиномиальным временем, который бы использовал алгоритм A для решения проблемы P, которая, как многие полагают, неразрешима за полиномиальное время. Это противоречие. Это означает, что поиск столкновений не может быть проще, чем решение P.

Однако это указывает лишь на то, что обнаружение коллизий затруднено в «некоторых» случаях, поскольку не все случаи вычислительно сложных задач обычно сложны. Действительно, очень большие случаи NP-сложных задач обычно решаются, в то время как только самые сложные практически невозможно решить.

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

Сложные проблемы

Примеры задач, которые предположительно неразрешимы за полиномиальное время

Недостатки доказуемого подхода

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

SWIFFT — это пример хеш-функции, которая позволяет обойти эти проблемы безопасности. Можно показать, что для любого алгоритма, который может взломать SWIFFT с вероятностью P за расчетное время T, мы можем найти алгоритм, который решает наихудший сценарий определенной сложной математической задачи за время T', в зависимости от T и P. ^{[ нужна ссылка ]}

Пример (непрактичной) доказуемо безопасной хэш-функции

Хэш( м ) = х ^м mod n , где n сложно факторизовать составное число, а x — некоторое заранее заданное базовое значение. Столкновение х ^м1 соответствующий х ^м2 обнаруживает кратное m1-m2 порядка x . Такую информацию можно использовать для факторизации n за полиномиальное время, предполагая определенные свойства x .

Но алгоритм совершенно неэффективен, поскольку он требует в среднем 1,5 умножения по модулю n на бит сообщения.

Более практичные доказуемо безопасные хэш-функции

VSH — Very Smooth Hash function — доказуемо безопасная, устойчивая к коллизиям хэш-функция, предполагающая сложность нахождения нетривиальных модульных квадратных корней по модулю составного числа. $n$ (доказано, что это так же сложно, как факторинг $n$ ).
МуХАШ
ECOH — хеш-функция только для эллиптических кривых — основана на концепции эллиптических кривых, проблеме суммы подмножеств и суммировании полиномов. Доказательство безопасности сопротивления столкновению было основано на ослабленных предположениях, и в конечном итоге была обнаружена вторая атака на прообраз.
FSB — хэш-функция на основе быстрого синдрома — можно доказать, что взломать FSB по крайней мере так же сложно, как решить определенную NP-полную задачу, известную как декодирование регулярного синдрома.
SWIFFT - SWIFFT основан на быстром преобразовании Фурье и доказуемо устойчив к коллизиям при относительно мягком предположении о сложности наихудшего случая поиска коротких векторов в циклических/ идеальных решетках .
Хэш-функция Чаума, ван Хейста, Пфитцмана — функция сжатия, в которой обнаружение коллизий так же сложно, как решение задачи дискретного логарифмирования в конечной группе. $F_{2p+1}$ .
Хэш-функции на основе рюкзака — семейство хэш-функций, основанное на задаче о рюкзаке .
Хэш-функция Земора-Тиллиха — семейство хеш-функций, основанных на арифметике группы матриц SL2 . Найти коллизии по крайней мере так же сложно, как найти факторизацию определенных элементов в этой группе. Это должно быть сложно, по крайней мере, PSPACE-полным . ^{[ сомнительно – обсудить ]} Для этого хеша в итоге была обнаружена атака с временной сложностью, близкой к $2^{n/2}$ . Это, безусловно, превосходит привязанность к дню рождения и идеальные сложности прообраза, которые $2^{3n/2}$ и $2^{3n}$ для хеш-функции Земора-Тиллиха. Поскольку атаки включают в себя поиск дней рождения в уменьшенном наборе размеров $2n$ они действительно не разрушают идею доказуемой безопасности и не делают схему недействительной, а скорее предполагают, что первоначальные параметры были слишком малы. ^[3]
Хэш-функции из сигма-протоколов — существует общий способ создания доказуемо безопасного хеша, в частности, из любого (подходящего) сигма-протокола . более быструю версию VSH (называемую VSH*). Таким способом можно получить

Ссылки

^ Гудин, Дэн (10 декабря 2012 г.). «Кластер из 25 графических процессоров взламывает любой стандартный пароль Windows менее чем за 6 часов» . Арс Техника . Проверено 23 ноября 2020 г.
^ http://eprint.iacr.org/2008/469.pdf ^{[ пустой URL PDF ]}
^ Пети, К.; Кискатер, Ж.-Ж.; Тиллих, Ж.-П., «Сложные и простые компоненты поиска коллизий в хеш-функции Земора-Тиллиха: новые атаки и сокращенные варианты с эквивалентной безопасностью» (PDF) , {{citation}}: Отсутствует или пусто |title= ( помощь )

[1] Гудин, Дэн (10 декабря 2012 г.). «Кластер из 25 графических процессоров взламывает любой стандартный пароль Windows менее чем за 6 часов» . Арс Техника . Проверено 23 ноября 2020 г.

[2] ttp://eprint.iacr.org/2008/469.pdf ^{[ пустой URL PDF ]}

[3] Пети, К.; Кискатер, Ж.-Ж.; Тиллих, Ж.-П., «Сложные и простые компоненты поиска коллизий в хеш-функции Земора-Тиллиха: новые атаки и сокращенные варианты с эквивалентной безопасностью» (PDF) , {{citation}}: Отсутствует или пусто |title= ( помощь )

[1]

[2]

[3]