An Optimal Attack on Cryptosystems Using Pre/Post Whitening Keys
- 講者Orr Dunkelman 教授 (Faculty of Mathematics and Computer Science The Weizmann Institute of Science)
邀請人：楊柏因老師 - 時間2011-04-28 (Thu.) 10:30 ~ 12:00
- 地點本所新館一樓106演講廳
摘要
The idea of adding independent pre-whitening and post-whitening keys to block ciphers was first proposed by Ron Rivest in 1984, and was used in several designs, including the DESX extension of DES and in the Even-Mansour scheme. Several attacks on such schemes were published since then, but so far the best known upper and lower bounds on the additional security provided by the two $n$-bit whitening keys (assuming that the block cipher itself, which has an additional $k$-bit key, is perfectly secure) do not match.
In this work we introduce a new extended variant of the slide attack called slidex, and use it to obtain the first tight bound on this construction:
Given any number $D$ of known plaintexts, we can find the 2n-bit key (without any preprocessing) in time T satisfying the tradeoff curve $TD=2^{n}$. In addition, we show that there is no comparable lower bound on the amount of memory needed in such attacks, by developing a memoryless variant of our attack which can be applied with the same time complexity when $D=2^{n/2}$.