Error Detection/Correction Code-Then-Encrypt

Question

I've just studied about the error correction schemes and encryption.

First rule when using EDC/ECC is to first encrypt and then calculate them, and the major motivation we were told is that "EDC/ECC Then Encrypt causes KPA attacks on GSM protocols to be Ciphertext Only Attacks, because it adds much redundancy to the plaintext". source (slide #50)

However I couldn't find any example or explanation for that, so I'd appreciate any help regarding this.

Answer 1

The valid advice of adding an Error Detection or/and Correction Code after encryption rather than before has two unrelated justifications:

1. If the cipher is weak, adding redundancy to the plaintext (as EDC/ECC before encryption does) might allow attack. In particular, it is possible to test if a key is valid by checking if the redundancy in tentatively deciphered plaintext is valid (a refinement of that is used to break the GSM cipher in the question's reference). However, that consideration is not a concern for good modern ciphers, since these should be resistant to chosen-plaintext attack.
2. EDC/ECC is typically optimized to detect/correct errors affecting few bits of the transmitted message. If encryption is applied after EDC/ECC, and correspondingly decryption applied before EDC/ECC on the receiver side, then errors on the transmitted message tend to get amplified by decryption (depending on the cryptosystem, as detailed hereafter). When this happens, desirable EDC/ECC properties such as insurance of detecting/correcting any at-most-N-bit error in the transmitted message tend to be lost, or greatly reduced.
   • for stream ciphers, CTR mode, and OFB mode, only errors on setup parameters or the IV will get amplified, but the effect of any such error will ruin the whole decrypted message;
   • in ECB mode, a 1-bit error is amplified to potentially one block;
   • in CBC mode (resp. CFB mode), a 1-bit error is amplified to potentially one block, and 1 bit in the next (resp. previous) block;
   • other modes exist such that error is amplified to the message after the error, or to the whole message;
   • with authenticated modes, practically any error will prevent decryption.

Answer 2

First, if you are using ECC/Encryption, you can't use a cryptographic scheme that propagates the transmission errors (like block ciphers).

Second, redundant data was encrypted, therefore some dependencies that existed before are passed to the ciphertext (that's the problem).

Some works like http://www.eng.tau.ac.il/~yash/infosec-seminar/2007/CS-2006-07.pdf create a ciphertext only attack on GSM using the fact that the sequence is ECC/Encryption.

I hope that helps.