25 окт. 2022 г. 11 min read Разработка

Хеширование на все вкусы

👋

Хочешь поучаствовать в жизни сайта? Мы ищем авторов!

Перевод статьи Ciprian Dorin Craciun: The many flavors of hashing.

Оглавление

Вступление

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

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

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

И, наконец, если вам нужно второе мнение - а оно всегда нужно! - вы также можете прочитать статью Programmers Don't Understand Hash Functions, похожую на мою (но написанную за год до нее), но больше сосредоточенную на криптографических аспектах.

Предупреждение!

Это мое личное мнение, основанное на практическом опыте разработки ПО, не стремящееся к теоретической точности и соблюдению всех деталей.

Я использую слово хеш или хеширование в самом широком смысле - от реальных хеш-функций до криптографических хеш-функций, включая контрольные суммы (checksums) и другие виды фингерпринтинга (fingerprinting, цифровой отпечаток).

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

Если вы считаете, что что-то из того, что я написал, неверно (устарело или неполно), пожалуйста, напишите мне (в разделе комментариев). (Ссылки на существующие статьи, поддерживающие ваши утверждения, очень приветствуются; просто мнения, не имеющие под собой оснований, приветствуются меньше).

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

Что такое хеширование?

Википедия определяет хеш-функцию как:

Хеш-функция - функция, осуществляющая преобразование массива входных данных произвольной длины в выходную битовую строку установленной длины, выполняемое определённым алгоритмом. Результат преобразования называется «хешем», «хеш-кодом», «хеш-суммой», «сводкой сообщения».

В рамках этой статьи я рассматриваю хеш-функцию как любой фрагмент кода, который:

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

Так, на Python хеш-функция может выглядеть следующим образом:

def hash (_input, _seed = None) :
    _hash = ... # код, который перерабатывает _input
    return _hash

Насчет "выглядит достаточно беспорядочно": поскольку размер входных данных почти всегда больше, чем выходных (которые имеет фиксированный размер), обычно существует бесконечное число вводов, для которых вывод одинаков, поэтому эти функции не инъективны. Когда два входа дают одинаковый выход, это называется коллизией. Лишь немногие хеш-функции не допускают коллизий, но большинство разработано таким образом, чтобы свести коллизии к минимуму.

Классификация хешей

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

В кратце, вот классы хеш-алгоритмов:

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

Хеши перемешивания

Ключевое свойство - скорость работы на маленьких входных данных.

Это наиболее общий и простой вид хеш-функций: при получении входных данных они возвращают небольшое число (16, 32 или 64 бита).

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

Прежде чем я перечислю примеры, вот несколько правил и запретов:

их не следует использовать в ситуациях, связанных с криптографией и безопасностью;
всегда следует ожидать, что коллизии будут происходить регулярно; (вы можете проверить, правильно ли работает ваш код, используя хеш-функцию, которая всегда возвращает 42;)
следует использовать с осторожностью, когда входные данные находятся под контролем потенциального злоумышленника (что обычно всегда, особенно в сетевых сервисах!); если это так, используйте хеш-функции с зерном (seed) или ключом; (иначе вас постигнет та же участь, что и серверы на базе NodeJS / V8 или Python, которые могли пострадать от DoS атак из-за этого;)
если вам нужно меньше битов, чем предоставляет функция, выберите другую функцию, которая предоставляет ближайшее (но все равно большее) количество битов, а затем просто отбросьте лишние биты; не делайте операцию XOR или смешивание битов самостоятельно, иначе вы нарушите какие-либо свойства функции;
при использовании для разбивки по бакетам, выберите либо степень двойки, либо простое число для желаемого количества бакетов, затем возьмите остаток; (также см. предыдущий пункт;)
в целом, и это особенно касается хеш-функций, которые предоставлены по умолчанию многими языками или рантаймами, вы не должны полагаться на то, что вывод функции будет одинаковым в разных процессах (например, после перезапуска приложения или в другом процессе), так как многие современные реализации иницилизируют хеш-функции случайным зерном при запуске; (если вам важно это свойство, выберите конкретную хеш-функцию и используйте ее явно;)

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

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

Для своих собственных нужд я использую следующее:

xxh3 или xxh128 из семейства xxHash (которое поддерживает инициализацию зерном); (на данный момент самые быстрые алгоритмы, согласно бенчмаркам;)
highwayhash (поддерживает инициализацию зерном); был разработан Google, и согласно им, он быстрее, чем SipHash, и поставляется с "гарантиями безопасности"; я бы выбрал его, если хакеры вызывают беспокойство;
SipHash, проверенная хеш-функция (поддерживает инициализацию зерном); присутствует в большинстве языков программирования как дефолтный алгоритм хеширования в хеш-таблицах (от Rust до Python, Ruby, NodeJS и других); я бы выбрал ее, если первые два варианта еще не реализованы для моего языка программирования;
djb2, алгоритм, разработанный D.J. Berstein, полезен, если простота имеет перстепенное значение (алгоритм всего на 3 строки кода); (и если злоумышленники не вызывают беспокойства;)

Позаимствую интересное резюме у автора бенчмарка smhasher:

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

Хеши целостности

Ключевое свойство - выявление мелких изменений во входных данных.

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

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

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

Сам я никогда не использовал такие хеши, я прибегал к бо́льшим хешам подписи (т.е. криптографически сильным хешам), и многие предпочитают использовать (более) безопасные варианты хешей перестановки. Я также рекомендую прочитать issue #229 xxHash, касающийся этой темы.

Стоит выделить два семейства алгоритмов:

Циклический избыточный код (Cyclic redundancy check, CRC), который повсеместно используется на нижних уровнях хранения данных и в сетях (особенно в железе);
Коды Боуза-Чоудхури-Хоквингема (BCH-коды), на которые я наткнулся в кодировке Bech32 (похожей на Base32, но со встроенной функцией обнаружения ошибок и адаптированной для QR); (кто бы мог подумать, что из всей этой криптовалютной "заварухи" выйдет что-то хорошее...)

Для личного использования, если речь идет о проверке целостности файловой системы, я предпочитаю использовать MD5. Это связано в основном с тем, что он доступен повсюду (через команду md5sum), а также с тем, что у меня уже есть коллекция цифровых отпечатков, которые уже являются MD5.

Хеши перестановки

Ключевое свойство - маленькие вводы и маленькие выводы, но без коллизий.

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

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

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

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

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

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

Кроме того, на HackerNews кто-то указал мне на книгу Correlated Multi-Jittered Sampling Эндрю Кенслера, хотя сам я ее пока не читал. В дополнение к этому, кто-то еще указал, что для этой цели можно также использовать "обратимые функции смешивания" (из шага смешивания различных более сильных алгоритмов хеширования).

Хеши подписи

Ключевое свойство - необратимость и стойкость к коллизиям.

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

Правила и запреты:

никогда не используйте эти алгоритмы (напрямую)!
действительно, не используйте ни один из этих алгоритмов! (спросите себя, какую проблему вы решаете? затем прочитайте эту статью об атаках удлинением сообщения, и вы поймете, что лучше не надо;)
не думайте, что они шифруют или обфусцируют вход! они просто эффективно искажают биты из входа; если атакующий видит хеш, и он может угадать возможные входы, то он легко узнает, каким был вход; если атакующий знает вход, он легко вычислит хеш, и таким образом он определит, соответствует ли любой из входов увиденным хешам; (я иногда использую хеши, которые описал ниже как хеши шифрования;)
не используйте их для паролей! используйте один из алгоритмов хеширования паролей, описанных ниже;
всегда используйте библиотеки (например, libsodium), которые предоставляют абстракции более высокого уровня (например, электронные подписи и HMAC);
если вы уверены, что вам просто необходимо использовать хеш-функцию подписи, всегда используйте ее с ключом (ключ можно поместить в файл конфигурации), или используйте HMAC, если алгоритм не имеет варианта с ключом;
хоть вы и можете использовать один из этих алгоритмов для заполнений бакетов, это расточительно с точки зрения нагрузки на процессор; используйте хеши перемешивания, описанные выше;

Очевидные варианты на выбор в этой категории:

Blake3 - последнее поколение семейства Blake; (или Blake2b, если хотите;) я предпочитаю его за производительность и гибкость (то есть, наличие как режима HMAC, так и режима вывода ключа);
SHA-3 - последнее поколение семейства SHA, стандартизированное NIST; (или SHA-2, если хотите;) Я советую использовать его, если Blake3 недоступен, или если вам нужна "печать одобрения" на ваших криптографических примитивах;

Очевидными неудачными вариантами (из-за их слабых мест) являются MD5 (и MD4), SHA1 и другие алгоритмы типа "поверь мне, это лучший крипто-алгоритм в мире".

Хеши паролей

Ключевое свойство - необратимость и стойкость к перебору.

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

Но если очень нужно, вот очевидные варианты в этой категории (без какого-либо порядка):

Argon2 - "победитель" Password Hashing Competition;
scrypt, бывший "лучший выбор" в сообществе информационной безопасности, который тем не менее все еще является хорошим вариантом; (вот хорошая статья, описывающая, как его настроить;)
bcrypt, который следует использовать, только если реализация двух предыдущих недоступна;

Стоит упомянуть и PBKDF2, хотя по сегодняшним стандартам он считается непригодным.

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

Хеши токенов

Ключевое свойство - необратимость и стойкость к коллизиям.

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

Когда следует использовать такой алгоритм? Лучший ответ: вы поймете, когда он вам понадобится.

Однако лучшее объяснение (с подробными деталями, 99% которых я уже забыл) я видел в статье Understanding HKDF; поэтому, если вам нужна такая хеш-функция, вы должны прочитать эту статью.

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

Blake3, который предлагает встроенный режим формирования ключей;
HKDF, который основывается на любом алгоритме HMAC;
PBKDF2, в случае, если вариант выше не реализован в вашем языке;

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

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

Ключевое свойство - обратимость при наличии зерна, и необратимость в обратном случае, а также стойкость к коллизиям.

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

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

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

Единственная статья, которую я нашел, затрагивающая эту тему, это Plan B for UUIDs - double AES-128. (Я бегло прочитал ее, но еще не вник в ее тонкости, поэтому не могу говорить о ней слишком подробно).

Когда-то давно я даже написал свою собственную опенсорсную реализацию такого алгоритма, доступную на github.com/cipriancraciun/java-token-obfuscator, однако уже давно (почти 8 лет) к ней не обращался... (Возможно, когда-нибудь я напишу еще одну реализацию и статью к ней в придачу...)

Кроме того, кто-то на HackerNews указал мне на книгу How to Encipher Messages on a Small Domain - Deterministic Encryption and the Thorp Shuffle Бена Морриса, Филлипа Рогауэя и Тилла Стегерса, хотя сам я ее пока не читал.

Другие хеши

Эта категория предназначена для тех типов хешей, которые либо слишком странные, либо слишком нишевые и потому не подходят ни под одну из предыдущих категорий:

скользящие хеши, которые могут использоваться для обнаружения дублирующихся кусков данных;
идеальные хеш-функции, которые в случае, если диапазон всех входов известен и ограничен, избегают любых коллизий;
имитовставки (коды аутентификации послания, message authentication code, MAC), как например, Poly1305, в некоторой степени связаны с контрольными суммами, обеспечивают устойчивость к взлому при передаче и хранении данных;
Soundex, который используется для обнаружения похожих по звучанию слов в английском языке;
перцептивное хеширование, которое можно использовать для сравнения похожих медиафайлов (изображений, аудио, видео и т.д.);
одноразовые пароли на основе времени (time-based one-time passwords, TOTP) или хеша (hash-based one-time passwords, HOTP), которые на самом деле не являются паролями, но представляют собой самую распространенную форму двухфакторной аутентификации;
(ничего другого пока на ум не приходит;)

Разные ссылки

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

Материал подготовлен с ❤️ редакцией Кухни IT.

Олег Ямников

Главный кухонный корреспондент.

☕

Заходи в канал Telegram и в чат! Кухня - это не только сайт, но и живое сообщество айтишников.