Cross tests with libecc

BerryYoghurt commented at 12:47 pm on June 24, 2022: none

TODO:

Try the test test_secp256k1_sign_libecc_verify(). (I still need to figure out how to try it without the whole ci overhead)
Write a test to sign with libecc and verify with libsecp256k1
Perform a byte-by-byte comparison
Add to ci properly

Cross test: sign with secp256k1, verify with libecc 5048bd559d

sign with secp256k1 - verify with libecc tested and runs correctly 51c18c18f8

in src/tests.c:6918 in 51c18c18f8 outdated

6913+    pubkey_buf += 1; // this is needed because libecc only supports uncompressed points
6914+    pubkey_len -= 1; // and does not recoginze B0
6915+
6916+    ec_pub_key ec_pubkey;
6917+    CHECK(ec_pub_key_import_from_aff_buf(&ec_pubkey, (const ec_params *)&params,
6918+                                         pubkey_buf + 1, pubkey_len - 1,

real-or-random commented at 4:38 pm on June 30, 2022:

Is this intentional given the lines above, where you already modify pubkey_buf and pubkey_len?

BerryYoghurt commented at 6:45 pm on June 30, 2022:

Oh. That’s a careless mistake I always make. After I successfully ran the test (without first modifying pubkey_buf and pubkey_len), I thought modifying them first would “look” better. So I did it and forgot to run the test again to check. I turns out that the code doesn’t even compile with pubkey_buf += 1, so the “better looking” modification is actually worse. I’ll correct the mistake. My bad!

real-or-random commented at 7:55 pm on June 30, 2022:

My bad!

No worries, we all have bugs in our draft code. ^^

in src/tests.c:6914 in 51c18c18f8 outdated

6909+
6910+    const ec_sig_mapping *sig_mapping;
6911+    CHECK(get_sig_by_name("ECDSA", &sig_mapping) == 0);
6912+
6913+    pubkey_buf += 1; // this is needed because libecc only supports uncompressed points
6914+    pubkey_len -= 1; // and does not recoginze B0

real-or-random commented at 4:39 pm on June 30, 2022:

What is B0?

Are you sure libecc doesn’t support compressed keys? that would surprise me.

and typo: “recoginze” ;)

BerryYoghurt commented at 6:54 pm on June 30, 2022:

After reading https://github.com/ANSSI-FR/libecc/blob/master/src/sig/ec_key.h several times, I concluded that libecc supports importing projective or affine coordinates, in either a “structured” or an “unstructured” format. By structured they mean that the buffer includes the curve parameters, the signature algorithm, etc., in addition to the key. So I thought the simplest way to port libsecp’s public key to libecc is through an unstructured affine buffer.

By B0 I just mean the first byte :). I took this terminology from here. I was puzzled why the public key produced by libsecp is 65 bytes long when a key is really two 32-byte values. So I googled a bit and found that “uncompressed keys” have an extra 04 at the beginning.

sipa commented at 7:00 pm on June 30, 2022:

Are you confusing jacobian/projective coordinates with compressed/uncompressed encoding?

Affine coordinates are tuples (x, y) on the curve.
Projective coordinates are tuples (X, Y, Z) representing the affine coordinate (X/Z, Y/Z).
Jacobian coordinates are tuples (X, Y, Z) representing the affine coordinates (X/Z^2, Y/Z^3).

SECG encoding of public keys is (all representing affine coordinates):

Compressed encoding
- (0x02 || x) for even y
- (0x03 || x) for odd y
Uncompressed encoding
- (0x04 || x || y)

BerryYoghurt commented at 7:07 pm on June 30, 2022:

Thanks for succinctly summarizing the different presentations :), but I don’t think I’m confusing them. I believe I’ve used the correct formats/encodings/presentations in the code..? The only mistake I’ve done is offsetting pubkey_buf twice.

real-or-random commented at 7:49 pm on June 30, 2022:

@BerryYoghurt Now you updated the comment to “does not recognize B0 = 04”. But that wouldn’t that mean it supports only compressed and not only uncompressed?

BerryYoghurt commented at 9:31 pm on June 30, 2022:

@real-or-random I think we have a misunderstanding because I did not word my comment correctly. The best wording will probably be “does not recognize the header byte”. libecc really only supports uncompressed keys, but throws errors at the header byte. It explicitly checks that the public key is exactly 64 bytes long (for curve secp256k1). Does that clear the misunderstanding?

real-or-random commented at 9:23 am on July 1, 2022:

Ok, yes. It’s surprising to me that libecc does not support compressed keys but I agree after looking at their code…

Anyway, this problem will just disappear if you simply pass the secret key to libecc and let libecc compute the public key (in whatever format it needs). That’s anyway necessary if you want to compare the result of signing (see below) and it’s also simpler.

BerryYoghurt commented at 2:12 pm on July 1, 2022:

@real-or-random For byte-by-byte comparison I’ll do that, but when signing with libsecp and verifying with libecc, isn’t it more logical to give libecc access only to the public key? I mean, the verifier doesn’t normally have the private key, they’re supposed to read the public key and the message from the signer then check the signature. Right?

sipa commented at 2:30 pm on July 1, 2022:

Perhaps it’s better to refer to this format supported by libecc as “raw public keys” or something like that; “uncompressed” is likely to be understood as SECG’s (0x04 || X || Y) format.

real-or-random commented at 3:08 pm on July 1, 2022:

@real-or-random For byte-by-byte comparison I’ll do that, but when signing with libsecp and verifying with libecc, isn’t it more logical to give libecc access only to the public key? I mean, the verifier doesn’t normally have the private key, they’re supposed to read the public key and the message from the signer then check the signature. Right?

So yes, in the real world, the signer obviously wouldn’t reveal the secret key.

For our purpose of cross-testing however, this is fine. If libecc recomputes the public key, then the cross-test would also cover the computation of the public key from the secret key. So if there’s a difference between the two libs in that algorithm, the test would also catch it.

BerryYoghurt commented at 3:01 pm on July 7, 2022:

@real-or-random I was convinced of cross-testing the key generation algorithm, and it is now done in the same testcase that compares signatures byte by byte. However, after writing the new testcase, I am still reluctant to derive the public key from the private key in the other two – for two reasons. First, it’s not much simpler (code-wise) to import the private key instead of the public key. The only difference is avoiding the header byte. Second, since it’s already done in test_compare_libecc_secp256k1, I think having both is better, more or less. What do you think?

real-or-random commented at 11:21 am on July 11, 2022:

Hm, I think if we verify with libsecp256k1 and libecc in test_compare_libecc_secp256k1, then we won’t need the other two tests anymore.

edit: Let me try to explain in more detail. So in general, I see that it makes sense to have multiple test cases. But one of the goals here should be efficiency because later on we want to run many iterations in a loop. In that sense

sign with libecc
sign with libsecp256k1
check sigs are identical
verify with libecc
verify with libsecp256k1

seems a rather efficient way of doing tests, i.e., we get a lot of “test value” per running time.

real-or-random commented at 6:19 pm on June 30, 2022: contributor

Nice :)

Do you have some instructions on how to build this together with libecc, so that people can play around with it?

I think the next step would be to try to produce the same signature with libsecp256k1 and libecc, and see if they match exactly. This should work out as libecc also uses deterministic ECDSA with RFC6979, so it should be the exact same algorithm. (If not, we need to see if they do something differently, and you may need to switch to their low-level function https://github.com/ANSSI-FR/libecc/blob/master/src/sig/fuzzing_ecdsa.c#L31.)

fix an over-optimization fbada8fc5e

BerryYoghurt commented at 7:15 pm on June 30, 2022: none

Do you have some instructions on how to build this together with libecc, so that people can play around with it?

The way I build them is a bit hacky and I am actually looking for a better way. But here it is:

clone libecc into the secp256k1/src
build libecc with CFLAGS="-W -Werror -Wextra -Wall -pedantic -fno-builtin -O3 -DWITH_LIBECC_CONFIG_OVERRIDE -DWITH_CURVE_SECP256K1 -DWITH_HASH_SHA256 -DWITH_SIG_ECDSA -DWITH_SIG_DECDSA -DWITH_HMAC -DWITH_STDLIB -fPIC" make debug (I used debug to know why tests failed when they did)
compile the tests.c file with gcc -ggdb -Wall -Wextra -Wno-unused-function tests.c ./precomputed_*.c ./libecc/src/external_deps/rand.o -I.. -L./libecc/build -lsign -o tests -D ECMULT_GEN_PREC_BITS=4 -D ECMULT_WINDOW_SIZE=15 -DENABLE_LIBECC_TESTS -DWITH_STDLIB -DWITH_LIBECC_CONFIG_OVERRIDE -DWITH_CURVE_SECP256K1 -DWITH_HASH_SHA256 -DWITH_SIG_ECDSA -DWITH_SIG_DECDSA -DWITH_HMAC . I don’t like that I have to (seemingly?) compile libecc twice. So I was thinking I could just declare the structs and functions I use in a little header file to be a part of libsecp, but I was postponing this decision till the end.
run ./tests 1 (to reach the libecc cross-tests quickly)

EDIT: modified to accommodate deterministic ECDSA

Merge branch 'master' of github.com:BerryYoghurt/secp256k1 into libecc-cross-tests

ci fails

dc3739304a

BerryYoghurt commented at 7:23 pm on June 30, 2022: none

I think the next step would be to try to produce the same signature with libsecp256k1 and libecc, and see if they match exactly. This should work out as libecc also uses deterministic ECDSA with RFC6979, so it should be the exact same algorithm. (If not, we need to see if they do something differently, and you may need to switch to their low-level function https://github.com/ANSSI-FR/libecc/blob/master/src/sig/fuzzing_ecdsa.c#L31.)

By this, do you mean comparing the signatures byte by byte?

real-or-random commented at 7:52 pm on June 30, 2022: contributor

By this, do you mean comparing the signatures byte by byte?

Yes, the serialized representations should be identical byte by byte.

Cross test: sign with libecc, verify with secp256k1 c9e6a88bc5

apostrophes are evil? 7e50c80b0b

byte-by-byte comparison 26bd2d39e3

BerryYoghurt commented at 3:17 pm on July 7, 2022: none

I am having some difficulty in including libecc cleanly.

What I thought I could do:

Write a header file libsig.h in src of libsecp256k1. In this header, forward declare all libecc structs and functions which will be used in tests.c. Include this file in tests.c, naturally.
Clone libecc in any directory, x, and build it. Then link the archive while compiling tests.c.

But the problem I’m facing right now is that most (if not all) libecc’s structs are anonymous (e.g., https://github.com/ANSSI-FR/libecc/blob/master/src/curves/ec_params.h#L51), and anonymous structs cannot be forward-declared.

I think there must be a way of “plugging in” libecc’s archive without compiling it twice..

Any help would be appreciated!

real-or-random commented at 7:03 pm on July 7, 2022: contributor

Hm, I’m not sure I can follow. So why would you want to forward-declare those?

So the usual way to use a C library is include its header in your source file and then later link against the compiled library. So you would

Create a file src/libecc-tests.c or similar (you could also use tests.c but I think a separate program will be cleaner, just make sure you #include "secp256k1.c like in tests.c to have full access to all internal functions).
Then include libsig.h from libecc,
which makes sure you can call public libecc functions in your src/libecc-tests.c
if you link to libecc later.

Or if item 1 adds complexity, first skip it and use the existing tests.c.

Or is the problem that you need access to internal functions or types of libecc?

real-or-random commented at 4:06 pm on May 8, 2023: contributor

Closing due to lack of activity. Cross-testing is tracked in #691.

real-or-random closed this on May 8, 2023

Cross tests with libecc #1112