Paper 2004/128

Elastic Block Ciphers

Debra L. Cook, Moti Yung, and Angelos D. Keromytis


We introduce the new concept of elastic block ciphers, symmetric-key encryption algorithms that (1) for a variable-size input do not expand the plaintext (i.e., do not require plaintext padding) and (2) adjust their computational load proportionally to the size increase. Contrary to stream ciphers, elastic block ciphers maintain the diffusion property and non-synchronicity of traditional block ciphers. Elastic block ciphers are ideal (when combined with encryption modes) for applications where length-preserving encryption is most beneficial, such as protecting variable-length database fields or network packets. 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.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Cipher DesignVariable Length Block CipherElastic Block CiphersEncryption AlgorithmKey Recovey AttacksSecurity Proofs
Contact author(s)
dcook @ cs columbia edu
2004-07-06: revised
2004-06-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Debra L.  Cook and Moti Yung and Angelos D.  Keromytis},
      title = {Elastic Block Ciphers},
      howpublished = {Cryptology ePrint Archive, Paper 2004/128},
      year = {2004},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.