bcrypt

Информацию об утилите шифрования файлов bcrypt см. в разделе Blowfish (шифр) .

bcrypt

Общий
Дизайнеры	Нильс Провос , Давид Мазьер
Впервые опубликовано	1999
Получено из	Иглобрюхая рыба (шифр)
Деталь
Размеры дайджеста	184 бит
Раунды	переменная через параметр стоимости

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

Функция bcrypt — это алгоритм хэширования паролей по умолчанию для OpenBSD . и был значением по умолчанию для некоторых дистрибутивов Linux, таких как SUSE Linux .

Существуют реализации bcrypt на C , C++ , C# , Embarcadero Delphi , Elixir , Идти , Ява , JavaScript , Perl , PHP , Ruby , Python и другие языки.

Предыстория

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

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

Описание

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

$2<a/b/x/y>$[cost]$[22 character salt][31 character hash]

Например, при вводе пароля 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 использует таблицу ./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789, который отличается от Кодировка RFC   4648 Base64 .

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

$2$ (1999)

Исходная спецификация bcrypt определяла префикс $2$. Это соответствует модульного склепа . формату формат, используемый при хранении паролей в файле паролей OpenBSD:

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

$2a$

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

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

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

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

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

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

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

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

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

Алгоритм

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

Function bcrypt
   Input:
      cost:     Number (4..31)                      log2(Iterations). e.g. 12 ==> 212 = 4,096 iterations
      salt:     array of Bytes (16 bytes)           random salt
      password: array of Bytes (1..72 bytes)        UTF-8 encoded password
   Output: 
      hash:     array of Bytes (24 bytes)

   //Initialize Blowfish state with expensive key setup algorithm
   //P: array of 18 subkeys (UInt32[18])
   //S: Four substitution boxes (S-boxes), S0...S3. Each S-box is 1,024 bytes (UInt32[256])
   P, S ← EksBlowfishSetup(password, salt, cost)   

   //Repeatedly encrypt the text "OrpheanBeholderScryDoubt" 64 times
   ctext ← "OrpheanBeholderScryDoubt"  //24 bytes ==> three 64-bit blocks
   repeat (64)
      ctext ← EncryptECB(P, S, ctext) //encrypt using standard Blowfish in ECB mode

   //24-byte ctext is resulting password hash
   return Concatenate(cost, salt, ctext)

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

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

Function EksBlowfishSetup
   Input:
      password: array of Bytes (1..72 bytes)   UTF-8 encoded password
      salt:     array of Bytes (16 bytes)      random salt
      cost:     Number (4..31)                 log2(Iterations). e.g. 12 ==> 212 = 4,096 iterations
   Output: 
      P:        array of UInt32                array of 18 per-round subkeys
      S1..S4:   array of UInt32                array of four SBoxes; each SBox is 256 UInt32 (i.e. each SBox is 1 KiB)

   //Initialize P (Subkeys), and S (Substitution boxes) with the hex digits of pi 
   P, S ← InitialState() 
 
   //Permute P and S based on the password and salt     
   P, S ← ExpandKey(P, S, password, salt)

   //This is the "Expensive" part of the "Expensive Key Setup".
   //Otherwise the key setup is identical to Blowfish.
   repeat (2cost)
      P, S ← ExpandKey(P, S, password, 0)
      P, S ← ExpandKey(P, S, salt, 0)

   return P, S

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

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

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

Function ExpandKey
   Input:
      P:        array of UInt32               Array of 18 subkeys
      S1..S4:   UInt32[1024]                  Four 1 KB SBoxes
      password: array of Bytes (1..72 bytes)  UTF-8 encoded password
      salt:     Byte[16]                      random salt
   Output: 
      P:        array of UInt32               Array of 18 per-round subkeys
      S1..S4:   UInt32[1024]                  Four 1 KB SBoxes       
 
   //Mix password into the P subkeys array
   for n ← 1 to 18 do
      Pn ← Pn xor password[32(n-1)..32n-1] //treat the password as cyclic
 
   //Treat the 128-bit salt as two 64-bit halves (the Blowfish block size).
   saltHalf[0] ← salt[0..63]  //Lower 64-bits of salt
   saltHalf[1] ← salt[64..127]  //Upper 64-bits of salt

   //Initialize an 8-byte (64-bit) buffer with all zeros.
   block ← 0

   //Mix internal state into P-boxes   
   for n ← 1 to 9 do
      //xor 64-bit block with a 64-bit salt half
      block ← block xor saltHalf[(n-1) mod 2] //each iteration alternating between saltHalf[0], and saltHalf[1]

      //encrypt block using current key schedule
      block ← Encrypt(P, S, block) 
      P2n ← block[0..31]      //lower 32-bits of block
      P2n+1 ← block[32..63]  //upper 32-bits block

   //Mix encrypted state into the internal S-boxes of state
   for i ← 1 to 4 do
      for n ← 0 to 127 do
         block ← Encrypt(state, block xor saltHalf[(n-1) mod 2]) //as above
         Si[2n]   ← block[0..31]  //lower 32-bits
         Si[2n+1] ← block[32..63]  //upper 32-bits
    return state

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

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

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

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

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

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

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

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

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

• PBKDF2 : pbkdf2 слабее, чем bcrypt. Широко используемый алгоритм хеширования SHA2 не требует большого объема памяти. SHA2 спроектирован так, чтобы быть чрезвычайно легким, поэтому его можно запускать на легких устройствах (например, смарт-картах). Это означает, что PBKDF2 очень слаб для хранения паролей, поскольку легко приобрести стандартное оборудование для хеширования SHA-2, способное выполнять триллионы хэшей в секунду.
• scrypt : scrypt слабее, чем bcrypt, для требований к памяти менее 4 МБ. scrypt требует примерно в 1000 раз больше памяти, чем bcrypt, для достижения сопоставимого уровня защиты от атак на основе графического процессора (для хранения паролей).
• argon2 : bcrypt более легкий, чем Argon2. Это может создать проблему для некоторых веб-приложений, где использование Argon2 потребует снижения параметров безопасности до неприемлемого уровня, чтобы сохранить производительность. В частности, Argon2 менее безопасен, чем bcrypt, для времени выполнения менее 1 секунды (т. е. для аутентификации с использованием общего пароля). Argon2 не соответствует мощности bcrypt и не превосходит ее до тех пор, пока время выполнения не превысит ≈1000 мс. Это может быть непригодно для хеширования паролей, но вполне приемлемо для получения ключей. В некоторых случаях рекомендуется использовать Argon2 вместо bcrypt, если параметры безопасности достаточно высоки.
• 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). ) Это делает Pufferfish2 гораздо более устойчивым к GPU или ASIC.

Критика

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

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

P1..P18 ← P1..P18 xor passwordBytes

Пароль (в кодировке 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. Это означает, что кодировка несовместима с более распространенным RFC 4648 .

См. также

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

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

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