6
\$\begingroup\$

I'm trying to generate secure randomness in Node as a personal challenge. I was wondering if the following implementations are correctly random or they have some flaws.

const crypto = require('crypto');

const secureRandomFloat = (bytes = 6) => {
  const size = Math.pow(2, bytes * 8);
  const hexString = crypto.randomBytes(bytes).toString('hex');
  const randInt = parseInt(hexString, 16);
  return randInt / size;
}

export const secureRandomIntRange = (min, max) => {
  const range = max - min; // max is the first not included integer [min, max)
  if (range > Number.MAX_SAFE_INTEGER) return null;
  // use an amount of bytes that will cover the range we need
  const bytes = Math.ceil(Math.log(range) / Math.log(256));
  const size = Math.pow(2, bytes * 8);
  // this is the "tail" of possible numbers. Using them that would
  // give us more chances to get lower values when using modulo
  const excess = size % range;

  let validRand = false;
  let hexString;
  let randInt;
  while (!validRand) {
    hexString = crypto.randomBytes(bytes).toString('hex');
    randInt = parseInt(hexString, 16);
    validRand = randInt + excess < size;
  }

  return min + randInt % range;
}

const secureRandomChoice = arr => {
  // This is to check that the "arr" is iterable, like an array
  // or a string, etc.
  if (arr == null) return null;
  if (typeof arr[Symbol.iterator] !== 'function') return null;
  if (!arr.hasOwnProperty('length')) return null;

  // use an amount of bytes that will cover the range we need
  const bytes = Math.ceil(Math.log(arr.length) / Math.log(256));

  const randIdx = secureRandomIntRange(0, arr.length);
  if (randIdx === null) return null;
  return arr[randIdx];
}

I've done some testing with a million iterations and results seem to be random, but I don't know if I'm missing something.

Are these implementations going to give me pseudo-randomness?

Culling

@Blindman67 has commented that culling, which I do in the while loop at secureRandomIntRange, is not going to give me random values. I don't have a strong argument to say that culling will give me random numbers, but I don't see why it won't.

I used culling because I remembered once I needed to generate random points in a sphere. To do that I took a random point in a cube (much simpler), and discarded the point if it was out of the sphere. I think it gave me a random distribution of points in the sphere.

I tried to apply this same idea to this problem. If I have 1 byte I can generate 256 possible combinations at random, say from number 0 to 255. If I wanted to select an integer from 0 to 99 (100 possible numbers), the naive way using modulo would give me the following relations:

randomByte:     0   1   2 ... 99 100 101 ... 199 200 201 ... 254 255
secureRandInt:  0   1   2 ... 99   0   1 ...  99   0   1 ...  54  55

But that way all numbers from 0-55 can be drawn from 3 different bytes, whereas numbers from 56-99 can only be drawn from 2 different bytes. Then, the way I thought could give me a random distribution in the range was assigning the numbers as follows:

randomByte:     0   1   2 ... 99 100 101 ... 199 200 201 ... 254 255
secureRandInt:  0   1   2 ... 99   0   1 ...  99   x   x ...   x   x

Where x means that the byte is not valid (!validRand) and I have to discard it and get a new byte at random.

In this example, the values for the different variables would be as follows:

range = 100
size = 256
excess = 56
isValid = randInt + excess < size
// isValid = randInt + 56 < 256 --> isValid = randInt < 200
// T for true and F for false
randomByte:  0   1   2 ... 99 100 101 ... 199 200 201 ... 254 255
isValid:     T   T   T ...  T   T   T ...   T   F   F ...   F   F

Do you think that approach is invalid to get random numbers?

\$\endgroup\$
  • \$\begingroup\$ I'm not qualified to comment on the correctness with regard to randomness, but secureRandomIntRange just takes min and max, and you also pass bytes in secureRandomChoice \$\endgroup\$ – Gerrit0 Mar 3 '18 at 23:30
  • \$\begingroup\$ secureRandomFloat(bytes) for bytes > 6 creates integer values greater than Number.MAX_SAFE_INTEGER so no longer has even distribution . Also the while loop in secureRandomIntRange is selectively culling values. That is not random \$\endgroup\$ – Blindman67 Mar 3 '18 at 23:53
  • \$\begingroup\$ @Gerrit0 you're right. That's a mistake because I was getting bytes as an argument instead of computing it in secureRandomIntRange. I didn't realize the mistake because I wasn't using that argument anymore, so no errors were thrown. I'll edit the code. Thanks for the catch! \$\endgroup\$ – Daniel Reina Mar 4 '18 at 9:21
  • \$\begingroup\$ @Blindman67 that's a good point. I'll check if the range is bigger than Number.MAX_SAFE_INTEGER and return an error. Regarding the culling, can you elaborate why that cannot be random? I'll update the question with my reasoning for doing culling. I'll add the check for range size. I'll also decrease the range size by 1, returning values from min to max, not including max –that seems to be the standard–. Thanks for the comment! \$\endgroup\$ – Daniel Reina Mar 4 '18 at 9:35
  • \$\begingroup\$ You are using crypto which as I understand has rigorous standards to comply with industry needs for security. Selectively culling random values reduces the set of all possible values. Though it may look random, the reduced set can provide a way to find the seed. Even a few out of a large set can significantly reduce the computational work needed to crack the sequence, knowing how you do the cull makes it even easier. \$\endgroup\$ – Blindman67 Mar 4 '18 at 12:14
3
\$\begingroup\$

secureRandomIntRange

Scheme

Basically what you generated with painstaking work is to create an implementation of the Complex Discard Method described in section A.5.2. That's a known secure scheme, so kudos for that.

I don't like the way bytes is calculated in the secureRandomIntRange function. It probably uses floating point and that may introduce rounding errors. It took quite a search, but it is easy to calculate the bit length of the integer using Math.clz32(x) where x is the number:

sizeBytes = ((32 - Math.clz32(range)) + 7) / 8;

Note the name change from bytes to sizeBytes.

If you look closely you'll notice that this creates a problem with the value 0, as that is now represented by 0 bytes. Best not to allow ranges of zero elements. And for one element, you may just want to return that element. It also shows that going to 2^32 and over will represent problems, so that's a maximum for the range in this case (which is different from MAX_SAFE_INTEGER because that's 2^53).

Performance

If the range is somewhat higher than half of maxValueOfBytes then the scheme will loop with a 50% certainty. You can somewhat reduce that by deliberately generating a higher amount of bytes. That way you don't need as many bytes from the random number generator in the worst case scenario (at the obvious disadvantage of requiring more bytes for the good scenario). Note thought that you can get very unlucky tossing coins, and you might want to avoid such hickups where the while loop keeps on running.

One little trick that is sometimes performed is to check if range has just one bit set, i.e. is a power of two. In that case you can just randomly generate bits and return those. For instance, if the range is 256, then you can just return a single byte. If the range is 128 then you can generate a single byte, set the most significant bit to 0 and return the result. Basically, if you use precisely as many bits as required then your method degenerates to the Simple Discard Method.


secureRandomFloat

Random float is designed well, except that you might want to check how it handles precision for larger byte sizes. There is likely a maximum integer size as well, so rounding will probably get problematic for larger values of parameter bytes.


secureRandomChoice

It does seem to pick a random from a list of options. So sure, fine.


Code

  • Already mentioned in passing: there should be more guard checks on the input, especially on the secureRandomIntRange low end values.
  • Guard statements should result in an exception, not in a function returning null. You're not just propagating the billion dollar mistake, you're adding to it.
  • Try to avoid floating point operations. I know, I know, that's a stupid requirement for JavaScript, but really it is important because proving that your JavaScript doesn't have any rounding issues might be tricky. Hence the integer calculations performed for sizeBytes above: I'm sure that they work as long as everything is within the maximum size of a 32 bit integer.

That last note is probably going to be contested, especially since floats should not loose precision for calculations that stay within [0, 2^53). So you may want to keep an open mind to different arguments about it.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.