Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Deprecate Random() default constructor, replace with Random.insecure() #59715

Open
natebosch opened this issue Dec 13, 2024 · 12 comments
Open

Deprecate Random() default constructor, replace with Random.insecure() #59715

natebosch opened this issue Dec 13, 2024 · 12 comments
Labels
area-core-library SDK core library issues (core, async, ...); use area-vm or area-web for platform specific libraries. library-math

Comments

@natebosch
Copy link
Member

natebosch commented Dec 13, 2024

Using an insecure seed for a random source is the wrong choice for many typical uses of random input. It would be easier to catch misuse if the constructor had a more obvious name. The default constructor, if anything, should be the safer version. If we think we can get away with changing behavior for current usage we could change the unnamed constructor to secure and add and insecure name constructor. If we think changing behavior is too risky (I lean this way) we can keep both named for the long term and deprecate the unnamed.

@lrhn what do you think?

@natebosch natebosch added area-core-library SDK core library issues (core, async, ...); use area-vm or area-web for platform specific libraries. library-math labels Dec 13, 2024
@jakemac53
Copy link
Contributor

+1 for just deprecating the unnamed constructor and making users choose one.

@lrhn
Copy link
Member

lrhn commented Dec 13, 2024

I think it's an educational problem, but that it might not be a solvable problem.

It requires users to know that secure and insecure random generators exist, that they need a secure random generator for a particular problem, and that they should never assume a random generator to be secure unless it explicitly says that it is.

If they already know that, then they'll look for Random.secure. If they don't, we won't have many chances for education them.

Having the plain Random constructor be named .insecure is a hint towards the first and last point: insecure random generators exist, and this is one.

That won't necessarily help the user realize whether they need security or not, but if there are only two explicitly named constructors, they'll at least be aware that they are making a choice. Only they can know what the right choice is.

I don't use Random often enough to have a preference.
Adding Random.insecure and deprecating Random.new seems fine.
Or we can call it .fast instead, so you're choosing between fast and secure, which should hint that the other one isn't that.

We hould be aware that, fx, List.shuffle defaults to a fast Random.
Should we make that parameter required instead. It starts to become verbose then, rather than list.shuffle(), it's list.shuffle(Random.fast()), plus possibly adding an import of dart:math.
Not very convenient.
(Secure random generators can be orders of magnitude slower than insecure PRNGs. They are bad defaults too.)

Using an insecure seed for a random source is the wrong choice for many typical uses of random input

Really? Which?

If it's not security, then you are at most risking bad distribution. That can be a performance problem, but that can scale to denial-of-service levels of performance problems.

That probably won't be the only problem that code has. using secure random might just cause other performance issues.

(If it is security, then it's never going to be secure if it is written by someone who used the first random generator they found. I'd rather they leave in this big red flag, so I can recognize it, than they just as blindly uses Random.secure and think they're safe then.)

@natebosch
Copy link
Member Author

natebosch commented Dec 13, 2024

Or we can call it .fast instead, so you're choosing between fast and secure, which should hint that the other one isn't that.

I think I prefer insecure (or weak maybe?) over fast but either way would I think be better than the unnamed constructor.

See also naming suggestions and arguments for and against making the default secure vs fast at https://news.ycombinator.com/item?id=42406773

We hould be aware that, fx, List.shuffle defaults to a fast Random.
Should we make that parameter required instead. It starts to become verbose then, rather than list.shuffle(), it's list.shuffle(Random.fast()), plus possibly adding an import of dart:math.
Not very convenient.

I think it would make sense for us to use Random.insecure() explicitly in places like List.shuffle. I don't think that removing the default constructor means we also need to change which behavior is used in core libraries.

@natebosch
Copy link
Member Author

Really? Which?

Of particular interest today is ef5295d

@lrhn
Copy link
Member

lrhn commented Dec 13, 2024

If it's not security,

Well, it was security.

I'm reading the linked article on Hackernews. One refers to DTD with

but it is somewhat secured by binding to a random port and a generated, random secret

The port is not security (you can scan 65536 ports fast enough that it doesn't matter whether it's predictable). That's just trying to avoid collisions.

A predictable secret is a failure, because that should be secret and unpredictable.

Would that code have been written differently if the author had had to write Random.insecure?
Maybe. (I don't know if the original code was intended as the end-product, or a prototype that outlived its intent.)
(It's a process failure that the original unsafe code managed to ship.)

And relevantly, the SelfPrivacy example contains the code res.split('')..shuffle();, where someone shuffles (randomly generated) passphrase characters using at most 32 bits of entropy again. So shuffle might be worth looking at too.
You can still get a "fast shuffle" if you pass a Random.insecure to it.
(I don't think the shuffle would add any security, if the individual characters were chosen uniformly at random from the same set, shuffling them afterwards doesn't change the distribution at all. With the less secure character selection, it might have added a little extra randomness.)

Let's do the rename. Let's consider uses of Random in the libraries too.

Having a slightly higher chance of avoiding mistakes like this is probably worth a little extra hassle for people who just want fast random numbers. (They can make their own Random fstRnd([int? seed]) => Random.insecure(seed); and speed up their typing too!)

@jakemac53
Copy link
Contributor

jakemac53 commented Dec 13, 2024

I do think it should be explicitly named insecure or weak and not fast to directly indicate it should not be used to for anything security related.

I do believe that would have avoided the specific issue at hand. It is much more obvious in review too.

@Wdestroier
Copy link

In a few simulation games the random seed and the inputs are shared to generate the same output in different machines. That way the output doesn't need to be shared across the network.

Could "deterministic" be a good name or would it be too long and also weird to see shuffle calling this? I don't know if Dart holds this behavior for all platforms and processor architectures, I guess so.

import 'dart:math';

main() {
  final (seed, inputs) = (42, [10, 10, 10]);
  
  final random = Random(seed);
  print(inputs.map(random.nextInt)); // Always prints 7, 8, 4.
}

I thought calling Random() always returned the same object. It's very convenient to not need to create a new Random and decide whether to store it in a variable, reuse it across the entire library, across the entire package or only within the current function.

@lrhn
Copy link
Member

lrhn commented Dec 14, 2024

Some patterns use a different generator if you give it a seed, than if you don't.
The one with the seed is deterministic, the other one might not be.

Calling Random() more than once never gives you the same object. With the same seed, each new instance starts freshly from the same state.

(The Random.secure probably could use the same object since the state is external to the object.)

@lrhn
Copy link
Member

lrhn commented Dec 14, 2024

We can consider whether to change the Random.insecure implementation to something with more initial state, maybe using 64 bits of seed.

That prompts the question of where to get 64 bits of entropy from.
Using a microsecond now timer is fairly predictable already. The current behavior is that it is fast, has a decent period and distribution, but without another randomness source, the starting point is somewhat predictable, and the starting point generation has low entropy. So you always get one of 2^32 starting points in that longer period.

@sma
Copy link

sma commented Dec 16, 2024

For me, the surprising fact was not that the default constructor is cryptographically insecure (this is well documented), but that there are "only" 2^32 different streams of pseudo random numbers, and that the seed could be brute-forced in less than 10 seconds with a modern CPU. IMHO, you should document that the (explicit or implicit) seed is restricted to 32 bits – or losen that restriction.

@lrhn
Copy link
Member

lrhn commented Dec 16, 2024

We should probably document that this is a 32 bit RNG. It only emits 32 bits at a time (the doubles only have 32 significant bits, not 52).
The internal state only works to give it a longer period than 2^32.

Even if the seed had more bits of entropy (and I wouldn't assume the current one even has 32 bits of real entropy), you should still assume that it can be broken in 10 seconds or less. Maybe not by brute force, but by any number of other techniques to reverse a hash.

It's not secure, which means that you must assume that a dedicated opponent can create collisions, or reverse engineer at least some of the state, just by looking at the output.

If you worry about having collisions in your own code, like starting a lot of independent processes and expecting a low risk of collision, then I can see why a larger set of starting states is relevant.
(And we should consider if that's an option, at least if given a seed by the user, so that we don't have to find 64 bits of real entropy.)

Being breakable by a competent attacker isn't going to change. It's not secure against attacks.

@cpeterso
Copy link

Sounds like this issue is discussing three separate changes that could be implemented independently:

  1. Add an explicit insecure Random constructor. Name to be bike shedded.
  2. Change the Random() default constructor to use the secure RNG and maybe deprecate the default constructor.
  3. Upgrade the insecure RNG to a better function, e.g. use a 64 bit seed and internal state.
  4. Make the RNGs return doubles with 52 significant bits instead of 32.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
area-core-library SDK core library issues (core, async, ...); use area-vm or area-web for platform specific libraries. library-math
Projects
None yet
Development

No branches or pull requests

6 participants