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

Question

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

Однако консенсусный ответ на вопрос Почему значения хеша MD5 не обратимы? is Поскольку бесконечное количество входных строк будет генерировать один и тот же вывод. Это кажется мне совершенно противоречивым.

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

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

EDIT:

Хорошо, позвольте мне увидеть, если у меня есть это прямо:

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

Answer 1

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

Будучи устойчивым к протекторам, это другое свойство, чем обратимость. Функция обратима, если задано 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 и т. д. все работает.

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

Answer 2

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

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

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

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

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

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

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

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

Answer 3

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

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

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

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

Answer 4

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

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

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

Answer 5

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

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

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

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

Answer 6

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

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

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

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

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

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

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

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