| Curta / Plonky2x Audit Report (0) | 2024.02.27 |
|---|---|
| zkSummit11 @ Athens (0) | 2024.02.24 |
| Paradigm CTF 2023: "Cryptography Challenges" (0) | 2023.10.30 |
| Scroll's Security Measure Seminar (0) | 2023.10.25 |
| Scroll zkEVM Audit Report (0) | 2023.10.17 |
https://hackmd.io/qS36EcIASx6Gt_2uNwlK4A
Curta / Plonky2x Audit Report - HackMD
owned this note owned this note Published Linked with GitHub # Curta / Plonky2x Audit Report  Audited by Allen Roh (rkm0959). Report Published by KALOS. # ABOUT US Pione
hackmd.io
| zkSummit11: Insights from and on Taxonomy of ZKP Vulnerabilities (0) | 2024.04.21 |
|---|---|
| zkSummit11 @ Athens (0) | 2024.02.24 |
| Paradigm CTF 2023: "Cryptography Challenges" (0) | 2023.10.30 |
| Scroll's Security Measure Seminar (0) | 2023.10.25 |
| Scroll zkEVM Audit Report (0) | 2023.10.17 |
| zkSummit11: Insights from and on Taxonomy of ZKP Vulnerabilities (0) | 2024.04.21 |
|---|---|
| Curta / Plonky2x Audit Report (0) | 2024.02.27 |
| Paradigm CTF 2023: "Cryptography Challenges" (0) | 2023.10.30 |
| Scroll's Security Measure Seminar (0) | 2023.10.25 |
| Scroll zkEVM Audit Report (0) | 2023.10.17 |
We participated in Paradigm CTF with KALOS team members and some friends (minaminao, taek, epist, gss1, pia).
During the competition, there were 2 challenges with the tag "cryptography" and I ended up getting first blood on both.
|
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
|
#!/usr/bin/env python3
from Crypto.Util.number import *
import random
import os
import hashlib
FLAG = os.getenv("FLAG", "PCTF{flag}").encode("utf8")
FLAG = bytes_to_long(FLAG[5:-1])
assert FLAG.bit_length() < 384
BITS = 1024
def xor(a, b):
return bytes([i ^ j for i, j in zip(a, b)])
# This doesn't really matter right???
def custom_hash(n):
state = b"\x00" * 16
for i in range(len(n) // 16):
state = xor(state, n[i : i + 16])
for _ in range(5):
state = hashlib.md5(state).digest()
state = hashlib.sha1(state).digest()
state = hashlib.sha256(state).digest()
state = hashlib.sha512(state).digest() + hashlib.sha256(state).digest()
value = bytes_to_long(state)
return value
def fiat_shamir():
p = getPrime(BITS)
g = 2
y = pow(g, FLAG, p)
v = random.randint(2, 2**512)
t = pow(g, v, p)
c = custom_hash(long_to_bytes(g) + long_to_bytes(y) + long_to_bytes(t))
r = (v - c * FLAG) % (p - 1)
assert t == (pow(g, r, p) * pow(y, c, p)) % p
return (t, r), (p, g, y)
while True:
resp = input("[1] Get a random signature\n[2] Exit\nChoice: ")
if "1" in resp:
print()
(t, r), (p, g, y) = fiat_shamir()
print(f"t = {t}\nr = {r}")
print()
print(f"p = {p}\ng = {g}\ny = {y}")
print()
elif "2" in resp:
print("Bye!")
exit()
|
cs |
So we are given a random signature oracle. To be precise, we know $t, r, p, g, y$ such that $$c = \text{hash}(g, y, t), \quad r \equiv (v - c \cdot flag) \pmod{p-1}$$ The key part I used is that we know $c, r, p$ and that $flag < 2^{384}$ as well as $v < 2^{512}$. In other words, we are finding the $0 < flag < 2^{384}$ such that $c \cdot flag + r \pmod{p-1}$ is less than $2^{512}$. This is a classic task suitable for lattice reduction (a bit overkill, but it is) and similar tricks have appeared in CTFs so much that I have a whole repository on this (https://github.com/rkm0959/Inequality_Solving_with_CVP)
A good heuristic to why this would work is that the "probability" of a value $flag$ satisfying $c \cdot flag + r \pmod{p-1} < 2^{512}$ would be around $2^{512} / p$, which is far less than $1/2^{384}$ as $p$ is 1024 bits. This means that there would be a unique $flag$ that satisfies our needs.
To understand how to solve this "linear inequality with modulo" task, see https://rkm0959.tistory.com/188 (korean).
|
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
|
from sage.all import *
from pwn import *
from Crypto.Util.number import GCD
def ceil(n, m): # returns ceil(n/m)
return (n + m - 1) // m
def is_inside(L, R, M, val): # is L <= val <= R in mod M context?
if L <= R:
return L <= val <= R
else:
R += M
if L <= val <= R:
return True
if L <= val + M <= R:
return True
return False
def optf(A, M, L, R): # minimum nonnegative x s.t. L <= Ax mod M <= R
if L == 0:
return 0
if 2 * A > M:
L, R = R, L
A, L, R = M - A, M - L, M - R
cc_1 = ceil(L, A)
if A * cc_1 <= R:
return cc_1
cc_2 = optf(A - M % A, A, L % A, R % A)
return ceil(L + M * cc_2, A)
# check if L <= Ax (mod M) <= R has a solution
def sol_ex(A, M, L, R):
if L == 0 or L > R:
return True
g = GCD(A, M)
if (L - 1) // g == R // g:
return False
return True
## find all solutions for L <= Ax mod M <= R, S <= x <= E:
def solve(A, M, L, R, S, E):
# this is for estimate only : if very large, might be a bad idea to run this
print("Expected Number of Solutions : ", ((E - S + 1) * (R - L + 1)) // M + 1)
if sol_ex(A, M, L, R) == False:
return []
cur = S - 1
ans = []
num_sol = 0
while cur <= E:
NL = (L - A * (cur + 1)) % M
NR = (R - A * (cur + 1)) % M
if NL > NR:
cur += 1
else:
val = optf(A, M, NL, NR)
cur += 1 + val
if cur <= E:
ans.append(cur)
# remove assert for performance if needed
assert is_inside(L, R, M, (A * cur) % M)
num_sol += 1
print("Actual Number of Solutions : ", num_sol)
return ans
# conn = remote("oven.challenges.paradigm.xyz", 1337)
# conn.interactive()
import hashlib
from Crypto.Util.number import *
def xor(a, b):
return bytes([i ^ j for i, j in zip(a, b)])
# This doesn't really matter right???
def custom_hash(n):
state = b"\x00" * 16
for i in range(len(n) // 16):
state = xor(state, n[i : i + 16])
for _ in range(5):
state = hashlib.md5(state).digest()
state = hashlib.sha1(state).digest()
state = hashlib.sha256(state).digest()
state = hashlib.sha512(state).digest() + hashlib.sha256(state).digest()
value = bytes_to_long(state)
return value
t = 93427683041905342461173547022600938643986887324972032834291939142561139490252265979618477433690413153065906221518481848227204925109596682649424431709625280133746760813834179099858484483652348113289609400674325409313902686091936601023976041128497642819529787946866157016217668015647432593957212819330706662552
r = 118742916848068745441234425121114897870051115198012668332112268094669581171444207495264796187702240967886273172282936547873545351825602051457018801135490983227564157979548997162173927440795170927696473299845487953514965643146540163956783643164820892016837035894476678034631205573666641222349277397600109205124
p = 126549310493151963326469876679724603661026366918265538391139061164994266707511395259083420603797826570096038735637035531704734213415007496749352216356840971790966322793226620694976878837854388424723443760043794854992519120259435122442271146978894991534180108105270279798030108380275673703977920882358759270081
g = 2
y = 101749117219274577198619316763589342740512542428910664337482178675253076795143579139493733233731229068585593656754291831105189837876269162333709022495477051005897166911586115461217424920314778304390479804373263955110732503700846048681418836722374515970914402818776396927744121752161147483063673287114906716300
c = custom_hash(long_to_bytes(g) + long_to_bytes(y) + long_to_bytes(t))
c //= 15
lmao = r % 15
r = (r - r % 15) // 15
M = (p - 1) // 15
print(GCD(c, M))
lst = solve(c, M, (-r) % M , ((1 << 512) // 15 - r + M) % M, 0, 1 << 384)
print(lst)
print(long_to_bytes(10803675063719384436548220153547010608867399889700922150272564339681282264952460761794626241561264720352594960927090))
|
cs |
The codebase is quite large, so I can't upload it all here. A quick summary -
Let's start with getting the max attack and defense. We just need matching extcodehash - so whatever we do in the constructor doesn't matter, as long as we return the same code. Therefore we can do some nice tricks as follows.
|
1
2
3
4
5
6
7
8
9
10
11
|
contract ItemShop2 is ItemShop {
constructor(bytes memory code) {
// write this
_itemInfo[4] = ItemInfo({name: "A", slot: EquipmentSlot.Weapon, value: type(uint40).max, price: 0}); // example
_itemInfo[5] = ItemInfo({name: "B", slot: EquipmentSlot.Shield, value: type(uint40).max, price: 0}); // example
_mint(msg.sender, 4, 1, "");
_mint(msg.sender, 5, 1, "");
assembly { return ( add(code, 0x20), mload(code)) }
}
}
|
cs |
Now we can equip this accordingly to get max attack/defense. We now have to predict the moves.
When the off-chain entity resolves the randomness, it first generates the random values for the mints' traits.
Only after that, it generates the random value for the dragon's move. This can be seen in the code below.
|
1
2
3
4
5
6
7
8
9
|
function resolveRandomness(bytes32 seed) external override {
if (msg.sender != address(factory.randomnessOperator())) {
revert Unauthorized(msg.sender);
}
_lastOffchainSeed = seed;
uint256 nextRound = _resolveMints();
_resolveFight(nextRound);
}
|
cs |
We can also fetch the traits, as the NFT contract provides a public function for it. This implies that we can fetch all the previously generated values for the off-chain provided seed. In other words, if we can compute $\text{rand}(seed, i + 1)$ from $\text{rand}(seed, i)$, we would be done.
|
1
2
3
|
function _generateRandomness(uint256 round) internal view returns (bytes32 rand) {
rand = randomness.generate(_lastOffchainSeed, round + 1);
}
|
cs |
Now let's look at the randomness itself.
|
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
|
// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.19;
import "./OwnedUpgradeable.sol";
import "./Interfaces.sol";
contract Randomness is IRandomness {
error AlreadySet();
// https://eips.ethereum.org/EIPS/eip-197 Y^2 = X^3 + 3
// a generator of alt_bn128 (bn254)
uint256 public constant Gx = 1;
uint256 public constant Gy = 2;
uint256 public immutable Px;
uint256 public immutable Py;
uint256 public immutable Qx;
uint256 public immutable Qy;
uint256 public constant fieldOrder =
uint256(21888242871839275222246405745257275088696311157297823662689037894645226208583);
uint256 public constant groupOrder =
uint256(21888242871839275222246405745257275088548364400416034343698204186575808495617);
constructor() {
uint256 P_x;
uint256 P_y;
uint256 Q_x;
uint256 Q_y;
bytes32 r = bytes32(uint256(0x123456789));
assembly {
mstore(0x80, Gx)
mstore(0xa0, Gy)
mstore(0xc0, r)
if iszero(staticcall(gas(), 0x07, 0x80, 0x60, 0x80, 0x40)) { revert(0, 0) }
P_x := mload(0x80)
P_y := mload(0xa0)
mstore(0x80, Gx)
mstore(0xa0, Gy)
mstore(0xc0, r)
mstore(0xc0, keccak256(0xc0, 0x20))
if iszero(staticcall(gas(), 0x07, 0x80, 0x60, 0x80, 0x40)) { revert(0, 0) }
Q_x := mload(0x80)
Q_y := mload(0xa0)
}
Px = P_x;
Py = P_y;
Qx = Q_x;
Qy = Q_y;
}
/// @notice Generates a sequence of random numbers from an initial seed
/// @param seed The initial seed
/// @param rounds The round to generate
/// @return rand The generated randomness for the round
function generate(bytes32 seed, uint256 rounds) external view override returns (bytes32 rand) {
uint256 Q_x = Qx;
uint256 Q_y = Qy;
uint256 P_x = Px;
uint256 P_y = Py;
assembly {
mstore(0x00, P_x)
mstore(0x20, P_y)
mstore(0x40, seed)
for { let i := 0 } lt(i, rounds) { i := add(i, 1) } {
if iszero(staticcall(gas(), 0x07, 0x00, 0x60, 0x40, 0x40)) { revert(0, 0) }
}
mstore(0x00, Q_x)
mstore(0x20, Q_y)
if iszero(staticcall(gas(), 0x07, 0x00, 0x60, 0x40, 0x40)) { revert(0, 0) }
rand := mload(0x40)
mstore(0x40, 0x80)
}
}
}
|
cs |
So it first takes $r$ as 0x123456789 and sets $P = r \cdot G$ and $Q = \text{hash}(r) \cdot G$. Then, the randomness is generated by iterating $seed \leftarrow (seed \cdot P).x$ for $round$ number of times and finishing with $out \leftarrow (seed \cdot Q).x$.
Now we see the idea - since we know the $(seed \cdot Q).x$ as the output, one can recover $seed \cdot Q$ where $seed$ is the result of $round$ iterations. Since we know the discrete-logarithm relations between $P$ and $Q$, this means that we can also recover $seed \cdot P$ - and taking the $x$ coordinate here would be the result of $round + 1$ iterations. Now doing $out \leftarrow (seed \cdot Q).x$ once again would be sufficient to get the randomness result for $\text{rand}(seed, round + 1)$. We have our theoretical exploit! Now on to the implementation.
To do this in a smart contract, the only hard part would be to recover the full elliptic curve point from the $x$ coordinate alone. To do this you need a modular square root, but since $p \equiv 3 \pmod{4}$ it's easy, (no Tonelli-Shanks) simply raise to $(p+1)/4$th power.
|
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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
|
// SPDX-License-Identifier: UNLICENSED
pragma solidity ^0.8.13;
import {Script, console2} from "forge-std/Script.sol";
import "../test/Counter.t.sol";
import "../src/ItemShop.sol";
import "../src/ItemShop2.sol";
import "../src/Challenge.sol";
contract Exploiter {
Challenge public challenge;
NFT public nft;
ItemShop public itemShop;
Factory public factory;
ItemShop2 public itemShop2;
Exploiter public lmao;
uint256 public cnter = 0;
uint256 public constant fieldOrder =
uint256(21888242871839275222246405745257275088696311157297823662689037894645226208583);
uint256 public constant groupOrder =
uint256(21888242871839275222246405745257275088548364400416034343698204186575808495617);
function exploit_part_1(address chall) external {
challenge = Challenge(chall);
factory = challenge.FACTORY();
nft = challenge.TOKEN();
itemShop = challenge.ITEMSHOP();
itemShop2 = new ItemShop2(address(itemShop).code);
itemShop2.setApprovalForAll(address(nft), true);
address[] memory myself = new address[](1);
myself[0] = address(this);
nft.batchMint(myself);
}
function exploit_part_2() external {
address[] memory myself = new address[](1);
myself[0] = address(this);
nft.batchMint(myself);
nft.fight(1, 0);
}
function onERC721Received(address sender, address from, uint256 tokenId, bytes memory data) external returns (bytes4) {
cnter += 1;
if(cnter == 1) {
nft.equip(tokenId, address(itemShop2), 4);
nft.equip(tokenId, address(itemShop2), 5);
}
return this.onERC721Received.selector;
}
function modExp(uint256 _b, uint256 _e, uint256 _m) public returns (uint256 result) {
assembly {
let pointer := mload(0x40)
mstore(pointer, 0x20)
mstore(add(pointer, 0x20), 0x20)
mstore(add(pointer, 0x40), 0x20)
mstore(add(pointer, 0x60), _b)
mstore(add(pointer, 0x80), _e)
mstore(add(pointer, 0xa0), _m)
let value := mload(0xc0)
if iszero(call(gas(), 0x05, 0, pointer, 0xc0, pointer, 0x20)) {
revert(0, 0)
}
result := mload(pointer)
mstore(0x40, pointer)
}
}
function getInput(FighterVars calldata attacker, FighterVars calldata attackee) external returns (uint256 inputs) {
Trait memory trait = nft.traits(2);
uint256 prev_rand = 0;
prev_rand += uint256(trait.rarity);
prev_rand += uint256(trait.strength) << 16;
prev_rand += uint256(trait.dexterity) << 56;
prev_rand += uint256(trait.constitution) << 96;
prev_rand += uint256(trait.intelligence) << 136;
prev_rand += uint256(trait.wisdom) << 176;
prev_rand += uint256(trait.charisma) << 216;
// recover the elliptic curve point
uint256 cube_3_3 = modExp(prev_rand, 3, fieldOrder) + 3;
uint256 y_val = modExp(cube_3_3, (fieldOrder + 1) / 4, fieldOrder);
uint256 interim;
assembly {
interim := mload(0x40)
}
assembly {
let pointer := mload(0x40)
mstore(pointer, prev_rand)
mstore(add(pointer, 0x20), y_val)
mstore(add(pointer, 0x40), 0x200ac28172d3dfaf595636a5d34fc6a98f3168b32317278ab95d95792e3b4f8f)
if iszero(staticcall(gas(), 0x07, pointer, 0x60, pointer, 0x40)) { revert(0, 0)}
interim := mload(pointer)
mstore(0x40, pointer)
}
uint256 Qx = 2771061477252358712132284804733770040260252456558485434530149143843066948317;
uint256 Qy = 21636887117896825552852388732829976843920120171647088092176094089927511555925;
assembly {
let pointer := mload(0x40)
mstore(pointer, Qx)
mstore(add(pointer, 0x20), Qy)
mstore(add(pointer, 0x40), interim)
if iszero(staticcall(gas(), 0x07, pointer, 0x60, pointer, 0x40)) { revert(0, 0)}
interim := mload(pointer)
mstore(0x40, pointer)
}
return type(uint256).max - interim;
}
function onERC1155Received(address, address, uint256, uint256, bytes calldata)
external
pure
returns (bytes4)
{
return this.onERC1155Received.selector;
}
function onERC1155BatchReceived(address, address, uint256[] calldata, uint256[] calldata, bytes calldata)
external
pure
returns (bytes4)
{
return this.onERC1155BatchReceived.selector;
}
}
contract CounterScript is Script {
Challenge challenge;
NFT nft;
ItemShop itemShop;
Factory factory;
ItemShop2 itemShop2;
Exploiter lmao;
uint256 public constant fieldOrder =
uint256(21888242871839275222246405745257275088696311157297823662689037894645226208583);
uint256 public constant groupOrder =
uint256(21888242871839275222246405745257275088548364400416034343698204186575808495617);
function setUp() public {}
function run() public {
vm.startBroadcast();
challenge = Challenge(0x4c2f201aFd08F986BDeed4907C263795c1510F75);
/*lmao = new Exploiter();
console2.log(address(lmao));
lmao.exploit_part_1(address(challenge));
vm.stopBroadcast();*/
lmao = Exploiter(0xf25888e0B386Ed0739B0d2D77CE68B6e1E0583b5);
console2.log(lmao.cnter());
lmao.exploit_part_2();
console2.logBool(challenge.isSolved());
vm.stopBroadcast();
}
}
|
cs |
| Curta / Plonky2x Audit Report (0) | 2024.02.27 |
|---|---|
| zkSummit11 @ Athens (0) | 2024.02.24 |
| Scroll's Security Measure Seminar (0) | 2023.10.25 |
| Scroll zkEVM Audit Report (0) | 2023.10.17 |
| ZKP Security Seminar @ SpearbitDAO (1) | 2023.07.27 |
https://twitter.com/Scroll_ZKP/status/1716781095138861158
X에서 Scroll 📜 님
This week, we'll be hosting an online webinar to dive into our security measures, and you're invited! We'll be joined by auditing collaborators from @immunefi, @zellic_io, @trailofbits, and @OpenZeppelin. 🗓 Save the date: October 25th, at 9:00AM EST. ht
twitter.com
| zkSummit11 @ Athens (0) | 2024.02.24 |
|---|---|
| Paradigm CTF 2023: "Cryptography Challenges" (0) | 2023.10.30 |
| Scroll zkEVM Audit Report (0) | 2023.10.17 |
| ZKP Security Seminar @ SpearbitDAO (1) | 2023.07.27 |
| A fun story on "Membership Proofs" (0) | 2022.12.07 |
제가 참가한 보안감사 리포트가 공개되었습니다 :)
| Paradigm CTF 2023: "Cryptography Challenges" (0) | 2023.10.30 |
|---|---|
| Scroll's Security Measure Seminar (0) | 2023.10.25 |
| ZKP Security Seminar @ SpearbitDAO (1) | 2023.07.27 |
| A fun story on "Membership Proofs" (0) | 2022.12.07 |
| DFX Finance Attack Overview (0) | 2022.11.16 |
| Scroll's Security Measure Seminar (0) | 2023.10.25 |
|---|---|
| Scroll zkEVM Audit Report (0) | 2023.10.17 |
| A fun story on "Membership Proofs" (0) | 2022.12.07 |
| DFX Finance Attack Overview (0) | 2022.11.16 |
| CODEGATE 2022: A Survey on Price Oracle Attacks (0) | 2022.11.05 |
https://twitter.com/RareSkills_io/status/1600279157942161408
트위터에서 즐기는 RareSkills
“1/ RareSkills is proud to present a totally new way to allowlist addresses for presales and airdrops. The gas efficiency soundly beats ECDSA signatures and Merkle Trees. The method is to use old fashion RSA signatures, but with a lot of tricks. Links an
twitter.com
https://twitter.com/rkm0959/status/1600312617310253056
트위터에서 즐기는 rkm0959
“If I'm not mistaken, the contract is vulnerable as you can create signatures for a lot of addresses. This is why cryptography is hard, and needs a lot of attention.”
twitter.com
| Scroll zkEVM Audit Report (0) | 2023.10.17 |
|---|---|
| ZKP Security Seminar @ SpearbitDAO (1) | 2023.07.27 |
| DFX Finance Attack Overview (0) | 2022.11.16 |
| CODEGATE 2022: A Survey on Price Oracle Attacks (0) | 2022.11.05 |
| A Look Back at Wyvern v2.2 1-day Vulnerabilities (0) | 2022.10.21 |