Как односторонние хэш-функции работают? (Отредактированный)
Я прочитал статью Wikipedia о хешах md5, но я все еще не могу понять, как хеш не может быть "воссоздан" назад к оригинальному тексту.
Кто-то мог объяснить кому-то, кто знает очень мало о криптографии, как это работает? Какая часть функции делает это односторонним?
6 ответов
Так как все до сих пор просто определили, что такое хеш-функция, я укусу.
Функция односторонней стороны - это не просто функция хеша - функция, которая теряет информацию - но функция f , для которой, с учетом изображения y («SE» Или 294 в существующих ответах) трудно найти предварительное изображение X такое, что f (x) = y .
Вот почему они называются односторонним: вы можете вычислить изображение, но вы не можете найти предварительное изображение для данного изображения.
Ни одна из обычной хэш-функции, предложенной до сих пор в существующих ответах, у этого свойства. Никто из них не является односторонним криптографическим хеш-функциями. Например, данный «SE», вы можете легко подобрать вход «SXXXE», вход с свойством, которое X-encode («SXXXE») = SE.
Нет «простых» односторонних функций. Они должны смешивать их входы так хорошо, что не только вы не распознаете вход вообще в выходе , но , а Вы также не распознаете другой вход.
SHA-1 и MD5 раньше были популярными функциями односторонних функций, но они оба чуть не сломаны (специалист знает, как создавать предварительные изображения для заданных изображений, или почти в состоянии сделать это). Проводит конкурс, чтобы выбрать новый стандартный, который будет назван SHA-3 .
Очевидный подход к инвертированию функции односторонней стороны будет вычислять много изображений и сохранить их в таблице, связанную с каждым изображением предварительного изображения. Чтобы сделать это невозможным на практике, все односторонние функции имеют большой выход, как минимум 64 бита, но, возможно, гораздо больше (до, скажем, 512 бит).
Отредактируйте: Как работают большинство криптографических хэш-функций?
Обычно они имеют в своем ядре одной функции, которая делает сложные преобразования на блоке битов (A блочного шифра ). Функция должна быть почти биктивна (она не должна отображать слишком много последовательностей к одному и тому же изображению, потому что это приведет к тому, что это приведет к слабымствиям позже), но это не должно быть именно биективным. И эта функция является итерацией фиксированного количества раз, достаточно, чтобы сделать вход (или любой возможный вход) невозможно.
Возьмите пример моток , один из сильных кандидатов для контекста 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 , то он должен быть очень сложным («вычислительно невыполнительно») к конструкции Еще одна строка, которая также хесируется в H .
Вы можете взглянуть на postageapp.com
-121--2981298-Использование массива params (суррогат того, что называется "именованными аргументами" в других языках ") - я люблю использовать его сам - но у него довольно большой минус: Аргументы не документируются с использованием стандартной нотации phpDoc таким образом, и, следовательно, среда IDE не сможет давать подсказки при вводе имени функции или метода.
-121--1842621-Вот очень простой пример. Предположим, что я начинающий криптограф и создаю хеш-функцию, которая делает следующее:
int SimpleHash(file) {
return 0 if file.length is even;
return 1 if file.length is odd;
}
Вот тест. SimpleHash (specityFile) имеет значение 0. Каков был мой исходный файл?
Очевидно, что нет пути узнать (хотя вы, вероятно, могли бы довольно легко обнаружить, что мой хеш основан на длине файла). Нет пути «восстановить» мой файл на основе хэша, потому что хэш не содержит всего, что сделал мой файл.
Хеш - это (очень) кодировка с потерями.
Чтобы дать вам более простые пример, представьте себе фиктивное 2-буквенное кодирование 5-буквенного слова, называемого X-кодировкой. Алгоритм для X-кодирования простой: воспользуйтесь первыми и последствиями слова.
Итак,
X-encode( SAUCE ) = SE
X-encode( BLOCK ) = BK
Очевидно, вы не можете восстановить соус от его кодирования SE (при условии, что наш диапазон возможных входов - это все 5-буквенные слова). Слово может так же легко быть местом.
Кроме того, тот факт, что соус и пространство оба производят SE как кодирование, называется Collision , и вы можете видеть, что X-Ecoding не сделает очень хорошее хэш. :)
Съемки для простой аналогии здесь вместо сложного объяснения.
Для начала, давайте сломаем тему на две части, односторонние операции и перемешивание. Что такое односторонняя операция и почему вы хотите один?
Операция по одному способу называется, потому что они не обратимы. Наиболее типичными операциями, такими как добавление и умножение, могут быть изменены, а подразделение модуло не может быть изменено. Почему это важно? Поскольку вы хотите обеспечить выходное значение, которое 1) трудно дублировать без исходных входов и 2) не дает способа выяснить входы с вывода.
Дополнение
. : Это может быть изменено, взяв сумму и вычитаю один из добавлений умножения : Это может быть изменено, принимая продукцию и разделившись одним из факторов подразделение по модулю : Это не может быть изменено, потому что нет операции, которую вы можете сделать для фактического и дивиденда, чтобы восстановить дивизор (или наоборот ). Можете ли вы найти операцию, чтобы заполнить, где «?» является? С этим говорим, что односторонние хэш-функции имеют одинаковое математическое качество, что и деление по модулю. позволяет сказать, что я дал вам ключ к шкафчику в автобусном терминале, который имеет одну тысячу шкафчиков и попросил вас доставить его на мой банкир. Будучи умным парнем, не говоря уже о подозрении, вы немедленно смотрели на ключ, чтобы увидеть, какой номер шкафчика написан на ключ. Зная это, я сделал несколько оправдательных вещей; Сначала я нашел два числа, когда разделенные, когда разделить модуло, дает мне номер в диапазоне от 1 до 1000, - во-вторых, я стерл исходный номер и написал на нем делитель из пары чисел, второй я выбрал автобусный терминал, который имеет Охранник, защищающий шкафчики от негодяев, только позволяя людям попробовать один шкафчик в день с их ключом, третий банкир уже знает дивиденды, поэтому, когда он получает ключ, он может сделать математику и выяснить остаток и знает, какой шкафчик открывается. Если я выбираю операнды мудро, могу приблизиться к отношениям к одному на один между коэффициентом и дивидендом, который заставляет вас попробовать каждый шкафчик, потому что ответ распространяет результаты возможных входов по диапазону желаемых чисел , шкафчики доступны в терминале. По сути, это означает, что вы не можете приобрести какие-либо знания о остальной части, даже если вы знаете одну из операндов. Итак, теперь я могу «доверять» вам доставить ключ к своему законному владельцу, не беспокоясь о том, что вы можете легко догадаться, к которому он принадлежит шкафчик. Конечно, вы можете перебраться за силой поиска всех шкафчиков, но это займет почти 3 года, достаточно времени для моего банкира использовать ключ и опорожнять шкафчик. См. Другие ответы для более специфики на различных хэш-функциях. 4 + 3 = 7
7 - 3 = 4
4 * 5 = 20
20 / 4 = 5
не обратимых
22 % 7 = 1
1 ? 7 = 22
1 ? 22 = 7
Почему это важно?
Из всего, что я прочитал, кажется, что объект не должен быть конкретным , и на самом деле должен был быть абстрактным.
Не только нет необходимости в том, чтобы он был конкретным, но после некоторого более прочтения я убежден, что объект не абстрактный противоречит базовой модели наследования - мы не должны допускать абстрактные подклассы конкретного класса, так как подклассы должны только добавлять функциональность.
Очевидно, что это не так в Java, где у нас есть абстрактные подклассы Object .
Одновременно можно использовать несколько именованных труб. Посмотрите на ServiceModelEx Ювала Лоуи из его книги Programming WCF Services. Вы увидите, когда он создает именованные трубы, он использует код, который выглядит примерно так:
Uri baseAddress = new Uri("net.pipe://localhost/" + Guid.NewGuid().ToString());Что должно избежать конфликтов имен.
-121--3879790-Говоря простым языком, хеш-функция работает, создавая большой запутанный беспорядок входных данных.
См., например, MD5 . Он обрабатывает входные данные 512-битными блоками. Каждый блок разделен на 16 32-битных слов. Существует 64 шага, каждый из которых использует одно из 16 входных слов. Таким образом, каждое слово используется четыре раза в течение алгоритма. Это то, откуда исходит односторонность: любой входной бит вводится в нескольких местах, и между двумя такими входами функция смешивает все текущие данные вместе, так что каждый входной бит влияет на большую часть 128-разрядного рабочего состояния. Это предотвращает инвертирование функции или вычисление коллизии путем просмотра только части данных. Вы должны посмотреть на все 128 бит, и пространство 128-разрядных блоков слишком велико, чтобы их можно было эффективно пройти.
Сейчас MD5 не справляется с этой задачей, так как можно найти коллизии для этой функции. С точки зрения криптографа, MD5 - повёрнутая функция шифрования. Обработка одного блока М сообщений (512 битов) использует входное состояние V (128-битное значение) и вычисляет новое состояние V 'как V' = V + E(M, V), где «+» - словосочетание, а «E» - симметричная функция шифрования (иначе «блочный шифр»), который использует М в качестве ключа и V в качестве сообщения, подлежащего шифрованию. С более пристального взгляда E can - своего рода «расширенная сеть Фейстеля», похожая на блочный шифр DES, с четырьмя четвертями вместо двух половин. Детали здесь не важны; Я хочу сказать, что то, что делает «хорошую» хеш-функцию, среди хеш-функций, которые используют эту структуру (называемую «Merkle-Damgârd»), похоже на то, что делает блочный шифр «безопасным». Успешные коллизионные атаки на 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 (не считая дюжины дополнительных, которые провалили административный тест на отправку полного представления с кодом, который компилирует и работает правильно).
Теперь давайте посмотрим более концептуально. Защищенная хеш-функция должна выглядеть как случайный оракул : оракул - это чёрный ящик, который при вводе сообщения M выводит ответ h (M) , который выбирается случайным образом, равномерно, в пространстве вывода (т.е. все n -битные последовательности, если длина вывода хеш-функции равна n ). Если в качестве входного значения указано то же самое сообщение M , Oracle выводит то же значение, что и ранее. Кроме этого ограничения, выход oracle на неиспользуемом входе 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 лет публичных исследований симметричных систем шифрования дали целую атрибутику понятий и инструментов (диффузия, лавина, дифференциалы, линейность...), которые могут быть применены. Итог, однако, состоит в том, что у нас нет доказательств того, что случайный оракул на самом деле может существовать. Мы хотим хеш-функцию, которая не может быть атакована. То, что у нас есть - кандидаты на хеш-функции, для которых в настоящее время атака не известна , и, что несколько лучше, у нас есть некоторые функции, для которых некоторые виды атаки могут быть доказаны, что они не работают.
Еще предстоит провести ряд исследований.