How large is the seed in an encryption algorithm such as stream cipher?

Question

The stream cipher is an encryption algorithm that was designed to approximate an idealized cipher, known as the One-Time Pad. It's crucial for a stream cipher to remain secure is to have a pseudorandom generator that hard to predictable and a seed that was never used. For this to be achieved, I assume we need to have a really large seed that the most powerful computer can't predict, but I can't approximate how large the number is.

Answer 1

The seed of a pseudorandom generator that is used as a stream cipher is called a key.

The most common key sizes are 128 bits and 256 bits. (That's symmetric keys, where there's no cheaper way to break than brute force. Asymmetric cryptography typically relies on keys having certain mathematical properties that make the algorithm work, but also enable better attacks than brute force.)

To understand how hard it is to break a 128-bit key, meaning that you have to try $p \cdot 2^{128}$ possibilities for a chance of success $p$, consider these orders of magnitude:

• A fast processor might be able to try about one billion keys per second (1GHz).
• A powerful attacker might be able to afford one billion processors.
• The universe is about 1 billion billion seconds old (a little over 30 billion years).
• 1 billion is slightly less than $2^{30}$ ($2^{30} = (2^{10})^3 = 1024^3 \gtrsim (10^3)^3 = 10^9$).

So if you're extremely rich and willing to wait until the universe is twice as old, you can enumerate about $2^{120}$ keys. If you're only willing to wait 30 years, you can only enumerate about $2^{90}$ keys, giving you a chance of breaking any particular key of less than one in 250 billion. Conclusion: a 128-bit key is sufficient for security against brute force.

A 256-bit key provides a security margin that can cover:

• Hypothetical advances in cryptanalysis that make the algorithm slightly easier to break.
• Hypothetical advances in computation, such as quantum computers, which effectively halve the key size.
• A very powerful adversary who tries to break basically every encrypted communication, and is interested in even succeeding for a tiny fraction.
• A very powerful adversary who records basically every encrypted communication, and would detect if the same key is used twice, which could then let them discover the key by non-cryptographic means (exploiting a bug, demanding it at gunpoint, a subpoena, …). Due to the “birthday paradox”, there's a macroscopic chance that two instances will generate the same random key if the number of instances is at least about the square root of the number of possible keys, so 8 billion people using a billion different keys each (about $2^{63}$ keys in total) would be around the threshold for 128-bit keys.

---

In practice, key size just isn't an issue except in legacy software and protocols that are at least 2 decades out of date (keys shorter than 128 bits became obsolete when AES became the de facto standard in the early 2000s). Cryptography gets broken by non-cryptographic means or due to implementation weaknesses such as side channels, or gets circumvented altogether due to non-cryptography-related security vulnerabilities (binary exploits, escaping exploits, misconfigured controls, phishing, …). Cryptographic algorithms are usually the strongest part of information security.

Answer 2

The seed is called the key and to be secure it really depends on the usage and known computing powers. The most powerful collective power (known) is currently the bitcoin miners that they have reached $\approx 2^{93}$ SHA256 calculations per year in this year.

Therefore, the effective key size must be larger than $2^{93}$ and the NIST requires a minimum of 112 bits. The miners need $2^{19}$ years to achieve $2^{112}$. This may true for the single target. The attackers, however, may use batch attack (multi-target attack) so that even the key size is 128-bit they can find the first target key with $2^{70}$ work with billion targets (See in Has AES-128 been fully broken?).

Therefore we prefer the golden standard as the 256-bit key sizes. The ChaCha20 can use a 256-bit key size or one can use AES-256 in CTR mode to achieve a stream cipher.

In addition to the key, the modern stream ciphers also using IV/nonce to use the key more than one encryption and this is also a countermeasure to batch attack. One must be careful about the (key,nonce) re-use issue that can at least remove the confidentiality. To mitigate this one can use XChaCha20 that uses 192-bit nonces or can use a non-misuse resistant scheme that is going to be the next standard in the future.

Of course, we don't use the stream cipher alone, we prefer Authenticated Encryption modes like ChaCha20-Poly1305 to achieve confidentiality, integrity, and authentication.

Answer 3

It depends on the exact encryption method you are using.

128-bit is theoretically sufficient against normal computers and 256-bit against quantum computers, as per previous answers, but you should always follow the best practice standard of the exact type of encryption you are using. This is because no encryption algorithms has perfect entropy, or in layman's terms, no encryption algorithm is perfectly random.

Because no key is perfectly random, it means that methods exist for predicting keys that do not require you to check every single possible key combination. So, while symmetric encryption like AES has very close to perfect randomness making 256-bit sufficient for all known use cases, many common asymmetric algorithms such as RSA suggest key lengths up to 4096-bit due to known methods existing against them that are more efficient than brute force.

That said, it is not really your key-length that is most important. The most important part of a symmetric encryption is the padding. This is a randomized string that is appended to the front of your plain-text string and then dropped. RC4 with a max length (2048 bit) key is actually quite easy to break, but RC4-drop512 with only a 512-bit key is much harder to break despite the shorter key because it does more to obscure the deterministic part of of the stream cipher making cracking it require something much closer to a brute force attack.