Paper 2014/016

Triple and Quadruple Encryption: Bridging the Gaps

Bart Mennink and Bart Preneel

Abstract

Triple encryption is a cascade of three block cipher evaluations with independent keys, in order to enlarge its key size. This design is proven secure up to approximately 2^{kappa+min{kappa/2,n/2}} queries (by Bellare and Rogaway, EUROCRYPT 2006, and Gaži and Maurer, ASIACRYPT 2009), where kappa denotes the key size and n the block length of the underlying block cipher. On the other hand, the best known attack requires about 2^{kappa+n/2} queries (by Lucks, FSE 1998, and Gaži, CRYPTO 2013). These bounds are non-tight for kappa <= n. In this work, we close this gap. By strengthening the best known attack as well as tightening the security bound, we prove that triple encryption is tightly secure up to 2^{kappa+min{kappa,n/2}} queries. Additionally, we prove that the same tight security bound holds for quadruple encryption (which consists of four sequentially evaluated block ciphers), and derive improved security and attack bounds for cascades consisting of five or more rounds. This work particularly solves the longstanding open problem of proving tight security of the well-known Triple-DES construction.