Achieving Higher Success Probability in Time-Memory Trade-Off Cryptanalysis without Increasing Memory Size

摘要

The time-memory trade-off cryptanalysis for block ciphers with a search space of size 2~N (N: key length) cannot achieve a success probability excceding 63. This is caused by some unavoidable overlapping of keys in the space. For elavating the success probability of finding the correct key, a larger search space is necessary. That is, the increase of time complexity for precomputation would be inevitable. This paper theoretically shows, however, no further price is required for the size of look-up tables for the number of encryptions for searching for the key that matches the given ciphertext - plaintext pairs. This theory is confirmed by some empilical results.