Open
Conversation
#102 issue: Update index.js
add a newline to the result to remove the percentage in the CLI output
maint(dependencies): Cleanup, update dependencies
feat(v3): Rework ulid based on ulidx
Hi @j0pgrm, re #81 Your `if` statement is there to cover the possbility that your PRNG will generate the number 1. In general, PRNGs produce values from 0 to _less than_ 1, i.e. from the range 0 (inclusive) to 1 (exclusive). This is because when they generate an N-bit binary fraction, the highest value (all `1`s) will be just a tiny bit smaller than 1. Your `Math.floor` correctly rounds downward, so that `rand` will be in the range 0 (inclusive) to ENCODING_LEN *- 1* (inclusive). So the `if` will never be triggered. If, for some reason, you in future switch to a prng that somehow can generate a 1, for example because it has an idiosyncratic desire to cover a range of 0 (_exclusive_) to 1 (_inclusive_), then: * the chance of this is extremely small (1 in 2**N, not 1 in 2**8) * the PRNG will have lost the ability to generate 0 * your random character generator would have a micrscopically smaller chance of generating the first encoding character, and have a microscopic chance of trying to pick the non-existent character at #ENCODING_LEN. A neat solution for you is to simply wrap round that exactly-1 PRNG value back to 0, most conveniently A simple way to achieve this is to modulo the `rand` by ENCODING_LEN. Thank you for an excellent library.
Resolve #81 to deal with a potential future scenario of PRNG generating `1`
The random number generation logic results in a bias leading to some
characters being more frequent than others, due to incorrect processing
of random bytes.
This can result in more easily guessable IDs, enabling some enumeration
of resources.
The crux of the vulnerability is that the RNG (as defined in
`detectPRNG`), generates a float by generating a random byte and
dividing by 255 (0xff). So, if the random byte is 0x00, it returns 0. If
the byte is 0x01, it returns ~0.0039, and so on, until if the random
byte is 0xff, it returns 1.
Thus, the float returned could be [0, 1], rather than [0, 1) (as some
comments expect).
For reference, The whole list of possible outputs of the rng function
returned by `detectPRNG` can be obtained by the following snippet:
```
const rngValues = Array.from(new Array(256), (_, idx) => (idx)/0xff);
> [0, 0.0039, …, 1]
```
As a result, the `randomChar` function (as used by `encodeRandom`) will
generate a bias, as it wraps around if the value is 1.
All possible randomPosition values are thus (where 32 is from
`ENCODING_LEN`):
```
const randomPositions = rngValues.map((v) => Math.floor(v * 32) % 32)
> [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, …, 31, 0]
```
If you take a look at the values of this array, you’ll notice that the
distribution isn’t equal:
```
randomPositions.reduce((acc, v) => {
if (!acc.has(v)) { acc.set(v, 0); }
acc.set(v, acc.get(v)+1);
return acc;
}, new Map());
> { 0 => 9, 1 => 8, 2 => 8, …, 30 => 8, 31 => 7 }
```
Therefore, it’s more likely to generate a ‘0’ character, than a ‘Z’
character, and thus will lead to bias, thus a lower entropy than
expected.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
See Commits and Changes for more details.
Created by
pull[bot] (v2.0.0-alpha.1)
Can you help keep this open source service alive? 💖 Please sponsor : )