[nullcon HackIM 2023] Curvy Decryptor1, 2

hakid29·2023년 8월 20일
CTFcrypto
0

cryptohack을 통해 웬만한 ECC attack은 공부했었는데 새로운 공격을 이용한 문제가 있어서 적어본다.

chall

#!/usr/bin/env python3
import os
import sys
import string
from Crypto.Util import number
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Cipher import AES
from binascii import hexlify

from ec import *
from utils import *
from secret import flag1, flag2

#P-256 parameters
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = -3
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
curve = EllipticCurve(p,a,b, order = n)
G = ECPoint(curve, 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)

d_a = bytes_to_long(os.urandom(32))
P_a = G * d_a

printable = [ord(char.encode()) for char in string.printable]

def encrypt(msg : bytes, pubkey : ECPoint):
	x = bytes_to_long(msg)
	y = modular_sqrt(x**3 + a*x + b, p)
	m = ECPoint(curve, x, y)
	d_b = number.getRandomRange(0,n)
	return (G * d_b, m + (pubkey * d_b))

def decrypt(B : ECPoint, c : ECPoint, d_a : int):
	if B.inf or c.inf: return b''
	return long_to_bytes((c - (B * d_a)).x)

def loop():
	print('I will decrypt anythin as long as it does not talk about flags.')
	balance = 1024
	while True:
		print('B:', end = '')
		sys.stdout.flush()
		B_input = sys.stdin.buffer.readline().strip().decode()
		print('c:', end = '')
		sys.stdout.flush()
		c_input = sys.stdin.buffer.readline().strip().decode()
		B = ECPoint(curve, *[int(_) for _ in B_input.split(',')])
		c = ECPoint(curve, *[int(_) for _ in c_input.split(',')])
		msg = decrypt(B, c, d_a)
		if b'ENO' in msg:
			balance = -1
		else:
			balance -= 1 + len([c for c in msg if c in printable])
		if balance >= 0:
			print(hexlify(msg))
			print('balance left: %d' % balance)
		else:
			print('You cannot afford any more decryptions.')
			return

if __name__ == '__main__':
	print('My public key is:')
	print(P_a)
	print('Good luck decrypting this cipher.')
	B,c = encrypt(flag1, P_a)
	print(B)
	print(c)
	key = long_to_bytes((d_a >> (8*16)) ^ (d_a & 0xffffffffffffffffffffffffffffffff))
	enc = AES.new(key, AES.MODE_ECB)
	cipher = enc.encrypt(flag2)
	print(hexlify(cipher).decode())
	try:
		loop()
	except Exception as err:
		print(repr(err))



situation

P=a∗GP = a*G
B=b∗GB = b*G
c=m+pubkey∗b=m+a∗b∗Gc = m + pubkey * b = m + a * b * G

GG, PP, BB, cc 가 주어졌고, aa, bb는 random generate된 상황
decrypt 함수 → BB, cc 를 입력하면 c−a∗Bc - a*B 를 반환

problem1 : recovering m

mm을 구하는 것이 첫 번째 문제이다. 주어진 BB, cc 를 그대로 decrypt함수에 넣으면 if문에 걸려서 이 부분만 우회해주면 된다.

c += G

r.sendline(f"{B.xy()[0]},{B.xy()[1]}".encode())
r.sendline(f"{c.xy()[0]},{c.xy()[1]}".encode())
r.recvuntil(b"c:")

cc에 GG를 더해서 send하면 if문을 우회하고, m+Gm+G를 반환 받는다. 따라서 GG를 빼주면 mm을 구할 수 있다.

x = int(eval(r.recvline().strip().decode()).decode(), 16)
flag = -E.lift_x(GF(p)(x)) - G
print(long_to_bytes(int(flag.xy()[0])).decode())

ENO{ElGam4l_1s_mult1pl1cativ3}


problem2 : recovering a

aa를 구하는 것이 두 번째 문제이다. 직접 dlp를 풀어야만 한다. 문제에 주어진 curve parameter을 봐도 별다른 취약점을 못 찾았다. 대회가 끝나고서야 invalid curve attack으로 문제를 해결할 수 있다는 것을 알게 되었다. (https://crypto.stackexchange.com/questions/88636/what-can-we-recover-with-an-invalid-curve-attack)

위 링크에 나온 바와 같이, 타원곡선에서 덧셈, 곱셈이 수행될 때 bb는 사용되지 않는다. 또한, decrypt함수에서는 주어진 곡선에서의 덧셈을 수행하는데, 입력으로 들어온 점이 주어진 곡선 위의 점인지 verify하지 않는다. 즉, bb를 마음대로 조정하여 다른 곡선 상의 점을 입력으로 넣을 수 있다.

이제, order가 smooth한 곡선들을 찾아서, 각각의 곡선에 대하여 aa에 대한 dlp를 구하고, crt로 정확한 aa값을 구하면 된다.

curve_ord_list = {
    0: 2**96 * 7 * 274177,
    1: 71 * 823 * 1229 * 7489 * 30203 * 1275057701,
    4: 13 * 19 * 179 * 13003 * 1307093479,
}

위의 곡선을 사용하여 aa를 구해보자. 

mod = []
remain = []

for b, sub_ord in curve_ord_list.items():
    E_ = EllipticCurve(GF(p), [a, b])
    G_ = E_.gens()[0]
    c_ = E_.random_point()
    ord_ = G_.order()

    assert ord_ % sub_ord == 0

    B_ = G_ * (ord_ // sub_ord)

    r.recvuntil(b"B:")
    r.sendline(f"{B_.xy()[0]},{B_.xy()[1]}".encode())
    r.recvuntil(b"c:")
    r.sendline(f"{c_.xy()[0]},{c_.xy()[1]}".encode())

    Dx = int(eval(r.recvline().strip()).decode(), 16)

    D_list = E_.lift_x(GF(p)(Dx)), -E_.lift_x(GF(p)(Dx))
    for D_ in D_list:
        try:
            P_ = -D_ + c_
            remain.append(discrete_log(P_, B_, operation="+"))
            mod.append(sub_ord)
            break
        except Exception as e:
            pass

a = crt(remain, mod)

key = long_to_bytes((a >> (8*16)) ^ (a & 0xffffffffffffffffffffffffffffffff))
aes = AES.new(key, AES.MODE_ECB)
flag2 = aes.decrypt(enc)
print(flag2.decode())

ENO{be5t_th1nk_out_0f_th3_curv3}


최종적으로 합친 코드는 다음과 같다.

from pwn import *
from Crypto.Util.number import *
from Crypto.Cipher import AES
from sage.all import *

#context.log_level = "debug"
r = remote("52.59.124.14", 10005)

p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = -3
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
order = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
E = EllipticCurve(GF(p), [a, b])
G = E([0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5])

r.recvuntil(b"Point(")
pk = eval(r.recvline().strip()[:-1])
pk = E(int(pk[0]), int(pk[1]))

r.recvuntil(b"Point(")
gd = eval(r.recvline().strip()[:-1])
B = E(int(gd[0]), int(gd[1]))
r.recvuntil(b"Point(")
pkd_m = eval(r.recvline().strip()[:-1])
c = E(int(pkd_m[0]), int(pkd_m[1]))

enc = bytes.fromhex(r.recvline().strip().decode())
c += G

r.sendline(f"{B.xy()[0]},{B.xy()[1]}".encode())
r.sendline(f"{c.xy()[0]},{c.xy()[1]}".encode())
r.recvuntil(b"c:")

x = int(eval(r.recvline().strip().decode()).decode(), 16)
flag = -E.lift_x(GF(p)(x)) - G
print(long_to_bytes(int(flag.xy()[0])).decode())

curve_ord_list = {
    0: 2**96 * 7 * 274177,
    1: 71 * 823 * 1229 * 7489 * 30203 * 1275057701,
    4: 13 * 19 * 179 * 13003 * 1307093479,
}

mod = []
remain = []

for b, sub_ord in curve_ord_list.items():
    E_ = EllipticCurve(GF(p), [a, b])
    G_ = E_.gens()[0]
    c_ = E_.random_point()
    ord_ = G_.order()

    assert ord_ % sub_ord == 0

    B_ = G_ * (ord_ // sub_ord)

    r.recvuntil(b"B:")
    r.sendline(f"{B_.xy()[0]},{B_.xy()[1]}".encode())
    r.recvuntil(b"c:")
    r.sendline(f"{c_.xy()[0]},{c_.xy()[1]}".encode())

    Dx = int(eval(r.recvline().strip()).decode(), 16)

    D_list = E_.lift_x(GF(p)(Dx)), -E_.lift_x(GF(p)(Dx))
    for D_ in D_list:
        try:
            P_ = -D_ + c_
            remain.append(discrete_log(P_, B_, operation="+"))
            mod.append(sub_ord)
            break
        except Exception as e:
            pass

a = crt(remain, mod)

key = long_to_bytes((a >> (8*16)) ^ (a & 0xffffffffffffffffffffffffffffffff))
aes = AES.new(key, AES.MODE_ECB)
flag2 = aes.decrypt(enc)
print(flag2.decode())

r.interactive()

ENO{be5t_th1nk_out_0f_th3_curv3}

꽤 흥미로운 공격 방식이어서 이해하면서 재미있었다.🙃🙃

profile
hakid29
.
이전 포스트

LLL practice 3

다음 포스트

[DownUnder CTF 2023] apbq-rsa-ii

0개의 댓글