 | Эта статья поднимает множество проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалить эти сообщения-шаблоны ) ( Узнайте, как и когда удалить этот шаблон сообщения )
|
В информатике , столкновение или столкновение является ситуация , которая возникает , когда два различных частей данных имеют одинаковый хэш - значение , контрольная сумма , отпечатков пальцев , или криптографической переваривать . [1]
Из-за возможных применений хеш-функций в управлении данными и компьютерной безопасности (в частности, криптографические хеш-функции ) предотвращение коллизий стало фундаментальной темой в информатике.
Коллизии неизбежны, когда члены очень большого набора (например, все возможные имена людей или все возможные компьютерные файлы ) отображаются в относительно короткую битовую строку. Это просто пример принципа «ящика» . [1]
Влияние столкновений зависит от приложения. Когда хеш-функции и отпечатки пальцев используются для идентификации похожих данных, таких как гомологичные последовательности ДНК или аналогичные аудиофайлы , функции разработаны таким образом, чтобы максимизировать вероятность столкновения между отдельными, но похожими данными, с использованием таких методов, как хеширование с учетом местоположения . [2] Контрольные суммы , с другой стороны, предназначены для минимизации вероятности конфликтов между одинаковыми входными данными, без учета конфликтов между очень разными входными данными. [3]
Компьютерная безопасность [ править ]
Хеш-функции могут сопоставлять разные данные с одним и тем же хешем (в силу принципа ячейки ), злоумышленники могут воспользоваться этим для имитации данных. [4]
Например; рассмотрим хеш-функцию, которая хеширует данные, возвращая первые три символа данной строки (например, «Password12345» переходит в «Pas»). Хакер, не знающий пароля пользователя, может вместо этого ввести «Pass», что приведет к сгенерированию того же хэш-значения «Pas». Несмотря на то, что хакер не знает правильный пароль, у них есть пароль, который дает им тот же хэш, который дает им доступ. Этот тип атаки называется атакой по прообразу .
На практике приложения, связанные с безопасностью, используют криптографические хэш-алгоритмы, которые разработаны так, чтобы быть достаточно длинными, чтобы случайные совпадения были маловероятными, достаточно быстрыми, чтобы их можно было использовать где угодно, и достаточно безопасными, чтобы было бы чрезвычайно сложно обнаружить коллизии. [3]
См. Также [ править ]
- Атака на день рождения
- Коллизионная атака (против криптографических хеш-функций)
- Сопротивление столкновению
- Разрешение коллизий (хеш-таблицы)
- Криптографическая хеш-функция
- Конфликт имен , случайное использование идентичных имен переменных
- Хеш пароля (функция получения ключа)
- Идеальная хеш-функция , хеш-функция, которая по дизайну не имеет коллизий.
- Атака на прообраз
- Доказанно безопасная хеш-функция
- Случайный оракул
Ссылки [ править ]
- ^ a b Джред Флойд (18.07.2008). "Что на самом деле означают коллизии хэшей?" . permabit.wordpress.com: Пермабиты и Петабайты . Проверено 24 марта 2011 .
Для подробного объяснения криптографических хешей и хеш-коллизий я написал немного назад для SNW Online колонку «Что вам нужно знать о криптографических хэшах и корпоративном хранилище». Краткая версия состоит в том, что системы дедупликации, которые используют криптографические хэши, используют эти хеши для генерации более коротких «отпечатков пальцев», чтобы однозначно идентифицировать каждую часть данных и определять, существуют ли эти данные уже в системе. Проблема в том, что по математическому правилу, называемому «принципом ящика», вы не можете однозначно сопоставить любые возможные файлы или фрагменты файла с более коротким отпечатком пальца. Статистически существует несколько возможных файлов с одинаковым хешем.
- ^ Раджараман, А .; Ульман, Дж. (2010). «Майнинг массивных наборов данных, глава 3» .
- ^ а б Аль-Кувари, Саиф; Давенпорт, Джеймс Х .; Брэдфорд, Рассел Дж. (2011). «Криптографические хеш-функции: последние тенденции дизайна и концепции безопасности» . Цитировать журнал требует
|journal=( помощь ) - ^ Шнайер, Брюс . «Криптоанализ MD5 и SHA: время для нового стандарта» . Компьютерный мир . Архивировано из оригинала на 2016-03-16 . Проверено 20 апреля 2016 .
Односторонние хеш-функции - это не просто алгоритмы шифрования, но и рабочие лошадки современной криптографии.
