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

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

Заявки и требования

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

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

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

• Хэш-функция Фаулера –Нолла–Во (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 («Daniel J. Bernstein, Times 33 with Addition»). Эта очень простая функция умножения и сложения была предложена Daniel J. Bernstein . Она быстра и эффективна во время инициализации. Многие среды программирования на основе PHP 5 , Python и ASP.NET используют варианты этого хеша. Хэш легко затопить , выставив серверы напоказ.
• BuzHash был создан Робертом Узгалисом в 1992 году. Он разработан на основе таблицы замен и может выдерживать крайне неравномерные распределения на входе.
• DEK — это ранний мультипликативный хеш, основанный на предложении Дональда Э. Кнута , и один из старейших хешей, который до сих пор используется.

Дизайн

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

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

Смотрите также

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

Ссылки

1. Эстебанез и др. 2013.
2. Сатисан и др. 2023, с. 1.
3. Sateesan et al. 2023, с. 2.
4. Миттельбах и Фишлин 2021, с. 303.
5. Марка 2011 г.
6. Эстебанес и др. 2013, с. 1.
7. Эстебанес и др. 2013, стр. 3–4.
8. Патгири, Наяк и Муппаланени, 2023, стр. 37–38.

Источники

• Sateesan, Arish; Biesmans, Jelle; Claesen, Thomas; Vliegen, Jo; Mentens, Nele (апрель 2023 г.). «Оптимизированные алгоритмы и архитектуры для быстрых некриптографических хэш-функций в оборудовании». Микропроцессоры и микросистемы . 98 : 104782. doi : 10.1016/j.micpro.2023.104782. ISSN  0141-9331.
• Эстебанес, Сезар; Саез, Яго; Ресио, Густаво; Исаси, Педро (28 января 2013 г.). «Производительность наиболее распространенных некриптографических хеш-функций» (PDF) . Программное обеспечение: практика и опыт . 44 (6): 681–698. дои : 10.1002/спе.2179. ISSN  0038-0644.
• Stamp, Mark (8 ноября 2011 г.). «Некриптографические хэши». Информационная безопасность: принципы и практика (2-е изд.). John Wiley & Sons. ISBN 978-1-118-02796-7. OCLC  1039294381.
• Патгири, Рипон; Наяк, Сабузима; Муппаланени, Нареш Бабу (25 апреля 2023 г.). Фильтр Блума: структура данных для компьютерных сетей, больших данных, облачных вычислений, Интернета вещей, биоинформатики и не только. Academic Press. стр. 37–38. ISBN 978-0-12-823646-8. OCLC  1377693258.
• Миттельбах, Арно; Фишлин, Марк (2021). «Некриптографическое хеширование». Теория хеш-функций и случайных оракулов . Cham: Springer International Publishing. стр. 303–334. doi :10.1007/978-3-030-63287-8_7. ISBN 978-3-030-63286-1.