Overhaul ECDSA signature parsing: strict DER, compact sigs, tests, lower-S #334

1. 
   sipa commented at 11:42 pm on October 12, 2015: contributor

   There are now 2 encoding formats supported: 64-byte “compact” and DER. The latter is strict: the data has to be exact DER, though the values inside don’t need to be valid.

   This means that applications that need more than strict DER as input, it needs to have a parser itself. I wish there was a better solution, but there really isn’t. Any subset of BER to implement would be arbitrary, incompatible with many other applications anyway, or be very complex and nearly untestable. Despite that, a code snippet to do so (with extensive testing) is included in the contrib/ directory now.

   Finally, by default, we now require non-malleable signatures (by requiring the lower-S form), but a separate function is provided to normalize a signature before verification if needed.

2. sipa force-pushed on Oct 12, 2015
3. sipa force-pushed on Oct 13, 2015
4. sipa force-pushed on Oct 14, 2015
5. sipa force-pushed on Oct 14, 2015
6. 
   sipa commented at 4:02 pm on October 14, 2015: contributor

   Added a commit that introduces a snippet for lax DER parsing (tested!).
7. sipa force-pushed on Oct 17, 2015
8. 
   sipa commented at 8:01 pm on October 17, 2015: contributor

   Addressed many comments.
9. sipa renamed this:
   Rewrite ECDSA signature parsing code
   Overhaul ECDSA signature parsing: strict DER, compact sigs, tests, lower-S
   on Oct 17, 2015
10. sipa force-pushed on Oct 17, 2015
11. sipa force-pushed on Oct 17, 2015
12. sipa force-pushed on Oct 18, 2015
13. sipa force-pushed on Oct 19, 2015
14. 
    sipa commented at 4:00 pm on October 19, 2015: contributor

    Added a certainly_not_der as output from the BER generator, and tests using it.
15. Improve testrand: add extra random functions

    This commit adds functions:
    * secp256k1_rand_bits, which works like secp256k1_rand32, but consumes
      less randomness
    * secp256k1_rand_int, which produces a uniform integer over any range
    * secp256k1_rand_bytes_test, which works like secp256k1_rand256_test
      but for arbitrary byte array

    251b1a62d3
16. Faster secp256k1_rand_int implementation f684d7d987
17. Add new tests for the extra testrand functions 49b374985d
18. Use secp256k1_rand_int and secp256k1_rand_bits more

    Update the unit tests to make use of the new RNG functions.

    fa57f1bdf1
19. Rewrite ECDSA signature parsing code

    There are now 2 encoding formats supported: 64-byte "compact" and DER.
    The latter is strict: the data has to be exact DER, though the values
    inside don't need to be valid.

    3bb9c44719
20. Add contrib/lax_der_parsing.h

    This shows a snippet of code to do lax DER parsing, without obeying to any
    particular standard.

    fea19e7bb7
21. Introduce explicit lower-S normalization

    ECDSA signature verification now requires normalized signatures (with S in the
    lower half of the range). In case the input cannot be guaranteed to provide this,
    a new function secp256k1_ecdsa_signature_normalize is provided to preprocess it.

    0c6ab2ff18
22. sipa force-pushed on Oct 21, 2015
23. gmaxwell cross-referenced this on Oct 21, 2015 from issue Test improvements and some small API fixes that they turned up. by gmaxwell
24. 
    gmaxwell commented at 5:42 pm on October 22, 2015: contributor

    ACK
25. sipa merged this on Oct 22, 2015
26. sipa closed this on Oct 22, 2015

    ---

27. sipa referenced this in commit 131afe5bf5 on Oct 22, 2015
28. sipa cross-referenced this on Nov 28, 2016 from issue Implement secp256k1_ecdsa_signature_serialize and int secp256k1_ecdsa_signature_parse by rustyrussell
29. practicalswift cross-referenced this on Jan 23, 2021 from issue Potential UB in secp256k1_der_parse_integer? by practicalswift

Contributors
sipa gmaxwell