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.
#[rocket::async_trait] impl<'r> FromRequest<'r> for Admin { typeError = &'staticstr;
asyncfnfrom_request(req: &'r Request<'_>) -> Outcome<Self, Self::Error> { match req.cookies().get("auth") { Some(auth) => { let parts = auth.value().split(".").collect::<Vec<&str>>(); letmut 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()); letmut plaintext = base64::decode(parts[2]).unwrap();
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.
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 = '' for i inrange(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('.'))
# Ciphertext of nonce, but the last byte is wrong block_output = [x ^ y for x, y inzip(ct, pt)]
for c in tqdm(range(256)): iv = bytes([x ^ y for x, y inzip(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 inzip(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.
defcheck_point(P, curve): p, a, b = curve["p"], curve["a"], curve["b"] if P == O: returnTrue else: return (P.y**2 - (P.x**3 + a*P.x + b)) % p == 0and0 <= P.x < p and0 <= P.y < p
defpoint_inverse(P, curve): p = curve["p"] if P == O: return P return Point(P.x, -P.y % p)
defpoint_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
defdouble_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
defrecv_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")
defrecv_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.")
defrecv_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
defrecv_secret(resp): """ Can you solve the discrete log problem? Expected format: {"d" : "0x123456789"} """ returnint(resp["d"], 16)
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...")
defverify(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.
# 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 ================================== """
deflift_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)
deflift_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))
defpoint_to_integer(self, P): """ Extracts an integer from a point for commitment. """ if P.is_zero(): return0 x,y = P.xy()
s = Integer(x.polynomial().coefficients()[0]) t = Integer(y.polynomial().coefficients()[0]) n = s << (t & 1) return n
defpublic(self): return self.d*G1
defhash(self, i, msg): m = bytes.fromhex(msg) return hashlib.sha512(bytes([i]) + m).hexdigest()
defhash_to_point(self, msg): i = 0 m = int(msg, 16) Hm = self.hash(i, msg) whileTrue: try: Hmx = int(Hm, 16) % p return m*E2.lift_x(Hmx) except: i += 1 i %= 256 Hm = self.hash(i, Hm)
defpairing(self, A, B): return A.ate_pairing(B, r, 12, E12.trace_of_frobenius())
defsign(self, msg): P = self.hash_to_point(msg) return self.d*P
defrecv_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.")
defcommit_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"] assertall( 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.")
defverify_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"] ifall(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.")
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:
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
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.
##################### # leak info about d # #####################
cancer = getCancer() remainder = []
for q, qq, magic inzip(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:] iflen(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 inenumerate(magic): if num == res: print(f"Found remainder for {q}: {i}") remainder += [i] break
############################################## # merge result to get possible private key d # ##############################################
defcrt(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 # #############
classComplex: def__init__(self, a, b): # a + bi self.a = a self.b = b
def__mul__(self, other): assertisinstance(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
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