Как работают односторонние хеш-функции?(Отредактировано)

https://stackoverflow.com/questions/2112685

22-09-2019
|

Вопрос

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

Может ли кто-нибудь объяснить тому, кто очень мало разбирается в криптографии, как это работает?Какая часть функции делает ее односторонней?

Решение

Поскольку все до сих пор просто определяли, что такое хеш-функция, я укушу.

Односторонняя функция — это не просто хэш-функция (функция, которая теряет информацию), а функция, f для чего, учитывая изображение y («SE» или 294 в существующих ответах), трудно найти прообраз x такой, что f(x)=y.

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

Ни одна из обычных хеш-функций, предложенных до сих пор в существующих ответах, не обладает этим свойством.Ни одна из них не является односторонней криптографической хэш-функцией.Например, учитывая «SE», вы можете легко получить входные данные «SXXXE», входные данные со свойством, которое X-encode(»SXXXE»)=SE.

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

SHA-1 и MD5 раньше были популярными односторонними функциями, но обе они почти сломаны (специалисты знают, как создавать предварительные изображения для заданных изображений, или почти умеют это делать).Сейчас проводится конкурс по выбору нового стандарта, который получит название ША-3.

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

РЕДАКТИРОВАТЬ:Как работают большинство криптографических хеш-функций?

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

Возьмем пример моток, один из сильных кандидатов для контекста SHA-3.Его основная функция повторяется 72 раза.Единственное количество итераций, для которых создатели функции умеют иногда соотносить выходы с некоторыми входами, — 25.Говорят, у него «коэффициент безопасности» 2,9.

Другие советы

Подумайте о самом простом хеше: для входной строки нужно вернуть сумму значений ASCII каждого символа.

hash( 'abc' ) = ascii('a')+ascii('b')+ascii('c')
              = 97 + 98 + 99
              = 294

Теперь, зная хэш-значение 294, можете ли вы сказать, какой была исходная строка?Очевидно, нет, потому что «abc» и «cba» (и многие другие) дают одно и то же значение хеш-функции.

Криптографические хеш-функции работают таким же образом, за исключением того, что алгоритм, очевидно, намного сложнее.Коллизии будут всегда, но если вы знаете строку s хеширует h, то должно быть очень сложно («вычислительно неосуществимо») построить другая строка, которая также хешируется h.

Здесь вместо сложного объяснения нужна простая аналогия.

Для начала давайте разобьем тему на две части: односторонние операции и хеширование.Что такое односторонняя операция и зачем она вам нужна?

Односторонние операции называются так потому, что они необратимы.Большинство типичных операций, таких как сложение и умножение, можно обратить вспять, тогда как деление по модулю нельзя повернуть вспять.Почему это важно?Потому что вы хотите предоставить выходное значение, которое 1) трудно продублировать без исходных входных данных и 2) не дает возможности определить входные данные из выходных данных.

Двусторонний

Добавление:

4 + 3 = 7

Это можно изменить, взяв сумму и вычитая одно из слагаемых.

7 - 3 = 4

Умножение:

4 * 5 = 20

Это можно изменить, взяв произведение и разделив его на один из коэффициентов.

20 / 4 = 5

Не обратимый

Деление по модулю:

22 % 7 = 1

Это нельзя обратить вспять, поскольку с частным и делимым нельзя выполнить операцию, чтобы восстановить делитель (или наоборот).

Можете ли вы найти операцию, чтобы заполнить, где "?" является?

1  ?  7 = 22  
1  ?  22 = 7

При этом односторонние хеш-функции имеют то же математическое качество, что и деление по модулю.

Почему это важно?

Допустим, я дал вам ключ от шкафчика на автовокзале, где есть тысяча шкафчиков, и попросил вас доставить его моему банкиру.Будучи умным парнем, не говоря уже о подозрительности, вы бы сразу посмотрели на ключ, чтобы увидеть, какой номер шкафчика написан на ключе.Зная это, я совершил несколько коварных поступков;сначала я нашел два числа, которые при делении по модулю дают мне число в диапазоне от 1 до 1000, во-вторых, я стер исходное число и написал на нем делитель пары чисел, во-вторых, я выбрал автовокзал, на котором есть охранник, защищающий шкафчики от злоумышленников, позволяя людям проверять ключом только один шкафчик в день, в-третьих, банкир уже знает дивиденды, поэтому, когда он получит ключ, он сможет посчитать, вычислить остаток и узнать, какой шкафчик открыть.

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

Итак, теперь я могу «доверить» вам доставку ключа его законному владельцу, не беспокоясь о том, что вы легко догадаетесь, какому шкафчику он принадлежит.Конечно, вы могли бы перебором обыскать все шкафчики, но это заняло бы почти 3 года, а у моего банкира достаточно времени, чтобы использовать ключ и опорожнить шкафчик.

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

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

int SimpleHash(file) {
    return 0 if file.length is even;
    return 1 if file.length is odd;
}

Теперь вот тест. SimpleHash(specialFile) равен 0. Каким был мой исходный файл?

Очевидно, что узнать это невозможно (хотя вы, скорее всего, довольно легко обнаружите, что мой хэш основан на длине файла).Невозможно «восстановить» мой файл на основе хеша, поскольку хеш не содержит всего, что сделал мой файл.

Хэш — это (очень) кодирование с потерями.

Чтобы дать вам более простой пример, представьте себе фиктивную двухбуквенную кодировку пятибуквенного слова, называемую X-кодировкой.Алгоритм X-кодирования прост:возьмите первую и последнюю буквы слова.

Так,

X-encode( SAUCE ) = SE
X-encode( BLOCK ) = BK

Очевидно, что вы не можете восстановить SAUCE по его кодировке SE (при условии, что наш диапазон возможных входных данных - все 5-буквенные слова).С таким же успехом это слово могло бы быть ПРОСТРАНСТВОМ.

Кстати, тот факт, что SAUCE и SPACE создают SE в качестве кодировки, называется столкновение, и вы можете видеть, что X-кодирование не дает очень хорошего хэша.:)

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

Видеть MD5 например.Он обрабатывает входные данные блоками по 512 бит.Каждый блок разбит на 16 32-битных слов.Всего 64 шага, каждый из которых использует одно из 16 входных слов.Таким образом, каждое слово используется четыре раза в ходе алгоритма.Отсюда и односторонность:любой входной бит вводится в нескольких местах, и между двумя такими входами функция смешивает все текущие данные вместе, так что каждый входной бит влияет на большую часть 128-битного рабочего состояния.Это не позволяет вам инвертировать функцию или вычислить коллизию, просматривая только часть данных.Вам придется просмотреть все 128 бит, а пространство 128-битных блоков слишком велико, чтобы его можно было эффективно пройти.

Теперь MD5 не справляется с этой задачей, поскольку для этой функции можно найти коллизии.С точки зрения криптографа, MD5 — это функция ротационного шифрования.Обработка одного блока сообщения M (512 бит) использует входное состояние V (128-битное значение) и вычисляет новое состояние V' как V' = V + E(M, V), где «+» — это слово. мудрое дополнение, и «E» — это функция симметричного шифрования (также известная как «блочный шифр»), которая использует M в качестве ключа и V в качестве сообщения, которое нужно зашифровать.Если присмотреться, E can представляет собой своего рода «расширенную сеть Фейстеля», похожую на блочный шифр DES, с четырьмя четвертями вместо двух половин.Детали здесь не важны;Я хочу сказать, что то, что делает «хорошую» хеш-функцию среди хеш-функций, использующих эту структуру (называемую «Меркле-Дамгордом»), аналогично тому, что делает блочный шифр «безопасным».Успешные коллизионные атаки на MD5 используют дифференциальный криптоанализ — инструмент, который был разработан в первую очередь для атаки на блочные шифры.

От хорошего блочного шифра к хорошей хэш-функции есть шаг, который нельзя игнорировать.При использовании структуры Меркла-Дамгорда хеш-функция безопасна, если базовый блочный шифр устойчив к «атакам со связанными ключами» — довольно неясному свойству, против которого блочные шифры редко усиливаются, поскольку для симметричного шифрования атаки со связанными ключами практически не имеют практического применения. влияние.Например, шифрование AES оказалось не настолько устойчивым к атакам с использованием связанных ключей, как хотелось бы, и это не вызвало всеобщей паники.Это сопротивление не входило в число тех свойств, которые искались при разработке AES.Это просто предотвращает превращение AES в хеш-функцию.Существует хеш-функция под названием Whirlpool, которая основана на производной от Rijndael, где «Rijndael» — первоначальное имя того, что стало AES;но Whirlpool заботится о том, чтобы изменить те части Rijndael, которые уязвимы к соответствующим ключевым атакам.

Кроме того, существуют и другие структуры, которые можно использовать для построения хэш-функции.Текущие стандартные функции (MD5, SHA-1 и семейство «SHA-2», также известные как SHA-224, SHA-256, SHA-384 и SHA-512) являются функциями Меркла-Дамгорда, но многие из потенциальных преемников нет.NIST (федеральная организация США, занимающаяся подобными вещами) постоянно проводит конкурс на выбор новой стандартной хэш-функции, получившей название «SHA-3».Видеть эта страница для получения подробной информации.На данный момент у них осталось 14 кандидатов из первоначальных 51 (не считая дюжины дополнительных, которые не прошли административную проверку по отправке полного представления с кодом, который компилируется и работает правильно).

Давайте теперь посмотрим более концептуально.Безопасная хэш-функция должна выглядеть как случайный оракул:Оракул — это черный ящик, в который при получении сообщения М в качестве входных данных выводит ответ ч(М) который выбирается случайным образом, равномерно в выходном пространстве (т.е.все н-битовые строки, если длина вывода хэш-функции равна н).Если получить то же сообщение М снова в качестве входных данных оракул выводит то же значение, что и раньше.Помимо этого ограничения, вывод оракула на ранее не использовавшийся вход М непредсказуем.Можно представить оракула как контейнер для гнома, который бросает кости и тщательно записывает входные сообщения и соответствующие выходные данные в большую книгу, чтобы выполнить свой контракт оракула.Невозможно предсказать, каким будет следующий результат, поскольку сам гном этого не знает.

Если существует случайный оракул, то инвертирование хэш-функции требует затрат 2^n:Чтобы получить заданный результат, нет лучшей стратегии, чем использование отдельных входных сообщений до тех пор, пока не будет получено ожидаемое значение.Благодаря равномерному случайному выбору вероятность успеха равна 1/(2^n) при каждой попытке, а среднее количество запросов к гному, бросающему кости, будет 2^n.Для коллизий (поиск двух разных входных данных, которые дают одно и то же значение хеш-функции) стоимость составляет около *1,4*2^(n/2)* (грубо говоря, с выходными данными *1,4*2^(n/2)* мы можем собраться вокруг 2^n пары выходных данных, каждый из которых имеет вероятность 1/(2^n) соответствия, т.е.наличие двух разных входов, которые имеют одинаковый выход).Это лучшее, что можно сделать с помощью случайного оракула.

Поэтому мы ищем хеш-функции, которые не хуже случайного оракула:они должны смешивать входные данные таким образом, чтобы мы не могли найти коллизию более эффективно, чем то, чего стоило бы просто вызвать функцию 2^(п/2) раз.Проклятие хэш-функции — это математическая структура, т.е.ярлыки, позволяющие злоумышленнику просмотреть внутреннее состояние хеш-функции (которое, по крайней мере, большое). н биты) как вариация математического объекта, живущего в гораздо более коротком пространстве.30 лет общественных исследований систем симметричного шифрования породили целый набор понятий и инструментов (диффузия, лавина, дифференциалы, линейность...), которые можно применять.Однако суть в том, что у нас нет доказательств того, что случайный оракул действительно может существовать.Мы хотеть хеш-функция, которую невозможно атаковать.Что мы иметь являются кандидатами на хэш-функции, для которых в настоящее время не проводится атака известен, и, что несколько лучше, у нас есть функции, для которых некоторый можно доказать, что виды атак не работают.

Предстоит еще провести некоторые исследования.

множество
Если присмотреться, ассоциативные массивы очень похожи на хеши.Основными отличиями было отсутствие символа % в именах хешей и то, что им можно было назначить только один ключ за раз.Таким образом, можно было бы сказать $foo{'key'} = 1;, но только @keys = keys(foo);.Знакомые функции, такие какeach, ключи и значения, работали так же, как и сейчас (а в Perl 2 было добавлено удаление).

В Perl 3 было целых три типа данных:он имел символ % на именах хэшей, позволял назначать весь хэш сразу и добавлял dbmopen (теперь устаревший в пользу галстука).В Perl 4 использовались хеш-ключи, разделенные запятыми, для эмуляции многомерных массивов (которые теперь лучше обрабатываются с помощью ссылок на массивы).

Perl 5 совершил гигантский скачок, назвав ассоциативные массивы хэшами.(Насколько мне известно, это первый язык, в котором структура данных упоминается таким образом, а не «хэш-таблица» или что-то подобное.) По иронии судьбы, он также перенес соответствующий код из hash.c в hv.c.

Номенклатура
Словари, как объяснялось ранее, представляют собой неупорядоченные коллекции значений, индексированные уникальными ключами.Их иногда называют ассоциативными массивами или картами.Их можно реализовать несколькими способами, один из которых — использование структуры данных, известной как хеш-таблица (и это то, что Perl называет хешем).

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

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow