Некриптографическая хэш-функция

Некриптографические хеш-функции ( NCHF ) — это хеш-функции, предназначенные для приложений, которым не нужны строгие требования безопасности криптографических хэш-функций (например, устойчивость к прообразу ), и поэтому они могут быть быстрее и менее ресурсоемкими. Типичные примеры некриптографических хэшей, оптимизированных для ЦП, включают FNV-1a , Murmur3 . Некоторые из некриптографических хэш-функций используются в криптографических приложениях (обычно в сочетании с другими криптографическими примитивами), в этом случае они описываются как универсальные хэш-функции .

Приложения и требования

Среди типичных применений некриптографических хэш-функций — фильтры Блума , хеш-таблицы и эскизы подсчета . Эти приложения требуют, помимо скорости, равномерного распределения и лавинных свойств. Устойчивость к коллизиям — это дополнительная функция, которая может быть полезна против с переполнением хэша атак ; простые NCHF, такие как проверка циклическим избыточным кодом (CRC), по существу не имеют устойчивости к коллизиям. и, следовательно, не может использоваться с входными данными, открытыми для манипуляций со стороны злоумышленника.

NCHF используются в различных системах: лексических анализаторах , компиляторах , базах данных , сетях связи , видеоиграх, DNS-серверах , файловых системах — везде, где требуется найти информацию очень быстро (желательно за время O(1) , что позволит также добиться идеальной масштабируемости ).

Эстебанес и др. перечислить «наиболее важные» NCHF:

• Хэш-функция Фаулера-Нолла-Во (FNV) была создана Гленном Фаулером и Фонг Во в 1991 году при участии Лэндона Курта Нолла . FNV с двумя его вариантами, FNV-1 и FNV-1a, очень широко используется в программном обеспечении, начиная от ОС Linux и FreeBSD , DNS-серверов, NFS до Twitter , PlayStation2 и консоли Xbox ;
• Lookup3 был создан Робертом Дженкинсом . Хэш также широко используется и его можно найти в PostgreSQL , Linux, Perl , Ruby и Infoseek ;
• SuperFastHash был создан Полом Шейем с использованием идей FNV и Lookup3, одной из целей которого была высокая степень лавинного эффекта. Хэш используется в WebKit (часть Safari и Google Chrome );
• MurmurHash 2 был создан Остином Эпплби в 2008 году и используется в libmemcached , Maatkit и Apache Hadoop ;
• DJBX33A («Дэниел Дж. Бернштейн, Times 33 с дополнением»). Эта очень простая функция умножения и сложения была предложена Дэниелом Дж. Бернштейном . Это быстро и эффективно во время инициализации. Многие среды программирования на базе PHP 5 , Python , ASP.NET используют варианты этого хеша. Хэш легко затопить , обнажая серверы;
• BuzHash был создан Робертом Узгалисом в 1992 году. Он построен на основе таблицы подстановки и может допускать крайне искаженное распределение входных данных;
• DEK — это ранний мультипликативный хеш, основанный на предложении Дональда Э. Кнута и являющийся одним из старейших хешей, которые до сих пор используются.

Дизайн

Некриптографические хэш-функции, оптимизированные для программного обеспечения, часто включают операцию умножения. Поскольку аппаратное умножение требует ресурсов и ограничивает частоту, ASIC были предложены более удобные для конструкции, включая SipHash (который имеет дополнительное преимущество, заключающееся в возможности использования секретного ключа для аутентификации сообщений ), NSGAhash и XORhash. Хотя технически облегченную криптографию можно использовать для тех же приложений, задержка ее алгоритмов обычно слишком высока из-за большого количества раундов . Сатисан и др. предлагают использовать версии облегченных хэшей и шифров с сокращенным циклом в качестве некриптографических хеш-функций.

Многие NCHF имеют относительно небольшой размер результата (например, 64 бита для SipHash или даже меньше): большой размер результата не увеличивает производительность целевых приложений, но замедляет расчет, поскольку необходимо сгенерировать больше битов.

См. также

• Список некриптографических хэш-функций

Источники

• Сатисан, Ариш; Бисманс, Йелле; Класен, Томас; Влиген, Джо; Ментенс, Неле (апрель 2023 г.). «Оптимизированные алгоритмы и архитектуры для быстрых аппаратных некриптографических хэш-функций». Микропроцессоры и микросистемы . 98 : 104782. дои : 10.1016/j.micpro.2023.104782 . ISSN   0141-9331 .
• Эстебанес, Сезар; Саез, Яго; Ресио, Густаво; Исаси, Педро (28 января 2013 г.). «Производительность наиболее распространенных некриптографических хэш-функций» (PDF) . Программное обеспечение: практика и опыт . 44 (6): 681–698. дои : 10.1002/сп.2179 . ISSN   0038-0644 .
• Штамп, Марк (8 ноября 2011 г.). «Некриптографические хеши» . Информационная безопасность: принципы и практика (2-е изд.). Джон Уайли и сыновья. ISBN  978-1-118-02796-7 . OCLC   1039294381 .
• Патгири, Рипон; Наяк, Сабузима; Муппаланени, Нареш Бабу (25 апреля 2023 г.). Фильтр Блума: структура данных для компьютерных сетей, больших данных, облачных вычислений, Интернета вещей, биоинформатики и не только . Академическая пресса. стр. 37–38. ISBN  978-0-12-823646-8 . OCLC   1377693258 .
• Миттельбах, Арно; Фишлин, Марк (2021). «Некриптографическое хеширование». Теория хеш-функций и случайные оракулы . Чам: Международное издательство Springer. стр. 303–334. дои : 10.1007/978-3-030-63287-8_7 . ISBN  978-3-030-63286-1 .