Plain versus Randomized Cascading-Based Key-Length Extension for Block Ciphers

Peter Gaži

Advances in Cryptology — CRYPTO 2013, Lecture Notes in Computer Science, Springer-Verlag, vol. 8042, pp. 551–570, Aug 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 $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, being a generalization of both the meet-in-the-middle attack on double encryption and the best known attack on triple cascade. - For 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}$ 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 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. These results suggest that XOR-cascades achieve a better security/efficiency trade-off than plain cascades and should be preferred.

BibTeX Citation

@inproceedings{Gazi13,
    author       = {Peter Gaži},
    title        = {Plain versus Randomized Cascading-Based Key-Length Extension for Block Ciphers},
    booktitle    = {Advances in Cryptology --- CRYPTO 2013},
    pages        = {551--570},
    series       = {Lecture Notes in Computer Science},
    volume       = {8042},
    year         = {2013},
    month        = {8},
    publisher    = {Springer-Verlag},
}