International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Applying Time-Memory-Data Trade-Off to Meet-in-the-Middle Attack

Jiali Choy
Khoongming Khoo
Chuan-Wen Loe
Search ePrint
Search Google
Abstract: In this paper, we present several new attacks on multiple encryption block ciphers based on the meet-in-the-middle attack. In the first attack (GDD-MTM), we guess a certain number of secret key bits and apply the meet-in-the-middle attack on multiple ciphertexts. The second attack (TMTO-MTM) is derived from applying the time-memory trade-off attack to the meet-in-the-middle attack on a single ciphertext. We may also use rainbow chains in the table construction to get the Rainbow-MTM attack. The fourth attack (BS-MTM) is defined by combining the time-memory-data trade-off attack proposed by Biryukov and Shamir to the meet-in-the-middle attack on multiple ciphertexts. Lastly, for the final attack (TMD-MTM), we apply the TMTO-Data curve, which demonstrates the general methodology for multiple data trade-offs, to the meet-in-the-middle attack. GDD-MTM requires no pre-processing, but the attack complexity is high while memory requirement is low. In the last four attacks, pre-processing is required but we can achieve lower (faster) online attack complexity at the expense of more memory in comparison with the GDD-MTM attack. To illustrate how the attacks may be used, we applied them in the cryptanalysis of triple DES. In particular, for the BS-MTM attack, we managed to achieve pre-computation and data complexity which are much lower while maintaining almost the same memory and online attack complexity, as compared to a time-memory-data trade-off attack by Biryukov et al. at SAC 2005. In all, our new methodologies offer viable alternatives and provide more flexibility in achieving time-memory-data trade-offs.
  title={Applying Time-Memory-Data Trade-Off to Meet-in-the-Middle Attack},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / block cipher, meet-in-the-middle, time-memory-data trade-off, triple DES},
  note={ICICS 2008, Springer, LNCS 5308, pp. 157-173 14253 received 8 Jan 2009},
  author={Jiali Choy and Khoongming Khoo and Chuan-Wen Loe},