Cryptographically secure random int in range

Question

I tried to make a cryptographically secure random int in range generator for javascript, practically the javascript equivalent of php's random_int(min,max):

function maybe_cryptographically_secure_random_int(min, max) {
    if (!Number.isInteger(min)) {
        throw new Error("min must be an integer");
    }
    if (!Number.isInteger(max)) {
        throw new Error("max must be an integer");
    }
    if (min < Number.MIN_SAFE_INTEGER) {
        throw new Error("min must be >= Number.MIN_SAFE_INTEGER (" + Number.MIN_SAFE_INTEGER + ")");
    }
    if (max > Number.MAX_SAFE_INTEGER) {
        throw new Error("max must be <= Number.MAX_SAFE_INTEGER (" + Number.MAX_SAFE_INTEGER + ")");
    }
    if (min === max) {
        return min;
    }
    if (min > max) {
        throw new Error("min must be <= max");
    }

    const range = max - min + 1;
    if (range >= Number.MAX_SAFE_INTEGER) {
        // hmm, i wonder if this is a problem or not
    }
    const bits_needed = Math.ceil(Math.log2(range));
    const bytes_needed = Math.ceil(bits_needed / 8);
    const max_value = Math.pow(256, bytes_needed);
    if (max_value > Number.MAX_SAFE_INTEGER) {
        // hmm, i wonder if this is a problem or not
    }
    const max_acceptable = Math.floor(max_value / range) * range - 1;
    if (max_acceptable > Number.MAX_SAFE_INTEGER) {
        // hmm, i wonder if this is a problem or not
    }
    const random_bytes = new Uint8Array(bytes_needed);
    let random_value;
    const max_attempts = 9999; // never seen it take more than 2 attempts...
    let attempts = 0;

    do {
        ++attempts;
        if (attempts > max_attempts) {
            throw new Error("Failed after " + max_attempts + " attempts");
        }
        crypto.getRandomValues(random_bytes);
        random_value = 0;
        for (let i = 0; i < random_bytes.length; i++) {
            random_value = random_value * 256 + random_bytes[i];
        }
    } while (random_value > max_acceptable);

    random_value = random_value % range;
    const ret = min + random_value;
    if (ret < min || ret > max) {
        // should be impossible...
        throw new Error("Generated value " + ret + " is out of range [" + min + ", " + max + "]");
    }
    // console.log("Attempts: " + attempts);
    return ret;
}

some simple test code:

o={"-1":0,"0":0,"1":0,"2":0,"3":0,"4":0,"5":0,"6":0,"7":0,"8":0,"9":0,"10":0};
for(let i=0;i<1_000_000;++i){
    ++o[maybe_cryptographically_secure_random_int(-1, 10)];
}
o;

yields something like

Where will you use this? Anywhere the JavaScript Crypto API is available? It has the getRandomValues function for getting strong random values. developer.mozilla.org/en-US/docs/Web/API/Crypto/getRandomValues — TomG
– TomG, Commented Nov 22, 2024 at 12:30
@TomG not at liberty to say exactly where it will be used, but I want to select random indexes from an array, hence I want index=cs_random_int(0, arr.length); - and browser/Node. Crypto API always available. — hanshenrik
– hanshenrik, Commented Nov 22, 2024 at 14:49

J_H · Accepted Answer · 2024-11-22 19:45:59Z

extract helper

The first several lines are great, necessary, and very clear. But they are a bit tedious. Consider burying them in a validate_args() helper. Then your main function might even fit in one screenfull with no scrolling.

specification

In the Review Context you helpfully mentioned the php function you want to emulate. But the source code fails to mention that, or any other spec. Coming from a python background I initially found the range calculation surprising, as I anticipated the usual half-open interval which composes nicely, rather than a closed interval. The source code should explain that the return value contract is:

A cryptographically secure, uniformly selected integer from the closed interval [min, max]. Both min and max are possible return values.

One could always put together a base implementation which uses an open interval and fixes min at \$0\$, and then have a thin façade do trivial impedance matching for the caller.

range too big

        // hmm, i wonder if this is a problem or not

Yes, it is. Throw a fatal error in this case. That can happen down in your "validate" helper.

JS integers go up to about \$2^{53}\$, plus there's a sign bit on the side. Attempt to represent a larger quantity and we'll have FP discarding low order bits, treating them as if they were supposed to be zero.

We see two more instances of this:

    if (max_value > Number.MAX_SAFE_INTEGER) {
        // hmm, i wonder if this is a problem or not
    }
    const max_acceptable = Math.floor(max_value / range) * range - 1;
    if (max_acceptable > Number.MAX_SAFE_INTEGER) {
        // hmm, i wonder if this is a problem or not
    }

If max_value is too big, it could be a problem deserving of a fatal throw. But it happens that all the low order bits truly are zero, so in this case a FP quantity will actually give a precise representation of figures like \$2^{54}\$ or \$2^{55}\$.

But then max_acceptable could run into trouble, and need a fatal throw.

Rather than writing some "maybe?" comments, it would be much better to exhaustively run "large" test cases. Or just declare by fiat that caller cannot ask for a range bigger than \$2^{32}\$, so the analysis is simpler.

The random_value * 256 + random_bytes[i] expression is worth worrying about. We wouldn't want it to go above MAX_SAFE_INTEGER, since at that point the addition of low-order bits is just adding in some zeros.

little vs big

Choosing to fill an array with uint8's instead of uint32's clearly can work. But it seems like you're doing more operations on smaller values. Working with bigger values should be more performant.

rejection sampling

I don't understand this remark:

    const max_attempts = 9999; // never seen it take more than 2 attempts...

I mean, suppose caller's parameters were (0, 1) -- caller is asking for a random bit. The do loop kind of goes away, since we're simply assigning random_value = random_bytes[0]. Now there are \$\frac{2}{256}\$ "good" dice rolls, and for the other \$\frac{254}{256}\$ rolls we reject and re-roll. That could take significantly more than 2 attempts.

Keep the rejection approach, it is sound. It deals nicely with e.g. (0, 2), generating the three values with equal probability.

The usual way folks deal with this is by masking some high order bits. bits_needed already has much of the answer. What we're looking for is a one-byte mask for the high order byte, one less than a power of two. In the (0, 2) example we would want 0x03. That way we really could be confident that just a handful of rejections would happen on each draw.

modulo

I don't understand this line:

    random_value = random_value % range;

Maybe it is leftover code from a previous implementation, before you'd implemented rejection sampling? A modulo approach isn't exactly terrible, but it does induce a small bias, so caller can distinguish the returned values from truly random values. Recommend you simply delete this line.

Oohhhh, wait. You're combining modulo with rejection?!? That's odd. Pick one or the other.

Also, if your base implementation fixes min at \$0\$ it will be a little easier to reason about.

paranoia

        // should be impossible...

I like it.

I agree with you, it should be impossible. But leave it in. It hammers home the contract very clearly.

Also, thank you for sharing the test code, that's helpful.

Stack Exchange Network

Cryptographically secure random int in range

1 Answer 1

extract helper

specification

range too big

little vs big

rejection sampling

modulo

paranoia

You must log in to answer this question.

Hot Network Questions

Cryptographically secure random int in range

1 Answer 1

extract helper

specification

range too big

little vs big

rejection sampling

modulo

paranoia

You must log in to answer this question.

Related

Hot Network Questions