Cryptography - Personal Notes #1
Monday, August 27, 2012 | Author: Deep Flash
These are my personal notes for Cryptography and any other subject related to Cryptography. They are for my reference however the fact that they are available here might help someone else who stumbles across this blog.

These notes are short lines, summarized to understand complex subjects. Mathematical Representations are used where required.

The content of this blog evolves with time. More information shall be added.

bcrypt hashing algorithm:

Designed by Niels Provos and David. Paper presented in Usenix in 1999.

Based on Blowfish 64 bit symmetric key block cipher.

It uses a similar key schedule algorithm as used in Blowfish, however slightly modified. Often referred to as an Expensive Key Schedule. This is the step that makes bcrypt hashing algorithm computationally intensive.

Similar to other block cipher based hashing algorithms like DEScrypt, it shares a few common properties:

Makes use of a 16 round Fiestel Network.
S Boxes (consists of 4 S Boxes) and P Array (Consisting of 18 Subkeys)
A key schedule which is used to derive the S boxes and P arrays from the encrypted key.

The differences are as follows:

Unlike DES, the S Boxes in bcrypt are not fixed. They depend on the encrypted key and the salt. Even though the 4 S Boxes are initialized with the hexadecimal digits of the number Pi, they are later modified using the bits of the salt.

Each S box consists of 256 32 bit words (dwords).

Size of 1 S Box = 256 * 32 bits = 8192 bits = 1024 bytes = 1 Kb
There are a total of 4 S Boxes.
Total Size = 4 Kb

During the expensive key schedule setup, the contents of these S boxes are modified constantly using the 128 bit salt (64 bits or 2 S box entries at a time).

This makes the bcrypt hashing algorithm memory intensive and hence it cannot be accelerated on GPU easily.

Similar to S Boxes, the contents of the P-Array are also modified using both the salt and the variable length key.

P Array consists of 18 sub keys.
Size of 1 sub key = 32 bits
Size of the P Array = 72 bytes

Number of Blowfish Encryptions per bcrypt hash:

There are 3 different types of invocations of the ExpandKey function in the Eksblowfish function:

1. ExpandKey(state, salt, key) - It uses the current key schedule along with the 128 bit salt and the variable length key to modify the contents of S boxes and P Arrays.

There is only one invocation of the ExpandKey function with the above arguments.

2. ExpandKey(state, 0, key) - Here the second argument of the function is 128 0 bits. Using the current state of the key schedule, it modifies the contents of the S Boxes and P Arrays. Since, the salt consists of 0 bits here, as a result of that, the key schedule setup is similar to that in Blowfish Block Cipher.

Reason being, during the key schedule setup, the XOR operations which are performed with the bits of the salt will now have no effect since, an XOR operation between a number and 0 gives back the number itself.

3. ExpandKey(state, 0, salt) - This is similar to the above function call, except for the fact that here the 16 byte salt is used as the encrypted key. The key schedule in this case is also the same as Blowfish Block Cipher.

Based on the work factor mentioned in the bcrypt hashing algorithm, the total number of iterations are decided.

Lets assume a work factor of 10 (which is realistic as per modern day systems).

This means, there are a total of 2^10 (1024) invocations of the ExpandKey(state, 0, key) and the ExpandKey(state, 0, salt) functions.

Now, let us calculate the total number of blowfish encryptions per bcrypt hash.

For one invocation of ExpandKey(state, salt, key) we have:

Each time, 64 bits of the salt are blowfish encrypted, they are used to replace the contents of 2 Sub Keys.

1 Blowfish Encryption = 2 Sub Keys replaced

Since there are a total of 18 sub keys, we require 9 Blowfish encryptions of 64 bits of the salt to replace all the Sub Key entries in the P Array.

At this point, we have,

9 Blowfish Encryptions = Replace all the entries in the P Array

Each time, 64 bits of the salt are blowfish encrypted, we can replace, 2 Sbox Entries

1 Blowfish Encryption = Replace 2 Box Entries

Since we have a total of 256 S box entries or 128 2 S box entries, we have,

128 Blowfish Encryptions = Replace 128 2 Sbox Entries = Replace all the entries of 1 S box.

Since we have a total of 4 S boxes, we have,

128*4 = 512 Blowfish encryptions to replace all the entries in all the sboxes.

Putting it together, we have,

9+512 blowfish encryptions to replace all the entries in the S boxes and the P Array in key schedule.

Now, we have two more ExpandKey functions, each called 1024 times (assuming a work factor of 10),

Each of these ExpandKey functions also require (9+512) blowfish encryptions to replace the contents of all the S boxes and P Arrays:

At this point, we have,

9+512 + 1024 * (512+9) * 2 blowfish encryptions to replace all the entries of the S boxes and P Arrays in bcrypt.

bcrypt hashing algorithm also encrypts a 192 bit constant value 64 times.

This 192 bit constant value = OrpheanBeholderScryDoubt

Since, Blowfish is a 64 bit block cipher, this 192 bit value will be blowfish encrypted in 3 iterations (in each iteration 64 bits of the constant value are encrypted).

Also, there are a total of 64 iterations where this 192 bit constant value is encrypted.

So, a total of:

64*3 blowfish encryptions to encrypt the 192 bit constant value in bcrypt.

Once again, putting it altogether, we have,

9+512 + 1024 * (512+9) * 2 + 64 * 3 = 521 + 1067008 + 192 = 1067721

Or, if we consider a work factor of 5, then it is:

9+512 + 32 * (512+9) * 2 + 64 *3 = 521 + 33344 + 192 = 34057

This value is in place with the calculation done by Solar Designer.