Date:2012-08-06, 9:30am

Venue:Conference Hall 322, Science Building

Title: Improved Attacks on Multiple Encryption

Speaker: Prof. Adi Shamir

Abstract:Multiple encryption schemes use a basic cryptographic scheme k times with independent n-bit keys in order to enhance its security. Typical examples of such schemes are double-DES and triple-DES, whose keys are 2*56 and 3*56 bits long, respectively. The security of such schemes had been studied extensively over many years, but all the known attacks on them (which are guaranteed to succeed) require time T and memory M whose product is at least 2^{kn}. In this talk I will present the first attacks on multiple encryption which break this bound, such as an attack on k=7 consecutive encryptions which require time of T=2^{4n} and memory of M=2^n, whose product is only TM=2^{5n} instead of the expected TM=2^{7n}. These attacks use a new technique called Dissection, which can be used to solve many combinatorial search problems which are unrelated to cryptography (such as the knapsack problem) with an algorithm which is more efficient than the best previously known techniques.

This is joint work with Itai Dinur, Orr Dunkelman, and Nathan Keller, which was selected as the best paper at the forthcoming CRYPTO 2012 conference.