# How to propagate error in variable-sized message?

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.

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.)

I'm leaning towards this solution:

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

• FFX mode works for short messages, unfortunately it's pretty complicated. For longer messages you could use EME mode (encipher-mask-encipher). That's quite a lot of complexity (and still weaker security), just to save a few bytes for IV and MAC. – CodesInChaos Sep 11 '15 at 16:31
• Actually, if performance isn't an issue, FFX works for long messages too. – poncho Sep 11 '15 at 16:33
• For reused stream cipher keystreams, the solution you're leaning towards would fall to a single known plaintext. ​ If "the ciphertext is the same length as the plaintext", then your system wouldn't be able to avoid reusing the stream cipher keystream. ​ ​ ​ ​ – user991 Sep 11 '15 at 21:17
• @RickyDemer: Not a problem - the keystream is different each time because there is a different secret key per message. I didn't mention it, but this crypto problem is embedded in a larger system which has supplies more data and verification capabilities. – Nayuki Sep 11 '15 at 21:53
• Even with that, if the adversary can perform the all-or-nothing transforms, then your system can't provide garbling, since anyone who knows the plaintext can just xor the ciphertext with [[the AONT of that plaintext] xor [the AONT of what they want to make an encryption of]]. ​ Does your larger system also let you use an AONT which the adversary can't perform? ​ ​ ​ ​ – user991 Sep 11 '15 at 22:11

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.

• Thanks for your informative answer. I have one main concern - it doesn't address the fact that many messages will be less than a block long. – Nayuki Sep 11 '15 at 19:40
• I have a few comments as well - the source code for the to-be-designed algorithm will become public, so no "security by obscurity" is permitted. This also means that EME and patents are a no-go either. And finally, IIRC PCBC is still malleable because if you flip the same bit position on two ciphertext blocks, the decryption error will be healed thereafter, right? (Thus prefering something like IGE instead.) – Nayuki Sep 11 '15 at 19:41
• @NayukiMinase The issue of the message length should be solvable by standard padding mechanisms like PKCS#7. And you seem to be right about that PCBC thing. And please note: None of the proposed methods is security by obscurity, EME has a security proof, the AONTs have security proofs (at least some) meaning you can only recover the correct original message if you're given the correct cipher text and XTS is widely believed to be secure (and may also have some proof I don't know). – SEJPM Sep 11 '15 at 19:56
• Well, what I mean by "security by obscurity" is a warning that any custom scheme you or I might propose will be subject to public scrutiny. I'm not criticizing any existing published schemes out there. It looks like PCBC is vulnerable to block swapping. Now I'm leaning towards an algorithm of AONT preprocessing + stream cipher. – Nayuki Sep 11 '15 at 20:52
• I believe the patent for EME2 has been withdrawn. – forest May 8 '19 at 6:41

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

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.

• Sorry, I have trouble understanding what you're trying to say... The formatting of your text isn't helping. – Nayuki Sep 11 '15 at 20:48
• This is a screenshot of my answer. ​ Is it rendering differently for you? ​ ​ ​ ​ – user991 Sep 11 '15 at 20:56
• It renders the same for me. I guess it's the extra spaces and the lack of list bullet points that made me think something was weird. – Nayuki Sep 11 '15 at 20:59
• FYI, this is how your post looks to me. Not that it's much worse, but you really need to open your mind to the fact that your visual formatting does not look the same for everyone. You should use normal spaces and line breaks, that would make your posts much more readable. – Gilles 'SO- stop being evil' Sep 11 '15 at 22:41