Хэш-столкновение

Джон Смит и Сандра Ди используют одно и то же значение хеш-функции 02, что приводит к коллизии хеш-функций.

В информатике — хеш-коллизия или хэш-конфликт. [1] это когда два разных фрагмента данных в хэш-таблице имеют одно и то же значение хеш-функции. Хэш-значение в этом случае получается из хеш-функции , которая принимает входные данные и возвращает фиксированную длину битов. [2]

Хотя алгоритмы хеширования были созданы с намерением обеспечить устойчивость к коллизиям , они все же иногда могут сопоставлять разные данные с одним и тем же хешем (в силу принципа группировки ). Злоумышленники могут воспользоваться этим для имитации, доступа или изменения данных. [3]

Из-за возможных негативных применений хеш-коллизий в управлении данными и компьютерной безопасности (в частности, криптографических хеш-функций ) предотвращение коллизий стало важной темой компьютерной безопасности.

Предыстория [ править ]

Коллизии хешей могут быть неизбежными в зависимости от количества объектов в наборе и от того, достаточно ли длинна битовая строка, с которой они сопоставлены. Когда существует набор из n объектов, если n больше | R |, который в данном случае R — это диапазон значения хеш-функции, вероятность того, что произойдет коллизия хеша, равна 1, что означает, что она гарантированно произойдет. [4]

Другая причина, по которой в какой-то момент времени вероятны коллизии хешей, связана с идеей парадокса дня рождения в математике. В этой задаче рассматривается вероятность того, что из n человек у набора из двух случайно выбранных людей будет одинаковый день рождения. [5] Эта идея привела к так называемой атаке на день рождения . Предпосылка этой атаки заключается в том, что трудно найти день рождения, который точно соответствует вашему дню рождения или конкретному дню рождения, но вероятность найти группу любых двух людей с совпадающими днями рождения значительно увеличивает вероятность. Злоумышленники могут использовать этот подход, чтобы упростить поиск хеш-значений, которые конфликтуют с любым другим хеш-значением, а не искать конкретное значение. [6]

Влияние столкновений зависит от приложения. Когда хеш-функции и отпечатки пальцев используются для идентификации схожих данных, таких как гомологичные последовательности ДНК или аналогичные аудиофайлы, функции разрабатываются таким образом, чтобы максимизировать вероятность коллизии между разными, но похожими данными, используя такие методы, как хеширование с учетом местоположения . [7] С другой стороны, контрольные суммы предназначены для минимизации вероятности конфликтов между одинаковыми входными данными, без учета конфликтов между очень разными входными данными. [8] Случаи, когда злоумышленники пытаются создать или найти хеш-коллизии, известны как коллизионные атаки. [9]

На практике приложения, связанные с безопасностью, используют криптографические алгоритмы хэширования, которые разработаны так, чтобы быть достаточно длинными, чтобы случайные совпадения были маловероятными, достаточно быстрыми, чтобы их можно было использовать где угодно, и достаточно безопасными, чтобы было чрезвычайно сложно обнаружить коллизии. [8]

Вероятность возникновения [ править ]

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

Примите во внимание следующие алгоритмы хеширования — CRC-32, MD5 и SHA-1. Это распространенные алгоритмы хеширования с различными уровнями риска коллизий. [10]

CRC-32 [ править ]

CRC-32 представляет самый высокий риск хеш-коллизий. Эту хэш-функцию обычно не рекомендуется использовать. Если бы хаб содержал 77 163 хэш-значения, вероятность возникновения хеш-коллизии составила бы 50 %, что чрезвычайно высоко по сравнению с другими методами. [11]

MD5 [ править ]

MD5 является наиболее часто используемым и по сравнению с двумя другими хэш-функциями представляет собой золотую середину с точки зрения риска хэш-коллизий. Чтобы получить 50%-ную вероятность возникновения хеш-коллизии, в хабе должно быть более 5,06 миллиарда записей. [11]

SHA-1 [ править ]

SHA-1 предлагает самый низкий риск коллизий хэшей. Чтобы функция SHA-1 имела 50% вероятность возникновения хеш-коллизии, должно быть 1,42 × 10. 24 записи в хабе. Обратите внимание: количество записей, упомянутых в этих примерах, должно находиться в одном и том же хабе. [11]

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

Разрешение столкновений [ править ]

Основная статья: Хэш-таблица § Разрешение конфликтов

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

Джона Смита и Сандру Ди отправляют в одну камеру. Открытая адресация приведет к тому, что хеш-таблица перенаправит Сандру Ди в другую ячейку.

Открытая адресация [ править ]

Основная статья: Открытая адресация

В этом методе ячейкам хеш-таблицы присваивается одно из трех состояний — занято, пусто или удалено. Если происходит коллизия хешей, таблица будет проверена для перемещения записи в альтернативную ячейку, которая указана как пустая. Существуют различные типы зондирования, которые происходят, когда происходит коллизия хэшей, и этот метод реализован. Некоторые типы зондирования — это линейное зондирование , двойное хеширование и квадратичное зондирование . [12] Открытая адресация также известна как закрытое хеширование. [13]

Отдельная цепочка [ править ]

Дополнительная информация: Хэш-таблица § Отдельная цепочка.

Эта стратегия позволяет «привязать» более одной записи к ячейкам хеш-таблицы. Если две записи направляются в одну и ту же ячейку, обе они попадут в эту ячейку как связанный список. Это эффективно предотвращает возникновение коллизий хэшей, поскольку записи с одинаковыми значениями хеш-функции могут помещаться в одну и ту же ячейку, но у этого есть свои недостатки. Отслеживать такое количество списков сложно, и это может привести к тому, что любой используемый инструмент будет работать очень медленно. [12] Раздельная цепочка также известна как открытое хеширование. [14]

Разрешение коллизий с учетом кэша [ править ]

Хотя он используется гораздо реже, чем два предыдущих, Аскитис и Зобель (2005) предложили в 2005 году метод разрешения коллизий с учетом кэша . [15] Эта идея аналогична методам отдельных цепочек, хотя технически она не включает в себя цепные списки. В этом случае вместо связанных списков хэш-значения представлены в виде непрерывного списка элементов. Это лучше подходит для строковых хеш-таблиц, а использование числовых значений пока неизвестно. [12]

См. также [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Hash_collision&oldid=1210911773"