Need to patch the python binding in https://github.com/Chia-Network/bls-signatures
Last active
April 30, 2023 06:07
-
-
Save maple3142/2efcfe8b5126faba12fb9ead40d13aab to your computer and use it in GitHub Desktop.
ångstromCTF 2023 - tau as a service
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| diff --git a/python-bindings/pythonbindings.cpp b/python-bindings/pythonbindings.cpp | |
| index 63f3d29..e5dcf46 100644 | |
| --- a/python-bindings/pythonbindings.cpp | |
| +++ b/python-bindings/pythonbindings.cpp | |
| @@ -444,6 +444,26 @@ PYBIND11_MODULE(blspy, m) | |
| return self * (*(bn_t *)&other); | |
| }, | |
| py::is_operator()) | |
| + .def( | |
| + "scalar_mul", | |
| + [](G1Element &self, py::int_ pyint) { | |
| + char buffer[40]; | |
| + if (_PyLong_AsByteArray( | |
| + (PyLongObject *)pyint.ptr(), | |
| + (unsigned char*)buffer, | |
| + 40, | |
| + 0, | |
| + 0) < 0) { | |
| + throw std::invalid_argument("Failed to cast int to buffer 128"); | |
| + } | |
| + py::gil_scoped_release release; | |
| + bn_t bn; | |
| + bn_new(bn); | |
| + bn_read_bin(bn, (uint8_t*) buffer, 40); | |
| + auto ret = self * bn; | |
| + bn_free(bn); | |
| + return ret; | |
| + }) | |
| .def( | |
| "__rmul__", | |
| [](G1Element &self, bn_t other) { |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from sage.all import * | |
| from pwn import process, remote | |
| from math import prod | |
| import json | |
| n = 0x73EDA753299D7D483339D80809A1D80553BDA402FFFE5BFEFFFFFFFF00000001 | |
| groups = [ | |
| 2**32, | |
| 3, | |
| 11, | |
| 19, | |
| 10177, | |
| 125527, | |
| 859267, | |
| 906349**2, | |
| 2508409, | |
| 2529403, | |
| 52437899, | |
| 254760293, | |
| ] | |
| remain = 254760293 | |
| assert prod(groups) * remain == n - 1 | |
| F = GF(n) | |
| g = F.multiplicative_generator() | |
| # io = process(["python", "taas.py"]) | |
| io = remote("challs.actf.co", 32500) | |
| data = {} | |
| for grp in groups: | |
| cf = (n-1)//grp | |
| sub_g = g ** ((n-1)//grp) | |
| M = ceil(sqrt(grp)) | |
| io.sendlineafter(b"power: ", str(cf).encode()) | |
| T = io.recvlineS().strip() | |
| print(grp, T) | |
| data[grp] = T | |
| with open("data.json", "w") as f: | |
| json.dump(data, f) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from sage.all import * | |
| import json | |
| from blspy import PrivateKey as Scalar, G1Element | |
| from tqdm import tqdm | |
| from Crypto.Util.number import long_to_bytes | |
| # I couldn't find a way to implement pohlig-hellman-like p-adic shifting to handle p^e case efficiently | |
| # So I just pick some reasonably sized subgroup and brute force the rest | |
| n = 0x73EDA753299D7D483339D80809A1D80553BDA402FFFE5BFEFFFFFFFF00000001 | |
| groups = [ | |
| 2**32, | |
| 3, | |
| 11, | |
| 19, | |
| 10177, | |
| 125527, | |
| 859267, | |
| 906349**2, | |
| 2508409, | |
| 2529403, | |
| 52437899, | |
| 254760293, | |
| ] | |
| remain = 254760293 | |
| assert prod(groups) * remain == n - 1 | |
| F = GF(n) | |
| g = F.multiplicative_generator() | |
| with open("data.json", "r") as f: | |
| data = json.load(f) | |
| """ | |
| Local only start | |
| """ | |
| with open("flag.txt", "rb") as f: | |
| tau = int.from_bytes(f.read().strip(), "big") | |
| assert tau < n | |
| target_x = F(tau).log(g) | |
| """ | |
| Local only end | |
| """ | |
| def g1_fast_scalar_mul(scalar): | |
| return bytes(Scalar.from_bytes(int(scalar).to_bytes(32, "big")).get_g1())#.hex() | |
| def fast_scalar_mul(scalar, point): | |
| return bytes(point.scalar_mul(int(scalar)))#.hex() | |
| def solve(grp, T): | |
| cf = (n - 1) // grp | |
| sub_g = g ** ((n - 1) // grp) | |
| M = ceil(sqrt(grp)) | |
| # T = oracle(cf) = tau^cf G1 = g^(x*tau) G1 | |
| # sub_g^x G1 = T | |
| # sub_g^(u+vM) G1 = T | |
| # sub_g^u G1 = sub_g^(-vM) T | |
| tbl = {} | |
| for u in tqdm(range(M), desc="lhs"): | |
| tbl[g1_fast_scalar_mul(sub_g**u)] = u | |
| sgm = sub_g**-M | |
| TP = G1Element.from_bytes(bytes.fromhex(T)) | |
| for v in tqdm(range(M), desc="rhs"): | |
| u = tbl.get(fast_scalar_mul(sgm**v, TP), None) | |
| if u is not None: | |
| print("found", u, v, u + v * M, target_x % grp) | |
| return u + v * M | |
| break | |
| data = sorted([(int(grp), T) for grp, T in data.items()]) | |
| xx = [] | |
| yy = [] | |
| for grp, T in data: | |
| grp = int(grp) | |
| print(f"Solving for {grp = }, {grp.bit_length() = }") | |
| xx.append(solve(grp, T)) | |
| yy.append(grp) | |
| L = reduce(lcm, yy) | |
| x_mod_L = crt(xx, yy) | |
| print(x_mod_L, target_x % L) | |
| for i in tqdm(range(remain)): | |
| msg = long_to_bytes(int(g ** x_mod_L)) | |
| if b'actf' in msg: | |
| print(i, msg) | |
| x_mod_L += L | |
| # actf{w3_g0t_the_p0wer_tod0_th4t} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment