The internals of bcrypt

Question

I'm attempting to get a better understanding of cryptography and have run into some questions about bcrypt.

1. Bcrypt relies on the blowfish cipher, which is a reversible method of encryption. But bcrypt is not reversible. How is that possible? Or am I mistaken? What does bcrypt do on top of blowfish to make it irreversible?

2. Why does bcrypt use blowfish instead of twofish or threefish?

Answer 1

You are correct, Blowfish is a reversible cipher if you know the key. Bcrypt has three parameters it uses to hash a password:

• Salt
• Password
• Cost

It derives a key using the salt, password and cost to encrypt the well known text "OrpheanBeholderScryDoubt" and not the password itself. So verification would be performing the encryption again on this string and see if the ciphertext is the same. The salt prevents scenarios where two users would use the same password to show up as the same ciphertext. So if you don't have the password you can't generate the ciphertext.

The reason why they are using Blowfish instead of twofish or threefish, is that it was published in 1999, whereas Twofish was from 1998 and threefish 2008. Bcrypt was seeking properties offered by Blowfish, namely slown key derivation so there was no reason to not use the already established blowfish (cryptographers are conservative and prefer to use proven solutions rather than cutting edge ones).

Answer 2

Lucas Kauffman is correct that the more recent algorithms were either too new to be proven, or not available at all, when bcrypt was designed. But this immediately brings up the question of whether a replacement for bcrypt could profitably make use of these more recent algorithms.

For password-hashing purposes, Blowfish has one great advantage over more recent algorithms: it is not key-agile.

Setting up Blowfish to use a new key is relatively expensive: you need to run the algorithm 521 times, replacing values in the P-boxes and then the S-boxes as you go. bcrypt uses a modified key schedule algorithm that is even more expensive, and whose expense can be configured to keep up with faster hardware over time. When computers become twice as fast, you don't have to replace the whole algorithm: you just run twice as many rounds.

Blowfish also requires maintaining 4 kiB of S-boxes, which represents a serious handicap to some kinds of password-cracking hardware that don't have a lot of memory. This too is an advantage over many more recent algorithms.

Finally, Blowfish was designed to run efficiently on general-purpose hardware. This means that using it on a server to validate logins is not significantly slower than using it on customized hardware to crack passwords. This is not an advantage over more recent algorithms, but it was a huge advantage over the existing DES-based hash that was widely used at the time.

Original paper.

Thomas Pornin's detailed answer from 2011.

Answer 3

Bcrypt relies on the blowfish cipher, which is a reversible method of encryption. But bcrypt is not reversible. How is that possible? Or am I mistaken? What does bcrypt do on top of blowfish to make it irreversible?

Using the psuedocode from the wikipedia article about bcrypt as an example:

bcrypt(cost, salt, input) state ← EksBlowfishSetup(cost, salt, input) ctext ← "OrpheanBeholderScryDoubt" //three 64-bit blocks repeat (64) ctext ← EncryptECB(state, ctext) //encrypt using standard Blowfish in ECB mode return Concatenate(cost, salt, ctext)

If you examine the main loop (the repeat 64 section), you can see that the hash input is being used as the key to the blowfish cipher in ecb mode, and is being used to encrypt the state. Then the ciphertext output of that encryption is used as the key to encrypt the state again, and again, until the repetitions are complete.

This means the output of bcrypt is essentially ciphertext output from the blowfish cipher. If you consider that the application of a strong cipher should effectively output pseudorandom data, this means the state is effectively being encrypted under a random key.

As long as the blowfish cipher is strong, ciphertext produced by it should be uninvertible without the key. Since the key was generated from the hash input, which is gone when the function call stack clears, the only way to regenerate the key is to know the hash input or find a collision.

Why does bcrypt use blowfish instead of twofish or threefish?

Only the designer could really answer this with absolute certainty, but I think that's a simple matter of when bcrypt was designed. Wikipedia says blowfish was published in 1993, and twofish in 1998, and bcrypt itself in 1999. While it appears twofish was available, it appears it was awfully new, which is considered an undesirable trait in cryptography. Threefish was first published in 2008, so was simply not available as a choice as it probably did not exist yet.