Bcrypt

Bcrypt — это адаптивная криптографическая хеш-функция, предназначенная для хеширования и защиты паролей. Она основана на блочном шифре Blowfish и включает в себя механизм «соли» (salt) и регулируемый параметр стоимости (cost factor), что делает её устойчивой к атакам с использованием специализированного оборудования (ASIC, GPU) и к атакам по радужным таблицам. Bcrypt является одной из наиболее распространённых и рекомендуемых функций для безопасного хранения паролей в веб-приложениях и базах данных.

История и происхождение

Bcrypt была разработана в 1999 году криптографами Нильсом Провосом (Niels Provos) и Дэвидом Мазьером (David Mazières) из Массачусетского технологического института (MIT). Алгоритм был представлен на конференции USENIX Annual Technical Conference в 1999 году. Основной целью создания bcrypt было преодоление ограничений существовавших на тот момент хеш-функций, таких как MD5 и SHA-1, которые были уязвимы для атак с перебором (brute-force) и атак по радужным таблицам из-за своей высокой скорости вычислений.

Разработчики взяли за основу блочный шифр Blowfish, созданный Брюсом Шнайером (Bruce Schneier) в 1993 году, и модифицировали его алгоритм расширения ключа (key schedule) для создания хеш-функции с регулируемой вычислительной сложностью. Ключевой инновацией стало введение параметра стоимости (cost factor), который позволяет увеличивать время вычисления хеша по мере роста производительности компьютерного оборудования, сохраняя защиту на десятилетия вперёд.

Принцип работы

Алгоритм

Bcrypt использует модифицированную версию алгоритма расширения ключа Blowfish, называемую eksblowfish (Expensive Key Schedule Blowfish). В отличие от стандартного Blowfish, где расширение ключа выполняется один раз, в eksblowfish этот процесс повторяется многократно, число итераций определяется параметром стоимости.

Процесс хеширования пароля состоит из следующих этапов:

1. Генерация соли: Создаётся случайная строка фиксированной длины (обычно 16 байт или 128 бит). Соль уникальна для каждого хешируемого пароля.
2. Инициализация: На основе соли и пароля выполняется серия итераций (2^cost_factor) алгоритма eksblowfish. Каждая итерация перемешивает ключи и данные в таблицах замен (S-блоках) и P-массиве.
3. Финальное шифрование: После завершения всех итераций выполняется 64-кратное шифрование константной строки (обычно "OrpheanBeholderScryDoubt") с помощью полученного ключа Blowfish. Результат этого шифрования является хешем пароля.
4. Формирование выходной строки: Хеш, соль и параметр стоимости объединяются в единую строку фиксированного формата.

Формат выходной строки

Стандартный формат bcrypt-хеша (в реализации BSD) выглядит следующим образом: $2a$10$N9qo8uLOickgx2ZMRZoMyeIjZAgcfl7p92ldGxad68LJZdL17lhWy

Разбор строки:

• $2a$ — идентификатор версии алгоритма. Существуют варианты $2a$ (оригинальный, с уязвимостью к атакам по времени), $2b$ (исправленная версия, устраняющая уязвимость, принятая в OpenBSD), $2x$ и $2y$ (исправления для старых баз данных).
• 10 — параметр стоимости (cost factor). Означает, что было выполнено 2^10 = 1024 итерации.
• N9qo8uLOickgx2ZMRZoMye — соль (22 символа в кодировке Base64, что соответствует 16 байтам).
• IjZAgcfl7p92ldGxad68LJZdL17lhWy — непосредственно хеш (31 символ в кодировке Base64, 23 байта).

Классификация и параметры

Параметр стоимости (Cost Factor)

Параметр стоимости (cost factor) — это целое число, обычно от 4 до 31, которое определяет количество итераций алгоритма как 2^cost_factor. Увеличение параметра на 1 удваивает время вычисления хеша. Рекомендуемые значения:

• Минимальное: 4 (16 итераций) — используется только для тестирования.
• Типичное (на 2024 год): 10–12 (1024–4096 итераций). Время вычисления на современном CPU составляет 50–200 миллисекунд.
• Высокое: 13–14 (8192–16384 итераций) — для систем с повышенными требованиями к безопасности.
• Максимальное: 31 (2,1 миллиарда итераций) — практически не используется из-за чрезмерного времени вычисления.

Соль (Salt)

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

Версии алгоритма

• $2a$ — оригинальная версия, содержащая уязвимость к атакам по времени при обработке символов с кодами выше 127 (например, UTF-8). В настоящее время не рекомендуется к использованию.
• $2b$ — исправленная версия, принятая в OpenBSD 5.5 (2014 год). Устраняет проблему с кодировкой, корректно обрабатывая все байты. Является стандартом де-факто.
• $2x$ и $2y$ — временные версии, использовавшиеся для миграции старых баз данных с $2a$ на $2b$.

Применение

Bcrypt широко применяется в различных областях информационной безопасности:

Хранение паролей

Основное применение — хеширование паролей перед сохранением в базу данных. В случае утечки базы данных злоумышленник не сможет восстановить исходные пароли без значительных вычислительных затрат. Bcrypt используется в:

• Веб-фреймворках: Django, Ruby on Rails, Spring Security, ASP.NET Core.
• Системах управления базами данных: PostgreSQL (расширение pgcrypto), MongoDB.
• Менеджерах паролей: KeePass, Bitwarden.
• Протоколах аутентификации: OpenID Connect, OAuth 2.0.

Криптовалюты и блокчейн

Bcrypt иногда используется в качестве функции Proof-of-Work (доказательство работы) в некоторых криптовалютах, хотя для этой цели чаще применяются специализированные алгоритмы (SHA-256, Scrypt, Ethash). Например, Bcrypt использовался в ранних версиях криптовалюты Litecoin.

Шифрование ключей

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

Сравнение с другими хеш-функциями

MD5 и SHA-1

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

SHA-256 и SHA-3

SHA-256 и SHA-3 являются криптостойкими хеш-функциями, но, как и MD5, не имеют встроенной соли и регулируемой сложности. При использовании для паролей требуется дополнительная реализация соли (например, PBKDF2-HMAC-SHA256) и многократное повторение итераций.

Scrypt

Scrypt — это функция, разработанная в 2009 году Колином Персивалем (Colin Percival) для хеширования паролей. В отличие от bcrypt, scrypt требует значительного объёма оперативной памяти (memory-hard), что делает её более устойчивой к атакам с использованием ASIC и FPGA. Bcrypt, в свою очередь, является CPU-bound (зависит от процессора) и требует меньше памяти, что делает её более простой в реализации на встраиваемых системах.

Argon2

Argon2 — победитель конкурса Password Hashing Competition (PHC) 2015 года. Является современной, memory-hard функцией с тремя вариантами: Argon2d (устойчив к атакам по времени), Argon2i (устойчив к атакам по побочным каналам) и Argon2id (гибридный). Argon2 считается более безопасным и гибким, чем bcrypt, но bcrypt остаётся более распространённым из-за своей зрелости и простоты использования.

Критика и ограничения

Уязвимость к атакам по времени (версия $2a$)

В оригинальной реализации bcrypt ($2a$$) была обнаружена уязвимость к атакам по времени при обработке символов с кодами выше 127 (например, кириллица, иероглифы). Эта уязвимость была исправлена в версии $2b$ (OpenBSD 5.5, 2014 год). Версия $2a$ не рекомендуется к использованию.

Отсутствие защиты от ASIC

Bcrypt не является memory-hard функцией, то есть не требует значительного объёма оперативной памяти. Это делает её уязвимой для атак с использованием специализированных ASIC-чипов, которые могут выполнять миллионы итераций bcrypt в секунду. Для защиты от ASIC рекомендуется использовать scrypt или Argon2.

Максимальная длина пароля

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

Регулируемая сложность

Хотя регулируемая сложность является преимуществом, она также создаёт проблему: при увеличении параметра стоимости время аутентификации пользователя растёт. Для систем с высокой нагрузкой (например, миллионы пользователей) это может привести к значительным задержкам. Требуется тщательный баланс между безопасностью и производительностью.

Интересные факты

• Название «bcrypt» происходит от «Blowfish crypt» (шифрование Blowfish).
• Bcrypt используется в операционной системе OpenBSD для хранения паролей пользователей с 1999 года.
• В 2020 году исследователи из компании Cisco обнаружили, что около 30% протестированных веб-сайтов используют bcrypt для хранения паролей, что делает его второй по популярности функцией после SHA-256 (часто используемой неправильно).
• В 2023 году была опубликована работа, демонстрирующая возможность атаки на bcrypt с использованием FPGA-массивов, которая позволяет подбирать пароли со скоростью до 10 000 попыток в секунду при параметре стоимости 10.

Источники

• Provos, N., & Mazières, D. (1999). A Future-Adaptable Password Scheme. USENIX Annual Technical Conference.
• Schneier, B. (1993). Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish). Fast Software Encryption.
• Percival, C. (2009). Stronger Key Derivation via Sequential Memory-Hard Functions. BSDCan 2009.
• Biryukov, A., Dinu, D., & Khovratovich, D. (2016). Argon2: the memory-hard function for password hashing and other applications. Password Hashing Competition.
• OpenBSD 5.5 Release Notes (2014). Fix for bcrypt time-based side-channel attack.