Post Syndicated from Cefan Daniel Rubin original https://blog.cloudflare.com/harnessing-office-chaos

In the children’s book The Snail and Whale, after an unexpectedly far-flung adventure, the principal character returns to declarations of “How time’s flown” and “Haven’t you grown?” It has been about four years since we last wrote about LavaRand and during that time the story of how Cloudflare uses physical sources of entropy to add to the security of the Internet has continued to travel and be a source of interest to many. What was initially just a single species of physical entropy source – lava lamps – has grown and diversified. We want to catch you up a little on the story of LavaRand. This blog post will cover the new sources of “chaos” that have been added to LavaRand and how you can make use of that harnessed chaos in your next application. We’ll cover how public randomness can open up uses of publicly trusted randomness — imagine not needing to take the holders of a “random draw” at their word when they claim the outcome is not manipulated in some way. And finally we’ll discuss timelock encryption which is a way to ensure that a message cannot be decrypted until some chosen time in the future.

LavaRand origins

The entropy sourced from our wall of lava lamps in San Francisco has long played its part in the randomness that secures connections made through Cloudflare.

Cloudflare’s servers collectively handle upwards of 55 million HTTP requests per second, the vast majority of which are secured via the TLS protocol to ensure authenticity and confidentiality. Under the hood, cryptographic protocols like TLS require an underlying source of secure randomness – otherwise, the security guarantees fall apart.

Secure randomness used in cryptography needs to be computationally indistinguishable from “true” randomness. For this, it must both pass statistical randomness tests, and the output needs to be unpredictable to any computationally-bounded adversary, no matter how much previous output they’ve already seen. The typical way to achieve this is to take some random ‘seed’ and feed it into a Cryptographically Secure Pseudorandom Number Generator (CSPRNG) that can produce an essentially-endless stream of unpredictable bytes upon request. The properties of a CSPRNG ensure that all outputs are practically indistinguishable from truly random outputs to anyone that does not know its internal state. However, this all depends on having a secure random seed to begin with. Take a look at this blog for more details on true randomness versus pseudorandomness, and this blog for some great examples of what can go wrong with insecure randomness.

For many years, Cloudflare’s servers relied on local sources of entropy (such as the precise timing of packet arrivals or keyboard events) to seed their entropy pools. While there’s no reason to believe that the local entropy sources on those servers are insecure or could be easily compromised, we wanted to hedge our bets against that possibility. Our solution was to set up a system where our servers could periodically refresh their entropy pools with true randomness from an external source.

That brings us to LavaRand. “Lavarand” has long been the name given to systems used for the generation of randomness (first by Silicon Graphics in 1997). Cloudflare launched its instantiation of a LavaRand system in 2017 as a system that collects entropy from the wall of lava lamps in our San Francisco office and makes it available via an internal API. Our servers then periodically query the API to retrieve fresh randomness from LavaRand and incorporate it into their entropy pools. The contributions made by LavaRand can be considered spice added to the entropy pool mix! (For more technical details, read our previous blog post.)

Adding to the office chaos

Our lava lamps in San Francisco have been working tirelessly for years to supply fresh entropy to our systems, but they now have siblings across the world to help with their task! As Cloudflare has grown, so has the variety of entropy sources found in and sourced from our offices. Cloudflare’s Places team works hard to ensure that our offices reflect aspects of our values and culture. Several of our larger office locations include installations of physical systems of entropy, and it is these installations that we have worked to incorporate into LavaRand over time. The tangible and exciting draw of these systems is their basis in physical mechanics that we intuitively consider random. The gloops of warmed ascending “lava” floating past cooler sinking blobs within lava lamps attract our attention just as other unpredictable (and often beautiful) dynamic systems capture our interest.

London’s unpredictable pendulums

Visible to visitors of our London office is a wall of double pendulums whose beautiful swings translate to another source of entropy to LavaRand and to the pool of randomness that Cloudflare’s servers pull from.

To the untrained eye the shadows of the pendulum stands and those cast by the rotating arms on the rear wall might seem chaotic. If so, then this installation should be labeled a success! Different light conditions and those shadows add to the chaos that is captured from this entropy source.

Indeed, even with these arms restricted to motion in two dimensions, the path traced by the arms is mesmerizingly varied, and can be shown to be mathematically chaotic. Even if we forget air resistance, temperature, and the environment, and then assume that the mutation is completely deterministic, still the resulting long-term motion is hard to predict. In particular the system is very sensitive to initial conditions, this initial state – how they are set in motion – paired with deterministic behavior produces a unique path that is traced until the pendulum comes to rest, and the system is set in motion by a Cloudflare employee in London once again.

Austin’s mesmerizing mobiles

The beautiful new Cloudflare office in Austin, Texas recently celebrated its first year since opening. This office contributes its own spin on physical entropy: suspended above the entrance of the Cloudflare office in downtown Austin is an installation of translucent rainbow mobiles. These twirl, reflecting the changing light, and cast coloured patterns on the enclosing walls. The display of hanging mobiles and their shadows are very sensitive to a physical environment which includes the opening and closing of doors, HVAC changes, and ambient light. This chaotic system’s mesmerizing and changing scene is captured periodically and fed into the stream of LavaRand randomness.

Mixing new sources into LavaRand

We incorporated the new sources of office chaos into the LavaRand system (still called LavaRand despite including much more than lava lamps) in the same way as the existing lava lamps, which we’ve previously described in detail.

To recap, at repeated intervals, a camera captures an image of the current state of the randomness display. Since the underlying system is truly random, the produced image contains true randomness. Even shadows and changing light conditions play a part in producing something unique and unpredictable! There is another secret that we should share: at a base level, image sensors in the real world are often a source of sufficient noise that even images taken without the lens cap removed could work well as a source of entropy! We consider this added noise to be a serendipitous addition to the beautiful chaotic motion of these installations.

Once we have a still image that captures the state of the randomness display at a particular point in time, we compute a compact representation – a hash – of the image to derive a fixed-sized output of truly random bytes.

The random bytes are then used as an input (along with the previous seed and some randomness from the system’s local entropy sources) to a Key Derivation Function (KDF) to compute a new randomness seed that is fed into a Cryptographically Secure Pseudorandom Number Generator (CSPRNG) that can produce an essentially-endless stream of unpredictable bytes upon request. The properties of a CSPRNG ensure that all outputs are practically indistinguishable from truly random outputs to anyone that does not know its internal state. LavaRand then exposes this stream of randomness via a simple internal API where clients can request fresh randomness.

seed = KDF(new image || previous seed || system randomness)
rng = CSPRNG(seed)
…
rand1 = rng.random()
rand2 = rng.random()

How can I use LavaRand?

Applications typically use secure randomness in one of two flavors: private and public.

Private randomness is used for generating passwords, cryptographic keys, user IDs, and other values that are meant to stay secret forever. As we’ve previously described, our servers periodically request fresh private randomness from LavaRand to help to update their entropy pools. Because of this, randomness from LavaRand is essentially available to the outside world! One easy way for developers to tap into private randomness from LavaRand is to use the Web Crypto API’s getRandomValues function from a Cloudflare Worker, or use one that someone has already built, like csprng.xyz (source).

Public randomness consists of unpredictable and unbiased random values that are made available to everyone once they are published, and for this reason should not be used for generateding cryptographic keys. The winning lottery numbers and the coin flip at the start of a sporting event are some examples of public random values. A double-headed coin would not be an unbiased and unpredictable source of entropy and would have drastic impacts on the sports betting world.

In addition to being unpredictable and unbiased, it’s also desirable for public randomness to be trustworthy so that consumers of the randomness are assured that the values were faithfully produced. Not many people would buy lottery tickets if they believed that the winning ticket was going to be chosen unfairly! Indeed, there are known cases of corrupt insiders subverting public randomness for personal gain, like the state lottery employee who co-opted the lottery random number generator, allowing his friends and family to win millions of dollars.

A fundamental challenge of public randomness is that one must trust the authority producing the random outputs. Trusting a well-known authority like NIST may suffice for many applications, but could be problematic for others (especially for applications where decentralization is important).

drand: distributed and verifiable public randomness

To help solve this problem of trust, Cloudflare joined forces with seven other independent and geographically distributed organizations back in 2019 to form the League of Entropy to launch a public randomness beacon using the drand (pronounced dee-rand) protocol. Each organization contributes its own unique source of randomness into the joint pool of entropy used to seed the drand network – with Cloudflare using randomness from LavaRand, of course!

While the League of Entropy started out as an experimental network, with the guidance and support from the drand team at Protocol Labs, it’s become a reliable and production-ready core Internet service, relied upon by applications ranging from distributed file storage to online gaming to timestamped proofs to timelock encryption (discussed further below). The League of Entropy has also grown, and there are now 18 organizations across four continents participating in the drand network.

The League of Entropy’s drand beacons (each of which runs with different parameters, such as how frequently random values are produced and whether the randomness is chained – more on this below) have two important properties that contribute to their trustworthiness: they are decentralized and verifiable. Decentralization ensures that one or two bad actors cannot subvert or bias the randomness beacon, and verifiability allows anyone to check that the random values are produced according to the drand protocol and with participation from a threshold (at least half, but usually more) of the participants in the drand network. Thus, with each new member, the trustworthiness and reliability of the drand network continues to increase.

We give a brief overview of how drand achieves these properties using distributed key generation and threshold signatures below, but for an in-depth dive see our previous blog post and some of the excellent posts from the drand team.

Distributed key generation and threshold signatures

During the initial setup of a drand beacon, nodes in the network run a distributed key generation (DKG) protocol based on the Pedersen commitment scheme, the result of which is that each node holds a “share” (a keypair) for a distributed group key, which remains fixed for the lifetime of the beacon. In order to do something useful with the group secret key like signing a message, at least a threshold (for example 7 out of 9) of nodes in the network must participate in constructing a BLS threshold signature. The group information for the quicknet beacon on the League of Entropy’s mainnet drand network is shown below:

curl -s https://drand.cloudflare.com/52db9ba70e0cc0f6eaf7803dd07447a1f5477735fd3f661792ba94600c84e971/info | jq
{
  "public_key": "83cf0f2896adee7eb8b5f01fcad3912212c437e0073e911fb90022d3e760183c8c4b450b6a0a6c3ac6a5776a2d1064510d1fec758c921cc22b0e17e63aaf4bcb5ed66304de9cf809bd274ca73bab4af5a6e9c76a4bc09e76eae8991ef5ece45a",
  "period": 3,
  "genesis_time": 1692803367,
  "hash": "52db9ba70e0cc0f6eaf7803dd07447a1f5477735fd3f661792ba94600c84e971",
  "groupHash": "f477d5c89f21a17c863a7f937c6a6d15859414d2be09cd448d4279af331c5d3e",
  "schemeID": "bls-unchained-g1-rfc9380",
  "metadata": {
    "beaconID": "quicknet"
  }
}

(The hex value 52db9b… in the URL above is the hash of the beacon’s configuration. Visit https://drand.cloudflare.com/chains to see all beacons supported by our mainnet drand nodes.)

The nodes in the network are configured to periodically (every 3s for quicknet) work together to produce a signature over some agreed-upon message, like the current round number and previous round signature (more on this below). Each node uses its share of the group key to produce a partial signature over the current round message, and broadcasts it to other nodes in the network. Once a node has enough partial signatures, it can aggregate them to produce a group signature for the given round.

curl -s https://drand.cloudflare.com/52db9ba70e0cc0f6eaf7803dd07447a1f5477735fd3f661792ba94600c84e971/public/13335 | jq
{
  "round": 13335,
  "randomness": "f4eb2e59448d155b1bc34337f2a4160ac5005429644ba61134779a8b8c6087b6",
  "signature": "a38ab268d58c04ce2d22b8317e4b66ecda5fa8841c7215bf7733af8dbaed6c5e7d8d60b77817294a64b891f719bc1b40"
}

The group signature for a round is the randomness (in the output above, the randomness value is simply the sha256 hash of the signature, for applications that prefer a shorter, fixed-sized output). The signature is unpredictable in advance as long as enough (at least a majority, but can be configured to be higher) of the nodes in the drand network are honest and do not collude. Further, anyone can validate the signature for a given round using the beacon’s group public key. It’s recommended that developers use the drand client libraries or CLI to perform verification on every value obtained from the beacon.

Chained vs unchained randomness

When the League of Entropy launched its first generation of drand beacons in 2019, the per-round message over which the group signature was computed included the previous round’s signature. This creates a chain of randomness rounds all the way to the first “genesis” round. Chained randomness provides some nice properties for single-source randomness beacons, and is included as a requirement in NIST’s spec for interoperable public randomness beacons.

However, back in 2022 the drand team introduced the notion of unchained randomness, where the message to be signed is predictable and doesn’t depend on any randomness from previous rounds, and showed that it provides the same security guarantees as chained randomness for the drand network (both require an honest threshold of nodes). In the implementation of unchained randomness in the quicknet, the message to be signed simply consists of the round number.

# chained randomness
signature = group_sign(round || previous_signature)

# unchained randomness
signature = group_sign(round)

Unchained randomness provides some powerful properties and usability improvements. In terms of usability, a consumer of the randomness beacon does not need to reconstruct the full chain of randomness to the genesis round to fully validate a particular round – the only information needed is the current round number and the group public key. This provides much more flexibility for clients, as they can choose how frequently they consume randomness rounds without needing to continuously follow the randomness chain.

Since the messages to be signed are known in advance (since they’re just the round number), unchained randomness also unlocks a powerful new property: timelock encryption.

Timelock encryption

Timelock (or “timed-release”) encryption is a method for encrypting a message such that it cannot be decrypted until a certain amount of time has passed. Two basic approaches to timelock encryption were described by Rivest, Shamir, and Wagner:

 There are two natural approaches to implementing timed release cryptography:

  - Use “time-lock puzzles” – computational problems that cannot be solved without running a computer continuously for at least a certain amount of time.

  - Use trusted agents who promise not to reveal certain information until a specified date.

Using trusted agents has the obvious problem of ensuring that the agents are trustworthy. Secret sharing approaches can be used to alleviate this concern.

The drand network is a group of independent agents using secret sharing for trustworthiness, and the ‘certain information’ not to be revealed until a specified date sounds a lot like the per-round randomness! We describe next how timelock encryption can be implemented on top of a drand network with unchained randomness, and finish with a practical demonstration. While we don’t delve into the bilinear groups and pairings-based cryptography that make this possible, if you’re interested we encourage you to read tlock: Practical Timelock Encryption from Threshold BLS by Nicolas Gailly, Kelsey Melissaris, and Yolan Romailler.

How to timelock your secrets

First, identify the randomness round that, once revealed, will allow your timelock-encrypted message to be decrypted. An important observation is that since drand networks produce randomness at fixed intervals, each round in a drand beacon is closely tied to a specific timestamp (modulo small delays for the network to actually produce the beacon) which can be easily computed taking the beacon’s genesis timestamp and then adding the round number multiplied by the beacon’s period.

Once the round is decided upon, the properties of bilinear groups allow you to encrypt your message to some round with the drand beacon’s group public key.

ciphertext = EncryptToRound(msg, round, beacon_public_key)

After the nodes in the drand network cooperate to derive the randomness for the round (really, just the signature on the round number using the beacon’s group secret key), anyone can decrypt the ciphertext (this is where the magic of bilinear groups comes in).

random = Randomness(round)
message = Decrypt(ciphertext,random)

To make this practical, the timelocked message is actually the secret key for a symmetric scheme. This means that we encrypt the message with a symmetric key and encrypt the key with timelock, allowing for a decryption in the future.

Now, for a practical demonstration of timelock encryption, we use a tool that one of our own engineers built on top of Cloudflare Workers. The source code is publicly available if you’d like to take a look under the hood at how it works.

# 1. Create a file
echo "A message from the past to the future..." > original.txt

# 2. Get the drand round 1 minute into the future (20 rounds) 
BEACON="52db9ba70e0cc0f6eaf7803dd07447a1f5477735fd3f661792ba94600c84e971"
ROUND=$(curl "https://drand.cloudflare.com/$BEACON/public/latest" | jq ".round+20")

# 3. Encrypt and require that round number
curl -X POST --data-binary @original.txt --output encrypted.pem https://tlock-worker.crypto-team.workers.dev/encrypt/$ROUND

# 4. Try to decrypt it (and only succeed 20 rounds x 3s later)
curl -X POST --data-binary @encrypted.pem --fail --show-error https://tlock-worker.crypto-team.workers.dev/decrypt

What’s next?

We hope you’ve enjoyed revisiting the tale of LavaRand as much as we have, and are inspired to visit one of Cloudflare’s offices in the future to see the randomness displays first-hand, and to use verifiable public randomness and timelock encryption from drand in your next project.

Chaos is required by the encryption that secures the Internet. LavaRand at Cloudflare will continue to turn the chaotic beauty of our physical world into a randomness stream – even as new sources are added – for novel uses all of us explorers – just like that snail – have yet to dream up.

And she gazed at the sky, the sea, the land
The waves and the caves and the golden sand.
She gazed and gazed, amazed by it all,
And she said to the whale, “I feel so small.”

Tune in for more news, announcements and thought-provoking discussions! Don’t miss the full Security Week hub page.