CSAW CTF Final 2021

 |  2021-11-14  | 

Intro

I played with the team Techsec, the MIT CTF team. Not surprisingly, I'm the only crypto player. I solved 4 out of 5 cryptos, the only unsolve requires certain reversing skill so I just skipped it. The first one is naive, so here's the other 3.

iBad

Challenge

I don't really know rust, so I attach part of the code and hopefully it makes things clear. There's a webpage which give us a cookie when we give the username as an input. The cookie is generated by encrypting username + '|regular|' + FLAG with AES-GCM with random nonce. There's also an oracle that decrypt our input and check if the plaintext contains '|admin|', it can either decrypt by AES-GCM mode or AES-CBC mode.

The oracle: 

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
#[rocket::async_trait]
impl<'r> FromRequest<'r> for Admin {
    type Error = &'static str;

    async fn from_request(req: &'r Request<'_>) -> Outcome<Self, Self::Error> {
        match req.cookies().get("auth") {
            Some(auth) => {
                let parts = auth.value().split(".").collect::<Vec<&str>>();
                let mut decrypted = match parts.len() {
                    2 => { // Legacy path
                        let iv = base64::decode(parts[0]).unwrap();
                        let ciphertext = base64::decode(parts[1]).unwrap();

                        let cipher = Aes128Cbc::new_from_slices(SECRET_KEY.as_ref(), &iv).unwrap();

                        cipher.decrypt_vec(ciphertext.as_ref()).unwrap()
                    },
                    3 => { // Upgraded encryption
                        let key = aes_gcm::Key::from_slice(SECRET_KEY);
                        let cipher = aes_gcm::Aes128Gcm::new(key);

                        let tag_raw = base64::decode(parts[0]).unwrap();
                        let tag = aes_gcm::Tag::from_slice(tag_raw.as_slice());
                        let nonce_raw = base64::decode(parts[1]).unwrap();
                        let nonce = aes_gcm::Nonce::from_slice(nonce_raw.as_slice());
                        let mut plaintext = base64::decode(parts[2]).unwrap();

                        cipher.decrypt_in_place_detached(nonce, b"", plaintext.as_mut_slice(), tag).unwrap();
                        plaintext
                    },
                    _ => return Outcome::Failure((rocket::http::Status::Unauthorized, "invalid cookie format"))
                };

                for _ in 0..decrypted.len() {
                    if decrypted.starts_with(b"|admin|") {
                        return Outcome::Success(Admin());
                    }
                    decrypted.rotate_left(1);
                }
                Outcome::Forward(())
            },
            None => Outcome::Failure((rocket::http::Status::Unauthorized, "No cookie"))
        }
    }
}

The cookie generator: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#[post("/login", data="<data>")]
fn login_submit(data: Form<LoginData<'_>>, cookies: &rocket::http::CookieJar<'_>) -> rocket::response::Redirect {

    let key = aes_gcm::Key::from_slice(SECRET_KEY);
    let cipher = aes_gcm::Aes128Gcm::new(key);
    
    let mut nonce_raw: [u8; 12] = [0; 12];
    let _ = getrandom(&mut nonce_raw).unwrap();
    let nonce = aes_gcm::Nonce::from_slice(&nonce_raw);

    let mut ciphertext = format!("{}|regular|{}", data.username, FLAG).bytes().collect::<Vec<u8>>();

    let tag = cipher.encrypt_in_place_detached(nonce, b"", ciphertext.as_mut_slice()).unwrap();

    cookies.add(rocket::http::Cookie::new("auth", format!("{}.{}.{}", base64::encode(tag), base64::encode(nonce), base64::encode(ciphertext))));
    Redirect::to(uri!(profile()))
}

Solution

It turned out that we only need the CTR mode ciphertext (from GCM mode), and the CBC decryption oracle to recover the flag. The idea is that CTR mode is like a one-time pad, with the keystream generated by the AES output of the nonce. With the cookie, we have the ciphertext and the plaintext (except the last 51 bytes of flag), so we can get the prefix of the keystream. Suppose we have the first 15 bytes of the keystream, we can recover the 16th byte by bruteforcing all possibilities and sending the speculated keystream to the CBC decryption, and see if it decrypts to the nonce.

Here's the more detailed explanation. If we want to recover the first character of the flag, we choose the username to be several 'A's, so that the plaintext will be 'A...AA|regular|FLAG', and the first byte of the flag should be the last byte of a block. With this username, we have the ciphertext for 'AA...AA|regular|*' (* is the unknown byte), so the keystream, which is the AES output of nonce + b'\x00\x00\x00\x02, is the xor value of the plaintext and the ciphertext. However, the last byte is unknown, so we iterate all possibilities and send the keystream to CBC oracle. Setting initial value to be nonce + b'\x00\x00\x00\x02' xor with b'AA...AA|admin|\x01, the decryption in CBC mode will be b'AA...AA|admin| if we get the correct ciphertext and directs us to the admin page. The last \x01 byte is due to PKCS#7 padding.

We can similarly do the same trick with other bytes. The following is the solve script.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import requests
import base64
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.Cipher import AES
import os
from tqdm import tqdm

FLAG_LEN = 51
url = 'http://crypto.chal.csaw.io:5015'

def isAdmin(cookies):
    s = requests.Session()
    s.cookies.set("auth", cookies)
    r = s.get(url + '/profile')
    if r.status_code != 200:
        return 'error'
    if 'Admin Profile' in r.text:
        return 'admin'
    else:
        return 'regular'    

def getCookie(username, debug = False):
    s = requests.Session()
    r = s.post(url + '/login', data = {"username": username})
    s.close()
    return s.cookies['auth']

def encodeCookie(cookie):
    return cookie.replace('=', '%3D').replace('/','%2F')

def decodeCookie(cookie):
    return cookie.replace('%3D', '=').replace('%2F', '/')

flag = ''
for i in range(FLAG_LEN): # recover the flag one byte by one byte
    username = 'A' * (16 - (len('|regular|') + i + 1) % 16)
    INPUT = f'{username}|regular|{flag}*' # * is the current unknown bytes
    blockIndex = len(INPUT) // 16 - 1
    _, nonce, ct = map(base64.b64decode, decodeCookie(getCookie(username)).split('.'))

    block = nonce + long_to_bytes(blockIndex + 2, 4)

    ct = ct[blockIndex * 16: blockIndex * 16 + 16]
    pt = INPUT[-16:].encode()

    # Ciphertext of nonce, but the last byte is wrong
    block_output = [x ^ y for x, y in zip(ct, pt)]

    for c in tqdm(range(256)):
        iv = bytes([x ^ y for x, y in zip(block, b'AAAAAAAA|admin|\x01')])
        block_output[-1] = c
        cookie = base64.b64encode(iv) + b'.' + base64.b64encode(bytes(block_output))
        cookie = encodeCookie(cookie.decode('ascii'))
        if isAdmin(cookie) == 'admin':
            pt = bytes([x ^ y for x, y in zip(block_output, ct)]).decode('ascii')
            flag += pt[-1]
            break

print(flag)

Interoperable

Challenge

The problem asks us to choose the curve (out of NIST-P256 and secp256k1), and a base point G. Then we have to solve a discrete log problem.

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
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
from math import ceil, sqrt, gcd, lcm
from gmpy2 import mpz
from collections import namedtuple
import random
import json
import os

# Remove
with open(os.path.join(os.path.abspath(os.path.dirname(__file__)), "flag.txt")) as f:
    FLAG = f.read().strip()

"""
=====================================
      Elliptic Curve Arithmetic
=====================================
"""

# Create a simple Point class to represent the affine points.
Point = namedtuple("Point", "x y")

# The point at infinity (origin for the group law).
O = 'Origin'

# Here's a choice of curves. They both offer 128-bit security
# so it doesnt matter to me!
curve_p256 = {
    "p": mpz(2**256 - 2**224 + 2**192 + 2**96 - 1),
    "a": mpz(-0x3),
    "b": mpz(0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b),
    "n": mpz(0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551)
}

curve_s256 = {
    "p": mpz(2**256 - 2**32 - 977),
    "a": mpz(0x0),
    "b": mpz(0x7),
    "n": mpz(0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141)
}


def check_point(P, curve):
    p, a, b = curve["p"], curve["a"], curve["b"]
    if P == O:
        return True
    else:
        return (P.y**2 - (P.x**3 + a*P.x + b)) % p == 0 and 0 <= P.x < p and 0 <= P.y < p


def point_inverse(P, curve):
    p = curve["p"]
    if P == O:
        return P
    return Point(P.x, -P.y % p)


def point_addition(P, Q, curve):
    p, a, b = curve["p"], curve["a"], curve["b"]
    if P == O:
        return Q
    elif Q == O:
        return P
    elif Q == point_inverse(P, curve):
        return O
    else:
        if P == Q:
            lam = (3*P.x**2 + a) * pow(2*P.y, -1, p)
            lam %= p
        else:
            lam = (Q.y - P.y) * pow((Q.x - P.x), -1, p)
            lam %= p
    Rx = (lam**2 - P.x - Q.x) % p
    Ry = (lam*(P.x - Rx) - P.y) % p
    R = Point(Rx, Ry)
    return R


def double_and_add(P, n, curve):
    Q = P
    R = O
    while n > 0:
        if n % 2 == 1:
            R = point_addition(R, Q, curve)
        Q = point_addition(Q, Q, curve)
        n = n // 2
    return R


"""
=====================================
           Util Functions
=====================================
"""


def recv_json():
    """
    Parse user input, expecting it as valid json
    """
    try:
        return json.loads(input("> "))
    except:
        exit("Please send data as json using the expected format")


def recv_curve(resp):
    """
    Pick to set the challenge over one of two prime 
    order curves:

    curve_p256: NIST-P256
    curve_s256: secp256k1

    Expected format: 
    {"curve" : "curve_name"}
    """
    chosen_curve = resp["curve"]
    if chosen_curve == "curve_s256":
        return curve_s256
    elif chosen_curve == "curve_p256":
        return curve_p256
    else:
        exit("Sorry, only our chosen prime order curves are allowed.")


def recv_generator(resp, curve):
    """
    Receive a point on the curve to use as a generator.
    Our curves are prime order, so any point will do!

    Expected format: 
    {"Gx" : "0x1337cafe", "Gy" : "0xc0ffee"}
    """
    Gx = mpz(int(resp["Gx"], 16))
    Gy = mpz(int(resp["Gy"], 16))
    G = Point(Gx, Gy)
    assert check_point(G, curve), "Whoops! Maybe you made a typo?"
    return G


def recv_secret(resp):
    """
    Can you solve the discrete log problem?

    Expected format: 
    {"d" : "0x123456789"}
    """
    return int(resp["d"], 16)


"""
=====================================
             Challenge
=====================================
"""


def public_key(G, curve):
    d = random.randint(1, curve["n"])
    return d, double_and_add(G, d, curve)


def verify(G, Q, d, curve):
    return double_and_add(G, d, curve) == Q


def main():
    curve = None
    G = None

    while True:
        resp = recv_json()
        if "curve" in resp:
            curve = recv_curve(resp)
        elif "Gx" in resp and "Gy" in resp:
            assert curve is not None
            G = recv_generator(resp, curve)
        else:
            break

    assert curve is not None
    assert G is not None

    print("Generating challenge...")
    d, Q = public_key(G, curve)
    print(f"Challenge: {Q}")

    print("What's my secret?")
    resp = recv_json()
    d_guess = recv_secret(resp)

    if verify(G, Q, d_guess, curve):
        print("What?!? I guess we better start moving to PQ-Crypto!")
        print(f"Flag: {FLAG}")
    else:
        exit("Don't be too tough on yourself, there are a lot of secrets to guess from...")


if __name__ == '__main__':
    main()

Solution

Choose curve: 

1
2
3
4
5
6
7
8
9
10
while True:
    resp = recv_json()
    if "curve" in resp:
        curve = recv_curve(resp)
    elif "Gx" in resp and "Gy" in resp:
        assert curve is not None
        G = recv_generator(resp, curve)
    else:
        break

Discrete log problem: 
1
2
def verify(G, Q, d, curve):
    return double_and_add(G, d, curve) == Q

We can change the curve after we choose the point, which is a sign of invalid curve attack.

As the first attempt, I choose a point from NIST-P256, and see if changing the curve to secp256k1 makes the discrete log easier. The invalid point on secp256k1 acts on the same \(p\) and \(a\), but the constant term \(b\) changes. If the result elliptic curve has a smooth order then we are done. However, it's not that easy to make it happen.

I start to try to find special point – if \(y = 0\), then the order is 2, but the curve has no such point, or the order is an even number, not a prime. Then it came to my mind that if \(a = 0\), then the point such that \(x = 0\) has order 3, and secp256k1 does satisfy \(a = 0\), so now the attack is really clear: choose curve NISTP256, choose point that \(x = 0\), change the curve to secp256k1. At the end, the order of the point is 3, and solving the discrete log is easy. It takes only a few minutes to code everything.

The script: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from pwn import *
import json

conn = remote('crypto.chal.csaw.io', 5017)

def send_json(j):
    conn.sendline(json.dumps(j))

Gx = 0
Gy = 69528327468847610065686496900697922508397251637412376320436699849860351814667

send_json({"curve":"curve_p256"})
send_json({"Gx": hex(Gx), "Gy": hex(Gy)})
send_json({"curve":"curve_s256"})
send_json({"OwO": "OAO"})

conn.recvuntil(b'y=mpz(')
y = int(conn.recvline().strip()[:-2])

p2 = 2**256 - 2**32 - 977

if y == Gy:
    send_json({"d": hex(1)})
elif y == -Gy % p2:
    send_json({"d": hex(2)})
else:
    send_json({"d": hex(3)})

conn.interactive()

aBoLiSh taBLeS

Challenge

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
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
import hashlib
import json
import string
import os

"""
==================================
  Global parameters for protocol
==================================
"""

with open(os.path.join(os.path.abspath(os.path.dirname(__file__)), "flag.txt")) as f:
    FLAG = f.read().strip()

# Safe prime
g_commit = 0x2
p_commit = 0x1b1177aadf10a3868443d5b4e6384d914f8c2eb51d1ebec4511d05ed22d8006a65cb4fc0442334e4ad5e2b11cd65cb82efec327d234f034321a818cfc9c71d48f

# BLS12-381 Parameters
# https://github.com/zkcrypto/bls12_381
p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
r = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
h1 = 0x396c8c005555e1568c00aaab0000aaab
h2 = 0x5d543a95414e7f1091d50792876a202cd91de4547085abaa68a205b2e5a7ddfa628f1cb4d9e82ef21537e293a6691ae1616ec6e786f0c70cf1c38e31c7238e5

# Define base fields
F1 = GF(p)
F2.<u> = GF(p^2, x, x^2 + 1)
F12.<w> = GF(p^12, x, x^12 - 2*x^6 + 2)

# Define the Elliptic Curves
E1 = EllipticCurve(F1, [0, 4])
E2 = EllipticCurve(F2, [0, 4*(1 + u)])
E12 = EllipticCurve(F12, [0, 4])

# Generator of order r in E1 / F1
G1x = 0x17f1d3a73197d7942695638c4fa9ac0fc3688c4f9774b905a14e3a3f171bac586c55e83ff97a1aeffb3af00adb22c6bb
G1y = 0x8b3f481e3aaa0f1a09e30ed741d8ae4fcf5e095d5d00af600db18cb2c04b3edd03cc744a2888ae40caa232946c5e7e1
G1 = E1(G1x, G1y)

# Generator of order r in E2 / F2
G2x0 = 0x24aa2b2f08f0a91260805272dc51051c6e47ad4fa403b02b4510b647ae3d1770bac0326a805bbefd48056c8c121bdb8
G2x1 = 0x13e02b6052719f607dacd3a088274f65596bd0d09920b61ab5da61bbdc7f5049334cf11213945d57e5ac7d055d042b7e
G2y0 = 0xce5d527727d6e118cc9cdc6da2e351aadfd9baa8cbdd3a76d429a695160d12c923ac9cc3baca289e193548608b82801
G2y1 = 0x606c4a02ea734cc32acd2b02bc28b99cb3e287e85a763af267492ab572e99ab3f370d275cec1da1aaa9075ff05f79be
G2 = E2(G2x0 + u*G2x1, G2y0 + u*G2y1)


"""
==================================
       BLS Signature Class
==================================
"""


class BLSSign():
    def __init__(self):
        self.d = randint(2, 2^70)
        self.public = self.public()

    def lift_E1_to_E12(self, P):
        """
        Lift point on E/F_q to E/F_{q^12} using the natural lift
        """
        assert P.curve() == E1, "Attempting to lift a point from the wrong curve."
        return E12(P)

    def lift_E2_to_E12(self, P):
        """
        Lift point on E/F_{q^2} to E/F_{q_12} through the sextic twist
        """
        assert P.curve() == E2, "Attempting to lift a point from the wrong curve."
        xs, ys = [c.polynomial().coefficients() for c in (h2*P).xy()]
        nx = F12(xs[0] - xs[1] + w ^ 6*xs[1])
        ny = F12(ys[0] - ys[1] + w ^ 6*ys[1])
        return E12(nx / (w ^ 2), ny / (w ^ 3))

    def point_to_integer(self, P):
        """
        Extracts an integer from a point for
        commitment.
        """
        if P.is_zero():
            return 0
        x,y = P.xy()

        s = Integer(x.polynomial().coefficients()[0])
        t = Integer(y.polynomial().coefficients()[0])
        n = s << (t & 1)
        return n

    def public(self):
        return self.d*G1

    def hash(self, i, msg):
        m = bytes.fromhex(msg)
        return hashlib.sha512(bytes([i]) + m).hexdigest()

    def hash_to_point(self, msg):
        i = 0
        m = int(msg, 16)
        Hm = self.hash(i, msg)
        while True:
            try:
                Hmx = int(Hm, 16) % p
                return m*E2.lift_x(Hmx)
            except:
                i += 1
                i %= 256
                Hm = self.hash(i, Hm)

    def pairing(self, A, B):
        return A.ate_pairing(B, r, 12, E12.trace_of_frobenius())

    def sign(self, msg):
        P = self.hash_to_point(msg)
        return self.d*P

    def verify(self, msg, sig):
        P = self.hash_to_point(msg)
        lhs = self.pairing(self.lift_E1_to_E12(self.public), self.lift_E2_to_E12(P))
        rhs = self.pairing(self.lift_E1_to_E12(G1), self.lift_E2_to_E12(sig))
        return lhs == rhs

    def commitment(self, msg):
        sig = self.sign(msg)
        x = self.point_to_integer(sig)
        return pow(g_commit, x, p_commit)


"""
==================================
  Util functions
==================================
"""


def recv_json():
    """
    Parse user input, expecting it as valid json
    """
    try:
        return json.loads(input("> "))
    except:
        exit("Please send data as json using the expected format.")


def commit_to_message(bls):
    """
    To be extra cautious, we will only give users our commitment
    to our signatures, we don't want people to be able to sign
    arbitary messages!
    """
    print("Please send your message to sign, encoded as a hex string.")
    resp = recv_json()
    if "message" in resp:
        msg = resp["message"]
        assert all(
            c in string.hexdigits for c in msg), "Invalid message. Please use hex encoding."
        commitment = bls.commitment(msg)
        print(f"Our commitment: {commitment}")
    else:
        print("You must send a message to see our commitment.")


def verify_signature(bls):
    """
    We'll give a flag to anyone who can supply a valid
    signature to the challenge message
    """
    challenge = b"https://cryptohack.org"
    print("Please send the valid signature for our challenge: {challenge}.")

    resp = recv_json()
    expected_coords = ["Sx0", "Sx1", "Sy0", "Sy1"]
    if all(s in resp for s in expected_coords):
        coords = [int(x, 16) for x in resp.values()]
        try:
            sig = E2(coords[0] + u*coords[1], coords[2] + u*coords[3])
        except:
            exit("You must send a point on the curve E2.")

        if bls.verify(challenge.hex(), sig):
            print(f"Flag: {FLAG}")
        else:
            exit("Fraudulent signature detected.")
    else:
        print("You must send the x and y coordinates of the signature.")


def main():
    bls = BLSSign()

    while True:
        print("Please send an option.")
        resp = recv_json()
        if "option" in resp:
            option = resp["option"]
            if option == "sign":
                commit_to_message(bls)
            elif option == "verify":
                verify_signature(bls)
            else:
                print("Invalid option")
        else:
            print("Invalid request.\nAvailable options: sign, verify.")


if __name__ == '__main__':
    main()

Solution

I'm not really familiar with the pairing, but I found 2 things that look sus: the private key d is small, and the hash_to_point function can lift point to something not actually on E2. If I can somehow control the hash_to_point function, then I can make a point of order 2, order 3, and so on. Solving the discrete log problem + Chinese Remainder Theorem can recover the private key easily. It turned out that I'm pretty much on the right track. The order of E2 (not the subgroup) is r * h2, and h2 has several small factors:

\[h_2 = 13^2 \cdot 23^2 \cdot 2713 \cdot 11953 \cdot 262069 \cdots\]

So if hash_to_point(msg) has order 2713, then we can get the value of \(d \bmod 2713\). How can we get such message? Notice that at the end of the hash function, they calculate m*E2.lift_x(Hmx), so it m = r * h2 // 2713, then we get a point of order 2713 with high probability. In the competition, I couldn't find a point of order 169, but only find a point with order 13. Same thing happened for 23, so at the end, solving CRT gives the remainder of \(d\) mod

\[13 * 23 * 2713 * 11953 * 262069 \approx 2^{51} \]

We are left with roughly \(2^{19}\) possibilities, and we can simply bruteforce it. After recover the secret key, we can forge a signature easily.

p.s. during the contest, my code failed several times before getting the flag (without changing anything), I don't know why.

I couldn't run sage and pwntools at the same time, so I run sage to print the list used for getting the reminader, save it to a file, and run python reading that file. The file is 37 MB big.

Sage script for determining the remainder:

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
######################################################## Copy-Pasted code
import hashlib
# Safe prime
g_commit = 0x2
p_commit = 0x1b1177aadf10a3868443d5b4e6384d914f8c2eb51d1ebec4511d05ed22d8006a65cb4fc0442334e4ad5e2b11cd65cb82efec327d234f034321a818cfc9c71d48f

# BLS12-381 Parameters
# https://github.com/zkcrypto/bls12_381
p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
r = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
h1 = 0x396c8c005555e1568c00aaab0000aaab
h2 = 0x5d543a95414e7f1091d50792876a202cd91de4547085abaa68a205b2e5a7ddfa628f1cb4d9e82ef21537e293a6691ae1616ec6e786f0c70cf1c38e31c7238e5

# Define base fields
F1 = GF(p)
F2.<u> = GF(p^2, x, x^2 + 1)
F12.<w> = GF(p^12, x, x^12 - 2*x^6 + 2)

# Define the Elliptic Curves
E1 = EllipticCurve(F1, [0, 4])
E2 = EllipticCurve(F2, [0, 4*(1 + u)])
E12 = EllipticCurve(F12, [0, 4])

def hash(i, msg):
    m = bytes.fromhex(msg)
    return hashlib.sha512(bytes([i]) + m).hexdigest()

def hash_to_point(msg):
    i = 0
    m = int(msg, 16)
    Hm = hash(i, msg)
    while True:
        try:
            Hmx = int(Hm, 16) % p
            return m*E2.lift_x(Hmx)
        except:
            i += 1
            i %= 256
            Hm = hash(i, Hm)

def point_to_integer(P):
    """
    Extracts an integer from a point for
    commitment.
    """
    if P.is_zero():
        return 0
    x,y = P.xy()

    s = Integer(x.polynomial().coefficients()[0])
    t = Integer(y.polynomial().coefficients()[0])
    n = s << (t & 1)
    return n

def commitment(x):
    return pow(g_commit, x, p_commit)

######################################################## Until here

order = h2 * r
factor = [169, 23 * 23, 2713, 11953, 262069]
ff = [13 ,23, 2713, 11953, 262069]

file = open('magic.txt', 'w')

for q, qq in zip(ff, factor):
    msg = hex(order // qq)[2:]
    if len(msg) % 2:
        msg = '0' + msg
    P = hash_to_point(msg)
    
    ls = []

    for i in range(q):
        Q = P * i
        ls += [hex(commitment(point_to_integer(Q)))]

    assert len(set(ls)) == len(ls)
    file.write(str(ls))

file.close()
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
178
179
180
181
from pwn import *
from tqdm import tqdm
import json

conn = remote('crypto.chal.csaw.io', 5018)

def getCancer():
    cancer = []
    file = open('magic.txt', 'r').read().replace('][', ']\n[').split('\n')
    for lsString in file:
        cancer += [eval(lsString)]

    return cancer

def send_json(j):
    conn.sendline(json.dumps(j))

g_commit = 0x2
p_commit = 0x1b1177aadf10a3868443d5b4e6384d914f8c2eb51d1ebec4511d05ed22d8006a65cb4fc0442334e4ad5e2b11cd65cb82efec327d234f034321a818cfc9c71d48f

p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
r = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
h1 = 0x396c8c005555e1568c00aaab0000aaab
h2 = 0x5d543a95414e7f1091d50792876a202cd91de4547085abaa68a205b2e5a7ddfa628f1cb4d9e82ef21537e293a6691ae1616ec6e786f0c70cf1c38e31c7238e5

factor = [169, 23 * 23, 2713, 11953, 262069]
ff = [13 ,23, 2713, 11953, 262069]
order = h2 * r

#####################
# leak info about d #
#####################

cancer = getCancer()
remainder = []

for q, qq, magic in zip(ff, factor, cancer):
    magic = [int(x, 16) for x in magic]
    send_json({"option": "sign"})
    conn.recvuntil(b'Please send your message to sign, encoded as a hex string.')
    msg = hex(order // qq)[2:]
    if len(msg) % 2 == 1:
        msg = '0' + msg
    send_json({"message": msg})

    conn.recvuntil(b'Our commitment: ')
    res = int(conn.recvline())
    print(q, res)
    for i, num in enumerate(magic):
        if num == res:
            print(f"Found remainder for {q}: {i}")
            remainder += [i]
            break

##############################################
# merge result to get possible private key d #
##############################################

def crt(ls: list) -> tuple:
    rem = 0
    mod = 1
    for q, r in ls:
        gcd = math.gcd(q, mod)
        if rem % gcd != r % gcd:
            return (-1, -1)
        rem += mod * ((r - rem) // gcd) * pow(mod // gcd, -1, q // gcd)
        mod = mod * q // gcd
        rem %= mod
    return (mod, rem)

MOD, _d = crt(zip(ff, remainder))
print(MOD, _d)

#############
# recover d #
#############

class Complex:
    def __init__(self, a, b):
        # a + bi
        self.a = a
        self.b = b

    def __add__(self, other):
        return Complex((self.a + other.a) % p, (self.b + other.b) % p)

    def __sub__(self, other):
        return Complex((self.a - other.a) % p, (self.b - other.b) % p)

    def __mul__(self, other):
        return Complex((self.a * other.a - self.b * other.b) % p,
                       (self.a * other.b + self.b * other.a) % p)

    def __eq__(self, other):
        return self.a == other.a and self.b == other.b

    def inv(self):
        iD = pow(self.a ** 2 + self.b ** 2, -1, p)
        return Complex(self.a * iD % p, -self.b * iD % p)

    def copy(self):
        return Complex(self.a, self.b)

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def toInt(self):
        a = self.x.a
        b = self.y.a
        return a << (b & 1)

    def __add__(self, other):
        if self.x == other.x:
            ld = Complex(3, 0) * self.x * self.x * Complex(2, 0).inv() * self.y.inv()
        else:
            ld = (self.y - other.y) * (self.x - other.x).inv()

        X = ld * ld - self.x - other.x
        Y = ld * (self.x - X) - self.y
        return Point(X, Y)

    def __mul__(self, other):
        assert isinstance(other, int)
        res = "O"
        base = Point(self.x.copy(), self.y.copy())
        while other:
            if other & 1:
                if res == "O":
                    res = base
                else:
                    res = res + base

            other >>= 1
            base = base + base
        return res

    def copy(self):
        return Point(self.x.copy(), self.y.copy())

msg = '1234'
G = Point(Complex(567187428662826536704554285744676765709023544078539176084186083325611611492203318998820105838752816922533510370900, 60052718657805885678787110624726048385207245407469335866892895204538864185656276944674285324741886152304381844132),
          Complex(700066217685000020766867958173455641165357526414324063897671833856058304658031527688201191640826209508168186734214, 445117887577014261707773299476067871930878669778756969958994951630910975535681646923346398743998984509699944220097))

# for the challenge
P = Point(Complex(687828580253418521894420198297981230713369955223000071927026438385848317085957422882499556266787416987577543108839, 3437849906304030911235272424131970890612194883775766747220678972212370864091554329430600230930083640667800574212878),
          Complex(1246346886386546987103714777226589478759768606505562002158286835891943575613915073704166759835452417743520860031360, 93187093546689440062949751687693403958101916426958958600514714210089900938755059872564179426916900362007032903797))

send_json({"option": "sign"})
conn.recvuntil(b'Please send your message to sign, encoded as a hex string.')
send_json({"message": msg})
conn.recvuntil(b'Our commitment: ')
res = int(conn.recvline())

cur_point = G * _d
step = G * MOD
privkey = -1

for d in tqdm(range(_d, 2 ** 70, MOD)):
    expected = pow(g_commit, cur_point.toInt(), p_commit)
    if expected == res:
        print(f'Found private key d = {d}')
        privkey = d
        break


    cur_point = cur_point + step

MAGIC = P * privkey

Sx0 = MAGIC.x.a
Sx1 = MAGIC.x.b
Sy0 = MAGIC.y.a
Sy1 = MAGIC.y.b

send_json({"option": "verify"})
challenge = b"https://cryptohack.org"
conn.recvuntil(b"Please send the valid signature for our challenge: {challenge}.")
send_json({"Sx0": hex(Sx0), "Sx1": hex(Sx1), "Sy0": hex(Sy0), "Sy1": hex(Sy1)})
conn.interactive()
tags:  #writeup
Expand all Back to top Go to bottom