How to propagate error in variable-sized message?

Question

I want to design a scheme to encrypt a variable-length message with a secret key, to provide confidentiality. The message is a short human-readable text string with byte granularity, let's say under 300 bytes. I prefer that the ciphertext is the same length as the plaintext (avoid padding).

Along the way, I also want to support integrity-checking on a best-effort basis. Preferably, I want it so that if any bit of the ciphertext is changed, then the decrypted plaintext will look garbled. (The decrypted output will actually be read by a human, and no automated checking is needed.)

It is not acceptable to append a MAC or any kind of check code due to message size restrictions; valid decryption must be inferred from the garbling of the message itself. CPU time is not a problem as long as it's under 0.1 second. An inefficient but secure scheme is okay, but the scheme should be conceptually simple to describe/audit/implement.

The complicating factor is that the message may be shorter than a block (say 16 bytes, for the AES cipher), which means ciphertext stealing can't be used. (Right?)

---

I'm aware of these facts already:

• Using a stream cipher satisfies the variable-length property but makes the ciphertext very malleable; this is undesirable.
• Using a block cipher gives the "decryption garble" property desired.
• Using CBC mode instead of ECB will mask repeating patterns in the input.
• Ciphertext stealing (for ECB or CBC) makes it possible to not increase the message length - but only if the message is at least one block long.
• It's possible to use a keyed hash function / MAC for 3 or 4 rounds to design a custom Feistel network cipher.
• It might be possible to use a stream cipher and a bytewise adaptation of the Infinite Garble Extension (IGE) mode to achieve garble propagation.
• Designing "home-made" crypto not reviewed by experts is frowned upon and may have subtle and fatal errors.

But I don't know what else I need to know, and how to proceed from here. I can post more details on some of the proposed algorithms (such as IGE and Feistel) if needed.

---

Addendum:

Feistel network idea: (using Python pseudocode)

Let H(k, m) be a MAC (such as HMAC-SHA-512) with secret key k.
Let M be the message to be encrypted.
Let i = floor(M.length / 2).

Algorithm:
M[0 : i] ^= truncate(H(k, M[i : M.length]))  # left half XOR H(right half)
M[i : M.length] ^= truncate(H(k, M[0 : i]))  # right half XOR H(left half)
M[0 : i] ^= truncate(H(k, M[i : M.length]))  # Round 3 to achieve error propagation
M[i : M.length] ^= truncate(H(k, M[0 : i]))  # Round 4 due to recommendations

(If half the message length is less than the MAC/hash length then truncating is easy. But if it's longer then some kind of stretching, i.e. CSPRNG, is needed.)

---

Second addendum:

I'm leaning towards this solution:

preprocessed = all-or-nothing-transform(message)
ciphertext = preprocessed XOR (stream cipher keystream)

Answer 1

The scenario you're facing is well-known in cryptography. You can't afford expanding the message at all (maybe by some IV). So you can't get strong authentication but have to rely on what is called poor man's authentication, you rely on tampering causing random messages.

Please note that all of the following modes are somewhat block-based, meaning you'd have to use padding (like PKCS#7) to ensure correctness of the data and you have to actually check the padding to protect against POODLE style attacks.

The exact same scenario is given in the full-disk-encryption (FDE) scenario. This gives you four options, plus those added by other answers.

• XTS, the standard mode for full-disk encryption. It allows for two tweaks hiding potential patterns. You can use standard padding methods (PKCS#7) if you're not hitting block boundaries, this is the most standard solution but may not scramble enough as it only affects the current block.
• PCBC is a mode that propagates errors infinitely into the following decrypted plain texts. It accepts IVs and also hides patterns. This may not be preferable compared to the all-or-nothing transforms but may be the choice if they're too slow. And you may want to avoid this one if possible to not fall against the "same flip attack" although this would still mean that two blocks (32 bytes for AES) are scrambled.
• EME, a mode originally specifically designed for full-disk encryption and tackling the poor man's authentication best. It turns every block cipher with block size $n$ into a larger block cipher with block size $n^2$ and accepts tweaks to hide patterns and provide random-access. If you'd use AES this would mean you can encrypt up to 2048 ($=128^2/8$) bytes and make sure the whole block is scrambled if tampered. The main drawbacks are potential patents and the lower speed of requriring double the amount of block cipher calls and a finite field multiplication. EME may not be a good choice if patent-freeness is required.
• All or nothing transforms. You can use standard XTS or something like that, but apply an all-or-nothing transform on the plain text to make sure the receiver has the complete and correct set of all blocks. This is somewhat non-standard but looks like the best solution.

Answer 2

Let pair be an efficiently computable, efficiently-invertible pairing function.
For example, ​ ​ ​ pair(x,y) ​ = ​ prefixfree(x) || y ​ ​ ​ and
pair(x,y) ​ ​ ​ = ​ ​ ​ if ​ length(y) < length(x) ​ then ​ 1 || prefixfree(y) || x ​ else ​ 0 || prefixfree(x) || y
each define such functions.

Use format-preserving encryption, via ​ Enc(k,tweak,m) = FPEenc(PRF(k,pair(tweak,length(m))),m)
and ​ Dec(k,tweak,c) = FPEdec(PRF(k,pair(tweak,length(c))),c) .
I believe the FPE schemes that are the-best-known for some input lengths are

sort-by-pseudorandom-values
the sometimes-recurse shuffle
swap-or-not
possibly-generalized Feistel networks

in order from short inputs to long inputs. ​ The message-lengths and the number
of queries might be such that you can just do Feistel and ignore the other three.