Коллизия хеш функции — это когда у двух разных входных элементов таблицы
будет hash одинаковым. Коллизии встречаются в разнообразных алгоритмах
хеширования, однако это не является нормой и в «правильных» алгоритмах их
возникновение сведено к минимальному значению. Но в то же время, когда
приходится работать с большими таблицами хеширования, то их возникновение
неизбежно. А в некоторых алгоритмах хеширования , к примеру в MD5, наличие
коллизии вообще обязательно.
Коллизия криптографической хеш функции
Любая криптографическая хеш функция подтверждает неизменность исходящей
информации. Поэтому наличие тут коллизий должно быть сведено к нулю. Ведь, к
примеру, если использовать данную функцию, чтобы создавать оцифрованную
подпись, то поиск ее коллизии практически приравнивается к подделки самой
подписи. Поэтому к криптографическому алгоритму хеширования не должен быть
возможным применен способ просто отыскать коллизию. Максимум — это
полностью перебирать все хеш-значения в таблице. То есть этот вид хеш функции
считается самым защищенным, так как применяется для хранения засекреченных
сведений.
Коллизия хеш функции может быть использована для
взлома
Можно разобрать простейшую форму для входа на какой-нибудь ресурс:
- когда новый пользователь регистрируется на каком-либо ресурсе, он придумывает логин пароль для входа ;эти значения записываются в таблицу хеширования хеш функцией;
- когда пользователь повторно входит на ресурс и вводит свои логин и пароль, эти значения сравниваются с внесенными уже в базу данных той же технологией хеширования. В целом это распространенный и защищенный метод хеширования. При таком варианте, если вдруг взломщику откроется возможность доступа к БД, ему все равно будет недоступно восстановление исходных паролей юзеров ресурса. Но в тоже время, если взломщик сможет найти коллизии для имеющейся хеш функции, он легко сможет подделать пароль, у которого hash-сумма будет идентична с hash- суммой пароля взломанных пользователей. Также злоумышленники часто используют коллизии хеш функции, чтобы подделать различные элементы:
- оповещения о финансовых операциях ;могут запрашивать секретные данные в сообщениях;
- оцифрованные подписи;
- дипломы и web-сертификаты и т.д
Защита от применения коллизий хеш функций
Как мы говорили чуть выше, поиск коллизии функции хеширования может привести к
взлому и подделке важных аспектов. Однако можно использовать ряд методов,
чтобы защититься от от использования коллизий в злых умыслах:
- Метод «salt». «Подсаливание» хеширования дополнительными элементами, то
есть добавляется последовательность каких-нибудь символов перед ним. В таком
случае взломщику нужно будет разгадать еще алгоритм «salt», что усложнит задачу в
несколько раз. - Метод конкатенации hash. Это когда значения hash «смешиваются» от двух
разных технологий хеширования. В таком случае взломщику нужно будет
предугадать коллизии сразу 2-х хеш функции.
Простые возможности поиска коллизии хеш функции
Каких-то универсальных возможностей поиска коллизии хеш функции не бывает. По
одной причине, что самих алгоритмов хеширования большое разнообразие. Для
некоторых вообще не существует способов поиска, для других он построен на
решении сложных математических уравнений.
Для hash функций с небольшой длиной хеша можно выделить несколько методов
для поиска коллизии:
- Поиск методом «Парадокс дня рождения». Атака осуществляется при помощи
подбора 2-х случайных наборов сообщений по формуле 2*n/2 . Где n — битовая
длина хеша. Предполагается, что в таком подборе есть вероятность найти пару
сообщений с одинаковыми значениями, равная 1⁄2. - Поиск методом «Атака расширения». При данном методе не атакуется само
значение в hash-таблице, а лишь его hash-значения. И как только он узнается,
открывается возможность переписывать чужие сообщения.
Возможно вам будет интересно почитать статью “Метод Ферми для быстрой оценки чего угодно”
А в целом подбирать метод поиска коллизии нужно в индивидуальном порядке. В
сети есть разнообразные варианты и формулы. Потому что многие «общие» или
простые возможности просто могут вам не подойти.
