bcrypt

Функция выработки ключа на основе пароля

bcrypt — это функция хеширования паролей, разработанная Нильсом Провосом и Дэвидом Мазьером на основе шифра Blowfish и представленная на конференции USENIX в 1999 году. ^[1] Помимо включения соли для защиты от атак с использованием радужных таблиц , bcrypt является адаптивной функцией: со временем количество итераций можно увеличить, чтобы замедлить ее работу, поэтому она остается устойчивой к атакам методом перебора даже при увеличении вычислительной мощности.

Функция bcrypt является алгоритмом хеширования паролей по умолчанию для OpenBSD [ 2 ^{] [ необходим неосновной источник ]} и использовалась по умолчанию для некоторых дистрибутивов Linux , таких как SUSE Linux . ^[3]

Существуют реализации bcrypt на языках C , C++ , C# , Embarcadero Delphi , Elixir , ^[4] Go , ^[5] Java , ^{[6] [7]} JavaScript , ^[8] Perl , PHP , Ruby , Python , Rust ^[9] , Zig ^[10] и других.

Фон

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

Провос и Мазьер воспользовались этим и пошли дальше. Они разработали новый алгоритм настройки ключа для Blowfish, назвав полученный шифр «Eksblowfish» («дорогой график ключей Blowfish»). Настройка ключа начинается с измененной формы стандартной настройки ключа Blowfish, в которой и соль, и пароль используются для установки всех подключаемых ключей. Затем есть несколько раундов, в которых применяется стандартный алгоритм ключа Blowfish, используя попеременно соль и пароль в качестве ключа, каждый раунд начинается с состояния подключаемого ключа из предыдущего раунда. Теоретически это не сильнее стандартного графика ключей Blowfish, но количество раундов переключений можно настраивать; поэтому этот процесс можно сделать произвольно медленным, что помогает сдерживать атаки методом перебора на хэш или соль.

Описание

Входные данные для функции bcrypt — строка пароля (до 72 байт), числовая стоимость и 16-байтовое (128-битное) значение соли. Соль обычно является случайным значением. Функция bcrypt использует эти входные данные для вычисления 24-байтового (192-битного) хеша. Окончательный вывод функции bcrypt — строка в форме:

$2<a/b/x/y>$[стоимость]$[соль из 22 символов][хеш из 31 символа]

Например, при вводе пароля abc123xyz, стоимости 12и случайной соли выход bcrypt представляет собой строку

$2a$12$R9h/cIPz0gi.URNNX3kh2OPST9/PgBkqquzi.Ss7KIUgO2t0jWMUW\__/\/ \____________________/\_____________________________/Стоимость Алг Соль Хэш

Где:

• $2a$: Идентификатор алгоритма хэширования (bcrypt)
• 12: Входная стоимость (2 ¹² т.е. 4096 раундов)
• R9h/cIPz0gi.URNNX3kh2O: Кодировка входной соли по алгоритму base-64
• PST9/PgBkqquzi.Ss7KIUgO2t0jWMUW: Кодировка первых 23 байтов вычисленного 24-байтового хэша в формате base-64

Кодировка base-64 в bcrypt использует таблицу ./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789[ ^11], которая отличается от кодировки Base64 RFC  4648 .

История версий

$2$ (1999)

Оригинальная спецификация bcrypt определяла префикс $2$. Это соответствует формату Modular Crypt Format ^[12] , используемому при хранении паролей в файле паролей OpenBSD:

• $1$: криптография на основе MD5 ('md5crypt')
• $2$: Криптография на основе Blowfish ('bcrypt')
• $sha1$: шифрование на основе SHA-1 ('sha1crypt')
• $5$: криптография на основе SHA-256 ('sha256crypt')
• $6$: криптография на основе SHA-512 ('sha512crypt')

$2a$

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

• строка должна быть в кодировке UTF-8
• нулевой терминатор должен быть включен

С этим изменением версия была изменена на $2a$^[13]

$2x$, $2y$ (июнь 2011 г.)

В июне 2011 года была обнаружена ошибка в crypt_blowfish , PHP-реализации bcrypt. Она заключалась в неправильной обработке символов с установленным 8-м битом. ^[14] Они предложили системным администраторам обновить существующую базу данных паролей, заменив ее $2a$на $2x$, чтобы указать, что эти хэши плохие (и нужно использовать старый сломанный алгоритм). Они также предложили идею, чтобы crypt_blowfish выдавал $2y$хэши, сгенерированные исправленным алгоритмом.

Никто другой, включая Canonical и OpenBSD, не принял идею 2x/2y. Это изменение маркера версии было ограничено crypt_blowfish .

$2 млрд. (февраль 2014 г.)

В реализации bcrypt в OpenBSD была обнаружена ошибка. Она использовала беззнаковое 8-битное значение для хранения длины пароля. ^{[13] [15] [16]} Для паролей длиной более 255 байт вместо усечения до 72 байт пароль усекался до меньшего из 72 или длины по модулю 256. Например, пароль длиной 260 байт усекался до 4 байт, а не до 72 байт.

bcrypt был создан для OpenBSD. Когда у них обнаружилась ошибка в библиотеке, они решили поднять номер версии.

Алгоритм

Функция bcrypt ниже шифрует текст "OrpheanBeholderScryDoubt" 64 раза с помощью Blowfish . В bcrypt обычная функция настройки ключа Blowfish заменена на дорогостоящую функцию настройки ключа (EksBlowfishSetup):

Функция bcrypt  Входные данные: стоимость: число (4..31)  log 2 (итерации). например, 12 ==> 2 12 = 4096 итераций соль: массив байтов (16 байт)  случайная соль пароль: массив байтов (1..72 байта)  пароль в кодировке UTF-8  Выходные данные:  хэш: массив байтов (24 байта) //Инициализация состояния Blowfish с помощью дорогостоящего алгоритма настройки ключа  //P: массив из 18 подключаемых ключей (UInt32[18])  //S: Четыре подстановочных блока (S-блока), S 0 ...S 3 . Каждый S-блок имеет размер 1024 байта (UInt32[256])  P , S ← EksBlowfishSetup( пароль , соль , стоимость )  // Повторно шифруем текст "OrpheanBeholderScryDoubt" 64 раза  ctext ← "OrpheanBeholderScryDoubt"  // 24 байта ==> три 64-битных блока  повторяются (64) ctext ← EncryptECB( P , S , ctext ) // шифруем с помощью стандартного Blowfish в режиме ECB //24-байтовый ctext — это результирующий хеш пароля  return Concatenate( cost , salt , ctext )

Дорогая установка ключа

Алгоритм bcrypt во многом зависит от алгоритма настройки ключа «Eksblowfish», который работает следующим образом:

Функция EksBlowfishSetup  Входные данные: пароль: массив байтов (1..72 байта)  пароль в кодировке UTF-8 соль: массив байтов (16 байт)  случайная соль стоимость: число (4..31)  log 2 (итерации). например, 12 ==> 2 12 = 4096 итераций  Выходные данные: P: массив UInt32  массив из 18 подключаемых ключей на раунд S 1 ..S 4 : массив UInt32  массив из четырех SBox; каждый SBox имеет размер 256 UInt32 ( т. е. каждый SBox имеет размер 1 КиБ) //Инициализируем P (подключи) и S (поля подстановки) шестнадцатеричными цифрами числа пи  P , S ← InitialState()  //Переставляем P и S на основе пароля и соли  P , S ← ExpandKey( P , S , пароль , соль ) //Это «дорогая» часть «дорогой настройки ключа».  //В остальном настройка ключа идентична Blowfish.  repeat (2 cost ) P , S ← ExpandKey( P , S , password, 0) P , S ← ExpandKey( P , S , salt, 0) возврат  П , С

InitialState работает так же, как и в оригинальном алгоритме Blowfish, заполняя записи P-массива и S-поля дробной частью в шестнадцатеричном формате. ${\displaystyle \pi }$

Развернуть ключ

Функция ExpandKey выполняет следующие действия:

Функция ExpandKey  Входные данные: P: массив UInt32  Массив из 18 подключаемых ключей S 1 ..S 4 : UInt32[1024]  Четыре SBoxes по 1 КБ пароль: массив байтов (1..72 байта)  пароль в кодировке UTF-8 соль: случайная соль Byte[16]  Выходные данные: P: массив UInt32  Массив из 18 подключаемых ключей на раунд S 1 ..S 4 : UInt32[1024]  Четыре SBoxes по 1 КБ   //Добавить пароль в массив подключей P  for  n ← 1 to 18 do P n ← P n  xor  password [32(n-1)..32n-1] //рассматривать пароль как циклический  //Рассматривать 128-битную соль как две 64-битные половины (размер блока Blowfish). saltHalf[0] ← соль [0..63] //Нижние 64 бита соли saltHalf[1] ← соль [64..127] //Верхние 64 бита соли //Инициализируем 8-байтовый (64-битный) буфер всеми нулями. блок ← 0 //Смешиваем внутреннее состояние в P-boxes  для  n ← 1 до 9 do  //xor 64-битного блока с 64-битной солью half  block ← block xor saltHalf [(n-1) mod 2] //каждая итерация чередуется между saltHalf [0] и saltHalf [1] // зашифровать блок, используя текущий ключевой график  block ← Encrypt( P , S , block ) P 2n ← блок [0..31] //нижние 32 бита блока P 2n+1 ← блок [32..63] //верхние 32 бита блока //Смешиваем зашифрованное состояние во внутренних S-блоках состояния  for  i ← 1 to 4 do  for  n ← 0 to 127 do  block ← Encrypt( state , block  xor  saltHalf [(n-1) mod 2]) //как указано выше S i [2n] ← block [0..31] //нижние 32 бита S i [2n+1] ← block [32..63] //верхние 32 бита  возвращают  состояние

Следовательно, совпадает с обычным расписанием ключей Blowfish, поскольку все XOR с нулевым значением соли неэффективны. аналогичен, но использует соль как 128-битный ключ.ExpandKey(state, 0, key)ExpandKey(state, 0, salt)

Пользовательский ввод

Многие реализации bcrypt обрезают пароль до первых 72 байтов, следуя реализации OpenBSD.

Сам математический алгоритм требует инициализации с 18 32-битными подключами (эквивалентно 72 октетам/байтам). Исходная спецификация bcrypt не предписывает какой-либо один конкретный метод преобразования текстовых паролей из пользовательского пространства в числовые значения для алгоритма. Один краткий комментарий в тексте упоминает, но не предписывает, возможность простого использования закодированного в ASCII значения строки символов: "Наконец, аргумент ключа - это секретный ключ шифрования, который может быть выбранным пользователем паролем длиной до 56 байт (включая завершающий нулевой байт, когда ключ - это строка ASCII)". ^[1]

Обратите внимание, что в приведенной выше цитате упоминаются пароли «до 56 байт», хотя сам алгоритм использует начальное значение в 72 байта. Хотя Провос и Мазьер не указывают причину более короткого ограничения, они могли быть мотивированы следующим утверждением из оригинальной спецификации Blowfish Брюса Шнайера : «Ограничение в 448 [бит] на размер ключа гарантирует, что [ sic ] каждый бит каждого подключа зависит от каждого бита ключа». ^[17]

Реализации различаются по подходу к преобразованию паролей в начальные числовые значения, включая иногда снижение надежности паролей, содержащих символы, не входящие в набор ASCII. ^[18]

Сравнение с другими алгоритмами хеширования паролей

Важно отметить, что bcrypt не является функцией вывода ключа (KDF) . Например, bcrypt не может использоваться для вывода 512-битного ключа из пароля. В то же время, такие алгоритмы, как pbkdf2 , scrypt и argon2, являются функциями вывода ключа на основе пароля, где вывод затем используется для хэширования пароля, а не просто для вывода ключа.

Обычно хеширование пароля должно быть завершено за < 1000 мс. В этом сценарии bcrypt сильнее, чем pbkdf2, scrypt и argon2.

• PBKDF2 : pbkdf2 слабее bcrypt. Обычно используемый алгоритм хеширования SHA2 не требует больших затрат памяти. SHA2 разработан так, чтобы быть чрезвычайно легким, поэтому он может работать на легких устройствах (например, смарт-картах). ^[19] Это означает, что PBKDF2 очень слаб для хранения паролей, поскольку легко приобрести стандартное оборудование для хеширования SHA-2, которое может выполнять триллионы хэшей в секунду. ^{[20] [21]}
• scrypt : scrypt слабее bcrypt при требованиях к памяти менее 4 МБ. ^[22] scrypt требует примерно в 1000 раз больше памяти, чем bcrypt, чтобы достичь сопоставимого уровня защиты от атак на основе графического процессора (для хранения паролей).
• argon2 : bcrypt легче, чем Argon2. Это может представлять проблему для некоторых веб-приложений, где использование Argon2 потребует снижения параметров безопасности до неприемлемого уровня, чтобы все еще быть производительным. В частности, Argon2 менее безопасен, чем bcrypt для времени выполнения менее 1 секунды (т. е. для обычной аутентификации пароля). Argon2 не достигает и не превосходит стойкость bcrypt, пока время выполнения не превысит ≈1000 мс. ^{[ необходима цитата ]} Это может быть неподходящим для хеширования паролей, но вполне приемлемо для выведения ключей. ^[23] В некоторых случаях Argon2 рекомендуется вместо bcrypt, если параметры безопасности достаточно высоки. ^[24]
• pufferfish2 — это эволюция bcrypt, которая использует настраиваемый объем памяти (как scrypt и argon2), а не фиксированный объем памяти 4 КБ bcrypt. Подобно scrypt или argon2, pufferfish2 получает свою сложность за счет использования большего объема памяти. В отличие от scrypt и argon2, pufferfish2 работает только в кэше L2 ядра ЦП. В то время как scrypt и argon2 получают свою жесткость памяти за счет случайного доступа к большому объему ОЗУ, pufferfish2 ограничивает себя только выделенным кэшем L2, доступным ядру ЦП. Это делает его еще более сложным для реализации в пользовательском оборудовании, чем scrypt и argon2. Идеальный объем памяти pufferfish2 — это размер кэша, доступного ядру (например, 1,25 МБ для Intel Alder Lake ^[25] ). Это делает pufferfish2 гораздо более устойчивым к графическим процессорам или ASIC.

Критика

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

bcrypt имеет максимальную длину пароля 72 байта. Этот максимум получается из первой операции функции ExpandKey , которая содержит xor's18 4-байтовых подключей (P) с паролем:

P 1 ..P 18 ← P 1 ..P 18 xor парольБайты

Пароль (в кодировке UTF-8) повторяется до тех пор, пока его длина не достигнет 72 байт. Например, пароль:

correct horse battery staple␀ (29 байт)

Повторяется до тех пор, пока не будет найдено соответствие 72 байтам 18 подключей P на раунд:

correct horse battery staple␀correct horse battery staple␀correct horse (72 байта)

В худшем случае пароль ограничен 18 символами, когда каждый символ требует 4 байта кодировки UTF-8. Например:

𐑜𐑝𐑟𐑥𐑷𐑻𐑽𐑾𐑿𐑿𐑰𐑩𐑛𐑙𐑘𐑙𐑒𐑔 (18 символов, 72 байта)

В 2024 году служба единого входа Okta, Inc. объявила об уязвимости, связанной с объединением пароля после имени пользователя и пары, хэшированной с помощью bcrypt, в результате чего пароль игнорировался при входе в систему с достаточно длинным именем пользователя ^[26] .

Усечение хэша пароля

Алгоритм bcrypt включает в себя многократное шифрование 24-байтового текста:

OrpheanBeholderScryDoubt (24 байта)

Это генерирует 24 байта зашифрованного текста, например:

85 20 af 9f 03 3d b3 8c 08 5f d2 5e 2d aa 5e 84 a2 b9 61 d2 f1 29 c9 a4 (24 байта)

Каноническая реализация OpenBSD обрезает это до 23 байтов ^{[ необходима ссылка ]} :

85 20 af 9f 03 3d b3 8c 08 5f d2 5e 2d aa 5e 84 a2 b9 61 d2 f1 29 c9 (23 байта)

Неясно, почему каноническая реализация удаляет 8 бит из результирующего хеша пароля. ^{[ необходима цитата ]}

Эти 23 байта превращаются в 31 символ при кодировании по системе счисления radix-64:

fQAtluK7q2uGV7HcJYncfII3WbJvIai (31 символ)

алфавит кодировки base64

Кодировка, используемая канонической реализацией OpenBSD, использует тот же алфавит Base64 , что и crypt , то есть ./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789. ^[11] Это означает, что кодировка несовместима с более распространенным RFC 4648 . ^{[ необходима цитата ]}

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

• Портал бесплатного и открытого программного обеспечения

• Argon2 — победитель конкурса по хешированию паролей в 2015 году
• bcrypt — кроссплатформенная утилита шифрования файлов на основе blowfish, разработанная в 2002 году ^{[27] [28] [29] [30]}
• crypt — функция библиотеки Unix C
• crypt - утилита Unix
• ccrypt - утилита
• Растяжка ключа
• mcrypt - утилита
• PBKDF2 — широко используемая стандартная функция деривации ключа на основе пароля 2
• scrypt - функция получения ключа на основе пароля (а также утилита)
• дакрипт

Ссылки

1. Provos N , Maziéres D (10 июня 1999 г.). Схема паролей, адаптируемая к будущему (PDF) . Ежегодная техническая конференция USENIX 1999 г. Том. Труды FREENIX Track. Монтерей, Калифорния: Ассоциация USENIX .
2. "Журнал CVS для src/lib/libc/crypt/bcrypt.c". Репозиторий CVS . OpenBSD . 23 марта 2014 г. Версия 1.32 (первое упоминание bcrypt в журнале) . Получено 25 мая 2023 г .. минимальное изменение в реализации bcrypt для того, чтобы не требовать статические глобальные переменные
3. "SUSE Security Announcement: (SUSE-SA:2011:035)". Security Advisories . SUSE . 23 августа 2011 г. Архивировано из оригинала 4 марта 2016 г. Получено 20 августа 2015 г. Реализация crypt() в SUSE поддерживает функцию хеширования паролей blowfish (id $2a), и системные входы по умолчанию также используют этот метод.
4. Уитлок, Дэвид (21 сентября 2021 г.). «Bcrypt Elixir: алгоритм хеширования паролей bcrypt для Elixir». GitHub . riverrun.
5. "Пакет bcrypt". godoc.org .
6. "jBCrypt - надежное хеширование паролей для Java". www.mindrot.org . Получено 11.03.2017 .
7. "bcrypt - автономная реализация Java хэш-функции пароля bcrypt". github.com . Получено 2018-07-19 .
8. "bcryptjs". npm . riverrun. 7 февраля 2017 г.
9. "rust-bcrypt". GitHub . Винсент Пруйе. 8 ноября 2024 г.
10. "zigstd". GitHub . jedisct1. 26 октября 2020 г.
11. Provos, Niels (13 февраля 1997 г.). "исходный код bcrypt.c, строки 57-58" . Получено 29 января 2022 г.
12. «Модульный формат шифрования — Документация Passlib v1.7.1». passlib.readthedocs.io .
13. "Исправлены ошибки хэша паролей bcrypt, изменения версий и последствия". undeadly.org .
14. Дизайнер, Solar. "oss-sec: запрос CVE: неправильная обработка 8-битных символов crypt_blowfish". seclists.org .
15. "'изменения версии bcrypt' - MARC". marc.info .
16. "bcrypt.c code fix for 2014 bug". 17 февраля 2014 г. Архивировано из оригинала 18 февраля 2022 г. Получено 17 февраля 2022 г.
17. Шнайер, Брюс (декабрь 1993 г.). «Быстрое программное шифрование, описание нового ключа переменной длины, 64-битный блочный шифр (Blowfish)». Труды Кембриджского семинара по безопасности . Springer-Verlag: 191–204.
18. "Рекомендации по безопасности jBCrypt". 1 февраля 2010 г.И «Изменения в CRYPT_BLOWFISH в PHP 5.3.7». php.net .
19. Безопасный стандарт хэширования nist.gov
20. "Рентабельность Goldshell KD6 | Стоимость майнера ASIC". www.asicminervalue.com .
21. «Рентабельность Goldshell KD6».
22. «Почему я не рекомендую Scrypt». 12 марта 2014 г.
23. «Argon2 против bcrypt против scrypt: какой алгоритм хеширования вам подходит?». Март 2023 г.
24. «Шпаргалка по хранению паролей OWASP».
25. «Характеристики продукта».
26. Джонс, Коннер (4 ноября 2024 г.). «Почему длинное имя? Okta раскрывает ошибку обхода аутентификации, влияющую на имена пользователей из 52 символов». The Register . Получено 5 ноября 2024 г.
27. Домашняя страница программы шифрования файлов bcrypt
28. "bcrypt APK для Android - бесплатная загрузка на Droid Informer". droidinformer.org .
29. "Пакет T2 - trunk - bcrypt - Утилита для шифрования файлов". t2sde.org .
30. "Oracle GoldenGateのライセンス" . docs.oracle.com .

Внешние ссылки

• crypt_blowfish, реализация, поддерживаемая Openwall