Digest truncation should happen according to bitlength not bytelength

[kyrkonos]

FIPS 186.4 states that:

If the length of the output of the hash function is greater than the bit length of n, then the leftmost n bits of the hash function output block shall be used in any calculation using the hash function output during the generation or verification of a digital signature.

(6.1.1 https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf)

However in python-ecdsa/src/ecdsa/keys.py 686-688, 1359-1361:

digest = normalise_bytes(digest)
if allow_truncate:
digest = digest[: self.curve.baselen]

truncation is based on the baselen value, which is calculated by python-ecdsa/src/ecdsa/util.py 62-63:

def orderlen(order):
return (1 + len("%x" % order)) // 2 # bytes

which returns the length in bytes and not bits as it should. If the bitlength happens to be a multiple of 8 (as usual) then the issue remains hidden.

[tomato42]

isn't the digest value taken modulo order later?

[kyrkonos]

Yes, but the wrong truncation cannot be reverted. See the following example:
Let's assume that n=37, so n.bit_length() = 6
If the digest is 0x9F... (10011111...) then the right truncation would be z = 100111b (39d) (the 6 leftmost bits). z % n = 39 % 37 = 2.
If the digest is truncated according to the byte-length then it would be z = 0x9F (159d) (1 byte). In this case z % n = 159 % 37 = 11

[tomato42]

The only curve "affected" (the only one with order that doesn't have a bit size that's a multiple of 8) is NIST521p, so you'd need to use it with some weird hash to hit this issue.
I won't work on it.

[kyrkonos]

Yes, you are right. All of the supported curves will work with no issue.
The reason I used this library was for testing and teaching purposes. So, I created a custom curve with a small prime and number of points so that it can be easily handled in general (graph the points, calculate coordinates etc).
Do you have any suggestion for any other library that I can use for this purpose?

[tomato42]

No, I don't have any suggestions for alternatives for learning about ECC.

I can point out that you don't have to use output from a real hash to understand what's happening when signing and verifying: ECDSA will work just the same when signing a single byte value (we don't use such short hashes because collisions for them are trivial, not because authenticating single-byte value doesn't make sense)

secondly, while I won't work on patches to fix it, I will review any PR fixing it and I'll merge it if it's good enough (consistent code style, test coverage)

[tomato42]

it was easier to fix than I expected so I did prepare a PR in the end: #215

@kyrkonos please check if it fixes the issue for you