A Cryptanalytic Time-Memory Tradeoff

Many searching problems allow time-memory tradeoffs. That is, if there are K possible solutions to search over, the time-memory tradeoff allows the solution to be found with high probability, in T operations (time) with M words of memory, provided the time-memory product T ×M is larger than K. Cryptanalytic attacks based on exhaustive key search are the typical context where time-memory tradeoffs are applicable. Due to large key sizes, exhaustive key search usually needs unrealistic computing pow-ers and corresponds to a situation where T = K and M = 1. However, if the same attack has to be carried out numerous times, it may be possible to execute the exhaus-tive search in advance and store all the results in a memory. Once this precomputation is done, the attack could be performed almost instantaneously, although in practice, the method is not realistic because of the huge amount of memory needed: T = 1, M = K. The aim of a time-memory tradeoff is to mount an attack that has a lower online processing complexity than exhaustive key search and lower memory complexity than a table lookup, neglecting the precomputations (hence, it only makes sense if the attack has to be performed multiple times). The method can be used to invert an