TMTO Variants
Objective
Research, implement, and assess an improvement to the Distinguished Point TMTO used in the Password Recovery Lab.
Scenario
There have been a number of improvements to the cryptanalytic TMTO originally developed by Hellman. In fact, the version that we used in the Password Recovery Lab was not the original TMTO, but the Distinguished Point (DP) variant which uses distinguished hash values (given by the prefix values in the table build code) to determine the end-point of a strand.
For this problem, you need to research a TMTO variant, implement it, and compare its performance to the DP variant that we used.
Several papers are provided in my Box drive, two of which describe specific TMTO variants:
- Oechslin's paper, Making a Faster Cryptanalytic Time-Memory Trade-Off introduces the use of rainbow strands and is the origin of the rainbow table approach.
- The paper by Hong et al., Variants of the Distinguished Point Method for Cryptanalytic Time-Memory Trade-Offs describes the variable distinguished point (VDP) method, a variant on the DP method.
Procedure
You will need to choose a paper describing a TMTO variant, study the paper, and write a summary of the technique and why it is an improvement over the DP TMTO. Further, you must implement the variant, preferably by modifying the code provide in the Password Recovery Lab, and assess its performance (passwords recovery rate and running time) compared to the DP TMTO.
- Choose a TMTO variant. You may use one of the provided papers or find one on your own.
- Study the paper and write a summary of the technique and its advantages. Explain why the variant is expected to produce improved performance, whether in recovery rate, running time, or storage requirement.
- Implement the variant, preferably by modifying the program build_table.py that was provided for the Password Recovery Lab.
- Assess the recovery rate (percentage of passwords recoverable) and compare to the recovery rate of the DP TMTO. Note: It is possible to test a single block by choosing a large, random selection of possible passwords, computing the hash for each, and then seeing what percentage of the passwords can be recovered from their hashes using just one block.
- Assess the running time of the every-time work. Collect empirical timings for both the variant and the DP TMTO. You do not have to worry about the one-time work, unless it is vastly different from the DP TMTO.
Advanced: Port your TMTO variant to a compiled language such as C++. Evaluate the performance improvement over the Python implementation.