# Resynchronizing brute-force attack against stream ciphers

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?

• 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. – fgrieu Mar 17 '15 at 12:27
• 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. – fgrieu Mar 17 '15 at 13:13