3
$\begingroup$

I have a noisy communications link between two points that occasionally deletes a byte.

By "self-synchronizing cryptosystem", I mean that the receiver attempting to recover the original plaintext will be mostly successful, with at most a dozen or so corrupted letters of plaintext corresponding to each missing ciphertext byte.

Are all such cryptosystems necessarily self-synchronizing stream ciphers?

In other words:

  • Cryptosystems that are some block cipher mode of operation:
  • Cryptosystems that are not some block cipher mode of operation
    • Do all such cryptosystems end up either being effectively a stream cipher, or are non-self-synchronizing, or both?

I realize this isn't a practical question -- in practice, we MAC the message as a whole, and if anything was changed, added, or deleted, we reject the entire message. (In practice, non-crypto networking techniques handle bit-alignment, byte-alignment, packet-alignment, etc. and then re-send or otherwise correct occasional missing bytes and assemble the complete message long before any crypto algorithms at the receiver ever see that message).

$\endgroup$
3
  • $\begingroup$ Does the noisy channel delete the bytes without you knowing or do you know where the dropped bytes should have been? In the former case self-synchronizing ciphers and many common error-correcting codes are useless. You need some kind of "guards" in the data stream that indicate position. And if you have those, you can encrypt the chunks basically however you like. $\endgroup$
    – otus
    Apr 6, 2016 at 10:44
  • $\begingroup$ @otus: These "self-synchronizing ciphers" you mention -- can you name even one that is not effectively a "self-synchronizing stream cipher"? I would be very interested in any such (non-stream) self-synchronizing cipher, even if it required me to know exactly where the dropped byte(s) should have been. On the other hand, perhaps no such cipher is possible? Either way, I look forward to learning something I didn't know before. $\endgroup$
    – David Cary
    Apr 6, 2016 at 15:11
  • $\begingroup$ Sorry, I meant to write "self-synchronizing stream ciphers". I don't really know the answer to your question. $\endgroup$
    – otus
    Apr 6, 2016 at 16:16

1 Answer 1

1
$\begingroup$

Your best bet is to use an error-correcting code to correct the errors on the ciphertext.

In general, accepting corrupted ciphertexts is a bad idea, because it can allow devastating chosen-ciphertext attacks and because unauthenticated encryption has caused major security holes in practice.

When proper authentication is in use (which should be always), any error will result in the entire message being rejected. There are two solutions:

  • Break the message into chunks, such that bad chunks can be detected and retransmitted.
  • Use error-correcting codes. These allow for errors to be corrected by introducing redundancy.

These can be combined.

$\endgroup$
1
  • $\begingroup$ It might help the person asking the question if you could expand a little bit on this… $\endgroup$
    – e-sushi
    Apr 8, 2016 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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