5
$\begingroup$

I'm planning on using this Javascript BCrypt implementation, but as you can see in the code, it uses a 4KB precalculated dataset for the P and S parameters needed for blowfish hashing. I've also tracked a similar dataset back to the original C BCrypt code.

Shouldn't blowfish hashing use a dynamically calculated dataset? How can this be secure? I'm going to do this client-side, so if an attacker reads the statically stored dataset, will it make it easier to find a collision for the BCrypt hashed value?

$\endgroup$
3
  • $\begingroup$ See code.google.com/p/javascript-bcrypt/source/browse/bCrypt.js to look at the source in question. $\endgroup$
    – mikeazo
    Mar 18, 2012 at 0:26
  • $\begingroup$ How do you believe that P and S should be computed? Are you thinking they should be dependent upon the salt and the password? $\endgroup$
    – mikeazo
    Mar 18, 2012 at 0:32
  • $\begingroup$ Welcome to Cryptography Stack Exchange. Your question was migrated here because of being not directly related to IT security, and being fully on-topic here. Please register your account here, too, to be able to comment and accept an answer. $\endgroup$ Mar 18, 2012 at 0:57

1 Answer 1

6
$\begingroup$

The BCrypt password hash algorithm is based on a modified version of the Blowfish encryption algorithm. The $P$ values are the round subkeys (used for XORing with the data), and the $S$ values are components for substitution boxes, both used in a Feistel network.

The initial values for $P$ and $S$ are the same as in the original Blowfish algorithm, and come from the hexadecimal digits of the circle constant $\pi$.

During the key schedule, these values $P$ and $S$ are used to create new (key-dependent) values, and then replaced by those. One critique point of Blowfish always was that it's key schedule is relatively slow (about as much as encrypting 4 KB of data - since we actually encrypt the zero string with the current $P$/$S$ values to create the new ones, and the size of $S$ and $P$ together is just 4 KB).

Bcrypt takes this slowness to a new level, using an expensive key schedule instead of the default blowfish key schedule, which takes a (configurable) much longer time.

This essentially (after a more complicated initial round which includes both salt and password) executes the normal key schedule $2^{\operatorname {cost}}$ times with each of salt and password as input, where $\operatorname{cost}$ is the cost parameter (the original bcrypt paper proposed $\operatorname{cost} = 6$ for normal user accounts, $\operatorname{cost} = 8$ for the administrator account). This is thus (time-)equivalent to encrypting $8·2^{\operatorname{cost}}+4$ KB of data with normal blowfish.

Then, a constant string (OrpheanBeholderScryDoubt) is (64 times) encrypted with the normal blowfish encryption using the thus created $P$ and $S$ boxes as state, producing an 192 bit string, which is then considered the bcrypt output (which is normally stored together with the salt and the cost parameter).

As we can see, the actually used values of $P$ and $S$ are very non-constant, depending strongly on the salt and password input. The initial values being fixed is not a vulnerability, but necessary to get identical output for identical input on each implementation.

Coming from the digits of $\pi$, they also quite likely don't contain a backdoor created by the designers of the algorithm (a nothing-up-my-sleeve-number).

Also, for a password hashing algorithm a collision attack is not the most important attack: An attacker finding two passwords which give (for a specific salt or pair of salts) the same hash, has about no advantage for finding the passwords to existing hashes (which also quite likely are using different salts).

$\endgroup$
2
  • $\begingroup$ Fantastic! ... do you know why the P and S values in the JS implementation is different than those in the C implementation? Could that be a vulnerability? $\endgroup$ Mar 19, 2012 at 7:19
  • $\begingroup$ @Jenko: Them being different would imply mainly an incompatibility (as the Blowfish encryption and crypt hash would not give the same results anymore), not an vulnerability (as long as the data still would be "random-like" enough). I didn't check all the values, but the one I checked have the same values. The C implementation uses uppercase and a trailing L (for the long datatype), the JavaScript one uses lowercase and no trailing L. $\endgroup$ Mar 19, 2012 at 8:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.