# What algorithm would give the shortest ciphertext for very short plaintexts?

I have to encrypt some very short messages (approx. 5 characters) and I would like the ciphertext to be as short as possible. I am currently using AES but the initialization vector (IV) is making my minimum cipher text be 32 bytes, even for plaintext of 1 byte.

Can I do better than 32 bytes?

-

For such short messages, you're not gaining much (if anything) from using a CBC, CFB, etc., that require an initialization vector (these modes of operation are to ensure against a block of output being repeated when a block of input is repeated). For your situation (input that's shorter than one block), using ECB shouldn't pose a major problem.

For a block cipher, the minimum output size in ECB mode will be one block. For AES, that'll be 16 bytes. For even smaller output, 3DES has a block size of only 8 bytes. To go smaller still, Rijndael (the algorithm that became AES) was originally designed to work with any block size that's a multiple of 32 bits, so you could use it with a 32-bit block size.[Oops -- it supports multiples of 32 bits, but no smaller than 128 bits.]

Using a stream cipher you can get output that's the same size as the input, but you need to use a different key for each message. This renders them unsuitable for most people/uses.

-
Rijndael supports block (and key) sizes in multiples of 32 bit, but only from 128 to 256. So, this will not give us a 32 bit block cipher. – Paŭlo Ebermann Jun 11 '12 at 16:15
What about AES with a fixed IV? – JoelFan Jun 11 '12 at 16:27
@JoelFan: A fixed IV defeats the purpose of having an IV at all. To be useful, each IV must be unique. – Jerry Coffin Jun 11 '12 at 16:31

There is a technique called "format preserving encryption", which could be called an "arbitrary-size block cipher". This would allow to map your set of 5-character strings onto itself. Of course, this can't really get too secure, as it has still the limitations of ECB mode: encrypting the same string with the same key always gives the same ciphertext.

Your idea of using a mode with initialization vector helps, but bloats the message size, of course.

Since your effective message is sufficiently smaller than the block size, you could use a kind of "random padding" (similar to how it is used for asymmetric ciphers like RSA). For example, if your actual message is 5 bytes (and always this size, so we don't need to encode the size), you could add 8 random bytes and three zero bytes (as an integrity check), and pass the whole 16-byte-string to AES (as a block cipher, i.e. one-block-ECB).

On the decrypting side, you check that the last three decrypted bytes are zero, and then ignore the random bytes.

Now the ciphertext is different each time a different random value is used, independently of the actual plaintext, making it secure if the cipher is secure. (Of course, you should not use the same key for more than about $2^{32}$ messages.)

The protection against existential forgery is not that high, though, as three check bytes mean only 24 bit protection (in average 4 million tries necessary before a message is accepted). You can make this higher by using a smaller random part and bigger check part (meaning you should use the same key even less often).

If your protocol is serial, you can include a message number instead of a random value and check value, which also helps against replay attacks.

-
 +1 for your suggestion with 8 random bytes, 5 bytes payload and 3 zero bytes for integrity / authentication. – sellibitze Aug 16 '12 at 12:00