Как работают односторонние хеш-функции?
Я прочитал статью в Википедии о хэшах md5, но до сих пор не могу понять, как хеш не может быть "восстановлен" обратно в исходный текст.
Может ли кто-нибудь объяснить кому-то, кто очень мало знает о криптографии, как это работает? Какая часть функции делает его односторонним?
7 ответов
Поскольку все до сих пор просто определили, что такое хэш-функция, я буду кусаться.
Односторонняя функция - это не просто хеш-функция - функция, которая теряет информацию - но функция f для которого дано изображение y ("SE" или 294 в существующих ответах), трудно найти предварительное изображение x, такое что f(x)=y,
Вот почему они называются односторонними: вы можете вычислить изображение, но не можете найти предварительное изображение для данного изображения.
Ни одна из обычных хеш-функций, предложенных до сих пор в существующих ответах, не обладает этим свойством. Ни одна из них не является односторонней криптографической хеш-функцией. Например, учитывая "SE", вы можете легко выбрать вход "SXXXE", вход со свойством, которое X-encode("SXXXE")=SE.
Здесь нет "простых" односторонних функций. Они должны смешивать свои входы так хорошо, что вы не только не будете полностью распознавать вход на выходе, но и другой вход.
Раньше SHA-1 и MD5 были популярными односторонними функциями, но они почти сломаны (специалист знает, как создавать предварительные изображения для заданных изображений, или почти способен это сделать). Идет конкурс по выбору нового стандарта, который будет называться SHA-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. Каким был мой оригинальный файл?
Очевидно, что нет никакого способа узнать (хотя вы, вероятно, довольно легко обнаружите, что мой хэш основан на длине файла). Невозможно "восстановить" мой файл на основе хэша, потому что хэш не содержит всего, что сделал мой файл.
Проще говоря, хеш-функция работает, создавая большой запутанный беспорядок входных данных.
Смотри 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 (не считая дюжины дополнительных, которые не прошли административный тест на отправку полного представления с кодом, который компилируется и работает правильно).
Давайте теперь посмотрим более концептуально. Безопасная хеш-функция должна выглядеть как случайный оракул: оракул - это черный ящик, который при получении сообщения М в качестве входного сигнала выдает ответ 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 лет публичных исследований симметричных систем шифрования позволили создать целый ряд понятий и инструментов (диффузия, лавина, дифференциалы, линейность...), которые можно применять. Суть, однако, в том, что у нас нет доказательств того, что случайный оракул действительно может существовать. Нам нужна хеш-функция, которую нельзя атаковать. У нас есть кандидаты в хеш-функции, для которых в настоящее время не известно ни одной атаки, и, что еще лучше, у нас есть некоторые функции, для которых можно доказать, что некоторые виды атак не работают.
Еще предстоит провести некоторые исследования.
Хеш - это (очень) кодировка с потерями.
Чтобы дать вам более простой пример, представьте вымышленную двухбуквенную кодировку пятибуквенного слова, называемую X-кодировкой. Алгоритм X-кодирования прост: взять первые и последние буквы слова.
Так,
X-encode( SAUCE ) = SE
X-encode( BLOCK ) = BK
Ясно, что вы не можете восстановить SAUCE из его кодировки SE (предполагая, что наш диапазон возможных вводов - все 5-буквенные слова). Слово может так же легко быть ПРОСТРАНСТВОМ.
Кроме того, тот факт, что SAUCE и SPACE создают SE в качестве кодировки, называется коллизией, и вы можете видеть, что X-ecoding не создаст очень хороший хеш.:)
Массив
С некоторыми косящимися ассоциативные массивы очень похожи на хэши. Основным отличием было отсутствие символа% на именах хэшей, и то, что им можно было назначить только одну клавишу за раз. Таким образом, можно сказать, $foo{'key'} = 1;, но только @keys = keys(foo);, Знакомые функции, такие как каждая, ключи и значения, работали так же, как и сейчас (и удаление было добавлено в Perl 2).
В Perl 3 было три целых типа данных: он имел символ% в именах хэшей, позволял сразу назначать целый хэш и добавил dbmopen (теперь не рекомендуется в пользу tie). Perl 4 использовал разделенные запятыми хеш-ключи для эмуляции многомерных массивов (которые теперь лучше обрабатываются ссылками на массивы).
Perl 5 сделал гигантский скачок, ссылаясь на ассоциативные массивы как хеши. (Насколько я знаю, это первый язык, который ссылается на структуру данных таким образом, а не на "хеш-таблицу" или что-то подобное.) По иронии судьбы он также переместил соответствующий код из hash.c в hv.c.
Номенклатура
Словари, как объяснялось ранее, представляют собой неупорядоченные наборы значений, индексируемых уникальными ключами. Их иногда называют ассоциативными массивами или картами. Они могут быть реализованы несколькими способами, одним из которых является использование структуры данных, известной как хеш-таблица (и это то, что Perl называет хеш-таблицей).
Использование в Perl термина "хэш" является источником некоторой потенциальной путаницы, поскольку выходные данные хэш-функции также иногда называют хеш-кодом (особенно в криптографических контекстах), а также потому, что хеш-таблицы обычно нигде не называются хеш-кодами.
Чтобы быть в безопасности, обращайтесь к структуре данных как к хеш-таблице и используйте термин "хеш" только в очевидных, специфичных для Perl контекстах.