Writeup - crypto- pekobot AIS3 Pre-Exam 2022

f.md

This solution is possibly unintended and based on logic vuln (i saw just pohlig-hellman attack in the author's writeup - https://github.com/maple3142/My-CTF-Challenges/blob/master/AIS3%20Pre-exam%202022/pekobot/solve.sage )

Solution

def encrypt(P, m):
    key = point_to_bytes(P)
    return bytes([x ^ y for x, y in zip(m.ljust(64, b"\0"), key)])

encrypt - just xor point x,y with plaintext And we see two options:

1. get encrypt result of point S*d and random.choice(quotes)

print("Public key wo kudasai!")
x = int(input("x: "))
y = int(input("y: "))
S = Point(E, x, y)
print(encrypt(S*d, choice(quotes).encode()).hex())

We can control S coordinates and we can bruteforce random.choice(quotes) then we can get S*d for any point S 2) we can get r*G and encrypt(r*P, flag) where P=d*G (where G is known point)

r = randbelow(n)
C1 = r * G
C2 = encrypt(r * P, flag)
print(point_to_bytes(C1).hex())
print(C2.hex())

Our plan:

1. get r*G and encrypt(r*(d*G), flag)
2. send S=r*G and get encrypt(r*G*d, random.choice(quotes)) there is no crypto lol

final script:

import pwn
from elliptic_curve import Curve,Point
from binascii import unhexlify as unhex

io = pwn.remote('archive.cryptohack.org',45328)
pwn.context.log_level = 'debug'

quotes = ["Konpeko, konpeko, konpeko! Hololive san-kisei no Usada Pekora-peko! domo, domo!","Bun bun cha! Bun bun cha!","kitira!","usopeko deshou","HA↑HA↑HA↓HA↓HA↓","HA↑HA↑HA↑HA↑","it's me pekora!","ok peko",]
a = -3
b = 41058363725152142129326129780047268409114441015993725554835256314039467401291
p = 2**256 - 2**224 + 2**192 + 2**96 - 1
E = Curve(p, a, b)
# E = EllipticCurve(GF(p), [a,b])
n = 115792089210356248762697446949407573529996955224135760342422259061068512044369
Gx = 48439561293906451759052585252797914202762949526041747995844080717082404635286
Gy = 36134250956749795798585127919587881956611106672985015071877198253568414405109
G = Point(E, Gx, Gy)

def point_to_bytes(P):
    return P.x.to_bytes(32, "big") + P.y.to_bytes(32, "big")

def bytes_to_point(bs):
    x = int.from_bytes(bs[:32], "big")
    y = int.from_bytes(bs[32:], "big")
    return (x,y)

def encrypt(P, m):
    key = point_to_bytes(P)
    return bytes([x ^ y for x, y in zip(m.ljust(64, b"\0"), key)])

def check(x,y):
    return (y**2-x**3-a*x-b)%p

io.sendlineafter('> ', '2')
C1 = bytes_to_point(unhex(io.recvline().decode().strip()))
C2 = unhex(io.recvline().decode().strip())
print('C1 = ', C1)
print('C2 = ', C2)

io.sendlineafter('> ', '1')
io.sendlineafter(': ', str(C1[0]))
io.sendlineafter(': ', str(C1[1]))
s = (unhex(io.recvline().decode().strip()))
S_d = bytes_to_point(s)

xs =[]
ys = []

for q in quotes:
    x,y = bytes_to_point(encrypt(Point(E,S_d[0],S_d[1]),q.encode()))
    if check(x,y): # check point lies on curve
        print(f'FOUND for quote "{q}":',x,y)
        xs.append(x)
        ys.append(y)

io.close()

for x,y in zip(xs,ys):
    print(encrypt(Point(E,x,y), C2))

And i dont know why we get some parts of flag and some garbage

b'EK\x07*lk\x11very_bad_ecc_implementation}8~\xe6\xab\x1dR\xfa\x97jd\x7f:b\xad\xf0\xac-\xce\xb0?\xe5?\xa8\x1f\xde\xc6\x01\x1e\xf7'
b'AIS3{a_very_baf_ecc]!,\x92\xea\xf6mentation}\xf9\xddZ\x0ef\xf1\xcf\\\x8b\xdf}\x1c\x06\xad\xf9\xd7\xd0n\xdd\xdc{\x9fuZ\xb5\xb4\xe3\xd7\xe9'

and some garbage:
b'K}\xdf\x95\x88\\p\xb4\x80\x8bP?\xa0\xa5\x80y\x04\xe3\x90\xa0I\x0e\x18\rDmentation}\xf9\xddZ\x0ef\xf1\xcf\\\x8b\xdf}\x1c\x06\xad\xf9\xd7\xd0n\xdd\xdc{\x9fuZ\xb5\xb4\xe3\xd7\xe9'
b'ba\xc5\xdc\x98H?\x94\xe3\xe31\x1e\x80\xe7\xf5\x17$\x81\xe5\xceimplementation}\xf9\xddZ\x0ef\xf1\xcf\\\x8b\xdf}\x1c\x06\xad\xf9\xd7\xd0n\xdd\xdc{\x9fuZ\xb5\xb4\xe3\xd7\xe9'