bcrypt

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
      S1..S4:   array of UInt32                array of four SBoxes; each SBox is 256 UInt32 (i.e. 1024 KB)

   //Initialize P (Subkeys), and S (Substitution boxes) with the hex digits of pi 
   P, S ${\displaystyle \gets }$ InitialState() 
 
   //Permutate P and S based on the password and salt     
   P, S ${\displaystyle \gets }$ ExpandKey(P, S, salt, password)

   //This is the "Expensive" part of the "Expensive Key Setup".
   //Otherwise the key setup is identical to Blowfish.
   repeat (2cost)
      P, S ${\displaystyle \gets }$ ExpandKey(P, S, 0, password)
      P, S ${\displaystyle \gets }$ 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 ${\displaystyle \pi }$ in hexadecimal.

The ExpandKey function does the following:

Function ExpandKey
   Input:
      password: array of Bytes (1..72 bytes)  UTF-8 encoded password
      salt:     Byte[16]                      random salt
      P:        array of UInt32               Array of 18 subkeys
      S1..S4:   UInt32[1024]                  Four 1 KB SBoxes
   Output: 
      P:        array of UInt32               Array of 18 per-round subkeys
      S1..S4:   UInt32[1024]                  Four 1 KB SBoxes       
 
   //Mix password into the P subkeys array
   for n ${\displaystyle \gets }$ 1 to 18 do
      Pn ${\displaystyle \gets }$ Pn xor password[32(n-1)..32n-1] //treat the password as cyclic
 
   //Treat the 128-bit salt as two 64-bit halves (the Blowfish block size).
   saltHalf[0] ${\displaystyle \gets }$ salt[0..63]  //Lower 64-bits of salt
   saltHalf[1] ${\displaystyle \gets }$ salt[64..127]  //Upper 64-bits of salt

   //Initialize an 8-byte (64-bit) buffer with all zeros.
   block ${\displaystyle \gets }$ 0

   //Mix internal state into P-boxes   
   for n ${\displaystyle \gets }$ 1 to 9 do
      //xor 64-bit block with a 64-bit salt half
      block ${\displaystyle \gets }$ block xor saltHalf[(n-1) mod 2] //each iteration alternating between saltHalf[0], and saltHalf[1]

      //encrypt block using current key schedule
      block ${\displaystyle \gets }$ Encrypt(P, S, block) 
      P2n ${\displaystyle \gets }$ block[0..31]      //lower 32-bits of block
      P2n+1 ${\displaystyle \gets }$ block[32..63]  //upper 32-bits block

   //Mix encrypted state into the internal S-boxes of state
   for i ${\displaystyle \gets }$ 1 to 4 do
      for n ${\displaystyle \gets }$ 0 to 127 do
         block ${\displaystyle \gets }$ Encrypt(state, block xor salt[64(n-1)..64n-1]) //as above
         Si[2n]   ${\displaystyle \gets }$ block[0..31]  //lower 32-bits
         Si[2n+1] ${\displaystyle \gets }$ block[32..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.

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 ${\displaystyle \gets }$ 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)

This also means that if a password were longer than 72-bytes UTF-8 encoded: the password would be truncated. Some characters can require 4-bytes when UTF-8 encoded. This means that in the worst case, this can limit a password to 18 characters:

𐑜𐑝𐑟𐑥𐑷𐑻𐑽𐑾𐑿𐑿𐑰𐑩𐑛𐑙𐑘𐑙𐑒𐑔 (18 characters, 72 bytes)

This limit of 72-byte passwords (18 subkeys * 4-bytes each) could have been addressed in a number of ways:

Solution 1 - Increase number of subkeys

You can increase the number of P subkeys used, and therefore increase the maximum password length available. Bruce Schneier, the original author of Blowfish, noted that people could play with adding more rounds,[20] which requires more subkeys, which for bcrypt would increase the maximum password length. A downside of this is that there is still a maximum password length - rather than no maximum length.

Solution 2 - Continue to xor mix the key bytes into the P subkeys array

Password mixing only continues as long as P₁...P₁₈. Once you've reached P₁₈ and you still have password bytes unprocessed, continue the xor process on P₁. A downside of this approach is that the computation time leaks the password length (side-channel information leak)

Solution 3 - Pre-hash password

The long password can be pre-hashed with another cryptographic hashing function. This function always outputs a digest of a fixed size. As long as the resulting digest is less than 72 bytes: it can be fed into bcrypt without being cut off. This is the approach taken by Dropbox[21] and others. For example, consider the password:

ਤੇਜ਼ ਭੂਰੇ ਲੂੰਬੜ ਨੇ ਆਲਸੀ ਕੁੱਤੇ ਉੱਤੇ ਛਾਲ ਮਾਰ ਦਿੱਤੀ (32 characters, 126 bytes)

If you hash that password using SHA-256, you get the 256-bit (32-byte) digest:

A7 B2 AA 86 CB 57 D3 08 EA 54 9F 34 E5 91 7E 8C 06 9B D0 0D 34 28 B1 CA 8D 71 B2 2E 84 DA C0 F8

Base64 encoding the digest gives a string that is consistently 44 characters:

p7KqhstX0wjqVJ805ZF+jAab0A00KLHKjXGyLoTawPg= (44 characters, 44 bytes)

and will always fit in the 72-byte bcrypt limit.

This is similar to an approach used by Pufferfish2, an cache-hard evolution of bcrypt, that uses HMAC_SHA-512 to convert the password into a fixed length 64-byte (512-bit) key.

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)

Which then should get radix-64 encoded to 32-characters:

hSCvnwM9s4wIX9JeLapehKK5YdLxKcmk (32-characters)

But the canonical OpenBSD implementation truncates password hash 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 a4 (23-bytes)

and the resulting base-64 encoded text, which normally would be:

hSCvnwM9s4wIX9JeLapehKK5YdLxKck=

has the trailing = removed, leaving a hash of:

hSCvnwM9s4wIX9JeLapehKK5YdLxKck

It is unclear why the canonical implementation deletes 8-bits from the resulting password hash.

The Base64 encoding used by the canonical OpenBSD implementation uses an encoding dictionary that is different from those available in nearly every language and platform. The encoding is compatible with crypt.[22] This means the encoding is not compatible with RFC 4648.