# How is an epsilon of 1/1000 non-negligible?

Lately I've been studying cryptography and in the current course I'm taking we're reviewing statistical tests and how they can be used to determine if a pseudo-random generator is secure or not.

Essentially, one of the requirements for a Pseudo-random generator to be secure is that the probability of guessing the next bit in the string is less than 1/2 + a non-negligible epsilon (epsilon being any statistical advantage the computer has of guessing the next bit of the string due to insecurity in the PRG).

In an example the professor uses, he states that the probability of guessing the next bit of output from the PRG is 1/2 + 1/1000 (the non negligible epsilon).

How is 1/1000 non-negligible? I understand we're using computers with thousands of times faster processing power than a normal human brain, but that still means that a computer only has a 50.1% chance of guessing the correct bit. How can a computer leverage that tiny extra probability to crack a secret key?

• Consider an attacker who induces your client to send its password 1000 times. They'll be able to recover most of the password by combining the information learned from each transmission. This is similar to the attacks against RC4 in TLS. – CodesInChaos Jul 11 '15 at 12:36
• There is an error in your definition: To be secure, $\epsilon$ has to be smaller than a negligible function. If the advantage is non-negligible, then it is insecure. Anyway about the example: If it includes a specific $n$, then you can calculate the advantage or an upper bound of it. If the advantage is independent of $n$, it can not be negligible. – tylo Jul 13 '15 at 10:35

How can a computer leverage that tiny extra probability to crack a secret key?

The answer to that depends on what type of key it is, how it's being used, etc. Certainly, the bias would make a brute-force attack easier, but you probably wouldn't need to worry about that, regardless.

Your professor, though, is trying to answer a different question. He wants to know, and wants you to think about:

How small does the bias have to be in order to ensure that no one can leverage it to crack a secret key?

Note that this question is general: it makes absolutely no reference to what kind of key is being generated, or how it's being used. And this is how it should be: we're designing a general-purpose PRNG, so we shouldn't make assumptions about those things.

Suppose we used this PRNG to generate a 128-bit AES key. Well, assuming the bits are independent (but have the 1/1000 bias), then some math shows that the statistical distance between the result and a truly random 128-bit value is about 0.018. It follows if you used this PRNG in place of some mathematically perfect one, an attacker might be able to increase the chances of a successful attack by as much as 1.8% (but by no more than that).

Is this something you should be worried about? Well, if it's a 1.8% increased chance of someone decrypting a harmless IM conversation you had with a friend... probably not. On the other hand, if you're encrypting your bank password or a set of nuclear launch codes, a 1.8% increased chance of being compromised is probably an intolerable risk.

The 1.8% is an upperbound. We might not be able to find an attack that obtains that advantage. But by limiting the bias to something like 2^{-80}, we can safely stop worrying about the matter entirely.

The theorists would define a bias as "negligible" if it decreases "really fast" with respect to some adjustable parameter of the PRNG. This definition aims to ensure that we can always choose a value for the PRNG parameter such that (1) it's bias is quantitatively really small, e.g. 2^{-80}, but (2) the PRNG is still efficient.

Ultimately, however, you have to fix the parameter when you go and actually start using the PRNG. At this point, you have to decide what concrete value of "negligible" you're comfortable with. This is a judgement call, but any reasonable PRNG will let you put it safely in the "we don't even have to worry about this" territory and still produce outputs as quickly as you could ask for.

A negligible function is one which decreases more rapidly than the inverse of any polynomial. A constant does not decrease at all, hence it is obviously non-negligible.

I'm going to use the following definition of a negligible function (source - http://www.cs.cornell.edu/courses/cs4830/2010fa/lecnotes.pdf page 27):

A function $\epsilon(n)$ is negligible if for every $c$, there exists some $n_0$ such that for all $n > n_0$, $\epsilon(n) ≤ \frac{1}{n^c}$.

Intuitively, a negligible function is asymptotically smaller than the inverse of any fixed polynomial. Examples of negligible functions include $2^{−n}$ and $n^{−log log n}$. We say that a function $t(n)$ is non-negligible if there exists some constant $c$ such that for infinitely many points $\{n_0, n_1, ...\}, t(n_i) > n_i^c$. This notion becomes important in proofs that work by contradiction.

This means that what non-negligible means is contextual, and is actually a function of $n$. Given a 0.1% bias we may not be able to crack a secret key but we can perhaps distinguish the output of the PRG from true random. If the PRG produces output not computationally indistinguishable from random then it is by definition not cryptographically secure. From there (as happened with RC4 I believe)) one is able to make a better than random guess as to what the bits of a key / key stream are. Hope that helps!

Look into brute force factorization. If you can leverage a weakness in the PRNG then your factorization time is substantially diminished.

• Could you elaborate on this? As it is, it doesn't answer the question at all. – Paŭlo Ebermann Jul 12 '15 at 9:35
• 1) This question is about what it means for an attacker's advantage to be negligible. Your answer doesn't address that at all. 2) Exploiting a weak PRNG to factor an RSA modulus generated by it isn't related to brute-force. 3) If you're referring to the "many moduli have a prime in common" problem, that was caused by very badly seeded PRNGs outputting identical data of several hundred bits for the first request of random data. This is unrelated to small biases. – CodesInChaos Jul 18 '15 at 15:09