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

Ответ 1

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

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

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

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

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

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

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

EDIT: Как работают большинство криптографических хеш-функций?

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

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

Ответ 2

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

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

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

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

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

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

Ответ 4

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

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

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

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

Ответ 5

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

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

Итак,

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

Понятно, что вы не можете восстановить SAUCE из своего кодирующего SE (при условии, что наш диапазон возможных входов - это все 5-буквенные слова). Слово могло так же легко быть SPACE.

В стороне, тот факт, что SAUCE и SPACE производят SE как кодирование, называется столкновением, и вы можете видеть, что X-ecoding не будет очень хорошим хешем.:)

Ответ 6

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

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

Теперь MD5 не справляется с этим, поскольку столкновений для этой функции можно найти. С точки зрения криптографа MD5 - это функция повернутого шифрования. Обработка одного блока сообщений М (512 бит) использует входное состояние V (128-битное значение) и вычисляет новое состояние V 'как V' = V + E (M, V), где '+' является слово- а "E" - симметричная функция шифрования (также называемая "блочным шифрованием" ), которая использует M как ключ и V в качестве зашифрованного сообщения. С более пристального взгляда E can - своего рода "расширенная сеть Файстеля", аналогичная блочному шифру DES, с четырьмя четвертями вместо двух половинок. Подробности здесь не важны; моя точка зрения заключается в том, что то, что делает "хорошую" хэш-функцию, среди хеш-функций, которые используют эту структуру (так называемый "Merkle-Damgård" ), похоже на то, что делает блочный шифр "безопасным". Успешные атаки на столкновение с 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) являются функциями Merkle-Damgård, но многие из потенциальных преемников нет. Существует постоянный конкурс, организованный NIST (федеральная организация США, которая занимается такими вещами), чтобы выбрать новую стандартную хеш-функцию, получившую название "SHA-3". Подробнее см. эту страницу. В настоящее время они составляют до 14 кандидатов от первоначальной 51 (не считая дюжины дополнительных, которые не прошли административный тест на отправку полного представления с кодом, который компилируется и работает должным образом).

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

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

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

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

Ответ 7

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

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

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

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

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

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