expl_uff.py

from pwn import *
import random
import pickle
import binascii
from pure25519.eddsa import *

def getrandbytes(l):
    return bytes(bytearray(random.getrandbits(8) for _ in xrange(l)))


def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m


def get_pubkeys(r):
    pubkeys = []
    for i in range(8):
        r.recvuntil("public key: ")
        pubkeys.append(binascii.unhexlify(r.recvuntil("\n").strip()))
    print(pubkeys)
    return pubkeys


def write_msg(r, pubkey, msg):
    l = len(msg)
    r.recvuntil("public key> ")
    r.sendline(pubkey.encode("hex"))
    r.recvuntil("length> ")
    r.sendline(str(l))
    r.recvuntil("message>")
    r.sendline(msg.encode("hex"))
    r.recvuntil("signed:     ")
    signature = binascii.unhexlify(r.recvuntil("\n")[:-1])
    
    return signature


def send_forge(r, forged_msg):
    r.recvuntil("public key> ")
    r.sendline(("\xaa"*32).encode("hex"))
    r.recvuntil("forgery>")
    r.sendline(forged_msg.encode("hex") + "X")
    return r.recvuntil("}")[-100:]


def calc_hash(sig, pk, msg):
    return scalar_to_bytes(Hint(sig[:32] + pk + msg))


found = False
from time import sleep
while not found:
    sleep(0.1)
    rem = remote("159.69.218.92", 25519)
    pubs = get_pubkeys(rem)
    for pub in pubs:
        if "\x00" in pub:
            weak_key = pub
            print("Found weak key", weak_key)
            found = True
            break
    else:
        rem.close()


wrong_key = bytearray(weak_key)
null_pos = weak_key.index("\x00")
wrong_key[null_pos + 1] = wrong_key[null_pos + 1] ^ 0xFF 
wrong_key = bytes(wrong_key)

msg = "pensi"

S1 = write_msg(rem, weak_key, msg)[:-1 * len(msg)]
S2 = write_msg(rem, wrong_key, msg)[:-1 * len(msg)]
h1 = calc_hash(S1, weak_key, msg)
h2 = calc_hash(S2, wrong_key, msg)

p = 2**252 + 27742317777372353535851937790883648493

denom = modinv((bytes_to_scalar(h1) - bytes_to_scalar(h2)), p)
nom = bytes_to_scalar(S1[32:]) - bytes_to_scalar(S2[32:])
secret_s = (nom * denom) % p


def sign(secret_s, pk, m):
    a = secret_s 
    r = Hint("313373373337737")
    R = Base.scalarmult(r)
    R_bytes = R.to_bytes()
    S = r + Hint(R_bytes + pk + m) * a
    return R_bytes + scalar_to_bytes(S)

forged_msg = "olololol"
forged_sig = sign(secret_s, weak_key, forged_msg)
assert checkvalid(forged_sig, forged_msg, weak_key), "Signature inavlid"

print("Signature: ", forged_sig.encode("hex"))
print(send_forge(rem, forged_sig + forged_msg))