bcrypt

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

Алгоритм[править | править исходный текст]

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

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

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

Функция ExpandKey:

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


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

bcrypt(cost, salt, key, input)
    state \gets EksBlowfishSetup(cost, salt, key)
    ctext \gets input
    repeat (64)
        ctext \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]

См. также[править | править исходный текст]

Ссылки[править | править исходный текст]

Примечания[править | править исходный текст]

  1. Provos, Niels; Mazières, David (1999). «A Future-Adaptable Password Scheme». Proceedings of 1999 USENIX Annual Technical Conference: 81–92.
  2. www.openbsd.org/papers/bcrypt-paper.pdf
  3. http://www.unlimitednovelty.com/2012/03/dont-use-bcrypt.html "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 "Unlike bcrypt, PBKDF2 has been the subject of intense research and still remains the best conservative choice."