Eliminate Hand-Rolled Cryptography

[DavidBuchanan314]

This is a meta-issue to figure out how to eliminate various forms of hand-rolled crypto from the Python atproto ecosystem, both in this repo, and in general.

A quick summary of the relevant areas of cryptography in atproto (official docs)

• Asymmetric keys are either secp256k1 ("bitcoin flavour") or secp256r1 (aka NIST-P256)
• Signatures for both key types use the ECDSA algorithm in conjunction with SHA256,
  • In "low-S" form as described in bitcoin BIP-0062
  • Serialised to bytes in "raw/compact*" format, which is 32 big-endian bytes of "r", followed by 32 big-endian bytes of "s"

*I don't think this format has a standard name! It's quite common though, for example, it's used internally to JWT

There are python bindings for secp256k1 libraries that handle these constraints internally (e.g. https://pypi.org/project/secp256k1/, due to its use in the Bitcoin world) , but I don't think there are existing solutions out there for producing low-S NIST-P256 signatures.

For that reason, and because I like pyca/cryptography, I adapted it to this use-case like so. As noted in the comments, this is a bit of a hack, and my hacks have since been incorporated into other Python projects in the atproto ecosystem. This isn't very good! We need to solve this properly, which either means writing some kind of "atproto crypto" wrapper library, or getting the needed features upstreamed. Since pyca/cryptogrphy depends on openssl, this might mean contributions to openssl.

Signature Serialisation

First, what is the format even called? Raw? Compact? IDK!

It could be a new pyca/cryptography feature, in the cryptography.hazmat.primitives.asymmetric.utils module (alongside encode_dss_signature and decode_dss_signature)

pyjwt already implements compatible logic inside jwt.utils https://github.com/jpadilla/pyjwt/blob/12420204cfef8fea7644532b9ca82c0cc5ca3abe/jwt/utils.py#L77-L96 (der_to_raw_signature and raw_to_der_signature respectively). Maybe these methods could be upstreamed into pyca/cryptography as-is? It would be a very uninvasive change.

Edit: webcrypto uses the same format, https://developer.mozilla.org/en-US/docs/Web/API/SubtleCrypto/sign#ecdsa

This encoding was also proposed by the IEEE 1363-2000 standard, and is sometimes referred to as the IEEE P1363 format.

Low-S enforcement

Assuming the der_to_raw_signature and raw_to_der_signature helper functions are adopted, they could be extended with a boolean flag that indicates whether Low-S should be enforced. The low-S-ness could be considered a serialisation detail, after all.

mockup: (based on jwt.utils linked above)

def der_to_raw_signature(der_sig: bytes, curve: "EllipticCurve", to_low_s: bool) -> bytes:
    num_bits = curve.key_size
    num_bytes = (num_bits + 7) // 8

    r, s = decode_dss_signature(der_sig)
    
    if to_low_s and s > curve.group_order // 2:
        s = curve.group_order - s

    return number_to_bytes(r, num_bytes) + number_to_bytes(s, num_bytes)


def raw_to_der_signature(raw_sig: bytes, curve: "EllipticCurve", from_low_s: bool) -> bytes:
    num_bits = curve.key_size
    num_bytes = (num_bits + 7) // 8

    if len(raw_sig) != 2 * num_bytes:
        raise InvalidSignature("Invalid signature length")

    r = bytes_to_number(raw_sig[:num_bytes])
    s = bytes_to_number(raw_sig[num_bytes:])

    if from_low_s and s > curve.group_order // 2:
        raise InvalidSignature("Invalid signature (high-S)")

    return bytes(encode_dss_signature(r, s))

The big blocker on this is that EllipticCurve.group_order isn't a thing. My current implementation hardcodes a lookup table - ideally, pyca/cryptography could provide this information itself (which probably means openssl needs to expose it, too)

Edit: EC_GROUP_get_order is a thing https://www.openssl.org/docs/man3.0/man3/EC_GROUP_get_order.html

[DavidBuchanan314]

This patch would avoid the need to hard-code curve group orders pyca/cryptography@main...DavidBuchanan314:cryptography:expose-group-order

[DavidBuchanan314]

upstreamed group order constants coming soon: pyca/cryptography#12113