Хэш-столкновение
В информатике — хеш-коллизия или хэш-конфликт. [1] это когда два разных фрагмента данных в хэш-таблице имеют одно и то же значение хеш-функции. Хэш-значение в этом случае получается из хеш-функции , которая принимает входные данные и возвращает фиксированную длину битов. [2]
Хотя алгоритмы хеширования, особенно криптографические алгоритмы хеширования, были созданы с целью обеспечения устойчивости к коллизиям , они все же иногда могут сопоставлять разные данные с одним и тем же хешем (в силу принципа группировки ). Злоумышленники могут воспользоваться этим для имитации, доступа или изменения данных. [3]
Из-за возможных негативных применений хеш-коллизий в управлении данными и компьютерной безопасности (в частности, криптографических хеш-функций ) предотвращение коллизий стало важной темой компьютерной безопасности.
Фон
[ редактировать ]Коллизии хэшей могут быть неизбежными в зависимости от количества объектов в наборе и от того, достаточно ли длинна битовая строка, с которой они сопоставлены. Когда существует набор из n объектов, если n больше | R |, который в данном случае R — это диапазон значения хеш-функции, вероятность того, что произойдет коллизия хеша, равна 1, что означает, что она гарантированно произойдет. [4]
Другая причина, по которой в какой-то момент времени вероятны коллизии хешей, связана с идеей парадокса дня рождения в математике. В этой задаче рассматривается вероятность того, что из n человек у набора из двух случайно выбранных людей будет одинаковый день рождения. [5] Эта идея привела к так называемой атаке на день рождения . Предпосылка этой атаки заключается в том, что трудно найти день рождения, который точно соответствует вашему дню рождения или конкретному дню рождения, но вероятность найти группу любых двух людей с совпадающими днями рождения значительно увеличивает вероятность. Злоумышленники могут использовать этот подход, чтобы упростить поиск хеш-значений, которые конфликтуют с любым другим хеш-значением, а не искать конкретное значение. [6]
Влияние столкновений зависит от приложения. Когда хэш-функции и отпечатки пальцев используются для идентификации схожих данных, таких как гомологичные последовательности ДНК или аналогичные аудиофайлы, функции разрабатываются так, чтобы максимизировать вероятность конфликта между разными, но похожими данными, используя такие методы, как хеширование с учетом местоположения . [7] С другой стороны, контрольные суммы предназначены для минимизации вероятности конфликтов между одинаковыми входными данными, без учета конфликтов между очень разными входными данными. [8] Случаи, когда злоумышленники пытаются создать или найти хеш-коллизии, известны как коллизионные атаки. [9]
На практике приложения, связанные с безопасностью, используют криптографические алгоритмы хэширования, которые разработаны так, чтобы быть достаточно длинными, чтобы случайные совпадения были маловероятными, достаточно быстрыми, чтобы их можно было использовать где угодно, и достаточно безопасными, чтобы было чрезвычайно сложно обнаружить коллизии. [8]
Вероятность возникновения
[ редактировать ]Хэш-коллизии могут возникать случайно и могут быть намеренно созданы для многих хэш-алгоритмов. Таким образом, вероятность коллизии хэшей зависит от размера алгоритма, распределения значений хеш-функции, а также от того, известно ли математически и вычислительно осуществимо создание конкретных коллизий.
Примите во внимание следующие алгоритмы хеширования — CRC-32, MD5 и SHA-1. Это распространенные алгоритмы хэширования с различными уровнями риска коллизий. [10]
КПР-32
[ редактировать ]CRC-32 представляет самый высокий риск хеш-коллизий. Эту хэш-функцию обычно не рекомендуется использовать. Если бы хаб содержал 77 163 хеш-значения, вероятность возникновения хеш-коллизии составила бы 50 %, что чрезвычайно высоко по сравнению с другими методами. [11]
MD5
[ редактировать ]MD5 является наиболее часто используемым и по сравнению с двумя другими хэш-функциями представляет собой золотую середину с точки зрения риска хеш-коллизий. Чтобы получить 50%-ную вероятность возникновения хеш-коллизии, в хабе должно быть более 5,06 миллиарда записей. [11]
ША-1
[ редактировать ]SHA-1 предлагает самый низкий риск коллизий хэшей. Чтобы функция SHA-1 имела 50% вероятность возникновения хеш-коллизии, должно быть 1,42 × 10. 24 записи в хабе. Обратите внимание: количество записей, упомянутых в этих примерах, должно находиться в одном и том же хабе. [11]
Наличие концентратора с меньшим количеством записей может снизить вероятность хэш-коллизии во всех этих хеш-функциях, хотя всегда будет присутствовать незначительный риск, который неизбежен, если не используются методы разрешения коллизий.
Разрешение столкновений
[ редактировать ]В хеш-таблицах, поскольку хеш-коллизии неизбежны, в хеш-таблицах есть механизмы борьбы с ними, известные как разрешение коллизий. Двумя наиболее распространенными стратегиями являются открытая адресация и отдельная цепочка . Разрешение коллизий с учетом кэша — это еще одна стратегия, которая обсуждалась ранее для строковых хеш-таблиц.
Открытая адресация
[ редактировать ]В этом методе ячейкам хеш-таблицы присваивается одно из трех состояний — занято, пусто или удалено. Если происходит коллизия хешей, таблица будет проверена для перемещения записи в альтернативную ячейку, которая указана как пустая. Существуют различные типы зондирования, которые происходят, когда происходит коллизия хэшей, и этот метод реализован. Некоторые типы зондирования — это линейное зондирование , двойное хеширование и квадратичное зондирование . [12] Открытая адресация также известна как закрытое хеширование. [13]
Отдельная цепочка
[ редактировать ]Эта стратегия позволяет «привязать» более одной записи к ячейкам хеш-таблицы. Если две записи направляются в одну и ту же ячейку, обе они попадут в эту ячейку как связанный список. Это эффективно предотвращает возникновение коллизий хэшей, поскольку записи с одинаковыми значениями хеш-функции могут помещаться в одну и ту же ячейку, но у этого есть свои недостатки. Отслеживать такое количество списков сложно, и это может привести к тому, что любой используемый инструмент будет работать очень медленно. [12] Отдельная цепочка также известна как открытое хеширование. [14]
Разрешение конфликтов с учетом кэша
[ редактировать ]Хотя он используется гораздо реже, чем два предыдущих, Аскитис и Зобель (2005) предложили в 2005 году метод разрешения коллизий с учетом кэша . [15] Эта идея аналогична методам отдельных цепочек, хотя технически она не включает в себя цепные списки. В этом случае вместо связанных списков хэш-значения представлены в виде непрерывного списка элементов. Это лучше подходит для строковых хеш-таблиц, а использование числовых значений пока неизвестно. [12]
См. также
[ редактировать ]- Универсальная односторонняя хеш-функция - тип универсальной хеш-функции в криптографии, предложенный в качестве альтернативы устойчивым к коллизиям хеш-функциям.
- Криптография - практика и изучение методов безопасной связи.
- Универсальное хеширование - метод выбора хеш-функций.
- Идеальная хеш-функция – хеш-функция без каких-либо коллизий.
Ссылки
[ редактировать ]- ^ Томас, Кормен (2009), Введение в алгоритмы , MIT Press, стр. 253, ISBN 978-0-262-03384-8
- ^ Стапко, Тимоти (2008), «Встроенная безопасность» , «Практическая встроенная безопасность » , Elsevier, стр. 83–114, doi : 10.1016/b978-075068215-2.50006-9 , ISBN 9780750682152 , получено 8 декабря 2021 г.
- ^ Шнайер, Брюс . «Криптоанализ MD5 и SHA: время нового стандарта» . Компьютерный мир . Архивировано из оригинала 16 марта 2016 г. Проверено 20 апреля 2016 г.
Односторонние хеш-функции — это не просто алгоритмы шифрования, а рабочие лошадки современной криптографии.
- ^ Кибербезопасность и прикладная математика . 2016. doi : 10.1016/c2015-0-01807-x . ISBN 9780128044520 .
- ^ Солтаниан, Мохаммад Реза Халифе (10 ноября 2015 г.). Теоретические и экспериментальные методы защиты от DDoS-атак . ISBN 978-0-12-805399-7 . OCLC 1162249290 .
- ^ Конрад, Эрик; Мисенар, Сет; Фельдман, Джошуа (2016), «Домен 3: Разработка безопасности (инжиниринг и управление безопасностью)» , CISSP Study Guide , Elsevier, стр. 103–217, doi : 10.1016/b978-0-12-802437-9.00004-7 , ISBN 9780128024379 , получено 8 декабря 2021 г.
- ^ Раджараман, А.; Ульман, Дж. (2010). «Анализ больших наборов данных, глава 3» .
- ^ Jump up to: Перейти обратно: а б Аль-Кувари, Саиф; Давенпорт, Джеймс Х.; Брэдфорд, Рассел Дж. (2011). Криптографические хеш-функции: последние тенденции проектирования и понятия безопасности . Инкрипт '10.
- ^ Схема, Майк (2012). Взлом веб-приложений .
- ^ Альтейд, Кори; Карви, Харлан (2011). Цифровая криминалистика с использованием инструментов с открытым исходным кодом . Эльзевир. стр. 1–8. дои : 10.1016/b978-1-59749-586-8.00001-7 . ISBN 9781597495868 . Проверено 8 декабря 2021 г.
- ^ Jump up to: Перейти обратно: а б с Линстедт, Дэниел; Ольшимке, Майкл (2016). «Масштабируемая архитектура хранилища данных». Создание масштабируемого хранилища данных с помощью Data Vault 2.0 . Эльзевир. стр. 17–32. дои : 10.1016/b978-0-12-802510-9.00002-7 . ISBN 9780128025109 . Проверено 7 декабря 2021 г.
- ^ Jump up to: Перейти обратно: а б с Нимбе, Питер; Офори Фримпонг, Самуэль; Опоку, Майкл (20 августа 2014 г.). «Эффективная стратегия разрешения конфликтов в хеш-таблицах» . Международный журнал компьютерных приложений . 99 (10): 35–41. Бибкод : 2014IJCA...99j..35N . дои : 10.5120/17411-7990 . ISSN 0975-8887 .
- ^ Клайн, Роберт. «Закрытое хеширование» . CSC241 Структуры данных и алгоритмы . Вест-Честерский университет . Проверено 6 апреля 2022 г.
- ^ «Открытое хеширование или отдельная цепочка» . Журнал 2 2 .
- ^ Аскитис, Николас; Зобель, Джастин (2005). Консенс, М.; Наварро, Г. (ред.). Разрешение конфликтов с учетом кэша в строковых хеш-таблицах . Международный симпозиум по обработке строк и поиску информации. Обработка строк и поиск информации SPIRE 2005 . Конспекты лекций по информатике. Том. 3772. Берлин, Гейдельберг: Springer Berlin Heidelberg. стр. 91–102. дои : 10.1007/11575832_11 . ISBN 978-3-540-29740-6 .
