Any progress?

[ifknot]

Hi, really compact and very readable implementation that I have just started following - did SG7 and yourself make any plans/progress?
Many thanks

[kokke]

Hi @ifknot - thanks for the compliments :)

I take it you are referring to issue #5 ?

Which part specifically are you concerned about, big-endianness support or an ECDSA implementation?

I haven't worked on any of the two issues, but thank you for reminding me: @SG7 said he might take a look at my ECDSA implementation, but I forgot to upload it...
Thanks for reminding me! I will see to it, that I get my broken ECDSA uploaded.

Big-endian support should be achieved by byte-swapping the const uint32_t numerals defining the curve:

/* NIST K-163 */
const gf2elem_t polynomial = { 0x000000c9, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000008 }; 
const gf2elem_t coeff_b    = { 0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000 }; 
const gf2elem_t base_x     = { 0x5c94eee8, 0xde4e6d5e, 0xaa07d793, 0x7bbc11ac, 0xfe13c053, 0x00000002 }; 
const gf2elem_t base_y     = { 0xccdaa3d9, 0x0536d538, 0x321f2e80, 0x5d38ff58, 0x89070fb0, 0x00000002 }; 
const scalar_t  base_order = { 0x99f8a5ef, 0xa2e0cc0d, 0x00020108, 0x00000000, 0x00000000, 0x00000004 }; 

[ifknot]

@kokke Hi yes 1/ an ECDSA sign and verify would be interesting 2/ any further with NIST K409 & K571 not working? Thanks
Edit for ECDSA could avoid CSDRNG issues by derive k's for msg and pkey?

[kokke]

Hi @ifknot

1/ an ECDSA sign and verify would be interesting

I agree. I really would like for this library to gain ECDSA capabilities.
Curve operations over binary Galois-fields are super-efficient, compared to say prime-curves.

2/ any further with NIST K409 & K571 not working?

Unfortunately no further progress on fixing the bugs with NIST K409 and K571 curves.
I haven't looked much into the issues since first determining that those curves were broken.

for ECDSA could avoid CSDRNG issues by derive k's for msg and pkey?

My interface for ECDSA signing is similar to that of ECDH: The user provides the random data.
That way, any PRNG can be used - cryptographically secure or not.
This little "trick" also separates this project from a CSDRNG :)

I will upload the code for ECDSA in a few hours when I get home.

[kokke]

I've committed my non-working attempts of the ECDSA functionality

[zcode1]

Can you clarify if both ecdsa_sign() and ecdsa_verify() are currently not working? I'm particularly interested in using verify for one particular curve at the moment.

Also, I was curious why in ecdsa_verify() you use gf2field_mul() for the step: (u1 * G) + (u2 * public)?
I noticed openssl uses EC_point_mul() in its verify function and by the name I thought perhaps you would use gf2point_mul() function here too.

[kokke]

Hi @zcode1 as the comments in the code says, ECDSA is currently not working.

I have uploaded the defunct code and marked this issue as "help wanted" exactly for this reason, to get hints from users (like yourself :)) to help me debug ECDSA.

Can you point me to the OpenSSL code you are referring to?

[zcode1]

Ok, thanks for the clarification.

Below is a link to the openssl code. Your algorithm looks similar, although I'm not familiar enough with the functions to understand any differences.

https://github.com/openssl/openssl/blob/master/crypto/ec/ecdsa_ossl.c#L434

[kokke]

Nice! That will hopefully provide me some insight as to why the current scheme is failing.

Thank you very much for your help @zcode1 :)

[zcode1]

I was hoping to sign a message using openssl and then pass it to your ecdsa_verify() function to verify. However I realized that your curve parameters are in reverse order from that used by openssl (network order). To correspond with that, I assume the byte order for the input parameters to ecdsa_verify() are all expected be LSB first?

[kokke]

To be frank with you @zcode1, I don't have much experience using the OpenSSL library. It is new to me if they support the same curves out of the box, but I haven't researched the case thoroughly.

This project - and especially the certification part - is still very much a work in progress.

[kokke]

At the moment the source code is not in any shape to do what you wish. I put the code online in a broken shape, hoping that someone would point me towards a solution. I don't have free time to check again with your new remarks, so don't expect progress (from me at least) in the near couple of weeks.

I will be very happy to accept pull requests that help massage the code towards a working certification part though - wink wink ;)

[zcode1]

Hi @kokke,
I have come back to look at the verify steps in more detail...
I see you have opened an issue regarding point multiplication - please confirm your changed lines are as below:
gf2point_mul(x1, y1, u1); //gf2field_mul(u1, x1, y1); /* u1 * G /
gf2point_mul(w, z, u2); //gf2field_mul(u2, w, z); / u2 * Q */

Also, I have a question about step 4) w = inv(s) mod n. The ANS x9.62 spec indicates that n = order. Should gf2field_inv() use base_order to perform the modulo operation in this step somehow? I only see the curve parameter "polynomial" used in gf2field_inv() but not "base_order." This seems correct for the shared_secret application (because that is working) but wondering if it needs to be different for verify? I suppose this applies to all "mod n" for verify steps.

[zcode1]

@kokke, Looking further at step 4) w = inv(s) mod n

Using this example calculator (https://www.xarg.org/tools/modular-inverse-calculator/)
x = a^-1 mod m
input: a=3, m=11
output: x = 4

When I try these values for gf2field_inv():
z = x^-1 mod polynomial
input: x = 3, polynomial = 11
output: z = 6

Do you expect the field inversion calculation to differ compared to this general calculator?

[xorhash]

I haven't gotten this to work yet (I came here after trying to get ECDSA into an ECIES library but gave up after realizing how much bignum math I'd have to implement), but I've been doing some reading on binary field EC lately. Allow me to preface it by expressing my deepest disbelief that anybody ever implemented any of this correctly.

At least for the verify step, as far as I know, all math except for the point addition/point multiplicatoin step should be normal modular bignum arithmetic instead of field arithmetic. I believe ecdsa_verify() steps 1–5 should not use field arithmetic; at the very least inv(s) mod n is almost certainly regular modular arithmetic. Presumably something similar would apply to signing. You'll likely have to import the entire tiny-bignum-c project and make it run in const time if that's a goal.

NIST has some examples with intermediate values for each step. You should probably work with these test vectors while developing it.

I also scoured found these other C implementations for reference (studying the ones with more restrictive licenses than tiny-ECDH-c without two cycles of rewrites will presumably end in a legal issue due to copyright infringement):

• OpenSSL (and forks), Apache-2.0 License
• Crypto++, Boost Software License? (license only as a compilation, so chopping individual parts from the source files together would presumably be covered by the public domain waiver on them?)
• NSS, MPLv2
• something in segher's Wii tools (ECDSA verification over NIST B-233 only), GPLv2
• ninty-233 (NIST B-233 only), GPLv2

Seems NIST B-233 in particular is extraordinarily popular because of Nintendo using it for something.

Missing support for short Weierstrass curves over binary fields are the following notable general cryptography libraries: libtomcrypt, GnuTLS, libgcrypt, mbedTLS.

Incidentally, djb and Andreas Hülsing have recently written a paper on fast constant-time modular inversion, which may or may not be useful to reference for the inv(s) operation after getting this whole thing to work.

[xorhash]

EDIT disregard this because Fermat's little theorem is a thing: More weather update: tiny-bignum-c will probably also need changes to represent signed numbers for the modular inverse operation. Getting ECDSA to work is probably going to be a relatively massive undertaking. Unless you've got serious licensing/memory constraints, sticking to the path beaten by other libraries is likely the only realistic way to go.

[mohamed-amine-mighri]

Hi,
I wanted to ask how I can perform the CPU cycle count for this ECDH implementation so I can test its performance. I need these tests in order to compare its performance with Crystal's Kyber.