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 InitState()
state ExpandKey(state, salt, key)
repeat (2cost)
state ExpandKey(state, 0, key)
state ExpandKey(state, 0, salt)
return state
Функція InitState відповідає оригінальній функції з шифру Blowfish; для заповнення масиву P і S-box використовується дробова частина числа .
Функція ExpandKey:
ExpandKey(state, salt, key)
for(n = 1..18)
Pn key[32(n-1)..32n-1] Pn //treat the key as cyclic
ctext Encrypt(salt[0..63])
P1 ctext[0..31]
P2 ctext[32..63]
for(n = 2..9)
ctext Encrypt(ctext salt[64(n-1)..64n-1]) //encrypt using the current key schedule and treat the salt as cyclic
P2n-1) ctext[0..31]
P2n ctext[32..63]
for(i = 1..4)
for(n = 0..127)
ctext Encrypt(ctext salt[64(n-1)..64n-1]) //as above
Si[2n] ctext[0..31]
Si[2n+1] ctext[32..63]
return state
Для обчислення хешу bcrypt обробляє вхідні дані еквівалентно шифруванню 'eksblowfish(посилений_ключ, input)':
bcrypt(cost, salt, key, input)
state EksBlowfishSetup(cost, salt, key)
ctext input
repeat(64)
ctext 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].
Дивись також
Посилання
Примітки