THORChain Exploit Report #3

Note: This report was prepared by THORSec.

This is a deep technical explanation of the exploit used in THORChain’s May 15th attack. It is meant to be an addendum to the previously published report #1 and report #2. This report is for the technically savvy reader who wishes to gain a more profound understanding of the cryptography surrounding the attack. In this article, we will describe what parts of our implementation were vulnerable, how the vulnerability was exploited, and finally, how the vulnerabilities have been mitigated in a way that would prevent this family of exploits from getting executed on THORChain again.

No cryptographic background is required to understand this publication, and only a basic understanding of math. To make it accessible, most of the examples have been simplified enough to reason about the exploit without excluding readers who do not have any background in cryptography. We aim to provide real intuition about the security provided by theoretical cryptography, as well as the vulnerabilities in the way that cryptography was implemented in version 0.1.6 of the tss-lib that THORChain was using at the time of the attack.

Some Background

In order to sign transactions, THORChain’s validators use a process called TSS or “Threshold Signature Scheme.” What this means in short is that the way a signature is formed has to involve a threshold of peers. THORChain uses a roughly two-thirds TSS threshold. This is similar in purpose to the supermajority used in BFT consensus, although the exact rules differ: an 18-node TSS committee requires 12 signers, while BFT consensus would require more than two-thirds of the voting power. Under TSS, signatures are computed in a distributed manner, no number of validators below the threshold can form a signature themselves.

What happens, though, if those keyshares used by validators are somehow leaked? This is where the economic security model breaks. If enough key shares (⅔) fall into a single entity’s hands, that entity can now recombine them to form the key and essentially have access to all the funds secured by that vault on addresses derived from it.

Generating Keyshares

In general terms, TSS is part of a wider family of cryptographic algorithms called MPC, or Multi-Party Computation.

These algorithms solve the problem of making a shared calculation without any participants learning the other participants' secrets, and not even the final result.

In the current protocol, each vault needs to have unique cryptographic keys. Those keys are used to compute (derive) all the keys to all the accounts/addresses/utxos that hold the vault’s funds on each of the chains it bridges.

Most funds use addresses derived from an ECDSA “master” key, and that would be the key we will focus on in this article. Other chains like Solana and (pretty soon also) Monero use a slightly different key that has no mathematical relationship with the ECDSA “Master key.”Because the Master key is derived via MPC, it does not really “physically” exist on any system.

If we were to represent the key as a sequence of bits, no system in the world should have that sequence at any given point in time. What does exist are parts of the key, (those “keyshares” we mentioned earlier) that are distributed among each of the validator nodes in that vault.

The process of generating the shares that correspond to the actual key is what we refer to as “keygen,” although no key is actually “physically” generated. We will not go into the actual cryptography used to generate those shares in a way that enables the threshold property. Just keep in mind that the process of keygen is performed once per vault-churn, meaning that the “ephemeral key” is only used to sign transactions (ideally) for a 3-day interval.

The Flawed Stage of Signature Generation

The process of using these keyshares for signing transactions is also too complex mathematically to explain even in this deep technical dive.

But the crux of the exploit lies in a single operation, which we will explain, without using too much math. In order to generate a “distributed” signature, each of the validators needs to perform mathematical operations on the message the vault is signing.

These operations need to be performed with every other peer in the committee. If a vault has 18 validators, ⅔ of them are 12, and each validator on the committee has to perform a mathematical operation with 11 other validators during each signature. The specific type of mathematical operation is called MtA or “Multiplicative to Additive.”

Lets do a quick example for the numbers 3 and 19:

3X19 = 57

That 57 can be broken apart into two additive numbers simply by subtracting any number from it. For example:

57 - 40 = 17.

Ideally what we want to have is two numbers, one for each of the two peers, that their sum equals the product of their two secrets:

40 + 17 = 19 X 3

So how does a validator do MtA with another validator without any of them exposing their secret? To solve this problem, the TSS algorithm GG20 (used by THORChain at the time of the attack) relies on a cryptographic scheme called “partial homomorphic encryption.” Homomorphic encryption allows calculations to be performed on encrypted values without decrypting them. Fully homomorphic encryption supports both addition and multiplication of compatible encrypted values. For example: encrypted 3 X encrypted 5 = encrypted 15. 

GG20 uses only a partially homomorphic encryption scheme called “Paillier.” With this scheme Bob (honest participant B) can multiply Alice’s (honest participant A) encrypted number by his own unencrypted number, producing an encrypted product. For example:encrypted 3 X 5 = encrypted 15.

Bob then adds a large random number (called a “mask”) before Alice decrypts it. That mask prevents Alice from learning Bob’s number. We can think of this encryption as some sort of box that allows us to put our value in it, send it to our peers, and have them perform some math on it without them knowing our key or the result (it’s encrypted with our key). Our peers can send the encrypted result back to us so we can decrypt it. In practice with our overly simplistic toy example:Alice sends her encrypted 4: enc(4)Bob just sees a blob, but he can multiply it with his own number: 23 X enc(4) = enc(92)

Bob still sees only a blob, but now he chooses some random number (let’s say 11) and adds it to the blob using the same type of partial homomorphic arithmetic: enc(92) + 11 = enc(103).Bob then sends Alice the blob back, she decrypts it with her key and gets 103.

Now each of them has a number, and these numbers' sums are equal to the product of the two secrets (103 and -11) without either of them knowing or even being able to guess the actual secret the other one has.

Don't be tempted to try and guess the numbers in this toy example. In reality, these numbers are huge 256-bit numbers, so trying to brute force the secret would take longer than the presumed age of the universe by 10^32.

In order for this partially homomorphic encryption to work, Bob has to have Alice’s public Paillier key (it’s better to think of a public asymmetric key as a lock, “I give you a lock to lock something with, so only I can unlock it because I am the only one who holds the lock’s key”). That’s the only way he can perform the MtA homomorphically with Alice. The entire attack circled around breaking this “lock” to see what’s inside.

To clarify, the attacker did not break Paillier’s scheme, which is proven to be impossible with today’s compute capabilities in any reasonable amount of time. The reason the attacker could take peeks into that locked box is because of a flaw in how the scheme was coded, as is the case with the vast majority of cryptographic attacks. We will now take a closer look at the implementation and how the attacker was able to use its gaps to reconstruct the key.

The Paillier Co-Prime Modulus Vulnerability

The first step was to be selected as part of the quorum that performs the keygen ritual for a given vault, or in other words, getting “churned in.”

While participating, each validator is required to generate their own share locally. Along with the keyshare, the validator also generates its own Paillier asymmetric key pair. The reason this key is generated once in the beginning of the churn is not cryptographic, as the Paillier key has no relationship to the keyshare. The actual reason is just the sheer difficulty of the operation which makes it time intensive.

For a Paillier public key to be valid, it must be composed of exactly 2 prime numbers, each approximately 1024 bits in size. The two large prime numbers are the private key. Finding such numbers has to happen randomly (otherwise the key would be predictable). The process involves randomly choosing huge numbers and then running tests to check if they are primes. This process continues until two primes roughly the same size are found, and it can take up to a few minutes.

During keygen each node sends its Paillier public key to every other peer, and it gets recorded in the local state file for each of the peers on the vault.

The first weakness the attacker exploited was that validators performed only a partial correctness check on the Paillier public key (N). 

The check had three parts:

• N had to be exactly 2048 bits.
• N could not be divisible by any of the first 168 primes—the primes below 1000.
• N had to pass a 13-round proof designed to reject moduli containing repeated prime factors.

Crucially, this proof did not establish that N contained exactly two prime factors. A carefully constructed modulus containing more than two distinct primes, each above 997, could therefore pass all three checks. That is, in fact, exactly what happened.The attacker used 17 prime numbers (and one large prime), each about 17 bits, to construct his Paillier key in a way that enabled them to “peek” into the locked box. 

To answer the question of “How does having a Paillier key composed out of small coprimes allow the attacker to leak other participants’ secrets?” we must delve a bit deeper.

A Paillier public key is basically just a modulus used to hide a value. If we imagine a modulus as a clock-like object (wrapping around every 12 hours), instead of having two huge clocks with an astronomical amount of digits, the attacker got his peers to “hide” their secret value using 17 small clocks. When the results on these “clocks” were cross-sectioned, they exposed the secret in a mathematically proven way. In our toy example, we left the modulus out because it is normally huge and rarely has any effect on the resulting encryption. We will include it in the next.

The mathematically proven way to expose the secret values is called “the Chinese Remainder Theorem” or CRT. It got that name because it was discovered in 3rd-century AD China by a mathematician/philosopher named Sunzi (later romanized into Sun Tzu), not to be confused with the military strategist with the same name who lived 800 years prior.

What the theorem states is that if you know a number’s remainders after dividing by several primes, those remainders together point to exactly one number, assuming that the number is smaller than the primes multiplied together. That is precisely what the attacker got when they issued their compromised Paillier public key that was composed of 17 small prime numbers (plus one massive prime that is less relevant to the following explanation).

To get some sort of intuition about it, let’s use the previous toy example, but this time, the peer who Bob thinks is Alice is in fact Mallory (malicious participant):

Initial setup (keygen ritual)

Mallory (the attacker) publishes a malicious Paillier modulus: N = 3 × 5 × 7 = 105. Bob’s secret is: x = 23.

Now Bob holds Mallory’s compromised Paillier public key.

Attack (keysign ritual)

In the MtA round (2nd of the 7 total rounds), Mallory does not send her actual secret, instead, she calculates a number that is her N divided by one of its factors, like: k = 105/3 = 35.

She sends her malicious “secret,” and Bob performs the partially homomorphic calculations with it and her N:

First Keysign Ritual

Mallory chooses k = 105 / 3 = 35 (divides by the first coprime of her malicious key). Suppose Bob chooses a mask of 11 like before. Bob returns: (35 * 23 + 11) mod 105 = 81. Mallory calculates: 81 mod 35 = 11 (this is the mask). Mallory removes the mask: (81 - 11) = 70

And divided by her malicious “secret”: 70 / 35 = 2. Now Mallory knows that Bob’s secret mod 3 (her first coprime) = 2.

She does not yet know it’s 23, although 23 mod 3 is indeed 2, but there are plenty of other candidates under 105:

2, 5, 8, 11, 14, 17, 20, 23, 26, 29... That’s too many to guess, Mallory needs more information.

Second Keysign Ritual

Mallory chooses k = 105 / 5 = 21 (divides by the second coprime of her malicious key). Suppose Bob chooses a mask of 8 this time (it’s a random different mask every time). Bob returns: (21 * 23 + 8) mod 105 = 71. Mallory calculates: 71 mod 21 = 8 (the mask). Mallory removes the mask: (71 - 8) / 21 = 3. Result: x mod 5 = 3.

Now Mallory has additional information, she knows x mod 3 = 2 and that x mod 5 = 3, so she can narrow down the list to:8, 23, 38, 53, 68, 83, 98... All satisfy both modulus conditions and are under 105. But the list is still very long (or let’s assume it is for our toy example).

Third Keysign Ritual

Mallory chooses k = 105 / 7 = 15. (divides by the third coprime of her malicious key). Suppose Bob chooses a mask of 6. Bob returns: (15 * 23 + 6) mod 105 = 36. Mallory calculates: 36 mod 15 = 6 (the mask). Mallory removes the mask: (36 - 6) / 15 = 2. Result: x mod 7 = 2.

With this 3rd condition, there is exactly one number that satisfies all modulus and is under 105, and it is 23 - Bob’s actual secret!

Each of these keysign rituals allows Mallory to take one “peek” in the locked “box” of all the participants, with enough peeks, she can infer the key.

In actuality, these numbers would have been huge, and the attacker would have needed around 16 keysign rituals to extract a peer’s share. That, of course, was not a problem since THORChain signs thousands of transactions during the course of a single churn. Additionally, each keysign round has validators performing MtA with every other validator on the committee (13 nodes for a 19 validator vault). Granted, not every committee has the exact same set of validators on it, so it could take longer than 16 keysigns under normal conditions. But the attacker did a clever trick, they deliberately failed the next round (3rd) of the TSS keysign ritual and got the vault members to retry signing the same transaction, effectively getting multiple MtA rounds on the same signature.

We can also see why the attacker’s compromised key would not have failed THORChain’s correctness checks: There is no problem for them to pre-compute a compromised Paillier key, which was composed of small coprimes. The key they computed was composed of 17 primes, 17 bits each, along with an 18th prime 1776 bits in size (let’s call it Q):65537, 65539, 65543, 65551, 65557, 65563, 65579, 65581, 65587, 65599, 65609, 65617, 65629, 65633, 65647, 65651, 65657 and Q. The product of these (N) was about 2048 bits in size.

Just to get an idea of how large those numbers are in relation to the small primes:Q = 3147237974619945196474823566094938793089473884388380531534315632292968897134016203785961363147483475477379664760276941347987548401776133662269888744401101917809083056502024301196785401046564000944457060042270350206320836845267270512611352035399470978581306366748396497081756326528999669260231924237566698364306564581203662592211915429313957642148683957456992114886215724758570247007604392039420646452938919388517439445323175778891476951536458127834954725516472435138069488759295307274866754188352213617764509199827102078761697389635819

N = 24237754553483255475536157516502463970333077002286613024097759070643491354150918169897901058642185097766538470691423514620589669362868190821316114289836212340473158025475747068812648312792239080097043228788050676207594163981964817121378570753857127852936234389027228782165681918655799356455664299342947789141435750042251256815513731089923427121142132026494741543558354244498269644531345235612693944648132837544457702788846393018198763364226234428302773209924965423420344263533115157293867826295198492602258906935492523451284497951263348710738281654446776237074088020620235910529662357721898290528008211173578839181893

Fun fact about the numbers chosen: the composition of coprimes published by Fireblocks in 2023 was 16 coprimes of 16 bits in size (smaller than that and you need more attempts, larger than that and your fewer attempts increase in compute costs). The attacker used a list of small primes that started precisely one prime above 2¹⁶ (65536), so a trivial check of that range would have missed it.

The “Leaky” Mask Vulnerability

Had the attacker only used the multiple co-primes Pailler public key (N), THORChain would not have been vulnerable to this attack despite the weak validation check. In the previous toy example we cheated a little bit, we made Bob choose very small masks (11, 8, and 6). If Bob had chosen 46 as his mask in the first example, the modulus would still be the same (11), and Mallory would not know if Bob’s mask was 46 or 11 (or 81, or any other number that follows 35X + 11), so she would not be able to properly subtract it. In the toy example, it was possible to just guess (brute force) the mask because there weren't a lot of options, but with real-world numbers, the sheer amount of possibilities would make this computation very unfeasible for the given amount of time.

“So, how did the attacker still manage to leak key information?”

There was a second bug in the MtA phase. The second bug was in the way Bob proved he was using honest numbers. In order to prove to other participants he is using valid numbers in the output he is sending back, Bob attaches a mathematical expression to his response. The proof is “zero-knowledge”, meaning that it is tied to his numbers without revealing anything about them. The mathematical expression Bob uses to prove his mask is legitimate has 3 terms:

1) The challenge: the result of a 256 hash function of a few of his cryptographic parameters (converted to an integer up to 256-bit large). This part is public.

2) His actual mask.

3) Gamma: some random value to hide the mask.

It looks like this:

Proof = challenge X mask + gamma

Let’s use a toy example:

Challenge: 100

Mask: 46

Gamma: 35,000

We get 100 X 46 + 35000 = 39600

Even if we know the public challenge to be 100, we cannot use this to our advantage:39600 / 100 = 396 which tells us nothing about 46

The bug was that the way Bob chose gamma was outputting much smaller numbers, 256-bit smaller than the product it needed to be.

If we use some smaller gamma, like 350 we get:

100 X 46 + 350 = 4950

If we divide by the public challenge, we get 49.5 which gives us a big hint that the mask would be 46 and not 11 or 81 or any other of the possible numbers.

The proof was leaking information about the mask.

The Degenerate Commitment

Yet again, we must say that if these were the only two vulnerabilities in the implementation, THORChain would not have been vulnerable to the attack. 

In the last example, we used tiny numbers (N = 105) so the malicious “secret” did not have to be massive. In the real cryptographic world, this malicious number would be enormous, much, much larger than any honest input a validator might submit as their secret.

Every time a validator sends their encrypted secret for the MtA round, they also attach a ZK (zero knowledge) range proof that allows the recipient to validate the secret k is not too large to be out of bounds. The zero-knowledge part allows them to do it without ever learning any useful information about the secret.

This is achieved mathematically by the zero-knowledge proof because it utilizes a commitment, a challenge, and several proof responses to that challenge. The commitment forces the prover to use the same value he is proving to be valid as their actual k for the MtA.

The verification equations are intended to show that Alice knows the plaintext encrypted in the MtA ciphertext and that it lies within the allowed curve-scalar range.

Alice’s honest secret is approximately 256 bits. The proof hides it using additional randomness, so the proof response may grow to approximately 768 bits. The commitment is an expression derived from the encrypted secret, so it has a mathematical relation to it, which is very difficult to forge.

This check should have caught the attacker’s malicious k, which was approximately 2031 bits, far larger than a valid curve scalar. With a normal challenge, such a large k would cause the provers’ response to the challenge to exceed its bound, making the proof fail.

“So how did the attacker still manage to pull off the attack?” The answer lies in the part where Alice commits to the fact that the secret she is validating is the same as the secret she is using for the MtA.

The implementation had another bug. The proof has one term (Z) which is the actual commitment, that is essentially a value calculated from the secret and raised to the power of some unpredictable exponent (the "challenge"). That term is multiplied with the other terms of the proof, so it has a huge effect on them. The bug was that the term Z was never validated to not be 1, which means that if someone were to send Bob 1 as their Z, it would have had no effect on the other terms (1 to any power is always 1, and 1 has no effect as a multiplier).

This “degenerate” commitment breaks the connection between the encrypted secret and the rest of the proof. If Z = 1, the prover effectively did not commit to anything and can use any k without failing the proof. The attacker still had to craft the other terms, but with nothing binding them to the number the attacker would actually use, they could just brute force them to fit the range proof. For a 17-bit prime, the grinding requires approximately 2^17 hash operations, which would roughly take one second on average on a modern laptop and can be pre-computed so the TSS keysign would not timeout.

Now with these three vulnerabilities combined, the attacker could carry out their attack. None of these would have worked on its own, nor any combination of two out of three. That does not mean they should not have been fixed, but fixing was not perceived as urgent to perform while an effort to replace the cryptographic implementation completely and migrate to a different TSS scheme was on its way.

Mitigation

In order to mitigate the vulnerabilities described above (and some others not described here nor used in the attack) we have migrated to a new patched version. The version contains code mitigations by Binance and by SodaLabs, the vast majority of them will not be described here. Below are the cryptographic checks and validations relevant to the three weaknesses described in this article. Fixing any one of those weaknesses would have broken this specific exploit chain. Together, the changes prevent the malformed multi-prime modulus and defective MtA-proof attack described here and provide additional layers of defense.

These mitigations do not prove that every possible Paillier implementation bug is impossible. No software change can provide that certainty, but the added checks substantially reduce the attack surface and prevent this particular family of exploits.

Mitigating a Malformed Paillier Modulus

As you might recall, a well-formed Paillier key N should be composed of exactly two co-primes, roughly the same size such that N = p X q and p ~= q. The following mechanisms were added to enforce these two properties.

Π_mod: During keygen, each participant proves that their Paillier modulus N has the required two-prime structure. The participant first chooses a random value W. From the session data, W, N and every earlier challenge, both the participant and the verifying nodes deterministically derive 80 challenges using a hash function:

challengeᵢ = Hash(session, W, N, previous challenges)

W is chosen by the participant and is not committed in a separate earlier round. A malicious participant can therefore try different W values and recalculate the challenges. However, for an invalid multi-prime N, the probability of satisfying all 80 tests is at most approximately 2⁻⁸⁰ for each attempted W. The participant would therefore need approximately 2⁸⁰ attempts.

The session data does not need to be secret or unpredictable: even if the attacker knows it in advance, they must still perform the full search over W. Even at the extremely optimistic rate of one trillion complete attempts per second, 2⁸⁰ attempts would take approximately 38,000 years.

Π_fac: This proof shows that the participant knows two hidden factors, p and q, whose product is N, and that the factors satisfy the proof’s size limits. The participant does not reveal p or q. Instead, they publish hidden commitments to them.

A hash of the session, N and those commitments produces a challenge e. The participant then sends responses containing expressions such as:

z₁ = e × p + random value

z₂ = e × q + random value

The verification equations ensure that the same hidden p and q were used in the commitments and that their product is N. The verifier also limits the size of z₁ and z₂. The exploit’s extremely unbalanced factorization, approximately 273 bits on one side and 1776 bits on the other, would make one of these responses too large and would fail.

Π_fac does not prove that p and q are prime, nor does it force them to be almost equal. For example, consider:

N = 3 × 5 × 7 × 11 = 1155

The factors could be grouped as:

p = 3 × 11 = 33

q = 5 × 7 = 35

A factor-knowledge proof could show that the participant knows 33 and 35 and that their product is 1155, but it would not show that 33 and 35 are not prime. This is why both proofs are needed: Π_mod proves the required two-prime structure, while Π_fac proves knowledge of a suitably bounded factorization.

Mitigating the Leaky Mask

The relevant proof response has the following form:

challenge × mask + gamma

In version 0.1.6, both the mask and gamma were chosen from ranges approximately the size of N, or roughly 2048 bits. Because the challenge can be approximately 256 bits, challenge × mask could grow to approximately 2304 bits, while gamma remained approximately 2048 bits. The product could therefore dominate the result and leak information about the mask.The 256 bits we refer to is the order of magnitude (or range) of the secp256k1 curve used for elliptic curve cryptography (ECDSA keys). We will refer to it as q for the rest of the explanation.

The patch changes both ranges:

The mask is now chosen below q⁵, an approximately 1280-bit range.

Gamma is now chosen below q⁷, an approximately 1792-bit range.

The product of the challenge and mask is therefore at most approximately q⁶, or 1536 bits. Gamma is sampled from a range approximately 256 bits wider, making the proof response statistically hide the mask.

The important change is not that gamma became larger in absolute terms. Instead, gamma became much larger relative to challenge × mask because the mask’s range was substantially reduced. A 1280-bit mask is still overwhelmingly larger than the approximately 256-bit secret it must hide.

Mitigating the Degenerate Z in the Range Proof

The range proof commitment term Z tying it to the actual k value used in the MtA round was broken. We mitigate this in a fairly straightforward manner

Explicitly fail if Z = 1: so that part of the proof does not become meaningless.

Reject other degenerate terms: this is not a mitigation to the specific exploit used for the attack, but it is worth mentioning. Along with explicitly rejecting Z = 1 we reject other term values that can render them meaningless, such as S = 1, S1 = S2 and others. The proof is hardened overall as a result.

Conclusion

In this article we described three bugs in the implementation of the cryptography THORChain was using for generating its TSS signatures.

None of the three had any effect on its own, but their combination produced a severe, exploitable vulnerability that has resulted in the theft of funds.

The effort for mitigation was not only fixing the exploitable implementation bugs, but also solving a large number of other seemingly non-sever implementation bugs as well.

The effort for securing THORChain cryptographically has expanded to deny any “building block”, no matter how small, that any would-be attacker might use to craft the next exploit.

This effort does delay our cryptography roadmap, since any change to the implementation of cryptography is itself a risk, and must be thoroughly evaluated and tested. Nevertheless in the current security climate, especially in the crypto ecosystem, the effort is worth the delay.

We should keep in mind that THORChain represents a unique intersection of risk:

THORChain is a cross chain infrastructure. Cross chain infrastructure such as bridges constitute the vast majority of funds stolen in blockchain attacks. Such infrastructures can also be exploited if an underlying bridged chain is attacked, as we’ve seen in the LTC hack (that caused great damage to other bridges, but left THORChain relatively unscathed).

THORChain is truly decentralized. We are an anonymous, permissionless blockchain - anyone can participate, no one is censored. This means that we must defend not only from malicious users aiming to exploit the protocol, but also from malicious validators, a much more privileged set of possible attackers that represents a higher risk.

THORChain is completely open sourced. Our code is available for everyone to scan for vulnerabilities. An attacker does not have a time constraint, they can keep sifting through the code until they find something. There is also an unlimited number of would be attackers, meaning that even if we mitigate 999 out of 1000 vulnerabilities, that vulnerability would still get found. We also need to secure against malicious contributors that might inject well-hidden vulnerabilities into our codebase.

All of these factors are what makes THORChain unique and valuable, and they are non-negotiable. Our security doctrine is constantly evolving to mitigate these risk factors in a way that would not have a detrimental effect on honest participants of the protocol.