Хэш -столкновение
В информатике , хэш -столкнутое столкновение или хэш -столк [ 1 ] это когда две отдельные части данных в хэш -таблице имеют одинаковое значение хэша. Значение хеша в этом случае получено из хэш -функции , которая принимает ввод данных и возвращает фиксированную длину битов. [ 2 ]
Хотя алгоритмы хэш, особенно криптографические алгоритмы хеш -аш, были созданы с целью быть устойчивыми к столкновению , они все еще могут иногда отображать разные данные с одним и тем же хэшем (в силу принципа голубей ). Злоупотребление пользователями может воспользоваться этим, чтобы имитировать, доступ или изменить данные. [ 3 ]
Из -за возможных негативных применений хэш -столкновений в управлении данными и компьютерной безопасности (в частности, криптографических хеш -функциях ), избегание столкновений стало важной темой в области компьютерной безопасности.
Фон
[ редактировать ]Хэш -столкновения могут быть неизбежными в зависимости от количества объектов в наборе и, является ли битовая строка, на которую они отображаются, достаточно длинной длиной. Когда есть набор n объектов, если n больше, чем | R |, который в этом случае r является диапазоном значения хэша, вероятность того, что столкновение хеш будет 1, что означает, что оно гарантированно произойдет. [ 4 ]
Другая причина, по которой хеш -столкновения в какой -то момент связаны с идеей парадокса по случаю дня рождения в математике. В этой проблеме рассматривается вероятность того, что набор из двух случайно выбранных людей, имеющих один и тот же день рождения из n числа людей. [ 5 ] Эта идея привела к тому, что была названа атакой на день рождения . Предпосылка этой атаки заключается в том, что трудно найти день рождения, который специально соответствует вашему день рождения или конкретному дню рождения, но вероятность найти набор из каких -либо двух человек с соответствующими днями рождения значительно увеличивает вероятность. Плохие актеры могут использовать этот подход, чтобы им было проще найти значения хэш, которые сталкиваются с любым другим значением хэша, а не в поисках определенного значения. [ 6 ]
Влияние столкновений зависит от приложения. Когда для выявления аналогичных данных используются функции хранения и отпечатки пальцев, такие как гомологичные последовательности ДНК или аналогичные аудиофайлы, функции разработаны таким образом, чтобы максимизировать вероятность столкновения между различными, но сходными данными, используя методы, такие как чувствительные к локальности хэширование . [ 7 ] Контрольные суммы , с другой стороны, предназначены для минимизации вероятности столкновений между аналогичными входами, без учета столкновений между очень разными входными данными. [ 8 ] Случаи, когда плохие актеры пытаются создать или найти хэш -столкновения, известны как атаки столкновений. [ 9 ]
На практике приложения, связанные с безопасностью, используют криптографические алгоритмы хэша, которые предназначены для того, чтобы быть достаточно длинными, чтобы случайные совпадения были маловероятными, достаточно быстрыми, чтобы их можно было использовать в любом месте, и достаточно безопасно, чтобы было бы чрезвычайно трудно найти столкновения. [ 8 ]
Разрешение столкновения
[ редактировать ]В хэш -таблицах, поскольку хеш -столкновения неизбежны, хэш -таблицы имеют механизмы общения с ними, известные как решения столкновений. Двумя наиболее распространенными стратегиями являются открытая адресация и отдельная цепочка . Резолюция по сознанию кеша-это еще одна стратегия, которая обсуждалась в прошлом для таблиц струнных хеш-таблиц.
Открытая адресация
[ редактировать ]Клетки в хэш -таблице назначают одно из трех состояний в этом методе - занятых, пустых или удаленных. Если произойдет хэш -столкновение, таблица будет рассмотрено для перемещения записи в альтернативную ячейку, которая считается пустой. Существуют различные типы зондирования, которые происходят, когда происходит столкновение хеш -столк, и этот метод реализован. Некоторые типы зондирования являются линейное зондирование , двойное хеширование и квадратичное зондирование . [ 10 ] Открытая адресация также известна как закрытый хэшинг. [ 11 ]
Отдельная цепочка
[ редактировать ]Эта стратегия позволяет «прикованной» к клеткам хэш -таблицы. Если две записи направлены на одну и ту же ячейку, оба введут в эту ячейку в качестве связанного списка. Это эффективно предотвращает столкновение хеш -столкновения, поскольку записи с одинаковыми значениями хэша могут попасть в одну и ту же ячейку, но у него есть свои недостатки. Отслеживать так много списков сложно и может вызвать любой инструмент, который используется, чтобы стать очень медленным. [ 10 ] Отдельная цепочка также известна как открытый хэшинг. [ 12 ]
Кэш-сознательное разрешение столкновения
[ редактировать ]гораздо меньше, чем в предыдущих двух, Несмотря на то, что Askites & Zobel (2005) предложил метод разрешения столкновения в кэше в 2005 году. [ 13 ] Это аналогичная идея с отдельными методами цепочки, хотя она технически не включает в себя прикованные списки. В этом случае, вместо цепных списков значения хэша представлены в смежном списке элементов. Это лучше подходит для таблиц струнных хеш -таблиц, и использование для числовых значений до сих пор неизвестно. [ 10 ]
Смотрите также
[ редактировать ]- Универсальная односторонняя хэш-функция -тип универсальной хеш-функции в криптографии, предложенная в качестве альтернативы страницам с устойчивыми к столкновению хэш-функций,
- Криптография - практика и изучение безопасных методов общения
- Universal Hashing - техника выбора хэш -функций
- Идеальная функция хеша - функция хэш без каких -либо столкновений
Ссылки
[ редактировать ]- ^ Томас, Кормен (2009), Введение в алгоритмы , с прессой, с. 253, ISBN 978-0-262-03384-8
- ^ Stapko, Timothy (2008), «Встроенная безопасность» , Практическая встроенная безопасность , Elsevier, с. 83–114, doi : 10.1016/b978-075068215-2.50006-9 , ISBN 9780750682152 Получено 2021-12-08
- ^ Шнайер, Брюс . «Cryptanalysis of MD5 и SHA: время для нового стандарта» . Computerworld . Архивировано с оригинала 2016-03-16 . Получено 2016-04-20 .
Гораздо больше, чем алгоритмы шифрования, односторонние хэш-функции-это рабочие лошадь современной криптографии.
- ^ Кибербезопасность и прикладная математика . 2016. DOI : 10.1016/C2015-0-01807-X . ISBN 9780128044520 .
- ^ Солтанян, Мохаммад Реза Халифех (10 ноября 2015 г.). Теоретические и экспериментальные методы защиты от атак DDOS . ISBN 978-0-12-805399-7 Полем OCLC 1162249290 .
- ^ Конрад, Эрик; Мисенар, Сет; Feldman, Joshua (2016), «Домен 3: Инженерная служба безопасности (Инженерное управление и управление безопасностью)» , учебное пособие CISSP , Elsevier, стр. 103–217, doi : 10.1016/b978-0-12-802437-9.00004-7 , ISBN 9780128024379 Получено 2021-12-08
- ^ Раджараман, А.; Ullman, J. (2010). «Майн массивных наборов данных, гл. 3» .
- ^ Jump up to: а беременный Аль-Кувари, Саиф; Давенпорт, Джеймс Х.; Брэдфорд, Рассел Дж. (2011). Криптографические хэш -функции: недавние тенденции дизайна и представления о безопасности . Inscrypt '10.
- ^ Схема, Майк (2012). Взломать веб -приложения .
- ^ Jump up to: а беременный в Нимбе, Петр; Ofori Frimpong, Самуил; Опоку, Майкл (2014-08-20). «Эффективная стратегия разрешения столкновений в хэш -таблицах» . Международный журнал компьютерных приложений . 99 (10): 35–41. Bibcode : 2014ijca ... 99J..35n . doi : 10.5120/17411-7990 . ISSN 0975-8887 .
- ^ Клайн, Роберт. «Закрытый хэшинг» . CSC241 Структуры данных и алгоритмы . Университет Западного Честера . Получено 2022-04-06 .
- ^ «Открытое хеширование или отдельная цепочка» . Log 2 2 .
- ^ Аскит, Николас; Зобель, Джастин (2005). Консен, м.; Наварро, Г. (ред.). Кэш-сознательное разрешение столкновения в струнных хэш-таблицах . Международный симпозиум по обработке струн и поиске информации. Обработка строки и поиск информации Spire 2005 . Заметки лекции в информатике. Тол. 3772. Берлин, Гейдельберг: Спрингер Берлин Хейдельберг. С. 91–102. doi : 10.1007/11575832_11 . ISBN 978-3-540-29740-6 .
