bcrypt is a
password-hashing function designed by
Niels Provos
Niels Provos is a German-American researcher in security engineering, malware, and cryptography. He received a PhD in computer science from the University of Michigan. From 2003 to 2018, he worked at Google as a Distinguished Engineer on security ...
and David Mazières, based on the
Blowfish
Tetraodontidae is a family of primarily marine and estuarine fish of the order Tetraodontiformes. The family includes many familiar species variously called pufferfish, puffers, balloonfish, blowfish, blowies, bubblefish, globefish, swellfis ...
cipher and presented at
USENIX in 1999.
Besides incorporating a
salt
Salt is a mineral composed primarily of sodium chloride (NaCl), a chemical compound belonging to the larger class of salts; salt in the form of a natural crystalline mineral is known as rock salt or halite. Salt is present in vast quantitie ...
to protect against
rainbow table attacks, bcrypt is an adaptive function: over time, the iteration count can be increased to make it slower, so it remains resistant to
brute-force search attacks even with increasing computation power.
The bcrypt function is the default password
hash algorithm
A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called ''hash values'', ''hash codes'', ''digests'', or simply ''hashes''. The values are usually ...
for
OpenBSD
OpenBSD is a security-focused, free and open-source, Unix-like operating system based on the Berkeley Software Distribution (BSD). Theo de Raadt created OpenBSD in 1995 by forking NetBSD 1.0. According to the website, the OpenBSD project em ...
and was the default for some
Linux distribution
A Linux distribution (often abbreviated as distro) is an operating system made from a software collection that includes the Linux kernel and, often, a package management system. Linux users usually obtain their operating system by downloading one ...
s such as
SUSE Linux.
There are implementations of bcrypt in
C,
C++
C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
,
C#,
Embarcadero Delphi
Delphi is a general-purpose programming language and a software product that uses the Delphi dialect of the Object Pascal programming language and provides an integrated development environment (IDE) for rapid application development of desktop, ...
,
Elixir
ELIXIR (the European life-sciences Infrastructure for biological Information) is an initiative that will allow life science laboratories across Europe to share and store their research data as part of an organised network. Its goal is to bring t ...
,
Go,
Java
Java (; id, Jawa, ; jv, ꦗꦮ; su, ) is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea to the north. With a population of 151.6 million people, Java is the world's List ...
,
JavaScript
JavaScript (), often abbreviated as JS, is a programming language that is one of the core technologies of the World Wide Web, alongside HTML and CSS. As of 2022, 98% of Website, websites use JavaScript on the Client (computing), client side ...
,
Perl
Perl is a family of two high-level, general-purpose, interpreted, dynamic programming languages. "Perl" refers to Perl 5, but from 2000 to 2019 it also referred to its redesigned "sister language", Perl 6, before the latter's name was offici ...
,
PHP
PHP is a general-purpose scripting language geared toward web development. It was originally created by Danish-Canadian programmer Rasmus Lerdorf in 1993 and released in 1995. The PHP reference implementation is now produced by The PHP Group. ...
,
Python
Python may refer to:
Snakes
* Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia
** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia
* Python (mythology), a mythical serpent
Computing
* Python (pro ...
,
Ruby
A ruby is a pinkish red to blood-red colored gemstone, a variety of the mineral corundum ( aluminium oxide). Ruby is one of the most popular traditional jewelry gems and is very durable. Other varieties of gem-quality corundum are called sa ...
, and other languages.
Background
Blowfish is notable among block ciphers for its expensive key setup phase. It starts off with subkeys in a standard state, then uses this state to perform a block encryption using part of the key, and uses the result of that encryption (which is more accurate at hashing) to replace some of the subkeys. Then it uses this modified state to encrypt another part of the key, and uses the result to replace more of the subkeys. It proceeds in this fashion, using a progressively modified state to hash the key and replace bits of state, until all subkeys have been set.
Provos and Mazières took advantage of this, and took it further. They developed a new key setup algorithm for Blowfish, dubbing the resulting cipher "Eksblowfish" ("expensive key schedule Blowfish"). The key setup begins with a modified form of the standard Blowfish key setup, in which both the salt and password are used to set all subkeys. There are then a number of rounds in which the standard Blowfish keying algorithm is applied, using alternatively the salt and the password as the key, each round starting with the subkey state from the previous round. In theory, this is no stronger than the standard Blowfish key schedule, but the number of rekeying rounds is configurable; this process can therefore be made arbitrarily slow, which helps deter brute-force attacks upon the hash or salt.
Description
The input to the bcrypt function is the password string (up to 72 bytes), a numeric cost, and a 16-byte (128-bit) salt value. The salt is typically a random value. The bcrypt function uses these inputs to compute a 24-byte (192-bit) hash. The final output of the bcrypt function is a string of the form:
$2<a/b/x/y>$
ost 2 character salt31 character hash]
For example, with input password
abc123xyz
, cost
12
, and a random salt, the output of bcrypt is the string
$2a$12$R9h/cIPz0gi.URNNX3kh2OPST9/PgBkqquzi.Ss7KIUgO2t0jWMUW
\__/\/ \____________________/\_____________________________/
Alg Cost Salt Hash
Where:
*
$2a$
: The hash algorithm identifier (bcrypt)
*
12
: Input cost (2
12 i.e. 4096 rounds)
*
R9h/cIPz0gi.URNNX3kh2O
: A base-64 encoding of the input salt
*
PST9/PgBkqquzi.Ss7KIUgO2t0jWMUW
: A base-64 encoding of the first 23 bytes of the computed 24 byte hash
The base-64 encoding in bcrypt uses the table
./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789
,
which is different than
Base64
In computer programming, Base64 is a group of binary-to-text encoding schemes that represent binary data (more specifically, a sequence of 8-bit bytes) in sequences of 24 bits that can be represented by four 6-bit Base64 digits.
Common to all bina ...
encoding.
Versioning history
$2$ (1999)
The original bcrypt specification defined a prefix of
$2$
. This follows the Modular
Crypt
A crypt (from Latin ''crypta'' "vault") is a stone chamber beneath the floor of a church or other building. It typically contains coffins, sarcophagi, or religious relics.
Originally, crypts were typically found below the main apse of a chur ...
Format format used when storing passwords in the OpenBSD password file:
*
$1$
: MD5-based crypt ('md5crypt')
*
$2$
: Blowfish-based crypt ('bcrypt')
*
$sha1$
: SHA-1-based crypt ('sha1crypt')
*
$5$
: SHA-256-based crypt ('sha256crypt')
*
$6$
: SHA-512-based crypt ('sha512crypt')
$2a$
The original specification did not define how to handle non-ASCII character, nor how to handle a null terminator. The specification was revised to specify that when hashing strings:
* the string must be UTF-8 encoded
* the null terminator must be included
With this change, the version was changed to
$2a$
$2x$, $2y$ (June 2011)
In June 2011, a bug was discovered in crypt_blowfish, a PHP implementation of bcrypt. It was mis-handling characters with the 8th bit set. They suggested that system administrators update their existing password database, replacing
$2a$
with
$2x$
, to indicate that those hashes are bad (and need to use the old broken algorithm). They also suggested the idea of having crypt_blowfish emit
$2y$
for hashes generated by the fixed algorithm.
Nobody else, including canonical OpenBSD, adopted the idea of 2x/2y. This version marker change was limited to crypt_blowfish.
$2b$ (February 2014)
A bug was discovered in the OpenBSD implementation of bcrypt. It was using an unsigned 8-bit value to hold the length of the password.
For passwords longer than 255 bytes, instead of being truncated at 72 bytes the password would be truncated at the lesser of 72 or the length
modulo 256. For example, a 260 byte password would be truncated at 4 bytes rather than truncated at 72 bytes.
bcrypt was created for OpenBSD. When they had a bug in their library, they decided to bump the version number.
Algorithm
The bcrypt algorithm is the result of encrypting the text ''"OrpheanBeholderScryDoubt"'' 64 times using
Blowfish
Tetraodontidae is a family of primarily marine and estuarine fish of the order Tetraodontiformes. The family includes many familiar species variously called pufferfish, puffers, balloonfish, blowfish, blowies, bubblefish, globefish, swellfis ...
. In bcrypt the usual Blowfish key setup function is replaced with an ''expensive'' key setup (EksBlowfishSetup) function:
Function bcrypt
Input:
cost: Number (4..31)
log2(Iterations). e.g. 12 > 212 = 4,096 iterations
salt: array of Bytes (16 bytes)
random salt
password: array of Bytes (1..72 bytes)
UTF-8 encoded password
Output:
hash: array of Bytes (24 bytes)
//Initialize Blowfish state with expensive key setup algorithm
//P: array of 18 subkeys (UInt32 8
//S: Four substitution boxes (S-boxes), S0...S3. Each S-box is 1,024 bytes (UInt32 56
''P'', ''S'' ← EksBlowfishSetup(''cost'', ''salt'', ''password'')
//Repeatedly encrypt the text "OrpheanBeholderScryDoubt" 64 times
''ctext'' ←
''"OrpheanBeholderScryDoubt"'' //24 bytes > three 64-bit blocks
repeat (64)
''ctext'' ← EncryptECB(''P'', ''S'', ''ctext'')
//encrypt using standard Blowfish in ECB mode
//24-byte ''ctext'' is resulting password hash
return Concatenate(''cost'', ''salt'', ''ctext'')
Expensive key setup
The bcrypt algorithm depends heavily on its "Eksblowfish" key setup algorithm, which runs as follows:
Function EksBlowfishSetup
Input:
password: array of Bytes (1..72 bytes)
UTF-8 encoded password
salt: array of Bytes (16 bytes)
random salt
cost: Number (4..31)
log2(Iterations). e.g. 12 > 212 = 4,096 iterations
Output:
P: array of UInt32
array of 18 per-round subkeys
S
1..S
4: array of UInt32
array of four SBoxes; each SBox is 256 UInt32 (''i.e.'' each SBox is 1 KiB)
//Initialize P (Subkeys), and S (Substitution boxes) with the hex digits of pi
''P'', ''S'' ← InitialState()
//Permute P and S based on the password and salt
''P'', ''S'' ← ExpandKey(''P'', ''S'', ''salt'', ''password'')
//This is the "Expensive" part of the "Expensive Key Setup".
//Otherwise the key setup is identical to Blowfish.
repeat (2
''cost'')
''P'', ''S'' ← ExpandKey(''P'', ''S'', 0, password)
''P'', ''S'' ← ExpandKey(''P'', ''S'', 0, salt)
return ''P'', ''S''
InitialState works as in the original Blowfish algorithm, populating the P-array and S-box entries with the fractional part of
in hexadecimal.
Expand key
The ExpandKey function does the following:
Function ExpandKey
Input:
password: array of Bytes (1..72 bytes)
UTF-8 encoded password
salt: Byte
6 random salt
P: array of UInt32
Array of 18 subkeys
S
1..S
4: UInt32
024
4 (four) is a number, numeral (linguistics), numeral and numerical digit, digit. It is the natural number following 3 and preceding 5. It is the smallest semiprime and composite number, and is tetraphobia, considered unlucky in many East Asian c ...
Four 1 KB SBoxes
Output:
P: array of UInt32
Array of 18 per-round subkeys
S
1..S
4: UInt32
024
4 (four) is a number, numeral (linguistics), numeral and numerical digit, digit. It is the natural number following 3 and preceding 5. It is the smallest semiprime and composite number, and is tetraphobia, considered unlucky in many East Asian c ...
Four 1 KB SBoxes
//Mix password into the P subkeys array
for ''n'' ← 1
to 18
do
P
n ← P
n xor ''password''
2(n-1)..32n-1//treat the password as cyclic
//Treat the 128-bit salt as two 64-bit halves (the Blowfish block size).
saltHalf
← ''salt''
..63 //Lower 64-bits of salt
saltHalf
← ''salt''
4..127 //Upper 64-bits of salt
//Initialize an 8-byte (64-bit) buffer with all zeros.
block ← 0
//Mix internal state into P-boxes
for ''n'' ← 1
to 9
do
//xor 64-bit ''block'' with a 64-bit salt half
''block'' ← ''block'' xor ''saltHalf''
n-1) mod 2//each iteration alternating between ''saltHalf'' and ''saltHalf'' /span>
//encrypt block using current key schedule
''block'' ← Encrypt(''P'', S, ''block'')
P2n ← ''block'' ..31 //lower 32-bits of ''block''
P2n+1 ← ''block'' 2..63 //upper 32-bits ''block''
//Mix encrypted state into the internal S-boxes of ''state''
for ''i'' ← 1 to 4 do
for ''n'' ← 0 to 127 do
''block'' ← Encrypt(''state'', ''block'' xor ''salt'' 4(n-1)..64n-1 //as above
Si n ← ''block'' ..31 //lower 32-bits
Si n+1← ''block'' 2..63 //upper 32-bits
return ''state''
Hence, ExpandKey(''state'', 0, ''key'')
is the same as regular Blowfish key schedule since all XORs with the all-zero salt value are ineffectual. ExpandKey(''state'', 0, ''salt'')
is similar, but uses the salt as a 128-bit key.
User input
Many implementations of bcrypt truncate the password to the first 72 bytes, following the OpenBSD implementation.
The mathematical algorithm itself requires initialization with 18 32-bit subkeys (equivalent to 72 octets/bytes). The original specification of bcrypt does not mandate any one particular method for mapping text-based passwords from userland into numeric values for the algorithm. One brief comment in the text mentions, but does not mandate, the possibility of simply using the ASCII encoded value of a character string: "Finally, the key argument is a secret encryption key, which can be a user-chosen password of up to 56 bytes (including a terminating zero byte when the key is an ASCII string)."[
Note that the quote above mentions passwords "up to 56 bytes" even though the algorithm itself makes use of a 72 byte initial value. Although Provos and Mazières do not state the reason for the shorter restriction, they may have been motivated by the following statement from ]Bruce Schneier
Bruce Schneier (; born January 15, 1963) is an American cryptographer, computer security professional, privacy specialist, and writer. Schneier is a Lecturer in Public Policy at the Harvard Kennedy School and a Fellow at the Berkman Klein Cente ...
's original specification of Blowfish, "The 448 itlimit on the key size ensures that the every bit of every subkey depends on every bit of the key."
Implementations have varied in their approach of converting passwords into initial numeric values, including sometimes reducing the strength of passwords containing non-ASCII characters.
Comparison to other password hashing algorithms
It is important to note that bcrypt is not a key derivation function (KDF). For example, bcrypt cannot be used to derive a 512-bit key from a password. At the same time, algorithms like pbkdf2
In cryptography, PBKDF1 and PBKDF2 (Password-Based Key Derivation Function 1 and 2) are key derivation functions with a sliding computational cost, used to reduce vulnerabilities of brute-force attacks.
PBKDF2 is part of RSA Laboratories' Publ ...
, scrypt
In cryptography, scrypt (pronounced "ess crypt") is a password-based key derivation function created by Colin Percival in March 2009, originally for the Tarsnap online backup service. The algorithm was specifically designed to make it costly ...
, and argon2
Argon2 is a key derivation function that was selected as the winner of the 2015 Password Hashing Competition. It was designed by Alex Biryukov, Daniel Dinu, and Dmitry Khovratovich from the University of Luxembourg. The reference implementation o ...
''are'' password-based key derivation functions - where the output is then used for the purpose of password hashing rather than just key derivation.
Password hashing generally needs to complete < 1000 ms. In this scenario, bcrypt is stronger than pbkdf2, scrypt, and argon2.
* PBKDF2: pbkdf2 is weaker than bcrypt. The commonly used SHA2 hashing algorithm is not memory-hard. SHA2 is designed to be extremely lightweight so it can run on lightweight devices (e.g. smart cards). This means PBKDF2 is very weak for password storage, as commodity SHA-2 hashing hardware that can perform trillions of hashes per second is easily procured
* scrypt: scrypt is weaker than bcrypt for memory requirements less than 4 MB. scrypt requires approximately 1000 times the memory of bcrypt to achieve a comparable level of defense against GPU based attacks (for password storage).
* argon2: Argon2 is weaker than bcrypt for run times less than 1 second (i.e. for password authentication). Argon2 does not match or surpass bcrypt's strength until >= ~1000ms runtimes (which is unsuitable for password hashing, but is perfectly acceptable for key-derivation).
* pufferfish2 is an evolution of bcrypt that uses a tunable memory footprint (like scrypt and argon2), rather than the fixed 4 KB memory footprint of bcrypt. Similar to scrypt or argon2, pufferfish2 gains its difficulty by using more memory. Unlike scrypt and argon2, pufferfish2 only operates in a CPU core's L2 cache. While scrypt and argon2 gain their memory hardness by randomly accessing lots of RAM, pufferfish2 limits itself to just the dedicated L2 cache available to a CPU core. This makes it even harder to implement in custom hardware than scrypt and argon2. The ideal memory footprint of pufferfish2 is the size of the cache available to a core (e.g. 1.25 MB for Intel Alder Lake) This makes pufferfish2 much more resistant to GPU or ASIC.
Criticisms
Maximum password length
bcrypt has a maximum password length of 72 bytes. This maximum comes from the first operation of the ExpandKey function that xor's
the 18 4-byte subkeys (P) with the password:
P1..P18 ← P1..P18 xor passwordBytes
The password (which is UTF-8 encoded), is repeated until it is 72-bytes long. For example, a password of:
:correct horse battery staple␀
''(29 bytes)''
Is repeated until it matches the 72-bytes of the 18 P per-round subkeys:
:correct horse battery staple␀correct horse battery staple␀correct horse
''(72 bytes)''
In the worst case a password is limited to 18 characters, when every character requires 4 bytes of UTF-8 encoding. For example:
:𐑜𐑝𐑟𐑥𐑷𐑻𐑽𐑾𐑿𐑿𐑰𐑩𐑛𐑙𐑘𐑙𐑒𐑔
''(18 characters, 72 bytes)''
Password hash truncation
The bcrypt algorithm involves repeatedly encrypting the 24-byte text:
:OrpheanBeholderScryDoubt
''(24-bytes)''
This generates 24 bytes of ciphertext, e.g.:
:85 20 af 9f 03 3d b3 8c 08 5f d2 5e 2d aa 5e 84 a2 b9 61 d2 f1 29 c9 a4
''(24-bytes)''
The canonical OpenBSD implementation truncates this to 23 bytes:
:85 20 af 9f 03 3d b3 8c 08 5f d2 5e 2d aa 5e 84 a2 b9 61 d2 f1 29 c9
''(23-bytes)''
It is unclear why the canonical implementation deletes 8-bits from the resulting password hash.
These 23 bytes become 31 characters when radix-64 encoded:
:fQAtluK7q2uGV7HcJYncfII3WbJvIai
''(31-characters)''
base64 encoding alphabet
The encoding used by the canonical OpenBSD implementation uses the same Base64
In computer programming, Base64 is a group of binary-to-text encoding schemes that represent binary data (more specifically, a sequence of 8-bit bytes) in sequences of 24 bits that can be represented by four 6-bit Base64 digits.
Common to all bina ...
alphabet as crypt
A crypt (from Latin ''crypta'' "vault") is a stone chamber beneath the floor of a church or other building. It typically contains coffins, sarcophagi, or religious relics.
Originally, crypts were typically found below the main apse of a chur ...
, which is ./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789
. This means the encoding is not compatible with the more common RFC 4648.
See also
* Argon2
Argon2 is a key derivation function that was selected as the winner of the 2015 Password Hashing Competition. It was designed by Alex Biryukov, Daniel Dinu, and Dmitry Khovratovich from the University of Luxembourg. The reference implementation o ...
- winner of the Password Hashing Competition
The Password Hashing Competition was an open competition announced in 2013 to select one or more password hash functions that can be recognized as a recommended standard. It was modeled after the successful Advanced Encryption Standard process and ...
in 2015
* bcrypt - blowfish-based cross-platform file encryption utility developed in 2002
* crypt
A crypt (from Latin ''crypta'' "vault") is a stone chamber beneath the floor of a church or other building. It typically contains coffins, sarcophagi, or religious relics.
Originally, crypts were typically found below the main apse of a chur ...
- Unix C library function
* crypt
A crypt (from Latin ''crypta'' "vault") is a stone chamber beneath the floor of a church or other building. It typically contains coffins, sarcophagi, or religious relics.
Originally, crypts were typically found below the main apse of a chur ...
- Unix utility
* ccrypt - utility
* Key stretching
In cryptography, key stretching techniques are used to make a possibly weak key, typically a password or passphrase, more secure against a brute-force attack by increasing the resources (time and possibly space) it takes to test each possible ke ...
* mcrypt
mcrypt is a replacement for the popular Unix crypt command. crypt was a file encryption tool that used an algorithm very close to the World War II Enigma cipher. Mcrypt provides the same functionality but uses several modern algorithms such as ...
- utility
* PBKDF2
In cryptography, PBKDF1 and PBKDF2 (Password-Based Key Derivation Function 1 and 2) are key derivation functions with a sliding computational cost, used to reduce vulnerabilities of brute-force attacks.
PBKDF2 is part of RSA Laboratories' Publ ...
- a widely used standard Password-Based Key Derivation Function 2
* scrypt
In cryptography, scrypt (pronounced "ess crypt") is a password-based key derivation function created by Colin Percival in March 2009, originally for the Tarsnap online backup service. The algorithm was specifically designed to make it costly ...
- password-based key derivation function (and also a utility)
References
External links
crypt_blowfish, the implementation maintained by Openwall
{{Cryptography navbox , hash
Cryptographic software