Entropy

A seeded generator is predictable by design: anyone who learns the seed can replay every number it will ever produce. For a simulation that is a feature. For a session token, a password salt or an encryption key it is a disaster — those numbers must be ones nobody can guess, so they cannot come from arithmetic inside the program.

They come from outside it. The operating system collects unpredictability — entropy — from hardware and from the timing of events, and the Entropy package asks it for some:

import Entropy::{ EntropyError, Fill, NextUint64 };
import Random::{ Pcg64Dxsm, PcgFromEntropy, UniformBelow };

The output is different on every run, and that is exactly what this lesson is about.

Every request can fail

Asking the system can fail: it may have no source, the request may be interrupted, or the system may simply refuse. So every function here is fallible, with an EntropyError enum saying why:

The whole point of these numbers is that nobody can guess them. A failure quietly replaced by some fixed value — a catch that answers 0 — would produce a "random" key that is the same on every machine. So the program checks every call and stops if one fails.

Describe turns the reason into words, and IsTransient says whether asking again might help:

func Describe(error: EntropyError) {
    let why = match error {
        EntropyError::Unsupported => "this system has no entropy source",
        EntropyError::Interrupted => "the request was interrupted",
        EntropyError::Failed => "the system refused",
        EntropyError::TooLarge => "too many bytes in one request"
    };
    // `IsTransient` says whether asking again might help. Only an interruption is worth a retry.
    PrintLine("no entropy: {} (worth retrying: {})", why, error.IsTransient());
}

One number

NextUint64 is the simplest request. A match on its outcome prints the value, or describes the failure and ends the program with status 1:

match NextUint64() {
    .Success(value) => PrintLine("a 64-bit value  {:#018x}", value),
    .Failure(error) => {
        Describe(error);
        return 1;
    }
}

{:#018x} prints it in hexadecimal with a 0x prefix, padded with zeros to 18 characters — the prefix and all 16 digits.

A buffer of bytes

A key is usually a run of bytes rather than one number. Fill writes as many bytes as you ask for into memory you provide, so it takes a pointer to the first byte and a count:

var key: byte[16] = [0; 16];
Fill(@key[0] as *var opaque, 16) catch {
    error => {
        Describe(error);
        return 1;
    }
};

@key[0] is the address of the first byte. Fill takes the buffer as *var opaque — a writable pointer to bytes of any type — because it neither knows nor cares what the bytes will be used for. It also cannot see how big the buffer is: the count you pass is all it has, so it must match the array.

The catch here names the error, error => { … }, so the arm can pass it to Describe.

The common use: an unguessable seed

Every request for entropy is a call into the operating system, while a generator makes a number in a few instructions — and a program rarely needs all its numbers to be unguessable. The usual pattern takes a little entropy once, as a seed, and then draws from a fast generator as in Distribution:

var generator = PcgFromEntropy() catch {
    error => {
        Describe(error);
        return 1;
    }
};
PrintLine("a die roll      {}", UniformBelow<Pcg64Dxsm>(generator, 6) + 1);

flowchart LR
    os(["Operating system<br/>hardware and timing"]) -- "NextUint64, Fill" --> v["Unguessable values:<br/>keys, tokens, salts"]
    os -- "PcgFromEntropy" --> g["Pcg64Dxsm with an<br/>unguessable seed"]
    g -- "UniformBelow, Shuffle, …" --> d["Fast draws that<br/>differ every run"]

Every run now rolls differently — and the program has given up the ability to replay a run, because nobody knows the seed.

The program

The whole lesson is one package in the Examples repository. Its comments explain every step.

// A seeded generator is predictable by design: anyone who learns the seed can replay it. When
// the numbers must be unguessable, such as a session token, a password salt, or the seed for a
// simulation that should differ every run, they have to come from outside the program.
//
// The operating system collects unpredictability from hardware and timing, and the Entropy
// package asks it for some. `NextUint64()` returns `uint64 ! EntropyError` and `Fill` fills a
// buffer, returning `! EntropyError`. Asking can fail (a system may have no source, or the
// request may be interrupted), and since the whole point is that the bytes are unguessable, a
// failure must never be quietly replaced by some fixed value. So every call here is checked.
//
// The output is different on every run, which is exactly what this lesson is about.
import Entropy::{ EntropyError, Fill, NextUint64 };
import Io::{ Print, PrintLine };
import Random::{ Pcg64Dxsm, PcgFromEntropy, UniformBelow };

func Describe(error: EntropyError) {
    let why = match error {
        EntropyError::Unsupported => "this system has no entropy source",
        EntropyError::Interrupted => "the request was interrupted",
        EntropyError::Failed => "the system refused",
        EntropyError::TooLarge => "too many bytes in one request"
    };
    // `IsTransient` says whether asking again might help. Only an interruption is worth a retry.
    PrintLine("no entropy: {} (worth retrying: {})", why, error.IsTransient());
}

func Main() -> int {
    // One unpredictable 64-bit number.
    match NextUint64() {
        .Success(value) => PrintLine("a 64-bit value  {:#018x}", value),
        .Failure(error) => {
            Describe(error);
            return 1;
        }
    }

    // Sixteen unpredictable bytes, written into a buffer through a pointer.
    var key: byte[16] = [0; 16];
    Fill(@key[0] as *var opaque, 16) catch {
        error => {
            Describe(error);
            return 1;
        }
    };
    Print("a 16-byte key  ");
    for b in key {
        Print(" {:02x}", b);
    }
    PrintLine();

    // The common use: seed a fast generator once from entropy, then draw from it as usual.
    // `PcgFromEntropy` returns `Pcg64Dxsm ! EntropyError`, so the seeding is checked too.
    var generator = PcgFromEntropy() catch {
        error => {
            Describe(error);
            return 1;
        }
    };
    PrintLine("a die roll      {}", UniformBelow<Pcg64Dxsm>(generator, 6) + 1);
    return 0;
}

Besides Io, its Rux.toml lists Entropy and Random under [Dependencies].

Run it

cd Examples/Utilities/Entropy
rux run

a 64-bit value  0x0739b89787c9e4f2
a 16-byte key   2f ec 37 79 c3 31 0e 0f ba 9a a0 34 15 17 b9 b7
a die roll      6

This is a sample: every value is different on each run.

This is a sample: every value is different on each run, and so is the die roll.

Common mistakes

Try it yourself

1. Run the program three times. Which lines change?
2. Make the key 32 bytes long. What else has to change besides the array's size?
3. Replace PcgFromEntropy() with Pcg64Dxsm(2026) (no catch needed — it cannot fail) and run twice. What happens to the die roll?
4. Leave out one arm of the match in Describe and read the compiler's message.

Learn more

• Random and Distribution — the generator that PcgFromEntropy seeds
• Pointer — the address Fill writes through
• Catch — recovering from a failure, and naming it with error =>
• Password — a checkpoint project that builds a password from entropy
• UUID — random identifiers made from the same source