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