4 ms·

Nothing in principle; it's the % operator that can biased the output. Also, outside the scope of Cordova apps, Node.js uses OpenSSL rather than /dev/urandom fo

Nothing in principle; it's the % operator that can biased the output. Also, outside the scope of Cordova apps, Node.js uses OpenSSL rather than /dev/urandom for their crypto.getRandomBytes() implementation, so I don't really trust it in that context. ;)

homakov 11y ago
% shouldn't decrease the entropy, modulo of random is still random.
- sarciszewski 11y ago
  If you generate 1000 random integers, but we know there's a 28% chance it will be 0 and a 14% chance it will be 1,2,3,4, or 5, a clever attacker can more accurately predict/brute force outputs. When you're working with cryptography, you want a uniform distribution of possible values as well as unpredictable randomness.
  - homakov 11y ago
    For 0..max random integer it depends on max and length. If max is 2^32 and 2^32 modulo charset.length = 0 it should be fine. Am I right? In our case length is 85 and it is indeed biased. Needs a pull request.
    - sarciszewski 11y ago
      Correct, that's the edge case where it actually falls together neatly. If you're starting with a random byte and charset.length is an even power of 2, you end up with no bias. It's better to design functions like this to discard values outside of an acceptable range and try again until they generate a safe value (also, apply a & bit mask to reduce the number of retries). This allows you to accept any arbitrary charset size without being concerned about security. See also: https://github.com/paragonie/random_compat/blob/5aa6689651a58a1f97e87d9e1188e5d90c871cc3/lib/random.php#L393-L447 https://github.com/paragonie/random_compat/blob/5aa6689651a5... I'll open a PR tonight if nobody beats me to it.
      - homakov 11y ago
        In theory, haha. In practice it gives me some numbers twice more. [2001954, 1000322, 998546, 1001551, 999105, 2000886, 998760, 998705, 1000001, 998424, 1000978, 2000907, 1002097, 998786, 1000101, 998818, 1000381, 1999818, 999662, 1001260, 999531, 1000076,
        sarciszewski 11y ago
        Your RNG is not cryptographically secure, I'd wager. http://3v4l.org/DC0RM http://3v4l.org/DC0RM
        homakov 11y ago
        I thought instead of cutting off out of range results we could num*85/4294967296 and round it. But now realized buckets for rounding won't be of equal size and it's wrong.
      - homakov 11y ago
        This also works i guess max = 100 length = 85 num = rand(max) puts (num * length)/max
- dchest 11y ago
  Entropy is maximized when the distribution probability is uniform. A biased random sequence has less entropy than the one of the same length which has uniform distribution. Here's an example from Wikipedia (https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Modulo_bias https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#M...) "For example, assume that your random number source gives numbers from 0 to 99 (as was the case for Fisher and Yates' original tables), and that you wish to obtain an unbiased random number from 0 to 15. If you simply divide the numbers by 16 and take the remainder, you'll find that the numbers 0–3 occur about 17% more often than others. This is because 16 does not evenly divide 100: the largest multiple of 16 less than or equal to 100 is 6×16 = 96, and it is the numbers in the incomplete range 96–99 that cause the bias. The simplest way to fix the problem is to discard those numbers before taking the remainder and to keep trying again until a number in the suitable range comes up. While in principle this could, in the worst case, take forever, the expected number of retries will always be less than one."
  - deleted 11y ago
    [deleted]
  - DanBC 11y ago
    This is one of the bugs found in CryptoCat. http://tobtu.com/decryptocat.php http://tobtu.com/decryptocat.php
- homakov 11y ago
  ^ hopefully i didn't sound too confident! Thanks for explanations.
- d0mine 11y ago
  To see the bias compare the last two pictures https://www.wakari.io/sharing/bundle/jfs/Test%20PRNG%20using%20gray%20bitmap https://www.wakari.io/sharing/bundle/jfs/Test%20PRNG%20using... From http://stackoverflow.com/questions/16829183/what-is-pseudo-random http://stackoverflow.com/questions/16829183/what-is-pseudo-r...
daviddahl 11y ago
Encryptr does not ue node.js crypto at all. Just Blink and Webkit's getRandomValues, which is secure
- sarciszewski 11y ago
  Yep, this is why I prefaced my statement with "outside the scope of Cordova apps".

homakov 11y ago

% shouldn't decrease the entropy, modulo of random is still random.

sarciszewski 11y ago
If you generate 1000 random integers, but we know there's a 28% chance it will be 0 and a 14% chance it will be 1,2,3,4, or 5, a clever attacker can more accurately predict/brute force outputs. When you're working with cryptography, you want a uniform distribution of possible values as well as unpredictable randomness.
- homakov 11y ago
  For 0..max random integer it depends on max and length. If max is 2^32 and 2^32 modulo charset.length = 0 it should be fine. Am I right? In our case length is 85 and it is indeed biased. Needs a pull request.
  - sarciszewski 11y ago
    Correct, that's the edge case where it actually falls together neatly. If you're starting with a random byte and charset.length is an even power of 2, you end up with no bias. It's better to design functions like this to discard values outside of an acceptable range and try again until they generate a safe value (also, apply a & bit mask to reduce the number of retries). This allows you to accept any arbitrary charset size without being concerned about security. See also: https://github.com/paragonie/random_compat/blob/5aa6689651a58a1f97e87d9e1188e5d90c871cc3/lib/random.php#L393-L447 https://github.com/paragonie/random_compat/blob/5aa6689651a5... I'll open a PR tonight if nobody beats me to it.
    - homakov 11y ago
      In theory, haha. In practice it gives me some numbers twice more. [2001954, 1000322, 998546, 1001551, 999105, 2000886, 998760, 998705, 1000001, 998424, 1000978, 2000907, 1002097, 998786, 1000101, 998818, 1000381, 1999818, 999662, 1001260, 999531, 1000076,
      - sarciszewski 11y ago
        Your RNG is not cryptographically secure, I'd wager. http://3v4l.org/DC0RM http://3v4l.org/DC0RM
        homakov 11y ago
        I thought instead of cutting off out of range results we could num*85/4294967296 and round it. But now realized buckets for rounding won't be of equal size and it's wrong.
    - homakov 11y ago
      This also works i guess max = 100 length = 85 num = rand(max) puts (num * length)/max
dchest 11y ago
Entropy is maximized when the distribution probability is uniform. A biased random sequence has less entropy than the one of the same length which has uniform distribution. Here's an example from Wikipedia (https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Modulo_bias https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#M...) "For example, assume that your random number source gives numbers from 0 to 99 (as was the case for Fisher and Yates' original tables), and that you wish to obtain an unbiased random number from 0 to 15. If you simply divide the numbers by 16 and take the remainder, you'll find that the numbers 0–3 occur about 17% more often than others. This is because 16 does not evenly divide 100: the largest multiple of 16 less than or equal to 100 is 6×16 = 96, and it is the numbers in the incomplete range 96–99 that cause the bias. The simplest way to fix the problem is to discard those numbers before taking the remainder and to keep trying again until a number in the suitable range comes up. While in principle this could, in the worst case, take forever, the expected number of retries will always be less than one."
- deleted 11y ago
  [deleted]
- DanBC 11y ago
  This is one of the bugs found in CryptoCat. http://tobtu.com/decryptocat.php http://tobtu.com/decryptocat.php
homakov 11y ago
^ hopefully i didn't sound too confident! Thanks for explanations.
d0mine 11y ago
To see the bias compare the last two pictures https://www.wakari.io/sharing/bundle/jfs/Test%20PRNG%20using%20gray%20bitmap https://www.wakari.io/sharing/bundle/jfs/Test%20PRNG%20using... From http://stackoverflow.com/questions/16829183/what-is-pseudo-random http://stackoverflow.com/questions/16829183/what-is-pseudo-r...

daviddahl 11y ago

Encryptr does not ue node.js crypto at all. Just Blink and Webkit's getRandomValues, which is secure

sarciszewski 11y ago
Yep, this is why I prefaced my statement with "outside the scope of Cordova apps".