7
$\begingroup$

I have this question in which I m struggling. I have read in many sites about encrypt-then-mac etc.

If the confidentiality for transmission is needed, discuss the feature for the order of encryption and encode by error correcting code (ECC), i.e., 1) encryption-then-encode, 2) encode-then-encryption.

Improve this question
$\endgroup$
2
9
$\begingroup$

With some modes you can encode then encrypt, specifically stream cipher modes (CTR, OFB). Bit errors during transmission translate to identical bit errors in the encoded plaintext, and error correction will work as intended.

However, with standard block cipher modes (ECB, CBC), the entire block is encrypted, and a 1 bit error in the ciphertext creates many bit changes to the decrypted block due to the avalanche effect. Depending on the type of correction used, this may be correctable, but it is generally better to apply the code to the ciphertext.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Even with stream ciphers you lose ability to recover from dropped bits/bytes, which some error correcting codes can deal with. (Self-synchronizing stream ciphers could help a bit there.) $\endgroup$ – otus Jun 16 '16 at 4:10
  • 1
    $\begingroup$ Missing term: error propagation, authentication tags should indeed also be taken into account, especially for transport mode security. $\endgroup$ – Maarten Bodewes♦ Jun 16 '16 at 21:42
4
$\begingroup$

The correct procedure is Compress $\to$ Encrypt $\to$ ECC $\to$ Transmit.

You would have no hope of error recovery if you were to apply error correcting information prior to encryption.

It is the design goal of a cipher to introduce bit flips with probability ${1}\over{2}$ and Shannon's noisy channel coding theorem tell us we cannot communicate at all if the transition probability of a binary symmetric channel is ${1}\over{2}$.

In his theory of communication, Shannon says

Equally “good” transmission would be obtained by dispensing with the channel entirely and flipping a coin at the receiving point.

If a single bit flip error occurred, by design of the cipher, it would spread to other bits and destroy any structure that the ECC had added to help detection and recovery.

Improve this answer
$\endgroup$
4
  • 2
    $\begingroup$ Actually, a goal of (most) ciphers is not to spread out changes to the ciphertext to other plaintext bits. As Ritchie points out, there are encryption methods that are malleable; that is, if you flip a bit of ciphertext, the modified plaintext also has that bit flipped; such a method would work with ECC (assuming, of course, that the errors you're correcting is individual bit flips, and you're not worried about bit flips in your MAC (you are using a MAC with your encryption, aren't you?)). That said, as you state, encryption and then encoding makes a lot more sense $\endgroup$ – poncho Jun 16 '16 at 18:20
  • $\begingroup$ @poncho Well you could argue that this property is a property of block ciphers. But then we would be discussing a single block encrypt, completely forgetting about the necessary mode of operation. Anyway, I agree what the answer should take the specific error propagation in of the mode of operation in mind. $\endgroup$ – Maarten Bodewes♦ Jun 16 '16 at 21:39
  • $\begingroup$ I disagree with the inclusion of compression in the recommended order, for reasons discussed in the linked questions. $\endgroup$ – otus Jun 17 '16 at 9:29
  • $\begingroup$ I agree with the answer and disagree with @otus. Compression should be done before encryption. "Ciphertexts tend to look like random strings and therefore compressing after encryption will not compress the data." - Dan Boneh $\endgroup$ – user1156544 May 2 '19 at 8:13
1
$\begingroup$

Another danger of error correction followed by is the following. If we follow Kerchoff's principle, the error correction method/code as well as the encryption method should be public. Thus the only unknown is the secret key, assuming a symmetric scheme.

Most error correction codes are linear and thus introduce dependencies between symbols that are input to the encryption mechanism. Thus you have a set of linear equations that the input symbols satisfy, which means that for certain input masks (assuming ECB mode, and a block cipher for simplicity) into the you have a linear equation that holds with probability $1.$

The adversary now only has to analyze only the output masks corresponding to those input masks, thus reducing the complexity of computing the relevant linear characteristics, which can make a difference for large Sboxes.

If a stream cipher was being used, then there are ready made parity check equations for the input, that can be used in cryptanalysis.

Even if the code is not linear (almost all good codes used in practice are, convolutional codes, LDPC codes, RS codes, RM codes) encoding still introduces predictable dependencies.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I do not believe message recovery is possible by exploiting ECC structure (see my own answer). If you model the cipher as a noisy communications channel, you will find very quickly that you cannot design an ECC to fight the error that it introduces. It seems cipher design applies the same principles used in ECC, but in an effort to minimize chance of message recovery, instead of maximize it. $\endgroup$ – user9070 Jun 17 '16 at 8:53
  • 1
    $\begingroup$ I'm probably missing something, but how can any transformation of the plaintext hurt if you are using secure (IND-CPA) encryption. $\endgroup$ – otus Jun 17 '16 at 9:32
  • $\begingroup$ @kodlu is daring to suggest that some ciphers are weak :) $\endgroup$ – user9070 Jun 17 '16 at 9:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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