Другое

Коллизия хеш-функции и самые простые методы поиска коллизий

Lorem ipsum dolor

Коллизия хеш-функции — это когда у двух разных входных элементов таблицы hash будет одинаковым. Коллизии встречаются в разнообразных алгоритмах хеширования, однако это не является нормой и в «правильных» алгоритмах их возникновение сведено к минимальному значению. Но в то же время, когда приходится работать с большими таблицами хеширования, то их возникновение неизбежно. А в некоторых алгоритмах хеширования, к примеру, в MD5, наличие коллизии вообще обязательно.

Коллизия криптографической хеш-функции

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

Коллизия хеш-функции может быть использована для взлома

Можно разобрать простейшую форму для входа на какой-нибудь ресурс:

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

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

Также злоумышленники часто используют коллизии хеш-функции, чтобы подделать различные элементы:

  • оповещения о финансовых операциях; могут запрашивать секретные данные в сообщениях;
  • оцифрованные подписи;
  • дипломы и web-сертификаты и т.д.

Защита от применения коллизий хеш-функций

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

  1. Метод «salt». «Подсаливание» хеширования дополнительными элементами, то есть добавляется последовательность каких-нибудь символов перед ним. В таком случае взломщику нужно будет разгадать еще алгоритм «salt», что усложнит задачу в несколько раз.
  2. Метод конкатенации hash. Это когда значения hash «смешиваются» от двух разных технологий хеширования. В таком случае взломщику нужно будет предугадать коллизии сразу 2-х хеш-функций.

Простые возможности поиска коллизии хеш-функции

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

Для hash-функций с небольшой длиной хеша можно выделить несколько методов для поиска коллизии:

  1. Поиск методом «Парадокс дня рождения». Атака осуществляется при помощи подбора 2-х случайных наборов сообщений по формуле 2*n/2. Где n — битовая длина хеша. Предполагается, что в таком подборе есть вероятность найти пару сообщений с одинаковыми значениями, равная 1⁄2.
  2. Поиск методом «Атака расширения». При данном методе не атакуется само значение в hash-таблице, а лишь его hash-значения. И как только оно узнается, открывается возможность переписывать чужие сообщения.

А в целом подбирать метод поиска коллизии нужно в индивидуальном порядке. В сети есть разнообразные варианты и формулы. Потому что многие «общие» или простые возможности просто могут вам не подойти.

 

Схожие статьи

Vue JS анимация. Примеры, синтаксис и основные разновидности анимации
Другое

Vue JS анимация. Примеры, синтаксис и основные разновидности анимации

Правила верстки сайта: что нужно знать, с чего начать, список советов
Другое

Правила верстки сайта: что нужно знать, с чего начать, список советов

Что такое кроссплатформенность, как её правильно сделать и проверить
Другое

Что такое кроссплатформенность, как её правильно сделать и проверить

Arduino и его лучшие аналоги
Другое

Arduino и его лучшие аналоги