The Balloon Hashing Algorithm

The Balloon Hashing Algorithm

Introduction

A good password hash should be expensive to compute, and it should be expensive in memory. Memory is the cost that custom chips cannot avoid. Balloon hashing is a password hashing function that uses a large buffer of memory, like scrypt, and it is built only from an ordinary hash function such as SHA-256. There are no special ciphers and no custom primitives.

Balloon has one feature that sets it apart from scrypt. The order in which it reads its memory does not depend on the password. An attacker who can watch the memory accesses of a running computation, for example through a cache, learns nothing about the password from them. This guide covers the whole algorithm, with every hash call shown for a small example.

Table of Contents

• History and Standards
• The Algorithm
• The Parameters
• Why the Access Pattern Is Password-Independent
• Interactive Visualizer
• A Worked Example
• Python Implementation
• Security Status
• FAQ
• References

History and Standards

Dan Boneh, Henry Corrigan-Gibbs, and Stuart Schechter designed Balloon hashing, and they presented it at ASIACRYPT 2016. The paper is titled “Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks”. Its abstract describes Balloon as the first practical cryptographic hash function that has proven memory-hardness properties in the random-oracle model, uses a password-independent access pattern, and meets or exceeds the performance of the best heuristically secure password hashing algorithms.

The authors’ project page says that Balloon is a “mode of operation” for a standard hash function, so that any standard hash such as SHA-3 or SHA-512 can be used inside it. It also says that the function is moderately hard to compute with N bits of space but prohibitively expensive to compute with much less space, for example N/8 bits. These are the authors’ claims.

I did not find an IETF RFC or an ISO standard for Balloon. The NIST digital identity guidelines, SP 800-63B, name it as one example of a suitable key derivation function, together with PBKDF2, and say that a memory-hard function should be used. The OWASP Password Storage Cheat Sheet does not list Balloon among its recommended algorithms. The authors warn that their own research prototype is not safe for production use.

The Algorithm

Balloon works on a buffer buf of s_cost blocks, where each block is one output of the hash function, which is 32 bytes for SHA-256. It has three steps. The pseudo-code below follows the paper, and every call of hash takes a counter first:

delta = 3                          # number of dependencies per block
cnt = 0                            # a counter, used in the security proof

# Step 1: expand the password and salt into the buffer
buf[0] = hash(cnt++, password, salt)
for m = 1 to s_cost - 1:
    buf[m] = hash(cnt++, buf[m-1])

# Step 2: mix the buffer t_cost times
for t = 0 to t_cost - 1:
    for m = 0 to s_cost - 1:
        prev = buf[(m - 1) mod s_cost]
        buf[m] = hash(cnt++, prev, buf[m])
        for i = 0 to delta - 1:
            idx_block = ints_to_block(t, m, i)
            other = to_int( hash(cnt++, salt, idx_block) ) mod s_cost
            buf[m] = hash(cnt++, buf[m], buf[other])

# Step 3: extract
return buf[s_cost - 1]

Expand. The first block is the hash of the password and the salt. Each next block is the hash of the one before. This is a long chain, and it fills the buffer.

Mix. This is the main work. For each round t and each block m, the block is first hashed together with the block before it, which wraps around at the start. Then it is hashed delta more times, each time with another block of the buffer. Which other block is chosen comes from other, a number between 0 and s_cost - 1. The number comes from a hash of the salt and an idx_block that holds the three numbers t, m, and i. The other block can be any block, including the one that is being updated. After a mixing round, every block has depended on many others, and the dependencies are spread over the whole buffer.

Extract. The output is the last block of the buffer.

The paper’s function ints_to_block is a detail of the encoding. This guide uses the encoding of the Python and Rust implementations, whose test vectors agree. A whole number is written as 8 bytes in little-endian order, and idx_block is the SHA-256 hash of the three numbers t, m, and i. The counter is written the same way. to_int reads a hash as a little-endian number.

The Parameters

• s_cost is the space cost. It is the number of blocks in the buffer, so the buffer needs 32 * s_cost bytes with SHA-256.
• t_cost is the time cost. It is the number of mixing rounds.
• delta is the number of other blocks that each block is hashed with in each round. The pseudo-code uses 3. The Rust crate fixes it at 3 in its code. The Python package accepts other values, but its test vectors use 3. So other values work in the code of this guide, but they are outside the set that outside vectors confirm.
• The hash function can be any standard hash in principle, such as SHA-512 or BLAKE2b. A different hash changes the block size and the output length, and the published vectors do not cover it. All concrete vectors and all the code in this guide use SHA-256, with counters and indices written as 8-byte little-endian numbers.
• p_cost applies to the multi-core variant described below.

The number of hash calls is s_cost + t_cost * s_cost * (1 + 3 * delta), because each block in each round takes 1 call for the previous block, and 3 calls for each of the delta dependencies. These are one for idx_block, one for other, and one to mix. For s_cost = 1024, the buffer has 32768 bytes. A buffer of 2^20 blocks has 32 MiB.

Balloon-M is a multi-core variant. It runs p_cost independent instances, and the instances differ only in a thread number, from 1 up to p_cost, which is written as 8 little-endian bytes after the salt. The outputs are XORed, and the result is hashed once more with the password and the salt.

Why the Access Pattern Is Password-Independent

In scrypt, the table index in the second loop comes from the data, which depends on the password. In Balloon, the index other comes from hash(cnt, salt, idx_block). The inputs are a counter, the salt, and the numbers t, m, and i. The password does not appear in any of them. So the list of blocks that are read is fixed by the salt and the costs alone. An attacker who sees which memory cells are read learns something about the salt, which is not secret, and nothing about the password.

The code in this guide checks this. Two different passwords with the same salt produce the same list of other indices, and a different salt produces a different list.

Interactive Visualizer

The visualizer above runs this exact algorithm, with SHA-256 and delta = 3. Enter a password and a salt as text, and set s_cost from 1 to 32 and t_cost from 1 to 4. Then click Derive key. The log shows every block of the expansion, and then every mixing step. Each mixing row names the previous block and the three other blocks that were used. The last row is the extraction. When it ends, the page tells you how many of the 256 bits change when one bit of your password is flipped.

A Worked Example

This is one of the test vectors. The password is empty, the salt is salt, s_cost = 3, t_cost = 3, and delta = 3. The result is 5f02f8206f9cd212485c6bdf85527b698956701ad0852106f94b94ee94577378.

Expand. The first hash takes the counter 0 as 8 bytes, the empty password, and the salt, which is the input 000000000000000073616c74, in the order counter, password, salt. The result is the first block, buf[0] = b9e2c4b92b90d8d91760f26071b3a2a84e6378b4dbf44d03c538d9dcf5863bf3. The counter 1 and buf[0] give buf[1] = 07783f2d7a6f0d1f2e19734e6c7d2469071df6529f5d24c54677b3aae1ab296e. The counter 2 and buf[1] give buf[2] = c5e03f53103378f390a7510b380da7c9595b6b91f41b5ee6482fe92b7ff65082. The counter is now 3.

The first mixing step. This is round 0, block 0. The previous block is buf[2], because the index wraps around. Hashing the counter 3, buf[2], and buf[0] gives 007ee9d66d47c24fa6ed9a6a583900c8a2ed280d766d75e5119c71239c99dec9, and this becomes the new buf[0]. Then the three dependencies follow:

1. For i = 0, the block idx_block is the hash of the numbers 0, 0, and 0, which is 9d908ecfb6b256def8b49a7c504e6c889c4b0e41fe6ce3e01863dd7b61a20aa0. The hash of the counter 4, the salt, and this block starts with 7d1c3c8cb80aec5cb66bcb9a3a5e677288cb2372eb8fed2fd0eb14bb476e47b4, and as a little-endian number modulo 3 it is 0. So buf[0] is hashed with buf[0], which is itself. The counter is now 6, and the new buf[0] is 503bd60b7aaebc25b3dee101ebd789dd1d9e2b75c6430268ee19b6c9be1b4d1a.
2. For i = 1, the idx_block is 85526ba79728a470972be92942ef4de212630c9368703cb4ab3cb42dece95912. The hash of the counter 6, the salt, and idx_block starts with d82282bab65b13bf598c773138b105640be6b90c4619024594a4ac8dd6341e0f, which gives 0 modulo 3. This is buf[0] again, and the new buf[0] is 13245eff238d8c25a4af16cfd3c5c97bcbd987cafa63752590f6f91d765a4c77.
3. For i = 2, the idx_block is 845c35898d2cf4c1a70d3ed5cc85ccc2366c5acbfbdb1d91829efee5a4f30394. The hash of the counter 8, the salt, and idx_block starts with 634f18c898bdec573dc3b69a62c4ab3200c3aecae36f819206826571767a6d74, which gives 2. This time the other block is buf[2], and the new buf[0] is 301f4adc8866003fa75c096a195bee240458d4230c6a2e1dbab6859411d8b4bb.

All the dependencies. The other blocks of all nine mixing steps, in the form (round, block): list, are:

(1, 0): 0, 0, 2; (1, 1): 0, 0, 0; (1, 2): 2, 0, 1; (2, 0): 0, 1, 2; (2, 1): 0, 2, 0; (2, 2): 1, 2, 1; (3, 0): 2, 0, 1; (3, 1): 2, 0, 1; (3, 2): 2, 2, 2

The list is the same for every password. With the password password and the same salt, the list does not change.

The result. After the last mixing step, buf[2] is 5f02f8206f9cd212485c6bdf85527b698956701ad0852106f94b94ee94577378. That is the output. The whole run used 93 hash calls, which matches 3 + 3 * 3 * 10. Other vectors are 716043dff777b44aa7b88dcbab12c078abecfac9d289c5b5195967aa63440dfb for the password hunter42 and the salt examplesalt with s_cost = 1024 and t_cost = 3, and 20aa99d7fe3f4df4bd98c655c5480ec98b143107a331fd491deda885c4d6a6cc for the password password, the empty salt, s_cost = 3, and t_cost = 3. For Balloon-M with the empty password, the salt salt, s_cost = 3, t_cost = 3, and p_cost = 2, the result is f8767fe04059cef67b4427cda99bf8bcdd983959dbd399a5e63ea04523716c23.

Python Implementation

This is a complete Balloon, with the multi-core variant. It uses the SHA-256 of Python’s hashlib. The function balloon can also record every step, so you can print the steps shown above.

# balloon.py
#
# Balloon hashing, the memory-hard password hashing function of Dan Boneh,
# Henry Corrigan-Gibbs and Stuart Schechter (ASIACRYPT 2016). It uses an
# ordinary hash function and a buffer of s_cost blocks. First it fills the
# buffer with a chain of hashes. Then it mixes the buffer t_cost times. In
# each mixing step a block is hashed with the block before it and with
# `delta` other blocks. Which other blocks is decided by the salt and the
# position, never by the password, so the memory access pattern does not leak.

import hashlib


def hash_ints_and_bytes(*parts):
    """SHA-256 of the parts joined together. A whole number is written as 8 little-endian bytes."""
    data = b""
    for part in parts:
        data += part.to_bytes(8, "little") if isinstance(part, int) else part
    return hashlib.sha256(data).digest()


def balloon(password, salt, s_cost, t_cost, delta=3, trace=None):
    """The hash for a password and a salt (both bytes). Returns the last block of the buffer.

    trace, when it is a list, receives (name, details) for each step, so that the steps can be printed.
    """
    if min(s_cost, t_cost, delta) < 1:
        raise ValueError("s_cost, t_cost and delta must be positive")
    cnt = 0
    buf = [hash_ints_and_bytes(cnt, password, salt)]          # buf[0] = hash(cnt++, passwd, salt)
    cnt += 1
    if trace is not None:
        trace.append(("expand", 0, buf[0]))
    for m in range(1, s_cost):                                # buf[m] = hash(cnt++, buf[m-1])
        buf.append(hash_ints_and_bytes(cnt, buf[m - 1]))
        cnt += 1
        if trace is not None:
            trace.append(("expand", m, buf[m]))
    for t in range(t_cost):
        for m in range(s_cost):
            prev = buf[(m - 1) % s_cost]
            before = buf[m]
            buf[m] = hash_ints_and_bytes(cnt, prev, buf[m])   # buf[m] = hash(cnt++, prev, buf[m])
            cnt += 1
            others = []
            for i in range(delta):
                idx_block = hash_ints_and_bytes(t, m, i)      # idx_block = ints_to_block(t, m, i)
                other = int.from_bytes(hash_ints_and_bytes(cnt, salt, idx_block), "little") % s_cost
                cnt += 1
                others.append(other)
                buf[m] = hash_ints_and_bytes(cnt, buf[m], buf[other])
                cnt += 1
            if trace is not None:
                trace.append(("mix", (t, m), before, prev, others, buf[m]))
    return buf[s_cost - 1]


def balloon_m(password, salt, s_cost, t_cost, p_cost, delta=3):
    """Balloon-M: p_cost independent instances, which differ in a thread number added to the salt, XORed together."""
    if p_cost < 1:
        raise ValueError("p_cost must be positive")
    combined = bytes(32)
    for thread in range(1, p_cost + 1):
        out = balloon(password, salt + thread.to_bytes(8, "little"), s_cost, t_cost, delta)
        combined = bytes(a ^ b for a, b in zip(combined, out))
    return hash_ints_and_bytes(password, salt, combined)


def verify(expected, password, salt, s_cost, t_cost, delta=3):
    got = balloon(password, salt, s_cost, t_cost, delta)
    difference = 0
    for a, b in zip(got, expected):
        difference |= a ^ b
    return len(expected) == len(got) and difference == 0


if __name__ == "__main__":
    # a test vector that the Python, Rust and Go implementations agree on
    out = balloon(b"hunter42", b"examplesalt", 1024, 3)
    print("Balloon('hunter42', 'examplesalt', s_cost=1024, t_cost=3):")
    print(out.hex())
    print("Verified: " + str(verify(out, b"hunter42", b"examplesalt", 1024, 3)))
    print("Wrong:    " + str(verify(out, b"hunter43", b"examplesalt", 1024, 3)))

Running it produces this output:

Balloon('hunter42', 'examplesalt', s_cost=1024, t_cost=3):
716043dff777b44aa7b88dcbab12c078abecfac9d289c5b5195967aa63440dfb
Verified: True
Wrong:    False

I checked this code against several independent sources before writing it up. It reproduces all five test vectors of the Python implementation in the package balloon-hashing by nachonavarro, and the Rust crate balloon-hash of RustCrypto has the same five values. The Rust tests say that they were checked against the Python package and against a Go implementation. The code also reproduces all eight Balloon-M vectors of the Rust tests, with p_cost from 1 to 4. I read these test files and did not run their code. No outside vectors that I found use a delta other than 3, so the code supports other values, but only the value 3 is checked. The paper’s PDF was not available to me, so the pseudo-code above comes from the comments in the Rust code, which quote it line by line, and from the abstract and the project page.

Security Status

The security claims of Balloon are of a specific kind. The authors prove its memory-hardness in the random-oracle model, which treats the hash function as an ideal random function, and for a sequential adversary. The abstract says that this model captures attacks that run on single-core machines. It adds that attacks on massively parallel special-purpose machines are outside the model, and that the paper discusses them and proposes practical defenses. The paper also gives proofs for scrypt and Argon2i in the same model, and it describes a practical attack on Argon2i that uses less space than was claimed.

Those parallel attacks have been studied. Joel Alwen and Jeremiah Blocki introduced theoretical attacks on Argon2i-A and Balloon at CRYPTO 2016. A later paper by the same authors has the title “Towards Practical Attacks on Argon2i and Balloon Hashing”. It reports that the attacks matter for practical parameters. It also reports that a technique of Corrigan-Gibbs and others for improving security can be overcome under realistic hardware constraints. These attacks need an attacker with a custom device and many cores. They are a reason to prefer large parameters, and a reason to be careful about claims of provable security.

The password-independent access pattern is a real advantage against side channels. In scrypt, memory reads that depend on secret data could leak information to an observer of the cache. In Balloon, they cannot. The price is that the Alwen-Blocki attacks work on functions with a data-independent pattern, and Balloon is one of them.

Balloon is also much less widely deployed than PBKDF2, bcrypt, scrypt, and Argon2. For most new systems, the OWASP guidance points to Argon2id first, and scrypt when Argon2id is not available. Balloon is a good design to study, and a possible choice where a library with good review is available.

FAQ

How is Balloon different from scrypt?

Both fill a large buffer. scrypt reads it back in an order that depends on the data, so its memory access depends on the password. Balloon reads it in an order that depends only on the salt and the costs. scrypt needs a block cipher core, Salsa20/8. Balloon needs only a hash function.

What do s_cost and t_cost control?

s_cost is the number of blocks, so it sets the memory. t_cost is the number of mixing rounds, so it sets how many times each block is mixed. The memory is 32 * s_cost bytes with SHA-256. The time grows with the product of both.

Which hash function does Balloon use?

Any standard hash can be used. The authors name SHA-3 and SHA-512 as examples. The test vectors in this guide use SHA-256. The output length of Balloon is the output length of the hash.

Does Balloon need a salt?

Yes, a salt is required. The salt is part of the first hash, and it also decides which blocks are read. The salt does not need to be secret, but it must be different for every password, so that two users with the same password do not share a pattern or a hash.

Should I use Balloon in production?

Balloon is mainly of research and educational interest. The authors’ own research code is not meant for production, and OWASP does not list Balloon. Prefer Argon2id, or scrypt, unless you have a specific reason to use Balloon. In that case, use a library that has been reviewed and tested against vectors, such as the Rust crate whose test vectors this guide uses.

References

1. Boneh, D., Corrigan-Gibbs, H., and Schechter, S. “Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks.” ASIACRYPT 2016. Available at: https://eprint.iacr.org/2016/027

2. Stanford Applied Crypto Group. “Balloon Hashing.” Project page. Available at: https://crypto.stanford.edu/balloon/

3. Alwen, J. and Blocki, J. “Towards Practical Attacks on Argon2i and Balloon Hashing.” Cryptology ePrint Archive, Paper 2016/759. Available at: https://eprint.iacr.org/2016/759

4. NIST. “Digital Identity Guidelines: Authentication and Lifecycle Management.” NIST Special Publication 800-63B. Available at: https://pages.nist.gov/800-63-3/sp800-63b.html

5. RustCrypto. “balloon-hash: Pure Rust implementation of the Balloon password hashing function.” Available at: https://github.com/RustCrypto/password-hashes/tree/master/balloon-hash

6. nachonavarro. “balloon-hashing: Python implementation of Balloon hashing.” Available at: https://github.com/nachonavarro/balloon-hashing

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