6

I am trying to shuffle an array using a cryptographically secure source of entropy.

I found a similar question, regarding shuffling arrays here How to randomize (shuffle) a JavaScript array?. However almost all solutions make use of Math.random, which is not secure. Unfortunately I do not have the reputation to comment/post on that question.

Here is the solution I came up with, which uses Durstenfeld shuffling paired with a CSPRNG for generating random integers in a given range (provided by random-number-csprng lib).

const randomNumber = require("random-number-csprng");

async function secureShuffleArray(array) {
  for (let i = array.length - 1; i > 0; i--) {
    const j = await randomNumber(0, i);
    const temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
}

Is this implementation correct and unbiased?

notes:

  • for my purposes the array would contain at most ~100 elements
  • running nodejs v6.10.3 LTS (transpiled)
David
  • 175
  • 2
  • 11
  • 1
    You indeed can post on any question starting from reputation 1 – smnbbrv Feb 27 '18 at 07:37
  • @smnbbrv i tried, but it appears that the question is "protected" and requires at least reputation 10 to post an answer on ... – David Feb 27 '18 at 07:44
  • And because that is a good question you now earned 10 reputation ;) – Thomas Feb 27 '18 at 08:13
  • 1
    [This question](https://stackoverflow.com/questions/47194034/shuffling-a-poker-deck-in-javascript-with-window-crypto-getrandomvalues) has some interesting insights related to the topic. – user3297291 Feb 27 '18 at 10:12
  • @user3297291 yes, i've seen that post, and it indeed seems that my solution is conceptually identical to [this solution](https://stackoverflow.com/a/47253709/2269027) which combines a few answers from different sources. At this point I believe my solution is likely correct, but it would be nice to have a consensus here as this seems like a fairly requested algorithm for nodejs (or potentially browserified javascript). – David Mar 15 '18 at 15:46

1 Answers1

3

After reviewing extensively, I have concluded that the solution is correct, being a verbatim implementation of the Durstenfeld shuffle.

However, the Durstenfeld / Fisher-Yates shuffle is only as random as it's RNG source. My solution depends on the random-number-csprng CSPRNG lib, which uses crypto.randomBytesAsync, and is therefore cryptographically secure for most all purposes (see How random is crypto#randomBytes?).

UPDATE: I have published a functionally equivalent yet more efficient version of this solution here crypto-secure-shuffle, also available as an npm package. Here is the relevant implementation:

const secureRandomInRange = require("random-number-csprng");

async function secureShuffle(array) {
    const promises = [];

    // asynchronously generate an array of random numbers using a CSPRNG
    for (let i = array.length - 1; i > 0; i--) {
        promises.push(secureRandomInRange(0, i));
    }

    const randomNumbers = await Promise.all(promises);

    // apply durstenfeld shuffle with previously generated random numbers
    for (let i = array.length - 1; i > 0; i--) {
        const j = randomNumbers[array.length - i - 1];
        const temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    return array;
}
David
  • 175
  • 2
  • 11