Какой алгоритм хеширования выбрать

Обновлено: 03.07.2024

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

В наши дни существует много криптографических алгоритмов. Они бывают разные и отличаются по сложности, разрядности, криптографической надежности, особенностям работы. Алгоритмы хеширования — идея не новая. Они появилась более полувека назад, причем за много лет с принципиальной точки зрения мало что изменилось. Но в результате своего развития хеширование данных приобрело много новых свойств, поэтому его применение в сфере информационных технологий стало уже повсеместным.

Что такое хеш (хэш, hash)?

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

Основная идея используемых в данном случае функций — применение детерминированного алгоритма. Речь идет об алгоритмическом процессе, выдающем уникальный и предопределенный результат при получении входных данных. То есть при приеме одних и тех же входных данных будет создаваться та же самая строка фиксированной длины (использование одинакового ввода каждый раз приводит к одинаковому результату). Детерминизм — важное свойство этого алгоритма. И если во входных данных изменить хотя бы один символ, будет создан совершенно другой хэш.

Убедиться в этом можно на любом онлайн-генераторе. Набрав слово «Otus» и воспользовавшись алгоритмом sha1 (Secure Hashing Algorithm), мы получим хеш 7576750f9d76fab50762b5987739c18d99d2aff7. При изменении любой буквы изменится и результат, причем изменится полностью. Мало того, если просто поменять регистр хотя бы одной буквы, итог тоже будет совершенно иным: если написать «otus», алгоритм хэш-функции отработает со следующим результатом: 1bbd70dc1b6fc84e5617ca8703c72c744b3b4fc1. Хотя общие моменты все же есть: строка всегда состоит из сорока символов.

В предыдущем примере речь шла о применении хэш-алгоритма для слова из 4 букв. Но с тем же успехом можно вставить слово из 1000 букв — все равно после обработки данных на выходе получится значение из 40 символов. Аналогичная ситуация будет и при обработке полного собрания сочинений Льва Толстого.

Криптостойкость функций хеширования

Говоря о криптостойкости, предполагают выполнение ряда требований. То есть хороший алгоритм обладает несколькими свойствами: — при изменении одного бита во входных данных, должно наблюдаться изменение всего хэша; — алгоритм должен быть устойчив к коллизиям; — алгоритм должен быть устойчив к восстановлению хешируемых данных, то есть должна обеспечиваться высокая сложность нахождения прообраза, а вычисление хэша не должно быть простым.

Проблемы хэшей

Одна из проблем криптографических функций хеширования — неизбежность коллизий. Раз речь идет о строке фиксированной длины, значит, существует вероятность, что для каждого ввода возможно наличие и других входов, способных привести к тому же самому хешу. В результате хакер может создать коллизию, позволяющую передать вредоносные данные под видом правильного хэша.

Цель хороших криптографических функций — максимально усложнить вероятность нахождения способов генерации входных данных, хешируемых с одинаковым значением. Как уже было сказано ранее, вычисление хэша не должно быть простым, а сам алгоритм должен быть устойчив к «атакам нахождения прообраза». Необходимо, чтобы на практике было чрезвычайно сложно (а лучше — невозможно) вычислить обратные детерминированные шаги, которые предприняты для воспроизведения созданного хешем значения.

Если S = hash (x), то, в идеале, нахождение x должно быть практически невозможным.

Алгоритм MD5 и его подверженность взлому

Атака дня рождения

Если поместить 23 человека в одну комнату, можно дать 50%-ную вероятность того, что у двух человек день рождения будет в один и тот же день. Если же количество людей довести до 70-ти, вероятность совпадения по дню рождения приблизится к 99,9 %. Есть и другая интерпретация: если голубям дать возможность сесть в коробки, при условии, что число коробок меньше числа голубей, окажется, что хотя бы в одной из коробок находится более одного голубя.

Вывод прост: если есть фиксированные ограничения на выход, значит, есть и фиксированная степень перестановок, на которых существует возможность обнаружить коллизию.

Когда разговор идет о сопротивлении коллизиям, то алгоритм MD5 действительно очень слаб. Настолько слаб, что даже бытовой Pentium 2,4 ГГц сможет вычислить искусственные хеш-коллизии, затратив на это чуть более нескольких секунд. Всё это в ранние годы стало причиной утечки большого количества предварительных MD5-прообразов.

SHA1, SHA2, SHA3

Secure Hashing Algorithm (SHA1) — алгоритм, созданный Агентством национальной безопасности (NSA). Он создает 160-битные выходные данные фиксированной длины. На деле SHA1 лишь улучшил MD5 и увеличил длину вывода, а также увеличил число однонаправленных операций и их сложность. Однако каких-нибудь фундаментальных улучшений не произошло, особенно когда разговор шел о противодействии более мощным вычислительным машинам. Со временем появилась альтернатива — SHA2, а потом и SHA3. Последний алгоритм уже принципиально отличается по архитектуре и является частью большой схемы алгоритмов хеширования (известен как KECCAK — «Кетч-Ак»). Несмотря на схожесть названия, SHA3 имеет другой внутренний механизм, в котором используются случайные перестановки при обработке данных — «Впитывание» и «Выжимание» (конструкция «губки»).

Что в будущем?

Вне зависимости от того, какие технологии шифрования и криптографические новинки будут использоваться в этом направлении, все сводится к решению одной из двух задач: 1) увеличению сложности внутренних операций хэширования; 2) увеличению длины hash-выхода данных с расчетом на то, что вычислительные мощности атакующих не смогут эффективно вычислять коллизию.

И, несмотря на появление в будущем квантовых компьютеров, специалисты уверены, что правильные инструменты (то же хэширование) способны выдержать испытания временем, ведь ни что не стоит на месте. Дело в том, что с увеличением вычислительных мощностей снижается математическая формализация структуры внутренних алгоритмических хэш-конструкций. А квантовые вычисления наиболее эффективны лишь в отношении к вещам, имеющим строгую математическую структуру.

Одним из ключевых слов, которые новички слышат, когда узнают о блокчейне, являются понятия хэша и алгоритма хэширования, которые кажутся распространёнными для безопасности. Запуск децентрализованной сети и консенсуса, такой как биткойн или сеть эфириум с десятками тысяч узлов, соединенных через p2p, требует, как “надежности”, так и эффективности проверки. То есть, эти системы нуждаются в способах кодирования информации в компактном формате, позволяющем обеспечить безопасную и быструю проверку ее участниками

Даже изменение одного символа во входных данных приведет к совершенно другому хэшу.

Криптографические хэши используются везде, от хранения паролей до систем проверки файлов. Основная идея состоит в том, чтобы использовать детерминированный алгоритм (алгоритмический процесс, который выдает уникальный и предопределенный результат для задачи входных данных), который принимает один вход и создает строку фиксированной длины каждый раз. То есть, использование одного и того же ввода всегда приводит к одному и тому же результату. Детерминизм важен не только для хэшей, но и для одного бита, который изменяется во входных данных, создавая совершенно другой хэш. Проблема с алгоритмами хэширования - неизбежность коллизий. То есть, тот факт, что хэши являются строкой фиксированной длины, означает, что для каждого ввода, который мы можем себе представить, есть другие возможные входы, которые приведут к тому же хэшу. Коллизия - это плохо. Это означает, что, если злоумышленник может создавать коллизии, он может передавать вредоносные файлы или данные, как имеющие правильный и неправильный хэш и скрываться под правильным хешем. Цель хорошей хэш-функции состоит в том, чтобы сделать чрезвычайно сложным для злоумышленников найти способы генерации входных данных, которые хешируются с одинаковым значением. Вычисление хэша не должно быть слишком простым, так как это облегчает злоумышленникам искусственное вычисление коллизий. Алгоритмы хэширования должны быть устойчивы к «атакам нахождения прообраза». То есть, получая хеш, было бы чрезвычайно сложно вычислить обратные детерминированные шаги, предпринятые для воспроизведения значения, которое создало хэш (т.е нахождение прообраза).

Учитывая S = hash (x), найти X должно быть почти невозможно.

Напомним, что «хорошие» алгоритмы хэширования имеют следующие свойства:

Изменение одного бита во входных данных должно создать эффект изменения всего хеша;
Вычисления хеша не должно быть слишком простым, высокая сложность нахождения прообраза;
Должен иметь очень низкую вероятность коллизии;

Вы когда-нибудь слышали о том, что если вы поместите 23 человека в комнату, есть 50% шанс, что у двух из них будет один и тот же день рождения? Доведение числа до 70 человек в комнате дает вам 99,9% шанс. Если голуби рассажены в коробки, причем число голубей больше числа коробок, то хотя бы в одной из клеток находится более одного голубя. То есть фиксированные ограничения на выход означают, что существует фиксированная степень перестановок, на которых можно найти коллизию.

По крайне мере, один отсек будет иметь внутри 2-ух голубей.

На самом деле MD5 настолько слаб к сопротивлению к коллизиям, что простой бытовой Процессор Pentium 2,4 ГГц может вычислить искусственные хэш-коллизии в течение нескольких секунд. Кроме того, его широкое использование в более ранние дни текущей сети создало тонны утечек MD5 предварительных прообразов в интернете, которые можно найти с помощью простого поиска Google их хэша.

Различия и развитие алгоритмов хеширования Начало: SHA1 и SHA2

NSA (Агентство национальной безопасности) уже давно является пионером стандартов алгоритмов хэширования, с их первоначальным предложением алгоритма Secure Hashing Algorithm или SHA1, создающий 160-битные выходы фиксированной длины. К сожалению, SHA1 просто улучшил MD5, увеличив длину вывода, количество однонаправленных операций и сложность этих односторонних операций, но не дает каких-либо фундаментальных улучшений против более мощных машин, пытающихся использовать различные атаки. Так как мы можем сделать что-то лучше?

В 2006 году Национальный институт стандартов и технологий (NIST) запустил конкурс, чтобы найти альтернативу SHA2, которая будет принципиально отличаться в своей архитектуре, чтобы стать стандартом. Таким образом, SHA3 появился как часть большой схемы алгоритмов хэширования, известной как KECCAK (произносится Кетч-Ак). Несмотря на название, SHA3 сильно отличается своим внутренним механизмом, известным как «конструкция губки», которая использует случайные перестановки для «Впитывания» и «Выжимания» данных, работая в качестве источника случайности для будущих входов, которые входят в алгоритм хэширования.

Когда дело дошло до интеграции алгоритма хеширования в блокчейн протоколы, биткоин использовал SHA256, в то время как Ethereum использовал модифицированный SHA3 (KECCAK256) для своего PoW. Однако важным качеством выбора хэш-функции для блокчейна с использованием доказательства работы является эффективность вычислений указанного хэша. Алгоритм хеширования биткойна SHA256 может быть вычислен достаточно просто с помощью специализированного оборудования, известного как специализированные интегральные схемы (или ASIC). Много было написано об использовании ASIC в майнинг пуле и о том, как они делают протокол направленным на централизацию вычислений. То есть доказательство работы стимулирует группы вычислительно эффективных машин объединяться в пулы и увеличивать то, что мы обозначаем “хэш-мощностью”, или мерой количества хэшей, которые машина может вычислить за интервал времени. Ethereum, выбрал модифицированный SHA3 известный как KECCAK 256. Кроме того, алгоритм PoW в Ethereum - Dagger-Hashimoto, должен был быть трудно вычисляемым для аппаратного обеспечения.

Почему биткоин использует двойное шифрование SHA256?

SHA3 не был единственным прорывом, который вышел из конкурса хеширования NIST в 2006 году. Несмотря на то, что SHA3 выиграл, алгоритм, известный как BLAKE, занял второе место. Для реализации шардинга Ethereum 2.0 использует более эффективное. Алгоритм хэширования BLAKE2b, который является высокоразвитой версией BLAKE от конкурентов, интенсивно изучается за его фантастическую эффективность по сравнению с KECCAK256 при сохранении высокой степени безопасности. Вычисление BLAKE2b фактически в 3 раза быстрее, чем KECCAK на современном процессоре.

Кажется, что независимо от того, что мы делаем, мы просто либо (1) увеличиваем сложность внутренних хеш-операций, либо (2) увеличиваем длину хеш-выхода, надеясь, что компьютеры атакующих не будут достаточно быстрыми, чтобы эффективно вычислять ее коллизию. Мы полагаемся на двусмысленность предварительных прообразов односторонних операций для обеспечения безопасности наших сетей. То есть цель безопасности алгоритма хеширования состоит в том, чтобы сделать как можно более сложным для любого, кто пытается найти два значения, которые хешируются на один и тот же вывод, несмотря на то, что существует бесконечное количество возможных столкновений. «Как насчет будущего квантовых компьютеров? Будут ли алгоритмы хэширования безопасными?» Короткий ответ и текущее понимание заключаются в том, что да, алгоритмы хэширования выдержат испытание временем против квантовых вычислений. То, что квантовые вычисления смогут сломать, - это те проблемы, которые имеют строгую математическую структуру, основанную на аккуратных трюках и теории, такой как шифрование RSA. С другой стороны, алгоритмы хэширования имеют менее формальную структуру во внутренних конструкциях. Квантовые компьютеры действительно дают повышенную скорость в вычислении неструктурированных проблем, таких как хэширование, но в конце концов, они все равно будут грубо атаковать так же, как компьютер сегодня попытается это сделать. Независимо от того, какие алгоритмы мы выбираем для наших протоколов, ясно, что мы движемся к вычислительно-эффективному будущему, и мы должны использовать наше лучшее суждение, чтобы выбрать правильные инструменты для работы и те, которые, мы надеемся, выдержат испытание временем.

Дмитриев Марк - Технический аналитик и управляющий криптоактивами инвестиционного фонда GT Blockchain Investments

Какой алгоритм хеширования лучше всего подходит для уникальности и скорости? Примеры (хороших) применений включают хеш-словари.

Я знаю, что есть такие вещи, как SHA-256 и тому подобное, но эти алгоритмы предназначены для обеспечения безопасности , что обычно означает, что они медленнее, чем алгоритмы, которые менее уникальны . Я хочу, чтобы алгоритм хеширования был быстрым, но оставался достаточно уникальным, чтобы избежать коллизий.

@ Orbling, для реализации хеш-словаря. Таким образом, столкновения должны быть сведены к минимуму, но это не имеет цели безопасности вообще. Обратите внимание, что вам нужно ожидать, по крайней мере, некоторых коллизий в вашей хэш-таблице, в противном случае таблица должна быть огромной, чтобы можно было обрабатывать даже относительно небольшое количество ключей . @zvrba Зависит от алгоритма. bcrypt разработан, чтобы быть медленным.

Я протестировал несколько разных алгоритмов, измеряя скорость и количество столкновений.

Я использовал три разных набора ключей:

Для каждого корпуса было зафиксировано количество столкновений и среднее время, проведенное за хешированием.

Результаты

Каждый результат содержит среднее время хеширования и количество столкновений.

Примечания :

ужасно

SuperFastHash быстр, с вещами, выглядящими довольно рассеянными; Боже мой, число столкновений. Я надеюсь, что парень, который портировал это, понял что-то не так; это довольно плохо
CRC32 довольно хорош . Медленнее, и таблица поиска 1k

Действительно ли случаются столкновения?

Да. Я начал писать свою тестовую программу, чтобы увидеть, действительно ли случаются коллизии хешей - и это не просто теоретическая конструкция. Они действительно случаются

Столкновения ФНВ-1

Столкновения ФНВ-1а

costarring сталкивается с liquid
declinate сталкивается с macallums
altarage сталкивается с zinke
altarages сталкивается с zinkes

Murmur2 столкновения

cataract сталкивается с periti
roquette сталкивается с skivie
shawl сталкивается с stormbound
dowlases сталкивается с tramontane
cricketings сталкивается с twanger
longans сталкивается с whigs

DJB2 столкновения

hetairas сталкивается с mentioner
heliotropes сталкивается с neurospora
depravement сталкивается с serafins
stylist сталкивается с subgenera
joyful сталкивается с synaphea
redescribed сталкивается с urites
dram сталкивается с vivency

DJB2a столкновения

haggadot сталкивается с loathsomenesses
adorablenesses сталкивается с rentability
playwright сталкивается с snush
playwrighting сталкивается с snushing
treponematoses сталкивается с waterbeds

CRC32 столкновения

codding сталкивается с gnu
exhibiters сталкивается с schlager

SuperFastHash столкновения

dahabiah сталкивается с drapability
encharm сталкивается с enclave
grahams сталкивается с gramary
. отсечь 79 столкновений .
night сталкивается с vigil
nights сталкивается с vigils
finks сталкивается с vinic

Randomnessification

Другая субъективная мера - насколько случайным образом распределены хэши. Отображение полученных HashTables показывает, насколько равномерно распределяются данные. Все хеш-функции показывают хорошее распределение при линейном отображении таблицы:

Кроме случаев , когда хэширования число строк ( "1" , "2" , . "216553" ) (например, почтовые индексы ), где модели начинают появляться в большинстве алгоритмов хэширования:

SDBM :

DJB2a :

FNV-1 :

Все, кроме FNV-1a , которые все еще выглядят довольно случайными для меня:

Фактически, Murmur2, кажется, имеет даже лучшую случайность с Numbers чем FNV-1a :

Когда я смотрю на FNV-1a карту «число», я думаю, что вижу тонкие вертикальные узоры. С Murmur я не вижу никаких закономерностей. Как вы думаете?

Дополнительное значение * в таблице обозначает, насколько плоха случайность. С FNV-1a является лучшим, и DJB2x является худшим:

Первоначально я написал эту программу, чтобы решить, нужно ли мне беспокоиться о столкновениях.

И тогда это превратилось в то, что хэш-функции были достаточно случайными.

Алгоритм FNV-1a

Хэш FNV1 поставляется в вариантах, которые возвращают 32, 64, 128, 256, 512 и 1024-битные хэши.

Где константы FNV_offset_basis и FNV_prime зависят от размера возвращаемого хеша:

Все мои результаты с 32-битным вариантом.

FNV-1 лучше, чем FNV-1a?

FNV-1a лучше вокруг. Было больше столкновений с FNV-1a при использовании английского слова corpus:

Теперь сравните строчные и прописные буквы:

В этом случае FNV-1a не «на 400%» хуже, чем FN-1, только на 20% хуже.

Я думаю, что более важным выводом является то, что существует два класса алгоритмов, когда речь идет о столкновениях:

редкие столкновения : FNV-1, FNV-1a, DJB2, DJB2a, SDBM
Общие коллизии : SuperFastHash, Loselose

И затем, насколько равномерно распределены хэши:

выдающийся дистрибутив: Murmur2, FNV-1a, SuperFastHas
отличное распределение: FNV-1
хорошее распределение: SDBM, DJB2, DJB2a
ужасное распределение: Loselose

Обновить

Ропщите? Конечно почему нет

Обновить

@whatshisname задалась вопросом, как будет работать CRC32 , добавила числа в таблицу.

CRC32 довольно хорош . Мало коллизий, но медленнее, и накладные расходы таблицы поиска 1k.

Отсеки все ошибочные материалы о распространении CRC - мой плохой

До сегодняшнего дня я собирался использовать FNV-1a в качестве своего фактического алгоритма хэширования хеш-таблицы. Но теперь я перехожу на Murmur2:

Быстрее
Лучшая рандомизация всех классов ввода

И я действительно, очень надеюсь, что что-то не так с SuperFastHash алгоритмом, который я нашел ; это слишком плохо, чтобы быть таким же популярным.

(1) - SuperFastHash имеет очень плохие свойства столкновения, которые были задокументированы в другом месте.

Так что, думаю, это не только я.

Обновление: я понял, почему Murmur быстрее, чем другие. MurmurHash2 работает с четырьмя байтами одновременно. Большинство алгоритмов побайтно :

Это означает, что когда ключи становятся длиннее, Murmur получает шанс сиять.

Обновить

GUID разработаны для того, чтобы быть уникальными, а не случайными

Даже алгоритм GUID Версии 4 не гарантированно непредсказуем, поскольку алгоритм не определяет качество генератора случайных чисел. Статья Википедии для GUID содержит первичное исследование, которое предполагает, что будущие и предыдущие GUID могут быть предсказаны на основе знания состояния генератора случайных чисел, поскольку генератор не является криптографически стойким.

Randomess - это не то же самое, что избегать столкновений; вот почему было бы ошибкой пытаться изобрести свой собственный алгоритм «хэширования», взяв некоторое подмножество «случайного» guid:

Примечание : опять же, в кавычки я помещаю «случайный GUID» , потому что это «случайный» вариант GUID. Более точное описание будет Type 4 UUID . Но никто не знает, что типа 4 или 1, 3 и 5. Так что проще назвать их «случайными» GUID.

Было бы действительно интересно посмотреть, как сравнивается SHA, а не потому, что он является хорошим кандидатом для алгоритма хеширования, но было бы очень интересно увидеть, как любой криптографический хэш сравнивается с этим, созданным для алгоритмов скорости. Новый хэш по имени 'xxHash' от Yann Collet недавно делал раунды. Я всегда с подозрением отношусь к новому хешу. Было бы интересно увидеть это в вашем сравнении (если вы не устали от людей, предлагающих добавлять случайные хэши, о которых они слышали . ) Привет Ян, моя реализация SuperFastHash в Delphi верна. При реализации я создал набор тестов в C и Delphi, чтобы сравнить результаты моей реализации и эталонной реализации. Там нет никаких различий. Итак, что вы видите, так это хеш хэш . (Вот почему я также опубликовал реализацию MurmurHash : landman-code.blogspot.nl/2009/02/… ) Знает ли автор, что это не просто потрясающий ответ - это фактический справочный ресурс в мире по этому вопросу? В любое время мне нужно иметь дело с хэшами, это решает мою проблему так быстро и авторитетно, что мне больше ничего не нужно. Это довольно очевидно, но стоит отметить, что для того, чтобы гарантировать отсутствие коллизий, ключи должны быть того же размера, что и значения, если только нет ограничений на значения, на которых алгоритм может извлечь выгоду. @ devios1 Ваше утверждение не имеет смысла. Во-первых, значения в хэш-таблице, совершенные или нет, не зависят от ключей. Во-вторых, идеальная хеш-таблица - это просто линейный массив значений, индексируемый результатом функции, которая была создана таким образом, чтобы все индексы были уникальными. @DavidCary Ничто по вашей ссылке не поддерживает вашу заявку. Возможно, вы перепутали O (1) с «без столкновений», но это совсем не одно и то же. Конечно, идеальное хеширование гарантирует отсутствие коллизий, но для этого необходимо, чтобы все ключи были известны заранее и их было относительно немного. (Но смотрите ссылку на cmph выше.)

Вот список хеш-функций, но короткая версия:

Если вы просто хотите иметь хорошую хеш-функцию и не можете ждать, djb2 это одна из лучших строковых хеш-функций, которую я знаю. Имеет отличное распределение и скорость для множества различных наборов ключей и размеров таблиц.

DJB довольно плох с точки зрения производительности и распространения. Я бы не использовал это сегодня. @ConradMeyer Бьюсь об заклад, DJB может быть ускорен в три раза, как и в этом моем вопросе, и тогда он, вероятно, побьет большинство используемых алгоритмов. По поводу раздачи я согласен. Хеш, создающий коллизии даже для двухбуквенных строк, не может быть действительно хорошим.

CityHash от Google - это алгоритм, который вы ищете. Это не хорошо для криптографии, но хорошо для генерации уникальных хэшей.

Прочитайте блог для получения более подробной информации и код доступен здесь .

CityHash написан на C ++. Там также есть обычный порт C .

Все функции CityHash настроены для 64-битных процессоров. Тем не менее, они будут работать (за исключением новых, которые используют SSE4.2) в 32-битном коде. Они не будут очень быстрыми. Вы можете использовать Murmur или что-то еще в 32-битном коде.

Я составил краткое сравнение скорости различных алгоритмов хэширования при хэшировании файлов.

Отдельные графики лишь незначительно отличаются в методе чтения и могут быть проигнорированы здесь, так как все файлы были сохранены в tmpfs. Поэтому, если вам интересно, тест не был связан с IO.

Алгоритмы включают в себя: SpookyHash, CityHash, Murmur3, MD5, SHA .

Некриптографические хеш-функции, такие как Murmur3, Cityhash и Spooky, довольно близки друг к другу. Следует отметить, что Cityhash может быть быстрее на процессорах с CRC инструкцией SSE 4.2s , которой нет у моего процессора. SpookyHash был в моем случае всегда чуть-чуть до CityHash.
MD5 представляется хорошим компромиссом при использовании криптографических хеш-функций, хотя SHA256 может быть более безопасным для уязвимостей коллизий MD5 и SHA1.
Сложность всех алгоритмов линейна - что на самом деле неудивительно, поскольку они работают блочно. (Я хотел посмотреть, если метод чтения имеет значение, так что вы можете просто сравнить самые правильные значения).
SHA256 был медленнее, чем SHA512.
Я не исследовал случайность хэш-функций. Но вот хорошее сравнение хеш-функций, отсутствующих в ответе Иана Бойдса . Это указывает на то, что у CityHash есть некоторые проблемы в угловых случаях.

Источник, используемый для участков:

Алгоритмы SHA (включая SHA-256) предназначены для быстрой работы .

На самом деле их скорость иногда может быть проблемой. В частности, распространенным методом хранения токена, полученного из пароля, является запуск стандартного алгоритма быстрого хеширования 10 000 раз (сохранение хэша хэша хэша пароля . ).

Конечно, это довольно быстрый алгоритм криптографического хеширования . Но OP просто хочет хранить значения в хеш-таблице, и я не думаю, что криптографическая хеш-функция действительно подходит для этого. Вопрос, поднятый (как ни странно, теперь кажется), был предметом криптографических хеш-функций. Это то, на что я отвечаю. Просто чтобы отвлечь людей от идеи: «В частности, распространенная техника хранения токена, полученного из пароля, - запуск стандартного алгоритма быстрого хеширования 10 000 раз» - хотя это обычное явление, это просто глупо. Для этих сценариев разработаны алгоритмы, например bcrypt . Используйте правильные инструменты. Криптографические хеши разработаны для обеспечения высокой пропускной способности, но это часто означает, что они требуют больших затрат на настройку, демонтаж .rodata и / или состояние. Когда вам нужен алгоритм для хеш-таблицы, у вас обычно есть очень короткие ключи и их много, но вам не нужны дополнительные гарантии криптографического ключа. Я сам использую измененный Дженкинс по отдельности. @ChrisMorgan: вместо использования криптографически безопасного хэша, HashTable DoS может быть решен гораздо более эффективно с помощью рандомизации хэшей, так что каждый запуск программ или даже в каждой хеш-таблице, так что данные не будут сгруппированы в одно и то же ведро каждый раз ,

Я знаю, что есть такие вещи, как SHA-256 и тому подобное, но эти алгоритмы предназначены для обеспечения безопасности , что обычно означает, что они медленнее, чем алгоритмы, которые менее уникальны .

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

Криптографические хеш-функции в идеале должны быть неотличимы от случайных ;
Но с некриптографическими хеш-функциями желательно, чтобы они благоприятно взаимодействовали с вероятными входными данными .

Это означает, что некриптографическая хеш-функция может иметь меньше коллизий, чем криптографическая, для «хорошего» набора данных - наборов данных, для которых она была разработана.

На самом деле мы можем продемонстрировать это с помощью данных в ответе Яна Бойда и немного математики: проблема дня рождения . Формула для ожидаемого числа сталкивающихся пар, если вы n случайным образом выбираете целые числа из набора [1, d] : (взято из Википедии):

При n подключении = 216,553 и d = 2 ^ 32 мы получаем около 5,5 ожидаемых коллизий . Тесты Яна в основном показывают результаты в окрестностях, но с одним существенным исключением: большинство функций получили нулевые коллизии в последовательных числовых тестах. Вероятность случайного выбора 216 553 32-битных чисел и получения нулевых коллизий составляет около 0,43%. И это только для одной функции - здесь у нас есть пять различных семейств хэш-функций с нулевыми столкновениями!

Итак, что мы видим здесь, так это то, что проверенные Яном хеши благоприятно взаимодействуют с последовательным набором чисел, т. Е. Они распределяют минимально разные входные данные более широко, чем идеальная криптографическая хеш-функция. (Примечание: это означает, что графическая оценка Яна, что FNV-1a и MurmurHash2 «выглядят случайными» для него в наборе данных номеров, может быть опровергнута из его собственных данных. Нулевые коллизии в наборе данных такого размера для обеих хеш-функций, поразительно неслучайно!)

Это не удивительно, потому что это желательное поведение для многих применений хеш-функций. Например, ключи хеш-таблицы часто очень похожи; В ответе Яна упоминается проблема, с которой MSN когда-то сталкивалась с хеш-таблицами почтового индекса . Это использование, когда предотвращение столкновений на вероятных входах выигрывает у случайного поведения.

Другое поучительное сравнение здесь - это контраст в целях разработки между CRC и криптографическими хеш-функциями:

CRC предназначен для улавливания ошибок, возникающих из-за шумных каналов связи , которые, вероятно, представляют собой небольшое количество битов;
Крипто-хэши предназначены для улавливания модификаций, сделанных злоумышленниками , которым выделены ограниченные вычислительные ресурсы, но произвольно большая хитрость.

Поэтому для CRC опять же хорошо иметь меньше коллизий, чем случайных, при минимально разных входах. С крипто хешами это нет-нет!

Даже изменение одного символа во входных данных приведет к совершенно другому хэшу.

Криптографические хэши используются везде, от хранения паролей до систем проверки файлов. Основная идея состоит в том, чтобы использовать детерминированный алгоритм (алгоритмический процесс, который выдает уникальный и предопределенный результат для задачи входных данных), который принимает один вход и создает строку фиксированной длины каждый раз. То есть, использование одного и того же ввода всегда приводит к одному и тому же результату. Детерминизм важен не только для хэшей, но и для одного бита, который изменяется во входных данных, создавая совершенно другой хэш. Проблема с алгоритмами хэширования — неизбежность коллизий. То есть, тот факт, что хэши являются строкой фиксированной длины, означает, что для каждого ввода, который мы можем себе представить, есть другие возможные входы, которые приведут к тому же хэшу. Коллизия — это плохо. Это означает, что, если злоумышленник может создавать коллизии, он может передавать вредоносные файлы или данные, как имеющие правильный и неправильный хэш и скрываться под правильным хешем. Цель хорошей хэш-функции состоит в том, чтобы сделать чрезвычайно сложным для злоумышленников найти способы генерации входных данных, которые хешируются с одинаковым значением. Вычисление хэша не должно быть слишком простым, так как это облегчает злоумышленникам искусственное вычисление коллизий. Алгоритмы хэширования должны быть устойчивы к «атакам нахождения прообраза». То есть, получая хеш, было бы чрезвычайно сложно вычислить обратные детерминированные шаги, предпринятые для воспроизведения значения, которое создало хэш (т.е нахождение прообраза).

Учитывая S = hash (x), найти X должно быть почти невозможно.

Напомним, что «хорошие» алгоритмы хэширования имеют следующие свойства:

Изменение одного бита во входных данных должно создать эффект изменения всего хеша;
Вычисления хеша не должно быть слишком простым, высокая сложность нахождения прообраза;
Должен иметь очень низкую вероятность коллизии;

Что такое «Атака дня рождения?»

По крайне мере, один отсек будет иметь внутри 2-ух голубей.

Различия и развитие алгоритмов хеширования Начало: SHA1 и SHA2

Использование SHA3

Хеширование и proof-of-work

Когда дело дошло до интеграции алгоритма хеширования в блокчейн протоколы, биткоин использовал SHA256, в то время как Ethereum использовал модифицированный SHA3 (KECCAK256) для своего PoW. Однако важным качеством выбора хэш-функции для блокчейна с использованием доказательства работы является эффективность вычислений указанного хэша. Алгоритм хеширования биткойна SHA256 может быть вычислен достаточно просто с помощью специализированного оборудования, известного как специализированные интегральные схемы (или ASIC). Много было написано об использовании ASIC в майнинг пуле и о том, как они делают протокол направленным на централизацию вычислений. То есть доказательство работы стимулирует группы вычислительно эффективных машин объединяться в пулы и увеличивать то, что мы обозначаем “хэш-мощностью”, или мерой количества хэшей, которые машина может вычислить за интервал времени. Ethereum, выбрал модифицированный SHA3 известный как KECCAK 256. Кроме того, алгоритм PoW в Ethereum — Dagger-Hashimoto, должен был быть трудно вычисляемым для аппаратного обеспечения.

Почему биткоин использует двойное шифрование SHA256?

Ethereum 2.0 и BLAKE

Будущее алгоритмов хэширования

Кажется, что независимо от того, что мы делаем, мы просто либо (1) увеличиваем сложность внутренних хеш-операций, либо (2) увеличиваем длину хеш-выхода, надеясь, что компьютеры атакующих не будут достаточно быстрыми, чтобы эффективно вычислять ее коллизию. Мы полагаемся на двусмысленность предварительных прообразов односторонних операций для обеспечения безопасности наших сетей. То есть цель безопасности алгоритма хеширования состоит в том, чтобы сделать как можно более сложным для любого, кто пытается найти два значения, которые хешируются на один и тот же вывод, несмотря на то, что существует бесконечное количество возможных столкновений. «Как насчет будущего квантовых компьютеров? Будут ли алгоритмы хэширования безопасными?» Короткий ответ и текущее понимание заключаются в том, что да, алгоритмы хэширования выдержат испытание временем против квантовых вычислений. То, что квантовые вычисления смогут сломать, — это те проблемы, которые имеют строгую математическую структуру, основанную на аккуратных трюках и теории, такой как шифрование RSA. С другой стороны, алгоритмы хэширования имеют менее формальную структуру во внутренних конструкциях. Квантовые компьютеры действительно дают повышенную скорость в вычислении неструктурированных проблем, таких как хэширование, но в конце концов, они все равно будут грубо атаковать так же, как компьютер сегодня попытается это сделать. Независимо от того, какие алгоритмы мы выбираем для наших протоколов, ясно, что мы движемся к вычислительно-эффективному будущему, и мы должны использовать наше лучшее суждение, чтобы выбрать правильные инструменты для работы и те, которые, мы надеемся, выдержат испытание временем.

Читайте также: