Blowfish Encryptions in Bcrypt hashing algorithm

Question

I am trying to understand the ExpandKey function used in the bcrypt hashing algorithm. As per the documentation of bcrypt hashing algorithm on USENIX here:

http://static.usenix.org/event/usenix99/provos/provos_html/node4.html

There is only one invocation of the ExpandKey function with the 128 bit salt value.

After this, the invocations of the ExpandKey function in the loop (2 ^ work factor), all have the second argument as 128 0 bits.

ExpandKey(state, 0, key)
ExpandKey(state, 0, salt)

Using these as inputs to how the ExpandKey function works, there will be repeated blowfish encryptions of 64 0 bits of salt which are used to replace the contents of P-Array and Sboxes.

If we take, ExpandKey(state, 0, key) as an example:

First all the subkeys in the P-Array are Xored with 32 bits of the encrypted key one by one (treating the key as cyclic).

Next, the first 64 bits of the salt (all 0 bits) are blowfish encrypted and the result is stored in P1 and P2 (first 2 32 bit sub keys).

The above result is Xored with the second half of the 128 bit salt (remaining 64 0 bits). Then blowfish encrypt it and store the result in P3 and P4.

This process goes on till the contents of all the subkeys are replaced followed by S-box entry replacement.

I wanted to know if my understanding is correct or not? We are effectively blowfish encrypting 64 0 bits every time in the loop.

What is the purpose of using the second argument of the ExpandKey function as all 0 bits instead of the actual 128 bit salt?

The key schedule would be more expensive, had they chosen the same 128 bit salt (as in the first invocation) for the remaining iterations. Or would this make bcrypt hashing algorithm computationally infeasible?

Thanks.

Answer 1

It is not really clear what you propose instead of the original algorithm - using ExpandKey(state, salt, key) instead of ExpandKey(state, 0, key)? What about the second call ExpandKey(state, 0, salt)?.

You are right, each ExpandKey(state, 0, xxx) contains one XOR-ing of xxx into the P-array, and then Blowfish-encrypting multiple 64-bit blocks of zeros – in CBC-mode, if I read the description right - thus actually we are not encrypting zero, but the ciphertext of the last block – but each block is encrypted with a different cipher state (as the result of each encryption replaces some of the P- or S-boxes).

Using salt as input instead of 0 would not be very more difficult, but (if I understand the argumentation on your linked page right) it might need some registers more to store the salt, and thus might slow down the execution on processors which are low on register count. Also, with zero salt, this is identical to the standard ExpandKey of Blowfish, so an existing (maybe optimized) implementation can be reused here, and all analysis of Blowfish can be applied, too.