# Breaking a PRNG Scheme

Assume the following scheme for a PRNG generating decimals in [0,100)

Given a message and a key, compute tag := HMAC512(message, key). Take the first 5 hexadecimal characters of the tag. If the result is smaller than 1,000,000 in decimal, divide it by 10,000 and return it, otherwise take the subsequent 5 hexadecimal characters of the tag and repeat. If all 25 cases of 5 hexadecimal character groups yield decimal integers >=1,000,000, the remaining 3 hex digits are divided by 100 (decimal) and returned (in decimal).

In order to compute a stream of numbers, there is a counter within the message that is incremented with each generation.

Obviously, this is not a good scheme (given the final clause listed). But, can an attacker, knowing the message and not the key, predict subsequent numbers or predict if subsequent numbers will be within a threshold (either >=50 or <50)?

-
No, SHA256 on key, HMAC512 on message, key. – geofflittle Jan 21 '14 at 21:54
I could see constructing a distinguisher that identifies this scheme vs. an actual RNG based on the fact that numbers [0,40.95] will appear slightly more often than others. Other than that, I'm still unsure of how to relate the distinguisher to predicting >=50 on return. – geofflittle Jan 21 '14 at 21:56
There must be a problem in the scheme in the case that the first 25 groups of 5 are all > 1000000: 3 hex digits represent a range of 4096 values, which do not fit in [0,100). These likely need some dividing down or something. – jspencer Jan 29 '14 at 18:13
@jspencer, fgrieu informed me that when we say "in decimal" we're implying division by 100. Therefore, where it says "the remaining 3 hex digits are returned (in decimal)" the meaning "convert to decimal by division of 100 and representation of digits [0-9]" is implied. – geofflittle Jan 30 '14 at 16:32
What format do you want your output? If you want it stored in one of the standard floating point notations then it seems to me simpler just to set the exponent to scale your number down into [0,1] then multiply by 100 – figlesquidge Jan 30 '14 at 17:09

The generator in the question internally transforms the $512$-bit string designated tag into an output determined either:

1. as $1/10^4$ of a non-negative integer less than $10^6$, whenever the "If the result is smaller.." clause applies;
2. as $1/10^2$ of a non-negative integer less than $2^{12}$, otherwise.

Determination process 2 occurs for $d_2=(2^{20}-10^6)^{25}\cdot2^{12}$ among the $2^{512}$ bit strings that tag could take (ignoring for now how tag is generated), which forms a tiny proportion $d_2/2^{512}=2^{-110.8\dots}$ of theses bit strings.

At this stage the applied cryptographer:

• concludes that determination process 2 is much more likely to occur as the result of a malfunction of something than for any other cause (including if the adversary knows and can manipulate key and message), and ignores that determination process 2 (at least with the level of other information available);
• sees that the only credible determination process remaining produces output numbers $x$ with $0\le x<100$ and exactly expressible with 4 decimal digits after the point, with flat distribution if the tag bit string has flat distribution;
• sees that any distinguisher between a perfect TRNG producing such $x$ (hereafter: apparent goal), and the output, would also be a distinguisher for HMAC512 assuming unknown key, which he rejects summarily;

and moves on, satisfied that the PRNG in the question is close enough to its apparent goal for any practical purpose, including being unpredictable if the key is unknown.

The theoretician continues unmoved, and carefully classifies the possible outputs into two categories:

1. one of the $2^{12}$ numbers $x$ with $0\le x<40.96$ and exactly expressible with 2 decimal digits after the point;
2. other numbers $x$ with $0\le x<100$ and exactly expressible with 4 decimal digits after the point.

Each of the $10^6-2^{12}$ outputs in category 2 is reached only by determination process 1, thus for $c_2=(2^{512}-d_2)/10^6$ tag bits strings. Thus assuming flat distribution of the tag bit string, category 2 is reached with odds $\widehat{p_2}=c_2\cdot(10^6-2^{12})/2^{512}$, which is less than odds $p_2=1-2^{12}/10^6$ of reaching that category in the apparent goal: $\widehat{p_2}=p_2\cdot(1-2^{-110.8\dots})$.

That generator is broken in the theoretician's eye, for he has a distinguisher much better than anything he can dream of for HMAC512.

That is, the theoretician can devise a strategy that will allows him to win with odds $p>1/2$ when playing a game where the objective is to guess, from one given RNG output, if that RNG was selected (by fair coin toss) as the RNG in the question (reaching category 2 with known odds $\widehat{p_2}>1/2$), or as a TRNG with the apparent goal (of reaching that category with known odds $p_2>\widehat{p_2}$). The theoretician is interested in the strategy giving him the highest possible advantage, defined as $\epsilon=|p-1/2|$ (the absolute value is used because it is trivial to turn a strategy worse than answering based on coin toss into one better than that).

Towards that goal the theoretician would hypothetically bet on the RNG in the question when the given RNG output is in category 1, and otherwise bet on a TRNG (not randomly according to the criteria that I gave previously, sorry about that mistake but I'm of the applied kind). To compute the odds $p$ of winning, we consider the two mutually exclusive winning cases for this strategy:

• the RNG in the question is selected, and its output is in category 1, which has odds $(1-\widehat{p_2})/2$;
• the TRNG is selected, and its output is in category 2, which has odds $p_2/2$;

giving $p=(p_2-\widehat{p_2}+1)/2$ thus advantage $\epsilon=(p_2-\widehat{p_2})/2=2^{-111.8\dots}$.

It is left as an exercise to the reader to show that if $n>1$ outputs of the same chosen RNG are given, the advantage obtained is less than $n\cdot\epsilon$; is still desperately marginal with $n\approx 1/\epsilon\approx2^{111.8}$ outputs; becomes sizable at $n\approx \epsilon^{-3/2}\approx2^{167.7}$ outputs.

-

Exhaustive computation over the range of possible 20-bit values less than 1000000 shows that exactly half of them are >= 50 when divided by 10,000. So the output of this PRNG, assuming HMAC512 produces independent, uniform bits, is evenly distributed on [0,100), all assuming the last case (using the upper 3 hex digits) is not used.

That being the case, it's straight-forward to prove the following: Assume the output of HMAC512 is computationally indistinguishable from random. Then this PRNG is computationally indistinguishable from random.

Sketch of Proof: Suppose to the contrary that there exists an Algorithm $A(S)$ which, on a sequence $S=\left<s_1, s_2,...,s_q\;|\;s_i\in \left[0..100\right)\right>$ of outputs from the PRNG, returns a 1 to indicate the next output will be >= 50 and a 0 otherwise, and it does so with non-negligible advantage $a$. Then we construct algorithm $B(T)$ for $T=\left<t_1, t_2,...,t_q\;|\;t_i\in \left\{0,1\right\}^{512}\right>$ to attack HMAC512 as follows:

On input T ,
Let S = {min((t[19:0])/10000, 99) | t in T}
Return A(S)


Notice the input to $A$ corresponds to the PRNGs calculation with probability $10^6/2^{20}\approx.95$. If we assign 0 advantage to $A$ in the other cases, we see that $B$ can predict whether $t_{q+1}$ has a value >= 500000 in the low 20 bits with advantage $\approx .95a$. This violates the assumption that HMAC512 is computationally indistinguishable from random, so $A$ cannot exist. qed.

What this says is that this PRNG is as secure as HMAC512 (which theoretically is an open question, but practically a pretty good bet.) Of course, you could (and probably should, to protect the validity of $A$'s input) make a better construction that would take all 25 cases of 20-bit blocks from $t\in T$, and even account for the top 3 hex digits. But then you're changing what predicate $B$ is able to predict--it would no longer be limited to the low 20 bits--and the calculations get ugly. In the reduction given, you could be more conservative and assign advantage -1 for those 5% cases. Then the value of $a$ starts to matter. Plus you need definitions to connect advantage with indistinguishability, which are available in the literature.

-
Forgive me, what is the meaning of "Let S = {min((t[19:0])/10000, 99) | t in T}", specifically, "t[19:0]"? – geofflittle Jan 30 '14 at 16:35
@geoff92: That's set notation which, if read aloud, would be something like: "Let S be the set of the minimum of 99 or the low 20 bits of t divided by 10000 for each t in T." I see I was a little sloppy in not defining S and T as sequences, so I'll edit that. The idea is that S is a sequence of outputs from your PRNG, which I can feed A and get a prediction on whether the next output is >=50. The proof shows if A is possible, then I can make a B that takes a sequence T of outputs from HMAC512 and predict something about it's next output, too. This set shows how I make an S from a given T. – jspencer Jan 30 '14 at 16:54
After my first careless erorr, I'm going with the probability of hitting 25 consecutive overflows as $$\left(1 - \frac{10^6}{2^{20}} \right)^{25} \approx 2^{-111}$$ (Bit worried I even managed to get that wrong first time round-maybe time to call it a day and get some rest!) Either way, that sounds very much like you could construct a decent distinguisher just based on the lack of randomness in the shorter, 3 character output – figlesquidge Jan 30 '14 at 17:34
I think the algorithm is still unclear in the case of the upper 3 digits, so I won't go too far in this vane. And I'm not sure which distinguisher you're referring to, but you've only got a $2^{-111}$ chance of even seeing a derivative of those digits. Even if your advantage is 1 there, I wouldn't call that a strong, practical distinguisher. And then, just because the derivative is bad doesn't mean HMAC512 is bad. – jspencer Jan 30 '14 at 17:53
@geoff92, about the last 3 digits: That's certainly clear. But by following it, you introduce a heavy bias in that case which, even though unlikely to happen often, makes a slight bias overall. Why not minimize that effect by dividing by 40.96 (or 41 if it's important to stay in integer math) and create a much more uniform result over [0,100)? – jspencer Jan 31 '14 at 21:29