вычисление, какие строки будут иметь одинаковый хэш

Question

с SHA-1, можно ли вычислить, какие конечные строки будут отображать равные хэши?

Answer 1

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

Фактически, одна из мер хорошей хэш-функции - это трудность нахождения столкновений. (Среди других мер - трудность реверсирования хеш-функции)

Следует отметить, что в хэшах, где ввод представляет собой любую длину строки, а выход представляет собой строку фиксированной длины, Pigeonhole Principle гарантирует, что существует по крайней мере, одно столкновение для любой заданной строки. Однако найти эту строку не так просто, так как это потребует в основном слепой догадки и проверки над практически бесконечным набором строк.

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

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

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

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

Хэш, подобный SHA1 или MD5, будет довольно сильным, и более или менее вычислительно невозможно найти столкновения (в течение разумного периода времени). В конечном счете вам не нужно искать хэш, для которого невозможно найти столкновений. Вам практически нужен только тот, где сложность его достаточно велика, что было бы слишком дорого для вычисления (т. Е. Порядка миллиарда лет или триллиона лет, чтобы найти столкновение).

Из-за того, что все хеши несовершенны , можно было бы проанализировать его внутреннюю работу и увидеть математические закономерности и эвристику и попытаться найти столкновения по этой схеме. Это похоже на хеш-функцию, состоящую из% 7 ... Хеширование числа 13 будет 13% 7 = 6, 89% 7 = 5. Если вы видели хэш из 3, вы могли бы использовать свое математическое понимание функции модуля для легко найти столкновение (т. е. 10) . К счастью для нас, более сильным хеш-функциям гораздо труднее понять математическую основу. (В идеале, так трудно, что ни один человек никогда не понять!)

Некоторых цифр:

• Нахождение столкновения для одного заданного SHA-0 хэша занимает около 13 полных дней запущенных вычислений на верхних суперкомпьютерах в мире, используя шаблоны, присущие математике.
• Согласно полезному комментатору, столкновения MD5 могут генерироваться «быстро», чтобы быть менее идеальным для чувствительных целей.
• До сих пор не было найдено или доказано, что метод SHA-1 практически не применим и не применим/не используется, хотя, как отмечалось в комментариях, есть некоторые недостатки, которые были обнаружены.

Здесь similar SO question, в котором ответы гораздо мудрее, чем у меня.

_{отметить, что, в то время как эта хэш-функция является слабым для столкновений, то она сильна, что это совершенно невозможно вернуться назад и найти данный ключ, если ваш хэш, скажем, 4. Есть все (4, 11, 18, 25 ...)}

Answer 2

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

Answer 3

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

Answer 4

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

Дальнейшее чтение: http://en.wikipedia.org/wiki/Collision_attack