[swift-evolution] [Proposal] Random Unification

[Jonathan Hull]

> On Sep 26, 2017, at 7:31 AM, Xiaodi Wu <xiaodi.wu at gmail.com> wrote:
> 
> Felix and Jonathan make some good points. Some general comments:
> 
> * I think, in general, this area needs a detailed review by those who are expert in the domain; especially if we are to assert that the design is cryptographically secure, we need to ensure that it is actually so. In other words, not just the algorithms that we intend to implement, but the implementations themselves. This is not at all trivial. We will also need to specify whether extension methods that generate certain distributions, etc., are guaranteed secure against side channel attacks where such implementations are known possible but more expensive.
> 
> * Without attempting to bikeshed, the use of the word “Source” is potentially confusing; it could suggest that the conforming type is a source of entropy when in fact it consumes entropy. In my proposed design, the protocol is simply named “PRNG” with an emphasis on the P (i.e. pseudorandom, not random).

This is a good point.  My use of the word “source" in the code I shared (much) earlier is because I have a “Source” protocol which essentially represents an (effectively) infinite iterator/sequence.  RandomSource is a specific sub-protocol I have which provides an infinite iterator/sequence for repeatably random numbers.  There are other sources which take an array and cycle it’s indices, for example.  I also have a constant source, which always returns the same thing.  I use all of this to do cool generative graphical effects.

>> We would give developers a false sense of security if we provided them with CSPRNG-grade algorithms that we called CSPRNGs and that they could seed themselves. Just because it says "crypto-secure" in the name doesn't mean that it'll be crypto-secure if it's seeded with time(). Therefore, "reproducible" vs "non-reproducible" looks like a good distinction to me.

> I disagree here, in two respects:
> 
> First, whether or not a particular PRNG is cryptographically secure is an intrinsic property of the algorithm; whether it's "reproducible" or not is determined by the published API. In other words, the distinction between CSPRNG vs. non-CSPRNG is important to document because it's semantics that cannot be deduced by the user otherwise, and it is an important one for writing secure code because it tells you whether an attacker can predict future outputs based only on observing past outputs. "Reproducible" in the sense of seedable or not is trivially noted by inspection of the published API, and it is rather immaterial to writing secure code. If your attacker can observe your seeding once, chances are that they can observe your reseeding too; then, they can use their own implementation of the PRNG (whether CSPRNG or non-CSPRNG) and reproduce your pseudorandom sequence whether or not Swift exposes any particular API.
> 
> Secondly, I see no reason to justify the notion that, simply because a PRNG is cryptographically secure, we ought to hide the seeding initializer (because one has to exist internally anyway) from the public.


To me, ReproducibleRandomSource has a semantic meaning (more than being a bag of methods).  It has an init(seed:) method because you HAVE to be able to seed it for reproducibility (not because sources which have a seed would all be reproducible).  The fact that RandomSource does not have that requirement doesn’t mean you can’t have a source which is seeded… it just allows for sources which aren’t.  If something calls itself Reproducible, it should actually be reproducible, which includes being able to restore previous states (not just the starting seed).


> * The distinction to be made here is CSPRNGs versus non-cryptographically secure PRNGs, where CSPRNG : PRNG. “Reproducible” is not the right word. Based on my understanding, some CSPRNGs can be “reproducible” if the seed is known; what makes it cryptographically secure is that observing its previous *outputs* does not provide information useful to predict future outputs. Along those lines, it may be important to securely delete the seed from memory as soon as possible; there is some way of doing so in C (it’s used in the ChaCha20 reference implementation) but I don’t believe any way of doing so in Swift.

Is CSPRNG vs PRNG really an important distinction for the API?  It is an important distinction when choosing a source, of course, but should that be reflected in our protocols?  We should definitely make sure that our API does not prevent secure/CSPRNGs from working (e.g. not requiring a seed in the base API).

Reproducible, on the other hand, is a completely different use-case, which requires a different API because it is used differently. We also need to make sure our protocol design does not preclude or make difficult these uses.  (We just want to avoid people using them while thinking they are secure).

We should default to something reasonably secure, but also fast.  People who are doing cryptography should be using a cryptography package… but that package should be able to plug seamlessly into whatever API we have created.

I am leaning towards a design with an abstract base protocol, and then sub-protocols for Reproducibility and Secureness.



> * On the issue of consuming entropy: a glaring underlying inconvenience in the API needs to be reckoned with. Sometimes, there simply isn’t enough entropy to generate another random number. If cryptographic security were not default, then it might be OK to fall back to some other method that produces a low-quality result. However, if we are to do the secure thing, we must decide whether the lack of entropy results in a call to a random method to (a) return nil; (b) throw; (c) fatalError; or (d) block. There is no way to paper over this problem; not enough entropy means you can’t get a random number when you want it. The debate over blocking versus non-blocking error, for example, held up the addition of getrandom() to Glibc for some time. In my proposed design, initializing a PRNG from the system’s secure stream of random bytes is failable; therefore, a user can choose how to handle the lack of entropy. However, it is desirable to have a thread-local CSPRNG that is used for calls, say, to Int.random(). It would be unfortunate if Int.random() itself was failable; however, that leads to an uncomfortable question: if there is insufficient entropy, should Int.random() block or fatalError? That seems pretty terrible too. However, one cannot simply write this off as an edge case: if this is to be a robust part of the standard library, it must do the “right” thing. Particularly if Swift is to be a true systems programming language and it must accommodate the case when a system is first booted and there is very little entropy.

Agreed.  I have an API (for non-cryptographic use) that has two methods of getting unique random objects.  One is failable, and returns nil if the object can’t be shown to be unique.  The other tries to get a unique object, but will give repeats if necessary… it always returns a thing.

We could do something similar with entropy.  We could have either an optional or throwing function which returns our random number.  A sub-protocol could define a version (with a different name) that is non-optional which will always return an answer, even at the risk of being less secure.


Thanks,
Jon