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

Обновлено: 03.07.2024

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

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

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

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

11 ответов 11

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

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

Числа от "1" до "216553" (вспомните почтовые индексы и то, как неудачный хэш уничтожил архив msn.com🕗)
216 553 "случайных" идентификатора GUID (т. е. uuid типа 4).

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

Результаты

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

Примечания:

Алгоритм LoseLose (где хэш = хеш+символ) действительно ужасен. Все попадает в одни и те же 1375 сегментов.
SuperFastHash работает быстро, а объекты выглядят довольно разбросанными; Боже мой, коллизий количество. Я надеюсь, что парень, который его портировал, сделал что-то не так; это очень плохо
CRC32 довольно хорош. Медленнее и таблица поиска размером 1 КБ.

Происходят ли коллизии на самом деле?

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

Столкновения FNV-1

Столкновения FNV-1a

звезда сталкивается с жидкостью
склонение сталкивается с макаллумами
altarage сталкивается с zinke
альтараги сталкиваются с цинками

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

катаракта сталкивается с перититом
Рокетт сталкивается со Скиви
платок сталкивается с stormbound
доулас сталкивается с трамонтаном
крикеты сталкиваются с громким звуком
лонганы сталкиваются с вигами

Конфликты DJB2

hetairas сталкивается с упоминанием
гелиотроп сталкивается с нейроспорой
испорченность сталкивается с серафинами
стилист сталкивается с подродами
радостное сталкивается с синафеей
переописанные коллизии с уритами
драм сталкивается с живностью

Конфликты DJB2a

агадот сталкивается с отвратительностью
красивость противоречит рентабельности
драматург сталкивается со снушем
драматургия сталкивается с хохотом
трепонематозы сталкиваются с водяными руслами

Конфликты CRC32

кодирование конфликтует с gnu
экспоненты сталкиваются со шлягером

Конфликты SuperFastHash

dahabiah противоречит драпируемости
зачарование сталкивается с анклавом
Грэмс сталкивается с грамматикой
ночь сталкивается с бодрствованием
ночи сталкиваются с бдениями
финкс сталкивается с виником

Случайное определение

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

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

СДБМ:

DJB2a:

ФНВ-1:

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

Похоже, что у Murmur2 случайность с числами даже выше, чем у FNV-1a :

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

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

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

Затем нужно было убедиться, что хэш-функции достаточно случайны.

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

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

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

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

ФНВ-1 лучше, чем ФНВ-1а?

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

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

В этом случае ФНВ-1а не "400%" хуже, чем ФН-1, а только на 20% хуже.

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

отличное распространение: Murmur2, FNV-1a, SuperFastHas
отличное распространение: FNV-1
хорошее распространение: SDBM, DJB2, DJB2a
ужасное распространение: Loselose

Обновить

Шуршать? Конечно, почему бы и нет

Обновить

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

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

Отсечь все неверные сведения о распространении CRC — это плохо

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

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

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

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

Думаю, дело не только во мне.

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

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

Обновить

Идентификаторы GUID должны быть уникальными, а не случайными

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

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

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

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

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

Новый хеш под названием «xxHash», созданный Яном Коллетом, недавно был в ходу. Я всегда с подозрением отношусь к новому хэшу. Было бы интересно увидеть это в вашем сравнении (если вы не устали от людей, предлагающих добавить случайные хэши, о которых они слышали).

Здравствуйте, Ян! Моя реализация SuperFastHash в Delphi верна. При реализации я создал набор тестов на C и Delphi, чтобы сравнить результаты моей реализации и эталонной реализации. Различий нет. Итак, то, что вы видите, - это фактическая вредность хэша. (Вот почему я также опубликовал реализацию MurmurHash: landman-code.blogspot.nl/2009/02/… )

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

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

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

@DavidCary Ничто по вашей ссылке не подтверждает ваше утверждение. Возможно, вы перепутали O(1) с «отсутствием столкновений», но это совсем не одно и то же. Конечно, идеальное хеширование гарантирует отсутствие коллизий, но требует, чтобы все ключи были известны заранее и чтобы их было относительно немного. (Но см. ссылку на cmph выше.)

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

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

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

Ребята, у меня сомнения. Вы говорите, что djb2 плохой, но результаты тестирования принятого ответа показывают, что он хороший.

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

Подробнее читайте в блоге, а код доступен здесь.

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

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

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

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

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

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

Источник, использованный для графиков:

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

Я знаю, что есть такие вещи, как 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 снова хорошо иметь меньше коллизий, чем случайные, в минимально различных входных данных. С криптовалютными хэшами этого делать нельзя!

MD5: 16 байт (время хеширования 500 МБ: 1462 мс)
SHA-1: 20 байт (1644 мс)
SHA256: 32 байта (5618 мс)
SHA384: 48 байт (3839 мс)
SHA512: 64 байта (3820 мс)
RIPEMD: 20 байт (7066 мс)

Каждая из этих функций работает по-разному. MD5 — самый быстрый, а RIPEMD — самый медленный.

Преимущество MD5 заключается в том, что он подходит для встроенного типа Guid; и это основа UUID типа 3. Хэш SHA-1 является основой UUID типа 5. Это делает их очень удобными для идентификации.

Однако MD5 уязвим для коллизий, SHA-1 также уязвим, но в меньшей степени.

При каких условиях какой алгоритм хеширования следует использовать?

Не следует ли доверять MD5? В обычных ситуациях, когда вы используете алгоритм MD5 без злого умысла и ни одна третья сторона не имеет никаких злонамеренных намерений, вы ожидаете ЛЮБЫЕ коллизии (имеется в виду, что два произвольных byte[] создают один и тот же хэш)

Насколько лучше RIPEMD, чем SHA1? (если он лучше) вычисляется в 5 раз медленнее, но размер хеша такой же, как у SHA1.

Каковы шансы получить непреднамеренные коллизии при хешировании имен файлов (или других коротких строк)? (Например, 2 случайных имени файла с одинаковым хэшем MD5) (с MD5 / SHA1 / SHA2xx) Каковы вообще шансы на незлонамеренные коллизии?

Это тест, который я использовал:

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

Исправьте, это не связано, это просто удобный факт, связанный с реализацией. Я понимаю, что бесконечность в 16 байт не влезешь. Вы можете получить коллизии с ЛЮБЫМ алгоритмом хеширования

Кроме того, Guid на практике уникален, теоретически, если вы продолжите генерировать Guid, в конечном итоге вы получите дубликаты.

Вы действительно не должны вставлять хэш в GUID, даже если он подходит. Самый простой пример: две копии одного и того же файла должны иметь разные GUID, но одинаковый хэш. Первые 8 букв имени человека также вполне умещаются в 16 байт.

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

9 ответов 9

В криптографии хеш-функции выполняют три отдельные функции.

Устойчивость к коллизиям. Насколько сложно найти два сообщения (любые два сообщения) с одинаковым хэшем.
Сопротивление прообразу. Насколько сложно найти другое сообщение с таким же хэшем при наличии хэша? Также известна как односторонняя хэш-функция.
Сопротивление второму прообразу: по заданному сообщению найдите другое сообщение с таким же хэшем.

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

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

SHA1 имеет недостаток, который теоретически позволяет обнаруживать коллизии за гораздо меньшее количество шагов, чем 2^80, которые потребовались бы для безопасной хеш-функции такой длины. Атака постоянно пересматривается и в настоящее время может быть выполнена примерно за 2 ^ 63 шага — едва ли в текущей области вычислимости. По этой причине NIST постепенно отказывается от использования SHA1, заявляя, что семейство SHA2 следует использовать после 2010 года.

SHA2 – это новое семейство хеш-функций, созданное после SHA1. В настоящее время неизвестны атаки на функции SHA2. SHA256, 384 и 512 являются частью семейства SHA2, но используют разные длины ключей.

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

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

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

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

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

Используйте Argon2id с минимальной конфигурацией памяти 15 МиБ, числом итераций, равным 2, и степенью параллелизма 1.
Если Argon2id недоступен, используйте bcrypt с рабочим коэффициентом 10 или более и ограничением пароля в 72 байта.
Для устаревших систем, использующих scrypt, используйте параметр минимальной стоимости ЦП/памяти (2^16), минимальный размер блока 8 (1024 байта) и параметр распараллеливания 1.
Если требуется соответствие FIPS-140, используйте PBKDF2 с рабочим фактором 310 000 или более и задайте внутреннюю хеш-функцию HMAC-SHA-256.
Рассмотрите возможность использования перца для обеспечения дополнительной глубокоэшелонированной защиты (хотя сам по себе он не обеспечивает дополнительных защитных характеристик).

Фон¶

Хеширование и шифрование¶

Хеширование и шифрование обеспечивают безопасность конфиденциальных данных. Однако почти во всех случаях пароли следует хэшировать, а НЕ шифровать.

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

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

В контексте хранения паролей шифрование следует использовать только в крайних случаях, когда необходимо получить исходный пароль в виде открытого текста. Это может быть необходимо, если приложению необходимо использовать пароль для аутентификации в другой системе, которая не поддерживает современный способ программного предоставления доступа, например OpenID Connect (OIDC). По возможности следует использовать альтернативную архитектуру, чтобы избежать необходимости хранить пароли в зашифрованном виде.

Дополнительные рекомендации по шифрованию см. в Памятке по криптографическому хранилищу.

Как злоумышленники взламывают хэши паролей¶

Хотя "расшифровать" хэши паролей для получения исходных паролей невозможно, в некоторых случаях можно "взломать" хэши.

Выберите пароль, который, по вашему мнению, выбрала жертва (например, password1! )
Вычислить хеш
Сравните вычисленный хэш с хэшем жертвы.Если они совпадают, вы правильно "взломали" хеш и теперь знаете значение открытого текста их пароля.

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

Списки паролей, полученные с других взломанных сайтов
Грубая сила (перебор всех возможных вариантов)
Словари или списки общих паролей

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

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

Концепции хранения паролей¶

Соление¶

Соль – это уникальная случайно сгенерированная строка, которая добавляется к каждому паролю в процессе хеширования. Поскольку соль уникальна для каждого пользователя, злоумышленник должен взламывать хэши один за другим, используя соответствующую соль, а не вычислять хеш один раз и сравнивать его с каждым сохраненным хэшем. Это значительно усложняет взлом большого количества хэшей, поскольку требуемое время растет прямо пропорционально количеству хэшей.

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

Современные алгоритмы хеширования, такие как Argon2id, bcrypt и PBKDF2, автоматически добавляют соль к паролям, поэтому при их использовании не требуется никаких дополнительных действий.

Приправление¶

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

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

Перец разделяется между сохраненными паролями, а не уникален, как соль.
В отличие от соли пароля, перец не должен храниться в базе данных.
Перцы — это секреты, и их следует хранить в «секретных хранилищах» или HSM (аппаратных модулях безопасности).
Как и для любого другого криптографического ключа, следует учитывать стратегию ротации перца.

Рабочие факторы¶

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

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

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

Повышение коэффициента работы¶

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

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

Алгоритмы хеширования паролей¶

Существует ряд современных алгоритмов хэширования, специально разработанных для безопасного хранения паролей. Это означает, что они должны быть медленными (в отличие от таких алгоритмов, как MD5 и SHA-1, которые были разработаны, чтобы быть быстрыми), а скорость их работы можно настроить, изменив коэффициент работы.

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

Три основных алгоритма, которые следует учитывать, перечислены ниже:

Argon2id¶

Argon2 — победитель конкурса хеширования паролей 2015 года. Существует три разных версии алгоритма, и следует использовать вариант Argon2id, так как он обеспечивает сбалансированный подход к сопротивлению атакам как по сторонним каналам, так и на основе графического процессора.

Вместо простого рабочего коэффициента, как у других алгоритмов, Argon2id имеет три различных параметра, которые можно настроить. Argon2id должен использовать один из следующих параметров конфигурации в качестве базового минимума, который включает минимальный размер памяти (m), минимальное количество итераций (t) и степень параллелизма (p).

Оба этих параметра конфигурации эквивалентны по обеспечиваемой ими защите. Единственная разница заключается в компромиссе между использованием ЦП и ОЗУ.

скрипт¶

scrypt — это функция получения ключа на основе пароля, созданная Колином Персивалем. В то время как в новых системах для хэширования паролей следует использовать Argon2id, scrypt следует правильно настроить при использовании в устаревших системах.

Как и Argon2id, scrypt имеет три различных параметра, которые можно настроить. scrypt должен использовать один из следующих параметров конфигурации в качестве базового минимума, который включает параметр минимальной стоимости ЦП/памяти (N), размер блока (r) и степень параллелизма (p).

N=2^16 (64 МиБ), r=8 (1024 байт), p=1
N=2^15 (32 МиБ), r=8 (1024 байт), p=2
N=2^14 (16 МиБ), r=8 (1024 байт), p=4
N=2^13 (8 МиБ), r=8 (1024 байт), p=8
N=2^12 (4 МиБ), r=8 (1024 байт), p=15

Эти параметры конфигурации эквивалентны по обеспечиваемой ими защите. Единственная разница заключается в компромиссе между использованием ЦП и ОЗУ.

bcrypt¶

Функция хеширования паролей bcrypt должна быть вторым выбором для хранения паролей, если Argon2id недоступен или требуется PBKDF2 для достижения соответствия FIPS-140.

Минимальный коэффициент работы для bcrypt должен быть равен 10.

Ограничения ввода¶

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

Предварительное хеширование паролей¶

Альтернативный подход заключается в предварительном хешировании введенного пользователем пароля с помощью быстрого алгоритма, такого как SHA-256, а затем хешировании полученного хэша с помощью bcrypt (например, bcrypt(base64(hmac-sha256(data:$password , ключ: $ перец)), $ соль, $ стоимость) ). Это опасная (но распространенная) практика, которой следует избегать из-за перехвата пароля и других проблем при комбинировании bcrypt с другими хеш-функциями.

PBKDF2¶

PBKDF2 рекомендован NIST и имеет реализации, проверенные FIPS-140. Таким образом, это должен быть предпочтительный алгоритм, когда это требуется.

PBKDF2 требует, чтобы вы выбрали внутренний алгоритм хеширования, такой как HMAC, или множество других алгоритмов хеширования. HMAC-SHA-256 широко поддерживается и рекомендуется NIST.

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

PBKDF2-HMAC-SHA1: 720 000 итераций
PBKDF2-HMAC-SHA256: 310 000 итераций
PBKDF2-HMAC-SHA512: 120 000 итераций

Эти параметры конфигурации эквивалентны по обеспечиваемой ими защите.

Если PBKDF2 используется с HMAC и пароль длиннее, чем размер блока хеш-функции (64 байта для SHA-256), пароль будет автоматически предварительно хеширован. Например, пароль «Это пароль длиннее 512 бит, что соответствует размеру блока SHA-256» преобразуется в хеш-значение (в шестнадцатеричном формате) fa91498c139805af73f7ba275cca071e78d78675027000c99a9925e2ec92eedd. Хорошая реализация PBKDF2 будет выполнять этот шаг перед дорогостоящей фазой повторного хеширования, но некоторые реализации выполняют преобразование на каждой итерации. Это может сделать хеширование длинных паролей значительно более дорогим, чем хеширование коротких паролей.Если пользователь может указать очень длинные пароли, существует потенциальная уязвимость, связанная с отказом в обслуживании, например уязвимость, опубликованная в Django в 2013 году. Предварительное хеширование вручную может снизить этот риск, но требует добавления соли на этапе предварительного хеширования.

Обновление старых хэшей¶

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

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

Один из способов – истечение срока действия и удаление хэшей паролей пользователей, которые не были активны в течение длительного периода времени, и требование от них сбросить свои пароли для повторного входа в систему. Несмотря на безопасность, этот подход не особенно удобен для пользователя. Срок действия паролей многих пользователей может вызвать проблемы у сотрудников службы поддержки или может быть истолкован пользователями как признак взлома.

Альтернативный подход заключается в использовании существующих хэшей паролей в качестве входных данных для более безопасного алгоритма. Например, если приложение изначально хранило пароли как md5($password) , его можно легко обновить до bcrypt(md5($password)) . Наслоение хэшей позволяет избежать необходимости знать исходный пароль; однако это может облегчить взлом хэшей. Эти хэши следует заменить прямыми хэшами паролей пользователей при следующем входе в систему.

Предположим, что какой бы метод хеширования паролей ни был выбран, в будущем его придется обновить. Убедитесь, что обновление вашего алгоритма хеширования максимально простое. На переходный период разрешите сочетание старых и новых алгоритмов хеширования. Использование комбинации алгоритмов хеширования упрощается, если алгоритм хеширования пароля и коэффициент работы хранятся вместе с паролем в стандартном формате, например в модульном строковом формате PHC.

Международные символы¶

Убедитесь, что ваша библиотека хеширования может принимать широкий диапазон символов и совместима со всеми кодовыми точками Unicode. Пользователи должны иметь возможность использовать весь спектр символов, доступных на современных устройствах, в частности, на мобильных клавиатурах. Они должны иметь возможность выбирать пароли на разных языках и включать пиктограммы. Перед хешированием энтропия пользовательской записи не должна уменьшаться. Библиотеки хеширования паролей должны иметь возможность использовать ввод, который может содержать байт NULL.

SHA-1, SHA-2, SHA-256, SHA-384 — что все это значит!!

Если вы слышали о «SHA» во многих его формах, но не совсем уверены, что это за аббревиатура и почему это важно, сегодня мы попытаемся пролить на это немного света.< /p>

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

Что такое хэш?

Алгоритм хеширования – это математическая функция, сжимающая данные до фиксированного размера. Так, например, если бы мы взяли предложение…

…и прогнали его через специальный алгоритм хеширования, известный как CRC32, и мы получили:

Этот результат известен как хэш или хеш-значение. Иногда хеширование называют односторонним шифрованием.

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

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

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

Существуют сотни алгоритмов хэширования, и все они предназначены для определенных целей: одни оптимизированы для определенных типов данных, другие — для скорости, безопасности и т. д.

Для сегодняшнего обсуждения нам нужны только алгоритмы SHA.SHA расшифровывается как Secure Hash Algorithm — его название раскрывает его назначение — это криптографическая безопасность.

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

Примечание. Чтобы упростить чтение и понимание этой статьи, я использую в качестве примера строку данных и алгоритм хэширования, который значительно короче, чем тот, который фактически используется на практике. Хэши, которые вы видели до сих пор, НЕ являются хэшами SHA любого типа.

Цифровые подписи

Теперь, когда мы знаем, что такое хэши, мы можем объяснить, как они используются в SSL-сертификатах.

Протокол SSL/TLS используется для обеспечения безопасной передачи данных с одного устройства на другое через Интернет. Для краткости кажется, что SSL часто называют «шифрованием». Но не забывайте, что SSL также обеспечивает аутентификацию. Файл сертификата SSL предназначен для предоставления необходимой информации, необходимой для аутентификации. Другими словами, SSL-сертификаты связывают определенный открытый ключ с личностью.

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

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

Вот почему аутентификация невероятно важна для того, чтобы убедиться, что SSL/TLS действительно обеспечивает значимую безопасность. Представьте, если бы у вашего компьютера не было надежного способа узнать, кому принадлежит ключ шифрования, который вы использовали? Шифрование вашего сеансового ключа с помощью этого открытого ключа было бы бесполезным, потому что вы не знали бы, у кого есть соответствующий закрытый ключ, который его расшифровывает. В конце концов, шифрование данных бесполезно, если вы отправляете их напрямую злоумышленнику-посреднику или злоумышленнику на другом конце соединения.

Цифровые подписи — важная часть аутентификации с помощью SSL-сертификатов. Когда сертификат выпускается, он подписывается цифровой подписью Центра сертификации (ЦС), который вы выбрали в качестве поставщика сертификата (например, Sectigo, DigiCert и т. д.). Эта подпись обеспечивает криптографическое доказательство того, что ЦС подписал SSL-сертификат и что сертификат не был изменен или воспроизведен. Что еще более важно, подлинная подпись является криптографическим доказательством того, что информация, содержащаяся в сертификате, была проверена доверенной третьей стороной.

Теперь давайте поговорим о том, как создается, наносится и ставится цифровая подпись — вы выбираете терминологию. Асимметричные ключи, о которых мы упоминали ранее, снова используются, но для подписи, а не для шифрования. С математической точки зрения подписание включает в себя изменение способа объединения данных и ключей (мы не будем слишком углубляться в особенности создания подписей, потому что это быстро усложняется. Если вам это интересно, Джошуа Дэвис написал отличный пост о том, как работают цифровые подписи). Чтобы облегчить компьютерам быстрое, но безопасное создание и проверку этих подписей, ЦС сначала хеширует файл сертификата и подписывает полученный хэш. Это более эффективно, чем подписывать весь сертификат.

Эти цифровые подписи обеспечивают необходимое доказательство того, что выданный вам сертификат является именно тем сертификатом, который был выдан доверенным ЦС для рассматриваемого веб-сайта. Никаких трюков. Нет спуфинга. Никакие посредники не манипулируют файлом сертификата SSL/TLS.

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

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

SHA-1 и SHA-2

Теперь, когда мы заложили основу, мы можем перейти к главной роли.

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

В первую очередь люди обращают внимание на длину в битах как на важное различие. SHA-1 — это 160-битный хэш. SHA-2 на самом деле представляет собой «семейство» хэшей различной длины, самая популярная из которых — 256-битная.

Разнообразие хэшей SHA-2 может привести к некоторой путанице, поскольку веб-сайты и авторы выражают их по-разному. Если вы видите «SHA-2», «SHA-256» или «SHA-256 бит», эти имена относятся к одному и тому же. Если вы видите «SHA-224», «SHA-384» или «SHA-512», это относится к альтернативной битовой длине SHA-2. Вы также можете увидеть, что некоторые сайты являются более подробными и указывают как алгоритм, так и длину в битах, например «SHA-2 384». Но это так же отвратительно, как заставлять людей включать свой инициал отчества, когда вы произносите свое имя.

Индустрия SSL выбрала SHA в качестве алгоритма хеширования цифровых подписей

С 2011 по 2015 год SHA-1 был основным алгоритмом. Растущее количество исследований, показывающих слабые стороны SHA-1, вызвало переоценку. На самом деле, Google даже зашел так далеко, что создал коллизию SHA-1 (когда две части разрозненных данных создают одно и то же значение хеш-функции) просто для обеспечения. Итак, с 2016 года SHA-2 является новым стандартом. Если вы получаете сертификат SSL/TLS сегодня, он должен использовать как минимум эту подпись.

Иногда вы увидите сертификаты, использующие 384-битный алгоритм SHA-2. Вы редко встретите 224-разрядную версию, которая не одобрена для использования с общедоступными доверенными сертификатами, или 512-разрядную версию, которая менее широко поддерживается программным обеспечением.

SHA-2, скорее всего, будет использоваться не менее пяти лет. Однако может быть обнаружена непредвиденная атака на алгоритм, которая вызовет более ранний переход.

Вот как выглядит хэш SHA-1 и SHA-2 SSL-сертификата нашего веб-сайта:

Так что да. Вот из-за этого вся суета. Это может показаться не таким уж большим, но цифровые подписи невероятно важны для обеспечения безопасности SSL/TLS.

По теме: Защитите свой веб-сайт с помощью SSL-сертификата Comodo.

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

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

Сколько хэшей?

Если предполагается, что алгоритм хеширования создает уникальные хэши для каждого возможного входного значения, то сколько существует возможных хэшей?

Бит имеет два возможных значения: 0 и 1. Возможное количество уникальных хэшей можно выразить как количество возможных значений, возведенное в число битов. Для SHA-256 существует 2 256 возможных комбинаций.

Итак, 2 256 комбинаций. Сколько это? Что ж, это огромное число. Серьезно. Это ставит такие числа, как триллион и септиллион, в позор. Это намного превышает количество песчинок в мире.

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

Существует (технически) бесконечное количество возможных входов[1], но ограниченное количество выходов. Таким образом, в конечном итоге каждый алгоритм хеширования, включая безопасный, приводит к коллизии. Но нас больше всего беспокоит, насколько легко это будет сделать. SHA-1 был признан небезопасным, поскольку из-за его размера и конструкции можно было создать коллизию.

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

Переход на SHA-2

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

Крайний срок выпуска новых SSL-сертификатов с хешами SHA-1 – 31 декабря 2015 года. По большей части отрасль уложилась в этот срок. С тех пор было допущено несколько ошибок и разрешено несколько особых случаев.

Браузеры обрабатывали сертификаты, подписанные SHA-1, срок действия которых истекает в 2017 году, с более строгим предупреждением. Это связано с тем, что безопасность подписи напрямую связана с тем, как долго она действительна.

Теперь, в 2018 году, Google без суда и следствия казнит владельца сайта и оставляет его труп в качестве предупреждения для других, которые могут осмелиться совершить те же грехи.

Защита подписей

Со временем атаки на криптографию будут улучшаться, а вычислительная мощность компьютеров будет дешеветь. Это делает действующую подпись SHA-2 менее безопасной в 2020 году, чем в 2016 году. По этой причине выбор алгоритма будет намного более надежным, чем это необходимо немедленно, чтобы краткосрочные улучшения не привели к риску безопасности. Не исключено, что конкретный алгоритм хеширования будет оставаться безопасным в течение десятилетия.

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

Это не означает, что криптографы будут просто сидеть и ждать, пока не возникнет проблема. Преемник SHA-2, получивший удобное название SHA-3, уже завершен. Когда придет время сделать еще один переход, индустрия SSL может использовать SHA-3 в качестве следующего выбора или может обратиться к совершенно другому алгоритму.

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

Время от времени нам нравится повторно хешировать некоторые из наших лучших старых материалов в надежде, что они понравятся нашим новым читателям. Эта статья, первоначально написанная Винсентом Линчем 29 июня 2016 г., была обновлена и исправлена Патриком Ноэ в 2018 г.

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