Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

migrated from security.stackexchange.com Mar 17 '12 at 23:07

This question came from our site for Information security professionals.

    
See code.google.com/p/javascript-bcrypt/source/browse/bCrypt.js to look at the source in question. –  mikeazo Mar 18 '12 at 0:26
    
How do you believe that P and S should be computed? Are you thinking they should be dependent upon the salt and the password? –  mikeazo Mar 18 '12 at 0:32
    
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. –  Paŭlo Ebermann Mar 18 '12 at 0:57
add comment

1 Answer 1

up vote 5 down vote accepted

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).

share|improve this answer
    
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? –  Jarvis Mar 19 '12 at 7:19
    
@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. –  Paŭlo Ebermann Mar 19 '12 at 8:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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