Random Numbers Don’t Lie: A Closer Technical Look into Recent DeFi Hacks

by
George Georgiev
My articles My books
Follow on:

As Ethereum gas fees soared to record highs during the 2021 bull market, rendering many decentralized finance (DeFi) protocols unusable for casual users, several projects were forced to deploy on other chains.

This created a huge surge in demand for cross-chain mechanisms – called bridges – able to securely transfer user assets from one chain to another. Cross-chain bridges can generally be divided into centralized custodial bridges (CCB) and Decentralized non-custodial bridges (DNCB).

As can be expected, the surging demand for cross-chain bridges resulted in the emergence of a fresh wave of protocols of varying repute. As cross-chain bridges serviced an increasingly valuable pool of user assets, it was only a matter of time before malicious actors and hackers took notice.

Generally speaking, hackers will target DNCBs because they can exploit shortcomings in protocols designed by inexperienced development teams. An experienced hacker can easily take advantage of errors in logic or loopholes embedded into the cryptography and design of a poorly designed protocol.

This brings us to today: the aftermath of multiple attacks on cross-chain bridges. Another blackeye on a battle-worn industry. To recap, only in the month of July 2021:

• ChainSwap suffered a hack on July 2nd, worth approximately $800K in user assets.
• AnySwap V3 liquidity pools suffered a hack on the 10th day of July, worth nearly $8M in $USDC and $MIM. AnySwap is a cross-chain DEX powered by the Fusion Network.
• ChainSwap suffered another hack, only 9 days after the first hack. This time worth $4M in user assets. ChainSwap is an Alameda-backed platform that bridges Ethereum to Binance Smart Chain.

The primary purpose of this editorial is to educate and introduce, in relative detail, two often-ignored-yet-vital elements of decentralized cross-chain bridges: the random number ‘k’ involved in Secure Multi-Party Computation (SMPC) and its derivative ‘R’.

The AnySwap Hack: Two is Not Always Better Than One

Reportedly, the AnySwap hack happened because two separate transactions were signed using the same ‘R’ value. The hacker used these two signatures to reverse engineer the private key controlling AnySwap’s cross-chain MPC account and stole users’ funds.

But what, exactly, is an ‘R’ value?

What is ‘R’ – the Achilles Heel of Account Security

One of the first lessons everyone in blockchain learns is that the funds in your wallet are controlled by your private key.

You’ve all heard the phrase: “not your keys, not your coins.” This idiom means that any individual who has a wallet’s private key has full control over the assets in that wallet. Indeed, the only thing needed to transfer funds from one account to another is to sign a transaction with that account’s private key.

At present, the standard digital signature algorithm used in blockchains is the Elliptic Curve Digital Signature Algorithm (ECDSA).

ECDSA belongs to the “non-deterministic” category of digital signature algorithms. Unlike “deterministic” algorithms that always give the same output given a particular input, “non-deterministic” algorithms can produce different outputs even if given the same input. For ECDSA, this means that the same data set, or transaction, will have multiple legal signatures.

Each time a transaction is signed using ECDSA, a cryptographically secure random number ‘k’ is generated. ‘k’ is then used to calculate a point on the elliptic curve which, in turn, is used to calculate the ‘R’ value. It is crucial that a new random number ‘k’ be generated each time a transaction is signed using ECDSA.

If the same ‘k’ is used to sign multiple transactions, the ‘R’ value of two transactions will be the same and the private key will leak. This is referred to as a ‘k’ value collision and is what caused Sony’s PS3 hack in late 2010. It is also what caused the AnySwap hack.

Next, let’s examine how the AnySwap hacker reverse-engineered the private key controlling AnySwap’s cross-chain MPC account to steal users’ funds.

Two is Definitely Not Always Better than one

Consider what happens when two transactions are signed using the same random number ‘k’. Since ‘k’ is used to derive ‘R’, the ‘R’ value of the two transactions will also be the same. Let’s call these two signatures (s1) and (s2).

Per ECDSA, the equations representing these two transactions are:

where S1, S2, and ‘R’ represent signature data and represent transaction data. This is all data publicly visible on the blockchain. This leaves two remaining unknown parameters: the random number ‘k’ and the account’s private key.

Those who remember their high school algebra will immediately know how to solve the unknown parameters using the two equations. The private key sk can therefore be written as:

The AnySwap hacker noticed that two transactions had the same ‘R’ value, implying that the same random number ‘k’ was used in both. This allowed the hacker to reverse engineer the private key controlling AnySwap’s cross-chain MPC account using simple algebra and steal users’ assets.

The critical error was that the same random number ‘k’ was used in multiple transactions. Clearly, ‘k’ was not randomly generated! So how could this have been avoided?

The Need for Secure Multi-Party Computation

When compared to basic transaction signatures, Secure Multi-Party Computation (SMPC) is indeed quite complex. However, it is well worth the extra effort. If SMPC – which is very different from multi-signatures – is properly used to generate real random numbers, there is no risk of the random number ‘k’ being exposed.

When leveraging SMPC, the signing agent is no longer an individual person, but multiple people working in concert to sign transactions.

With basic transaction signatures, a true random number generator alone is enough to generate the ‘R’ value and guarantee security. However, because SMPC involves multiple unrelated parties, there is always the threat that one or more of these parties are malicious.

As such, it is not reasonable to allow a single person to generate the ‘R’ value alone as they may be a malicious actor. If they alone control the random number ‘k’ and, in turn, the ‘R’ value, they will be able to reverse engineer the account’s private key and steal assets. Therefore, three principles must be adhered to when using SMPC to generate the ‘R’ value:

1. The ‘R’ value cannot be generated by a single individual;
2. No single individual may know the random number ‘k’ used to derive the ‘R’ value;
3. The random number ‘k’ must be sufficiently random so as to be unbiased and unpredictable.

In Laymen’s terms, SMPC requires a group of people to work together on a task without knowing what it is they are working on, nor with whom they are working.

SMPC Standard-Setter: Wanchain’s Publicly Verifiable Secret Sharing Design

Wanchain’s cross-chain bridges rely on a unique mechanism that uses SMPC to keep cross-chain assets locked in accounts managed by 25 anonymous parties called Storeman nodes. The number of Storeman nodes can be increased as needed.

When signing transactions from the locked account, the ‘R’ value is jointly determined by these 25 Storeman nodes through a process known as Publicly Verifiable Secret Sharing. This process ensures that no two transactions will ever have the same ‘R’ value.

The specific steps that these 25 Storeman nodes undertake are as follows:

1. Each Storeman node (Pi) generates a random number ‘ki’ locally using a true random number generator;
2. Each Storeman node (Pi) shares its random number ‘ki’ with the other nodes through a secure channel using Shamir’s Secret Sharing.
   Shamir’s Secret Sharing is a secret sharing scheme designed to share a secret in a distributed way. The secret is split into multiple parts, called shares. The secret can be reconstructed using a minimum number of shares. Shamir’s Secret Sharing is often used in cryptography.
3. After receiving the secret shares from the other nodes, each Storeman node collects the secret shares and multiplies them by the elliptic curve base point, and broadcasts the result;
4. Each Storeman node performs Lagrange interpolation using the broadcast data to obtain an elliptic curve point whose abscissa is the ‘R’ value.

Although the above process is quite complicated, the core concept is quite simple. The ‘R’ value is jointly determined by 25 Storeman nodes. Each Storeman node contributes part of the encrypted random number ‘k’. The ‘R’ value is then determined through cryptographic operations.

In other words, the 25 Storeman nodes are working together without knowing what it is they are working on, nor who the other Storeman nodes are.

Publicly Verifiable Secret Sharing: Why Is It Critical

Publicly Verifiable Secret Sharing ensures that:

1. It is impossible for any two transactions to have the same R-value

There are two primary reasons for this. First, the ‘R’ value is jointly determined by 25 Storeman nodes, rather than an individual. In theory, as long as there is a single honest node, the ‘R’ value will be random. Second, each Storeman node’s contribution is generated by the true random number generator.

Combined, two transactions will only have the same ‘R’ value if the sum of the random numbers selected by all 25 Storeman nodes is the same in two transactions. The probability of this occurring is 2^(-256). This is less likely than you being hit by a meteorite right now, as you read this sentence.

2. The random number ‘k’ used to derive the ‘R’ value remains hidden

As demonstrated earlier, once the random number ‘k’ is known, the private key can be reverse-engineered. When signing transactions from the locked account, each Storeman node only generates a share of the random number ‘k’. Because each share is transmitting through secure channels, no Storeman node can recover the full value of the random number ‘k’.

In other words, thanks to Wanchain’s SMPC design, the random number ‘k’ used to derive the ‘R’ value always remains hidden. The locked accounts used in Wanchain’s industry-leading cross-chain bridges are extremely secure. There is no possibility that the private key leaks.

Verdict

The Wanchain R&D team disagrees that the AnySwap hack represents a general risk to other projects that adopt SMPC. The Wanchain R&D team, in alignment with other developers throughout the industry who have implemented SMPC, does not view the vulnerabilities or mistakes that allowed the AnySwap hack as a general risk.

The team also wants to emphasize the important role that random numbers play in the blockchain. Random numbers are not only used for the purpose of signing transactions. They are used at multiple levels of technical design and are important components of PoS Consensus and shard algorithms, which directly determine the security of a blockchain network.

Efficiently generating reliable random numbers is no simple task. It is the holy grail of entire swaths of mathematics and cryptography. Brilliant people have dedicated their lives and their minds to optimizing random number generation.

Blockchain developers around the world need to continue this tradition and develop better distributed random number generation algorithms while continuing to optimize on-chain random number generation. The future of DeFi – and indeed blockchain as a whole – will be built on the work done today.

Disclosure: This article was written by the Wanchain R&D team.