Skip to content

Instantly share code, notes, and snippets.

@theoremoon
Created Jul 19, 2021
Embed
What would you like to do?
the solution script of tiramisu from Google CTF 2021
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# Copyright 2020 Google LLC
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
# https://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
from pwnlib.tubes import remote
from ptrlib import crt
import sys
import challenge_pb2
import struct
import json
from concurrent.futures import ThreadPoolExecutor, as_completed
from fastecdsa import curve
from fastecdsa.point import Point
from cryptography.hazmat.primitives import hashes, hmac
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.primitives.asymmetric import ec
from cryptography.hazmat.backends import default_backend
CHANNEL_CIPHER_KDF_INFO = b"Channel Cipher v1.0"
CHANNEL_MAC_KDF_INFO = b"Channel MAC v1.0"
IV = b'\x00\x11\x22\x33\x44\x55\x66\x77\x88\x99\xaa\xbb\xcc\xdd\xee\xff'
class AuthCipher(object):
def __init__(self, secret, cipher_info, mac_info):
self.cipher_key = self.derive_key(secret, cipher_info)
self.mac_key = self.derive_key(secret, mac_info)
def derive_key(self, secret, info):
hkdf = HKDF(
algorithm=hashes.SHA256(),
length=16,
salt=None,
info=info,
backend=default_backend(),
)
return hkdf.derive(secret)
def encrypt(self, iv, plaintext):
cipher = Cipher(algorithms.AES(self.cipher_key), modes.CTR(iv), backend=default_backend())
encryptor = cipher.encryptor()
ct = encryptor.update(plaintext) + encryptor.finalize()
h = hmac.HMAC(self.mac_key, hashes.SHA256(), backend=default_backend())
h.update(iv)
h.update(ct)
mac = h.finalize()
out = challenge_pb2.Ciphertext()
out.iv = iv
out.data = ct
out.mac = mac
return out
def handle_pow(tube):
raise NotImplemented()
def read_message(tube, typ):
n = struct.unpack('<L', tube.recvnb(4))[0]
buf = tube.recvnb(n)
msg = typ()
msg.ParseFromString(buf)
return msg
def write_message(tube, msg):
buf = msg.SerializeToString()
tube.send(struct.pack('<L', len(buf)))
tube.send(buf)
def curve2proto(c):
return challenge_pb2.EcdhKey.CurveID.SECP256R1
def key2proto(key):
assert(isinstance(key, ec.EllipticCurvePublicKey))
out = challenge_pb2.EcdhKey()
out.curve = curve2proto(key.curve)
x, y = key.public_numbers().x, key.public_numbers().y
out.public.x = x.to_bytes((x.bit_length() + 7) // 8, 'big')
out.public.y = y.to_bytes((y.bit_length() + 7) // 8, 'big')
return out
def proto2key(key):
assert(isinstance(key, challenge_pb2.EcdhKey))
assert(key.curve == challenge_pb2.EcdhKey.CurveID.SECP224R1)
curve = ec.SECP224R1()
x = int.from_bytes(key.public.x, 'big')
y = int.from_bytes(key.public.y, 'big')
public = ec.EllipticCurvePublicNumbers(x, y, curve)
return ec.EllipticCurvePublicKey.from_encoded_point(curve, public.encode_point())
def run_session(x, y, b, guess_d, mod):
tube = remote.remote('tiramisu.2021.ctfcompetition.com', 1337)
# tube = pwnlib.tubes.remote.remote('127.0.0.1', port)
# print(tube.recvuntil('== proof-of-work: '))
if tube.recvline().startswith(b'enabled'):
handle_pow()
server_hello = read_message(tube, challenge_pb2.ServerHello)
server_key = proto2key(server_hello.key)
# print(server_hello)
# private_key = ec.generate_private_key(ec.SECP224R1())
out = challenge_pb2.EcdhKey()
out.curve = challenge_pb2.EcdhKey.CurveID.SECP256R1
out.public.x = x.to_bytes((x.bit_length() + 7) // 8, 'big')
out.public.y = y.to_bytes((y.bit_length() + 7) // 8, 'big')
client_hello = challenge_pb2.ClientHello()
client_hello.key.CopyFrom(out)
# print(client_hello)
write_message(tube, client_hello)
c = curve.P224
c.b = b
p = c.p
try:
guessed_shared_x = (guess_d * Point(x % p, y % p, curve=curve.P224)).x
except ValueError:
return False
shared_key = guessed_shared_x.to_bytes(224 // 8, "big")
# shared_key = private_key.exchange(ec.ECDH(), server_key)
# print(shared_key)
channel = AuthCipher(shared_key, CHANNEL_CIPHER_KDF_INFO, CHANNEL_MAC_KDF_INFO)
msg = challenge_pb2.SessionMessage()
msg.encrypted_data.CopyFrom(channel.encrypt(IV, b'hello'))
write_message(tube, msg)
# print('msg:', msg)
reply = read_message(tube, challenge_pb2.SessionMessage)
# print("d: {}, mod: {}".format(guess_d, mod))
# print('reply:', repr(reply))
# import code
# code.interact(local=locals())
tube.close()
if len(repr(reply)):
return True
return False
def try_guess(x, y, b, mod):
for guess_d in range(mod):
if run_session(x, y, b, guess_d, mod):
return (guess_d, mod)
return None
def main():
with open("values.json") as f:
values = json.load(f)
sorted(values, key=lambda x: x[3])
start = int(sys.argv[1]) if len(sys.argv) > 1 else 0
pairs = []
# for x, y, b, mod in values[start:]:
# try_guess(x, y, b, mod)
# input("[pause]")
with ThreadPoolExecutor() as ex:
futures = []
for x, y, b, mod in values[start:]:
futures.append(ex.submit(try_guess, x, y, b, mod))
for f in as_completed(futures):
pair = f.result()
if pair is None:
continue
print("{}/{}".format(len(pairs) + 1, len(values)), pair)
pairs.append(pair)
print(pairs)
print(crt(pairs))
main()
from fastecdsa.curve import P224
from fastecdsa.point import Point
from ptrlib import crt
from tqdm import tqdm
from Crypto.Util.number import inverse
from cryptography.hazmat.primitives import hashes, hmac
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.primitives.kdf.hkdf import HKDF
from cryptography.hazmat.backends import default_backend
from itertools import product
CHANNEL_CIPHER_KDF_INFO = b"Channel Cipher v1.0"
CHANNEL_MAC_KDF_INFO = b"Channel MAC v1.0"
flagCipherKdfInfo = b"Flag Cipher v1.0"
flagMacKdfInfo = b"Flag MAC v1.0"
flagFixedIV = bytes([0x73, 0x40, 0x76, 0xd5, 0x67, 0xe0, 0x9, 0x2a, 0xbc, 0xe1, 0x9, 0x15, 0x82, 0x55, 0x43, 0x7d])
d = 70660979691982122950200127958675461805766058089618993620860247487201
IV = b'\x00\x11\x22\x33\x44\x55\x66\x77\x88\x99\xaa\xbb\xcc\xdd\xee\xff'
class AuthCipher(object):
def __init__(self, secret, cipher_info, mac_info):
self.cipher_key = self.derive_key(secret, cipher_info)
self.mac_key = self.derive_key(secret, mac_info)
def derive_key(self, secret, info):
hkdf = HKDF(
algorithm=hashes.SHA256(),
length=16,
salt=None,
info=info,
backend=default_backend(),
)
return hkdf.derive(secret)
def encrypt(self, iv, plaintext):
cipher = Cipher(algorithms.AES(self.cipher_key), modes.CTR(iv), backend=default_backend())
encryptor = cipher.encryptor()
ct = encryptor.update(plaintext) + encryptor.finalize()
h = hmac.HMAC(self.mac_key, hashes.SHA256(), backend=default_backend())
h.update(iv)
h.update(ct)
mac = h.finalize()
return (iv, ct, mac)
def decrypt(self, iv, ciphertext):
cipher = Cipher(algorithms.AES(self.cipher_key), modes.CTR(iv), backend=default_backend())
decryptor = cipher.decryptor()
pt = decryptor.update(ciphertext) + decryptor.finalize()
return pt
# cipher = AuthCipher(b"hello", flagCipherKdfInfo, flagMacKdfInfo)
# iv, ct, mac = cipher.encrypt(flagFixedIV, b"hogehoge")
# print(cipher.decrypt(iv, ct))
P = Point(16172896427079531402065391174021745391759293127844103141392333432900, 3771244459121791372570158792354692313003593392921088306467285612598, curve=P224)
G = Point(P224.gx, P224.gy, curve=P224)
pairs = [(60, 1181), (177, 1811), (327, 6571), (455, 2399), (550, 1607), (476, 1061), (123, 3797), (1481, 6871), (991, 3389), (564, 1907), (1612, 6343), (502, 5431), (497, 1283), (319, 3109), (2161, 4931), (262, 1361), (121, 2969), (878, 4513), (1470, 6599), (1735, 4289)]
data = b">}\"B\352\"WgA\234*\014p\326b\\O6\374\250\217K\343\334U\374\252~\267\026\325\212J\3178M\354{q\231\201\310\351yyj`3_\224^\313\204P\200\323\233="
for pat in tqdm(product([0, 1], repeat=len(pairs))):
pairs2 = pairs[:]
for i in range(len(pat)):
if pat[i] == 1:
pairs2[i] = (-pairs2[i][0] % pairs2[i][1], pairs2[i][1])
d, _ = crt(pairs2)
# print(d)
# P_ = d*G
# if P_.x == P.x and P_.y == P.y:
# print(d)
try:
key = d.to_bytes(224 // 8, "big")
cipher = AuthCipher(key, flagCipherKdfInfo, flagMacKdfInfo)
m = cipher.decrypt(flagFixedIV, data)
if b"CTF" in m:
print(m)
except OverflowError:
pass
from itertools import combinations
# parameters of secp224r1
secp224r1_p = 0xffffffffffffffffffffffffffffffff000000000000000000000001
K = GF(secp224r1_p)
a = K(0xfffffffffffffffffffffffffffffffefffffffffffffffffffffffe)
used_mod = set()
modulus = 1
values = []
secp256r1_p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
secp256r1_K = GF(secp256r1_p)
secp256r1_a = secp256r1_K(0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc)
secp256r1_b = secp256r1_K(0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b)
secp256r1_E = EllipticCurve(secp256r1_K, (secp256r1_a, secp256r1_b))
secp256r1_G = secp256r1_E(0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)
secp256r1_E.set_order(0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551 * 0x1)
while modulus < secp224r1_p:
b = randint(0, secp224r1_p-1)
EC = EllipticCurve(GF(secp224r1_p), [a, b])
P = EC.random_point()
try:
alarm(10)
order = int(P.order())
factors = factor(order, limit=20000)
cancel_alarm()
except AlarmInterrupt:
continue
for f, _ in factors:
if f in used_mod:
continue
if not 1000 < f < 10000:
continue
used_mod.add(f)
Q = (order // f) * P
qx, qy = Q.xy()
qx, qy = int(qx), int(qy)
if qy == 0:
continue
px, py = secp256r1_E.random_point().xy()
px, py = int(px), int(py)
x = CRT_list([px, qx], [secp256r1_p, secp224r1_p])
y = CRT_list([py, qy], [secp256r1_p, secp224r1_p])
modulus *= f
values.append((int(x),int(y), int(b), int(f)))
print(f, len(values), modulus)
import json
with open("values.json", "w") as f:
json.dump(values, f)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment