There is a stream cipher without any known cryptographic weaknesses. The attacker knows parts of the key so she can reduce the key-space to a size that can be practically brute-forced.

However the attacker only accesses some (continuous) parts of the ciphertext and she doesn't know how many bits she missed (the attacker is out of sync). She does know the general structure of the underlying plaintext and can check if a part of the keystream decrypts a partial ciphertext correctly. The attacker can also match known ciphertext-plaintext pairs, so parts of the keystream is also known to her.

There are no encrypting or decrypting oracles to use.

My understanding is that the attacker should generate a (theoretically) infinite long keystream and check if any parts match the ciphertext parts for every key candidate. This is of course impractical even for a couple of possible keys.

Is there a practical strategy for the attacker to brute-force the correct key and "synchronize" with the cipher stream?

What kind of cryptographic weakness of the cipher would make the task easier?

EDITED: Added some clarifications based on the comments of @fgrieu.

  • $\begingroup$ Is the stream cipher in the question strictly exclusive-OR of plaintext with a single large keystream (or is it a more complex protocol)? $\;$ Also: can the attacker mount a chosen-plaintext attack? If yes, hint: do this with a plaintext that does not require re-synchronization. $\endgroup$ – fgrieu Mar 17 '15 at 12:27
  • $\begingroup$ The keystream is simply XORd. The attacker can't mount CPA. $\endgroup$ – buherator Mar 17 '15 at 12:58
  • $\begingroup$ Can we liberally interpret "know the general structure of the underlying plaintext" into all plaintext bytes have high bit clear? If yes, hint: that's choosen-enough plaintext. $\;$ If no, please clarify what the quote allows. $\endgroup$ – fgrieu Mar 17 '15 at 13:13
  • 2
    $\begingroup$ Ah, so that attacker knows synchronized ciphertext-plaintext pairs, thus some of the true keystream. Is there anything problematic with just searching the chronologically first such known keystream segment in each candidate keystream corresponding to candidate keys, and in those few where it appears soon enough, computing more candidate keystream and search the other known keystream segments, in order to confirm the candidate key? $\endgroup$ – fgrieu Mar 17 '15 at 14:49
  • 1
    $\begingroup$ Searching the first 32-bit or 64-bit segment of known keystream into the candidate keystream while it is generated can be done at very little cost, if that's engineered into the software (or hardware) generating the candidate keystream; the rest of the search is more costly, but rare, thus has little impact on performance. $\endgroup$ – fgrieu Mar 17 '15 at 15:30

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.