SekaiCTF 2025 Writeup #1 - Sceleri's Blog

Writeups for crypto challenges from SekaiCTF 2025. unfairy-ring will be in a separate post.

SSSS#

Description#

Shamir SendS the Secret to everyone
Author: Utaha

1
import random, os
2

3
p = 2 ** 256 - 189
4
FLAG = os.getenv("FLAG", "SEKAI{}")
5

6
def challenge(secret):
7
  t = int(input())
8
  assert 20 <= t <= 50, "Number of parties not in range"
9

10
  f = gen(t, secret)
11

12
  for i in range(t):
13
    x = int(input())
14
    assert 0 < x < p, "Bad input"
15
    print(poly_eval(f, x))
16

17
  if int(input()) == secret:
18
    print(FLAG)
19
    exit(0)
20
  else:
21
    print(":<")
22

23
def gen(degree, secret):
24
  poly = [random.randrange(0, p) for _ in range(degree + 1)]
25
  index = random.randint(0, degree)
26

27
  poly[index] = secret
28
  return poly
29

30
def poly_eval(f, x):
31
  return sum(c * pow(x, i, p) for i, c in enumerate(f)) % p
32

33
if __name__ == "__main__":
34
  secret = random.randrange(0, p)
35
  for _ in range(2):
36
    challenge(secret)

Solution#

In general, Shamir needs degree+1 points to reconstruct the polynomial. However if we have g with order t, the constant term overlaps with the t-th term, so the polynomial can be reconstructed with t points. Notice that (p-1)%29==0, so we can find g with order t=29. Since we have two queries, secret is the intersection of the coefficients of the two polynomials.

1
from sage.all import *
2
from pwn import *
3

4
context.log_level = 'debug'
5

6
p = 2 ** 256 - 189
7
R = PolynomialRing(GF(p), 'x')
8
t = 29
9

10
io = process(["python3", "chall.py"])
11

12
def sample():
13
    io.sendline(str(t).encode())
14
    while True:
15
        g = randint(1, p)
16
        g = pow(g, (p-1)//t, p)
17
        if g != 1:
18
            break
19
    shares = []
20
    for i in range(t):
21
        x0 = pow(g, i, p)
22
        io.sendline(str(x0).encode())
23
        y0 = int(io.recvline().strip())
24
        shares.append((x0, y0))
25
    return R.lagrange_polynomial(shares).coefficients()
26

27
s0 = sample()
28
io.sendline(b'1')
29
io.recvline()
30
s1 = sample()
31

32
for secret in set(s0) & set(s1):
33
    io.sendline(str(secret).encode())
34
    io.interactive()

I Dream of Genni#

Description#

I had the strangest dream last night.
Author: Neobeo

1
from hashlib import sha256
2
from Crypto.Cipher import AES
3

4
x = int(input('Enter an 8-digit multiplicand: '))
5
y = int(input('Enter a 7-digit multiplier: '))
6
assert 1e6 <= y < 1e7 <= x < 1e8, "Incorrect lengths"
7
assert x * y != 3_81_40_42_24_40_28_42, "Insufficient ntr-opy"
8

9
def dream_multiply(x, y):
10
    x, y = str(x), str(y)
11
    assert len(x) == len(y) + 1
12
    digits = x[0]
13
    for a, b in zip(x[1:], y):
14
        digits += str(int(a) * int(b))
15
    return int(digits)
16
assert dream_multiply(x, y) == x * y, "More like a nightmare"
17

18
ct = '75bd1089b2248540e3406aa014dc2b5add4fb83ffdc54d09beb878bbb0d42717e9cc6114311767dd9f3b8b070b359a1ac2eb695cd31f435680ea885e85690f89'
19
print(AES.new(sha256(str((x, y)).encode()).digest(), AES.MODE_ECB).decrypt(bytes.fromhex(ct)).decode())

Solution#

A simple branch and prune is enough to solve this challenge. We could use MITM to find larger pairs, but once the digits go beyond 10, it is nearly impossible to find a valid pair.

If we accept 1*3=03, we can still find some larger pairs like 8827954385162 * 987958187368 = 8721649812532036435033616.

1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <map>
5
#include <memory>
6
#include <cmath>
7
// g++ -O3 solve.cpp -o solve && ./solve
8

9
typedef __int128 int128_t;
10
std::ostream &operator<<(std::ostream &os, int128_t val)
11
{
12
    std::string result;
13
    bool is_negative = val < 0;
14
    if (is_negative)
15
    {
16
        val *= -1;
17
    }
18

19
    do
20
    {
21
        result.push_back((val % 10) + '0');
22
        val /= 10;
23
    } while (val != 0);
24

25
    if (is_negative)
26
    {
27
        result.push_back('-');
28
    }
29

30
    std::reverse(result.begin(), result.end());
31
    return (os << result);
32
}
33

34
typedef std::pair<int64_t, int64_t> vec2;
35
typedef std::tuple<int64_t, int64_t, int128_t> vec3;
36
std::vector<vec2> pairs;
37

38
void gen1(int digits, std::shared_ptr<std::vector<vec3>> &result)
39
{
40
    if (digits == 1)
41
    {
42
        for (const auto &pair : pairs)
43
        {
44
            int64_t a = pair.first;
45
            int64_t b = pair.second;
46
            result->emplace_back(a, b, a * b);
47
        }
48
        return;
49
    }
50

51
    int128_t mul = std::round(std::pow(10, digits - 1));
52
    int128_t mul1 = std::round(std::pow(10, digits));
53
    int128_t mul2 = mul * mul;
54
    if (mul % 10 != 0 || mul1 % 10 != 0 || mul2 % 10 != 0)
55
    {
56
        std::cerr << "Error: mul is not a multiple of 10" << std::endl;
57
        exit(1);
58
    }
59

60
    std::shared_ptr<std::vector<vec3>> result0 = std::make_shared<std::vector<vec3>>();
61
    gen1(digits - 1, result0);
62
    for (const auto &item : *result0)
63
    {
64
        int64_t x = std::get<0>(item);
65
        int64_t y = std::get<1>(item);
66
        int128_t xy_mul = std::get<2>(item);
67
        for (const auto &pair : pairs)
68
        {
69
            int64_t a = pair.first;
70
            int64_t b = pair.second;
71
            int128_t x2 = a * mul + x;
72
            int128_t y2 = b * mul + y;
73
            int128_t xy_mul2 = xy_mul + (a * b) * mul2;
74
            if ((x2 * y2 - xy_mul2) % mul1 == 0)
75
            {
76
                result->emplace_back(x2, y2, xy_mul2);
77
            }
78
        }
79
    }
80
}
81

82
void gen2(int digits, std::shared_ptr<std::vector<vec3>> &result)
83
{
84
    if (digits == 1)
85
    {
86
        for (const auto &pair : pairs)
87
        {
88
            int64_t a = pair.first;
89
            int64_t b = pair.second;
90
            for (int64_t i = 1; i < 10; i++)
91
            {
92
                int64_t x = 10 * i + a;
93
                int64_t y = b;
94
                result->emplace_back(x, y, 100 * i + a * b);
95
            }
96
        }
97
        return;
98
    }
99

100
    std::shared_ptr<std::vector<vec3>> result0 = std::make_shared<std::vector<vec3>>();
101
    gen2(digits - 1, result0);
102
    for (const auto &item : *result0)
103
    {
104
        int64_t x = std::get<0>(item);
105
        int64_t y = std::get<1>(item);
106
        int128_t xy_mul = std::get<2>(item);
107
        for (const auto &pair : pairs)
108
        {
109
            int64_t a = pair.first;
110
            int64_t b = pair.second;
111
            int128_t x2 = 10 * x + a;
112
            int128_t y2 = 10 * y + b;
113
            int128_t xy_mul2 = 100 * xy_mul + a * b;
114
            int128_t lower_bound = x2 * y2;
115
            int128_t upper_bound = (x2 + 1) * (y2 + 1);
116
            if (lower_bound <= xy_mul2 && xy_mul2 < upper_bound)
117
            {
118
                result->emplace_back(x2, y2, xy_mul2);
119
            }
120
        }
121
    }
122
}
123

124
#define M1 2
125
#define M2 3
126
#define M3 2
127

128
int main()
129
{
130
    for (int64_t i = 1; i < 10; i++)
131
        for (int64_t j = 1; j < 10; j++)
132
        {
133
            if (i * j >= 10)
134
            {
135
                pairs.push_back({i, j});
136
            }
137
        }
138

139
    std::shared_ptr<std::vector<vec3>> result1 = std::make_shared<std::vector<vec3>>();
140
    std::shared_ptr<std::vector<vec3>> result2 = std::make_shared<std::vector<vec3>>();
141
    gen1(M2 + M3, result1);
142

143
    std::cout << "Size1: " << result1->size() << std::endl;
144

145
    int128_t last_M3_digits = std::round(std::pow(10, M3));
146
    int128_t last_M3_digits2 = last_M3_digits * last_M3_digits;
147
    int128_t last_M2_digits = std::round(std::pow(10, M2));
148

149
    std::shared_ptr<std::map<uint64_t, std::vector<vec3>>> result_map = std::make_shared<std::map<uint64_t, std::vector<vec3>>>();
150
    for (const auto &item : *result1)
151
    {
152
        int64_t x = std::get<0>(item);
153
        int64_t y = std::get<1>(item);
154
        int128_t xy_mul = std::get<2>(item);
155
        uint64_t x2 = x / last_M3_digits;
156
        uint64_t y2 = y / last_M3_digits;
157
        uint64_t key = (x2 << 32) | y2;
158
        if (result_map->find(key) == result_map->end())
159
        {
160
            (*result_map)[key] = std::vector<vec3>();
161
        }
162
        (*result_map)[key].emplace_back(x, y, xy_mul);
163
    }
164
    result1.reset();
165
    std::cout << "Finished processing map" << std::endl;
166

167
    gen2(M1 + M2, result2);
168
    std::cout << "Size2: " << result2->size() << std::endl;
169
    for (const auto &item : *result2)
170
    {
171
        int64_t x = std::get<0>(item);
172
        int64_t y = std::get<1>(item);
173
        int128_t xy_mul = std::get<2>(item);
174
        uint64_t x2 = x % last_M2_digits;
175
        uint64_t y2 = y % last_M2_digits;
176
        uint64_t key = (x2 << 32) | y2;
177
        auto it = result_map->find(key);
178
        if (it != result_map->end())
179
        {
180
            for (const auto &pair : it->second)
181
            {
182
                int64_t x1 = std::get<0>(pair);
183
                int64_t y1 = std::get<1>(pair);
184
                int128_t xy_mul1 = std::get<2>(pair);
185
                int128_t x_final = (int128_t)x * last_M3_digits + (int128_t)x1 % last_M3_digits;
186
                int128_t y_final = (int128_t)y * last_M3_digits + (int128_t)y1 % last_M3_digits;
187
                int128_t xy_mul_final = xy_mul * last_M3_digits2 + xy_mul1 % last_M3_digits2;
188
                if (x_final * y_final == xy_mul_final)
189
                {
190
                    std::cout << "Found: x=" << x_final << ", y=" << y_final << ", x*y=" << xy_mul_final << std::endl;
191
                }
192
            }
193
        }
194
    }
195
}

Literal Eval#

Description#

Trust me, it’s 1000% safe to use literal eval in crypto!
Author: Sceleri

1
from Crypto.Util.number import bytes_to_long
2
from hashlib import shake_128
3
from ast import literal_eval
4
from secrets import token_bytes
5
from math import floor, ceil, log2
6
import os
7

8
FLAG = os.getenv("FLAG", "SEKAI{}")
9
m = 256
10
w = 21
11
n = 128
12
l1 = ceil(m / log2(w))
13
l2 = floor(log2(l1*(w-1)) / log2(w)) + 1
14
l = l1 + l2
15

16
class WOTS:
17
    def __init__(self):
18
        self.sk = [token_bytes(n // 8) for _ in range(l)]
19
        self.pk = [WOTS.chain(sk, w - 1) for sk in self.sk]
20

21
    def sign(self, digest: bytes) -> list[bytes]:
22
        assert 8 * len(digest) == m
23
        d1 = WOTS.pack(bytes_to_long(digest), l1, w)
24
        checksum = sum(w-1-i for i in d1)
25
        d2 = WOTS.pack(checksum, l2, w)
26
        d = d1 + d2
27

28
        sig = [WOTS.chain(self.sk[i], w - d[i] - 1) for i in range(l)]
29
        return sig
30

31
    def get_pubkey_hash(self) -> bytes:
32
        hasher = shake_128(b"\x04")
33
        for i in range(l):
34
            hasher.update(self.pk[i])
35
        return hasher.digest(16)
36

37
    @staticmethod
38
    def pack(num: int, length: int, base: int) -> list[int]:
39
        packed = []
40
        while num > 0:
41
            packed.append(num % base)
42
            num //= base
43
        if len(packed) < length:
44
            packed += [0] * (length - len(packed))
45
        return packed
46

47
    @staticmethod
48
    def chain(x: bytes, n: int) -> bytes:
49
        if n == 0:
50
            return x
51
        x = shake_128(b"\x03" + x).digest(16)
52
        return WOTS.chain(x, n - 1)
53

54
    @staticmethod
55
    def verify(digest: bytes, sig: list[bytes]) -> bytes:
56
        d1 = WOTS.pack(bytes_to_long(digest), l1, w)
57
        checksum = sum(w-1-i for i in d1)
58
        d2 = WOTS.pack(checksum, l2, w)
59
        d = d1 + d2
60

61
        sig_pk = [WOTS.chain(sig[i], d[i]) for i in range(l)]
62
        hasher = shake_128(b"\x04")
63
        for i in range(len(sig_pk)):
64
            hasher.update(sig_pk[i])
65
        sig_hash = hasher.digest(16)
66
        return sig_hash
67

68
class MerkleTree:
69
    def __init__(self, height: int = 8):
70
        self.h = height
71
        self.keys = [WOTS() for _ in range(2**height)]
72
        self.tree = []
73
        self.root = self.build_tree([key.get_pubkey_hash() for key in self.keys])
74

75
    def build_tree(self, leaves: list[bytes]) -> bytes:
76
        self.tree.append(leaves)
77

78
        if len(leaves) == 1:
79
            return leaves[0]
80

81
        parents = []
82
        for i in range(0, len(leaves), 2):
83
            left = leaves[i]
84
            if i + 1 < len(leaves):
85
                right = leaves[i + 1]
86
            else:
87
                right = leaves[i]
88
            hasher = shake_128(b"\x02" + left + right).digest(16)
89
            parents.append(hasher)
90

91
        return self.build_tree(parents)
92

93
    def sign(self, index: int, digest: bytes) -> list:
94
        assert 0 <= index < len(self.keys)
95
        key = self.keys[index]
96
        wots_sig = key.sign(digest)
97
        sig = [wots_sig]
98
        for i in range(self.h):
99
            leaves = self.tree[i]
100
            u = index >> i
101
            if u % 2 == 0:
102
                if u + 1 < len(leaves):
103
                    sig.append((0, leaves[u + 1]))
104
                else:
105
                    sig.append((0, leaves[u]))
106
            else:
107
                sig.append((1, leaves[u - 1]))
108
        return sig
109

110
    @staticmethod
111
    def verify(sig: list, digest: bytes) -> bytes:
112
        wots_sig = sig[0]
113
        sig = sig[1:]
114
        pk_hash = WOTS.verify(digest, wots_sig)
115
        root_hash = pk_hash
116
        for (side, leaf) in sig:
117
            if side == 0:
118
                root_hash = shake_128(b"\x02" + root_hash + leaf).digest(16)
119
            else:
120
                root_hash = shake_128(b"\x02" + leaf + root_hash).digest(16)
121
        return root_hash
122

123
class Challenge:
124
    def __init__(self, h: int = 8):
125
        self.h = h
126
        self.max_signs = 2 ** h - 1
127
        self.tree = MerkleTree(h)
128
        self.root = self.tree.root
129
        self.used = set()
130
        self.before_input = f"public key: {self.root.hex()}"
131

132
    def sign(self, num_sign: int, inds: list, messages: list):
133
        assert num_sign + len(self.used) <= self.max_signs
134
        assert len(inds) == len(set(inds)) == len(messages) == num_sign
135
        assert self.used.isdisjoint(inds)
136
        assert all(b"flag" not in msg for msg in messages)
137
        sigs = []
138
        for i in range(num_sign):
139
            digest = shake_128(b"\x00" + messages[i]).digest(32)
140
            sigs.append(self.tree.sign(inds[i], digest))
141
        self.used.update(inds)
142
        return sigs
143

144
    def next(self):
145
        new_tree = MerkleTree(self.h)
146
        digest = shake_128(b"\x01" + new_tree.root).digest(32)
147
        index = next(i for i in range(2 ** self.h) if i not in self.used)
148
        sig = new_tree.sign(index, digest)
149
        self.tree = new_tree
150
        return {
151
            "root": new_tree.root,
152
            "sig": sig,
153
            "index": index,
154
        }
155

156
    def verify(self, sig: list, message: bytes):
157
        digest = shake_128(b"\x00" + message).digest(32)
158
        for i, s in enumerate(reversed(sig)):
159
            if i != 0:
160
                digest = shake_128(b"\x01" + digest).digest(32)
161
            digest = MerkleTree.verify(s, digest)
162
        return digest == self.root
163

164
    def get_flag(self, sig: list):
165
        if not self.verify(sig, b"Give me the flag"):
166
            return {"message": "Invalid signature"}
167
        else:
168
            return {"message": f"Congratulations! Here is your flag: {FLAG}"}
169

170
    def __call__(self, type: str, **kwargs):
171
        assert type in ["sign", "next", "get_flag"]
172
        return getattr(self, type)(**kwargs)
173

174
challenge = Challenge()
175
print(challenge.before_input)
176
try:
177
    while True:
178
        print(challenge(**literal_eval(input("input: "))))
179
except:
180
    exit(1)

Solution#

The challenge is a hash based signature scheme which supports infinite time signatures. As the name suggests, the target is to use literal_eval to craft malicious input.

The most suspicious function is sign, which signs many messages at once. Additionally, you may specify the indexes of the WOTS keys to sign. A straightforward idea is to somehow reuse the same key for multiple messages, hence the one-time signature is no longer secure.

Although the sign function does many checks to prevent this, the type hint of function parameters isn’t enforced. Hence, we can pass a dictionary with numerical keys. Since dict is also iterable, it won’t raise an error and the keys will be used as indexes. For example, {i: 0 for i in range(255)} will generate 255 signatures with the same key.

The rest is a simple WOTS key reuse attack.

1
from math import floor, ceil, log2
2
from Crypto.Util.number import bytes_to_long
3
import os
4
from hashlib import shake_128
5
from ast import literal_eval
6
from secrets import token_bytes
7
from pwn import *
8

9
def pack(num: int, length: int, base: int) -> list[int]:
10
    packed = []
11
    while num > 0:
12
        packed.append(num % base)
13
        num //= base
14
    if len(packed) < length:
15
        packed += [0] * (length - len(packed))
16
    return packed
17

18
def get_d(digest, m = 256, w = 21):
19
    l1 = ceil(m / log2(w))
20
    l2 = floor(log2(l1*(w-1)) / log2(w)) + 1
21
    l = l1 + l2
22
    d1 = pack(bytes_to_long(digest), l1, w)
23
    checksum = sum(w-1-i for i in d1)
24
    d2 = pack(checksum, l2, w)
25
    d = d1 + d2
26
    return d
27

28
io = process(["python3", "chall.py"])
29
io.recvuntil(b"public key:")
30
root = bytes.fromhex(io.recvline().strip().decode())
31
k = 255
32

33
def send(msg):
34
    io.recvuntil(b"input:")
35
    io.sendline(str(msg).encode())
36
    ret = io.recvline().decode()
37
    if "Traceback" in ret:
38
        io.interactive()
39
    return literal_eval(ret)
40

41
msgs = [os.urandom(32) for _ in range(k)]
42
disgests = [shake_128(b"\x00" + msg).digest(32) for msg in msgs]
43
ds = [get_d(digest) for digest in disgests]
44
sigs = send({
45
    "type": "sign",
46
    "num_sign": k,
47
    "inds": {i: 0 for i in range(k)},
48
    "messages": msgs,
49
})
50

51
target_digest = shake_128(b"\x00" + b"Give me the flag").digest(32)
52
target = get_d(target_digest)
53

54
wots_sign = []
55
for i in range(len(target)):
56
    find = False
57
    for dd, sig in zip(ds, sigs):
58
        if dd[i] == target[i]:
59
            wots_sign.append(sig[0][i])
60
            find = True
61
            break
62
    assert find
63

64
forged_sig = [wots_sign] + sigs[0][1:]
65
print(send({
66
    "type": "get_flag",
67
    "sig": [forged_sig],
68
}))

Alter Ego#

Description#

Even so, You alone should drown in blue and vanish.
Before being consumed by those sorrow-filled eyes, divide the world by zero, humming with a hoarse voice.
The finale’s sound is ringing out.
Author: kanon

1
from Crypto.Util.number import *
2

3
from random import randint
4
import os
5

6
from montgomery_isogenies.kummer_line import KummerLine
7
from montgomery_isogenies.kummer_isogeny import KummerLineIsogeny
8

9
FLAG = os.getenv('flag', "SEKAI{here_is_test_flag_hehe}").encode()
10
proof.arithmetic(False)
11

12
MI = 3
13
KU = 9
14
MIKU = 39
15

16
ells = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 587]
17
p = 4 * prod(ells) - 1
18

19
Fp = GF(p)
20
F = GF(p**2, modulus=x**2 + 1, names='i')
21
i = F.gen(0)
22
E0 = EllipticCurve(F, [1, 0])
23
E0.set_order((p + 1)**2)
24

25

26
def group_action(_C, priv, G):
27
    es = priv[:]
28
    while any(es):
29
        x = Fp.random_element()
30
        P = _C(x)
31
        A = _C.curve().a2()
32
        s = 1 if Fp(x ^ 3 + A * x ^ 2 + x).is_square() else -1
33

34
        S = [i for i, e in enumerate(es) if sign(e) == s and e != 0]
35
        k = prod([ells[i] for i in S])
36
        Q = int((p + 1) // k) * P
37
        for i in S:
38
            R = (k // ells[i]) * Q
39
            if R.is_zero():
40
                continue
41

42
            phi = KummerLineIsogeny(_C, R, ells[i])
43
            _C = phi.codomain()
44
            Q, G = phi(Q), phi(G)
45
            es[i] -= s
46
            k //= ells[i]
47

48
    return _C, G
49

50

51
def BEAM(base_alice_priv):
52
    alice_priv = base_alice_priv
53

54
    pub = 0
55

56
    for _ in range(MIKU):
57

58
        E = EllipticCurve(F, [0, pub, 0, 1, 0])
59
        omae_E = KummerLine(E)
60
        G = E.random_point()
61
        _G = omae_E(G)
62

63
        _final_E1, _final_G = group_action(omae_E, alice_priv, _G)
64
        _final_G = _final_G
65
        print(f"final_a2 = {_final_E1.curve().a2()}")
66
        print(f"{_final_G=}")
67

68
        omae_priv = list(map(int, input("your priv >").split(", ")))
69

70
        assert all([abs(pi) < 2 for pi in omae_priv])
71
        assert len(omae_priv) == len(ells)
72

73
        alice_priv = [ai + yi for ai, yi in zip(alice_priv, omae_priv)]
74
        print("updated")
75

76
        pub = _final_E1.curve().a2()
77
    print("FIN!")
78

79

80
if __name__ == "__main__":
81

82
    print("And now, it's time for the moment you've been waiting for!")
83

84
    alice_priv = [randint(MI + KU, MI * KU) for _ in ells]
85
    BEAM(alice_priv)
86

87
    alter_ego = list(map(int, input('ready?! here is the "alter ego" >').split(", ")))
88

89
    assert alice_priv != alter_ego
90
    assert len(alice_priv) == len(alter_ego)
91
    assert all([-MI * KU <= ai < 0 for ai in alter_ego])
92

93
    _E0 = KummerLine(E0)
94
    G = E0.random_point()
95
    _G = _E0(G)
96

97
    _alter_ego_E1, _ = group_action(_E0, alter_ego, _G)
98
    _alice_E1, __ = group_action(_E0, alice_priv, _G)
99

100
    if _alter_ego_E1.curve().a2() == _alice_E1.curve().a2():
101
        print("There you are... I've been waiting and waiting for you to come to me.")
102
        print(FLAG)
103
    else:
104
        print("YOU CANT FIND MY ALTER EGO....")
105
        exit()

Solution#

Every $G\in E(\mathbb{F}_{p^2})$ can be decomposed into $G = P + Q$ , where $P\in E(\mathbb{F}_p)$ and $Q$ lies on the twist of $E(\mathbb{F}_p)$ . The $l$ -isogeny in function group_action can reduce the order of either $P$ or $Q$ by a factor of $l$ depending on the sign.

For any odd prime $l\mid p+1$ , the order of $P$ can’t have factor $l$ if the sign in alice_priv is positive. This indicates the sign of alice_priv. Hence, we can keep sending $-1$ and observe the order of $P$ and $Q$ .

After retrieving alice_priv, the next step is to find a negative priv that walks to the same curve. The idea is the same as su_auth from SUCTF 2025. So simply [e-36 for e in alice_priv] passes the check.

1
from sage.all import *
2
from pwn import *
3
from tqdm import tqdm
4

5
MI = 3
6
KU = 9
7
MIKU = 39
8

9
ells = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 587]
10
p = 4 * prod(ells) - 1
11

12
Fp = GF(p)
13
F = GF(p**2, modulus=[1, 0, 1], names='i')
14
i = F.gen(0)
15

16
E0 = EllipticCurve(F, [0, 0, 0, 1, 0])
17

18
io = process(['sage', 'chall.sage'])
19

20
def group_action(E0, priv):
21
    E = E0
22
    es = priv[:]
23
    while any(es):
24
        x = Fp.random_element()
25
        P = E.lift_x(x)
26
        s = 1 if P[1] in Fp else -1
27
        S = [i for i, e in enumerate(es) if sign(e) == s and e != 0]
28
        k = prod([ells[i] for i in S])
29
        Q = ((p + 1) // k) * P
30

31
        for i in S:
32
            R = (k // ells[i]) * Q
33
            if R.is_zero():
34
                continue
35
            phi = E.isogeny(R)
36
            E = phi.codomain()
37
            Q = phi(Q)
38
            es[i] -= s
39
            k //= ells[i]
40
    return E
41

42
def read_curve():
43
    io.recvuntil(b'final_a2 = ')
44
    a2 = int(io.recvline().strip())
45
    E2 = EllipticCurve(F, [0, a2, 0, 1, 0])
46
    E2.set_order((p + 1)**2)
47
    return E2
48

49
def read_point(EC):
50
    io.recvuntil(b'_final_G=')
51
    point_str = io.recvline().strip().decode()
52
    x, z = eval(point_str.replace(':', ', '))
53
    x = F(x)
54
    z = F(z)
55
    G = EC.lift_x(x / z)
56
    return G
57

58
def get_orders(G):
59
    EC = G.curve()
60
    gen1 = gen2 = None
61
    while gen1 is None or gen2 is None:
62
        x0 = Fp.random_element()
63
        P = EC.lift_x(x0)
64
        is_gen = True
65
        for ell in ells:
66
            P1 = ((p + 1) // ell) * P
67
            if P1.is_zero():
68
                is_gen = False
69
                break
70
        if not is_gen:
71
            continue
72
        if P.y() in Fp:
73
            gen1 = P
74
        else:
75
            gen2 = P
76
    pairing1 = G.weil_pairing(gen1, p+1)
77
    pairing2 = G.weil_pairing(gen2, p+1)
78
    return pairing2.multiplicative_order(), pairing1.multiplicative_order()
79

80
orders = []
81
curves = []
82

83
for _ in tqdm(range(MIKU)):
84
    cur_E = read_curve()
85
    curves.append(cur_E)
86
    G = read_point(cur_E)
87
    orders.append(get_orders(G))
88
    io.sendline(", ".join(["-1"]*len(ells)).encode())
89
io.recvuntil(b"FIN!\n")
90

91
guess_priv = []
92

93
for ell in ells:
94
    left = MI + KU
95
    right = MI * KU
96
    for i, (o1, o2) in enumerate(orders):
97
        if o1 % ell == 0:
98
            right = min(right, i)
99
        if o2 % ell == 0:
100
            left = max(left, i)
101
    guess_priv.append((left, right-left))
102

103
print("guess_priv =", guess_priv)
104

105
E1 = curves[0]
106
G0 = E0.random_point()
107

108
left, offset = zip(*guess_priv)
109
left = list(left)
110
offset = list(offset)
111
print(offset)
112

113
def gen_all_possible_privs(offset):
114
    if len(offset) == 1:
115
        for i in range(offset[0]+1):
116
            yield [i]
117
    else:
118
        for os in gen_all_possible_privs(offset[1:]):
119
            for i in range(offset[0]+1):
120
                yield [i] + os
121

122
E1_base = group_action(E0, left)
123

124
def check():
125
    for os in gen_all_possible_privs(offset):
126
        E1_new = group_action(E1_base, os).montgomery_model()
127
        # print(E1_new.j_invariant(), E1.j_invariant(), E1_new, os)
128
        if E1_new.j_invariant() == E1.j_invariant():
129
            real_priv = [l + o for l, o in zip(left, os)]
130
            print("Found valid private key:", real_priv)
131
            return real_priv
132

133
real_priv = check()
134
real_priv2 = [x - 36 for x in real_priv]
135
io.sendline(", ".join(map(str, real_priv2)).encode())
136

137
io.recvuntil(b'There you are...')
138
io.recvline()
139
print(io.recvline().strip().decode())

APES#

Description#

The Advanced Permutation Encryption Standard (APES) offers 512-bit security for encrypting your permutations.
Author: Neobeo

1
import os
2
FLAG = os.getenv("FLAG", "SEKAI{TESTFLAG}")
3

4
def play():
5
    plainperm = bytes.fromhex(input('Plainperm: '))
6
    assert sorted(plainperm) == list(range(256)), "Invalid permutation"
7

8
    key = os.urandom(64)
9
    def f(i):
10
        for k in key[:-1]:
11
            i = plainperm[i ^ k]
12
        return i ^ key[-1]
13

14
    cipherperm = bytes(map(f, range(256)))
15
    print(f'Cipherperm: {cipherperm.hex()}')
16
    print('Do you know my key?')
17
    return bytes.fromhex(input()) == key
18

19
if __name__ == '__main__':
20
    # if you're planning to brute force anyway, let's prevent excessive connections
21
    while not play():
22
        print('Bad luck, try again.')
23
    print(f'APES TOGETHER STRONG! {FLAG}')

Solution#

This is a super tiny block cipher with block size 8 bits. The encyrption function consists of multiple rounds of substitution and round key addition. We can choose the substitution table and need to find an unique key.

Theoretically, if we choose a random permutation, we get about 1600 bits of information. But random permutation also makes it hard to find the key. So we need a more structured permutation and linear mapping seems to be a good choice.

Let’s say we use a linear mapping $f(x) = ax, x\in\mathbb{F}_{256}$ , where $a$ is a generator of the field. Since xor is the same as addition, after the encryption, we can get $enc(x)=a^{63}x + \sum_{i=0}^{63} a^{63-i}k_i$ . As we can see, the only information we get is $\sum_{i=0}^{63} a^{63-i}k_i$ , which isn’t enough to recover the key.

The solution is simple, we can add some error to the linear mapping. For a 3 cycle permutation $g=(0, 1, 255)$ ¹, only three numbers are changed, so $f\circ g=g'\circ f, f=ax+b$ and $g'$ is another 3 cycle permutation. Therefore,

f_1\circ g_1\circ f_2\circ\cdots\circ g_{63}\circ f_{64}=g_1'\circ g_2'\circ\cdots\circ g_{63}'\circ F

where $F=a^{63}x+b$ and $f_i$ are linear.

Since these 3-cycles can affect at most $192$ numbers, we can recover $F$ using the remaining $64$ numbers. The problem is then reduced to decomposing the permutation into 3-cycles. We can simplify it by choosing a special case where every 3-cycle only make the cycle “larger”. This means that each time we add a 3-cycle, the cycle won’t be split into smaller cycles. With this property, we can ensure that these cycles don’t contain the numbers that satisfy the linear mapping $F$ . Hence, we can filter all possible $k_i$ and enumerate to find the real key.

The average probability of success is about $1$ in $60$ keys.

1
from sage.all import *
2
from pwn import *
3
from tqdm import tqdm
4
from collections import Counter
5

6
io = process(['python3', 'chall.py'])
7

8
F = GF(2**8, 'a')
9
a = F.gen()
10

11
perm1 = []
12
for i in range(256):
13
    x = F.from_integer(i)
14
    y = a * x
15
    perm1.append(y.to_integer())
16
perm1[0], perm1[1], perm1[255] = perm1[1], perm1[255], perm1[0]
17

18
def fail():
19
    io.sendline(b'00')
20
    io.recvuntil(b'Bad luck, try again.')
21

22
def try_solve():
23
    io.sendlineafter(b'Plainperm: ', bytes(perm1).hex().encode())
24
    io.recvuntil(b'Cipherperm: ')
25
    cipherperm = bytes.fromhex(io.recvline().strip().decode())
26
    cipherperm_F = [F.from_integer(x) for x in cipherperm]
27

28
    cipherperm_F = [x / (a**63) for x in cipherperm_F]
29
    for b in range(257):
30
        assert b < 256, "This should not happen"
31
        b0 = F.from_integer(b)
32
        cipherperm_F2 = [(x+b0).to_integer()+1 for x in cipherperm_F]
33
        if len(Permutation(cipherperm_F2).fixed_points()) > 20:
34
            break
35

36
    perm2 = Permutation(cipherperm_F2)
37
    cycles = perm2.cycle_tuples()
38
    cycles = [cycle for cycle in cycles if len(cycle) > 1]
39
    u = sum([(len(cycle)-1)//2 for cycle in cycles])
40

41
    if u != 63 or max([len(cycle) for cycle in cycles]) > 51:
42
        fail()
43
        return
44

45
    cycles = [tuple(F.from_integer(x-1) for x in cycle) for cycle in cycles]
46
    print(([len(cycle) for cycle in cycles]), u)
47

48
    all_numbers = [F.from_integer(i) for i in range(256)]
49
    possible_k0 = [all_numbers[:] for _ in range(63)]
50

51
    def check(us):
52
        for cycle in cycles:
53
            if all(u in cycle for u in us):
54
                inds = [cycle.index(u) for u in us]
55
                inversions = 0
56
                if inds[0] > inds[1]: inversions += 1
57
                if inds[0] > inds[2]: inversions += 1
58
                if inds[1] > inds[2]: inversions += 1
59
                if inversions % 2 == 1:
60
                    return False
61
                return True
62
        return False
63

64
    for i in range(63):
65
        filtered = []
66
        a0 = a ** i
67
        ts = [F.from_integer(t)/a0 for t in [0, 1, 255]]
68

69
        for k0 in possible_k0[i]:
70
            us = [u + k0 for u in ts]
71
            if check(us):
72
                filtered.append(k0)
73
        possible_k0[i] = filtered
74

75
    def update():
76
        all_pos = sum([list(cycle) for cycle in cycles], [])
77
        c = {pos: [] for pos in all_pos}
78

79
        for i in range(63):
80
            a0 = a ** i
81
            ts = [F.from_integer(t)/a0 for t in [0, 1, 255]]
82
            for k0 in possible_k0[i]:
83
                us = [u + k0 for u in ts]
84
                for u in us:
85
                    c[u].append((i, k0))
86

87
        for pos in c:
88
            if len(c[pos]) == 1:
89
                i, k0 = c[pos][0]
90
                possible_k0[i] = [k0]
91

92
    for _ in range(16):
93
        update()
94

95
    if prod([len(x) for x in possible_k0]) > 2**14:
96
        fail()
97
        return
98

99
    print([len(x) for x in possible_k0], prod([len(x) for x in possible_k0]).bit_length())
100

101
    possible_maps = [[] for _ in range(63)]
102
    for i in range(63):
103
        a0 = a ** i
104
        ts = [F.from_integer(t)/a0 for t in [0, 1, 255]]
105
        for k0 in possible_k0[i]:
106
            us = [u + k0 for u in ts]
107
            us = [x.to_integer() + 1 for x in us]
108
            perm3 = Permutation([tuple(us)])
109
            possible_maps[i].append((k0, perm3))
110

111
    def search(cur_map, i):
112
        if i == 63:
113
            if cur_map == perm2:
114
                return [[]]
115
            else:
116
                return None
117

118
        all_results = []
119
        for k0, perm3 in possible_maps[i]:
120
            new_map = cur_map * perm3
121
            result = search(new_map, i + 1)
122
            if result is not None:
123
                for r in result:
124
                    all_results.append([k0] + r)
125

126
        if all_results:
127
            return all_results
128

129
    pathes = search(cur_map=Permutation(list(range(1, 257))), i=0)
130
    if pathes is None or len(pathes) == 0:
131
        fail()
132
        return
133

134
    print(len(pathes), pathes)
135
    path = pathes[0]
136

137
    real_ks = []
138
    a0 = 1
139
    c0 = 0
140
    for i in range(63):
141
        k0 = path[i]
142
        ts = [F.from_integer(t)/a0 for t in [0, 1, 255]]
143
        us = [u + k0 for u in ts]
144
        c1 = a0 * us[0]
145
        real_k = (c0 - c1)
146
        real_ks.append(real_k.to_integer())
147
        a0 *= a
148
        c0 += real_k
149
        c0 *= a
150
    real_ks.append((b0 * (a ** 63) + c0).to_integer())
151
    print(bytes(real_ks).hex())
152
    io.sendlineafter(b'Do you know my key?', bytes(real_ks).hex().encode())
153
    io.interactive()
154

155
for _ in tqdm(range(1000)):
156
    ret = try_solve()

law and order#

Description#

My friends were the FROST to implement sharing signatures for flag and ensured to always include me but somehow its still not working?
Author: deuterium

1
from py_ecc.secp256k1 import P, G as G_lib, N
2
from py_ecc.secp256k1.secp256k1 import multiply, add
3
import random
4
from secrets import randbelow
5
import os
6
from hashlib import sha256
7
import sys
8

9
CONTEXT = os.urandom(69)
10
NUM_PARTIES = 9
11
THRESHOLD = (2 * NUM_PARTIES) // 3 + 1
12
NUM_SIGNS = 100
13
FLAG = os.environ.get("FLAG", "FLAG{I_AM_A_NINCOMPOOP}")
14

15
# IO
16
def send(msg):
17
    print(msg, flush=True)
18

19

20
def handle_error(msg):
21
    send(msg)
22
    sys.exit(1)
23

24

25
def receive_line():
26
    try:
27
        return sys.stdin.readline().strip()
28
    except BaseException:
29
        handle_error("Connection closed by client. Exiting.")
30

31

32
def input_int(range=P):
33
    try:
34
        x = int(receive_line())
35
        assert 0 <= x <= range - 1
36
        return x
37
    except BaseException:
38
        handle_error("Invalid input integer")
39

40

41
def input_point():
42
    try:
43
        x = input_int()
44
        y = input_int()
45
        assert not (x == 0 and y == 0)
46
        return Point(x, y)
47
    except BaseException:
48
        handle_error("Invalid input Point")
49

50

51
# Helper class
52
class Point:
53
    """easy operator overloading"""
54

55
    def __init__(self, x, y):
56
        self.point = (x, y)
57

58
    def __add__(self, other):
59
        return Point(*add(self.point, other.point))
60

61
    def __mul__(self, scalar):
62
        return Point(*multiply(self.point, scalar))
63

64
    def __rmul__(self, scalar):
65
        return Point(*multiply(self.point, scalar))
66

67
    def __neg__(self):
68
        return Point(self.point[0], -self.point[1])
69

70
    def __eq__(self, other):
71
        return (self + (-other)).point[0] == 0
72

73
    def __repr__(self):
74
        return str(self.point)
75

76

77
G = Point(*G_lib)
78

79

80
def random_element(P):
81
    return randbelow(P - 1) + 1
82

83

84
def H(*args):
85
    return int.from_bytes(sha256(str(args).encode()).digest(), "big")
86

87

88
def sum_pts(points):
89
    res = 0 * G
90
    for point in points:
91
        res = res + point
92
    return res
93

94

95
def sample_poly(t):
96
    return [random_element(N) for _ in range(t)]
97

98

99
def gen_proof(secret, i):
100
    k = random_element(P)
101
    R = k * G
102
    mu = k + secret * H(CONTEXT, i, secret * G, R)
103
    return R, mu % N
104

105

106
def verify_proof(C, R, mu, i):
107
    c = H(CONTEXT, i, C, R)
108
    return R == mu * G + (-c * C)
109

110

111
def gen_poly_comms(coeffs):
112
    return [i * G for i in coeffs]
113

114

115
def eval_poly(coeffs, x):
116
    res = 0
117
    for coeff in coeffs[::-1]:
118
        res = (res * x + coeff) % N
119
    return res
120

121

122
def gen_shares(n, coeffs):
123
    return {i: eval_poly(coeffs, i) for i in range(1, n + 1)}
124

125

126
def poly_eval_comms(comms, i):
127
    return sum_pts([comms[k] * pow(i, k, N) for k in range(THRESHOLD)])
128

129

130
def check_shares(comms, shares, i):
131
    return G * shares[i] == poly_eval_comms(comms, i)
132

133

134
def gen_nonsense():
135
    d, e = random_element(N), random_element(N)
136
    D, E = d * G, e * G
137
    return (d, e), (D, E)
138

139

140
def lamb(i, S):
141
    num, den = 1, 1
142
    for j in S:
143
        if j == i:
144
            continue
145
        num *= j
146
        den *= (j - i)
147
    return (num * pow(den, -1, N)) % N
148

149

150
def main():
151
    """https://eprint.iacr.org/2020/852.pdf"""
152
    send("=" * 50)
153
    send("=== Law and Order! You should always include your friends to sign and you are mine <3 ===")
154
    send("=" * 50)
155
    send( f"We have {NUM_PARTIES - 1} parties here, and you will be party #{NUM_PARTIES}.")
156
    send(f"Idk why is our group signing not working")
157
    send("\n--- Round 1: Commitment ---")
158

159
    # Keygen
160

161
    send(f"context string {CONTEXT.hex()}")
162

163
    your_id = NUM_PARTIES
164

165
    all_coeffs = {}
166
    all_comms = {}
167
    for i in range(1, NUM_PARTIES):
168
        # 1.1
169
        coeffs = sample_poly(THRESHOLD)
170
        # 1.2
171
        zero_proof = gen_proof(coeffs[0], i)
172
        # 1.3
173
        comms = gen_poly_comms(coeffs)
174
        # 1.5
175
        if not verify_proof(comms[0], zero_proof[0], zero_proof[1], i):
176
            handle_error(f"[-] Party {i} secret PoK invalid")
177
        all_coeffs[i] = coeffs
178
        all_comms[i] = comms
179
        send(f"[+] Commitments from party {i}:")
180
        for k, C_ik in enumerate(comms):
181
            send(f"  C_{i},{k} = {C_ik}")
182

183
    send("\n[?] Now, provide the commitments (points) for your coefficients.")
184
    your_comms = [input_point() for _ in range(THRESHOLD)]
185
    send("\n[?] Finally, provide your proof-of-knowledge for your secret share (c_i,0).")
186
    send("[>] Send Point R:")
187
    your_zero_proof_R = input_point()
188
    send("[>] Send mu:")
189
    your_zero_proof_mu = input_int()
190
    your_zero_proof = (your_zero_proof_R, your_zero_proof_mu)
191

192
    if not verify_proof(your_comms[0], your_zero_proof[0], your_zero_proof[1], your_id):
193
        handle_error(f"[-] party {your_id} secret PoK invalid")
194
    all_comms[your_id] = your_comms
195
    send("[+] Your commitments and proof have been accepted.")
196
    send("\n--- Round 2: Share Distribution ---")
197

198
    send(f"[?] Please provide your shares for the other {NUM_PARTIES} parties.")
199
    # 2.1
200
    your_shares = {}
201
    for i in range(1, NUM_PARTIES + 1):
202
        send(f"[>] Send share for party {i}:")
203
        your_shares[i] = input_int(N)
204

205
    # 2.2
206
    for i in range(1, NUM_PARTIES + 1):
207
        if not check_shares(your_comms, your_shares, i):
208
            handle_error(f"[-] party {your_id} shares for party {i} invalid")
209
    send("[+] Your shares have been verified")
210

211
    all_shares = {}
212
    for l in range(1, NUM_PARTIES):
213
        shares_l = gen_shares(NUM_PARTIES, all_coeffs[l])
214
        for i in range(1, NUM_PARTIES + 1):
215
            if not check_shares(all_comms[l], shares_l, i):
216
                handle_error(f"[-] party {l} shares for party {i} invalid")
217
        all_shares[l] = shares_l
218
        send(f"[+] Share for you from party {l}: {shares_l[your_id]}")
219
    all_shares[your_id] = your_shares
220

221
    # 2.3
222
    signing_shares = {}
223
    for i in range(1, NUM_PARTIES + 1):
224
        signing_shares[i] = 0
225
        for j in range(1, NUM_PARTIES + 1):
226
            signing_shares[i] += all_shares[j][i]
227

228
    # 2.4
229
    group_public_key = sum_pts([all_comms[i][0] for i in range(1, NUM_PARTIES + 1)])
230
    send(f"\n[+] Group Public Key: {group_public_key}")
231

232
    send("[?] Provide your public verification share `Y_i`.")
233
    your_public_share = input_point()
234
    if your_public_share != sum_pts([poly_eval_comms(all_comms[j], your_id) for j in range(1, NUM_PARTIES + 1)]):
235
        handle_error(f"[-] party {your_id} public share invalid")
236

237
    public_shares = {i: v * G for i, v in signing_shares.items()}
238
    public_shares[your_id] = your_public_share
239
    send("[+] Public verification shares have been computed.")
240

241
    send(f"\n--- Phase 3: Presign and Sign ({NUM_SIGNS} rounds) ---")
242
    for _ in range(NUM_SIGNS):
243
        # presign
244
        send("[?] Provide your nonces (D_i, E_i) for this round.")
245
        your_D = input_point()
246
        your_E = input_point()
247
        your_nonsense = (your_D, your_E)
248

249
        nonsense_sec, nonsense = {}, {}
250
        for i in range(1, NUM_PARTIES + 1):
251
            # 1.a, 1.b & 1.c
252
            (d, e), (D, E) = gen_nonsense()
253
            nonsense_sec[i] = (d, e)
254
            nonsense[i] = (D, E)
255
        nonsense[your_id] = your_nonsense
256

257
        # Sign
258

259
        # S is set of alpha, alpha is in t to n right?
260
        S = {random.randint(THRESHOLD, NUM_PARTIES) for _ in range(NUM_PARTIES - THRESHOLD)}
261
        S.add(your_id)  # should always include you <3
262
        send(f"[+] Set of signers for this round: {S}")
263

264
        m = "GIVE ME THE FLAG PLEASE"
265
        combined_nonsense = {}
266

267
        group_nonsense = 0 * G
268
        nonsense = {i: nonsense[i] for i in S}
269
        # 2
270
        nonsense_ordered = sorted([(i, Di, Ei) for i, (Di, Ei) in nonsense.items()])
271
        # 4
272
        rhos = {i: H(i, m, nonsense_ordered) for i in S}
273
        for i, (D, E) in nonsense.items():
274
            send(f"[+] Party {i} nonces: D={D}, E={E}")
275
            D, E = nonsense[i]
276
            nonsense_i = D + rhos[i] * E
277
            group_nonsense = group_nonsense + nonsense_i
278
            combined_nonsense[i] = nonsense_i
279

280
        group_challenge = H(group_nonsense, group_public_key, m)
281
        send(f"[+] Group challenge `c`: {group_challenge}")
282
        send("[?] Provide your signature share `z_i`.")
283

284
        your_zi = input_int(N)
285

286
        # 7.b
287
        if your_zi * G != combined_nonsense[your_id] + \
288
                public_shares[your_id] * group_challenge * lamb(your_id, S):
289
            handle_error(f"[-] party {your_id} signature shares invalid")
290

291
        final_signing_shares = {your_id: your_zi}
292
        for i in S - {your_id}:
293
            si = signing_shares[i]
294
            di, ei = nonsense_sec[i]
295
            # 5
296
            zi = di + (ei * rhos[i]) + si * group_challenge * lamb(i, S)
297
            Ri, Yi = combined_nonsense[i], public_shares[i]
298
            if Yi != sum_pts([poly_eval_comms(all_comms[j], i) for j in range(1, NUM_PARTIES + 1)]):
299
                handle_error(f"[-] party {i} public share invalid")
300
            if zi * G != Ri + Yi * group_challenge * lamb(i, S):
301
                handle_error(f"[-] party {i} signature share invalid")
302
            final_signing_shares[i] = zi
303

304
        # 7.c
305
        z = sum(final_signing_shares.values()) % N
306

307
        if z * G == group_nonsense + group_public_key * group_challenge:
308
            send("[+] Signature verification successful")
309
            send(f"[+] Here is your flag: {FLAG}")
310
            sys.exit(0)
311
    handle_error("[-] We are out of signing ink")
312

313

314
if __name__ == "__main__":
315
    try:
316
        main()
317
    except Exception as e:
318
        handle_error("[-] An error occured: {e}")

Solution#

We have created many variants of this challenge. There’re 2 major modifications:

Replace point equality check with (self + (-other)).point == (0, 0). It’ll block points like (0, y).
No input of your_public_share, directly compute it from all_comms. But we need either NUM_PARTIES%3!=1 or NUM_PARTIES=15 to solve it.

Although we’ve decided to use the easiest version, the handout still contains the second modification and NUM_PARTIES is still 9. I’m very sorry for that.

The bug is both py_ecc and Point didn’t check if the point is on the curve. Hence we can send invalid points and try to pass all assertions.

Let’s first take a look at the point operations in py_ecc.

Jacobian coordinates#

1
def from_jacobian(p: "PlainPoint3D") -> "PlainPoint2D":
2
    """
3
    Convert a Jacobian point back to its corresponding 2D point representation.
4

5
    :param p: the point to convert
6
    :type p: PlainPoint3D
7

8
    :return: the 2D point representation
9
    :rtype: PlainPoint2D
10
    """
11
    z = inv(p[2], P)
12
    return cast("PlainPoint2D", ((p[0] * z**2) % P, (p[1] * z**3) % P))

py_ecc first converts the point to Jacobian coordinates and then do the calculation. The relation of Jacobian coordinates and 2D coordinates is $(x, y, z)\sim(\frac{x}{z^2}, \frac{y}{z^3})$ .

Double and add#

1
def jacobian_add(p: "PlainPoint3D", q: "PlainPoint3D") -> "PlainPoint3D":
2
    """
3
    Add two points in Jacobian coordinates and return the result.
4

5
    :param p: the first point to add
6
    :type p: PlainPoint3D
7
    :param q: the second point to add
8
    :type q: PlainPoint3D
9

10
    :return: the resulting Jacobian point
11
    :rtype: PlainPoint3D
12
    """
13
    if not p[1]:
14
        return q
15
    if not q[1]:
16
        return p
17
    U1 = (p[0] * q[2] ** 2) % P
18
    U2 = (q[0] * p[2] ** 2) % P
19
    S1 = (p[1] * q[2] ** 3) % P
20
    S2 = (q[1] * p[2] ** 3) % P
21
    if U1 == U2:
22
        if S1 != S2:
23
            return cast("PlainPoint3D", (0, 0, 1))
24
        return jacobian_double(p)
25
    H = U2 - U1
26
    R = S2 - S1
27
    H2 = (H * H) % P
28
    H3 = (H * H2) % P
29
    U1H2 = (U1 * H2) % P
30
    nx = (R**2 - H3 - 2 * U1H2) % P
31
    ny = (R * (U1H2 - nx) - S1 * H3) % P
32
    nz = (H * p[2] * q[2]) % P
33
    return cast("PlainPoint3D", (nx, ny, nz))

Addition doesn’t use A and B at all, so it is actually adding on the unique curve y^2 = x^3 + Ax + B determined by the input points.

1
def jacobian_double(p: "PlainPoint3D") -> "PlainPoint3D":
2
    """
3
    Double a point in Jacobian coordinates and return the result.
4

5
    :param p: the point to double
6
    :type p: PlainPoint3D
7

8
    :return: the resulting Jacobian point
9
    :rtype: PlainPoint3D
10
    """
11
    if not p[1]:
12
        return cast("PlainPoint3D", (0, 0, 0))
13
    ysq = (p[1] ** 2) % P
14
    S = (4 * p[0] * ysq) % P
15
    M = (3 * p[0] ** 2 + A * p[2] ** 4) % P
16
    nx = (M**2 - 2 * S) % P
17
    ny = (M * (S - nx) - 8 * ysq**2) % P
18
    nz = (2 * p[1] * p[2]) % P
19
    return cast("PlainPoint3D", (nx, ny, nz))

The doubling algorithm uses A=0 to compute. Similarly, it is doubling on the unique curve y^2 = x^3 + B determined by the input point.

Infinite point#

In py_ecc, the infinite point is encoded as (0, 0). This isn’t a problem if the point check is working correctly. As we can see, if the y-axis is zero, the point is considered infinite in double and add. It is very helpful because we can create infinite points more easily.

Also, if the x-axis is same in addition, the result is also infinite.

Low order points attack#

Even though we can create invalid points, it is still impossible to get the shared secret or control group_challenge. The only way to pass it is to generate an invalid group_public_key whose order is sufficiently low. Similarly, to pass 7.b, we want your_public_share to be a low order point. To achieve this, we must pass all the checks.

The only way to control group_public_key is sending bad your_comms[0]. But there’s a commitment check which is hard for points not on the curve. So we need your_comms[0] to be a low order point to generate the commitment at infinite point.

The next problem is passing check_shares(your_comms, your_shares, i) for all parties. It is the hardest part because now your_comms[0] is not on the curve. There’re many feasible constructions. The intended solution is to find the bug of (self + (-other)).point[0] == 0, which allows (0, y)==(0, 0). Also (0, y) is a low order point, so everything is fine. My idea is to use low order points and Fermat’s little theorem. Details are in the harder version.²

The last problem is your_public_share. Since it’s from input, the check in 2.4 is easily achievable. We can fix the x-axis to be the same as sum_pts([poly_eval_comms(all_comms[j], your_id) for j in range(1, NUM_PARTIES + 1)]) and use the y-axis to find a low order point.

1
from sage.all import *
2
from sage.rings.generic import ProductTree
3
from pwn import *
4
from hashlib import sha256
5
from ast import literal_eval
6
from tqdm import tqdm
7
from py_ecc.secp256k1 import P, G as G_lib, N
8
from py_ecc.secp256k1.secp256k1 import multiply, add
9

10
NUM_PARTIES = 9
11
THRESHOLD = 7
12
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
13
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
14

15
R = PolynomialRing(GF(p), ['x', 'y'])
16
xbar, ybar = R.gens()
17

18
def send_point(p):
19
    io.sendline(str(p.point[0]).encode())
20
    io.sendline(str(p.point[1]).encode())
21

22
def send_int(n):
23
    io.sendline(str(n).encode())
24

25
def jacobian_double(p):
26
    """
27
    Double a point in Jacobian coordinates and return the result.
28

29
    :param p: the point to double
30
    :type p: PlainPoint3D
31

32
    :return: the resulting Jacobian point
33
    :rtype: PlainPoint3D
34
    """
35
    # if not p[1]:
36
    #     return (0, 0, 0)
37
    ysq = (p[1] ** 2)
38
    S = (4 * p[0] * ysq)
39
    A = 0
40
    M = (3 * p[0] ** 2 + A * p[2] ** 4)
41
    nx = (M**2 - 2 * S)
42
    ny = (M * (S - nx) - 8 * ysq**2)
43
    nz = (2 * p[1] * p[2])
44
    return (nx, ny, nz)
45

46
def jacobian_add(p, q, return_H=False):
47
    """
48
    Add two points in Jacobian coordinates and return the result.
49

50
    :param p: the first point to add
51
    :type p: PlainPoint3D
52
    :param q: the second point to add
53
    :type q: PlainPoint3D
54

55
    :return: the resulting Jacobian point
56
    :rtype: PlainPoint3D
57
    """
58
    # if not p[1]:
59
    #     return q
60
    # if not q[1]:
61
    #     return p
62
    U1 = (p[0] * q[2] ** 2)
63
    U2 = (q[0] * p[2] ** 2)
64
    S1 = (p[1] * q[2] ** 3)
65
    S2 = (q[1] * p[2] ** 3)
66
    # if U1 == U2:
67
    #     if S1 != S2:
68
    #         return (0, 0, 1)
69
    #     return jacobian_double(p)
70
    H = U2 - U1
71
    R = S2 - S1
72
    H2 = (H * H)
73
    H3 = (H * H2)
74
    U1H2 = (U1 * H2)
75
    nx = (R**2 - H3 - 2 * U1H2)
76
    ny = (R * (U1H2 - nx) - S1 * H3)
77
    nz = (H * p[2] * q[2])
78
    if return_H:
79
        return (nx, ny, nz), H
80
    return (nx, ny, nz)
81

82
class Point:
83
    """easy operator overloading"""
84
    def __init__(self, x, y):
85
        self.point = (x, y)
86

87
    def __add__(self, other):
88
        return Point(*add(self.point, other.point))
89

90
    def __mul__(self, scalar):
91
        return Point(*multiply(self.point, scalar))
92

93
    def __rmul__(self, scalar):
94
        return Point(*multiply(self.point, scalar))
95

96
    def __neg__(self):
97
        return Point(self.point[0], -self.point[1])
98

99
    def __eq__(self, other):
100
        return (self + (-other)).point == (0, 0)
101

102
    def to_jacobian(self):
103
        return (self.point[0], self.point[1], 1)
104

105
    def __repr__(self):
106
        return str(self.point)
107

108
G = Point(*G_lib)
109

110
def H(*args):
111
    return int.from_bytes(sha256(str(args).encode()).digest(), "big")
112

113
def verify_proof(C, R, mu, i):
114
    c = H(CONTEXT, i, C, R)
115
    return R == mu * G + (-c * C)
116

117
def sum_pts(points):
118
    res = 0 * G
119
    for point in points:
120
        res = res + point
121
    return res
122

123
def poly_eval_comms(comms, i):
124
    return sum_pts([comms[k] * pow(i, k, N) for k in range(THRESHOLD)])
125

126
def check_shares(comms, shares, i):
127
    return G * shares[i] == poly_eval_comms(comms, i)
128

129
def start():
130
    global CONTEXT, io
131
    io = process(["python3", "chall.py"])
132
    io.recvuntil(b"context string")
133

134
    CONTEXT = bytes.fromhex(io.recvline().strip().decode())
135
    all_comms = {}
136

137
    for i in range(1, 9):
138
        io.recvuntil(b"[+] Commitments from party ")
139
        io.recvline()
140
        comm = []
141
        for j in range(THRESHOLD):
142
            c_j = literal_eval(io.recvline().strip().decode().split("=")[-1].strip())
143
            comm.append(Point(*c_j))
144
        all_comms[i] = comm
145

146
    pt0 = sum([all_comms[i][0] for i in range(1, NUM_PARTIES)], Point(0, 0))
147

148
    P0 = (xbar, ybar, 1)
149
    PA = jacobian_add(P0, pt0.to_jacobian())
150
    PB = jacobian_add(jacobian_double(P0), P0)
151

152
    poly1 = PA[1]
153
    poly2 = 4 * ybar**2 - 3 * xbar**3
154

155
    p3 = poly1.change_ring(ZZ).resultant(poly2.change_ring(ZZ), ybar.change_ring(ZZ)).change_ring(GF(p)).univariate_polynomial()
156

157
    def find():
158
        for x0 in p3.roots(multiplicities=False):
159
            if x0 == 0:
160
                continue
161
            p1 = PA[1](x=x0).univariate_polynomial()
162
            for y0 in p1.roots(multiplicities=False):
163
                if poly2(x=x0, y=y0) != 0:
164
                    continue
165
                your_comm0 = Point(int(x0), int(y0))
166
                if (pt0 + your_comm0).point[1] != 0:
167
                    continue
168
                return int(x0), int(y0)
169

170
    res = find()
171
    if res is None:
172
        io.close()
173
        return
174
    x0, y0 = res
175
    print(f"Found x0: {x0}, y0: {y0}")
176
    assert poly2(x=x0, y=y0)==0
177

178
    your_comm0 = Point(int(x0), int(y0))
179

180
    assert (pt0 + your_comm0).point[1] == 0, (pt0 + your_comm0)
181
    assert (3 * your_comm0).point == (0, 0), (3 * your_comm0)
182

183
    def find_mu():
184
        for mu in range(1, 10000):
185
            R0 = mu * G
186
            if verify_proof(your_comm0, R0, mu, NUM_PARTIES):
187
                print(f"Found mu: {mu}")
188
                return R0, mu
189

190
    your_zero_proof = find_mu()
191

192
    def find_7():
193
        Q7 = (xbar, ybar, 1)
194
        _, H7 = jacobian_add(Q7, jacobian_double(jacobian_add(Q7, jacobian_double(Q7))), return_H=True)
195
        T = jacobian_add(Q7, jacobian_double(Q7))
196
        H7 = H7//(ybar**8)
197
        Q0 = jacobian_add(your_comm0.to_jacobian(), Q7)
198

199
        while True:
200
            r = randint(1, p)
201
            R0 = r * G
202
            poly2 = R0.point[0] * Q0[2]**2 - Q0[0]
203
            poly1 = H7
204
            M = poly1.sylvester_matrix(poly2, ybar)
205
            R0 = PolynomialRing(GF(P), 'x')
206
            M = matrix(R0, M)
207
            p3 = M.determinant()
208
            for x0 in p3.roots(multiplicities=False):
209
                if x0 == 0:
210
                    continue
211
                p1 = poly2(x=x0).univariate_polynomial()
212
                for y0 in p1.roots(multiplicities=False):
213
                    if poly1(x=x0, y=y0) != 0:
214
                        continue
215
                    your_comm6 = Point(int(x0), int(y0))
216
                    if (your_comm0+your_comm6)==r*G:
217
                        return r, your_comm6
218

219
    def find_mid(your_comm6):
220
        while True:
221
            r7 = randint(1, p)
222
            r1 = randint(1, p)
223
            R7 = r7 * G
224
            R1 = r1 * G
225

226
            S0 = (R7.point[0], ybar, 1)
227
            S1 = jacobian_add(S0, your_comm6.to_jacobian())
228
            poly = S1[0] - R1.point[0] * S1[2]**2
229
            poly = poly.univariate_polynomial()
230
            for y0 in poly.roots(multiplicities=False):
231
                if y0 == 0:
232
                    continue
233
                mid = Point(R7.point[0], int(y0))
234
                if  R1 == (mid + your_comm6) and R7 == mid:
235
                    return r1, r7, mid
236

237
    def try_find_3(your_comm0, mid):
238
        R2 = PolynomialRing(GF(P), ['r0', 'r1'])
239
        r0, r1 = R2.gens()
240

241
        M2 = (12 * r0**2, 36 * r0**3, 1)
242
        M4 = (12 * r1**2, -36 * r1**3, 1)
243

244
        mid1 = jacobian_add(your_comm0.to_jacobian(), M2)
245
        mid2 = jacobian_add(mid.to_jacobian(), M4)
246

247
        rpoly1 = mid1[0] * mid2[2]**2 - mid2[0] * mid1[2]**2
248
        rpoly2 = mid1[1] * mid2[2]**3 - mid2[1] * mid1[2]**3
249

250
        M = rpoly1.sylvester_matrix(rpoly2, r1)
251
        R0 = PolynomialRing(GF(P), 'r0')
252
        rbar = R0.gen()
253
        M = matrix(R0, M)
254

255
        det = M.determinant()
256
        print(f"det degree: {det.degree()}")
257

258
        for r0_sol in det.roots(multiplicities=False):
259
            if r0_sol == 0:
260
                continue
261
            if rpoly1(r0=r0_sol) == 0:
262
                continue
263
            for r1_sol in rpoly1(r0=r0_sol).univariate_polynomial().roots(multiplicities=False):
264
                if rpoly2(r0=r0_sol, r1=r1_sol) != 0:
265
                    continue
266
                if r1_sol == 0:
267
                    continue
268
                your_comm2 = Point(int(12 * r0_sol**2), int(36 * r0_sol**3))
269
                your_comm4 = Point(int(12 * r1_sol**2), int(36 * r1_sol**3))
270
                aaa = your_comm0 + your_comm2 + your_comm4
271
                if aaa.point == mid.point:
272
                    print(f"Found your_comm2: {your_comm2}, your_comm4: {your_comm4}")
273
                    return your_comm2, your_comm4
274

275
    def try_find_2():
276
        while True:
277
            r3, your_comm6 = find_7()
278
            target_point = sum_pts([poly_eval_comms(all_comms[j], NUM_PARTIES) for j in range(1, NUM_PARTIES)])
279
            target_point = target_point + (your_comm0+your_comm6)
280
            poly = 4 * ybar**2 - 3 * target_point.point[0] ** 3
281
            y_fake = poly.univariate_polynomial().roots(multiplicities=False)
282
            if len(y_fake) > 0:
283
                break
284

285
        while True:
286
            r1, r7, mid = find_mid(your_comm6)
287
            try:
288
                res = try_find_3(your_comm0, mid)
289
                if res is not None:
290
                    your_comm2, your_comm4 = res
291
                    return r1, r3, r7, your_comm2, your_comm4, your_comm6
292
            except Exception as e:
293
                print(f"Error: {e}, retrying with new r1, r7")
294
                continue
295

296
    r1, r3, r7, your_comm2, your_comm4, your_comm6 = try_find_2()
297
    your_comms = [your_comm0, Point(1, 0), your_comm2, Point(1, 0), your_comm4, Point(1, 0), your_comm6]
298
    shares = [None, r1, r1, r3, r1, r1, r3, r7, r1, r3]
299

300
    for i in range(1, NUM_PARTIES + 1):
301
        print(i, check_shares(your_comms, shares, i))
302

303
    for your_comm in your_comms:
304
        send_point(your_comm)
305
    all_comms[NUM_PARTIES] = your_comms
306

307
    send_point(your_zero_proof[0])
308
    send_int(your_zero_proof[1])
309

310
    io.recvuntil(b"[+] Your commitments and proof have been accepted.")
311

312
    for i in range(1, NUM_PARTIES + 1):
313
        send_int(shares[i])
314

315
    my_shares = {}
316
    for i in range(1, NUM_PARTIES):
317
        io.recvuntil(b"[+] Share for you from party ")
318
        my_shares[i] = int(io.recvline().strip().decode().split(":")[-1].strip())
319
    my_shares[NUM_PARTIES] = r3
320

321
    target_point = sum_pts([poly_eval_comms(all_comms[j], NUM_PARTIES) for j in range(1, NUM_PARTIES + 1)])
322

323
    poly = 4 * ybar**2 - 3 * target_point.point[0] ** 3
324

325
    y_fake = poly.univariate_polynomial().roots(multiplicities=False)[0]
326
    P_fake = Point(target_point.point[0], y_fake)
327

328
    assert P_fake == target_point
329
    group_public_key = pt0 + your_comm0
330

331
    send_point(P_fake)
332

333
    io.recvuntil(b"[+] Public verification shares have been computed.")
334

335
    def gen_D_E():
336
        while True:
337
            r = randint(1, p)
338
            E = Point(12*r**2 % p, 36*r**3 % p)
339
            D = (1337, ybar, 1)
340
            nonce = jacobian_add(D, E.to_jacobian())
341
            poly = nonce[1]
342
            poly = poly.univariate_polynomial()
343
            for y0 in poly.roots(multiplicities=False):
344
                if y0 == 0:
345
                    continue
346
                D = Point(1337, int(y0))
347
                nonsense_ordered = [(NUM_PARTIES, D, E)]
348
                m = "GIVE ME THE FLAG PLEASE"
349
                rho = H(NUM_PARTIES, m, nonsense_ordered)
350
                if rho % 3 == 1:
351
                    group_nonsense = D + E
352
                    group_challenge = H(group_nonsense, group_public_key, m)
353
                    if group_challenge % 3 != 0:
354
                        continue
355
                    return D, E
356

357
    D, E = gen_D_E()
358
    send_point(D)
359
    send_point(E)
360

361
    io.recvuntil(b"[+] Set of signers for this round: ")
362
    signers = literal_eval(io.recvline().strip().decode())
363
    print(f"Signers: {signers}")
364
    if len(signers) > 1:
365
        io.close()
366
        return
367

368
    io.recvuntil(b"[+] Group challenge `c`: ")
369
    c = int(io.recvline().strip().decode())
370
    print(f"Challenge {c}, {c % 3}")
371
    send_int(0)
372

373
    io.interactive()
374

375
for _ in range(100):
376
    start()

Harder version#

Here’s the harder version of the challenge.

1
--- chall.py
2
+++ chall_clean5.py
3
@@ -7,8 +7,8 @@
4
 import sys
5

6
 CONTEXT = os.urandom(69)
7
-NUM_PARTIES = 9
8
-THRESHOLD = (2 * NUM_PARTIES) // 3 + 1
9
+NUM_PARTIES = 15
10
+THRESHOLD = 13
11
 NUM_SIGNS = 100
12
 FLAG = os.environ.get("FLAG", "FLAG{I_AM_A_NINCOMPOOP}")
13

14
@@ -68,7 +68,7 @@
15
         return Point(self.point[0], -self.point[1])
16

17
     def __eq__(self, other):
18
-        return (self + (-other)).point[0] == 0
19
+        return (self + (-other)).point == (0, 0)
20

21
     def __repr__(self):
22
         return str(self.point)
23
@@ -229,12 +229,8 @@
24
     group_public_key = sum_pts([all_comms[i][0] for i in range(1, NUM_PARTIES + 1)])
25
     send(f"\n[+] Group Public Key: {group_public_key}")
26

27
-    send("[?] Provide your public verification share `Y_i`.")
28
-    your_public_share = input_point()
29
-    if your_public_share != sum_pts([poly_eval_comms(all_comms[j], your_id) for j in range(1, NUM_PARTIES + 1)]):
30
-        handle_error(f"[-] party {your_id} public share invalid")
31
-
32
     public_shares = {i: v * G for i, v in signing_shares.items()}
33
+    your_public_share = sum_pts([poly_eval_comms(all_comms[j], your_id) for j in range(1, NUM_PARTIES + 1)])
34
     public_shares[your_id] = your_public_share
35
     send("[+] Public verification shares have been computed.")

The solution is similar to the easier one except the construction of your_comms.

For simplicity, denote $y_i$ as your_comm[i].

Let’s assume $y_2$ and $y_4$ are order $3$ points. Hence $y_0 + i^2y_2 + i^4y_4$ has two values. If $3\nmid i$ , it’ll be $y_0+y_2+y_4$ and if $3\mid i$ , it’ll be $y_0$ . It is intuitive that $y_0+y_2+y_4$ can go to almost any points. Similarly, we can set $y_6$ and $y_{12}$ to be order $7$ points. For $3\mid i$ , it’ll be $y_0+y_6+y_{12}$ , hence we can control the value of your_public_share. The final step is to make sure $y_0+y_2+y_4$ and $y_0+y_2+y_4+y_6+y_{12}$ can be verified. This is easy because $y_2$ and $y_4$ are still unused.

1
from sage.all import *
2
from sage.rings.generic import ProductTree
3
from pwn import *
4
from hashlib import sha256
5
from ast import literal_eval
6
from tqdm import tqdm
7
from py_ecc.secp256k1 import P, G as G_lib, N
8
from py_ecc.secp256k1.secp256k1 import multiply, add
9

10
NUM_PARTIES = 15
11
THRESHOLD = 13
12
p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
13
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
14

15
R = PolynomialRing(GF(p), ['x', 'y'])
16
xbar, ybar = R.gens()
17

18
def jacobian_double(p):
19
    """
20
    Double a point in Jacobian coordinates and return the result.
21

22
    :param p: the point to double
23
    :type p: PlainPoint3D
24

25
    :return: the resulting Jacobian point
26
    :rtype: PlainPoint3D
27
    """
28
    # if not p[1]:
29
    #     return (0, 0, 0)
30
    ysq = (p[1] ** 2)
31
    S = (4 * p[0] * ysq)
32
    A = 0
33
    M = (3 * p[0] ** 2 + A * p[2] ** 4)
34
    nx = (M**2 - 2 * S)
35
    ny = (M * (S - nx) - 8 * ysq**2)
36
    nz = (2 * p[1] * p[2])
37
    return (nx, ny, nz)
38

39
def send_point(p):
40
    io.sendline(str(p.point[0]).encode())
41
    io.sendline(str(p.point[1]).encode())
42

43
def send_int(n):
44
    io.sendline(str(n).encode())
45

46
def jacobian_add(p, q, return_H=False):
47
    """
48
    Add two points in Jacobian coordinates and return the result.
49

50
    :param p: the first point to add
51
    :type p: PlainPoint3D
52
    :param q: the second point to add
53
    :type q: PlainPoint3D
54

55
    :return: the resulting Jacobian point
56
    :rtype: PlainPoint3D
57
    """
58
    # if not p[1]:
59
    #     return q
60
    # if not q[1]:
61
    #     return p
62
    U1 = (p[0] * q[2] ** 2)
63
    U2 = (q[0] * p[2] ** 2)
64
    S1 = (p[1] * q[2] ** 3)
65
    S2 = (q[1] * p[2] ** 3)
66
    # if U1 == U2:
67
    #     if S1 != S2:
68
    #         return (0, 0, 1)
69
    #     return jacobian_double(p)
70
    H = U2 - U1
71
    R = S2 - S1
72
    H2 = (H * H)
73
    H3 = (H * H2)
74
    U1H2 = (U1 * H2)
75
    nx = (R**2 - H3 - 2 * U1H2)
76
    ny = (R * (U1H2 - nx) - S1 * H3)
77
    nz = (H * p[2] * q[2])
78
    if return_H:
79
        return (nx, ny, nz), H
80
    return (nx, ny, nz)
81

82
class Point:
83
    """easy operator overloading"""
84

85
    def __init__(self, x, y):
86
        self.point = (x, y)
87

88
    def __add__(self, other):
89
        return Point(*add(self.point, other.point))
90

91
    def __mul__(self, scalar):
92
        return Point(*multiply(self.point, scalar))
93

94
    def __rmul__(self, scalar):
95
        return Point(*multiply(self.point, scalar))
96

97
    def __neg__(self):
98
        return Point(self.point[0], -self.point[1])
99

100
    def __eq__(self, other):
101
        return (self + (-other)).point == (0, 0)
102

103
    def to_jacobian(self):
104
        return (self.point[0], self.point[1], 1)
105

106
    def __repr__(self):
107
        return str(self.point)
108

109
G = Point(*G_lib)
110

111
def H(*args):
112
    return int.from_bytes(sha256(str(args).encode()).digest(), "big")
113

114
def verify_proof(C, R, mu, i):
115
    c = H(CONTEXT, i, C, R)
116
    return R == mu * G + (-c * C)
117

118
def sum_pts(points):
119
    res = 0 * G
120
    for point in points:
121
        res = res + point
122
    return res
123

124
def poly_eval_comms(comms, i):
125
    return sum_pts([comms[k] * pow(i, k, N) for k in range(THRESHOLD)])
126

127
def check_shares(comms, shares, i):
128
    return G * shares[i] == poly_eval_comms(comms, i)
129

130
def gen_7_point():
131
    while True:
132
        E = EllipticCurve(GF(p), [0, randint(1, p-1)])
133
        order = E.order()
134
        if order % 7 == 0:
135
            break
136
    return E.torsion_basis(7)
137

138
def start():
139
    global CONTEXT, io
140
    io = process(["python3", "chall_clean5.py"])
141
    io.recvuntil(b"context string")
142

143
    CONTEXT = bytes.fromhex(io.recvline().strip().decode())
144

145
    all_comms = {}
146

147
    for i in range(1, NUM_PARTIES):
148
        io.recvuntil(b"[+] Commitments from party ")
149
        io.recvline()
150
        comm = []
151
        for j in range(THRESHOLD):
152
            c_j = literal_eval(io.recvline().strip().decode().split("=")[-1].strip())
153
            comm.append(Point(*c_j))
154
        all_comms[i] = comm
155

156
    pt0 = sum([all_comms[i][0] for i in range(1, NUM_PARTIES)], Point(0, 0))
157

158
    P0 = (xbar, ybar, 1)
159

160
    PA = jacobian_add(P0, pt0.to_jacobian())
161
    PB = jacobian_add(jacobian_double(P0), P0)
162

163
    RZ = PolynomialRing(ZZ, ['x', 'y'])
164

165
    poly1 = PA[1]
166
    poly2 = 4 * ybar**2 - 3 * xbar**3
167

168
    p3 = poly1.change_ring(ZZ).resultant(poly2.change_ring(ZZ), ybar.change_ring(ZZ)).change_ring(GF(p)).univariate_polynomial()
169

170
    def find():
171
        for x0 in p3.roots(multiplicities=False):
172
            if x0 == 0:
173
                continue
174
            p1 = PA[1](x=x0).univariate_polynomial()
175
            for y0 in p1.roots(multiplicities=False):
176
                if poly2(x=x0, y=y0) != 0:
177
                    continue
178
                your_comm0 = Point(int(x0), int(y0))
179
                if (pt0 + your_comm0).point[1] != 0:
180
                    continue
181
                return int(x0), int(y0)
182

183
    res = find()
184
    if res is None:
185
        io.close()
186
        return
187
    x0, y0 = res
188
    print(f"Found x0: {x0}, y0: {y0}")
189
    assert poly2(x=x0, y=y0)==0
190

191
    your_comm0 = Point(int(x0), int(y0))
192

193
    assert (pt0 + your_comm0).point[1] == 0, (pt0 + your_comm0)
194
    assert (3 * your_comm0).point == (0, 0), (3 * your_comm0)
195

196
    def find_mu():
197
        for mu in range(1, 10000):
198
            R0 = mu * G
199
            if verify_proof(your_comm0, R0, mu, NUM_PARTIES):
200
                print(f"Found mu: {mu}")
201
                return R0, mu
202

203
    your_zero_proof = find_mu()
204

205
    your_public_share_pt0 = sum_pts([poly_eval_comms(all_comms[j], NUM_PARTIES) for j in range(1, NUM_PARTIES)])
206

207
    def find_7(your_comm0):
208
        R2 = PolynomialRing(GF(P), ['r0', 'r1'])
209
        r0, r1 = R2.gens()
210

211
        A7_, B7_ = gen_7_point()
212

213
        A7 = (A7_.x() * r0 ** 2, A7_.y() * r0 ** 3, 1)
214
        B7 = (B7_.x() * r1 ** 2, B7_.y() * r1 ** 3, 1)
215

216
        C = jacobian_add(your_comm0.to_jacobian(), A7)
217
        C = jacobian_add(C, B7)
218

219
        while True:
220
            r3 = randint(1, p)
221
            R = r3 * G
222
            R_fake = (R.point[0], ybar, 1)
223
            fake_share = jacobian_add(your_public_share_pt0.to_jacobian(), R_fake)
224
            poly0 = 4 * fake_share[1] ** 2 - 3 * fake_share[0] ** 3
225
            y_fake = poly0.univariate_polynomial().roots(multiplicities=False)
226
            if len(y_fake) == 0:
227
                continue
228
            y_fake = y_fake[-1]
229
            R_fake = (int(R.point[0]), int(y_fake))
230

231
            poly1 = R_fake[0] * C[2] ** 2 - C[0]
232
            poly2 = R_fake[1] * C[2] ** 3 - C[1]
233

234
            M = poly1.sylvester_matrix(poly2, r1)
235
            R0 = PolynomialRing(GF(P), 'r0')
236
            M = matrix(R0, M)
237
            det = M.determinant()
238
            print(f"det degree: {det.degree()}")
239

240
            for r0_sol in det.roots(multiplicities=False):
241
                if r0_sol == 0:
242
                    continue
243
                if poly1(r0=r0_sol) == 0:
244
                    continue
245
                for r1_sol in poly1(r0=r0_sol).univariate_polynomial().roots(multiplicities=False):
246
                    if poly2(r0=r0_sol, r1=r1_sol) != 0:
247
                        continue
248
                    if r1_sol == 0:
249
                        continue
250
                    your_comm6 = Point(int(A7_.x() * r0_sol ** 2), int(A7_.y() * r0_sol ** 3))
251
                    your_comm12 = Point(int(B7_.x() * r1_sol ** 2), int(B7_.y() * r1_sol ** 3))
252
                    aaa = your_comm0 + your_comm6 + your_comm12
253
                    if aaa.point == R_fake:
254
                        return r3, your_comm6, your_comm12
255

256
    def find_mid(your_comm6, your_comm12):
257
        while True:
258
            r7 = randint(1, p)
259
            r1 = randint(1, p)
260
            R7 = r7 * G
261
            R1 = r1 * G
262

263
            S0 = (R7.point[0], ybar, 1)
264
            S1 = jacobian_add(S0, your_comm6.to_jacobian())
265
            S1 = jacobian_add(S1, your_comm12.to_jacobian())
266
            poly = S1[0] - R1.point[0] * S1[2]**2
267
            poly = poly.univariate_polynomial()
268
            for y0 in poly.roots(multiplicities=False):
269
                if y0 == 0:
270
                    continue
271
                mid = Point(R7.point[0], int(y0))
272
                if R1 == (mid + your_comm6 + your_comm12) and R7 == mid:
273
                    return r1, r7, mid
274

275
    def try_find_3(your_comm0, mid):
276
        R2 = PolynomialRing(GF(P), ['r0', 'r1'])
277
        r0, r1 = R2.gens()
278

279
        M2 = (12 * r0**2, 36 * r0**3, 1)
280
        M4 = (12 * r1**2, -36 * r1**3, 1)
281

282
        mid1 = jacobian_add(your_comm0.to_jacobian(), M2)
283
        mid2 = jacobian_add(mid.to_jacobian(), M4)
284

285
        rpoly1 = mid1[0] * mid2[2]**2 - mid2[0] * mid1[2]**2
286
        rpoly2 = mid1[1] * mid2[2]**3 - mid2[1] * mid1[2]**3
287

288
        M = rpoly1.sylvester_matrix(rpoly2, r1)
289
        R0 = PolynomialRing(GF(P), 'r0')
290
        rbar = R0.gen()
291
        M = matrix(R0, M)
292

293
        det = M.determinant()
294
        print(f"det degree: {det.degree()}")
295

296
        for r0_sol in det.roots(multiplicities=False):
297
            if r0_sol == 0:
298
                continue
299
            if rpoly1(r0=r0_sol) == 0:
300
                continue
301
            for r1_sol in rpoly1(r0=r0_sol).univariate_polynomial().roots(multiplicities=False):
302
                if rpoly2(r0=r0_sol, r1=r1_sol) != 0:
303
                    continue
304
                if r1_sol == 0:
305
                    continue
306
                your_comm2 = Point(int(12 * r0_sol**2), int(36 * r0_sol**3))
307
                your_comm4 = Point(int(12 * r1_sol**2), int(36 * r1_sol**3))
308
                aaa = your_comm0 + your_comm2 + your_comm4
309
                if aaa.point == mid.point:
310
                    print(f"Found your_comm2: {your_comm2}, your_comm4: {your_comm4}")
311
                    return your_comm2, your_comm4
312

313
    def try_find_2():
314
        r3, your_comm6, your_comm12 = find_7(your_comm0)
315
        print(f"Found r3: {r3}, your_comm6: {your_comm6}, your_comm12: {your_comm12}")
316

317
        while True:
318
            r1, r7, mid = find_mid(your_comm6, your_comm12)
319
            try:
320
                res = try_find_3(your_comm0, mid)
321
                if res is not None:
322
                    your_comm2, your_comm4 = res
323
                    return r1, r3, r7, your_comm2, your_comm4, your_comm6, your_comm12
324
            except Exception as e:
325
                print(f"Error: {e}, retrying with new r1, r7")
326
                continue
327

328
    r1, r3, r7, your_comm2, your_comm4, your_comm6, your_comm12 = try_find_2()
329
    your_comms = [your_comm0, Point(1, 0), your_comm2, Point(1, 0), your_comm4, Point(1, 0), your_comm6] + [Point(1, 0)] * 5 + [your_comm12]
330
    shares = [None, r1, r1, r3, r1, r1, r3, r7, r1, r3, r1, r1, r3, r1, r7, r3]
331

332
    for i in range(1, NUM_PARTIES + 1):
333
        print(i, check_shares(your_comms, shares, i))
334

335
    for your_comm in your_comms:
336
        send_point(your_comm)
337
    all_comms[NUM_PARTIES] = your_comms
338

339
    send_point(your_zero_proof[0])
340
    send_int(your_zero_proof[1])
341

342
    io.recvuntil(b"[+] Your commitments and proof have been accepted.")
343

344
    for i in range(1, NUM_PARTIES + 1):
345
        send_int(shares[i])
346

347
    my_shares = {}
348
    for i in range(1, NUM_PARTIES):
349
        io.recvuntil(b"[+] Share for you from party ")
350
        my_shares[i] = int(io.recvline().strip().decode().split(":")[-1].strip())
351
    my_shares[NUM_PARTIES] = r3
352

353
    group_public_key = pt0 + your_comm0
354
    io.recvuntil(b"[+] Public verification shares have been computed.")
355

356
    def gen_D_E():
357
        while True:
358
            r = randint(1, p)
359
            E = Point(12*r**2 % p, 36*r**3 % p)
360
            D = (1337, ybar, 1)
361
            nonce = jacobian_add(D, E.to_jacobian())
362
            poly = nonce[1]
363
            poly = poly.univariate_polynomial()
364
            for y0 in poly.roots(multiplicities=False):
365
                if y0 == 0:
366
                    continue
367
                D = Point(1337, int(y0))
368
                nonsense_ordered = [(NUM_PARTIES, D, E)]
369
                m = "GIVE ME THE FLAG PLEASE"
370
                rho = H(NUM_PARTIES, m, nonsense_ordered)
371
                if rho % 3 == 1:
372
                    group_nonsense = D + E
373
                    group_challenge = H(group_nonsense, group_public_key, m)
374
                    if group_challenge % 3 != 0:
375
                        continue
376
                    return D, E
377

378
    D, E = gen_D_E()
379

380
    send_point(D)
381
    send_point(E)
382

383
    io.recvuntil(b"[+] Set of signers for this round: ")
384
    signers = literal_eval(io.recvline().strip().decode())
385
    print(f"Signers: {signers}")
386
    if len(signers) > 1:
387
        io.close()
388
        return
389

390
    io.recvuntil(b"[+] Group challenge `c`: ")
391
    c = int(io.recvline().strip().decode())
392
    print(f"Challenge {c}, {c % 3}")
393
    send_int(0)
394

395
    io.interactive()
396

397
for _ in range(100):
398
    start()

The cycle $=(0, 1, 255)$ is carefully chosen to ensure $\{a^i, 255\times a^i, 254\times a^i| i=0,1\cdots,63\}$ in $\mathbb{F}_{256}$ are all distinct. ↩
I’ve tried to replace it with self.point == other.point, but it’ll be unsolvable because we still need your_public_share not on the standard curve. ↩

SSSS#

Description#

Solution#

I Dream of Genni#

Description#

Solution#

Literal Eval#

Description#

Solution#

Alter Ego#

Description#

Solution#

APES#

Description#

Solution#

law and order#

Description#

Solution#

Jacobian coordinates#

Double and add#

Infinite point#

Low order points attack#

Harder version#

Footnotes#