International Association
for Cryptologic Research

The question of security of various efficient key-length

extending constructions for block ciphers in the ideal

cipher model has so far received considerable attention. The

security of triple encryption was investigated in

[Luc98,BR06], longer cascades were considered in [GM09] and

a construction with comparable security as triple encryption

requiring only 2 block cipher calls, denoted 2-XOR-cascade,

was proposed and analyzed in [GT12].

In this paper, we put the above results into perspective by

completing the picture of the investigated landscape in

various ways. We give the following attacks and security

lower bounds for constructions using a block cipher with key

length $k$ and block length $n$:

- For the plain cascade of odd (resp. even) length $l$ we

present a generic attack requiring roughly

$2^{k+\\frac{l-1}{l+1}n}$ (resp. $2^{k+\\frac{l-2}{l}n}$)

queries. This is a generalization of both the well-known

meet-in-the-middle attack on double encryption and the

attack on triple cascade given in [Luc98].

- For the general case of XOR-cascade of odd (resp. even)

length $l$ we prove security up to

$2^{k+\\frac{l-1}{l+1}n}$ (resp. $2^{k+\\frac{l-2}{l}n}$)

queries and also an improved bound $2^{k+\\frac{l-1}{l}n}$

for the special case $l\\in\\{3,4\\}$. This is achieved by

relating the problem to existing results in an independent

line of work on the security of key-alternating ciphers in

the random permutation model.

- Finally, for a natural class of sequential constructions

where block cipher encryptions are interleaved with

key-dependent permutations, we show a generic attack

requiring roughly $2^{k+\\frac{l-1}{l}n}$ queries. Since

XOR-cascades are sequential, this proves tightness of our

above result for XOR-cascades of length $l\\in\\{3,4\\}$ as

well as their optimal security within the class of

sequential constructions.