Bcrypt

bcrypt — адаптивна криптографічна функція формування ключа, що використовується для безпечного зберігання паролів. Розробники: Нільс Провос^[en] і 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 та деяких інших.

Алгоритм

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

EksBlowfishSetup(cost, salt, key)
 state ${\displaystyle \gets }$ InitState()
 state ${\displaystyle \gets }$ ExpandKey(state, salt, key)
 repeat (2^cost)
 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»[2].

Недоліки

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

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

Дивись також

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

Посилання

• jBCrypt — реалізація bcrypt на Java [Архівовано 27 квітня 2018 у Wayback Machine.]
• py-bcrypt — реалізація bcrypt на Python [Архівовано 22 червня 2017 у Wayback Machine.]
• BCrypt.Net — реалізація bcrypt на C# [Архівовано 1 липня 2014 у Wayback Machine.]
• JFBCrypt — реалізація bcrypt на Objective C
• bcrypt-ruby — реалізація bcrypt на Ruby
• Crypt::Eksblowfish::Bcrypt — реалізація bcrypt на Perl
• bcrypt.js — реалізація bcrypt на JavaScript [Архівовано 27 березня 2016 у Wayback Machine.]
• twin-bcrypt — реалізація bcrypt на JavaScript / asm.js [Архівовано 11 червня 2018 у Wayback Machine.]
• bcrypt.go — реалізація bcrypt на Go [Архівовано 4 жовтня 2014 у Wayback Machine.]
• tutanota.com — приклад використання bcrypt в сервісі end-to-end шифрованого пошти [Архівовано 28 січня 2017 у Wayback Machine.]

Примітки

1. Provos, Niels; Mazières, David; Talan Jason Sutton 2012 (1999). «A Future-Adaptable Password Scheme». Proceedings of 1999 USENIX Annual Technical Conference: 81–92.
2. Архівована копія (PDF). Архів оригіналу (PDF) за 15 червня 2018. Процитовано 13 квітня 2018.
3. http://www.unlimitednovelty.com/2012/03/dont-use-bcrypt.html [Архівовано 14 квітня 2018 у Wayback Machine.] «Not only does scrypt give you more theoretical safety than bcrypt per unit compute time, but it also allows you to configure the amount of space in memory needed to compute the result.»
4. http://www.unlimitednovelty.com/2012/03/dont-use-bcrypt.html [Архівовано 14 квітня 2018 у Wayback Machine.] «Unlike bcrypt, PBKDF2 has been the subject of intense research and still remains the best conservative choice.»