[swift-evolution] [Proposal] Random Unification

Tue Sep 26 09:31:10 CDT 2017

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).

* 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.

* 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.

* What should the default CSPRNG be? There are good arguments for using a
cryptographically secure device random. (In my proposed implementation, for
device random, I use Security.framework on Apple platforms (because
/dev/urandom is not guaranteed to be available due to the sandbox, IIUC).
On Linux platforms, I would prefer to use getrandom() and avoid using file
system APIs, but getrandom() is new and unsupported on some versions of
Ubuntu that Swift supports. This is an issue in and of itself.) Now, a
number of these facilities strictly limit or do not guarantee availability
of more than a small number of random bytes at a time; they are recommended
for seeding other PRNGs but *not* as a routine source of random numbers.
Therefore, although device random should be available to users, it probably
shouldn’t be the default for the Swift standard library as it could have
negative consequences for the system as a whole. There follows the
significant task of implementing a CSPRNG correctly and securely for the
default PRNG.

* It is well settled, based on math and precedent in other languages such
as C++ and Python, that Int.random() should return a number between Int.min
and Int.max, inclusive, and that Float.random() should return a number in
the range 0..<1 (note the exclusive upper bound). There are good
mathematical reasons for this and computational ones, and having these two
primitives as well as raw random bytes allows the implementation of other
distributions. It is, however, not trivial to implement Float.random()
correctly so as never to generate the value 1. Of course, it should be
possible for people to get a random value in a range with a syntax such as
Int.random(in: 0...4), and this is trivial to implement on top of the
primitive standard uniform distribution.

* “Coin flip” is the Bernoulli distribution with p = 0.5 (i.e. a fair coin,
vs. coins biased towards heads or tails), which can be built trivially on
top of Float.random(). (This is one reason why Float.random() returns a
value in 0..<1; otherwise, heads would be slightly more or less likely than
tails if you tried to implement the Bernoulli distribution in this way.)
Similarly, there are good algorithms to implement the normal distribution.
I agree that both are probably common enough to merit inclusion in the
standard library in addition to the uniform distribution and raw random
bytes, but also agree with Chris that probably not much more than that
needs to be standard so long as existing facilities allow people to
implement their own.

I will reply at some later point with a proposed API taking into account
these points and comments above.

On Tue, Sep 26, 2017 at 06:59 Jonathan Hull via swift-evolution <
swift-evolution at swift.org> wrote:

> Instead of “UnsafeRandomSource”, I would call it
> “ReproducibleRandomSource”.  I have also found that you often need to be
> able to “rewind” a reproducible random source for graphics applications:
>
> protocol ReproducibleRandomSource : RandomSource {
> init(seed: UInt64)
> func mark()->Int
> func returnToMark(_ mark:Int) //These could use something like an index
> instead of Int. My version just returns 1 the first time you call mark(), 2
> the second time, etc...
> }
>
> Also, I find that there are just a few primitive types I actually need
> from a random source:
>
> • Double (full coverage of possible values)
> • Double (in range of 0…1)
> • UInt32
>
> The following are also nice to have (built from the above), and commonly
> used:
>
> • Bool / CoinFlip
> • Int (positive value)
> • FixedWidthInteger (of various sizes.  Full coverage of possible values)
> • Character/String
> • CGFloat
>
> Any other type can be built from these building blocks.  I have a
> RandomSourceCreatable protocol which allows exactly that.  Once you have
> that, you can put a method on random source which allows you to create any
> conforming type:
>
> extension RandomSource {
> func next<T:RandomSourceCreatable>(_ type: T.Type)->T
> }
>
> This is extremely useful to create colors, offsets, etc…
>
> One thing we need to definitely consider are constraints which people may
> want on the random value.  For example, should an Int be positive?  Should
> it be in a certain range?  I have a “constraints” parameter on my
> RandomSourceCreatable protocol to handle this, and it works well, but I am
> not 100% happy with the ergonomics.  I also have a variant with an “in
> range:” parameter that works for simple linear types like Ints and Floats.
> We could do something like:
>
> extension RandomSource {
> func next<T:RandomRangeCreatable>(_ type: T.Type, in range:
> ClosedRange<T>) -> T
> }
>
> Finally, don’t underestimate the usefulness of coinFlip and func oneIn(_
> number:UInt)->Bool.  They let you quickly branch based on a random value:
>
> if source.oneIn(100) { //This will be true roughly 1 in 100 times
> //Do something occasionally
> }
>
> Thanks,
> Jon
>
>
> On Sep 25, 2017, at 9:57 PM, Alejandro Alonso via swift-evolution <
> swift-evolution at swift.org> wrote:
>
> Hello evolution,
>
> I am very thankful for all the feedback, and I’ve been working on a design
> that tries to utilize everybody’s ideas. The link to what I have so far is
> here: https://gist.github.com/Azoy/15f0518df38df9b722d4cb17bafea4c1.
> Please keep in mind this is just a design, no actual implementation as I
> would most likely need assistance in doing. The default source for
> randomness will use the OS’s unseeded CSPRNG. This current setup exposes
> developers to an API that lets them create their own RandomSources on the
> fly. I want to make the distinction that any existing or new sources of
> randomness that conform to UnsafeRandomSource are to be considered non
> cryptographically secure.
>
> I would love to get this discussion flowing again, and I would love input
> on the design. A few things I came across with this design is that some may
> want to use ranges as an argument for the numeric types,
> RandomAccessCollection returning an optional when getting a random, and how
> to incorporate an API that allows distributions. I wanted to get input on
> how you feel about each of these topics as I’m indifferent about them all.
> I’m in no way saying this is the design we should go for, but I’m simply
> providing something I think we should build on or talk about.
>
> - Alejandro
>
> On Sep 8, 2017, 11:52 AM -0500, Alejandro Alonso via swift-evolution <
> swift-evolution at swift.org>, wrote:
>
> Hello swift evolution, I would like to propose a unified approach to
> `random()` in Swift. I have a simple implementation here
> https://gist.github.com/Azoy/5d294148c8b97d20b96ee64f434bb4f5. This
> implementation is a simple wrapper over existing random functions so
> existing code bases will not be affected. Also, this approach introduces a
> new random feature for Linux users that give them access to upper bounds,
> as well as a lower bound for both Glibc and Darwin users. This change would
> be implemented within Foundation.
>
> I believe this simple change could have a very positive impact on new
> developers learning Swift and experienced developers being able to write
> single random declarations.
>
> I’d like to hear about your ideas on this proposal, or any implementation
> changes if need be.
>
> - Alejando
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
>
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20170926/cf9b5862/attachment.html>