Вопрос по – Каковы важные моменты в криптографических хеш-функциях?

11

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

И все же консенсус-ответ на вопросWhy aren't MD5 hash values reversible? являетсяBecause an infinite number of input strings will generate the same output.  Это кажется совершенно противоречивым для меня.

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

Что происходит, когда размер входных данных меньше фиксированного размера выходных данных (например, хеширование пароля "abc")?

EDIT:

OK, let me see if I have this straight:

It is really, really hard to infer the input from the hash because there are an infinite amount of input strings that will generate the same output (irreversible property). However, finding even a single instance of multiple input strings that generate the same output is also really, really hard (collision resistant property).
Да, «консенсус» в ответах на вопрос, который вы связали совершенно неправильно. Я только добавил еще один ответ, исправляющий это. Paŭlo Ebermann
Я не видел твоих правок. Я думаю, вы подвели итог этим двум пулям. Alex Feinman
Причиной свойства обратимости является не «бесконечное количество входных строк», это также должно быть в том случае, если вы ограничиваете входное значение чем-то небольшим (например, вокруг выходного размера). Paŭlo Ebermann

Ваш Ответ

6   ответов
18

Предупреждение: длинный ответ

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

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

(Несмотря на распространенное мнение о ненадежности MD5, MD5 по-прежнему устойчив к прообразам. Любой, кто не верит мне, может дать мне все, что хэширует2aaddf751bff2121cc51dc709e866f19. Чего нет у MD5, так это сопротивление столкновению, что совсем другое.)

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

Так возникает вопрос: а почему бы и нет? (Или, другими словами, как вы делаете функцию устойчивой к прообразу?)

Ответ заключается в том, что криптографические хеш-функции имитируют хаотические системы. Они принимают ваше сообщение, разбивают его на блоки, смешивают эти блоки вокруг, взаимодействуют между собой некоторые блоки, смешивают эти блоки и повторяют это много раз (ну, одна криптографическая хеш-функция делает это; другие имеют свои собственные методы). Поскольку блоки взаимодействуют друг с другом, блок C должен не только взаимодействовать с блоком D, чтобы создать блок A, но он должен взаимодействовать с блоком E, чтобы создать блок B. Теперь, конечно, вы можете найти значения блоков C, D, E, который произведет блоки A и B в вашем хэш-значении, но когда вы вернетесь дальше, внезапно вам понадобится блок F, который взаимодействует с C, чтобы сделать D, и с E, чтобы сделать B, и ни один такой блок не может сделать оба в в то же время! Должно быть, вы догадались неправильные значения для C, D и E.

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

6

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

стойчивость к прообразу @Being - это другое свойство, нежели обратимость. Функция является обратимой, если при y = f (x) существует ровно один подходящий x (легко это или нет). Например, определите f (x) = x mod 10. Тогда f необратим. Из f (x) = 7 вы не можете определить, было ли x 17, 27 или что-то еще. Но f не является устойчивым к прообразу, так как значения x 'такие, что f (x) = 7, легко найти. x '= 17, 27, 12341237 и т. д. все работают.

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

12

1: Основная цель хэша состоит в том, чтобы отобразить очень, очень большое пространство на меньшее, но все еще очень большое пространство (например, MD5, которое будет принимать «что угодно» и преобразовывать его в пространство размером 2 ^ 128 - большой, но не такой большой, как алеф-0.

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

Представьте себе идиотскую хэш-функцию sum (, которая просто добавляет все цифры входного числа: она преуспевает в отображении, но есть множество коллизий (входы с одинаковым выходом, как 3 и 12 и 21 на нижний конец выходного пространства и верхний конец пространства почти пуст. В результате он очень плохо использует пространство, легко взламывается и т. Д.

Так что хороший хеш, который равномерно использует пространство назначения, затруднит поиск двух входов с одинаковым выходом, просто по коэффициенту: если бы MD5 был идеальным, вероятность того, что два входа имели бы одинаковый выход, была бы 2 ^ -128. Это довольно приличные шансы: лучшее, что вы можете сделать, не прибегая к большему пространству на выходе. (На самом деле MD5 не идеален, что делает его уязвимым.

Но все равно будет верно, что огромное количество входов будет отображаться на любой данный хэш, потому что пространство ввода «бесконечно», а деление бесконечности на 2 ^ 128 по-прежнему дает бесконечность.

2: Да, хэши всегда вызывают потерю данных, за исключением случая, когда ваше пространство вывода равно или больше, чем ваше пространство ввода - и в этом случае вам, вероятно, не нужно хешировать!

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

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

-1 Вы упустили момент, что в вычислительном отношении должно быть трудно перевернуть хэш-функцию. Линейная функция может очень хорошо распределять хеш-значения и при этом не подходить для криптографии. starblue
Извините, я не имел в виду, что функция линейно распределяет функцию, просто, что распределение чисел должно быть плавным при большом sc, ale. Alex Feinman
+ 1, хотя некоторые детали отсутствуют, я думаю, что этот ответ все еще полезен. laalto
Я не знаю, как редактировать, не меняя полностью свой ответ. Ответ Зарела выглядит довольно хорошо, хотя. Не столько спорьте по поводу «шансов», так как это предполагает, что атакующий не может сделать ничего лучше, чем случайная попытка. (Если хеш-функция является хорошей криптографической, это будет иметь место, но ваш аргумент ничего не говорит об этом. Смотрите мойsimple_hash ответьте в моем ответе на другой вопрос и проверьте, какие из ваших аргументов также применимы к нему - они неправильные.) Paŭlo Ebermann
То, что вы говорите, касается хеш-функций, которые можно использовать для хеш-таблиц, но при этом упускает смысл криптографических хеш-функций (например, сопротивление прообразу). Paŭlo Ebermann
2

Однако предостережение: MD5 больше не следует использовать из-за найденных в нем уязвимостей. Проверьте раздел «Уязвимости» и внешние ссылки, подробно описывающие эти атаки.http: //en.wikipedia.org/wiki/Md Вы можете создать конфликт MD5, изменив только 128 бит в сообщении.

SHA-1 безопасен для простого хеширования, хотя есть некоторые атаки, которые могут ослабить его против хорошо финансируемых организаций (правительств, крупных корпораций)

SHA-256 - безопасная отправная точка против технологий на ближайшие пару десятилетий.

Не обязательно. Принятый ответ в вопросе, на который я ссылался, использует пример хеш-функции H (x) = x mod 2. Эта хеш-функция обладает свойством труднообращаться, но не свойством низкого столкновения. Rob Sobers
@ vg1890: свойства Криптографической хэш-функции. H (x) = x mod 2 не является криптографической хеш-функцией. (Хотя это может быть полезно для хэш-таблицы с 2 записями.) Paŭlo Ebermann
1

почему значения MD5 не являются обратимыми?" потому что «бесконечное количество входных строк будет генерировать один и тот же результат».

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

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

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

0

Почему значения MD5 не являются обратимыми?; потому что «бесконечное количество входных строк> будет генерировать один и тот же вывод»

это причина того, что невозможно изменить хеш-функцию (получить тот же вход). криптографические хеш-функции устойчивы к коллизиям, это означает, что также трудно найти другое входное значение, которое отображается на тот же выход (если ваша хеш-функция была mod 2: 134 mod 2 = 0; теперь вы не можете получить 134 из результат, но мы можем все еще найти номер 2 с тем же выходным значением (134 и 2 сталкиваются)).

Когда вход меньше размера блока, Обивка используется, чтобы соответствовать размеру блока.

По-прежнему не имеет смысла, трудно найти два входа, которые производят один и тот же вывод, но тот факт, что многие входы имеют одинаковый выход, является причиной того, что хэш является необратимым. Как это не противоречие? Rob Sobers
обращение функции - это нечто иное, чем нахождение коллизии. В идеале единственный способ найти коллизию - это попробовать один ввод за другим и сравнить выходной результат хеш-функции со значением, которое вы хотите обратить / найти коллизию (это сложно). Но даже если бы вы это сделали, вы бы не знали, было ли обнаруженное вами столкновение оригинальным или вы просто нашли новую строку с тем же хеш-значением. cube

Похожие вопросы