Каковы важные моменты в криптографических хеш-функциях?
Я читал этот вопрос о хэш-значениях MD5, и принятый ответ смущает меня. Как я понимаю, одним из основных свойств криптографической хеш-функции является невозможность найти два разных сообщения (входных данных) с одинаковым хеш-значением.
И все же единодушный ответ на вопрос: почему значения MD5 не являются обратимыми? Потому что бесконечное количество входных строк будет генерировать один и тот же вывод. Это кажется совершенно противоречивым для меня.
Кроме того, меня несколько смущает тот факт, что алгоритмы являются общедоступными, однако значения хеш-функции все еще необратимы. Это потому, что в хэш-функции всегда происходит потеря данных, поэтому невозможно определить, какие данные были выброшены?
Что происходит, когда размер входных данных меньше фиксированного размера выходных данных (например, хеширование пароля "abc")?
РЕДАКТИРОВАТЬ:
Хорошо, позвольте мне посмотреть, если у меня есть это прямо:
- Это действительно очень сложно определить входные данные из хэша, потому что существует бесконечное количество входных строк, которые будут генерировать один и тот же результат (необратимое свойство).
- Однако найти даже один экземпляр нескольких входных строк, которые генерируют один и тот же вывод, также очень и очень сложно (свойство устойчивости к столкновениям).
6 ответов
Вы можете быть смущены, потому что ответ на вопрос, который вы цитируете , сбивает с толку. Одним из требований к криптографической хэш-функции является то, что она должна быть устойчивой к прообразу. То есть, если вы знаете 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 и т. д. все работают.
При выполнении криптозащиты вам обычно нужны функции, которые устойчивы к прообразу (и другие свойства, такие как устойчивость к столкновениям), а не просто что-то необратимое.
Предупреждение: длинный ответ
Я думаю, что во всех этих ответах отсутствует очень важное свойство криптографических хеш-функций: не только невозможно вычислить исходное сообщение, которое было хешировано, чтобы получить заданный хеш, но и невозможно вычислить любое сообщение, которое хэширует до заданного значения хеш-функции., Это называется сопротивлением прообразу.
(Под "невозможным" - я имею в виду, что никто не знает, как сделать это за меньшее время, чем требуется, чтобы угадать каждое возможное сообщение, пока вы не угадаете то, которое было хэшировано в ваш хэш.)
(Несмотря на распространенное мнение о ненадежности MD5, MD5 по-прежнему устойчив к прообразам. Любой, кто не верит мне, волен давать мне все, что хэширует 2aaddf751bff2121cc51dc709e866f19, Что у MD5 нет, так это сопротивление столкновению, что совсем другое.)
Теперь, если единственная причина, по которой вы не можете "работать в обратном направлении" в криптографической хеш-функции, заключается в том, что хеш-функция отбрасывает данные для создания хеш-функции, то это не гарантирует устойчивость к прообразу: вы все равно можете "работать в обратном направлении" и просто вставить случайные данные везде, где хеш-функция отбрасывает данные, и хотя вы не получите оригинальное сообщение, вы все равно получите сообщение, которое хэширует до желаемого значения хеш-функции. Но ты не можешь.
Поэтому возникает вопрос: почему бы и нет? (Или, другими словами, как сделать функцию устойчивой к прообразу?)
Ответ заключается в том, что криптографические хеш-функции моделируют хаотические системы. Они принимают ваше сообщение, разбивают его на блоки, смешивают эти блоки вокруг, взаимодействуют между собой некоторые блоки, смешивают эти блоки и повторяют это много раз (ну, одна криптографическая хеш-функция делает это; другие имеют свои собственные методы). Поскольку блоки взаимодействуют друг с другом, блок C должен не только взаимодействовать с блоком D, чтобы создать блок A, но он должен взаимодействовать с блоком E, чтобы создать блок B. Теперь, конечно, вы можете найти значения блоков C, D, E, который произведет блоки A и B в вашем хэш-значении, но когда вы вернетесь дальше, внезапно вам понадобится блок F, который взаимодействует с C, чтобы сделать D, и с E, чтобы сделать B, и ни один такой блок не может сделать оба в в то же время! Вы, должно быть, догадались, неправильные значения для C, D и E.
Хотя не все криптографические хеш-функции в точности соответствуют описанному выше для взаимодействия с блоками, они имеют одну и ту же идею: если вы попытаетесь "работать в обратном направлении", у вас будет множество тупиков и время вам нужно попробовать достаточно значений, чтобы сгенерировать прообраз порядка сотен или миллионов лет (в зависимости от хэш-функции), что не намного лучше, чем время, которое потребуется, чтобы просто попробовать сообщения, пока вы не найдете работающее.
1: Основная цель хэша состоит в том, чтобы отобразить очень, очень большое пространство на меньшее, но все еще очень большое пространство (например, MD5, которое возьмет "что угодно" и преобразует его в пространство размером 2^128 - большое, но не такой большой, как алеф-0.)
В дополнение к другим функциям хорошие хеши равномерно заполняют пространство назначения. Плохие хеши заполняют пространство комковатым способом, предлагая тот же хеш для многих общих входных данных.
Представьте себе идиотскую хэш-функцию sum(), которая просто добавляет все цифры входного числа: она преуспевает в отображении, но есть множество коллизий (входы с одинаковым выходом, как 3 и 12 и 21) на низком уровне конец выходного пространства и верхний конец пространства практически пуст. В результате он очень плохо использует пространство, легко взламывается и т. Д.
Таким образом, хороший хеш, который даже использует пространство назначения, затруднит поиск двух входов с одинаковым выходом, просто по коэффициенту: если бы MD5 был идеальным, вероятность того, что два входа имели бы одинаковый выход, была бы 2^-128. Это довольно приличные шансы: лучшее, что вы можете сделать, не прибегая к большему пространству на выходе. (На самом деле MD5 не идеален, что делает его уязвимым.)
Но все равно будет верно, что огромное количество входных данных будет отображаться на любой заданный хэш, потому что входное пространство является "бесконечным", а деление бесконечности на 2 ^ 128 по-прежнему дает бесконечность.
2: Да, хеши всегда вызывают потерю данных, за исключением случая, когда ваше пространство вывода равно или больше, чем ваше пространство ввода - и в этом случае вам, вероятно, не нужно было хешировать!
3: для меньших входов, лучшая практика состоит в том, чтобы солить вход На самом деле, это хорошая практика для любого криптографического хэширования, потому что в противном случае злоумышленник может передать вам определенные входные данные и попытаться выяснить, какой хеш вы используете. "Соль" - это просто набор дополнительной информации, которую вы добавляете (или добавляете) к своему входу; Вы тогда хешируете результат.
редактирование: в криптографии также важно, чтобы хеш-функция была устойчивой к атакам с предварительным изображением, интуитивно, что трудно угадать ввод для данного вывода, даже зная множество других пар ввода / вывода. Функцию "сумма", вероятно, можно было бы угадать довольно легко (но, поскольку она уничтожает данные, обратное преобразование может быть не так просто)
Это свойства хеш-функций в целом.
Однако, предостережение: 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 сталкиваются)).
Когда ввод меньше размера блока, для подгонки его под размер блока используется заполнение.