# Logarithmic brute-force for stream-ciphers

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 to cipherchar. 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.

• They usually operate on a bit like Trivium or bytes, larger types are possible but not common – kelalaka May 23 '20 at 17:05

## 2 Answers

…I could then brute-force all secrets which map plainchar to cipherchar. 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.

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$$...

• Thanks for pointing this out! You are right, the search space is not reduced, but the effort to encrypt the plaintext to the ciphertext for a guessed password. This operation has to be run in every loop iteration and usually is the expensive one. – darkdragon May 24 '20 at 5:32