We present a general algorithm for converting a traditional block cipher, such as AES, to its elastic version, and analyze the security of the resulting cipher against key recovery attacks. Our approach allows us to ``stretch'' the supported block size of a block cipher up to twice the original length, while increasing the computational load proportionally to the expanded block size. Our approach does not allow us to use the original cipher as a ``black box'' (i.e., as an ideal cipher or a pseudorandom permutation as is used in constructing modes of encryption). Nevertheless, under some reasonable conditions on the cipher's structure and its key schedule, we reduce certain key recovery attacks of the elastic version to such attacks on the fixed-size block cipher. This schema and the security reduction enable us to capitalize on secure ciphers and their already established security properties in developing elastic designs. We note that we are not aware of previous ``reduction type'' proofs of security in the area of concrete (i.e., non ``black-box'') block cipher design. Our work puts forth the notion of elasticity in block cipher design.
Category / Keywords: secret-key cryptography / Cipher Design, Variable Length Block Cipher,Elastic Block Ciphers, Encryption Algorithm, Key Recovey Attacks,Security Proofs Date: received 30 May 2004, last revised 5 Jul 2004 Contact author: dcook at cs columbia edu Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Version: 20040706:003121 (All versions of this report) Short URL: ia.cr/2004/128 Discussion forum: Show discussion | Start new discussion