GPU-hostile, Precomputation-Resistant Hashing Algorithms
School: La Cueva High
Area of Science: Security, Mathematics
Interim: Problem Definition:
Hashing algorithms map an input of some sort to a fixed-length (or length range) target, providing several functions, such as checking file integrity, checking passwords without storing them, finding data, and more. Current hash functions are built to output a set-length target, giving the algorithm an “expiration date” when the entropy offered by the hashing function becomes weak enough to be attackable.
Many current hashing algorithms are extremely vulnerable to rainbow-table precomputation attacks. The SHA family of hashes is currently non-reversible, but due to the nature of the algorithm they can quickly be sped-up on a GPU, and with the advent of multi-terabyte hard drives and CUDA/OpenCL, the storage and generation of fractional-reserve rainbow tables is possible on a $1,000 budget. These precomputation attacks can be used to attack any site using the encryption algorithm the table was built with, assuming the site didn’t use a salt.
Plan for Solving:
Resistance to rainbow-table attacks is already implemented by some in the form of a salt, but this salt is a construct placed on top of the has function, usually using some form of string concatenation. We intend to build the salt into the algorithm—by allowing the modification of the starting hx variables to other primes in addition to an optional concatenation salt. We plan to implement a branching-pathway approach to the hash to both complicate the hash logic to be further resistant against GPU, FPGA, and ASIC approaches, and to further the difficulty of reversing the hash logically. By implementing a salt into the algorithm, we see two main advantages: rainbow tables must be computed after the hacker retrieves both the hashes and the salt input values, and a rainbow table can’t be reused in attacks against other databases of hashed data. If the database is attacked, there is a grace-period padding of time in which the data hasn’t been cracked, and in which necessary steps can be taken to make the cracked data useless (such as freezing accounts, changing passwords, etc.) In order to future-proof the algorithm (instead of having to adapt the algorithm to a larger digest at a later point in time), our algorithm will be able to accept an arbitrary number of starting hx values, making the hashing function dynamic in regard to supported maximum entropy. We intend to tackle to idea of expediting the creation of rainbow tables by making the algorithm memory-intensive, requiring large lookup tables. In doing this, GPUs have a harder time computing the hashes, while CPUs have larger memory stores, allowing the algorithm to run at a reasonable speed on CPU-based systems.
So far, we have gotten a working, slow Java implementation of a modified version of SHA1 which takes custom hx inputs. We have planned, but not yet implemented, our branching algorithm concept, and we have worked on (but have not completed) a memory step that requires around 4KB of lookup table data, which in the future may also be a pivot point for a built-in seed. We have tested our current algorithm, and as expected have not found any collisions through testing over 2,000,000 different unique inputs. Our message digest is not a fixed-size digest, but a fixed-target, that target being 38-40 characters long.
We expect to, by April, have a working algorithm that accepts custom hx inputs (as an alternative to string-concatenation salts), works on a branching-algorithm to prevent reversal, is based on the proven foundation of the SHA family, requires lots of memory for lookup tables making GPUs, FPGAs, and potentially ASICs less efficient at generating rainbow tables, and allowing a custom number of hx inputs to increase or decrease maximum entropy without requiring a new implementation of the given algorithm. This algorithm will have its outputs distributed very evenly among all output possibilities by using primality in hx inputs, and will be resistant to precomputation attacks due to its built-in, forced salt.
Connor Brown, Gavin Lewis, Ryan DeLaO, Maxwell Sanchez
Ryan De La O
Sponsoring Teacher: Samuel Smith
Mail the entire Team