Plain versus Randomized Cascading-Based Key-Length Extension for Block Ciphers
Peter Gaži · 2013
Cascading-based constructions represent the predominant approach to the problem of key-length extension for block ciphers. Besides the plain cascade, existing works also consider its modification containing key-whitening steps between the invocations of the block cipher, called randomized cascade or XOR-cascade. We contribute to the understanding of the security of these two designs by giving the following attacks and security proofs, assuming an underlying ideal block cipher with key length κ and block length n: – For the plain cascade of odd (resp. even) length ℓ we present a generic attack requiring roughly ℓ−1 κ+ 2 ℓ+1 n ℓ−2 κ+ (resp. 2 ℓ n) queries, being a generalization of both the meet-in-the-middle attack on double encryption and the best known attack on triple cascade. ℓ−1 κ+ – For XOR-cascade of odd (resp. even) length ℓ we prove security up to 2 ℓ+1 n ℓ−2 κ+ (resp. 2 ℓ n) ℓ−1 κ+ queries and also an improved bound 2 ℓ n for the special case ℓ ∈ {3, 4} by relating the problem to 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 ℓ−1 κ+ with key-dependent permutations, we show a generic attack requiring roughly 2 ℓ n queries. Since XOR-cascades are sequential, this proves tightness of our above result for XOR-cascades of length ℓ ∈ {3, 4} as well as their optimal security within the class of sequential constructions. These results suggest that XOR-cascades achieve a better security/efficiency trade-off than plain cascades and should be preferred.