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

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

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

Типы безопасности хеш-функций [ править ]

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

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

Значение слова «жесткий» [ править ]

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

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

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

Регистр пароля [ править ]

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

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

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

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

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

Доказанно безопасные хэш-функции [ править ]

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

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

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

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

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

Серьезные проблемы [ править ]

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

Задача дискретного логарифма
Поиск модульных квадратных корней
Задача целочисленной факторизации
Задача суммы подмножества

Недостатки доказуемого подхода [ править ]

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

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

Пример (непрактичной) надежно защищенной хеш-функции [ править ]

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

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

Более практичные хеш-функции с доказанной безопасностью [ править ]

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

Ссылки [ править ]

^ Гудин, Дэн (2012-12-10). «Кластер на 25 GPU взламывает каждый стандартный пароль Windows менее чем за 6 часов» . Ars Technica . Проверено 23 ноября 2020 .
^ http://eprint.iacr.org/2008/469.pdf
^ Petit, C .; Quisquater, J.-J .; Тиллих, Ж.-П., «Жесткие и простые компоненты поиска коллизий в хэш-функции Земора-Тиллиха: новые атаки и сокращенные варианты с эквивалентной безопасностью» (PDF) , Отсутствует или пусто |title=( справка )

[1] Гудин, Дэн (2012-12-10). «Кластер на 25 GPU взламывает каждый стандартный пароль Windows менее чем за 6 часов» . Ars Technica . Проверено 23 ноября 2020 .

[2] ttp://eprint.iacr.org/2008/469.pdf

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

[1]