Implementation and Comparison of Cryptanalytic Trade-offs

Abstract

Information security plays a central role in today's society, protecting sensitive communications and financial transactions and authenticating entities on the Internet. Hash functions are widely used in these applications. These deterministic one way functions take any input and produce a random fixed size output that cannot be reversed back to the input. This experimental research empirically compares three computational characteristics, namely disk storage, memory use and processing, of three cryptanalytic trade-off techniques that invert the output of hash functions. The techniques were implemented in Python and compared along three dimensions: a brute force attack for processing, and a dictionary attack for memory and for disk. Since the Hellman and Rainbow Tables techniques are probabilistic, that is, they offer no guarantee that every hash in the database can be inverted, only the tests in which all submitted hashes were inverted were analysed. The third algorithm, called Vanilla, is the only non-probabilistic one, so every hash in its database is always reversible. Each technique was submitted to multiple runs with varying configuration parameters over the same input set. Considering only the runs with full success that use half of the disk space of a dictionary attack, Rainbow Tables, Hellman and Vanilla required 0.0038, 0.0055 and 0.213 times the processing of a brute force attack, and used 3, 0.15 and 0.002 times the memory of a dictionary attack. The probabilistic algorithms need about 45 times less processing than Vanilla, while Hellman and Rainbow Tables use roughly 75 and 1500 times more memory during inversion. The conclusion is that, despite performing more hash operations, Vanilla uses exponentially less memory than the probabilistic algorithms, which makes it competitive on architectures that favour processing over memory, such as GPUs and FPGAs.