Logarithmic brute-force for stream-ciphers

Question

First of all, I want to make sure I understand stream ciphers correctly: I put a plainchar (e.g. byte?) through the stream cipher and receive a cipherchar. Correct?

When I now have a pair of plaintext/ciphertext, I could then brute-force all secrets which map plainchar[0] to cipherchar[0]. For the next character, I only need to try those passwords which succeeded for the first one. This way the brute-force search space is reduced logarithmically.

Is this correct?

Update As @poncho pointed out correctly, the search space is not reduced logarithmically, but the expensive encryption operation which generates the ciphertext for the plaintext. This has to be done for every tried password which is every possible password for brute-force.

Answer 1

…I could then brute-force all secrets which map plainchar[0] to cipherchar[0]. For the next character, I only need to try those passwords which succeeded for the first one. This way the brute-force search space is reduced logarithmically.

Yes¹^,². Problem is, ‘brute-force all secrets’ is supposed to be impossible in the first place.

---

¹ For a secure stream cipher.

² And a non-standard definition of reduced logarithmically as rightly pointed in another answer.

Answer 2

This way the brute-force search space is reduced logarithmically.

Well, no.

If there are $N$ possible keys, then you test $N$ keys on the first byte. Then, you keep only those that succeed on the first byte, and test those on the second byte; that's approximately $N / 256^1$. Then, you test those keys that succeed on both bytes, that's approximately $N / 256^2$ keys.

When you count the total number of keys you've tested (including those you tested multiple times), you come up with an expected:

$$N + N/256^1 + N/256^2 + N/256^3 + … = (256/255)N$$

And, $(256/255)N$ is not a "logarithmic reduction" over $N$...