# 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
Do not do this. Especially if you have a very small plaintext space, ECB performs poorly. Imagine using AES in ECB mode on messages with length 1 bit. Every message would be an encryption of $0$ or $1$. Finding out what is $E(0)$ and $E(1)$ is not that much guesswork any more. Especially with short messages, it is very important to have some form of randomization to hide the fact that the same message has been encrypted. – tylo Jun 23 '14 at 13:47

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
Alternatively, AES in counter mode also hides the ECB weakness. If you have some part of the message as verification means (something like 3 bytes zero at the end), it doesn't even matter if packages arrive slightly out of order, because multiple counter increments can be tested. – tylo Jun 23 '14 at 13:54
@tylo counter mode by itself doesn't provide any authentication, so an intercepting attacker who guesses the right plaintext can substitute an arbitrary different one. – Paŭlo Ebermann Jun 23 '14 at 18:47
Ah, you're right about counter mode offering no integrity any more. But it does avoid the weakness of ECB that the same plaintext is always transformed into the same ciphertext. But I guess, counter mode is after all a bad idea. – tylo Jun 23 '14 at 19:54

XOR cipher preserves bit length, but depending on the accepted cleartext alphabet will result in longer ciphertexts.

So if you have a 1 byte cleartext, XOR will result in a 1 byte ciphertext.

Edit: Yes well you asked if you can do better than 32 bytes for a 1 byte message, and if so which algorithm would give the shortest ;)

Technically you can encrypt 1 byte to a length of one byte but your options are limited, and the stream cipher (or 1 byte block cipher) will almost certainly use XOR somewhere in its schedule since its so cheap and its pretty effective if you use a large enough key.

-
However, this is extremely insecure... the key can be easily recovered by an attacker that knows the ciphertext for a single plaintext – JoelFan Jun 19 '14 at 20:02
It is also subject to frequency analysis which doesn't even require a plaintext / ciphertext pair. It seems equivalent to a Vernam cipher. – JoelFan Jun 19 '14 at 20:08