Blowing Up A Balloon And Breaking Crypto Crackers

Blowing Up A Balloon And Breaking Crypto Crackers

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]. It 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, where tCost (time cost) is the number of rounds. The delta value is the number of random blocks to mix with. The 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.

If we try an example from [here]:

===================
Message:        buildmeupbuttercup
Salt:		JqMcHqUcjinFhQKJ
Delta:		5
Time cost:	18
Space cost:	24
===================
Hash:	0c0c124bef8f70a9051dd29e0bd524479e488cfe1212c648d5ae33df728753ca

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.