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

Question

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

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

Answer 1

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

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

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

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

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

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

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

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

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

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

Answer 2

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

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

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

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

Answer 3

Съемка для простой аналогии здесь вместо сложного объяснения.

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

Односторонние операции называются так, потому что они необратимы. Наиболее типичные операции, такие как сложение и умножение, могут быть обращены вспять, в то время как деление по модулю не может быть обращено вспять. Почему это важно? Поскольку вы хотите предоставить выходное значение, которое 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 года, достаточно времени, чтобы мой банкир использовал ключ и опустошил шкафчик.

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

Answer 4

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

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

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

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

Answer 5

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

См., Например, 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 с использованием столкновений используют дифференциальный криптоанализ, инструмент, который был разработан для атаки на блочные шифры.

От хорошего блочного шифра до хорошей хеш-функции есть шаг, который нельзя сбрасывать со счетов. Со структурой Merkle-Damgård хеш-функция является безопасной, если базовый блочный шифр устойчив к «атакам по связанному ключу», довольно неясное свойство, против которого блочные шифры редко укрепляются, потому что для симметричного шифрования атаки по ключевым ключам практически не имеют практического влияние. Например, шифрование 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 (не считая дюжины дополнительных, которые не прошли административную проверку отправки полной заявки с кодом, который компилируется и выполняется правильно).

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

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

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

Еще предстоит кое-какое исследование.

Answer 6

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

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

Итак,

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

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

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

Answer 7

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

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

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

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

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

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