Tags: crypto
Rating:
# TeamItaly CTF 2022
## Elliptic Pizza (2 solves)
All italians have a secret key to order a special pizza at Sorbillo. It's impossible to fool them, you can't even read their conversations...
## Solution
### Passing the zero knowledge proof
The goal of the challenge is to pass the zero knowledge proof to get the flag from Sorbillo. The only possible ways to pass it are to discover the `italian_private_key` or to guess the coin tosses and send an appropriate value of `A`:
1. If `coin == 0` we can compute a random `r` and send `A = r*italian_G` and responde to the challenge with `r`.
2. If `coin == 1` we can compute a random `r` and send `A = -italian_pub_key + r*italian_G`. Since Sorbillo will check if `m*italian_G == A + italian_pub_key`, we can just respond with `r` and pass the check.
From the source code we see that `coin = random.getrandbits(1)`, but, since `random` uses the Mersenne Twister, knowing enough random bits we can predict the outputs and pass the verification.
The only source of randomness is from the conversations we can intercept, but these are encrypted with AES and the only way to decrypt them is breaking the key exchange.
### Breaking SIDH (another time)
The key for encrypting the conversations is derived through a variant of SIDH: SIDH with masked torsion point images. The paper where this idea is proposed is https://eprint.iacr.org/2022/1054. This doesn't allow the Castryck-Decru attack. But, computing the weil pairing of the masked torsion points we have:
$$e(b\cdot PB, b\cdot QB) = e(b\cdot \phi(P2), b\cdot \phi(Q2)) = e(P2, Q2)^{(b^2\cdot deg(\phi))}.$$
Hence, letting B be the order of P2 and Q2, by computing the discrete logarithm of $e(b\cdot \phi(PB), b\cdot \phi(QB))$ with base $e(P2, Q2)$ we can derive:
$$b^2\cdot deg(\phi) \mod(B) => b^2 \mod(B).$$
In this case we know that $B = 2^a$, thus we have only 4 square roots modulo (B) and, by bruteforcing all of them and trying the Castryck-Decru attack, we can recover the secret key and derive the encryption key used for AES. (In the paper the variant proposed uses torsion points with an order that has a large number of prime factors: this way one has an exponential number import square roots modulo $B$ and this attack becomes infeasible.)
Once we have the shared key we can start decrypting the conversations and getting enough bits from `random.getrandbits` and recover the Mersenne Twister seed. At this point we can either proceed by predicting the challenges as said before or by recovering the `italian_private_key` by intercepting some other conversations and predicting `r` (suggest you to try also this way to discover what's the key).
### Exploit
```python
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from pwn import process, remote
from rcrack import Untwister
import os
import warnings
# https://github.com/jack4818/Castryck-Decru-SageMath
# Thanks to all the people who contributed to this <3
# For the story of the implementation: https://research.nccgroup.com/2022/08/08/implementing-the-castryck-decru-sidh-key-recovery-attack-in-sagemath/
load("castryck_decru_shortcut.sage")
debug = True
def generate_distortion_map(E):
return E.isogeny(E.lift_x(ZZ(1)), codomain=E)
def compute_final_curve(E, priv_key, P, Q):
K = P + priv_key*Q
phi = E.isogeny(K, algorithm="factored")
E_final = phi.codomain()
return E_final.j_invariant()
# Setup SIDH params
lA,a, lB,b = 2,91, 3,57
p = lA^a * lB^b - 1
Fp2. = GF(p^2, modulus=x^2+1)
E_start = EllipticCurve(Fp2, [0,6,0,1,0])
two_i = generate_distortion_map(E_start)
P2 = E_start([689824709835763661212917891210192229166873119806353925*i + 2478485702646772354085217778801988934296596878299338050, 942903695767137584026537717052710977828250723819628138*i + 364625566770303975901492217768553886851432032784755076])
Q2 = E_start([2742917099100796602246115112758864407275043210045673210*i + 1224220368752701250142143989282248366644465532537779451, 3027039163506222584359297393447359222232947335466083600*i + 3169601705630822879781127309238868216961138055829555931])
P3 = E_start([3490059421151589241282844776547134156509060455350829321*i + 1794875097282666540523000574016315517012678449510183952, 3164937069244528012501785994511807136863378511336753997*i + 1615640198356510736828007505990397689903302760897759569])
Q3 = E_start([1359082117671312119351641025674270894687770763828316567*i + 1701631453787849568492693572465367443829807713991899911, 1743784037307975250157545016470187260457358261256646798*i + 2069327206845474638589006802971309729221166400917212890])
HOST = os.environ.get("HOST", "elliptic-pizza.challs.teamitaly.eu")
PORT = int(os.environ.get("PORT", 15012))
chall = remote(HOST, PORT)
def curve_from_str(curve_str: str):
split_str = curve_str.split(" + ")
a2 = eval(split_str[1].split('*x')[0])
a4 = eval(split_str[2].split('*x')[0])
a6 = eval(split_str[3].split()[0])
if debug:
print("a2 =", split_str[1].split('*x')[0])
print("a4 =", split_str[2].split('*x')[0])
print("a6 =", split_str[3].split()[0])
E = EllipticCurve(Fp2, [0, a2, 0, a4, a6])
return E
def point_from_str(point_str: str, E):
split_str = point_str.split('(')[1].split(')')[0].split(" : ")
x = eval(split_str[0])
y = eval(split_str[1])
return E([x, y])
def attack(EA, PA, QA, EB, PB, QB):
x = PB.weil_pairing(QB, 2**a)
base = P2.weil_pairing(Q2, 2**a)
sol = log(x, base)
assert base**sol == x
sol = Zmod(2**a)(3**b)^-1*sol
possible_bs = sol.nth_root(2,all=True)
possible_bs = [possible_bs[0], possible_bs[2]]
for hope in possible_bs:
origin_PB = int(Zmod(2**a)(hope)^-1)*PB
origin_QB = int(Zmod(2**a)(hope)^-1)*QB
try:
priv_B = CastryckDecruAttack(E_start, P2, Q2, EB, origin_PB, origin_QB, two_i, num_cores=1)
j = compute_final_curve(EA, priv_B, PA, QA)
shared = int(j.polynomial().coefficients()[0]).to_bytes(int(p).bit_length()//8 + 1, "big")
key = sha256(shared).digest()
print(f"{key.hex() = }")
return priv_B, hope, key
except:
print("Nope")
# This is to split the numbers in the right format for the Untwister
def split_in_words(random_number, num_of_words):
words = []
for _ in range(num_of_words):
words.append(bin(random_number & 0xffffffff)[2:].zfill(32))
random_number >>= 32
return words
def encrypt_message(plaintext, key):
iv = os.urandom(16)
cipher = AES.new(key, AES.MODE_CBC, iv=iv)
ciphertext = cipher.encrypt(pad(plaintext, AES.block_size))
return iv.hex() + ciphertext.hex()
def decrypt_message(ciphertext, key):
iv = ciphertext[:16]
ciphertext = ciphertext[16:]
cipher = AES.new(key, AES.MODE_CBC, iv=iv)
plaintext = unpad(cipher.decrypt(ciphertext), AES.block_size)
return plaintext.decode()
def decrypt_conversation(key):
words = []
chall.sendlineafter(b"> ", b'2')
chall.recvline()
for _ in range(29):
for _ in range(3):
chall.recvline()
ciphertext = bytes.fromhex(chall.recvline().decode().split()[-1])
plain = decrypt_message(ciphertext, key)
ciphertext = bytes.fromhex(chall.recvline().decode().split()[-1])
if plain == "Send me r: ":
r = int(decrypt_message(ciphertext, key))
words.extend(split_in_words(r, 8))
else:
for _ in range(8):
words.append('?'*32)
chall.recvline()
words.append('?'*32)
chall.recvline()
return words
def get_words(words, key):
while len([w for w in words if '?' not in w]) < 1400:
words.extend(decrypt_conversation(key))
print(f"[+] Known words: {len([w for w in words if '?' not in w])}")
return words
def get_rand(words, key):
words = get_words(words, key)
cracker = Untwister()
for w in words:
cracker.submit(w)
rand = cracker.get_random()
return rand
def elem_to_list(n):
# I know, probably there is something better, but it works
try:
int(n)
return [int(n), 0]
except:
# For numbers of the form 3*i this doesn't work, but it's very unlikely for what this function is used
coefs = n.polynomial().coefficients()
return coefs
# Italian parameters
italian_p = 2^255 - 19
italian_Fp = GF(italian_p)
italian_E = EllipticCurve(italian_Fp, [0, 486662, 0, 1, 0])
def get_flag():
chall.recvline()
chall.recvline()
chall.recvline()
italian_G = point_from_str(chall.recvline().decode(), italian_E)
italian_pub_key = point_from_str(chall.recvline().decode(), italian_E)
for _ in range(7):
chall.recvline()
words = []
# Sorbillo params
EA = curve_from_str(chall.recvline().decode())
PA = point_from_str(chall.recvline().decode(), EA)
QA = point_from_str(chall.recvline().decode(), EA)
if debug:
print(f"{EA = }")
print(f"{PA = }")
print(f"{QA = }")
for _ in range(4):
words.append('?'*32)
# Italian params
EB = curve_from_str(chall.recvline().decode())
PB = point_from_str(chall.recvline().decode(), EB)
QB = point_from_str(chall.recvline().decode(), EB)
if debug:
print(f"{EB = }")
print(f"{PB = }")
print(f"{QB = }")
priv_B, _b, key = attack(EA, PA, QA, EB, PB, QB)
words.extend(split_in_words(priv_B, 2))
for _ in range(2):
words.append('?'*32)
if debug:
print(f"{priv_B = }")
rand = get_rand(words, key)
chall.sendlineafter(b"> ", b'1')
priv_sorbillo = rand.getrandbits(64)
_a = 3*rand.getrandbits(64) + 1
K = P2 + priv_sorbillo*Q2
phi = E_start.isogeny(K, algorithm="factored")
EA = phi.codomain()
print(f"{EA = }")
print(chall.recvline().decode())
PA, QA = _a*phi(P3), _a*phi(Q3)
print(f"{PA = }")
print(f"{QA = }")
print(chall.recvline().decode())
print(chall.recvline().decode())
chall.recvline()
# These was so useless, have no idea why I did it... :(
priv_key = 1337
K = P3 + priv_key*Q3
phi = E_start.isogeny(K, algorithm="factored")
EB = phi.codomain()
a1_2, a1_1 = elem_to_list(EB.a1())
a2_2, a2_1 = elem_to_list(EB.a2())
a3_2, a3_1 = elem_to_list(EB.a3())
a4_2, a4_1 = elem_to_list(EB.a4())
a6_2, a6_1 = elem_to_list(EB.a6())
chall.sendlineafter(b"a1_1: ", str(a1_1).encode())
chall.sendlineafter(b"a1_2: ", str(a1_2).encode())
chall.sendlineafter(b"a2_1: ", str(a2_1).encode())
chall.sendlineafter(b"a2_2: ", str(a2_2).encode())
chall.sendlineafter(b"a3_1: ", str(a3_1).encode())
chall.sendlineafter(b"a3_2: ", str(a3_2).encode())
chall.sendlineafter(b"a4_1: ", str(a4_1).encode())
chall.sendlineafter(b"a4_2: ", str(a4_2).encode())
chall.sendlineafter(b"a6_1: ", str(a6_1).encode())
chall.sendlineafter(b"a6_2: ", str(a6_2).encode())
PB, QB = phi(P2), phi(Q2)
xP_2, xP_1 = elem_to_list(PB[0])
yP_2, yP_1 = elem_to_list(PB[1])
xQ_2, xQ_1 = elem_to_list(QB[0])
yQ_2, yQ_1 = elem_to_list(QB[1])
chall.sendlineafter(b"xP_1: ", str(xP_1).encode())
chall.sendlineafter(b"xP_2: ", str(xP_2).encode())
chall.sendlineafter(b"yP_1: ", str(yP_1).encode())
chall.sendlineafter(b"yP_2: ", str(yP_2).encode())
chall.sendlineafter(b"xQ_1: ", str(xQ_1).encode())
chall.sendlineafter(b"xQ_2: ", str(xQ_2).encode())
chall.sendlineafter(b"yQ_1: ", str(yQ_1).encode())
chall.sendlineafter(b"yQ_2: ", str(yQ_2).encode())
j = compute_final_curve(EA, priv_key, PA, QA)
shared = int(j.polynomial().coefficients()[0]).to_bytes(int(p).bit_length()//8 + 1, "big")
key = sha256(shared).digest()
chall.recvline()
for _ in range(30):
chall.recvline()
c = rand.getrandbits(1)
if c:
A = -italian_pub_key + 1337*italian_G
else:
A = 1337*italian_G
chall.recvline()
chall.sendline(encrypt_message(str(A[0]).encode(), key))
chall.recvline()
chall.sendline(encrypt_message(str(A[1]).encode(), key))
chall.recvline()
chall.sendline(encrypt_message(b'1337', key))
print(decrypt_message(bytes.fromhex(chall.recvline().decode()), key))
ciphertext = bytes.fromhex(chall.recvline().decode())
plain = decrypt_message(ciphertext, key)
print(f"{plain = }")
get_flag()
```
