Schnorr Protocol Implementation - Sometimes Fails on Curve25519

Question

I am implementing the Schnorr Protocol in python and am having reliability issues when using some curves. I am wondering if this is an issue with my logic, or some implementation issue. I am using ECPy version 0.8 to implement a Schnorr Signature.

Terminology and notes:

• Public keys are called ZKSignature and are public pieces of information stored on a server
• The self.hash method returns the salted hash of the provided data, converted to an int, modulo the curve order
• Points are converted to/from bytes automatically during hashing

Following the Schnorr Signature for signature generation, we follow the Key Generation section in the afore-linked wiki:

Note: The params refer to the arbitrary hashing algorithm, curve, and salt used throughout the process.

def hash_numeric(*values: Union[str, bytes, bytearray, int, Point], alg="sha3_256") -> int:
    """
    Compute the cryptographic hash of the provided values and return the digest in integer form
    """
    return convert.bytes_to_int(hash_data(*values, alg=alg))

class ZK:

    ...

    def hash(self, *values) -> int:
        return hash_numeric(*[
            v for v in values if v is not None
        ], self.params.salt, alg=self.params.alg) % self.curve.order

    def create_signature(self, secret: Union[str, bytes]) -> ZKSignature:
        return ZKSignature(
            params=self.params,
            signature=to_bytes(
             self.hash(secret) * self.curve.generator),
        )

This seems to be where my issue lies.

Creation of a "ZKProof" object follows the Signing section of the wiki with a simple helper function called sign to create ZKProofs.

class ZK:

    ...

    def create_proof(self, secret: Union[str, bytes], data: Union[int, str, bytes]=None) -> ZKProof:
        key = self.hash(secret)                     # Create original private signing key
        r = secrets.randbits(self._bits)            # Generate random integer of comparable size to curve
        R = r * self.curve.generator                # Random point whose discrete log, `r`, is known
        c = self.hash(data, R)                      # Hash the data to sign and the random point
        m = mod(r - (c * key), self.curve.order)    # Send offset between discrete log of R from c*x mod curve order
        return ZKProof(params=self.params, c=int_to_bytes(c), m=int_to_bytes(m))

    def sign(self, secret: Union[str, bytes], data: Union[int, str, bytes]) -> ZKData:
        data = to_str(data)
        return ZKData(
            data=data,
            proof=self.create_proof(secret, data),
        )

The resulting ZKProof object is also public data. This can be fed into ZK.verify along with the public signature. This demonstrates that the creator of the ZKProof knows the discrete logarithm of the public Signature point (their salted password hash), without revealing what the password or hash value is.

class ZK:
  ...

    def verify(self, challenge: Union[ZKData, ZKProof], signature: ZKSignature, data: Union[str, bytes, int]=""):
        if isinstance(challenge, ZKProof):
            data, proof = data, challenge
        elif isinstance(challenge, ZKData):
            data, proof = challenge.data, challenge.proof
        else:
            raise TypeError("Invalid challenge type provided")
        # Now `data` contains the message and `proof` contains the ZKProof generated above
        c, m = map(bytes_to_int, (proof.c, proof.m))
        return c == self.hash(data, (m * self.curve.generator) + (self._to_point(signature) * c))

Everything here works flawlessly for every curve that ECPy has defined except for Curve25591 (it even works with Ed25591). I'm wondering if this is an implementation issue on ECPy's part or if there is something different about the Curve25591.

The jwt() method creates a signed JSON Web Token which contains the public signature and salt, is signed by the server, and expires 10 seconds after generation, which means for a login to be successful, you must return a provably signed version of a JWT which only lasts for 10 seconds.

Side-note: For usernames that do not exist, a fake signature is generated using a salted hash of their username to derive the salt and signature. This makes it impossible to determine who is and is not signed up as requesting any user will always give you a seemingly static salt and signature.

def foo():
    curves = [
        "secp256r1", "secp256k1", "secp224k1", "secp224r1",
        "secp192k1", "secp192r1", "secp160k1", "secp160r1", "secp160r2",
        "Brainpool-p256r1", "Brainpool-p256t1", "Brainpool-p224r1", 
        "Brainpool-p224t1", "Brainpool-p192r1", "Brainpool-p192t1",
        "Brainpool-p160r1", "Brainpool-p160t1", "NIST-P256", "NIST-P224",
        "NIST-P192", "Ed25519", "Curve25519",
    ]

    hash_algs = [
        "blake2s", "blake2b", "md5", "sha3_256", "sha3_512",
    ]

    jwt_algs = [
        "HS3_256", "HS3_512",   # SHA3 256/512
        "HB2S", "HB2B",         # BLAKE2 S/B
    ]
    
    for c in curves:
        g, b = 0, 0
        for _ in range(50):
            zk = ZK.new(
                curve_name=c,
                hash_alg=random.choice(hash_algs),
                jwt_secret=JWT_SECRET, jwt_alg=random.choice(jwt_algs), salt_size=16,
            )

            sig = zk.create_signature(PASSWORD)
            # This signature is the public key and can be stored 

            for i in range(5):
                # User can sign a JWT generated by the server which itself contains the signature
                data = zk.sign(PASSWORD, zk.jwt(sig))

                # Server validates/reads JWT and checks the signed message against the signature within the JWT
                if zk.login(data):
                    g += 1
                else:
                    b += 1
        print(c, "Good:", g, "Bad:", b)

With the output looking like this:

secp256r1 Good: 250 Bad: 0
secp256k1 Good: 250 Bad: 0
secp224k1 Good: 250 Bad: 0
secp224r1 Good: 250 Bad: 0
secp192k1 Good: 250 Bad: 0
secp192r1 Good: 250 Bad: 0
secp160k1 Good: 250 Bad: 0
secp160r1 Good: 250 Bad: 0
secp160r2 Good: 250 Bad: 0
Brainpool-p256r1 Good: 250 Bad: 0
Brainpool-p256t1 Good: 250 Bad: 0
Brainpool-p224r1 Good: 250 Bad: 0
Brainpool-p224t1 Good: 250 Bad: 0
Brainpool-p192r1 Good: 250 Bad: 0
Brainpool-p192t1 Good: 250 Bad: 0
Brainpool-p160r1 Good: 250 Bad: 0
Brainpool-p160t1 Good: 250 Bad: 0
NIST-P256 Good: 250 Bad: 0
NIST-P224 Good: 250 Bad: 0
NIST-P192 Good: 250 Bad: 0
Ed25519 Good: 250 Bad: 0
Curve25519 Good: 120 Bad: 130

What I have realized is that, if a signature is generated which can produce a valid proof, then 100% of the proofs generated from that signature are valid. However, if it does not produce a valid proof, then 100% of the proofs generated are invalid. I cannot for the life of me understand what is different about this curve.