Does is work on big endian machines?

[SG7]

Kokke! Thanks for the project, looks great!

A few questions:

1. Can it be used on big endian machines with same results?
2. In ecdh.h two curves NIST_K409 and NIST_K571 are marked as not working. What is a possible reason?

[kokke]

Hi @SG7 and thanks for your kind words :)

1. Can it be used on big endian machines with same results?

Short answer: No I don't think so :O

Longer version: I would expect endianness issues with the definition of polynomials etc. as they are implemented using arrays of 32-bit quantities - An example:

/* 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 }; 

If compiling on big-endian targets, you would probably need to byte-swap the const numerals to achieve the correct values.

I don't have access to big-endian hardware, so I'm not sure to test it myself. Maybe I could test it with QEMU.

---

2. In ecdh.h two curves NIST_K409 and NIST_K571 are marked as not working. What is a possible reason?

I'm not sure exactly what causes those curve-parameters to not work.
I expect it is a bug in the Galois field arithmetic, where I have made an incorrect assumption or something similar.

I can't get ECDSA working with the current finite field arithmetic either, so I expect there to be a bug in there somewhere.

[SG7]

Thank you for your answers! The second problem( 2) is puzzling at least.

I expect it is a bug in the Galois field arithmetic.

If there is such bug I would expect that it should resurface for all the curves sice all of them use the same functions.

If indeed problem is in a functions, one way to catch the problem is to run all field arithmetic functions though tests agains other implementations. Other implementations tests could be used to minimize the efforts.

Another approach would be to run in parallel the failing curve with tiny-ECD and another "good" curve implementation to compare intermediate results. (Maybe there is a buffer overflow or lost carry over bit somewhere.)

There is a few implementations Fast Galois Field Arithmetic Library in C/C++
or Implementation of Galois field arithmetic which could be potentially used for the verification.

[kokke]

Hi @SG7 and thanks for a good discussion :)

I also like checking my code against other implementations, but I haven't been able to find implementations of the ECDH with curves over Galois fields. Everybody seem more interested in prime-field curves these days, and fair enough, they do seem more secure at the moment re http://safecurves.cr.yp.to/

I just can't implement the math as efficient as with the Galois-field arithmetic.

There is a few implementations Fast Galois Field Arithmetic Library in C/C++
or Implementation of Galois field arithmetic which could be potentially used for the verification.

The problem with finding another implementation of Galois-field arithmetic is that it only checks the maths in the binary fields, not if my algorithms are flawed. I would likely make the same mistake twice. I would love to check against a ECC implementation that supported these curves. That would test the library end-to-end and not just the GF2 maths.

(Maybe there is a buffer overflow or lost carry over bit somewhere.)

I have tried running with clang-sanitizer without finding any problems yet, but that doesn't rule it out. I could try run it through CBMC from http://www.cprover.org/cbmc/ - that could prove the absence of run-time errors, but I would need to re-structure the code a bit. It doesn't work well for the looping constructs I've used so far.

Do you have experience with, or knowledge of the subject? I could use an extra pair of eyes on my current (non-working) ECDSA attempt wink-wink :)

[SG7]

I would love to check against a ECC implementation that supported these curves.

I am looking at:

NIST K-409, NIST K-571 and more binary elliptic curves:
https://github.com/relic-toolkit/relic/blob/master/src/eb/relic_eb_param.c

Test vectors:
http://point-at-infinity.org/ecc/nisttv

Optimization of binary elliptic curves arithmetic:
https://www.emsec.rub.de/media/attachments/files/2014/11/MA_Bluhm.pdf

Elliptic curve math library for binary polynomial field curves:
https://github.com/jfqd/illumos-omnios/tree/master/usr/src/common/crypto/ecc

prime
https://github.com/poojagarg/ECC
https://github.com/esxgx/easy-ecc // secp128r1, secp192r1, secp256r1, and secp384r1

Do you have experience with, or knowledge of the subject? I could use an extra pair of eyes on my current (non-working) ECDSA attempt wink-wink.

I am experienced C, C++ programmer and excellent bug catcher but only recently got interested in ECDH. I am not sure if I can improve your ECDSA :) but I could try to contribute.

[kokke]

Hi @SG7 - i totally forgot about this...

I've now uploaded the defunct attempts at ECDSA. Maybe, if you still feel for it, you could have a look :) ?