Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Is there's a way for someone (with the key) to decrypt a message encrypted with the cipher mode shown?

Cipher description

$$ P_0 = IV $$ $$ C_i = P_{i-1} \oplus E_K(P_i) \oplus P_i $$

share|improve this question
    
I believe he's asking if there's a way for someone (with the key) to decrypt a message encrypted with the above cipher mode. The answer, of course, is that there is no way to unambiguously rederive the plaintext; it is quite possible for two different plaintext message encrypt to the same ciphertext with the same IV (unless there's some nontrivial requirements on the "Encryption" blocks, such as $Encrypt(X) \oplus X$ be a permutation). –  poncho Dec 21 '11 at 18:05
1  
@poncho I see what you mean - I was probably a bit hasty on the close, sorry. Have edited your interpretation in, feel free to answer. –  Ninefingers Dec 21 '11 at 19:48

2 Answers 2

Ok, I will assume that:

  • The block you have labeled as "Encryption" is some sort of block cipher

  • You run this mode to transform the IV and the plaintext into a ciphertext

  • You are asking whether someone with the IV, the ciphertext and the block cipher key can recover the original plaintext.

Well, the quick answer is that they can't. This is true in two senses:

  • It is difficult to find a message that would encrypt to the given ciphertext. To recover (say) the first plaintext block, they would need to find a $P_1$ that solves the equation:

    $C_1 \oplus IV = E_K( P_1 ) \oplus P_1$

    However, for conventional block ciphers, there's no easy way to solve for such a $P_1$. Now, if the receiver knew the last plaintext block, he could decrypt all the rest. However, that isn't a standard assumption.

  • There might be multiple plaintext messages that encrypt into the same value. This is because, while $E_K( P_i )$ is a bijection (this is a standard assumption of block ciphers), there's no reason to suppose that $E_K( P_i ) \oplus P_i $ is (and, in fact, with high probability, it isn't).

To give a simple example of this last point, why don't see assume that we have a 1 byte block cipher with:

$E_k( 0x00 ) = 0x71$

$E_k( 0x17 ) = 0x66$

Then, if $IV = 0x19$, then:

The encryption of the single byte message $0x00$ will be the single byte $0x19 \oplus E_k( 0x00 ) \oplus 0x00 = 0x19 \oplus 0x71 \oplus 0x00 = 0x68$

The encryption of the single byte message $0x17$ will be the single byte $0x19 \oplus E_k( 0x17 ) \oplus 0x17 = 0x19 \oplus 0x66 \oplus 0x17 = 0x68$

Hence, in this case, if we get an encrypted message $0x68$, we have no idea if the original plaintext was $0x00$ or $0x17$

share|improve this answer
    
Actually, this is why $E_K(X) \oplus X$ is a construction often used in compression functions for hash functions. –  Paŭlo Ebermann Dec 21 '11 at 20:49

As poncho notes, knowing the last plaintext block (and the key, of course) allows all the other blocks to be decrypted. Also, given this knowledge, the "IV" is completely unnecessary for decryption, as is the first block of the ciphertext!

So, let's change the system a bit, adding the IV to the end of the plaintext rather than to the beginning. (That is, we append a random block to the end of the plaintext, and also include it in the plain in the encrypted message to allow decryption.) Now we have a system that can be decrypted, but it's kind of backwards compared to the usual block cipher modes, so let's flip it around like this: $$P_0 = IV$$ $$C_i = P_{i-1} \oplus E_K(P_{i-1}) \oplus P_i$$

This is exactly the same as the system you described, except mirrored horizontally, so that we feed the previous plaintext block through the block cipher instead of the next. Now we can decrypt the ciphertext like this (where $P_0 = IV$ as before): $$P_i = P_{i-1} \oplus E_K(P_{i-1}) \oplus C_i$$

Is this a good block cipher mode? I don't think so. In particular, it shares a major weakness with ECB mode, in that, since $C_i$ only depends on $P_i$ and $P_{i-1}$, identical pairs of adjacent plaintext blocks will yield identical ciphertext blocks. (The same holds for your original mode as well.) It could perhaps be secure if the encryption and decryption operations were swapped, so that we'd have: $$C_0 = IV$$ $$C_i = C_{i-1} \oplus E_K(C_{i-1}) \oplus P_i$$ $$P_i = C_{i-1} \oplus E_K(C_{i-1}) \oplus C_i$$

This would make it a variant of CFB mode, with $E_K(C_{i-1})$ replaced by $C_{i-1} \oplus E_K(C_{i-1})$. I suspect this construction should be secure, if the underlying block cipher is, although I can't really prove that off the top of my head. But we're getting pretty far from your original question here.

Just out of curiosity, where did you find this peculiar block cipher mode anyway?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.