Decrypting ciphertext that is missing a block

In the AES encryption, suppose that the key is known. The ciphertext is also known except for a block of the same size as the key. For example, the adversary knows $$k, c_0, c_1, \dots, c_{n - 1}$$; They do not know the final ciphertext $$c_n$$.

In the worst case scenario for the attacker, how hard is it for them to successfully decrypt the ciphertext, compared with the case when the key is unknown and the ciphertext is fully known?

• Please be more specific. For AES-128 the attacker knows nothing if there is only one block encrypted. – kelalaka Dec 8 '18 at 10:12
• It completely depends on the mode of operation and the set of possible plaintext messages. However, we can conclude that, by definition, decryption without the key will be at least as hard (give or take a bit or 2) and very likely much harder. Voted to close as the mode of operation and information about the plaintext is missing in the question. – Maarten - reinstate Monica Dec 8 '18 at 11:27
• I edited your question to attempt to clarify what you're asking - please ensure I did not accidentally change the meaning of your question. – Ella Rose Dec 14 '18 at 18:05
• Note that the key size and block size of a block cipher may differ as well. The key size doesn't have to do as much with the block size as most people assume. – Maarten - reinstate Monica Dec 15 '18 at 1:22

The details depend on the mode of operation, but for all the commonly used modes, most of the message will still be fully decryptable without any guesswork even if one block of ciphertext is missing.

For the (insecure!) ECB mode, and for the OFB and CTR modes, all you will lose is the plaintext for the missing block. Everything else can still be decrypted in the normal manner. This is because, in these modes, each block of ciphertext only affects the corresponding block of plaintext. (Indeed, for the OFB and CTR modes, each bit of ciphertext only affects the corresponding bit of plaintext.)

For CBC and CFB modes, you will lose the missing block and the next one. On the flip side, if you can guess the plaintext for either of these missing blocks, you can use that to reconstruct the other one. If your guess is wrong, the reconstruction will be essentially random gibberish. If the plaintext doesn't normally look completely random, that can provide a useful way to verify your guess.

(At least, this is true for CBC mode and for CFB with full-block feedback. For the rarely used CFB-8 and CFB-1 modes, you should still be able to easily reconstruct the next block if you can guess the plaintext for the missing one, but going the other way is slightly trickier. I believe it should be doable with a backtracking search, but it'll be a bit more complex than just the single XOR and AES decrypt operation needed for normal full-block CFB and CBC.)

The also rarely used PCBC ("propagating CBC") mode is the one notable exception here, since it was designed so that decrypting a block of ciphertext should require knowing the previous block of plaintext. Thus, with that mode, you will only be able to directly decrypt the message up to the last block before the missing one.

However, if you can guess the plaintext for any of the later blocks, then you can still decrypt the entire message, since you can in fact run the PCBC decryption process both forwards and backwards from the guessed block. In fact, even if you can't directly guess any of the later plaintext blocks, you can still obtain the bitwise XOR of every pair of plaintext blocks after the break in the ciphertext, which effectively reduces the PCBC mode encryption to something equivalent to a repeating key XOR cipher and allows you to apply all the well known techniques for breaking a many-time pad.

As for more modern authenticated encryption modes, those generally don't fare any better in this scenario. Indeed, most of them are built by combining one of the classical modes (usually CTR) with a message authentication code, and thus are just as easy to decrypt in this case as CTR mode itself. The authentication layer can even give the attacker a reliable way to verify their guess about the possible content of the missing block.

In any case, just like with the similar recent question about decrypting without the IV, the moral of the story is that modern encryption systems are designed with the assumption that the key is secret and everything else is public. If you break that assumption by making the key available to the attacker, then the system will probably not be secure any more, not even if you try to hide some of the assumed-to-be-public information instead.

• I don't see the term "error propagation" anywhere in the answer. Should it be added, or do you assume that completely missing blocks do not relate to error propagation? – Maarten - reinstate Monica Dec 15 '18 at 1:20
• @MaartenBodewes: Although it certainly is related to the effects of a missing ciphertext block on different modes of operation, I feel that error propagation in the context of block cipher modes (and cryptography in general) is mostly a red herring. Since I could answer this question perfectly well without mentioning it, I felt it was clearer not to explicitly introduce it as a concept. For further discussion, I guess I could just point people to this question, and specifically to your and Squeamish Ossifrage's answers there. – Ilmari Karonen Dec 15 '18 at 8:40

If the cipherext was generated in ECB mode, which is already insecure, the attacker could decrypt all except of course the missing block as each block stands on its own.

If instead it was generated in CBC mode the hacker could decrypt all except the missing block and the block after that.

Please be more specific with the question for a more precise answer.

Edit: based on my understanding of the edited question, the adversary is much worse off if the key is unavailable than if some of the cipherext is unavailable. My original answer holds for CBC, that the adversary with a key would recover with no effort all except the missing block and the one that follows it. But if you have another mode in mind please say which one.

• I edited the question to be more specific. I need to know how secure it could be (at best) if we just let the key out and keep one block of the encrypted data. – Alireza Dec 8 '18 at 12:17