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 и других языках.

Фон

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\__/\/ \____________________/\_____________________________/Alg Cost Salt Hash

Где:

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

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

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

2 доллара (1999)

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

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

$2a$

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

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

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

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

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

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

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

В реализации bcrypt в OpenBSD была обнаружена ошибка. Для хранения длины пароля использовалось беззнаковое 8-битное значение. ^{[11] [13] [14]} Для паролей длиной более 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 (поля подстановки) шестнадцатеричными цифрами pi  P , S ← InitialState()  //Поменять местами P и S на основе пароля и соли  P , S ← ExpandKey( P , S , пароль , соль ) //Это «Дорогая» часть «Дорогой настройки ключей».  //В остальном настройка ключей идентична Blowfish.  повтор (2 стоимости ) P , S ← ExpandKey( P , S , пароль, 0) P , S ← ExpandKey( P , S , соль, 0) вернуть  П , С

InitialState работает так же, как и исходный алгоритм Blowfish, заполняя записи P-массива и S-box дробной частью в шестнадцатеричном формате. ${\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]  Четыре SBox по 1 КБ   //Смешиваем пароль с массивом подключей P  для  n ← от 1 до 18 do P n ← P n  xor  пароль [32(n-1)..32n-1] // обрабатываем пароль как циклический  //Считаем 128-битную соль как две 64-битные половины (размер блока Blowfish).  saltHalf[0] ← salt [0..63] //Младшие 64 бита соли saltHalf[1] ← salt [64..127] //Верхние 64 бита соли //Инициализируем 8-байтовый (64-битный) буфер нулями. блок ← 0 //Смешиваем внутреннее состояние в P-блоки  для  n ← от 1 до 9 do  //xor 64-битный блок с 64-битным полублоком соли  ← block xor saltHalf [ (n-1) mod 2] //каждая итерация чередуется между saltHalf [0] и saltHalf [1] // зашифровать блок с использованием текущего ключа  блока расписания ← Шифровать( P , S , блок ) P 2n ← блок [0..31] //младшие 32 бита блока P 2n+1 ← блок [32..63] //старшие 32-битный блок //Смешиваем зашифрованное состояние во внутренние S-блоки состояний  для  i ← от 1 до 4 do  for  n ← от 0 до 127 do  block ← Encrypt( state , block  xor  salt [64(n-1)..64n-1]) //как указано выше S i [2n] ← блок [0..31] // младшие 32 бита S i [2n+1] ← блок [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 ] каждый бит каждого подраздела зависит от каждого бита ключа». ^[15]

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

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

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

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

• PBKDF2 : pbkdf2 слабее, чем bcrypt. Широко используемый алгоритм хеширования SHA2 не требует большого объема памяти. SHA2 спроектирован так, чтобы быть чрезвычайно легким, поэтому его можно запускать на легких устройствах (например, смарт-картах). ^[17] Это означает, что PBKDF2 очень слаб для хранения паролей, поскольку легко приобрести стандартное оборудование для хеширования SHA-2, способное выполнять триллионы хэшей в секунду. ^{[18] [19]}
• scrypt : scrypt слабее, чем bcrypt, для требований к памяти менее 4 МБ. ^[20] scrypt требует примерно в 1000 раз больше памяти, чем bcrypt, для достижения сопоставимого уровня защиты от атак на основе графического процессора (для хранения паролей).
• argon2 : bcrypt более легкий, чем Argon2. Это может создать проблему для некоторых веб-приложений, где использование Argon2 потребует снижения параметров безопасности до неприемлемого уровня, чтобы сохранить производительность. В частности, Argon2 менее безопасен, чем bcrypt, для времени выполнения менее 1 секунды (т. е. для аутентификации с использованием общего пароля). Argon2 не соответствует мощности bcrypt и не превосходит ее до тех пор, пока время выполнения не превысит ~1000 мс. ^{[ нужна цитация ]} Это может быть непригодно для хеширования паролей, но вполне приемлемо для получения ключей. ^[21] В некоторых случаях рекомендуется использовать Argon2 вместо bcrypt, если параметры безопасности достаточно высоки. ^[22]
• 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 ^[23] ). Это делает pufferfish2 гораздо более устойчивым к графическому процессору или ASIC.

Критика

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

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

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

Пароль (в кодировке 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 байта)

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

Алгоритм 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 символом при кодировании по системе счисления 64:

fQAtluK7q2uGV7HcJYncfII3WbJvIai (31 символ)

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

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

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

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

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

Рекомендации

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

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

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