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

摘要

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