secp256k1_ecdsa_sign: document the low S values

DavidEGrayson commented at 0:49 am on February 2, 2015: none

Hello. I am working on a Ruby binding for libsecp256k1. When I was writing a test for secp256k1_ecdsa_sign, I was surprised that the signature it produced was different from the signature produced by my pure-Ruby ECDSA implementation, even though I had passed the same arguments to both. I looked into it and I determined that the difference was caused by these lines in libsecp256k1, which force the S value to be in the lower 50% of its range:

https://github.com/bitcoin/secp256k1/blob/e84e761915e7882badcb611c40bb1c17b22d99eb/src/ecdsa_impl.h#L201-205

This pull request which adds documentation to the secp256k1_ecdsa_sign function explaining the low S values. For people using the library for Bitcoin, I think this is an important guarantee to have on the signature, so it should be documented and we (anyone developing the library) should commit to it. For people using the library for other purposes, or comparing it to other implementations, the low S values might be surprising since it makes this library behave differently from the standard ECDSA signing algorithm.

In general, my understanding is that ECDSA is defined by SEC1, so if this library behaves differently from SEC1 then we should document that difference and explain the motivation for it. Does that sound good? Or is there some other standard you refer to?

secp256k1_ecdsa_sign: Document the low S value property.

For people using the library for Bitcoin, this is an important
guarantee to have on the signature, so it should be documented
and we should commit to it.

For people using the library for other purposes, the low S values
might be surprising since it makes this library behave differently
from the standard ECDSA signing algorithm.

d2069df0be

gmaxwell commented at 1:46 am on February 2, 2015: contributor

The signing implemented by this library is standard signing. The difference is that the nonce is selected so that S is always in the lower part of the range. The nonce is random in standard ECDSA. So this is not defined by SEC1.

It’s computationally simpler to correct it after the fact rather than testing nonces, and since anyone can post process a signature to achieve this in any case (so it cannot reduce security).

I’d rather not direct users some place else to understand why this is done. I’ll create another PR in the moment.

As an aside, your binding implementation should almost certainly not expose users to direct nonce selection. If you do some will generate nonces in insecure ways which will guarantee a security compromise.

DavidEGrayson commented at 2:37 am on February 2, 2015: none

Thank you for the information. I look forward to seeing the PR you create.

Continuing your aside about nonce generation in a Ruby binding: I understand why you want to hide the nonce generation features from users, because of the “Be difficult to use insecurely” principle from libsecp256k1’s README. However, I do not think that a Ruby-language binding is the right place to implement important decisions like that. I do not see why the Ruby users would need more protection than the C users for that sort of thing.

I envision just making a very boring Ruby binding that provides access to all of the features of libsecp256k1, without hiding anything or adding anything. I think there is value in having a consistent-feeling interface to the library, regardless of whether you are writing your code in Ruby, C, or something else. (I do want to protect the users from undefined behavior and memory leaks because that is what they should expect in Ruby. I am not sure yet if I want to protect them against race conditions caused by calling secp256k1_start in different threads concurrently.) The features/principles/values that I have written down so far in the README for the Ruby binding are:

Provides access to all features of the secp256k1 library.
Does not add any new features.
Avoids making arbitrary decisions when possible.
Provides a safe interface: there should be no way for a user of the wrapper to cause undefined behavior or memory leaks. (One exception is multiple threads are used in an unsafe way.)
Avoids making assumptions about the behavior of the library that do not come from the official documentation.
Exception messages produced by this wrapper are less verbose than they could be to help avoid leaking secret information.

I’ll definitely make it easier to use the secure default options than to generate your own nonces.

I also think it would be fine to have a separate, higher-level API in Ruby that removes features and adds protections, but I think the lower-level API should come first.

gmaxwell commented at 2:45 am on February 2, 2015: contributor

We have tentative plans to remove the global initialization and either replace it with a context variable or make all of it static.

DavidEGrayson commented at 2:51 am on February 2, 2015: none

Thanks, that would be nice. I was wondering what I would do if I had two different modules/libaries using libsecp256k1 in the same process. I decided it would be safe if there was a single-threaded initialization phase where each module called secp256k1_start with the flags that it requires, and then I would just never call secp256k1_stop. But if you change the way initialization is done, people won’t have to think so hard about that stuff.

DavidEGrayson commented at 1:23 am on February 4, 2015: none

I’m closing this because pull request #205 does a better job.

DavidEGrayson closed this on Feb 4, 2015

secp256k1_ecdsa_sign: document the low S values #204