BalloonBalloon was created in 2017 by Dan Boneh, Henry Corrigan-Gibbs, and Stuart Schechter [paper]. It is a password derived function. It is the first cryptography method which has proven memory-hardness properties and uses a password-independent access pattern. A memory-hardness system aims to consume a large amount of memory and thus defeat GPU/specialist hardware. With this we often fill up a buffer with random data, and then read and write bytes to the buffer. The existing methods of password derivation functions such as BCrypt, PBKDF2 and scrypt suffer from weaknesses. Methods such as BCrypt and PBKDF2 are not memory hard techiques, and scrypt produces a password-dependent memory access pattern. |
Background
Ballon aims to make the cracking of a hash difficult when running against GPUs, as it uses a number of rounds for the hashing processes, along with providing a memory cost to reduce the opportunity for dictionary attacks.
func Balloon(block_t passwd, block_t salt, int s_cost, // Space cost (main buffer size) int t_cost): // Time cost (number of rounds) int delta = 3 // Number of dependencies per block int cnt = 0 // A counter (used in security proof) block_t buf[s_cost]): // The main buffer // Step 1. Expand input into buffer. buf[0] = hash(cnt++, passwd, salt) for m from 1 to s_cost-1: buf[m] = hash(cnt++, buf[m-1]) // Step 2. Mix buffer contents. for t from 0 to t_cost-1: for m from 0 to s_cost-1: // Step 2a. Hash last and current blocks. block_t prev = buf[(m-1) mod s_cost] buf[m] = hash(cnt++, prev, buf[m]) // Step 2b. Hash in pseudorandomly chosen blocks. for i from 0 to delta-1: block_t idx_block = ints_to_block(t, m, i) int other = to_int(hash(cnt++, salt, idx_block)) mod s_cost buf[m] = hash(cnt++, buf[m], buf[other]) // Step 3. Extract output from buffer. return buf[s_cost-1]
In this we have a password and some salt. It then uses s_cost (space cost) as the number of digest-sized blocks in buffer, where tCost (time cost) is the number of rounds. The delta value is the number of random blocks to mix with.
If we try an example from [here]:
=================== Message: buildmeupbuttercup Salt: JqMcHqUcjinFhQKJ Delta: 5 Time cost: 18 Space cost: 24 =================== Hash: 0c0c124bef8f70a9051dd29e0bd524479e488cfe1212c648d5ae33df728753ca