Rigging RANDAO: Defeating Crypto’s Favorite “Trustless” Random Number Generator

Recently, I discovered a 0-day vulnerability in Keybase’s new cryptographic coin-flipper. (Don’t worry, it’s been patched.) The basic premise of the algorithm is that each user supplies a number to add some entropy to the output, and all of these numbers are combined to produce a pseudo-random result.

Keybase does a better job describing the algorithm than I ever have, and you can read all about it in their feature announcement article here: https://keybase.io/blog/cryptographic-coin-flipping

For the impatient, here is the quick and dirty description:

• Each participant picks a number and keeps it secret.
• Each participant publishes a hash of their secret number.
• Once all participants have committed, each participant reveals their secret number.
• The numbers are verified against their respective hashes.
• We combine all participants’ numbers to produce the pseudo-random output.

If you’ve been paying a lot of attention to the blockchain ecosystem, the algorithm may look familiar. In crypto circles, it is called RANDAO, and it has been hyped off-and-on for a few years now. You can find the unofficially canonical Solidity code here: https://github.com/randao/randao. (This is also patched now.)

Where RANDAO goes wrong

The existing conventional wisdom about RANDAO has been that, because every participant must commit to their number before any other participant’s number is revealed, we only need one of those participants to be honest. In other words, if everyone is cheating and colluding except you, the algorithm will still produce a number that they cannot predict.

However, as you will see, this is false.

The weakness lies in the way RANDAO combines participants’ numbers. RANDAO uses bitwise exclusive or(XOR) to aggregate the inputs. XOR has some exploitable mathematical properties that open RANDAO to attack. Here are the most relevant math facts:

• For any value of N, N xor N = 0.
• For any value of N, 0 xor N = N.

Colluding attackers can pick an output of their choosing

Scenario:

• Alice is trying to play fair.
• Bob and Charlie are conspiring to cheat.
• Alice’s, Bob’s, and Charlie’s numbers are A, B, and C, respectively.

The commit phase

• Charlie can commit hash(C) whenever. He does.
• Bob waits for Alice to commit hash(A).
• Alice commits hash(A).
• Without knowing what A is, Bob commits the same hash as Alice.
• Alice’s and Bob’s inputs are equal.
• The final committed inputs are [A, A, C].

At this point, the output is determined. We just don’t know what it is yet. But Charlie does. In fact, the output is guaranteed to be equal to Charlie’s input C because:

• If A xor A = 0,
• And 0 xor C = C,
• Then A xor A xor C = C.
• (Also note that order doesn’t matter. A xor C xor A would also be C.)

The reveal phase is fairly arbitrary at this point.

• Charlie can reveal C whenever. He does.
• Bob has to wait for Alice to reveal A.
• Alice reveals A.
• Bob “reveals” A by copying Alice again.

This also works with more participants. For N participants, N/2 of them can coerce the output to zero. N/2 + 1 can coerce the output to an arbitrary number. Attackers need to ensure there is one duplicate input for every honest input to bring the aggregate back to 0, at which point they can rig the output.

By the way, don’t panic: Ethereum 2.0 will be fine.

For those of you who are extra-informed, you may be aware that there is a RANDAO mixer included in the Ethereum 2.0 protocol spec. I have already spoken to Vitalik Buterin, and he has assured me that the way they integrate BLS signatures into the overall protocol negates the attack.

Fixing RANDAO

So how do the rest of us keep this from happening?

An elegant fix for the algorithm would be to use a different aggregation function. In another article I wrote, before I knew what RANDAO was, I prescribed a very similar commit-reveal algorithm that uses modular addition to aggregate the inputs. Modular addition does not suffer from the same problems as XOR. However, it is more computationally costly, which can be an important consideration for blockchain code.

A quicker fix, and the one that both Keybase and the RANDAO contract repo maintainers have employed, is to simply reject duplicate inputs. This helps Keybase maintain some backward compatibility and helps the RANDAO contract keep its blockchain costs lower.

---

Blockchain Cryptocurrency Development Ethereum