Add a 'secure' constructor to Random in dart:math returning a cryptographically

Add a 'secure' constructor to Random in dart:math returning a cryptographically
secure random generator which reads from the entropy source provided by the
embedder for every generated random value.
Add a test.
Fixes #1746.

R=lrn@google.com

Committed: https://github.com/dart-lang/sdk/commit/09954546fb3246c4476ee4a92c4b7bef73964756

[regis, 2015-10-12 22:22:53]

regis@google.com changed reviewers:
+ sethladd@google.com

[regis, 2015-10-13 20:38:57]

regis@google.com changed reviewers:
+ lrn@google.com

[Lasse Reichstein Nielsen, 2015-10-14 11:08:46]

lgtm

https://codereview.chromium.org/1398453004/diff/20001/runtime/lib/math.cc
File runtime/lib/math.cc (right):

https://codereview.chromium.org/1398453004/diff/20001/runtime/lib/math.cc#new...
runtime/lib/math.cc:211: "Entropy source is not setup"));
setup -> set up.

This message is directed at the embedder, but will be seen by the user.
The user can't set up an entropy source, and won't necessarily know what it is.

Maybe: "No source of cryptographically secure random numbers available"

https://codereview.chromium.org/1398453004/diff/20001/runtime/lib/math_patch....
File runtime/lib/math_patch.dart (right):

https://codereview.chromium.org/1398453004/diff/20001/runtime/lib/math_patch....
runtime/lib/math_patch.dart:184: // No local optimizations needed for this
rather slow call.
Really?

How about only asking for the number of bytes you need, so for nextInt(2), you
don't have to waste three bytes of entropy.

(Would it make sense to save unused entropy in the class, so eight consecutive
nextBool calls wouldn't need to use more than one byte of entropy?)

https://codereview.chromium.org/1398453004/diff/20001/runtime/lib/math_patch....
runtime/lib/math_patch.dart:186: throw new ArgumentError("max must be positive
and < 2^32: $max");
< 2^32 should be <= 2^32

Use a range error for this.:

  throw new RangeError.range(max, 0, _POW2_32, "max", "Must be positive and <=
2^32");

https://codereview.chromium.org/1398453004/diff/20001/runtime/lib/math_patch....
runtime/lib/math_patch.dart:193: } while ((rnd32 - result + max) >= _POW2_32);
Should >= be > ?
If max is a power of 2 and rnd32 is (2^32 - max) then the result should be fine,
but this test rejects it and loops.
It's safe but slower than necessary.

https://codereview.chromium.org/1398453004/diff/20001/sdk/lib/_internal/js_ru...
File sdk/lib/_internal/js_runtime/lib/math_patch.dart (right):

https://codereview.chromium.org/1398453004/diff/20001/sdk/lib/_internal/js_ru...
sdk/lib/_internal/js_runtime/lib/math_patch.dart:66: throw new
UnsupportedError("Unsupported secure random generator");
No need to write "unsupported" in the message too, the error's toString prefixes
the message with "Unsupported operation: ".

https://codereview.chromium.org/1398453004/diff/20001/sdk/lib/math/random.dart
File sdk/lib/math/random.dart (right):

https://codereview.chromium.org/1398453004/diff/20001/sdk/lib/math/random.dar...
sdk/lib/math/random.dart:29: * The generator reads from the entropy source to
generate every
the entropy source -> an entropy source
(there is no description of which entropy source it is, so using a definite
pronoun is confusing - it makes me think I should know what it is talking
about).
Or better, drop the entire sentence - it's an implementation detail.
The user does no need to know that you are using "entropy" from somewhere (which
is just a fancy word for "random bits"). The returned random number generator is
cryptographically secure, that's all you need to know.
Well, maybe we should say what "cryptographically secure" means in this context
- I wouldn't trust something just because it calls itself cryptographically
secure, for all I know it could be implemented by amateurs who thinks xoring
with timestamps is safe. What are the guarantees provided by using this RNG?

I'm not sure an embedded device is able to implement this safely.
What should an implementation do if it doesn't have access to cryptographically
secure entropy? Should it throw an UnsupportedError?
That seems safer than falling back on something insecure.
So, maybe add to docs: If the program cannot provide a cryptographically secure
source of random numbers, it throws an [UnsupportedError].


Are we absolutely sure we want this in dart:math.

https://codereview.chromium.org/1398453004/diff/20001/tests/lib/math/random_s...
File tests/lib/math/random_secure_test.dart (right):

https://codereview.chromium.org/1398453004/diff/20001/tests/lib/math/random_s...
tests/lib/math/random_secure_test.dart:16:
Expect.isFalse(results.contains(intVal));
This is not a test of randomness.
It's just a flaky test with a very long expected period between failures.
That is, if the test fails, it's not showing an actual error. Only if a long
sequence of test runs have too many failures is it a sign that the randomness
isn't random enough.

The odds of collisions in 10 elements out of 10'000'000 values is ... (looking
up birthday paradox) ... ~5e-7.

We won't be able to detect whether it fails significantly more often than once
per 2M runs, unless it is extremely often. If we see a failure, there is no
rational action to take, so the failure will be ignored and so the test might as
well not be here.

I'm not sure what is a good way to test randomness (some proper randomness tests
testing specific properties of the distribution over a long period might work),
but being random is about lacking some properties in general (and
cryptographically secure even more so), but any test will fail eventually for a
specific run of any proper random generator.

https://codereview.chromium.org/1398453004/diff/20001/tests/lib/math/random_s...
tests/lib/math/random_secure_test.dart:19:
Expect.isFalse(results.contains(doubleVal));
I wouldn't check doubles in the same loop as the integers, or even on the same
RNG.

https://codereview.chromium.org/1398453004/diff/20001/tests/lib/math/random_s...
tests/lib/math/random_secure_test.dart:22: }
Basically, there is no need to make a new test. Use whatever test we already
have for the non-CS RNG and run it on the CSRNG as well.
If it was good enough before, then it probably still is (or at least it's no
worse).

[regis, 2015-10-14 20:22:36]

Thank you, Lasse.

PTAL

https://codereview.chromium.org/1398453004/diff/20001/runtime/lib/math.cc
File runtime/lib/math.cc (right):

https://codereview.chromium.org/1398453004/diff/20001/runtime/lib/math.cc#new...
runtime/lib/math.cc:211: "Entropy source is not setup"));
On 2015/10/14 11:08:45, Lasse Reichstein Nielsen wrote:
> setup -> set up.
> 
> This message is directed at the embedder, but will be seen by the user.
> The user can't set up an entropy source, and won't necessarily know what it
is.
> 
> Maybe: "No source of cryptographically secure random numbers available"

Done.

https://codereview.chromium.org/1398453004/diff/20001/runtime/lib/math_patch....
File runtime/lib/math_patch.dart (right):

https://codereview.chromium.org/1398453004/diff/20001/runtime/lib/math_patch....
runtime/lib/math_patch.dart:184: // No local optimizations needed for this
rather slow call.
On 2015/10/14 11:08:45, Lasse Reichstein Nielsen wrote:
> Really?
> 
> How about only asking for the number of bytes you need, so for nextInt(2), you
> don't have to waste three bytes of entropy.
> 
> (Would it make sense to save unused entropy in the class, so eight consecutive
> nextBool calls wouldn't need to use more than one byte of entropy?)

By "slow", I meant it is a call to the runtime, so the local optimization done
in class _Random is not worth doing here. I removed the comment.

Good point about only asking for the minimum number of bytes needed.
Done.

https://codereview.chromium.org/1398453004/diff/20001/runtime/lib/math_patch....
runtime/lib/math_patch.dart:186: throw new ArgumentError("max must be positive
and < 2^32: $max");
On 2015/10/14 11:08:45, Lasse Reichstein Nielsen wrote:
> < 2^32 should be <= 2^32
> 
> Use a range error for this.:
> 
>   throw new RangeError.range(max, 0, _POW2_32, "max", "Must be positive and <=
> 2^32");

Done here and in class _Random above.
The inclusive lower bound is actually 1.

https://codereview.chromium.org/1398453004/diff/20001/runtime/lib/math_patch....
runtime/lib/math_patch.dart:193: } while ((rnd32 - result + max) >= _POW2_32);
On 2015/10/14 11:08:45, Lasse Reichstein Nielsen wrote:
> Should >= be > ?
> If max is a power of 2 and rnd32 is (2^32 - max) then the result should be
fine,
> but this test rejects it and loops.
> It's safe but slower than necessary.

Agreed.
Actually, it made it impossible to use a max of 1 << 32. I am surprised that no
one complained about it (same bug in class _Random).
I fixed it and also updated the wrong comment about the range of max in the API.

https://codereview.chromium.org/1398453004/diff/20001/sdk/lib/_internal/js_ru...
File sdk/lib/_internal/js_runtime/lib/math_patch.dart (right):

https://codereview.chromium.org/1398453004/diff/20001/sdk/lib/_internal/js_ru...
sdk/lib/_internal/js_runtime/lib/math_patch.dart:66: throw new
UnsupportedError("Unsupported secure random generator");
On 2015/10/14 11:08:45, Lasse Reichstein Nielsen wrote:
> No need to write "unsupported" in the message too, the error's toString
prefixes
> the message with "Unsupported operation: ".

Done.
I used the message you suggested for the VM:
No source of cryptographically secure random numbers available.

https://codereview.chromium.org/1398453004/diff/20001/sdk/lib/math/random.dart
File sdk/lib/math/random.dart (right):

https://codereview.chromium.org/1398453004/diff/20001/sdk/lib/math/random.dar...
sdk/lib/math/random.dart:29: * The generator reads from the entropy source to
generate every
On 2015/10/14 11:08:45, Lasse Reichstein Nielsen wrote:
> the entropy source -> an entropy source
> (there is no description of which entropy source it is, so using a definite
> pronoun is confusing - it makes me think I should know what it is talking
> about).
> Or better, drop the entire sentence - it's an implementation detail.

Dropped.

> The user does no need to know that you are using "entropy" from somewhere
(which
> is just a fancy word for "random bits"). The returned random number generator
is
> cryptographically secure, that's all you need to know.
> Well, maybe we should say what "cryptographically secure" means in this
context
> - I wouldn't trust something just because it calls itself cryptographically
> secure, for all I know it could be implemented by amateurs who thinks xoring
> with timestamps is safe. What are the guarantees provided by using this RNG?
> 
> I'm not sure an embedded device is able to implement this safely.
> What should an implementation do if it doesn't have access to
cryptographically
> secure entropy? Should it throw an UnsupportedError?
> That seems safer than falling back on something insecure.
> So, maybe add to docs: If the program cannot provide a cryptographically
secure
> source of random numbers, it throws an [UnsupportedError].

Added.

> 
> 
> Are we absolutely sure we want this in dart:math.

It is what the bug report wanted.
Now, the plan is to expand the crypto package. We may revisit then.
But it is good to have a hook here, since people looking for a random generator
may see the secure one and use it for their cryptographic application.

https://codereview.chromium.org/1398453004/diff/20001/tests/lib/math/random_s...
File tests/lib/math/random_secure_test.dart (right):

https://codereview.chromium.org/1398453004/diff/20001/tests/lib/math/random_s...
tests/lib/math/random_secure_test.dart:16:
Expect.isFalse(results.contains(intVal));
On 2015/10/14 11:08:45, Lasse Reichstein Nielsen wrote:
> This is not a test of randomness.
> It's just a flaky test with a very long expected period between failures.
> That is, if the test fails, it's not showing an actual error. Only if a long
> sequence of test runs have too many failures is it a sign that the randomness
> isn't random enough.
> 
> The odds of collisions in 10 elements out of 10'000'000 values is ... (looking
> up birthday paradox) ... ~5e-7.
> 
> We won't be able to detect whether it fails significantly more often than once
> per 2M runs, unless it is extremely often. If we see a failure, there is no
> rational action to take, so the failure will be ignored and so the test might
as
> well not be here.
> 
> I'm not sure what is a good way to test randomness (some proper randomness
tests
> testing specific properties of the distribution over a long period might
work),
> but being random is about lacking some properties in general (and
> cryptographically secure even more so), but any test will fail eventually for
a
> specific run of any proper random generator.

Acknowledged.
I just copied code from random_big_test.dart, which is even more flaky, given
the smaller max.
The idea here is only to detect a totally broken implementation that would
always return the same value.

https://codereview.chromium.org/1398453004/diff/20001/tests/lib/math/random_s...
tests/lib/math/random_secure_test.dart:19:
Expect.isFalse(results.contains(doubleVal));
On 2015/10/14 11:08:46, Lasse Reichstein Nielsen wrote:
> I wouldn't check doubles in the same loop as the integers, or even on the same
> RNG.

Done.

https://codereview.chromium.org/1398453004/diff/20001/tests/lib/math/random_s...
tests/lib/math/random_secure_test.dart:22: }
On 2015/10/14 11:08:46, Lasse Reichstein Nielsen wrote:
> Basically, there is no need to make a new test. Use whatever test we already
> have for the non-CS RNG and run it on the CSRNG as well.
> If it was good enough before, then it probably still is (or at least it's no
> worse).

One existing test checks that the sequence is deterministic given the same seed
(not applicable here). The other test (that I copied from) checks that a big
seed is allowed (no seed here). 

I prefer to have a new test, so I can mark it as failing for dart2js. Making the
existing one a multi-test requires even more fiddling with the status files.

I added a comment to the new test explaining that it is flaky by definition, but
still better than no test.

[Lasse Reichstein Nielsen, 2015-10-15 09:32:33]

lgtm

https://codereview.chromium.org/1398453004/diff/40001/runtime/lib/math_patch....
File runtime/lib/math_patch.dart (right):

https://codereview.chromium.org/1398453004/diff/40001/runtime/lib/math_patch....
runtime/lib/math_patch.dart:185: if ((max <= 0) || (max > _POW2_32)) {
This can be reduced to:
  RangeError.checkValueInInterval(max, 1, _POW2_32, "max",
                                  "Must be positive and <= 2^32");
if you want to save a little space (but probably lose a little performance if
the call isn't inlined).

https://codereview.chromium.org/1398453004/diff/40001/runtime/lib/math_patch....
runtime/lib/math_patch.dart:198: } while ((rnd - result + max) > _POW2_32);
The limit should be  0x100 << byteCount  when you fetch less than four bytes.

https://codereview.chromium.org/1398453004/diff/40001/tests/lib/math/random_s...
File tests/lib/math/random_secure_test.dart (right):

https://codereview.chromium.org/1398453004/diff/40001/tests/lib/math/random_s...
tests/lib/math/random_secure_test.dart:34: checkInt(1 << (32 - i));
Does it even make sense to call for i < (1<<28) - the checkInt doesn't check
anything in that case.

https://codereview.chromium.org/1398453004/diff/40001/tests/lib/math/random_s...
tests/lib/math/random_secure_test.dart:48: rng1 = new Random.secure();
You could just make checkDouble create the new rng1 as a local variable.

https://codereview.chromium.org/1398453004/diff/40001/tests/lib/math/random_t...
File tests/lib/math/random_test.dart (right):

https://codereview.chromium.org/1398453004/diff/40001/tests/lib/math/random_t...
tests/lib/math/random_test.dart:59: Expect.equals( 1552504971, rnd.nextInt(i));
Why? We already called with that value of max above.

[regis, 2015-10-15 17:12:02]

Thanks!

https://codereview.chromium.org/1398453004/diff/40001/runtime/lib/math_patch....
File runtime/lib/math_patch.dart (right):

https://codereview.chromium.org/1398453004/diff/40001/runtime/lib/math_patch....
runtime/lib/math_patch.dart:185: if ((max <= 0) || (max > _POW2_32)) {
On 2015/10/15 09:32:33, Lasse Reichstein Nielsen wrote:
> This can be reduced to:
>   RangeError.checkValueInInterval(max, 1, _POW2_32, "max",
>                                   "Must be positive and <= 2^32");
> if you want to save a little space (but probably lose a little performance if
> the call isn't inlined).

Done. We have a runtime call below, so performance is not an issue.

https://codereview.chromium.org/1398453004/diff/40001/runtime/lib/math_patch....
runtime/lib/math_patch.dart:198: } while ((rnd - result + max) > _POW2_32);
On 2015/10/15 09:32:33, Lasse Reichstein Nielsen wrote:
> The limit should be  0x100 << byteCount  when you fetch less than four bytes.

Good catch. The correct limit is actually 1 << 8*byteCount.

https://codereview.chromium.org/1398453004/diff/40001/tests/lib/math/random_s...
File tests/lib/math/random_secure_test.dart (right):

https://codereview.chromium.org/1398453004/diff/40001/tests/lib/math/random_s...
tests/lib/math/random_secure_test.dart:34: checkInt(1 << (32 - i));
On 2015/10/15 09:32:33, Lasse Reichstein Nielsen wrote:
> Does it even make sense to call for i < (1<<28) - the checkInt doesn't check
> anything in that case.

It makes sure that we can generate random values with a large max without
crashing or looping forever.

https://codereview.chromium.org/1398453004/diff/40001/tests/lib/math/random_s...
tests/lib/math/random_secure_test.dart:48: rng1 = new Random.secure();
On 2015/10/15 09:32:33, Lasse Reichstein Nielsen wrote:
> You could just make checkDouble create the new rng1 as a local variable.

Sure. I prefer to keep the symmetry with other tests.

https://codereview.chromium.org/1398453004/diff/40001/tests/lib/math/random_t...
File tests/lib/math/random_test.dart (right):

https://codereview.chromium.org/1398453004/diff/40001/tests/lib/math/random_t...
tests/lib/math/random_test.dart:59: Expect.equals( 1552504971, rnd.nextInt(i));
On 2015/10/15 09:32:33, Lasse Reichstein Nielsen wrote:
> Why? We already called with that value of max above.

Aargh. Left over from debugging. Reverted.

I was trying to figure out why is this test not failing, since we have the wrong
check in nextInt:
(rnd32 - result + max) >= _POW2_32
instead of
(rnd32 - result + max) > _POW2_32

The reason it succeeds is that we use another code path if max is a power of 2.

[regis, 2015-10-15 17:16:08]

Committed patchset #4 (id:60001) manually as
09954546fb3246c4476ee4a92c4b7bef73964756 (presubmit successful).