СипХэш
SipHash — это на основе add-rotate-xor (ARX), семейство псевдослучайных функций созданное Жаном-Филиппом Омассоном и Дэниелом Дж. Бернштейном в 2012 году. [1] : 165 [2] в ответ на серию атак типа «хеш-флуд» типа «отказ в обслуживании» (HashDoS) в конце 2011 года. [3]
SipHash спроектирован как некриптографическая хеш-функция . Хотя его можно использовать для обеспечения безопасности, SipHash фундаментально отличается от криптографических хеш-функций, таких как алгоритмы безопасного хеширования (SHA), тем, что он подходит только в качестве кода аутентификации сообщения : хэш-функции с ключом , такой как хеш-код аутентификации сообщения ( HMAC ). То есть SHA спроектирован таким образом, что злоумышленнику сложно найти два сообщения X и Y , такие что SHA( X ) = SHA( Y ), даже если кто угодно может вычислить SHA( X ). Вместо этого SipHash гарантирует, что, увидев X i и SipHash( X i , k ), злоумышленник, не знающий ключа k, не сможет найти (любую информацию о) k или SipHash( Y , k ) для любого сообщения Y ∉ { X i } чего они раньше не видели.
Обзор [ править ]
SipHash вычисляет 64-битный код аутентификации сообщения на основе сообщения переменной длины и 128-битного секретного ключа. Он был разработан, чтобы быть эффективным даже для коротких входных данных, с производительностью, сравнимой с некриптографическими хеш-функциями, такими как CityHash . [4] : 496 [2] это можно использовать для предотвращения атак типа «отказ в обслуживании» на хеш-таблицы («хеш-флудинг»), [5] или для аутентификации сетевых пакетов . Позже был добавлен вариант, который дает 128-битный результат. [6]
Хеш-функция без ключа, такая как SHA, устойчива к коллизиям только в том случае, если используется весь вывод. Если он используется для генерации небольшого результата, например индекса в хэш-таблице практического размера, то ни один алгоритм не может предотвратить коллизии; злоумышленнику нужно сделать столько попыток, сколько существует возможных результатов.
Например, предположим, что сетевой сервер спроектирован так, чтобы иметь возможность одновременно обрабатывать до миллиона запросов. Он отслеживает входящие запросы в хеш-таблице с двумя миллионами записей, используя хеш-функцию для сопоставления идентификационной информации каждого запроса с одной из двух миллионов возможных записей таблицы. Злоумышленнику, знающему хеш-функцию, достаточно ввести в нее произвольные входные данные; один из двух миллионов будет иметь определенное значение хеш-функции. Если злоумышленник теперь отправит на сервер несколько сотен запросов, выбранных с одинаковым значением хеш-функции, это приведет к большому количеству коллизий хеш-функций, замедляя (или, возможно, останавливая) сервер с эффектом, аналогичным потоку пакетов. многомиллионному Запросы. [7]
Используя ключ, неизвестный злоумышленнику, хэш-функция с ключом, такая как SipHash, предотвращает атаки такого рода. Хотя можно добавить ключ к неключевой хэш-функции ( HMAC — популярный метод), SipHash гораздо более эффективен.
Функции в семействе SipHash обозначаются как SipHash- c - d , где c — количество раундов на блок сообщения, а d — количество раундов финализации. Рекомендуемые параметры: SipHash-2-4 для лучшей производительности и SipHash-4-8 для консервативной безопасности. В нескольких языках используется Siphash-1-3 для обеспечения производительности с риском пока неизвестных DoS-атак. [8]
Эталонная реализация была выпущена как общедоступное программное обеспечение под лицензией CC0 . [6]
Использование [ править ]
SipHash используется в хэш-таблиц реализациях различного программного обеспечения: [9]
- Языки программирования
- Хаскелл
- JavaScript
- Node.js [10]
- V8 (движок JavaScript) (доступен как опция во время компиляции) [11]
- Node.js [10]
- OCaml [12]
- Perl 5 (доступен как опция во время компиляции ) [13]
- Python (начиная с версии 3.4, [14] SipHash 1-3 с версии 3.11 [15] )
- Раку [16]
- Руби (SipHash 1-3) [17]
- Ржавчина (SipHash 1-3) [18]
- Быстрый
Следующие программы используют SipHash другими способами:
- Биткойн для коротких идентификаторов транзакций [23]
- Bloomberg BDE как C++ объектов хэшер [24]
- Межпланетная файловая система (IPFS) за семь фильтров Блума . хешей [25]
Реализации
- C (эталонная реализация, являющаяся общественным достоянием)
- C++ (Wassenberg & Alakuijala 2017, часть их работы «highwayhash»)
- С#
- Крипто++
- Идти
- Хаскелл
- JavaScript
- ПикоЛисп
- Ржавчина
- Быстрый
- Верилог
- VHDL
См. также [ править ]
- Фильтр Блума (приложение для быстрых хэшей)
- Криптографическая хэш-функция
- Хэш-функция
- Код аутентификации сообщения
- Список хэш-функций
Ссылки [ править ]
- ^ Добрауниг, Кристоф; Мендель, Флориан; Шлеффер, Мартин (29 ноября 2014 г.). «Дифференциальный криптоанализ SipHash». Избранные области криптографии -- SAC 2014 . Конспекты лекций по информатике. Том. 8781. стр. 165–182. дои : 10.1007/978-3-319-13051-4_10 . ISBN 978-3-319-13050-7 . Проверено 28 февраля 2018 г.
- ^ Перейти обратно: а б Жан-Филипп Омассон и Дэниел Дж. Бернштейн (18 сентября 2012 г.). «SipHash: быстрый PRF с коротким вводом» . Архив электронной печати по криптологии .
- ^ Леннон, Майк (28 декабря 2011 г.). «Уязвимость хеш-таблицы делает возможным широкомасштабные DDoS-атаки» . Неделя Безопасности .
- ^ Итак, Вон; Нарайанан, Ашок; Оран, Дэвид; Стапп, Марк (2013). «Именованная сеть передачи данных на маршрутизаторе». Материалы конференции ACM SIGCOMM 2013 по SIGCOMM . стр. 495–496. дои : 10.1145/2486001.2491699 . ISBN 9781450320566 . S2CID 1457918 . Проверено 28 февраля 2018 г.
Недавно предложенный SipHash [1] предлагает хороший баланс, поскольку он обеспечивает устойчивость к коллизиям и производительность, сравнимую с некриптохешами.
- ^ Омассон, Жан-Филипп; Бернштейн, Дэниел Дж .; Босслет, Мартин (8 ноября 2012 г.). Перезагрузка DoS-затопления хэшем: атаки и защита (PDF) . Форум по безопасности приложений – Западная Швейцария , 2012 г. Архивировано из оригинала (PDF) 13 сентября 2013 г.
- ^ Перейти обратно: а б «SipHash: быстрый PRF с коротким вводом» . 01.08.2016. Архивировано из оригинала 02 февраля 2017 г. Проверено 21 января 2017 г.
Интеллектуальная собственность: нам неизвестны какие-либо патенты или заявки на патенты, имеющие отношение к SipHash, и мы не планируем подавать на них заявки. Справочный код SipHash выпущен под лицензией CC0, лицензией, аналогичной общедоступной.
- ^ Кросби, Скотт А.; Уоллах, Дэн С. (6 августа 2003 г.). Отказ в обслуживании посредством атак, усложняющих алгоритм . Симпозиум по безопасности Usenix . Вашингтон
- ^ Омассон, Жан-Филипп (veorq) (12 ноября 2015 г.). «Комментарий: измените Siphash, чтобы использовать один из более быстрых вариантов алгоритма (Siphash13, Highwayhash) · Проблема № 29754 · ржавчина-lang/rust» . Гитхаб . Проверено 28 февраля 2024 г.
Дизайнер SipHash здесь, не изменил своего мнения о SipHash-1-3 :-) [...] Есть «отличитель» на 4 раундах [...] или, проще говоря, статистическая погрешность, которая проявляется при конкретный шаблон различия во входных данных 4-раундовой последовательности. Но вы не можете внедрить этот шаблон в SipHash-1-3, потому что вы не контролируете все состояние. И даже если бы вы могли внедрить этот шаблон, предвзятостью все равно нельзя было бы воспользоваться.
- ^ Омассон, Жан-Филипп; Бернштейн, Дэниел Дж. (01 августа 2016 г.). «SipHash: быстрый PRF с коротким вводом, пользователи» . Архивировано из оригинала 02 февраля 2017 г. Проверено 21 января 2017 г.
- ^ Вагг, Род (28 февраля 2019 г.). «сборка: включить SipHash v8 для создания начального хэша» . Нод.js. Получено 21 октября 2021 г. - через GitHub .
- ^ Го, Ян (9 января 2019 г.). «При желании используйте полусифаш для целочисленного хеширования» . В8 . Проверено 21 октября 2021 г.
- ^ «Библиотека OCaml: Hashtbl» . Проверено 17 февраля 2024 г.
- ^ «Безопасность Perl – атаки, усложняющие алгоритм» . Perldoc-браузер . 16 мая 2016 г. Проверено 21 октября 2021 г.
- ^ Хаймс, Кристиан (27 сентября 2013 г.). «PEP 456 — Безопасный и взаимозаменяемый алгоритм хеширования» . Проверено 21 января 2017 г.
- ^ «Переход на SipHash-1-3 #73596» .
- ^ Маквей, Саманта (16 июля 2018 г.). «Реализовать SipHash, использовать в качестве нашей функции хеширования с 64-битными хеш-значениями» . МоарВМ . Получено 16 июля 2018 г. - через GitHub .
- ^ https://bugs.ruby-lang.org/issues/13017
- ^ Макартур, Шон (30 июня 2016 г.). «std: используйте siphash-1-3 для HashMap» . Ржавчина . Получено 21 января 2017 г. - через GitHub .
- ^ Пёттеринг, Леннарт (22 декабря 2013 г.). «shared: переключить нашу реализацию хэш-таблицы на SipHash» . системад . Получено 21 января 2017 г. - через freedesktop.org .
- ^ https://github.com/openbsd/src/blob/master/sys/crypto/siphash.h
- ^ https://svnweb.freebsd.org/base/head/sys/crypto/siphash/
- ^ https://github.com/WireGuard/wg-dynamic/commit/360b9c8c8b4c4364b755dc0935f05e4ba4429cb0
- ^ «Компактное блочное реле» . Гитхаб . Проверено 27 сентября 2018 г.
- ^ bslh_siphashalgorithm.h
- ^ https://github.com/ipfs/bbloom/blob/73e3f896a4f8bbed8589df6ff5c28ebfbd728e31/sipHash.go#L15
Внешние ссылки [ править ]
- Жан-Филипп Омассон; Дэниел Дж. Бернштейн (01 августа 2016 г.). «SipHash: быстрый PRF с коротким вводом — страница проекта» . Гитхаб .
- Жан-Филипп Омассон; Дэниел Дж. Бернштейн (18 сентября 2012 г.). «SipHash: быстрый PRF с коротким вводом» (PDF) .
- Жан-Филипп Омассон; Дэниел Дж. Бернштейн (15 августа 2012 г.). «SipHash: быстрый PRF с коротким вводом - слайды презентации» (PDF) .
- Жан-Филипп Омассон; Дэниел Дж. Бернштейн; Мартин Босслет (29 декабря 2012 г.). «Перезагрузка DoS с хэш-флудом: атаки и защита» .
- «Хеширование» . Книга производительности Rust . – описывает, когда SipHash недостаточно быстр
