We introduce a new concept of elastic block ciphers, symmetric-key encryption algorithms that for a variable size input do not expand the plaintext, (i.e., do not require plaintext padding), while maintaining the diffusion property of traditional block ciphers and adjusting their computational load proportionally to the size increase. Elastic block ciphers are ideal for applications where length-preserving encryption is most beneficial, such as protecting variable-length database entries or network packets. We present a general algorithmic schema for converting a traditional block cipher, such as AES, to its elastic version, and analyze the security of the resulting cipher. 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 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 the security of the elastic version to that of 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 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 implementation of the elastic version of AES, which accepts blocks of all sizes in the range 128 to 255 bits, was measured to be almost twice as fast when encrypting plaintext that is only a few bits longer than a full block (A128 bits), when compared to traditional "pad and block-encrypt" approach.