# Would this method deliver a perfectly non-malleable encryption for at least two blocks? [closed]

Disclaimer: the algorithms I present here (and in other messages) are used as a hands-on way to learn about developing crypto algorithms, (and might also be of interest for other curious people), not for practical use (at least not after dozens of iterations and peer-review). I understand some people vote down not just because it seems unproved and speculative, and possibly flawed, but also perhaps because I'm not necessarily presenting it this way. This is just a manner of speech. Most of this *is* probably flawed, but that's the whole point here!

Say I’m using a 128 bit block cipher and would like to encrypt a 256 bit input that would be divided to two blocks, however I wish that every bit changed in the ciphertext would completely corrupt both plaintext blocks when decrypted.

Consider the following simple solution:

Version 1 - two blocks only (very flawed - kept for historical reference)

Encryption:

1. XOR the first plaintext block with the second one and store the result in place of the first ciphertext block.
2. Encrypt the two blocks with PCBC mode, meaning both the first block’s plaintext and ciphertext are XORed with the second block’s plaintext before encrypting.

Decryption:

1. Decrypt the two ciphertext blocks with PCBC mode.
2. XOR the first plaintext block with the second and store the result in place of the first.

Will this method deliver true non-malleability?

What about an extended version with more than two blocks? - in which during encryption, the additional processing simply goes from the last block backwards, XORs with the subsequent block and stores the result in place (the processing during decryption is also simple, i think). I read though that with PCBC "if two adjacent ciphertext blocks are exchanged, this does not affect the decryption of subsequent blocks." so I'm not sure it would deliver its promise in this case.

Version 2 - two blocks only (reformulated to overcome issues pointed out by @poncho but still flawed - kept for historical reference).

Encryption:

1. XOR the first plaintext block with the IV and the second plaintext block and store the result in place of the first plaintext block.
2. Encrypt the first plaintext block twice, with two different keys (where the second key may be derived from the first).
3. Output the first encryption of the first block as the first ciphertext block.
4. XOR the second plaintext block with the second encryption of the first block (note the second encryption is completely secret and will never be known).
5. Encrypt the XORed second block and output it.

Decryption:

1. Decrypt the first ciphertext block.
2. Re-encrypt the resulting plaintext of the first block with the secondary key (note the resulting plaintext is still XORed with the IV and original second plaintext block).
3. Decrypt the second ciphertext block.
4. XOR the resulting plaintext with the re-encryption of the first block and store it in place.
5. XOR the first block with the IV and decrypted second block and store it in place.

[TODO: consider if this could be extended to more than 2 blocks - the "pre-processing stage" is explained in the remarks of the first version of the algorithm]

NOTE: this still needs some work, it has a serious problem!

Assume an IV of 0, and both plaintext blocks of 0: corrupting on bit of the second ciphertext block would give out a completely psuedorandom second plaintext block, XOR it with the second encryption of the first decrypted block to get the final value of the second, now XORing with the first would yield the exact same value for the two blocks! So right now it does propagate errors backwards, but doesn't deliver true non-malleability. I'll try to see how to fix that tomorrow..

A possible sketch of a solution is to try to a create a dependency for the first block on a psuedorandom permutation of the second one rather than on its plain value. Hopefully that can be done without introducing an additional encryption step. We'll see about that..

Version 3 - two blocks only - (corrects the flaw in the second one, modified in-place to overcome flaws pointed out by @Ricky Demer - might be correct)

Encryption:

Derive intermediate blocks $I_1,I_2$:
$I_1 = P_1 \oplus E_{key_2}(IV \oplus P_2)$
$I_2 = P_2 \oplus E_{key_2}(IV \oplus I_1)$

Derive ciphertext blocks $C_1,C_2$:
$C_1 = E_{key_1}(I_1)$
$C_2 = E_{key_1}(I_2)$

Decryption:

Derive intermediate blocks $I_1,I_2$:
$I_1 = D_{key_1}(C_1)$
$I_2 = D_{key_1}(C_2)$

Derive plaintext blocks $P_1,P_2$:
$P_2 = I_2 \oplus E_{key_2}(IV \oplus I_1)$
$P_1 = I_1 \oplus E_{key_2}(IV \oplus P_2)$

An initial attempt for handling the general case for $n$ blocks (based on the same technique as the previous one - but flawed for $n>2$)

Encryption:

For every plaintext block $P_k, k \leq n$

Derive an intermediate block:
$I_k = P_k \oplus E_{key_2}(IV \oplus I_1 \oplus I_2 \oplus ... \oplus I_{k-1} \oplus P_{k+1})$
(where the last block would be $I_n = P_n \oplus E_{key_2}(IV \oplus I_1 \oplus I_2 \oplus ... \oplus I_{n-1})$)

Encrypt the intermediate block:
$C_k = E_{key_1}(I_k)$

Decryption:

Go forward and decrypt all the intermediate blocks with the first key:

For every ciphertext block $C_k, k \leq n$
$I_k = D_{key_1}(C_k)$

Now start at $n$ and go backwards to derive the plaintext blocks:

Derive the last plaintext block:
$P_n = I_n \oplus E_{key_2}(IV \oplus I_1 \oplus I_2 \oplus ... \oplus I_{n-1})$
For every intermediate block $I_k, k < n$:
$P_k = I_k \oplus E_{key_2}(IV \oplus I_1 \oplus I_2 \oplus ... \oplus I_{k-1} \oplus P_{k+1})$

Note: This is vulnerable to block-exchanging attacks, since during decryption the intermediate blocks are XORed before encryption, and the XOR operation is commutative. I'm considering different solutions:

• A simple but impractical solution would be to use a different key for each block (i.e. one key per index).

• A faster one would be to XOR the current intermediate block with a hash of all the previous ones before encrypting it to the ciphertext, i.e. $C_k = E_{key_1}(I_k \oplus H(I_1..I_{k-1}))$ and reverse the operation during decryption. Since the intermediate blocks are in essence secret, encrypted, psuedo-random data, the hash used probably doesn't need to be cryptographic (e.g. perhaps CRC32/64 could suffice) and could be calculated incrementally, giving a relatively small impact on performance.

• An even more interesting (but speculative and possibly flawed) solution is not to use decryption at all but to use the block cipher in something akin to counter mode with a different nonce for each block for the outward encryption, where the nonce would be the XOR of all the previously decrypted blocks. The decryption of the ciphertext would be something like $I_k = C_k \oplus E_{key_1}(IV \oplus I_1 \oplus I_2 \oplus ... \oplus I_{k-1})$. This may actually imply a total reformulation and simplification of the whole algorithm.

Version 4: (A new approach, completely reformulated to prevent block exchange attacks. In development - might be flawed at its current state)

Note: for convenience, the IV is considered to be the 0th intermediate block, i.e. $I_0 = IV$

Encryption:

For all non-final plaintext blocks $P_k, 1 \le k < n$

Derive a non-final intermediate block $I_k$:
$I_k = P_k \oplus E(I_{k-1} \oplus P_{k+1} \oplus E(I_0))$
Derive a non-final ciphertext block $C_k$:
$C_k = I_k \oplus E(I_{k-1})$

For the final plaintext block $P_n$:

Derive a final intermediate block $I_n$:
$I_n = P_n \oplus E(I_{n-1})$
Derive a final ciphertext block $C_n$:
$C_n = E(I_n)$

Decryption:

Iterate forward to derive intermediate blocks:

Derive all non-final intermediate blocks $I_k, 1 \le k < n$:
$I_k = C_k \oplus E(I_{k-1})$
Derive the final intermediate block $I_n$:
$I_n = D(C_n)$

Iterate backwards to derive plaintext blocks:

Derive the final plaintext block $P_n$:
$P_n = I_n \oplus E(I_{n-1})$
Derive all non-final plaintext blocks $P_k, 1 \le k < n$:
$P_k = I_k \oplus E(I_{k-1} \oplus P_{k+1} \oplus E(I_0))$

The approach here is a bit more subtle. The outer encryption XORs the current intermediate block with the encryption of the previous one. This means that during the forward iterating part of the decryption process, the first corrupted ciphertext block would actually render the underlying intermediate block malleable, since changing one bit of its corresponding ciphertext block would only change one bit of it. The next ones would be randomly corrupted though, since they depend on an encryption of the previous ones. This is not a real issue though, since during the backwards stage it would be corrupted again, this time randomly since the next plaintext block would not be the expected one.

(There are currently some minor issues with the similarity of the inner and outer encryption, especially for the cases where the plaintext is 0. I'm looking for ways to get around that [without using two different keys]. The current solution is to XOR the inner encryption arguments with the constant value $E(I_0)$ as a secret random constant (per IV) to avoid situations where both the inner and outer will yield the same result and cancel each other - this doesn't require an additional encryption operation since it is needed anyway by the outer encryption. I'm also considering adding a counter if that would prove necessary)

The following diagram describes the encryption process (For $n=3$. The two layers have been separated for clarity, but it should be understood that the whole process occurs in one forward pass): This one describes the two-stage decryption process (also for $n=3$). NOTE: this is a work in progress, and might contain severe or careless mistakes.. It is very preliminary and there is still much to analyze - the scrutiny of the community is needed and strongly appreciated.

In case this algorithm does, at some point, evolve to a correct algorithm (though in the special case of $n \le 2$ it might already be at its current state), it would be published under CC-BY.

• It looks like your third version requires 4 encryptions per block, 2 with each key. $\;$ – user991 May 21 '15 at 8:39
• @RickyDemer Since there are a total of two blocks involved here so I think it actually might be two per block (my assertion of 3 was probably incorrect). Anyway I'm considering how to completely reformulate it again, I think it could be made simpler. Perhaps I need to start treating the IV as the "previous" block on the chain, as this could be extended further to more than two blocks. – Anon2000 May 21 '15 at 8:57
• You should also note that if 128 is large, then there is a simple&standard way to do the no-ciphertext-expansion version of what you're trying for, although it's slightly less efficient than your third version. $\;$ – user991 May 21 '15 at 9:26
• @RickyDemer: I would definitely look at other algorithms but first I want to finish this one. – Anon2000 May 21 '15 at 10:06
• I'm voting to close this question because Crypto.SE is not the place to develop a new cryptographic algorithm. – cpast May 24 '15 at 16:28

Will this method deliver true non-malleability?

No. If we set the ciphertext to the value $(B, B)$, then the decrypted plaintext will have the second block as $B$ (assuming that the PCBC mode uses an implicit plaintext/ciphertext IV of 0; if it's two known constants, it's easy to adjust for that).

Even if we ignore this, it also fails to make sure that any change in a ciphertext bit modifies each plaintext bit with probability $\approx 0.5$; if you modify bit $i$ in the first ciphertext block, that will modify bit $i$ in the first plaintext block (with probability 1), and not any other bit in that first plaintext block.

• Thanks, I admit I haven't really figured out your answer at all but first I must ask.. What it you simply rejected equivalent blocks during decryption? (and in general for cases with non-zero IV simply rejected those particular edge cases) and say, used another, derived, key if this extremely rare outcome happened during encryption? – Anon2000 May 20 '15 at 15:49
• @Anon2000: how in the world would you be able to decrypt with your suggestion? If the decryptor got a ciphertext $(A,B)$, how does he guess whether to use the normal method, or whether he should use the derived key? As for figuring out the answer, well, that's straightforward; start with a ciphertext with two identical blocks, and step through the decrypt process – poncho May 20 '15 at 16:10
• Well, I guess with a more constructive approach, I could try to work out the problems (thanks for the feedback!) but I must ask first: Does a non-malleable encryption for more than a single block been mathematically proven impossible? (so I can rest assured this would be fruitless and go for a vacation? :) ) or there exists the possibility something would actually come out of this? (I'm only doing this for fun and learning I guess..) – Anon2000 May 20 '15 at 16:40
• Choose random nonce n, set the IV for CBC mode as HMAC(n, m), where m is the entire message, including the nonce and padding. – Steve Peltz May 20 '15 at 18:31
• @StevePeltz: how would you decrypt? In any case, I suspect Anon2000 is looking for a mode that doesn't do any ciphertext expansion – poncho May 20 '15 at 18:33

Let $H(m)$ be any strong hash function. Since you want to use encryption only, we'll specify that $H(m)$ = $E_{key}(m)$ where $E$ is a 128-bit block cipher. We're trying to create an encryption mode that will cause any change to the ciphertext to propagate over all blocks of the plaintext.

Strategy is to do two passes over the message, first forwards, then backwards, using the hashing function to diffuse any changes over the entire message. Any change to the plaintext (or IV) will change all bits in the ciphertext, any change to the ciphertext (including transmitted IV) will change all bits in the plaintext.

$n$ is the number of blocks in the message.

Encrypt
$I_0=IV$
$I_k=P_k \oplus H(I_{k−1})$ (for $0 \lt k \le n$)
$J_n=I_n$
$J_k=I_k \oplus H(I_{k+1})$ (for $0 \le k \lt n$)
$C_k=E_{key}(J_k)$ (for $0 \le k \le n$, $C_0$ is the transmitted IV)

Decrypt
$J_k = D_{key}(C_k)$ (for $0 \le k \le n$, $C_0$ is the transmitted IV)
$I_n = J_n$
$I_k = J_k \oplus H(I_{k+1})$ (for $0 \le k \lt n$)
$P_k = I_k \oplus H(I_{k-1})$ (for $0 \lt k \le n$)

The IV is discarded at the end of decryption. If semantic security isn't needed, set $I_0 = 0$ and don't calculate $J_0$ or $C_0$.

Alternatively, if you set $I_0$ to a constant, or a hash of the entire message, do the rest of the processing normally, then $C_0$ will function as a MAC (verify $I_0$ is the correct value).

If using that form, you can still get semantic security by appending a nonce to the message (perhaps the last 64 bits of the last block, with any padding occurring before the nonce to avoid a padding attack).

When using $H = E_{key}$, the first pass is using the cipher in CFB mode. Since both passes are keyed, not just hashes, you should be able to skip the third encryption.

• Looks quite straightforward, and that's good because it makes it easy to reason about it. Though I've spent a lot on trying to limit my own approach to only two expensive operations per block. Surprisingly, your idea of iterating backwards during encryption as well didn't occur to me though (even on the previous drafts), probably since I already have a (hopefully correct) solution with only 2 operations per block (which can even be streamed, since it only iterates forward). My solution in the comments required one encrypt, one crypto hash and one fast hash, but may not be up to crypto standard – Anon2000 May 23 '15 at 22:42
• $I_0 = H(IV \oplus Key)$ would be cheap and help protect against known- and chosen-plaintext attacks (though known-plaintext would be hard, it would make it almost impossible, for chosen-plaintext, that would be important, as the plaintext could be set to allow blocks to be swapped.) – Anon2000 May 24 '15 at 0:04
• Not sure how that's better than $H(IV)$ or just $I_0 = IV$, especially if $H = E_{key}$. I'm not sure why I specified $I_0 = H(IV)$ instead of just $I_0 = IV$, I'll change that in the text. – Steve Peltz May 24 '15 at 0:40
• @Anon2000 I added a note that if H is an encryption function, you should be able to skip the third encryption. – Steve Peltz May 24 '15 at 3:13
• Say $H$ is an encryption function and the encryption step is skipped, and there is only one plaintext block then $C_1 = P_1 \oplus E(IV)$ - in this case a one bit change in $C_1$ would lead to one bit change in $P_1$. That's the reason I used direct encryption on the last block and on the inner ones XORed the previous intermediate with the next plaintext block before the inner encryption. So as I described in the comments, the first intermediate block is malleable on the the forward pass, but then it gets randomly corrupted on the backwards one (not 100% this is an ultra-precise explanation). – Anon2000 May 24 '15 at 8:37

An alternative solution using one encryption, one cryptographic hash and one (possibly fast) non-cryptographic pseudorandom number generator operation per block.

Encryption:

1. Take the last plaintext block, and use its value (or some part of it), to seed a (possibly non-cryptographic) random number generator (note it could be XORed with the key for added security, so it would be impossible to guess).
2. XOR all non-final plaintext blocks with the output of the RNG.
3. Encrypt all plaintext blocks except the last in CBC mode (or some other mode that would work..).
4. Use a crypto-hash to calculate $H(Key \oplus IV || C_1 || C_2 || .. || C_{n-1})$ (could use something even more secure like an HMAC, but I gave this as an example)
5. XOR the hash with the last plaintext block before encryption and encrypt it (not required to use CBC mode here).

Decryption:

1. Calculate $H(Key \oplus IV || C_1 || C_2 || .. || C_{n-1})$
2. Decrypt the ciphertext.
3. Decrypt the last block and XOR it with the calculated hash.
4. Seed the resulting value to the RNG.
5. XOR all non-final blocks with the output of the RNG.

Required RNG properties:

For this to work some properties of the RNG should be ensured (in general, at least these are what I can think of right now):

1. Given two different seeds (one guaranteed to be pseudo-random) it produces a two different pseudorandom sequences of values, that are highly unlikely to contain sub-sequences of each other.
2. Given the output with a given seed, the probability of having a result at position k that's equal the one with given with a different (but psuedorandom) seed is 1/max value of the RNG (assume the result is integer and the min value is zero).

A nice property of this is that if a MAC is calculated anyway on the chiphertext, this could be used as a relatively cheap addition to make the message non-malleable as well. I'm not sure how much benefit this would give in practice if a MAC is already transmitted with the message, but it's interesting to know it can be done relatively cheaply (if this proves to be secure of course).

An attempt at improvement of the previous algorithm to use only one encryption and one non-crypto RNG operation (i.e. without a hash function):

Encryption:

1. Take the last plaintext block, and use its value (or some part of it), to seed a random number generator (note it could be XORed with the key for added security, so it would be impossible to guess).
2. XOR all non-final plaintext blocks with the output of the RNG.
3. Encrypt all non-final plaintext blocks in the following way (assuming $C_0 = IV$ and $P_0 = 0$):
$C_k = P_k \oplus E(P_{k-1})$
4. Encrypt the final block as follows:
$C_n = E(P_n \oplus P_{n-1})$

Decryption:

1. Decrypt all non-final blocks:
$P_k = C_k \oplus E(P_{k-1})$
2. Decrypt the final block as follows:
$P_n = D(C_k) \oplus P_{n-1}$
3. Use the last plaintext block to seed the RNG
4. XOR all non-final blocks with the RNG output.

(note: for a weaker RNG maybe $C_n = E(P_n \oplus E(P_{n-1}))$ would have better guarantees on the randomness of the seed)

This was hastily written so I hope this is correct and secure (if not it may be possible to fix it without making it significantly slower), but still need to look into it (haven't deeply considered block exchange attacks, for example). If it is correct it may be faster than my original solution.

Another thing: a nice property of non-malleable encryption, is of course, it can easily be used to create a MAC - just set the last plaintext block to an expected value such as a zero block or some other constant (probably not zeroes in this case as it wouldn't be a good seed to the RNG, perhaps using the key would be an interesting alternative), so this might be a cheap, fast way to both render the massage non-malleable and add a MAC to it (of course, assuming it's correct and secure).

Note: if this works then the type of encryption mode used here could be used a general, fast way to both encrypt and MAC and the same time (?!!) - without the RNG, i mean?. That seems unreasonable.. I guess I have to analyze this further to verify it's not flawed in some way..

Update: I posted a separate question to try to evaluate and scrutinize this method of authenticated encryption, independently of the way it's being used here to achieve non-malleability.