In Cybersecurity, Memory Overflows Are Normally Bad … But Not With Balloon
In Cybersecurity, Memory Overflows Are Normally Bad … But Not With Balloon
I find these tables rather silly:
Why? Because it all depends on the hashing method used, and the speed of the cracking, and whether we are using brute force methods or dictionary attacks. Typically, in the statistics above, the estimation is based on a fast hashing method, such as SHA-1 or SHA-256. In real life, 11 lowercase letters of a password might actually take a long time to crack with brute force — and not a single day as defined. Most proper password cracking, too, uses GPUs, and the table gives no indication as to whether GPUs are used for the cracking.
Breaking GPUs
We have a problem with password hashing in that crackers can now run at speeds of TeraHashes per second. That’s a thousand billion passwords that can be hashed every second. The reason we can achieve these rates is that we can run the cracker on GPUs which have thousands of processing elements. We thus just segment our passwords up and then allocate them as threads to our processing elements. A GPU with 4,000 processing elements will thus speed up the hashing process by a factor of around 4,000. If we have four GPUs, it will speed up by a factor of around 16,000 over a single processing element.
Other weaknesses exist with hashing methods, including the ability to examine the cache memory and thus reveal the original password. So we need to find methods which challenge the crackers but still allow for good performance levels for valid password entry.
Balloon is one such method and was created in 2017 by Dan Boneh, Henry Corrigan-Gibbs, and Stuart Schechter [paper]:
Balloon
Balloon is a password derived function (PRF) and is the first cryptography method which has proven memory-hardness properties and 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 techniques, and scrypt produces a password-dependent memory access pattern.
The operation of Balloon supports the integration of other standard hashing methods, such as MD5, SHA-1, SHA-256, and SHA-3. It is also resistant from cache attacks, and where the internal state of the memory will not reveal information about the passwords which is being hashed.
Ballon thus aims to make the cracking of a hash difficult when running against GPUs, as it uses a number of rounds for the hashing processes which are difficult to perform in a threaded manner, along with providing a memory cost to reduce the opportunity for dictionary attacks.
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.
- t_cost (time cost) is the number of rounds.
- delta is the number of random blocks to mix with.
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. The basic algorithm is:
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]The implementation is then [here][here]:
import hashlib
hash_functions = {
'md5': hashlib.md5,
'sha1': hashlib.sha1,
'sha224': hashlib.sha224,
'sha256': hashlib.sha256,
'sha384': hashlib.sha384,
'sha512': hashlib.sha512
}
HASH_TYPE = 'sha256'
def hash_func(*args):
"""Concatenate all the arguments and hash the result.
Note that the hash function used can be modified
in the global parameter HASH_TYPE.
Args:
*args: Arguments to concatenate
Returns:
str: The hashed string
"""
t = ''.join([str(arg) for arg in args])
return hash_functions[HASH_TYPE](t).digest()
def expand(buf, cnt, space_cost):
"""First step of the algorithm. Fill up a buffer with
pseudorandom bytes derived from the password and salt
by computing repeatedly the hash function on a combination
of the password and the previous hash.
Args:
buf (list str): A list of hashes as bytes.
cnt (int): Used in a security proof (read the paper)
space_cost (int): The size of the buffer
Returns:
void: Updates the buffer and counter, but does not
return anything.
"""
for s in range(1, space_cost):
buf.append(hash_func(cnt, buf[s - 1]))
cnt += 1
def mix(buf, cnt, delta, salt, space_cost, time_cost):
"""Second step of the algorithm. Mix time_cost number
of times the pseudorandom bytes in the buffer. At each
step in the for loop, update the nth block to be
the hash of the n-1th block, the nth block, and delta
other blocks chosen at random from the buffer.
Args:
buf (list str): A list of hashes as bytes.
cnt (int): Used in a security proof (read the paper)
delta (int): Number of random blocks to mix with.
salt (str): A user defined random value for security
space_cost (int): The size of the buffer
time_cost (int): Number of rounds to mix
Returns:
void: Updates the buffer and counter, but does not
return anything.
"""
for t in range(time_cost):
for s in range(space_cost):
buf[s] = hash_func(cnt, buf[s - 1], buf[s])
cnt += 1
for i in range(delta):
other = int(hash_func(cnt, salt, t, s, i).encode('hex'), 16) % space_cost
cnt += 1
buf[s] = hash_func(cnt, buf[s], buf[other])
cnt += 1
def extract(buf):
"""Final step. Return the last value in the buffer.
Args:
buf (list str): A list of hashes as bytes.
Returns:
str: Last value of the buffer as bytes
"""
return buf[-1]
def balloon(password, salt, space_cost, time_cost, delta=3):
"""Main function that collects all the substeps. As
previously mentioned, first expand, then mix, and
finally extract. Note the result is returned as bytes,
for a more friendly function with default values
and returning a hex string see the function balloon_hash
Args:
password (str): The main string to hash
salt (str): A user defined random value for security
space_cost (int): The size of the buffer
time_cost (int): Number of rounds to mix
delta (int): Number of random blocks to mix with.
Returns:
str: A series of bytes, the hash.
"""
buf = [hash_func(0, password, salt)]
cnt = 1
expand(buf, cnt, space_cost)
mix(buf, cnt, delta, salt, space_cost, time_cost)
return extract(buf)
def balloon_hash(password, salt):
"""A more friendly client function that just takes
a password and a salt and computes outputs the hash in hex.
Args:
password (str): The main string to hash
salt (str): A user defined random value for security
Returns:
str: The hash as hex.
"""
delta = 4
time_cost = 20
space_cost = 16
return balloon(password, salt, space_cost, time_cost, delta=delta).encode('hex')If we try an example from [here][here]:
===================
Message: buildmeupbuttercup
Salt: JqMcHqUcjinFhQKJ
Delta: 5
Time cost: 18
Space cost: 24
===================
Hash: 0c0c124bef8f70a9051dd29e0bd524479e488cfe1212c648d5ae33df728753caThe objective is to overflow the memory that is assigned to GPU element, and thus to make it difficult for the processors to allocate local memory:
Overall, the two main competitors to Balloon are scrypt and Argon2i, and where Bohen managed to find an attack against the method. Argon2 was designed Alex Biryukov, Daniel Dinu, and Dmitry Khovratovich, and is a key derivation function (KDF), where were we can create hashed values of passwords, or create encryption keys based on a password. It was a winner of the Password Hashing Competition in July 2015, and is robust against GPU and side channel attacks
Conclusions
The hashing methods we have often created are often optimized for speed, but sometimes we need to make the processing of a hashed password difficult, so that we can stop the crackers. Balloon is well matched to this challenge. Here is a demo:
https://asecuritysite.com/kdf/balloon
References
[1] Boneh, D., Corrigan-Gibbs, H., & Schechter, S. (2016). Balloon hashing: A memory-hard function providing provable protection against sequential attacks. In Advances in Cryptology–ASIACRYPT 2016: 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4–8, 2016, Proceedings, Part I 22 (pp. 220–248). Springer Berlin Heidelberg.