Коллизия хешей
Коллизия хешей возникает, когда два разных входа дают один и тот же хеш-дайджест.
Определение
Коллизия хешей возникает, когда два различных входа дают один и тот же дайджест в одной и той же хеш-функции. Для любого хеша фиксированного размера коллизии неизбежны, потому что возможных входов больше, чем выходов, но стойкая хеш-функция делает их поиск вычислительно непрактичным.
Стойкость к коллизиям важна, когда дайджест используют для идентификации содержимого, подписания документов, сравнения файлов или защиты целостности от атакующего.
Стойкость к коллизиям
Для идеального n-битного хеша общий поиск коллизии требует примерно 2^(n/2) работы из-за парадокса дней рождения. Это отличается от стойкости к прообразу, где нужно найти вход для одного заданного дайджеста, а общий порядок работы составляет около 2^n.
Для MD5 и SHA-1 существуют практические атаки на коллизии, поэтому их нельзя выбирать для новых чувствительных к безопасности систем. SHA-256, SHA-512, SHA-3 и BLAKE2 — современные варианты при правильном применении.
Чего коллизия не означает
Атака на коллизии не расшифровывает хеш и не раскрывает исходное сообщение. Она показывает, что атакующий может создать два разных входа с одним дайджестом, что ломает подписи, сертификаты или идентификаторы содержимого, зависящие от уникальности.
Безопасность HMAC не зависит только от стойкости к коллизиям так же, как обычные подписи по дайджесту, но протоколы всё равно должны выбирать актуальные хеш-функции и следовать спецификациям.
Нет. Коллизии математически неизбежны, но хорошо спроектированный хеш делает поиск полезных коллизий непрактичным.
Нет. Обращение ищет вход для заданного дайджеста, а коллизия ищет два разных входа с одинаковым дайджестом.
Для них есть практические атаки на коллизии, поэтому атакующие могут создавать разные входы с одним дайджестом там, где стойкость к коллизиям важна.