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…
