Improved Time-Memory Trade-Offs with Multiple Data
Improved Time-Memory Trade-Offs with Multiple Data
复制标题
DOI：
10.1007/11693383_8
复制
发表时间：
2005-08
期刊：
影响因子：
--
通讯作者：
A. Biryukov;S. Mukhopadhyay;P. Sarkar
中科院分区：
文献类型：
--
作者：
A. Biryukov;S. Mukhopadhyay;P. Sarkar
本文从两个角度对时间/内存/数据权衡攻击进行了研究。我们证明了Hellman的时间-记忆权衡(TMTO)可以扩展到时间/记忆/密钥权衡。例如，如果攻击者可以使用不同密钥下的任意固定文本的243种加密，则128位密钥的AES只有85位安全性。这种攻击是通用的，并且比最近针对轮减少版本的AES的一些高复杂性选择的相关密钥攻击更实用。它们对任何使用80位或更短密钥的密码构成了实际威胁，而对于128位密钥密码则略微实用。我们发现，即使使用精心生成的密码，UNIX密码方案也容易受到实际的权衡攻击。我们的第二个贡献是提供了一个分析多个数据权衡的统一框架。巴贝奇-戈里奇(BG)公式和比尤科夫-沙米尔(BS)公式都可以作为该框架的特例得到。此外，我们确定了一类新的单表多数据权衡，无论是BG还是BS权衡都无法获得。最后对Oechslin的彩虹方法进行了分析，结果表明，对于多个数据，彩虹方法的TMTO曲线不如Hellman方法的TMTO曲线。
In this paper we study time/memory/data trade-off attacks from two points of view. We show that Time-Memory trade-off (TMTO) by Hellman may be extended to Time/Memory/Key trade-off. For example, AES with 128-bit key has only 85-bit security if 243encryptions of an arbitrary fixed text under different keys are available to the attacker. Such attacks are generic and are more practical than some recent high complexity chosen related-key attacks on round-reduced versions of AES. They constitute a practical threat for any cipher with 80-bit or shorter keys and are marginally practical for 128-bit key ciphers. We show that UNIX password scheme even with carefully generated passwords is vulnerable to practical trade-off attacks. Our second contribution is to present a unifying framework for the analysis of multiple data trade-offs. Both Babbage-Golic (BG) and Biryukov-Shamir (BS) formulas can be obtained as special cases of this framework. Moreover we identify a new class ofsingle tablemultiple data trade-offs which cannot be obtained either as BG or BS trade-off. Finally we consider the analysis of the rainbow method of Oechslin and show that for multiple data, the TMTO curve of the rainbow method is inferior to the TMTO curve of the Hellman method.