If we have a stream cipher and the key but have lost a significant part of the beginning of the cipher stream of unknown length. Obviously we can add syncing information outside but I was wondering what can be done without extra info.

I was thinking of a scenario where there is a pattern we expect to find periodically in plain text to know if we are synced. If we lost up to $n$ bits and the first occurrence of our sync pattern is no more then $k$ bits into our part of the stream then there is a trivial $\mathcal{O}(n \cdot k)$ algorithm.

Can we do better?

What can we do if we can't hold $k$ bits of the cipher stream in memory and may need to throw out more cipher text before we find the sync?

  • $\begingroup$ It would be much easier to do this using a separate channel, but you could possibly leave "hints", e.g. words with a certain value that indicate how far the pattern is from that specific position. That's just a brainstorm though. If you can make sure the bit stream is byte aligned you can of course skip 7 out of 8 possible decryptions. And finally a self synchronizing cipher would of course be beneficial in this particular use case (rather than a stream cipher that produces a key stream). $\endgroup$ – Maarten Bodewes Apr 29 '17 at 13:31
  • $\begingroup$ One obvious approach to this sort of problem is to use CFB mode; that'll automatically resync after a fixed number of bits. Now, CFB isn't typically considered to be a stream cipher; is there a specific reason you have your heart set on one? $\endgroup$ – poncho May 2 '17 at 3:36
  • $\begingroup$ Purely academic. Though I was thinking of adverserial scenarios where we might have poorly applied stream cipher and something similar might be possible for an attacker $\endgroup$ – Meir Maor May 2 '17 at 3:57

Your Answer

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

Browse other questions tagged or ask your own question.