Institute of Information Science, Academia Sinica



Press Ctrl+P to print from browser


An Optimal Attack on Cryptosystems Using Pre/Post Whitening Keys

  • LecturerProf. Orr Dunkelman (Faculty of Mathematics and Computer Science The Weizmann Institute of Science)
    Host: Dr. Bo-Yin Yang
  • Time2011-04-28 (Thu.) 10:30 – 12:00
  • LocationAuditorium 106 at new IIS Building

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}$.