Description:
I just launched my brand new signature service called "message.sign".
The domain is still missing but you can beta-test it if you want.
Hopefully you are not finding any bugs, let me know if you do :)
Within the challenge, the user is able to sign messages, initialize a curve-object and exit.
The code for the Curve-Class looks like this:
class Curve:
def __init__(self, hash_function: typing.Callable):
self.hash_function = hash_function
self.priv_key = bytes_to_long(FLAG.encode())
self.lfsr = LFSR(
message_sign_secret.LSFR_SEED,
message_sign_secret.LSFR_MASK,
64
)
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
K = GF(p)
a = K(0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc)
b = K(0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b)
self.E = EllipticCurve(K, (a, b))
self.E.set_order(n * 0x1)
self.G = self.E(
0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296,
0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5
)
def public_key(self) -> EllipticCurvePoint:
return self.priv_key * self.G
def sign(
self,
message: str
) -> tuple[sage.rings.finite_rings, sage.rings.finite_rings]:
message_digest = self.hash_function(message.encode()).digest()
e = bytes_to_long(message_digest)
r, s = 0, 0
while r == 0 or s == 0:
# According to the internet, the nonce has to be selected securely
k = self.lfsr.get_int(256)
P = k * self.G
P_x, P_y = P.xy()
r = Fn(P_x)
s = Fn(Fn(k)^(-1) * (e + r * self.priv_key))
return (r, s)
def verify(
self,
message: str,
signature: tuple[sage.rings.finite_rings, sage.rings.finite_rings],
priv_key: int
) -> bool:
r, s = signature
r, s = Fn(r), Fn(s)
e = bytes_to_long(self.hash_function(message.encode()).digest())
s_inverse = Fn(s)^(-1)
u1 = (e * s_inverse) % n
u2 = (r * s_inverse) % n
P = (u1 * self.G) + (u2 * priv_key * self.G)
P_x, P_y = P.xy()
return Fn(P_x) == rIn the konstructor (__init__), the class creates a LFSR-Object using a seed and a mask from the file message_sign_secret.py
As mentioned in the comment within this file, the content that participants are given is different from the one that is running on the remote server.
The LFSR-Object is being used in order to crate the nonce for the ECDSA signature.
Participants might not be able to break the LFSR by itselfe, but they are able to reinitialize the Curve-Object.
By doing this, they can force a nonce-reuse which is enouth to break ECDSA.
If we can force a nonce-reuse, then we are able to calculate the nonce (and therfore also the private key) from two seperate signatures.
The nonce reuse was successfull if
The private-key can be calcualted in the following way:
This can finally be rearanged into:
Now that we have recovered the nonce, we can use it to calcualte the private key.
Now the previous formular for k can be used in thie formula. In order to make it more readable, I'll use fractions.
However because everything is being computed withn a finite field, the division does not exist (only the modulo-inverse does).
The following exploit solves the challenge locally
import hashlib
import json
import os
from Cryptodome.Util.number import inverse
from Cryptodome.Util.number import bytes_to_long
from Cryptodome.Util.number import long_to_bytes
import pwn
n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
def sign_message(chall_connection, message: str) -> tuple[int, int]:
pwn.log.info(f"Receive the signature for {message}")
chall_connection.sendline(
json.dumps(
{
"action": "sign",
"message": message
}
).encode()
)
chall_connection.recvuntil(b"signature: ")
signature = chall_connection.recvline().decode().strip()
(r, s) = signature.split("(")[1].split(")")[0].split(", ")
r, s = int(r), int(s)
return (r, s)
def main() -> int:
chall_connection = pwn.process(["sage", "challenge.sage"])
pwn.log.info(f"Connection: {target}")
host, port = target.split(":")
chall_connection = pwn.remote(host, int(port))
msg_1 = "Hello World"
msg_2 = "Hello ACSC"
chall_connection.recvuntil(b">")
(r1, s1) = sign_message(chall_connection, msg_1)
e1 = bytes_to_long(hashlib.sha256(msg_1.encode()).digest())
chall_connection.recvuntil(b">")
chall_connection.sendline(
json.dumps({
"action": "init"
}).encode()
)
chall_connection.recvuntil(b">")
(r2, s2) = sign_message(chall_connection, msg_2)
e2 = bytes_to_long(hashlib.sha256(msg_2.encode()).digest())
assert(r1 == r2)
nominator = (((s2 * e1) % n) - ((s1 * e2) % n)) % n
denominator = (r1 * ((s1 - s2) % n)) % n
d = (nominator * inverse(denominator, n)) % n
pwn.log.success(f"Flag: {long_to_bytes(d)}")
chall_connection.sendline(
json.dumps({
"action": "exit"
}).encode()
)
return 0
if __name__ == "__main__":
raise SystemExit(main())