bcrypt

bcrypt — адаптивная криптографическая хеш-функция формирования ключа, используемая для защищенного хранения паролей. Разработчики: Нильс Провос и David Mazières. Функция основана на шифре Blowfish, впервые представлена на USENIX в 1999 году^[1]. Для защиты от атак с помощью радужных таблиц bcrypt использует соль (salt); кроме того, функция является адаптивной, время её работы легко настраивается и её можно замедлить, чтобы усложнить атаку перебором.

Шифр Blowfish отличается от многих алгоритмов вычислительно сложной фазой подготовки ключей шифрования^[англ.].

Провос и Mazières воспользовались этой особенностью, но изменили алгоритм подготовки ключей, получив шифр «Eksblowfish» (expensive key schedule Blowfish). Количество раундов в подготовке ключей должно быть степенью двойки; конкретная степень может задаваться при использовании bcrypt.

Изначально реализовано в функции crypt в OpenBSD. Существуют реализации для Java, Python, Nim, C#, Ruby, Perl, PHP 5.3, Node.js, Go^[2] и некоторых других.

Алгоритм bcrypt использует алгоритм настройки ключей из «Eksblowfish»:

EksBlowfishSetup(cost, salt, key)
    state ${\displaystyle \gets }$ InitState()
    state ${\displaystyle \gets }$ ExpandKey(state, salt, key)
    repeat (2cost)
        state ${\displaystyle \gets }$ ExpandKey(state, 0, key)
        state ${\displaystyle \gets }$ ExpandKey(state, 0, salt)
    return state

Функция InitState соответствует оригинальной функции из шифра Blowfish; для заполнения массива P и S-box используется дробная часть числа ${\displaystyle \pi }$.

Функция ExpandKey:

ExpandKey(state, salt, key)
    for(n = 1..18)
        Pn ${\displaystyle \gets }$ key[32(n-1)..32n-1] ${\displaystyle \oplus }$ Pn //treat the key as cyclic
    ctext ${\displaystyle \gets }$ Encrypt(salt[0..63])
    P1 ${\displaystyle \gets }$ ctext[0..31]
    P2 ${\displaystyle \gets }$ ctext[32..63]
    for(n = 2..9)
        ctext ${\displaystyle \gets }$ Encrypt(ctext ${\displaystyle \oplus }$ salt[64(n-1)..64n-1]) //encrypt using the current key schedule and treat the salt as cyclic
        P2n-1) ${\displaystyle \gets }$ ctext[0..31]
        P2n ${\displaystyle \gets }$ ctext[32..63]
    for(i = 1..4)
        for(n = 0..127)
            ctext ${\displaystyle \gets }$ Encrypt(ctext ${\displaystyle \oplus }$ salt[64(n-1)..64n-1]) //as above
            Si[2n] ${\displaystyle \gets }$ ctext[0..31]
            Si[2n+1] ${\displaystyle \gets }$ ctext[32..63]
    return state

Для вычисления хеша bcrypt обрабатывает входные данные эквивалентно шифрованию 'eksblowfish(усиленный_ключ, input)':

bcrypt(cost, salt, key, input)
    state ${\displaystyle \gets }$ EksBlowfishSetup(cost, salt, key)
    ctext ${\displaystyle \gets }$ input
    repeat (64)
        ctext ${\displaystyle \gets }$ EncryptECB(state, ctext) // шифрование стандартным Blowfish в режиме ECB
    return Concatenate(cost, salt, ctext)

В различных ОС (linux, OpenBSD), использующих алгоритм bcrypt в стандартной функции crypt (3), в качестве input подается константа «OrpheanBeholderScryDoubt»^[3].

bcrypt был разработан в 1999 году и был защищен от эффективного перебора на аппаратных средствах того времени. В настоящее время получили широкое распространение ПЛИС, в которых bcrypt реализуется эффективнее. В 2009 был создан алгоритм scrypt, требующий для своей работы значительный объем памяти (со случайным доступом), объем памяти настраивается^[4].

В сравнении с PBKDF2, алгоритм расширения ключа в bcrypt практически не исследовался криптографами^[5].

• Crypt (Unix)
• Crypt (C)
• PBKDF2
• scrypt

• jBCrypt — реализация bcrypt на Java
• py-bcrypt — реализация bcrypt на Python
• BCrypt.Net- реализация bcrypt на C#
• JFBCrypt — реализация bcrypt на Objective C
• bcrypt-ruby — реализация bcrypt на Ruby
• Crypt::Eksblowfish::Bcrypt — реализация bcrypt на Perl
• bcrypt.js — реализация bcrypt на JavaScript
• twin-bcrypt — реализация bcrypt на JavaScript / asm.js
• bcrypt.go — реализация bcrypt на Go Архивная копия от 4 октября 2014 на Wayback Machine
• tutanota.com — пример использования bcrypt в сервисе end-to-end шифрованной почты