This challenge involves a blockchain-like system that uses a chameleon hash function for transaction integrity. The goal is to exploit the chameleon hash properties to forge a transaction “Selling|flag|x” that allows us to buy the flag.
Mechanics
The app lets up perform a set of actions to interact with the chain:
- Work: Gives us some money
- Buy Gift: Appends a “Buy” entry followed by a “Selling|gift|100” onto the chain
- Refund oldest: Turns the oldest “Buy” transaction into a “Work|x” entry by internally forging a satisfying hash. (This is our entry point)
- Show: pretty obvious xd
- Rewrite: Gives us an arbitrary write to change any transaction in the chain.
Vulnerability Analysis
Since the concept of Chameleon hashes is pretty new to me, I wanted to look it up in some papers to better understand it. While there were some pretty interesting ones, especially this one, there wasn’t a clear implementation to compare to the challenge.
What also threw me off is that the challenge linked the library’s github repo as a hint, leading me to think that there was an unpatched issue with the library of some kind, but that led nowhere either.
I decided to play the cards I’ve been dealt, and read the code to know what exactly I’m poking into.
Chameleon Hashes
This hashing primitive is structured in a way similar to public key cryptosystems, where the hashing operation is done with a public and a private key.
The hashing operation itself is done using the public key, and whatever party holds the corresponding private key can forge a collision for any message to any corresponding hash.
In this implementation, the Public Key is self.pp, with the Private Key being self.td_ID, so it would be pretty obvious that our goal is to recover td_ID, but that didn’t occur to me straight away xd
The Rabbit Hole
Before looking for a way to recover the private key, I wanted to inspect the hashing function itself:
1
2
| def _Hash(self, L, m, r):
return self.pp[6] ** m * self.pp[5] ** r[0] * pair(r[1], self.pp[1] / (self.pp[0] ** self.ID)) * pair((self.pp[4] / (self.pp[3] ** self.ID)) ** L, r[2])
|
Since all the variable that come into play here are pretty known, I thought that it might be a good idea to find a way to substitute m while tweaking the randomness to keep the same hash value.
But if you look at this for more that 5 seconds, it’ll be clear why this is pretty much impossible: m is introduced as an exponent, paired with the fact that pairing group operations are done in a finite field, makes it Discrete Log Problem. So unless I have access to some advanced quantum computer, this path is pretty much dead.
The LEAK
Going back to the private key, we must find a way to somehow leak it. And surprise surprise, the server-side collision function does just that!
To recap, Col is the function that attempts to find a new randomness that would let us forge a satisfying hash for some new message. It derives td_b_ID from the private key to prevent reuse attacks, but it’s not prevented here.
If you look closely at the new randomess:
1
| return (r[0] + (m - m_p) * td_b_ID[0], r[1] * (td_b_ID[1] * (self.pp[4] / (self.pp[3] ** self.ID)) ** (s * L)) ** (m - m_p), r[2] * (td_b_ID[2] * (self.pp[1] / (self.pp[0] ** self.ID)) ** s) ** (m_p - m))
|
the derived secret key is linear to the randomness value (and some other value which doesn’t really matter).
The solution
Since each component gof the derived secret is linear to Δ_ri (the difference between new_randomness_i and old_randomness_i) aswell as the difference between the messages, it essentially boils down to solving a linear equation to recover tdb_ID. The solution also eliminated the new-added randomness (s,tp) so we pretty much end up with The private key td_ID.
With the private key recovered, we can forge collisions just like the server, and the rest is history
Script
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
| from charm.toolbox.pairinggroup import PairingGroup, ZR
from pwn import *
from tqdm import trange
Local = False
if Local:
HOST = "192.168.1.11"
PORT = 1445
else:
HOST = "s1.r3.ret.sh.cn"
PORT = 32316
io = remote(HOST, PORT)
P = PairingGroup("SS512")
io.recvuntil(b"number! ")
ll = io.recvline().decode().strip()[1:-1].split(", ")
pp = [P.deserialize(x[1:-1].encode()) for x in ll]
def send_cmd(i: int):
"""
1. Work, work
2. Buy gift
3. Refund oldest gift
4. Show my bill
5. Write my bill
6. Run payment
"""
io.recvuntil(b"Run payment\n> ")
io.sendline(str(i).encode())
def get_bill():
send_cmd(4)
lines = io.recvuntil(b"END", drop=True).decode().strip().split("\n")
bill = []
counter = 0
entry = {}
for l in lines:
match (counter %4):
case 0:
hp = l.split(" ")[1]
entry["HP"] = P.deserialize(hp.encode())
case 1:
r = l[5:-2].split("', '")
R = tuple(P.deserialize(x.encode()) for x in r)
entry["R"] = R
case 2:
L = l[3:]
entry["L"] = L
case 3:
M = l[3:]
entry["M"] = M
if counter %4 == 3:
bill.append(entry)
entry = {}
counter +=1
return bill
def hashy(e):
return P.hash(e, ZR)
send_cmd(2)
bill_old = get_bill()
c = bill_old[0]["HP"]
target_block_old = bill_old[1]
R_old = target_block_old["R"]
HP_prev = target_block_old["HP"]
M_old = target_block_old["M"]
L_1 = target_block_old["L"]
full_M_old = P.serialize(HP_prev).decode() + M_old
send_cmd(3)
hint_hash_m = io.recvline().decode().strip()
hint_hash_mp = io.recvline().decode().strip()
bill_new = get_bill()
target_block_new = bill_new[1]
R_new = target_block_new["R"]
M_new = target_block_new["M"]
full_M_new = P.serialize(HP_prev).decode() + M_new
m_hash_old = hashy(full_M_old)
m_hash_new = hashy(full_M_new)
delta_hash_observed = m_hash_old - m_hash_new
delta_m_inv = delta_hash_observed ** -1
rec_t = (R_new[0] - R_old[0]) * delta_m_inv
L_hash = hashy(L_1)
t1 = (R_new[1] / R_old[1]) ** delta_m_inv
t2 = (R_new[2] / R_old[2]) ** (c * L_hash * delta_m_inv)
rec_td_ID_1 = t1 * t2
ID = hashy("ADMIN")
td_ID = (rec_t, rec_td_ID_1)
def Col(L, m, r, m_p):
L = P.hash(L, ZR)
m = P.hash(m, ZR)
print(f"{P.serialize(m).decode()}")
m_p = P.hash(m_p, ZR)
print(f"{P.serialize(m_p).decode()}")
s, t_p = P.random(ZR), P.random(ZR)
td_b_ID = (td_ID[0], td_ID[1] * (pp[4] / (pp[3] ** ID)) ** (L * t_p), (pp[1] / (pp[0] ** ID)) ** t_p)
return (r[0] + (m - m_p) * td_b_ID[0], r[1] * (td_b_ID[1] * (pp[4] / (pp[3] ** ID)) ** (s * L)) ** (m - m_p), r[2] * (td_b_ID[2] * (pp[1] / (pp[0] ** ID)) ** s) ** (m_p - m))
target = "Selling|flag|0"
l = target_block_new["L"]
m = full_M_new
r = R_new
m_p = P.serialize(HP_prev).decode() + target
forged_r = Col(l,m,r,m_p)
forged_r_repr = tuple(P.serialize(x).decode() for x in forged_r)
send_cmd(5)
io.sendline(b"1")
io.sendline(target.encode())
io.sendline(str(forged_r_repr).encode())
#----WOOOOOOORK
for _ in trange(30):
send_cmd(1)
send_cmd(2)
send_cmd(2)
send_cmd(2)
send_cmd(6)
io.interactive()
|
R3CTF{N0w-Y0U_@2E-7H3-GoD-1n-THe_D0M4IN-0f_id3NTl7y-b@5ED_ChaMeleon_H@sh_YOu_c4n_d0_any_7r@d30}
