SipHash является дополнением поворота-XOR (ARX) на основе семейства псевдослучайных функций , созданных Жан-Филипп Aumasson и Daniel J. Bernstein в 2012 году [1] : 165 [2] в ответ на волна «хэш наводнения» denial- служебных атак в конце 2011 года. [3]
Хотя 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 для консервативной безопасности.
Эталонная реализация была выпущена в качестве публичного домена программного обеспечения под CC0 . [6]
Использование [ править ]
SipHash используется в реализациях хеш-таблиц различного программного обеспечения: [8]
- Perl 5 (доступен как опция во время компиляции) [9]
- Python (начиная с версии 3.4) [10]
- Раку [11]
- Рубин
- Ржавчина [12]
- systemd [13]
- OpenDNS
- Haskell
- OpenBSD
- Быстрый
- Биткойн для коротких идентификаторов транзакций [14]
- Bloomberg BDE как хешер объектов C ++ [15]
- IPFS как хэш фильтра Блума
Реализации
- C (эталонная реализация общественного достояния)
- Ржавчина
- Крипто ++
- C #
- Haskell
- JavaScript
- VHDL
- Verilog
- Идти
- Быстрый
- ПикоЛисп
См. Также [ править ]
- Фильтр Блума (приложение для быстрых хешей)
- Криптографическая хеш-функция
- Хеш-функция
- Код аутентификации сообщения
- Список хеш-функций
Ссылки [ править ]
- ^ Добрауниг, Кристоф; Мендель, Флориан; Шлеффер, Мартин (29 ноября 2014 г.). Дифференциальный криптоанализ SipHash . Международный семинар по избранным направлениям криптографии . Конспект лекций по информатике. 8781 . С. 165–182. DOI : 10.1007 / 978-3-319-13051-4_10 . ISBN 978-3-319-13050-7. Проверено 28 февраля 2018 .
- ^ a b Жан-Филипп Аумассон и Даниэль Дж. Бернштейн ( 18 сентября 2012 г. ). «SipHash: быстрый PRF с коротким вводом» .
- ^ Леннон, Майк (2011-12-28). «Уязвимость хеш-таблицы делает возможными широкомасштабные DDoS-атаки» . SecurityWeek .
- ^ Итак, Вон; Нараянан, Ашок; Оран, Дэвид; Стэпп, Марк (2013). Именованная сеть передачи данных на маршрутизаторе: пересылка со скоростью 20 Гбит / с и выше . Материалы конференции ACM SIGCOMM 2013 по SIGCOMM . п. 495. DOI : 10,1145 / 2486001,2491699 . ISBN 9781450320566. S2CID 1457918 . Проверено 28 февраля 2018 .
Недавно предложенный SipHash [1] предлагает хороший баланс, поскольку он обеспечивает устойчивость к коллизиям и сопоставимую производительность с некриптографическими хэшами.
- ^ Aumasson, Жан-Филипп; Бернштейн, Дэниел Дж .; Бослет, Мартин (2012-11-08). Перезагрузка DoS-атак с хеш-флудом: атаки и защиты (PDF) . Применение Форум безопасности - Западная Швейцария 2012 .
- ^ a b "SipHash: быстрый PRF с коротким вводом" . 2016-08-01 . Проверено 21 января 2017 .
Интеллектуальная собственность: нам не известны какие-либо патенты или патентные заявки, относящиеся к SipHash, и мы не планируем подавать заявки на них.
Ссылочный код SipHash выпущен под лицензией CC0, лицензией, подобной общедоступной.
- ^ Кросби, Скотт А .; Уоллах, Дэн С. (2003-08-06). Отказ в обслуживании посредством атак с алгоритмической сложностью . Симпозиум по безопасности Usenix . Вашингтон, округ Колумбия
- ^ Жан-Филипп Аумассон; Дэниел Дж. Бернштейн (2016-08-01). «SipHash: быстрый PRF с коротким вводом, пользователи» . Проверено 21 января 2017 .
- ^ "Безопасность Perl - атаки на алгоритмическую сложность" . 2016-05-16 . Проверено 21 января 2017 .
- ^ Кристиан Heimes (2013-09-27). «PEP 456 - Безопасный и взаимозаменяемый алгоритм хеширования» . Проверено 21 января 2017 .
- ^ «Внедрить SipHash, использовать в качестве нашей хеш-функции с 64-битными хеш-значениями» . 2018-07-16 . Проверено 16 июля 2018 .
- ^ Грейдон Хор (2012-07-24). «Добавить core :: hash, содержащий реализацию SipHash-2-4. Re: # 1616 и # 859» . Проверено 21 января 2017 .
- ^ Поттеринг (2013-12-22). "shared: переключить нашу реализацию хеш-таблицы на SipHash" . Проверено 21 января 2017 .
- ^ "Компактное блочное реле" . GitHub . Проверено 27 сентября 2018 .
- ^ bslh_siphashalgorithm.h
Внешние ссылки [ править ]
- Жан-Филипп Аумассон; Дэниел Дж. Бернштейн (2016-08-01). «SipHash: быстрый PRF с коротким вводом - страница проекта» .
- Жан-Филипп Аумассон; Дэниел Дж. Бернштейн (18 сентября 2012 г.). «SipHash: быстрый PRF с коротким вводом» (PDF) .
- Жан-Филипп Аумассон; Дэниел Дж. Бернштейн (2012-08-15). «SipHash: быстрый PRF с коротким вводом - слайды презентации» (PDF) .
- Жан-Филипп Аумассон; Дэниел Дж. Бернштейн; Мартин Бослет (29 декабря 2012 г.). «Перезагрузка DoS с хеш-флудом: атаки и защиты» .
- «Хеширование» . Книга производительности Rust . - описывает, когда SipHash недостаточно быстр