3
$\begingroup$

I remember reading somewhere that sometimes in some stream ciphers it is necessary to skip the first values they produce. I can't find any information on this right now.

But it seems to make sense. Just as a hash function needs to do many rounds before it returns a random result, the CSPRNG needs some number of iterations so that seed and key information cannot be obtained from the first results.

How do you determine how many iterations this must be? Or are there other ways to solve this problem? For the results to be random from the first iterations it would be enough to have proper initialization with a random key and seed (which can also be treated as a key). But I don't think this solves the problem of first generator results. You can still read some key properties from those first results, exactly as if you didn't do enough rounds in the hash function.

PS My idea to test how many iterations we have to skip is to treat the CSPRNG as a hash function with a key and feed it by numbers $1,2,3,...$ as a seed with some keys, especially specially selected to make them appear weak (but also with random keys). Then see if such a hash function passes statistical tests, such as PractRand. This would be a minimum condition. It still does not preclude that there will be methods of sophisticated cryptographic attacks that will pick out bits of the key from the numbers looking for PractRand as random numbers.

$\endgroup$
1
  • 1
    $\begingroup$ A good stream cipher should not have those kind of properties. Older / not so good stream ciphers such as RC4 do have distinguishing properties in their output key stream. Some of these indicate an issue with the output bytes in general, but others depend on a relation with the internal state of the algorithm, and those then are of course algorithm specific. This is kind of where the problem is: first of all, some possible issues may not be detectable by "simple" output analysis in the first place. For others the attack depends entirely on the algorithm. So the number of iterations depends. $\endgroup$
    – Maarten Bodewes
    May 22 at 20:57

2 Answers 2

3
$\begingroup$

I remember reading somewhere that sometimes in some stream ciphers it is necessary to skip the first values they produce.

Not some stream ciphers, but one specific cipher: RC4. RC4 is from an earlier era when cryptographic primitives did not receive a lot of scrutiny – in fact, it was originally a secret algorithm. Once the design of RC4 was made public, a number of weaknesses were discovered. The main weakness was that a bias in the beginning of the keystream. RC4 was popular at the time an attack based on this bias was first discovered, and a countermeasure was to discard the first few bytes. Over time, the bias analysis was improved, which made discards insufficient, and RC4 gradually lost in popularity.

RC4 has a very simple design: each round consists of some simple scrambling of the internal state, and emits one byte of output. It turns out that until there have been enough rounds, the output is somewhat predictable.

Most ciphers perform multiple rounds of scrambling before emitting any output. And ciphers in common use have been validated by years of study by the cryptographic research community.

Just as a hash function needs to do many rounds before it returns a random result, the CSPRNG needs some number of iterations so that seed and key information cannot be obtained from the first results.

Yes and no. It's true that a CSPRNG needs enough scrambling from the seed. But that scrambling is built into the basic constituents of the algorithm. Typical modern CSPRNG are based either on a hash (which already has many rounds inside) or on a block or stream cipher (which already has many rounds inside).

My idea to test how many iterations we have to skip is to treat the CSPRNG as a hash function with a key and feed it by numbers 1,2,3,... as a seed with some keys

This is a valid and popular approach for key derivation functions — deterministically generating pseudorandom material from a seed. (Note that I'm talking about key derivation from high-entropy material, not password-based key derivation, also known as key stretching, which has different requirements.) Examples of key derivation algorithms that follow this paradigm are NIST SP 800-108 KDF in counter mode and HKDF.

However, as a random generator, this approach is missing something — which RC4 is also missing, by the way (which made it a poor choice for a CSPRNG, despite its popularity). It lacks backtracking resistance: the property that if the state is compromised, this compromises future RNG outputs, but not past outputs. Backtracking resistance requires a one-way transformation of the RNG's state each time it emits output. Any construction that uses a constant secret and a public variable to generate outputs lacks backtracking resistance.

$\endgroup$
4
  • $\begingroup$ You need a correction. See it here $\endgroup$
    – kelalaka
    May 25 at 14:37
  • $\begingroup$ @kelalaka Can you (well, Squeamish Ossifrage) please expand or provide references? AFAIK ARC4 was published in 1994, and statistical anomalies were known pretty quickly but not within 24 hours, but attacks didn't come out until the early 2000s (notably mattblaze.org/papers/others/rc4_ksaproc.pdf in 2001 — whose “previous attacks” section cites 1997 and 1998 papers which 1. didn't lead to practical attack and 2. came after RC4 was popular, e.g. it was used in SSL). $\endgroup$ May 25 at 15:32
  • $\begingroup$ Bob Jenkins, Sep 15, 1994, 6:51:50 PM talk about the Bias on Sci.Crypt. $\endgroup$
    – kelalaka
    May 25 at 21:34
  • $\begingroup$ @kelalaka Ah, thanks. I see, yes, I'd written about the bias but meant (practical) attacks based on that bias, which took a few years. $\endgroup$ May 25 at 21:51
1
$\begingroup$

Most traditional stream ciphers have state $S=(s_1,\ldots,s_n)$ of size $n$ bits, a state update function $\phi:S\rightarrow S$, which is initialized by random key material, say $S_0=(k_1,\ldots,k_n)$ and the state iteration is $S_{t+1}=\phi(S_t),$ for $t=1,2,\ldots.$ They also have an output function $f:S\rightarrow \{0,1\}^\ell,$ which outputs $\ell$ bits at once. Typically we can have $\ell=1,$ or $\ell=8.$

So a certain number of iterations are required for any easily computable correlations from the key material to dissipate in the observed keystream sequence $f(S_t),f(S_{t+1}),\ldots$ (assuming known ciphertext or known plaintext and an additive cipher where plaintext is XORed with the keystream).

Traditionally the mapping $\phi$ was of the form $$ \phi(s_1,\ldots,s_n)=(s_2,\ldots,s_n,s_{n+1}),\quad s_{n+1}=g(s_1,\ldots,s_n) $$

for efficiency reasons, as in shift registers. So you'd need a constant multiple of $n$ iterations before actually using the keystream.

As in the comments, in modern stream ciphers a number of measures such as using IVs or Nonces, or using various modes of operations of stream ciphers, it is possible to use the keystream right away, without throwing any of it away. For example, if the IV is random and independent of the key and is the same bitlength as the state and it is XORed into the initial state (while being public) this has a whitening effect and makes the keystream independent of the key.

$\endgroup$
1
  • $\begingroup$ Thanks, this answear makes this topic even more clear to me. $\endgroup$
    – Tom
    Jun 1 at 2:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.