Problems with the PCG implementation from npm:pcg
Reaction: 🤬🤬🤬🤬
TL;DR: It will DoS your app, never use it!
It’s slow. It’s slow as hell. It’s ≈100x slower than an optimized implementation. They say, a PRNG is unlikely to become a performance bottleneck, but this particular one is a performance bottleneck! And it also can DoS your app, see below.
It’s slow, part 2. For a single-step state
transition during the number generation, it uses the arbitrary length
jump algorithm. Not something as simple and obvious as
y = x * MULT + c
, but more like
y = nextNthState(x, n=1)
.
It makes the bundler cry (due to Ramda).
It’s bloated. It’s ≈19 KiB minigzipped! Well, it’s due to Ramda, and if you use it and related, ahem, bloatware, the impact of this particluar module will not be that high, but it’s still much heavier than alternatives, especially taking in account that it doesn’t have any features except a single function to generate bounded integers, but it is…
It’s incorrect
Here is the core function randomInt(min, max)
:
// (referred as $b$)
const bound = max - min;
// (1)
if (
< 0 ||
bound >= pcg.algorithm.outputMaxRange
bound
)throw new RangeError();
// (referred as $t$)
const threshold =
.algorithm.outputMaxRange - bound) %
(pcg;
bound
// Uniformity guarantees that this loop will terminate
// (↑ oh dear…)
let n: Long;
let nextPcg = pcg;
// (2)
do {
= Long.fromValue(
n .getOutput(pcg.state),
nextPcg// (!!WRONG!!)
// (↑ `pcg` never changes!)
;
)= nextState(nextPcg);
nextPcg while (n.lt(threshold));
}
return [
.mod(bound).add(min).toNumber(),
n,
nextPcg; ]
Parenthesized comments are mine.
No full range integers!
LET’S IMAGINE the (WRONG)
fragment is
not wrong. In this case, the generator cannot yield integers in
the full range
, only
:
- The check
(1)
throws if the bound , so you can’trandomInt(0,2³²)
to get values in . - If the bound
, the threshold
. The loop
(2)
continues while the generated value is less than the threshold . If the generator yields , the loop will continue (actually, it will continue forever). If the generator yields in , the loop terminates, andrandomInt(…)
returns , but if , the result is .
Infinite loop!
But the main problem is that it loops infinitely! (Or rather, either once xor infinitely.)
The problem is in the (WRONG)
fragment. It calls
getOutput()
on nextPcg
, but the method doesn’t
depend on the state of nextPcg
, it just computes the output
function of its argument. And, yes, the argument
never changes! So if the first generated value
is
, the code will loop forever! What
a nice generator that DoSes your app at random!
Wait, this is a critical vulnerability, isn’t it?
How to use it
If you absolutely need this particular generator for some reason, you should use it like this:
let handle = createPcg32(...params);
const rand = () => {
let x = handle.getOutput(handle.state);
= nextState(handle);
handle return x;
; }
The exploit
This margin is too narrow to contain it.
The GitHub issue: https://github.com/philihp/pcg/issues/137
Well, the probability to get infinite loop is
. E.g., for
it is
, for a simple d6
roll it’s
, and for
it’s
.
The vulnerability can be exploited by finding an application, that
- uses a vulnerable version either server-side and
accepts user input for
min
andmax
bounds, - or client-side and accepts the data from other users for the bounds.
Everything that remains is to fill these fields to get the bound , PROFIT, the app is DoSed.