Kiln's solutions to Paradigm CTF 2023
Kiln recently participated in the Paradigm CTF 2023 and achieved rank 24th over more than 200 participants.
The Paradigm CTF is a renowned web3 security contest held annually and there, our team successfully navigated through a series of interesting challenges, ultimately demonstrating our skill and expertise in the field. In this post, we will delve into each one of our solutions during the challenge resolution.
SKILL BASED GAME
Context and discovery
Not much context had been given and the challenge folder appeared quite minimal so let’s have a look at how the challenge was deployed:
In the deployment script we can see that the challenge involved a smart-contract 0xA65D59708838581520511d98fB8b5d1F76A96cad already deployed on mainnet and called BLACKJACK. Although the contract on the mainnet was empty at that time, it had been generously funded with 50 ETH at the moment the challenge was deployed.
The criteria for completing the challenge were outlined in the Challenge.sol contract and was pretty simple: to get the flag, we needed to satisfy BLACKJACK.balance == 0. The goal was then to empty the BLACKJACK contract or manage to transfer the 50 ETH elsewhere.
Now let’s have a look at this BLACKJACK contract. The contract is verified on Etherscan and if we still had any doubt about the name of the contract variable name, it confirmed that it’s indeed a Blackjack gambling game. The contract has 3 public functions corresponding to the 3 game moves- deal, hit and stand, and other internal functions to compute the game (draw cards, compute scores etc). The only way to get some ETH out of the contract was to play and win against the casino.
How to beat the casino?
Place your bets (first solution)
The initial strategy that was adopted took a simplistic approach, the player started with 1000 ETH, adhering to a minimum bet requirement of 5 ETH. In a typical game of Blackjack, the odds for a player winning stood at 42.22%. So, the question arose: why not simply play by the rules and see where it leads?
Let’s simulate it:
Results:
The odds of winning 50 ETH with 1000 ETH is around 4.32% (based on 100,000 simulations). Given that you can replay an infinite number of times, it is theoretically possible to use this strategy. But it will require a lot of time and a bit of luck, and because we have a lot of challenges to solve, this is probably not the best one.
Rob the casino (second solution)
First, let’s have a look at how the smart contract really works internally, especially on how cards are dealt.
To pick a card in a 52 cards deck, the system calls deal(address player, uint8 cardNumber) where player is the player address and cardNumber the number of cards dealt during the game. To compute which card to draw, the function does the hash of 4 items modulo 52, the items are:
- The block hash of the current block
- The player address
- The card number
- The timestamp of the current block
When we are in the same block, we know the block number (then the block hash) and timestamp, the sender address and the card number. So, where is the randomness? Nowhere, we can actually easily compute everything before calling the function.
Now, we can play and just skip if we deal a card that does not fit with our hand, but it still requires to implement an advanced strategy and that’s why we chose to do a very simple one.
With a deck of 52 cards, the odds of getting a Blackjack (21 points) are 4.8%. There are then 4.8 Blackjacks every 100 games, so, 10 Blackjacks every 209 games. The strategy is: if we can directly win, we play; if we can’t, we wait for the next block. To do that, we developed a very simple contract:
Now we just have to call the function play() of this contract with a value of 5 ETH until we empty the BLACKJACK contract. Here is the script to do it:
Notes: even if we know when we don’t win a game, we still have to do a tx to move the chain forward and change the block number. Otherwise, we will never get a new hand.
Congrats, you just beat the casino. The conclusion of this challenge is: do not use on-chain data to create randomness.
PCTF{0n_chA1N_rAnd0Mn355_15_hArD}
DROPPER
The “Dropper” is a king of the hill challenge, where the objective was to airdrop ETH, ERC20 tokens and ERC721 tokens, all while minimizing gas consumption.
We kicked off with a straightforward solidity implementation to establish a reference. Following this, we incorporated some assembly optimizations, resulting in this version:
Despite our initial progress, our solution was not competitive enough. So, we decided to rebuild the contract using Huff, which significantly reduced our score to: 1,347,607.
However, by the end of the CTF, this score was not sufficient to break into the top 16 and earn points for this particular challenge.
We considered trying to game the randomness, first running a simulation to get the addresses and values to drop, programmatically generating bytecode using those values directly hardcoded to eliminate the need to load calldata. Unfortunately, time constraints prevented us from exploring these avenues.
Other simpler gas-saving techniques, such as using an access list and self destructing the contract at the end for a gas refund, were also considered but not discovered in time.
OVEN
%2520(1).png)
The Oven challenge involved interacting with a server that knows a FLAG value and performs cryptographic operations upon request, outputting computed values.
In our initial analysis, we noticed a few exciting things:
- The program uses a technique called Fiat Shamir on the FLAG. By doing some research, we were able to understand that these techniques are used to generate Zero-Knowledge Proof, which meant that the server was actually generating a proof that it knows the FLAG, with us playing the role of the verifier.
- The ability to request the server as much proof as we want for the same FLAG value gives us a hint that there is some information leakage to exploit. We could create a system of equation ri = (v - ci * FLAG) % (pi - 1) which reminded us of the Chinese Remainder Theorem, but it is not applicable here as p -1 is used as modulus so (pi - 1) are not co-prime.
- Using the provided t, r, p, g and y we can bruteforce FLAG value by verifying the assumption that t == (pow(g, r, p) * pow(y, c, p)) % p. However flag length is up to 384 bits, which is too much to compute. We tried to bruteforce on a lower range but did not get any result.
By doing further research on Fiat Shamir and information leakage, we discovered a paper which introduced us to the Hidden Number Problem, an issue that can be exploited to leak the secret of a Fiat Shamir proof if the randomness used during the proof generation is not strong enough.
Indeed, looking at the script here, v is a random value chosen in the range [2, 2**256]. So, v has a size of 512 bits at most, which is way lower than the p - 1 value as p is a prime of 1024 bits.
Quoting the paper:
the first partial randomness (i.e. nonce) leakage attack on DSA by reducing it to the closest vector problem (CVP), which can be solved using Babai’s nearest plane algorithm together with the LLL lattice reduction algorithm
A lattice is a space you can define based on a set of points in which you can move by adding/substracting points as much as you want.
This becomes interesting when we reformulate our problem from ri = (v - ci * FLAG) % (pi - 1) to vi = ri + ci * FLAG - (pi - 1) * ki
We construct our lattice by generating 5 data points from the server the following way:
Basically:
- we start with pi -1 value in diagonal, to represent (pi - 1) * ki
- we add a line for ci values (as we have ci * FLAG where FLAG is constant)
- we add a line for ri values
- the 6th column represents the coefficient of FLAG (only 1 on 6th line as we have ci * FLAG)
- the 7th column specifies that we need a solution vector to be short enough, as v is max 512 bits
As stated in the above quote, we can use the (magic) LLL algorithm to find a short solution vector for v, ultimately leading us to the FLAG.
Thankfully, sage math already implements the LLL algorithm and provides an easy way to construct the lattice. Here is the final script:
[+] Flag is F1at_shAm1R_HNP_g0_Cr4ZyyYy_m0rE_1iK3_f4T_Sh4mIr
DODONT
“DODONT”, compared to others, presented a unique challenge: drain a contract without access to the sources of various referenced contracts in the deployment script.
At first glance, this seemed like a reverse engineering challenge. However, after looking up the addresses on Etherscan, we were able to locate the sources for all the contracts, which were from DODODEX.
To get more information on how dodo works, you can read their announcement post.
Looking at their docs’ list of the current deployed contract, and comparing the addresses in the challenge with the current canonical deployment address, we identified that the DVM contract address was not the same, indicating the challenge used an outdated, potentially vulnerable version. We downloaded both versions and ran a diff:
Not much has changed, but we clearly saw that the new version added bool internal _DVM_INITIALIZED_, the 1.0.0 was vulnerable to multiple initialization!
This was interesting because in the init(), we could replace the quote token with one we just created.
On top of initializing with a token, we controlled that we set k=0 and lpFeeRate=0 which respectively prevented slippage no matter the size of the trade and any funds from going to the liquidity provider which prevented us from draining everything.
With those parameters, we could drain all the WETH by selling the same amount of quote tokens that are in the reserve.
PCTF{UNpr0t3cT3D_INITI4Liz3Rs_4r3_s0_L4ST_Y34R}
100%
Context and discovery
For this challenge, we were given 2 contracts, Split and SplitWallet. The Split contract served as a factory of SplitWallet contracts. Within the Split contract, there was a function designed to create a new split, with an associated newly deployed SplitWallet using the Clone proxy.
We observed that the createSplit function accepted arrays of accounts & percents, dictating the portion of the splitWallet balance owed to each account. Following this, it would deploy a SplitWallet, and link it to the custom hash of the split details. We noted that ownership of the split was managed following the ERC721 standard, a feature inherited by the Split contract.
Upon further inspection, we saw that the splits were validated at the time of their creation. This was crucial to ensure that the relayer fee remained below 10% and the sum of all percentages equaled 100%.
From our analysis, the objective was crystal clear: we needed to empty the Split and the first deployed SplitWallet, but we didn’t have any ownership of one of them of course.
How to steal the Splits money?
To solve the problem, we first needed to empty the SplitWallet, where funds had been deposited during the deployment of the challenge.
To do so, we simply had to call the distribute function of the contract, which handled all the logic for redistributing the funds locked in the SplitWallet.
As observed, calling the SplitWallet ’s pullToken function triggered the distribution of funds to the Split contract. However, we were not beneficiaries of the split, so we could not withdraw this value. Having solved the first step of the challenge, we then needed to find an exploit in the Split contract to empty its balance.
This exploit came from the previously shown custom hash function: _hashSplit.
Inside the distribute function _hashSplit was utilized to compare the hash of the given parameters with the hash associated with the given split id. This ensured that the provided parameters matched those given at the creation of the SplitWallet.
However, we could easily exploit this hash function named _hashSplit and create a collision with new parameters but same hash due to the usage of encodePacked
In solidity, array elements have a size of 32 bytes, so,
This way, we could distribute a completely invalid dept from the contract toward our address just by creating the split with the first set of data and calling distribute with the second set of data as arguments.
Afterward, we just needed to withdraw the funds we had deposited in the first split and we still had a debt from the contract to withdraw the funds of the first split wallet.
Finally, we just needed to withdraw 200 ETH held in Split to solve the challenge.
PCTF{gU355_7H3r3_w45n7_3nOUgH_1NpU7_V4L1D471ON}
BLACK SHEEP
This challenge is a Huff contract designed to hold funds, releasing them only when 0xd8dA6Bf26964AF9D7eed9e03e53415D37AA96044 provides a correct ECDSA signature.
The MAIN() macro was comprised of two functions within the dispatcher: receive to fund the contract and withdraw which is supposed to only let the owner to take the funds out.
Taking a look at the WITHDRAW() macro, we realized that if we had a 0 on the top of the stack after CHECKSIG(), all the stored funds would be sent to the caller.
Further investigation into the CHECKSIG() function revealed its attempt to validate the given signature.
The problem lay in the fact that if the ECDSA recovery neither reverted nor returned 0xd8dA6Bf26964AF9D7eed9e03e53415D37AA96044 we could go back to WITHDRAW() without pushing a 1 on top of the stack.
If we find a way to have a 0 on top of the stack at that point we can make WITHDRAW() send us the ETH.
Before entering this macro, we went through CHECKVALUE() which gave us an opportunity to push a 0 on the stack.
We then built a simple attacker contract :
attack() will call the target contract. When reaching the CHECKVALUE() macro, it calls the attacker contract which will go through the receive() function that reverts if the value is low, leaving a 0 on the stack. CHECKSIG() does not revert leading the WITHDRAW() macro to send all the funds to the attacker contract, this call does not revert as opposed to the first one since the value is over 32, and voila we have broken the bank!
PCTF{7rU57_8u7_vEr1fy}
COSMIC RADIATION (koth)
%2520(1).png)
The name of the challenge made us think of the Cosmic Bit Flip problem, particularly in fields like rocket engineering where external factors like cosmic radiations can sometimes affect the computer's memory by randomly flipping certain bits, which can lead to corruption of the memory value.
The challenge implemented this in a funny manner: it lets us request the creation of an Ethereum mainnet fork and specify a list of bit flip operations to perform on addresses we specify before launching the fork. This means that we can effectively re-write any Ethereum smart contract code.
Some constraints we have:
- challenge input format is like 0xaaaaa:1:2:3:4,0xbbbbbb:5:42:2:2:1:7 where each contract operation is comma separated and bit shift operations are : separated
- we cannot bit shift the code of contracts with 0 balance
- we cannot bit shift the same contract multiple times
- the balance of a shifted smart contracts is reduced via a ratio depending on the number of shift operations
- these operations are performed at the start of the fork instance, all transactions will be performed after
The challenge end goal was to send as many ETH as possible to the Challenge Smart Contract, deployed during the fork setup. The balance of this contract then becomes the team score in the challenge leaderboard.
1. Our strategy
First, we thought of which payload we want to encode in the targeted smart contracts to get their balance, we did this in 2 phases:
- Override an existing function to make it send its balance ⇒ quite complicated as it would be different shifts for each contract and payload can be quite big (which reduces the balance of the contract)
- Override the first bytes of the targeted contracts to call the msg.sender with the contract balance
- But this is 11 bytes 5f5f5f5f47335AF15f5fF3, and we can optimize it with a simple selfdestruct operation which sends all the balance to the last item (address) on the stack
- Which is only 2 bytes 33FF!
Now we make a script to compute the bitswaps necessary for a provided contract to have 33FF as first 2 bytes in its code.
Example of outputs:
Using Google BigQuery Ethereum database, we exported all biggest Ethereum address balance that have code and balance > 5 ETH. And made a script to generate a batch input string (like: 0x00000000219ab540356cBB839Cbe05303d7705Fa:7:6:3:1:15:14:13:12:11:10:9,0xC02aaA39b223FE8D0A0e5C4F27eAD9083C756Cc2:7:6:3:1:15:14:13:12:11:8,0x8315177aB297bA92A06054cE80a67Ed4DBd7ed3a:7:6:3:1:15:14:13:12:11:10:9) for the challenge.
Once the instance is setup, we just have to call (with a simple transfer) the contracts we have overriden to get their balances. To simplify this process, we deployed a batch contract for 500 addresses at a time, avoiding doing many transactions (which can take a lot of time if you have thousands to do).
The issue we face now is that the more address/shifts we provide, the more the setup script takes time to process it, and at some point the instance just resets the connection, which creates a non-deterministic constraint. By doing a dichotomy we found the maximum to be around ~ 4000 contracts that could be processed and managed to outperform the current submissions.
2. Optimizations
Now the goal was to make the most out of our ~4,000 operations. We started looking at how we could factorize some operations in to one, by fixing the implementation instead of proxied, for example. We started looking at rocketpool vault implementation and sage implementations.
Some safe implementations have a balance on mainnet (user mistakes?), so we can fix them! Doing this allows us to remove 2,000 out of the 4,000 addresses of the top 4,000, so huge optimization!
Unfortunately, for us, the challenge changed a few minutes before our optimization was ready. The new version now performs as many input as you want, with one input = one contract shift, thus killing the need to make optimization of the number of operations to perform.
We then submitted a “naive” attempt with the top 9,000+ contracts by balances on Ethereum mainnet, with one transfer tx to each. As the runner was processing ~70 shifts per minute, we did not have time to submit it in time. So, we submitted the inputs and transactions to perform before the end of the CTF to paradigm as they allowed players to give them inputs to run after the CTF for those who don’t have enough time to run their solutions.
In the end we finished with 44,940,629 points.
DRAGON TYRANT
Goal
Kill a Dragon.
Context
There’s a core contract that can issue NFTs. Each NFT has traits that define the strength, health and other characteristics of individual NFTs. When the contract is created, it mints an NFT for itself which he calls the Dragon. This Dragon has the maximum possible attack stat, and almost maximum defense (just missing 1 there).
The goal of the challenge is to find a way to burn the Dragon NFT.
Anyone has the ability to create one or several of these NFTs. But what is particular about this NFT contract is that the randomness is provided by an off-chain randomness operator. Its role is simple. Whenever randomness is requested in the contract, the operator will submit a hash that can be used as a seed for various actions that need some form of randomness.
When minting new NFTs, this process will give the contract randomness to be able to generate random traits.
The contract gives the ability to fight other NFTs. The owner of an NFT can specify another NFT id and a fight will happen once the randomness operator provides a new randomness seed. When two NFTs fight, the losing one is burned.
There is also an item shop that sells swords and shields that can increase the strength (attack) and construction (defense) of one of your NFTs.
Finding our Hero
While we’re able to mint as many NFTs as we want, we want to have one that has sufficient traits to be able to defeat the Dragon. The maximum value for the stats is uint40.max.
If we look closer into how the fight mechanism works, we see that we need to have an attack that is greater than its defense to inflict damages to the Dragon; and to survive an attack from the Dragon, we need to have a defense greater or equal to its attack.
So, we would need to find a “Hero” with uint40.max for its attack and defense. Knowing that the generation of the traits is random, the odds of finding this knight are 0.0000000000000000000000008% , making it impossible to brute-force.
(Medieval) Shopping Time
We’re moving our attention to the item shop now. It sells 3 items, a sword that increases the attack by 1 << 38 and a shield that does the same for defense. Both cost 1 ETH and we are given 1000 ETH initially. There’s also a legendary sword that increases the attack by uint40.max but its cost is too high for us to afford.
Looking at the cheaper items, the stat is increased by 1 << 38, which is ~25% of the value of uint40.max . So, the odds to find a Hero capable to attaining maximum attack and defense when equiped with the sword and the shield now jumps to 6.25% !
Preparing to fight
Now that we know how to defeat the dragon, let’s look at how the fight is unfolding in the contracts.
First, we can see that both fighters are loaded in memory using _getFighter. This is where the stats of our Hero are increased with the equiped weapon and shield.
The fight is composed of 256 rounds. For each round, the attacker and attackee can either attack or defend. If you defend while the opponent attacks, you will suffer the difference between the attack and defense as damage. If you don’t defend, you take the full attack as damage.
There is a small detail I omitted: the Dragon has 60 HP, while the Hero has only 1 HP. There is absolutely no room for luck in this fight. If the Hero forgets to defend even once, the fight is over. To define the sequence of action, our smart contract is given the ability to send an uint256 value where each bit of the value defines the action of each round: 1 is attack, 0 is defense.
The attackee, on the other hand, is using a randomness generator that uses the seed in the contract to generate the sequence of actions. This randomness generator uses the ecMul precompile, which performs a scalar multiplication on the elliptic curve alt_bn128
Knowing this, we can say that our goal is to return ~attackeeInput when getInput is called on our contract.
This can be translated to ~randomness.generate(seed, 1) (round is 1 as we will make sure no mints happen during the fight processing).
Something very important to note is that all these fight steps are happening WHEN the randomness operators sends the new seed. This means that there is no way to retrieve the value of the current seed when the fight is happening, as the seed is not stored in a public storage variable or exposed via any view call.
We are now facing the real problem of this challenge: how can we predict all the moves that the Dragon will do in his fight, as otherwise we are guaranteed to get obliterated.
The Dragon’s downfall inside the crystal
Now our task has taken another dimension. We need to predict the next seed that the randomness operator will provide in order to be able to perfectly fight against the Dragon. Let’s have a look at how the randomness operator actually provides randomness to the contracts.
Now, there’s something important to note here. The randomness comes from a call to random.randBytes(32) , which is a standard python utility to retrieve random numbers and bytes. It is something to know about.
That’s where things are starting to get interesting. It would be possible to predict the next random number generated by the randomness operator if we know enough previous values generated by the same instance.
And we have been lucky to stumble across https://github.com/tna0y/Python-random-module-cracker
This library is able to predict the next random number generated if it is given 624 numbers that were previously generated, in their generation order.
Configuring the prediction
In order to retrieve 624 numbers, we need to retrieve 78 seeds (each is composed of 8 numbers) provided by the randomness operator, feed them into our prediction script, and generate the next 8 numbers to predict the next seed that the operator is going to send to the contract in a future transaction.
To do this, we crafted a Contract that handles all internal solidity actions, a node script that takes care of invoking the contract and a python script to generate the next seed once we have gathered enough number. The contract will be able to mint the Heroes, and the script will call the Contract 78 times, registering the seed that the randomness operator is providing each time.
Once it reached the required number of seeds, the script generates the next seed, buys the sword and shield, equips the Hero, and starts the fight, knowing in advance all the moves that the Dragon will perform. This happens in the fight() method, and works only if the node script finished its work and called setNextSeed(bytes32).
Here are all the scripts used to solve this problem, DragonDestroyer being the main exploit contract.
On this one, we would need to call mint as many times as we need it. Once we have called setNextSeed with the predicted next “randomly” generated seed, then we can call fight() and our Hero should take care of the Dragon.
With this nodejs and python scripts we can perform all the required transactions automatically and properly generate the next seed.
And here’s the python script that is called by the nodejs script. It takes the 624 numbers as input (one big bytes input holds all the concatenated seeds) and outputs the hash in a bytes32 format.
We killed the Dragon
We know that this was not the expected resolution. But it took advantage of another form of cryptographic flaw, which is weak random number generation.
It allowed us to be able to predict future random numbers generated by the operator if we had sufficient prior information. This allowed us to know in advance exactly when the Dragon will attack and defend, and we only had to do the exact opposite to win our prize.
PCTF{8r0_H4CK5_N54_1N_3VM}
Conclusion
Special thanks to Iulian Rotaru, Gauthier Mayer, Mathieu Willay, Ismaël Fall, Martin Saldinger and Loïc Titren who represented Kiln during this contest and shared their solutions above.
Also big thanks to Paradigm and especially samczsun for organising this new edition and being responsive during the competition.
See you next year, now back to work.
About Kiln
Kiln is the leading enterprise-grade staking platform, enabling institutional customers to stake assets, and to whitelabel staking functionality into their offering. Kiln runs validators on all major PoS blockchains, with over $2.2 billion crypto assets being programmatically staked, and running over 3% of the Ethereum network on a multi-cloud, multi-region infrastructure. Kiln also provides a validator-agnostic suite of products for fully automated deployment of validators, and reporting and commission management, enabling custodians, wallets and exchanges to streamline staking operations across providers. Kiln is also SOC2 Type 2 certified.
.png)
