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 &lt;50)?
The generator in the question internally transforms the $512$-bit string designated tag into an output determined either:


as $1/10^4$ of a non-negative integer less than $10^6$, whenever the "If the result is smaller.." clause applies;
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&lt;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:


one of the $2^{12}$ numbers $x$ with $0\le x&lt;40.96$ and exactly expressible with 2 decimal digits after the point;
other numbers $x$ with $0\le x&lt;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&gt;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}&gt;1/2$), or as a TRNG with the apparent goal (of reaching that category with known odds $p_2&gt;\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&gt;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.