Может ли теоретически у двух различных строк быть одинаковый хеш и почему

Обновлено: 06.07.2024

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

ОТВЕТЫ

Ответ 1

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

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

Если это окажется проблемой, я предлагаю посмотреть на хэш-функции SHA-2 (SHA-256, SHA-384 и SHA-512). Недостатком является то, что он немного медленнее и имеет более длинный выход хеширования.

Ответ 2

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

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

Ответ 3

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

См. этот и этот для примера.

Ответ 4

Да, конечно: хеши MD5 имеют конечную длину, но существует бесконечное количество возможных строк символов, которые могут быть хешированы MD5.

Ответ 5

Да, это возможно. Он называется Hash collision.

Сказав это, алгоритмы, такие как MD5, предназначены для минимизации вероятности столкновения.

Википедия в MD5 объясняет некоторые уязвимости в MD5, о которых вы должны знать.

Ответ 6

Просто быть более информативным. С математической точки зрения функции Хэша не инъективные.
Это означает, что между стартовым набором и полученным результатом нет отношения 1 к 1 (но одностороннему).

EDIT: существуют полные инъективные хэш-функции: он называется Идеальное хеширование.

Ответ 7

Да, возможно, что две разные строки могут генерировать один и тот же хэш-код MD5.

Они генерируют другую сумму SHA-1, но то же самое значение хеша MD5. Во-вторых, строки очень похожи, поэтому трудно найти разницу между ними.

Разницу можно найти по следующей команде:

Пример выше столкновений берется от Марка Стивенса: Одноблочное столкновение для MD5, 2012; он объясняет свой метод, с исходным кодом (альтернативная ссылка на бумагу).

Еще одно испытание:

Разная сумма SHA-1, то же MD5-хэш.

Разница в одном байте:

Ответ 8

Да, это так! Столкновение будет возможно (хотя риск очень мал). Если нет, у вас будет довольно эффективный метод сжатия!

EDIT. Как говорит Конрад Рудольф: потенциально неограниченный набор входных данных, преобразованный в конечный набор результатов (32 шестнадцатеричных символа), приведет к бесконечному количеству столкновений.

Ответ 9

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

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

Ответ 10

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

Ответ 11

Я понимаю, что это старо, но я думал, что внесет свое решение. Есть 2 ^ 128 возможных комбинаций хэшей. И, таким образом, вероятность того, что парадокс дня рождения будет 2 ^ 64. Хотя нижеприведенное решение не устранит вероятность столкновений, оно наверняка уменьшит риск на очень существенную величину.

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

Итак, мой псевдокод для этого:

То есть к практической невероятности столкновения. Но если вы хотите быть супер параноиком и не можете этого добиться, а пространство для хранения данных не является проблемой (и не является циклом вычисления).

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

Ради меня, я думаю, что вероятность столкновения не так уж и редка, что я буду считать это не "верным", но так маловероятно, что это соответствует потребностям.

Теперь возможные комбинации значительно увеличиваются. Хотя вы могли бы потратить много времени на то, сколько комбинаций это могло бы получить вас, я скажу, что теоретически это приземляет вас ЗНАЧИТЕЛЬНО больше, чем цитированное число выше

Вероятнее всего на сотню цифр. Теоретический максимум, который может дать вам, будет

Нужно чтобы хэш их был одинаковый. Подскажите есть ли подобные алгоритмы?

Вопрос задан более трёх лет назад
8654 просмотра

Оценить 2 комментария

В качестве сравниваемых строк могут быть не адреса Simhash или charikar's hash.
Используется в гугле для поиска похожих документов. Легко переделывается для строк (в качестве фич берутся не биграммы-токены, а биграммы-символы).
Подробный алгоритм здесь.
Теоретическое обоснование – в статье «Similarity estimation techniques from rounding algorithms».

см. расстояние Левенштейна.

А хеш одинаковый это вряд ли, конечно…

Не получится, слишком много неопределенностей, особенно без сравнения строк, для примера
Васюковая -> Масюковая -> Масюковае -> Масюковое -> Масуковое -> Мосуковое -> Мозуковое -> Мозуговое -> Мозугавое -> Мозугадое
Каждое слово схоже с следующим, и следовательно должено иметь одинаковый хэш, но разница между первым и последним уже огромная. Совсем без сравнений, как мне кажется, нельзя. Если нет возможности сравнивать входящие данные, сравнивайте выходящие — сами хэши. Применение не обязательно к адресам. Это может быть что угодно.
Хэши могут отличаться, но так, что бы была возможность при задании некого коэффициента схожести говорить, что эти строки одинаковые. Тогда стоит определиться что значит «коэффициент схожести»
Например, «Васюковская улица» и «ацилу яаксвокюсаВ» — совсем несхожие строки, а состоят из одинаковых букв. То есть формально они схожие.
Рассматриваем вашу задачу формально — строки являются схожими, если одна переводится в другую заменой не более N символов, убиранием не более M символов и вставлением не более K символов.
При N = 4, M = 3, K = 3 строка «счастье» будет равна строке «жопа»
Какие у вас коэффициенты? можно учитывать и порядок букв.
Я же не привожу свой алгоритм, у меня нет коэфициентов, мне интересно есть ли уже существующий, чтобы не изобретать велосипед Уточните вопрос
Вам нужен конкретный алгоритм, возвращающий одинаковый хэш для двух этих конкретных строк (и не важно что для всех остальных)?
Или вам нужен генератор алгоритмов хэш-функций, которому на вход дают две строки, а генератор генерирует такой алгоритм хэширования, чтобы для этих заданных строк получалась коллизия (и опять не важно, что там получится для всех остальных)?

Можно пробовать хеш функцию, которая является суммой всех символов div С, где С — константа, большая (например,100). Тогда с высокой долей вероятности, строки, которые отличаются на 1-2 символа будут попадать в один хеш.

В общем случае, для адресов не спасает расстояние Левенштейна, и не спасают какие либо хеш — функции.

Вначале их нужно привести к какому-то одинаковому виду
Разбить строку по словам, привести к одному регистру, выкинуть малозначительное и неуникальное, типа «ул.», знаки препинания и прочее.
Слить слова в строку, вида «москва васюковская» «москва васюковая», взять фонетический код, получится, например, 479465.
С цифрами несколько непонятно, какие будут варианты. Но в данном случае — выкинуть все повторы и оставить только цифры, входящие в номер как первой строки, так и второй.

Таким образом у нас получится две одинаковые строки (если фонетический код совпадет) вида

«479465 12»
«479465 12»

Можно вычислять хэш.

Не думали насчет алгоритмов нечеткого поиска, как, например, Soundex или метафон? Готовая имплементация есть в Apache Codec, алгоритмы Metaphone и Metaphone 2.

Смотрите вот здесь. Онлайн демка (работает судя по всему только с латиницей).

Я когда-то думал над подобным способом для поиска слов с опечатками. Одним хешем тут точно не обойтись, и вот почему. Допустим (упростим задачу), все слова имеют одинаковую длину, например, 4 символа, мы хотим, чтобы у слов, различающихся 1 буквой, был одинаковый хеш. Тогда слова abcd и abce имеют одинаковый хеш, слова abcd и zbcd имеют одинаковый хеш… в итоге, все слова будут иметь один и тот же хеш.

Потому, одним хешем тут не обойтись. Нужно как минимум, несколько.

Например, хеш для всех букв, кроме первой. Хеш для всех, кроме второй, и т.д. Тогда у различающихся 1 буквой слов будут 2 совпадающих хеша.

Или другой подход — разбиение слов на триграммы и поиск по ним. У похожих слов большинство триграмм будет одинаковыми.

Напишите функцию, которая примет a='Москва, ул. Васюковская 12 ' и b='Москва, ул. Васюковая 121' и вернет true для определенных условий (что-то вроде дом начинается одинаково && первые 5-6 символов улиц начинаются/заканчиваются одинаково && одинаковый город). Тогда берите все части, которые совпали и берите по ним хэш.
Скажем, для данного примера возьмите хэш по выделенной строке:
Москва, ул. Васюковская 12
Москва, ул. Васюковая 121

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

Я уточнил вопрос, строки не сравниваются между собой

Нет. Как вы себе представляете работу такой функции? А если дом 122? Или 21? Тоже одинаковый хэш должен быть? А если улица «Масюковская» — тоже? А когда он должен делаться неодинаковый?

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

адреса приведены в качестве примера, да должен быть одинаковый

Вообще, вопрос противоречит сам себе.
Насколько я помню, одна из основных особенностей (требований или хз как назвать) хэша заключается в том, что он должен выдавать совершенно разные значения даже для максимально близких строк.

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

Не совсем. Контакт у хеш функции такой:
1) Равенство/одинаковость объектов значит, что хеши равны.
2) Неравенство/неодинаковость объектов не означает, что хеши разные.

Вомзожно можно оптимизировать алгоритм шинглов, только вместо слов использовать n-ое кол-во символов.

Кстати, с адресом очень интересный пример. Если бы задача ограничивалась адресом, то решалась бы так:
1. неким алгоритмом получаем название страны (например, страна часто пишется в адресе последней, есть список стран) и берем его идентификатор как первую часть хеш-кода
2. другим алгоритмом получаем название штата/области (в US двубуквенные сокращения, в пост-СССР со словом «обл.», есть список штатов всех стран), если найден — берем как вторую часть кода
3. третьим алгоритмом получаем город (обычно идет первым, с большой буквы, без префиксов, есть список городов, есть список ZIP кодов/индексов), его идентификатор становится третьей частью хеш-кода. Если есть связка город-штат и неопределен результат в п.2, заполняем его

Получаем трехкомпонентный хеш-код, который с большой долей вероятности будет одинаков для всех адресов одного города (как и в изначальном примере). Написания улиц могут и будут различаться, потому эту часть мы специально отбрасываем и расчитываем на коллизию размером с все улицы одного города.
Такой метод подходит для большей части городов мира, особенно для суб-урбанизированных стран вроде США и совершенно не подходит для Москвы и других мегаполисов.

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

Могу ли я быть уверен, что хеш для данной строки («очень длинная строка») всегда будет одинаковым?

Могу ли я быть уверен, что у двух разных строк не будет одного и того же хеша?

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

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

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

Класс String переопределяет реализацию GetHashCode по умолчанию в объекте.

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

Могу ли я быть уверен, что хеш для данной строки («очень длинная строка») всегда будет одинаковым?

В вашем использовании - да.

Могу ли я быть уверен, что у двух разных строк не будет одного и того же хеша?

Нет. Две разные строки могут иметь один и тот же хэш.

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

Вероятность довольно низкая, результирующий хеш из домена 4G является довольно случайным.

И так же, как для equals(), для метода hashCode() есть официальные требования, прописанные в документации Oracle:

Если два объекта равны (т.е. метод equals() возвращает true), у них должен быть одинаковый хэш-код.

Иначе наши методы будут лишены смысла. Проверка по hashCode(), как мы и сказали, должна идти первой для повышения быстродействия. Если хэш-коды будут разными, проверка вернет false, хотя объекты на самом деле равны (согласно нашему определению в методе equals()).

Если метод hashCode() вызывается несколько раз на одном и том же объекте, каждый раз он должен возвращать одно и то же число.

Правило 1 не работает в обратную сторону. Одинаковый хэш-код может быть у двух разных объектов.

Я запутался помогите разобраться:
Почему в 3 правило написано мол правило 1 не работает в обратную сторону?
Получается 1 правило 2 объекта равны и у них хэш-код одинаковый.
А 3 правило так же одинаковый хэш-код у 2 объектов или я не очень понимаю? Почему в 1 правило написано если 2 объекта равны, а в 3 правило написано одинаковый хэш-код может быть у двух РАЗНЫХ объектов, как понять разных?

64.8k 6 6 золотых знаков 47 47 серебряных знаков 102 102 бронзовых знака Вся суть в том, что множество объектов ограничено только Вашей фантазией, а множество хэш-кодов ограничено диапазоном типа Integer . Исходя из этого, кол-во различных объектов может быть больше, чем кол-во различных хэш-кодов, откуда следует, что у разных объектов может быть одинаковый хэш-код (т.н. коллизия). Сначала проверяется хэш-код, а затем equals . Если хэш-коды разные, то и объекты гарантированно разные и проверять на equals смысла нет. Если же хэш-коды одинаковые, то необходимо еще проверить на equals .

Примечание: предполагается, что в классе переопределен метод hashCode() .

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

Пример: хеш строки считается по длине строки: length*3 . Тогда у строк foo и bar одинаковые хеши.

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

Обычно он используется для сравнения объектов:
Допустим, у вас есть объект, в котором есть много-много полей. В большинстве случаев объекты для сравнения будут неравны. Чтобы не сравнивать кучу переменных(если объекты не равны), можно сначала сравнивать хешкод(т.к., если хеш различается, то объекты точно различны). Если хеши отличаются - можно дальше не сравнивать переменные. Если одинаковы - дальше нужно сравнить переменные(т.к., если хеши одинаковы, то это не значит, что объекты одинаковы).

Ну и последнее - почти всегда возвращаемый тип метода hashCode() - int . У int есть определенный предел(от -21. до +21. если я не ошибаюсь). Если разных объектов будет больше, чем этот предел, то физически нельзя сгенерировать разные хеши для всех объектов. Т.е., при использовании хешей можно увеличить производительность программы.

Читайте также: