Просмотр кода страницы Bcrypt

{{lowercase|title=bcrypt}}
{{Карточка хеш-функции
| название     = bcrypt
| изображение  = 
| разработчик  = 
| разработчики = [[Нильс Провос]] и David Mazières
| создан       = 
| впервые опубликован = 1999
| опубликован   = 
| отменён       = 
| преемник      = 
| стандарты     = 
| размер хэша   = 
| число раундов = 2<sup>n</sup>
| тип           = 
}}
'''bcrypt''' — адаптивная криптографическая [[хеш-функция]] [[Функция формирования ключа|формирования ключа]], используемая для защищенного хранения [[Пароль|паролей]]. Разработчики: [[:en:Niels_Provos|Нильс Провос]] и David Mazières. Функция основана на шифре [[Blowfish]], впервые представлена на [[USENIX]] в 1999 году<ref>{{статья |ссылка=http://www.usenix.org/events/usenix99/provos/provos_html/node1.html |заглавие=A Future-Adaptable Password Scheme |издание=Proceedings of 1999 USENIX Annual Technical Conference |страницы=81—92 |язык=und |автор=Provos, Niels; Mazières, David |год=1999 |archivedate=2012-02-04 |archiveurl=https://web.archive.org/web/20120204044914/http://www.usenix.org/events/usenix99/provos/provos_html/node1.html }}</ref>. Для защиты от атак с помощью [[Радужная таблица|радужных таблиц]] bcrypt использует соль (salt); кроме того, функция является адаптивной, время её работы легко настраивается и её можно замедлить, чтобы усложнить атаку перебором.

Шифр Blowfish отличается от многих алгоритмов вычислительно сложной фазой {{не переведено|усиление ключа|подготовки ключей шифрования|en|Key stretching}}.

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

Изначально реализовано в функции [[crypt]] в [[OpenBSD]]. Существуют реализации для Java, Python, Nim, C#, Ruby, Perl, PHP 5.3, Node.js, Go<ref>{{Cite web|url=https://godoc.org/golang.org/x/crypto/bcrypt|title=Package bcrypt|publisher=godoc.org|lang=en|accessdate=2020-01-10|archive-date=2020-05-29|archive-url=https://web.archive.org/web/20200529003742/https://godoc.org/golang.org/x/crypto/bcrypt|deadlink=no}}</ref> и некоторых других.

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

 EksBlowfishSetup(''cost'', ''salt'', ''key'')
     ''state'' <math>\gets</math> InitState()
     ''state'' <math>\gets</math> ExpandKey(''state'', ''salt'', ''key'')
     '''repeat''' (2<sup>''cost''</sup>)
         ''state'' <math>\gets</math> ExpandKey(state, 0, key)
         ''state'' <math>\gets</math> ExpandKey(state, 0, salt)
     '''return''' ''state''

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

Функция ExpandKey:

 ExpandKey(''state'', ''salt'', ''key'')
     for(''n'' = 1..18)
         P<sub>n</sub> <math>\gets</math> ''key''[32(n-1)..32n-1] <math>\oplus</math> P<sub>n</sub> //treat the key as cyclic
     ''ctext'' <math>\gets</math> Encrypt(''salt''[0..63])
     P<sub>1</sub> <math>\gets</math> ''ctext''[0..31]
     P<sub>2</sub> <math>\gets</math> ''ctext''[32..63]
     for(''n'' = 2..9)
         ''ctext'' <math>\gets</math> Encrypt(''ctext'' <math>\oplus</math> ''salt''[64(n-1)..64n-1]) //encrypt using the current key schedule and treat the salt as cyclic
         P<sub>2n-1)</sub> <math>\gets</math> ''ctext''[0..31]
         P<sub>2n</sub> <math>\gets</math> ''ctext''[32..63]
     for(''i'' = 1..4)
         for(''n'' = 0..127)
             ''ctext'' <math>\gets</math> Encrypt(''ctext'' <math>\oplus</math> ''salt''[64(n-1)..64n-1]) //as above
             S<sub>i</sub>[2n] <math>\gets</math> ''ctext''[0..31]
             S<sub>i</sub>[2n+1] <math>\gets</math> ''ctext''[32..63]
     '''return''' ''state''

<!-- -->

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

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

В различных ОС (linux, OpenBSD), использующих алгоритм bcrypt в стандартной функции crypt (3), в качестве input подается константа «OrpheanBeholderScryDoubt»<ref>{{Cite web |url=http://www.openbsd.org/papers/bcrypt-paper.pdf |title=Архивированная копия |access-date=2015-08-19 |archive-date=2018-06-15 |archive-url=https://web.archive.org/web/20180615201340/http://www.openbsd.org/papers/bcrypt-paper.pdf |deadlink=no }}</ref>.

== Недостатки ==
bcrypt был разработан в 1999 году и был защищен от эффективного перебора на аппаратных средствах того времени. В настоящее время получили широкое распространение ПЛИС, в которых bcrypt реализуется эффективнее. В 2009 был создан алгоритм [[scrypt]], требующий для своей работы значительный объем памяти (со случайным доступом), объем памяти настраивается<ref>http://www.unlimitednovelty.com/2012/03/dont-use-bcrypt.html {{Wayback|url=http://www.unlimitednovelty.com/2012/03/dont-use-bcrypt.html |date=20180414010849 }} «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.»</ref>.

В сравнении с [[PBKDF2]], алгоритм расширения ключа в bcrypt практически не исследовался криптографами<ref>http://www.unlimitednovelty.com/2012/03/dont-use-bcrypt.html {{Wayback|url=http://www.unlimitednovelty.com/2012/03/dont-use-bcrypt.html |date=20180414010849 }} «Unlike bcrypt, PBKDF2 has been the subject of intense research and still remains the best conservative choice.»</ref>.

== См. также ==
* [[Crypt (Unix)]]
* [[Crypt (C)]] 
* [[PBKDF2]]
* [[scrypt]]

== Ссылки ==
* [http://www.mindrot.org/projects/jBCrypt/ jBCrypt — реализация bcrypt на Java]
* [https://pypi.python.org/pypi/bcrypt/2.0.0 py-bcrypt — реализация bcrypt на Python]
* [http://bcrypt.codeplex.com/ BCrypt.Net- реализация bcrypt на C#]
* [https://web.archive.org/web/20121011021330/http://www.jayfuerstenberg.com/blog/bcrypt-in-objective-c JFBCrypt — реализация bcrypt на Objective C]
* [https://web.archive.org/web/20170304040233/http://bcrypt-ruby.rubyforge.org/ bcrypt-ruby — реализация bcrypt на Ruby]
* [https://metacpan.org/pod/Crypt::Eksblowfish::Bcrypt Crypt::Eksblowfish::Bcrypt — реализация bcrypt на Perl]
* [https://github.com/ncb000gt/node.bcrypt.js/ bcrypt.js — реализация bcrypt на JavaScript]
* [https://github.com/fpirsch/twin-bcrypt twin-bcrypt — реализация bcrypt на JavaScript / asm.js]
* [http://godoc.org/code.google.com/p/go.crypto/bcrypt bcrypt.go — реализация bcrypt на Go] {{Wayback|url=http://godoc.org/code.google.com/p/go.crypto/bcrypt |date=20141004084903 }}
* [https://tutanota.com/ tutanota.com — пример использования bcrypt в сервисе end-to-end шифрованной почты]  

== Примечания ==
{{примечания}}

{{Хеш-алгоритмы}}

[[Категория:Криптографические хеш-функции]]