Bcrypt

bcrypt — адаптивна криптографічна функція формування ключа, що використовується для безпечного зберігання паролів. Розробники: Шаблон:Iw і David Mazières. Функція заснована на шифрі Blowfish, вперше представлена на USENIX у 1999 році. Для захисту від атак за допомогою райдужних таблиць bcrypt використовує сіль (salt); крім того, функція є адаптивною, час її роботи легко налаштовується і її можна сповільнити, щоб ускладнити атаки перебором.

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

Спочатку реалізовано функції crypt в OpenBSD. Існують реалізації для Java, Python, Nim, C#, Ruby, Perl, PHP 5.3, Node.js та деяких інших.

Алгоритм

Алгоритм bcrypt використовує алгоритм налаштування ключів з «Eksblowfish»:

EksBlowfishSetup(cost, salt, key)
 state $\leftarrow$ InitState()
 state $\leftarrow$ ExpandKey(state, salt, key)
 repeat (2cost)
 state $\leftarrow$ ExpandKey(state, 0, key)
 state $\leftarrow$ ExpandKey(state, 0, salt)
 return state

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

Функція ExpandKey:

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

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

bcrypt(cost, salt, key, input)
 state $\leftarrow$ EksBlowfishSetup(cost, salt, key)
 ctext $\leftarrow$ input
 repeat(64)
 ctext $\leftarrow$ EncryptECB(state, ctext) // шифрування стандартним Blowfish в режимі ECB
 return Concatenate(cost, salt, ctext)

В різних ОС (linux, OpenBSD), використовують алгоритм bcrypt в стандартній функції crypt (3), в якості input подається константа «OrpheanBeholderScryDoubt».

Недоліки

bcrypt був розроблений в 1999 році і був захищений від ефективного перебору на апаратних засобах того часу. В даний час одержали широке поширення ПЛІС, в яких bcrypt реалізується ефективніше. У 2009 був створений алгоритм scrypt, що вимагає для своєї роботи значний обсяг пам'яті (з випадковим доступом), об'єм пам'яті налаштовується.

У порівнянні з PBKDF2, алгоритм розширення ключа в bcrypt практично не досліджувався криптографами.

Дивись також

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

Посилання

• jBCrypt — реалізація bcrypt на Java Шаблон:Webarchive
• py-bcrypt — реалізація bcrypt на Python Шаблон:Webarchive
• BCrypt.Net — реалізація bcrypt на C# Шаблон:Webarchive
• JFBCrypt — реалізація bcrypt на Objective C
• bcrypt-ruby — реалізація bcrypt на Ruby
• Crypt::Eksblowfish::Bcrypt — реалізація bcrypt на Perl
• bcrypt.js — реалізація bcrypt на JavaScript Шаблон:Webarchive
• twin-bcrypt — реалізація bcrypt на JavaScript / asm.js Шаблон:Webarchive
• bcrypt.go — реалізація bcrypt на Go Шаблон:Webarchive
• tutanota.com — приклад використання bcrypt в сервісі end-to-end шифрованого пошти Шаблон:Webarchive