Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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
  • Идти
  • Быстрый
  • ПикоЛисп

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

  • Фильтр Блума (приложение для быстрых хешей)
  • Криптографическая хеш-функция
  • Хеш-функция
  • Код аутентификации сообщения
  • Список хеш-функций

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

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

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

  • Жан-Филипп Аумассон; Дэниел Дж. Бернштейн (2016-08-01). «SipHash: быстрый PRF с коротким вводом - страница проекта» .
  • Жан-Филипп Аумассон; Дэниел Дж. Бернштейн (18 сентября 2012 г.). «SipHash: быстрый PRF с коротким вводом» (PDF) .
  • Жан-Филипп Аумассон; Дэниел Дж. Бернштейн (2012-08-15). «SipHash: быстрый PRF с коротким вводом - слайды презентации» (PDF) .
  • Жан-Филипп Аумассон; Дэниел Дж. Бернштейн; Мартин Бослет (29 декабря 2012 г.). «Перезагрузка DoS с хеш-флудом: атаки и защиты» .
  • «Хеширование» . Книга производительности Rust . - описывает, когда SipHash недостаточно быстр