Deterministic signing? about micro-ecc HOT 21 CLOSED

I had considered it, but I never got around to implementing it. Pull requests are welcome! The last part of uECC_sign() (after the first do-while loop) could be factored out and used in both cases. I assume the hash function would be passed in as an argument to uECC_sign_deterministic()?

from micro-ecc.

Yes, my thinking exactly. I don't want to include any hashing algorithms in the code, simple the ability to pass them as function pointers. I like the lean, concise nature of the code base.

from micro-ecc.

Hello all.
I implemented RFC6979 in a very stripped down version of the uECC code (for Bitcoin applications) here.

A unit test is here.

I won't have time in the immediate future to submit a pull request, but will try to do so, unless someone else adds it first. Using a separate function int uECC_sign_deterministic(...) as ricmoo suggests would be more portable than my implementation. Ricmoo, feel free to use this code if you wish.

from micro-ecc.

That is awesome! I got as far as implementing HMAC and the non-160-bit signing before other things booked up all my recent time. I also hit a road block trying to find/generate test vectors.

Are all those extra files from https://github.com/trezor/trezor-crypto ? It's a great library, but I would probably distill it down to the parts just needed for RFC6979. Perhaps including 1 additional file would be alright, which would contain all the deterministic goop? Then just one new uECC.h forward declaration for a version of sign that takes in a k? What do you think, @kmackay? You are the one that has to maintain this? :)

I also wasn't sure if the existing vli_* functions would suffice for the 160-bit curve since I don't think they allow values beyond the intended range of n, which means you won't be able to detect overflow, which for RFC6979 requires extra rounds to try to derive k... Again, I think... Some of the finer points of both the code and the standard had my brain puttering in circles...

from micro-ecc.

I don't really see a reason to have an additional file, as long as the hash function is passed in. The HMAC and k derivation code isn't really that complex.

For the 160-bit curve, you will need to do 1 extra round on average since curve_n is only slightly bigger than 2^160. I think all of the necessary functions for dealing with curve_n-sized integers are already defined since they are already used in the existing signing code.

from micro-ecc.

The Trezor crypto code base was a starting point for me, and much of the goop is from there (including the rfc function and unit test). The hmac file was not attributed at the time I pulled it, but I see they added a copyright for themselves and a license since. Their ECDSA code was quite leaky (in terms of side channel attacks), so I was happy to find the uECC library. I agree that distilling the rfc functions down as much as possible and trying to keep everything in one file is an attractive solution.

from micro-ecc.

I am also interested in deterministic signing, though I havn't written any line of code for it yet.

A generic HMAC construction needs to know the size of one internal block B and the size of the output digest L for the underlying cryptographic hash function. By passing in a hash function as an argument to uECC_sign_deterministic(), do you mean passing in the function pointer as well as the parameters (B, L) about the hash function? If that is the case, it looks like we should have an HMAC function in uECC.c first, whose prototype might looks like this:

static void hmac(void (*H)(const uint8_t *i, size_t ilen, uint8_t *o),
                 size_t B, size_t L,
                 const uint8_t *key, size_t keylen,
                 const uint8_t *msg, size_t msglen,
                 uint8_t *output);

The new uECC_sign_deterministic() function has to accept those parameters from its caller first and passes them into generate_k() and then hmac(). If passing (B, L) at run time looks terrible, we might need to wrap (H, B, L) as a struct... Or just use uECC_BYTES for L and another preprocessor macro for B value which the user must provide in advance. (e.g., B is either 64 or 128 for SHA-2)

In fact we never use the hash function directly, since uECC_sign() accepts hashed input. Thus we could also choose to make the new uECC_sign_deterministic() and generate_k() functions accept an HMAC function pointer, which is a little bit simpler... But the user might only have a hash function without any HMAC implementation.

from micro-ecc.

I implemented deterministic signing (not tested yet). Currently it requires the user to define the block size and output size for their hash algorithm. Another option would be to have the user create the necessary scratch buffers (2 buffers sized to the hash output size, and 1 buffer sized to the hash block size) and pass them in in the hash_context.

from micro-ecc.

I ended up preferring the method where the user passes in a scratch buffer in hash_context. I forgot to put #37 in the commit message though :-(

from micro-ecc.

Looks awesome, @kmackay! Test vectors for secp256k1 are easy to generate, but some of the other curves are hard to find libraries for that support RFC6979. I'll poke around a bit this weekend and try to generate a test suite.

from micro-ecc.

FYI the implementation deviates slightly from the RFC (in ways that do not impact the security), so I don't think you will be able to directly compare against existing test vectors.

from micro-ecc.

There are test vectors in the RFC with values for k. In theory if I did it right, the k values calculated by micro-ecc are endian-reversed from the test vectors.

from micro-ecc.

Dear @kmackay, thanks for your work on these! After taking a look at your current implementation of uECC_sign_deterministic(), I think it is very close to RFC 6979 already. Maybe all we need to add is just the bits2octets() conversion from RFC 6979? I will try it out later.

from micro-ecc.

In the commit 40f4ad5, I add a function rfc6979_bits2octets() which is used for converting message_hash into an octet string that matches the byte length of the curve order. After a T value is chosen, vli_bytesToNative() is used for a candidate of k.

Because I wanted a MSB first format of curve_n and the original vli_ functions do not handle the endianness, N_1 ~ N_4 and some arithmetics are hardcoded there. (Or we need to refactor the code)

I have tested the code under secp256r1 with SHA-256, and the testing vector from RFC 6979 passes. Feel free to use the code directly or let me know if you prefer opening another pull request.

from micro-ecc.

In addition, if we select the curve secp160r1, the average number of retries before we get a RFC6979-correct k value will be definitely higher than the current value of MAX_TRIES == 64. That needs to be fixed too.

EDIT: This is not true. The average number of retries is about 2, and MAX_TRIES == 64 is a good choice.

from micro-ecc.

I don't see any reason to use bits2octets for k or message_hash. It doesn't add any security, and it increases the code size and signing time.

from micro-ecc.

@concise - why would you expect the maximum number of retries to be large for secp160r1? As far as I can tell the expected number of tries should be approximately 2 (since curve_n is only slightly larger than 2^160). My testing indicates that a good value for k is generated typically on the first or second try, and in 256,000 random signs, the maximum number of tries was 18.

The probability of the number of tries being greater than 64 is approximately 2^-64.

from micro-ecc.

I don't see any reason to use bits2octets for k or message_hash. It doesn't add any security, and it increases the code size and signing time.

That's a good call. The only possible reason of the additional code size and computation time is for testing the correctness against other RFC 6979 implementations, if anyone is interested.

As far as I can tell the expected number of tries should be approximately 2

Oh, that is a good catch. For some stupid reason, I thought the integer outputted from bits2int() is 168-bit, but it should be only 161-bit long. Therefore you are right about the successful probability of each trial to be 0.5. Thanks for correcting that!

from micro-ecc.

@concise Thanks for trying out the deterministic signing; it is good to get verification that the implementation would conform to RFC 6979 if bits2octects was added.

from micro-ecc.

I had a thought: why have two implementations of sign, one using a random number, the other using a DRBG? Why not just expose sign_with_k(), and let the user be responsible for how K is generated?

At the very least, that means the HMAC code can go away.

Applying this way of thinking elsewhere has the potential to entirely remove any dependency of uECC on a random number generator.

Does this sound completely insane?

from micro-ecc.

Generating k using the deterministic algorithm is fairly complicated to do correctly. It's nicer to provide an implementation of it. In general, I am trying to reduce the amount of complexity that users need to deal with as much as possible; exposing the fact that signing depends on a 'k' value is the kind of thing that I am trying to abstract away.

from micro-ecc.