Question

) Suppose A,B are using the majority error-correcting code scheme F discussed in class. To review, if M is the plaintext bit-string A wants to get to B, A calculates F(M) to be the bit-string consisting of every bit of M repeated thrice. So, for example, if M = 011, F(M) will be 000111111. The idea is that F(M) is transmitted, and if there is a single bit error (so that a 1 gets switched to a 0 or a 0 gets switched to a 1), B will not only be able to detect that an error has taken place, but will be actually able to figure out what the error is and correct it. So, if on the above example, if the 6th bit gets flipped and what is transmitted is 000110111, B will follow the majority-rule and decode the 110 as 1 to recover the correct M = 011.

Now suppose this scheme is combined with encryption using DES as follows. A calculates C = EK(F(M) and transmits C. B first calculates F(M) = DK(C) and then recovers M from F(M).

Suppose there is a single bit error (so that a 1 gets switched to a 0 or a 0 gets switched to a 1) in transmission, and what B receives is C′ which differs from C in a single bit.

(a) Will B probably still be able to figure out that an error has taken place?

i. Give a YES/NO answer.

ii. Explain your answer i.e. if you said YES explain how you think B will find out whether an error has taken place, and if you said NO explain why you think B can’t detect the error.

(b) Will B probably still be able to recover the original message M?

i. Give a YES/NO answer.

ii. Explain your answer i.e. if you said YES explain how you think B will recover M from C, if you said NO explain why you think B will not be able to recover M.

Answer 1

1.(a) Will B probably still be able to figure out that an error has taken place?

i)Yes.

ii)B will still not be able to find out that the error has taken place,but error detection is possible by exploiting ECC structure. 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.We can use simple encode-decode technique to find out what the message was before encryption.

1.(b) Will B probably still be able to recover the original message M?

i)Yes

ii)

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.But still the message is recoverable.

The correct procedure is Compress →→ Encrypt →→ ECC →→ Transmit.

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