Is error propagation desired in modes of operation

Question

I'm taking a very simple class on cryptography. The class is not mathematical is just the very basics. We learned about modes of operations recently (such as CBC and CTR), one of the things I learned was about error propagation. I just don't quiet understand if this is a desired effect or not. Sorry for such a simple question, but unfortunately my class doesn't have textbooks, it's just slides, and when I have questions is difficult to look for answers. Thank you.

Answer 1

No, it's not desired, it's a matter of knowing just how much error propagation is there for your chosen mode so you understand which blocks have been decrypted in error, and which haven't.

Answer 2

It is neither desirable nor undesirable on its own. Error propagation is not relevant to any modern cryptography. The concept is a relic of an archaic school of crypto engineering that has been left to the junk heap of the previous century, but not all textbooks or instructors with job requirements to teach courses called Cryptography 101 have kept up with the state of the art.

What is relevant is authentication. If there is any chance that an adversary might have the power to interfere with the channel between two peers—whether by intercepting packets on the wire or by compromising the server where messages or stored or what—then the peers should have a system for authenticating messages so that any changes an adversary makes have negligible chance of going undetected by the recipient.

If the peers already share a secret key that they could use with a block cipher, then, instead of picking a block cipher and a mode of operation as last century's school of engineering prescribes, they should pick an authenticated encryption scheme. This is a gizmo that takes a key, a message sequence number, and an arbitrary bit string as a message, and turns it into a ciphertext which the recipient can use the same key to detect modifications in and, if unmodified, turn back into the message.

One example of an authenticated encryption scheme is NaCl/libsodium crypto_secretbox_xsalsa20poly1305. Another example is AES256-GCM. AES256-GCM happens to be built out of the block cipher AES-256, but this is an implementation detail—you should think of it as picking AES256-GCM as a unit, not picking AES and then a 256-bit key and then GCM as a mode of operation. crypto_secretbox_xsalsa20poly1305 is not built out of a block cipher at all, and has some advantages over AES256-GCM—faster and safer in software, larger message sequence numbers so you can safely randomize them.

Answer 3

No, generally we don't care about error propagation anymore.

First of all, error propagation is of use if error handling, e.g. due to transmission errors, needs to be taken care of at the layer that performs the cryptography. Nowadays we try and separate that kind of functionality. For instance, TLS is implemented on top of TCP/IP which already provides a reliable stream. Error correction is already applied as low as the Physical layer of the OSI model.

Second, limiting error propagation will only ensure you that more of the plaintext will be left unscathed. It is however debatable if this can give any security advantages. In the end you will still not know which bits of the original message have been altered or not. It is near impossible to build a secure scheme on top of that. You could of course use an error correcting scheme to correct that, but as indicated, it is probably better to do that before decryption.

Thirdly, if we consider an active adversary - an adversary that can alter, drop and / or retransmit ciphertext - then limiting error propagation can have serious negative side effects. For instance, if you use CTR mode then an adversary can flip any bit of plaintext by flipping a bit of the ciphertext at the same position. CTR has excellent properties with regards to error propagation when bits are altered (not inserted or removed) but it is extremely vulnerable to attack because of that.

In the end we're only interested in receiving messages that are considered confidential, integrity protected and authentic for most of our use cases. For that reason we try and use encrypt-then-MAC or authenticated encryption. This performs the exact opposite of a mode that provides limited error propagation: if a single bit of the message is changed then the entire message is discarded and an error is generated. Mathematically speaking, the output of decryption is often denoted $\bot$ in that case.

---

Notes:

• Error propagation of course doesn't mean that every bit of affected plaintext is changed. Generally the bit of plaintext is flipped with a chance of 100% or 50%, depending on how the plaintext is being generated.
• There is a mode called Bi-IGE where each bit of plaintext is flipped with a chance of 50% if even a single bit of ciphertext is changed, i.e. the plaintext is randomized if the ciphertext is altered. Although this mode has full error propagation, it isn't the same as authenticated encryption. As there is no detection, it is impossible to tell if the entire plaintext was altered or not, i.e. it doesn't provide integrity protection nor message authentication by itself.
• Probably the only reason to learn the specifics of error propagation in a course is that it requires you to take a deeper look into the way a mode of operation works. The purpose of putting error propagation in a course is more likely to understand the mode of operation better rather then to understand about error propagation itself.