The bcrypt Algorithm

The bcrypt Algorithm

Introduction

Most hash functions are designed to be fast. For storing passwords, that is a flaw. An attacker who steals a database wants to try billions of guesses, and a fast hash gives them away cheaply. bcrypt goes the other way. It is a hash that is slow on purpose, and it lets the operator choose how slow.

bcrypt is built from the Blowfish cipher. Blowfish has a key setup that is already fairly costly, because it fills a large table with the results of many encryptions. bcrypt keeps that idea and repeats it as many times as the operator wants. The cost is a single number, and every step up doubles the work. This guide follows the algorithm from the digits of pi to the final string, with every value shown.

Table of Contents

• History and Standards
• From Blowfish to Eksblowfish
• The Algorithm
• The Hash String
• The 72-Byte Limit
• Versions and Bugs
• Interactive Visualizer
• A Worked Example
• Python Implementation
• Security Status
• FAQ
• References

History and Standards

Niels Provos and David Mazieres designed bcrypt for OpenBSD, and they presented it at USENIX in 1999 in a paper titled “A Future-Adaptable Password Scheme”. The name of the key setup in that paper is Eksblowfish, which stands for “expensive key schedule Blowfish”. The OpenBSD manual says that bcrypt first appeared in OpenBSD 2.1.

bcrypt is not an IETF or NIST standard. It is a de facto standard, with a reference implementation in OpenBSD and many ports in other systems. Its format follows the “modular crypt” convention, in which a hash starts with $ and an identifier. The OpenBSD manual describes the Blowfish form. It has 128 bits of salt, and the state is expanded with the salt and the password for a variable number of rounds. The maximum password length is 72. The final entry comes from encrypting the string OrpheanBeholderScryDoubt with the Blowfish state 64 times.

From Blowfish to Eksblowfish

Blowfish is a block cipher with 64-bit blocks and a 16-round Feistel network. Its state has two parts. The P-array has 18 words of 32 bits. Four S-boxes have 256 words of 32 bits each. Both start as the digits of pi, so there are 1,042 words in all, and their starting values are the same for every key. The first words are 243f6a88 85a308d3 13198a2e 03707344. The code in this guide computes all 1,042 words. A mistake in any of them would change the Blowfish test vectors, and the code reproduces all of those vectors, as the section on the code shows. The Blowfish guide describes the cipher in detail.

The normal Blowfish key setup is a loop. First, the key bytes are XORed into the P-array, with the key repeated as often as needed. Then the cipher encrypts a block of zeros with the current state. The result replaces the first two P words. The new result is encrypted again, and it replaces the next two words, and so on. This goes through all 18 P words and all 1,024 S-box words. The setup therefore needs 521 block encryptions, and the new state depends on every byte of the key.

bcrypt changes this key setup in two ways. It adds a salt, a 16-byte value that is XORed into every block before it is encrypted. And it repeats the whole expansion 2^cost times. That is the “expensive” part of Eksblowfish.

The Algorithm

Call the key expansion ExpandKey(state, salt, key). With a salt, it works like this:

for each of the 18 words P[i]:  P[i] = P[i] xor next 4 bytes of key (repeated)
data = 0 (64 bits)
for each pair of words (P[0], P[1]), (P[2], P[3]), ... then every S-box pair:
    data = data xor next 8 bytes of salt (repeated)
    data = BlowfishEncrypt(state, data)
    the pair of words = data

Without a salt, the XOR step is skipped, and the rest is the same. This is the standard Blowfish setup. The full algorithm has these steps:

1. Setup. Start from the digits of pi, and run ExpandKey(state, salt, key) once.
2. Repeat. Do 2^cost times: ExpandKey(state, 0, key), then ExpandKey(state, 0, salt). The salt serves as a second key here.
3. Encrypt. Take the 24 bytes of OrpheanBeholderScryDoubt as three 64-bit blocks. Encrypt all three blocks with the state in ECB mode. Do this 64 times in all, each time on the result of the last round.
4. Output. The 24 bytes after the last round are the hash. In the string, only the first 23 are used.

The key is the password bytes followed by one zero byte, cut to 72 bytes. The salt is 16 bytes. The cost is a number from 4 to 31. In all, bcrypt makes (1 + 2 * 2^cost) * 521 + 192 calls of the block cipher. The 192 are the 64 rounds of three blocks at the end. For cost 12 that is 4,268,745 calls, and every step up in cost doubles it.

The Hash String

A bcrypt hash is a string of 60 characters:

$2b$05$CCCCCCCCCCCCCCCCCCCCC.E5YPO9kmyuRGyh0XouQYb4YMJKvyOeW

It has four parts. $2b$ is the version. 05 is the cost, written with two digits. The next 22 characters are the salt, and the last 31 characters are the hash. This way the string carries everything that is needed to check a password later. The check repeats the computation with the same salt and cost, and it compares the results.

The salt and the hash are written in a Base64 variant that is particular to bcrypt. Its alphabet is ./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789, so a dot is 0 and a slash is 1. It has no padding. The 16-byte salt becomes 22 characters, which carry 132 bits, so the last character only uses its top 2 bits. That is why the last salt character is always one of ., O, e, or u. The 23 bytes of the hash become 31 characters. The code in this guide accepts any of the 64 characters in the last salt place, and it writes the salt in its canonical form in the result. For example, the salts that end in . and in A give the same hash, and the result shows the . form.

The 72-Byte Limit

The 18 words of the P-array take 72 bytes of key. So bcrypt cannot use more. The key is the password and its zero byte, cut to 72 bytes, which means a password of 72 or more bytes loses its zero byte, and any bytes after the 72nd are ignored. The OWASP guidance says the same: for most implementations the limit is 72 bytes, and it advises a password limit of 72 bytes or less.

For example, with the salt of the worked example below, 72 letters x and 80 letters x give the same hash, D7RDOYXakZhsFmh/LdqQNx0kQ424AFS. But 71 letters give WbbLb4J7PKYWYm3biA.M18AI380Pnzu. Two long passwords that share their first 72 bytes are therefore the same password to bcrypt. In the code of this guide, a zero byte inside a password is an ordinary byte. C functions such as crypt() take a string and stop at the first zero byte, but two of the pyca/bcrypt test vectors have a zero byte inside the password, and they confirm the ordinary-byte treatment.

Versions and Bugs

The prefix of a hash names the version. This list follows the history that Wikipedia describes, and the vectors of Openwall confirm the technical points:

• $2$ is the original version of 1999. Its key has no terminating zero byte.
• $2a$ is a revision of the original. It specified that the password is UTF-8 and that the terminating zero byte is part of the key.
• $2x$ and $2y$ came from the crypt_blowfish library of Openwall in June 2011. A bug in some code mishandled bytes of 0x80 or more. The prefix $2x$ marks hashes made with the bug, and $2y$ marks the fixed algorithm. Other projects did not adopt the idea.
• $2b$ came from OpenBSD in February 2014. It fixed a bug in which the length of a password of more than 255 bytes was stored in 8 bits, so such passwords were cut short.

The bug behind $2x$ was a sign extension. The C code read each key byte as a signed number, and a byte of 0x80 or more became a negative number when it was ORed into the 32-bit key word. All the upper bits of the word were set to one. As a result, different passwords gave the same key. With the salt /OK.fbVrR/bpIqNJ5ianF. and cost 5, the buggy code gives the same hash, ending in CE5elHaaO4EbggVDjb8P19RukzXSM3e, for the one-byte password a3 and for the three-byte password ff ff a3. The fixed algorithm gives Sa7shbm4.OzKpvFnX1pQLmQW96oUlCq for a3, and for ff ff a3 it gives CE5elHaaO4EbggVDjb8P19RukzXSM3e. The second one is the same as the buggy hash of a3. These values are in the Openwall test list, and the Python code in this guide reproduces them, with the bug as an option.

For plain ASCII passwords, $2a$, $2b$, and $2y$ give the same hash. The hash in the example above is the same under all three prefixes.

Interactive Visualizer

The visualizer above runs this exact algorithm with the $2b$ version. Enter a password of up to 72 bytes and a salt of 22 characters, and set the cost from 4 to 10. Then click Derive key. The log shows the start state, the first expansion with the salt, every round of the repeated expansion, the 64 encryptions of the magic string, and the final encoding. To keep the rows short, each of them shows the first three words of the P-array, and the first 24 bytes of long values. The salt must end in one of ., O, e, or u. When it ends, the page tells you how many of the 184 hash bits change when one bit of your password is flipped.

A Worked Example

This hashes the password U*U with the salt CCCCCCCCCCCCCCCCCCCCC. and cost 5. It is a test case in the Openwall list, which is why the salt looks odd. The values of the middle steps are not published anywhere. They come from the code in this guide, which gives the published hash.

The key and the salt. The password has three bytes, so the key is 552a5500, which is the password and the zero byte. Repeated, it gives the words 552a5500 and 552a5500, which are the same here. The salt decodes to the 16 bytes 10410410410410410410410410410410. As words, they are 10410410 and 41041041, repeated.

The start state. The P-array begins with P[0] = 243f6a88 and P[1] = 85a308d3, and it ends with P[17] = 8979fb1b. The first S-box begins with d1310ba6, and the last word of the last S-box is 3ac372e6. These come from the digits of pi.

The first expansion. XORing the key into the first two words gives 71153f88 and d0895dd3. After the whole expansion with the salt, the first four words of the P-array are 74bde96e df6cd999 6e8be7de 90129686.

The repeated expansions. With cost 5, there are 32 rounds. Each round runs ExpandKey with the key and then with the salt. After round 1, the first three P words are ae291558 eab98c8c 9cc6940c. After round 32, they are e5944bda e349ca19 7568b7a1.

The magic string. The 24 bytes of OrpheanBeholderScryDoubt are 4f72706865616e4265686f6c64657253637279446f756274. After 64 rounds of encryption with the final state, they become:

1bb69143f9a8d304c8d23d99ab049a77a68e2ccc744206bb

The last byte, bb, is dropped. The first 23 bytes are written in Base64 as E5YPO9kmyuRGyh0XouQYb4YMJKvyOeW, and the full hash is:

$2b$05$CCCCCCCCCCCCCCCCCCCCC.E5YPO9kmyuRGyh0XouQYb4YMJKvyOeW

In all, this run made 34057 calls of the block cipher. Changing one bit of the first password byte changes 97 of the 184 hash bits.

Python Implementation

This is a complete bcrypt, with Blowfish, the digits of pi, and the Base64 encoding. The tables are not copied from anywhere. The function pi_words computes them from Machin’s formula for pi, which takes a fraction of a second.

# bcrypt.py
#
# bcrypt, the password hashing function of Niels Provos and David Mazieres
# (USENIX 1999). It is the Blowfish cipher with an expensive key setup.
# The setup mixes the salt and the password into the cipher state, and then
# repeats a key expansion 2^cost times. At the end, bcrypt encrypts the
# 24 bytes "OrpheanBeholderScryDoubt" 64 times with that state. The result is
# written in the "modular crypt" form $2b$05$<22 salt chars><31 hash chars>.

import re

MASK = 0xFFFFFFFF


def pi_words(count):
    """The first `count` 32-bit words of the fractional part of pi, from Machin's formula."""
    bits = 32 * count + 64
    one = 1 << bits

    def arctan_inverse(x):
        total = term = one // x
        x2 = x * x
        n, sign = 1, -1
        while term:
            term //= x2
            n += 2
            total += sign * (term // n)
            sign = -sign
        return total

    pi = 4 * (4 * arctan_inverse(5) - arctan_inverse(239))
    frac = pi - 3 * one
    return [(frac >> (bits - 32 * (i + 1))) & MASK for i in range(count)]


# Blowfish starts from the digits of pi: 18 words for the P-array, then 4 * 256 for the S-boxes
_PI = pi_words(18 + 4 * 256)
INIT_P = _PI[:18]
INIT_S = [_PI[18 + 256 * i:18 + 256 * (i + 1)] for i in range(4)]


class Blowfish:
    def __init__(self):
        self.p = INIT_P[:]
        self.s = [box[:] for box in INIT_S]

    def f(self, x):
        s = self.s
        return ((((s[0][x >> 24] + s[1][(x >> 16) & 255]) & MASK) ^ s[2][(x >> 8) & 255]) + s[3][x & 255]) & MASK

    def encrypt(self, left, right):
        p = self.p
        for i in range(16):
            left ^= p[i]
            right ^= self.f(left)
            left, right = right, left
        left, right = right, left
        right ^= p[16]
        left ^= p[17]
        return left, right


def stream_word(data, pos, buggy=False):
    """The next 4 bytes of data as a big-endian word, wrapping around the end. Returns (word, new position).

    buggy=True reproduces the sign-extension bug of old crypt_blowfish code, which the prefix $2x$ marks:
    a byte of 0x80 or more was OR-ed into the word as a negative number.
    """
    word = 0
    for _ in range(4):
        byte = data[pos]
        if buggy and byte >= 0x80:
            byte |= 0xFFFFFF00
        word = ((word << 8) & MASK) | byte
        pos = (pos + 1) % len(data)
    return word, pos


def expand_key(bf, key, salt=None, buggy=False):
    """Blowfish key expansion. With a salt, each pair of words that replaces the state is first XORed with 8 bytes of salt."""
    pos = 0
    for i in range(18):
        word, pos = stream_word(key, pos, buggy)
        bf.p[i] ^= word
    left = right = 0
    spos = 0
    for i in range(0, 18, 2):
        if salt is not None:
            w1, spos = stream_word(salt, spos)
            w2, spos = stream_word(salt, spos)
            left ^= w1
            right ^= w2
        left, right = bf.encrypt(left, right)
        bf.p[i], bf.p[i + 1] = left, right
    for box in bf.s:
        for i in range(0, 256, 2):
            if salt is not None:
                w1, spos = stream_word(salt, spos)
                w2, spos = stream_word(salt, spos)
                left ^= w1
                right ^= w2
            left, right = bf.encrypt(left, right)
            box[i], box[i + 1] = left, right


MAGIC = b"OrpheanBeholderScryDoubt"
ALPHABET = "./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"


def key_bytes(password, minor="b"):
    """The key bytes: the password and a terminating zero byte (not for the original $2$), cut to 72 bytes.

    The password is an array of bytes, and a zero byte inside it is an ordinary byte. (The C function
    crypt() takes a C string, so it would stop at the first zero byte.)
    """
    return (password if minor == "" else password + b"\x00")[:72]


def eks_setup(cost, salt, key, observer=None, buggy=False):
    """EksBlowfishSetup: the expensive key setup."""
    bf = Blowfish()
    expand_key(bf, key, salt, buggy)
    for round_number in range(1 << cost):
        expand_key(bf, key, None, buggy)
        expand_key(bf, salt)
        if observer:
            observer(round_number, bf)
    return bf


def bcrypt_raw(password, salt, cost, minor="b", observer=None):
    """The 24-byte result of bcrypt for a 16-byte salt and a cost from 4 to 31."""
    if len(salt) != 16:
        raise ValueError("the salt must have 16 bytes")
    if not 4 <= cost <= 31:
        raise ValueError("the cost must be from 4 to 31")
    # the version "x" exists only to reproduce old hashes that were made with the sign-extension bug
    bf = eks_setup(cost, salt, key_bytes(password, "a" if minor == "x" else minor), observer, minor == "x")
    ctext = [int.from_bytes(MAGIC[4 * i:4 * i + 4], "big") for i in range(6)]
    for _ in range(64):
        for i in range(0, 6, 2):
            ctext[i], ctext[i + 1] = bf.encrypt(ctext[i], ctext[i + 1])
    return b"".join(w.to_bytes(4, "big") for w in ctext)


def b64_encode(data):
    """bcrypt's Base64: its own alphabet, no padding, bits taken from the top of each byte."""
    out = []
    for i in range(0, len(data), 3):
        chunk = data[i:i + 3]
        c1 = chunk[0]
        out.append(ALPHABET[c1 >> 2])
        c1 = (c1 & 3) << 4
        if len(chunk) == 1:
            out.append(ALPHABET[c1])
            break
        c2 = chunk[1]
        out.append(ALPHABET[c1 | (c2 >> 4)])
        c1 = (c2 & 15) << 2
        if len(chunk) == 2:
            out.append(ALPHABET[c1])
            break
        c3 = chunk[2]
        out.append(ALPHABET[c1 | (c3 >> 6)])
        out.append(ALPHABET[c3 & 63])
    return "".join(out)


def b64_decode(text, length):
    values = [ALPHABET.index(c) for c in text]
    out = bytearray()
    for i in range(0, len(values) - 1, 4):
        v = values[i:i + 4]
        out.append(((v[0] << 2) | (v[1] >> 4)) & 255)
        if len(out) >= length or len(v) < 3:
            break
        out.append(((v[1] << 4) | (v[2] >> 2)) & 255)
        if len(out) >= length or len(v) < 4:
            break
        out.append(((v[2] << 6) | v[3]) & 255)
    return bytes(out[:length])


def parse_setting(setting):
    """Split '$2b$05$<22 salt characters>...' into (minor version, cost, salt text)."""
    m = re.match(r"\$2([abxy]?)\$(\d\d)\$([./A-Za-z0-9]{22})", setting)
    if not m:
        raise ValueError("not a bcrypt setting")
    return m.group(1), int(m.group(2)), m.group(3)


def hashpw(password, setting):
    """password: bytes. setting: '$2b$05$' and 22 salt characters (anything after them is ignored)."""
    minor, cost, salt_text = parse_setting(setting)
    salt = b64_decode(salt_text, 16)
    digest = bcrypt_raw(password, salt, cost, minor)
    return "$2%s$%02d$%s%s" % (minor, cost, b64_encode(salt), b64_encode(digest[:23]))


def checkpw(password, hashed):
    expected = hashed
    got = hashpw(password, hashed)
    difference = len(got) ^ len(expected)
    for a, b in zip(got, expected):
        difference |= ord(a) ^ ord(b)
    return difference == 0


if __name__ == "__main__":
    # a known hash of the Openwall test set: the password is U*U
    setting = "$2a$05$CCCCCCCCCCCCCCCCCCCCC."
    hashed = hashpw(b"U*U", setting)
    print("Hash:     " + hashed)
    print("Verified: " + str(checkpw(b"U*U", hashed)))
    print("Wrong:    " + str(checkpw(b"U*V", hashed)))

Running it produces this output:

Hash:     $2a$05$CCCCCCCCCCCCCCCCCCCCC.E5YPO9kmyuRGyh0XouQYb4YMJKvyOeW
Verified: True
Wrong:    False

I checked this code against several independent sources before writing it up. The digits of pi and the Blowfish cipher match Eric Young’s test vectors, as published by Schneier: all 34 ECB vectors, all 24 key lengths of the key setup test, and the CBC test. Those vectors use only the key setup without a salt, so they test the tables and the cipher but not the salt. The hashes test the rest. The code reproduces 26 hashes of the Openwall crypt_blowfish test list, including the 8-bit cases of $2y$ and $2b$, and eight cases of $2x$ with the bug. It also reproduces 28 vectors from the test suite of pyca/bcrypt and 93 vectors from Botan, at costs 4, 5, and 12. Two entries of the Openwall list are not reproduced. They use the $2a$ mode of crypt_blowfish with certain 8-bit passwords. That mode gives other values for them, and this code does not copy it. The code is slow, because it runs in pure Python. The Botan vectors with cost 12 take most of the test time.

Security Status

bcrypt has a long record. It has been in use since 1999, and OWASP still lists it among the strong, slow hashing algorithms for password storage. The cost parameter is the answer to faster hardware: when computers get faster, the operator raises the cost by one, and the work doubles. OWASP advises a work factor of 10 or more for legacy systems that use bcrypt, and it recommends Argon2id first, then scrypt, when they are available.

The weakness of bcrypt is the other side of its design. Its working state is only 4168 bytes, about 4 KiB, which is the P-array and the four S-boxes. A scrypt table can have 16 MiB or more for each guess, so a chip that runs many guesses in parallel needs a lot of memory. A bcrypt guess needs only 4 KiB, so a chip can hold many copies. bcrypt makes a guess slow, but it does not make it big. The scrypt guide and the Argon2 guide cover the memory-hard designs.

The 72-byte limit is also a practical risk. A password longer than 72 bytes is silently cut. Some systems pre-hash the password with SHA-2 first to avoid that. OWASP warns that this is dangerous when done carelessly. A hash value can contain a zero byte, and the original bcrypt reads its password as a string that ends at the first zero byte. The hash value should be encoded as Base64 first. A pre-hash also allows “password shucking”, in which a leaked hash of the same inner function is used to speed up the attack.

FAQ

What does the cost number mean?

It is the base-2 logarithm of the number of rounds. Cost 5 means 32 rounds of expansion, and cost 12 means 4,096 rounds. Each step up doubles the time. The cost is stored in the hash string, so old hashes keep working when you raise it for new ones.

Why is the salt in the hash string?

Because it is not a secret. The salt only has to be unique for each password, so that two users with the same password get different hashes. The check needs the salt, and the string carries it. A 16-byte random salt from a good generator is the normal choice.

Why is the output only 23 bytes?

The cipher produces 24 bytes, but the hash part of the string has 31 characters. They carry 186 bits, which is 23 whole bytes. The 24th byte is dropped, and every compatible library does the same.

Is bcrypt still safe to use?

It is a sound choice for existing systems, with a cost of 10 or more, and when a well-reviewed implementation is the only option. For new designs, prefer Argon2id. OWASP recommends Argon2id first and scrypt second, and it lists bcrypt for legacy systems. The main reasons are its small memory use and the 72-byte limit on passwords.

Why do hashes start with $2a$, $2b$, or $2y$?

The prefix is the version. They differ in edge cases, such as passwords with 8-bit characters or more than 255 bytes. For ordinary ASCII passwords, the three give the same hash. A verifier can accept all three.

References

1. Provos, N. and Mazieres, D. “A Future-Adaptable Password Scheme.” USENIX Annual Technical Conference, 1999. Available at: https://www.usenix.org/legacy/event/usenix99/provos/provos.pdf

2. OpenBSD. “crypt(3) manual page.” Available at: https://man.openbsd.org/crypt.3

3. Solar Designer. “crypt_blowfish: bcrypt in C, with the test list.” Openwall. Available at: https://github.com/openwall/crypt_blowfish

4. Schneier, B. “Eric Young’s Blowfish test vectors.” Available at: https://www.schneier.com/wp-content/uploads/2015/12/vectors-2.txt

5. OWASP. “Password Storage Cheat Sheet.” Available at: https://cheatsheetseries.owasp.org/cheatsheets/Password_Storage_Cheat_Sheet.html

6. pyca. “bcrypt test vectors.” Available at: https://github.com/pyca/bcrypt

7. Botan project. “bcrypt test vectors.” Available at: https://github.com/randombit/botan

8. Wikipedia. “bcrypt.” Available at: https://en.wikipedia.org/wiki/Bcrypt