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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Это свойства хэш-функций в целом.

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

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

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

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

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

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

Причина такой невозможности в том, что входные данные так тщательно "смешаны вместе"

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

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

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