cross-testing

[real-or-random]

In #635 I was convinced that cross-testing is a good thing. It would be nice to have cross tests for

• https://github.com/elichai/ecc-secp256k1 as inspired by the discussion in Remove OpenSSL tests #635, or another "simple" library
• gnupg. If I understand https://gist.github.com/markblundeberg/af59d7cd234cbdb14dcf9e00f0ea2c17 correctly, it should produce compatible signatures (ignoring the encoding).

[elichai]

Just linking to #641 (which I stopped because there was no more discussion around if it's wanted and how to vendor the code)

[real-or-random]

@gmaxwell suggests micro-ecc in #716. I think that's by far the simplest alternative (simple, mostly portable C), see #716 for a detailed discussion. I'd prefer this over the other mentioned projects. What do people think?

[real-or-random]

Now after the OpenSSL tests are gone, we should make this a priority.

Here are some possibilities:

• kmackay/micro-ecc in pure C: See PR Replace OpenSSL in cross-testing with micro-ecc(uECC) #738.
• elichai/ecc-secp256k1 in Rust. That one is nice because @elichai says he wrote it without really looking at our code here. See PR Adding random tests against a naive implementation #641.
• LLFourn/secp256kfun in Rust
• randombit/botan in C++

I think micro-ecc is a nice option and a good first choice. @elichai would you still interested in getting this in?

#641 got stuck because there was no clear commitment to using Rust. I wouldn't opposed to other languages than C in the test but here's a suggestion that I find very attractive: We could compile the Rust down to (ugly) C using mrustc and vendor this C code. This would mean that we get the best of both worlds: One can compare to an independent simple implementation with the same API and one does not need a Rust compiler to run the tests. The same is true for secp256kfun but I don't know how independent that implementation is. (cc @LLFourn)

But before we decide on the way forward, here's another very interesting direction: A much more sophisticated approach to this kind of testing is cryptofuzz by @guidovranken, which does differential testings of all kinds of algorithms and libraries. For example, it's used to test libsecp256k1 against Botan on oss-fuzz (google/oss-fuzz#5717).

@guidovranken Were you aware of our OpenSSL cross tests (removed in #983)? I really wonder how crytofuzz compares against these. I can imagine it would be superior to simply use cryptofuzz and maybe integrate more libraries such as some of the ones mentioned above.

[guidovranken]

• micro-ecc: There were issues with last time I tried and I abandoned testing it: OSS-Fuzz integration kmackay/micro-ecc#179
• libecc Very good library albeit slow due to timing channel resistance. It is also being fuzzed on OSS-Fuzz against Botan by me.
• Botan is supreme, I use it for testing in almost every crypto project
• I don't know if you're running Wycheproof tests on libsec256k1, but if not, you definitely should. I recently found bugs in another secp256k1 library (https://github.com/paulmillr/noble-secp256k1) after it was audited by simply running Wycheproof tests on it.
• Trezor firmware is very good and is in fact used in the Cryptofuzz fuzzer for libsecp256k1 https://github.com/google/oss-fuzz/blob/0c1d5231de61b4166281b4d5685aa66e9f4948a8/projects/bitcoin-core/build_cryptofuzz.sh#L73

Apart from testing sign/verify/recover, it is also a good idea to test point validation, addition and multiplication.

[real-or-random]

Thanks, that's a helpful overview! Unfortunately the Wycheproof tests do not match our semantics entirely, see C2SP/wycheproof#70 .

@guidovranken Can you also comment on the high-level ideas here? For example, when it comes to functionatily, do you think cryptofuzz is superior in every aspect, or do you think it would still make sense for us to maintain our own cross tests?

Of course there are also other considerations besides functionality, e.g., build integration etc. For example, if we think we stick to maintain own tests because it's easier to ship them to the user, I imagine we could still have a short run of cryptofuzz on CI.

[LLFourn]

The same is true for secp256kfun but I don't know how independent that implementation is. (cc @LLFourn)

The best rust impl to try this approach for would be k256 since it is a completely independent code base and even uses different algorithms for ECC (it uses projective addition formula from https://eprint.iacr.org/2015/1060.pdf). I was going to move secp256kfun over to using it as a backend eventually anyway.

[guidovranken]

@guidovranken Can you also comment on the high-level ideas here? For example, when it comes to functionatily, do you think cryptofuzz is superior in every aspect, or do you think it would still make sense for us to maintain our own cross tests?

A notable shortcoming of CF is that it only compares the results produced by various crypto libraries, but not the absence of results. For example it doesn't confirm the absence of a result in these cases:

• Point multiplication by 0 is an illegal operation and should not produce a result.
• Point addition/multiplication involving invalid points should not produce a result.
• ECDSA recovery that yields a point at infinity pubkey should not produce a result.
• ECDSA verification involving a pubkey or signature which are not valid points may result false or it may not produce a result at all.

Technically, each operation run in a crypto library returns a std::optional<Result>. It returns std::nullopt if it cannot compute a result for any reason, and it returns a Result if it can. Once the operation has been run in every crypto library, CF filters out all results which are std::nullopt. The remaining set is then compared for differences.

So in Python-pseudocode:

results = []

# Run operation in each crypto library
for module in modules:
    results += [ module.Run(operation) ]

# Filter out nullopt results
results = filter(lambda r: r != None, results)

# Detect discrepancies
if len(set(results)) != 1:
    crash()

This logic exists for a good reason in CF but the corollary is that it can miss certain types of bugs. I do want to address this at some point in the future but for now having a separate test suite is still valuable.

[elichai]

The best rust impl to try this approach for would be k256 since it is a completely independent code base and even uses different algorithms for ECC (it uses projective addition formula from https://eprint.iacr.org/2015/1060.pdf).

I'm not sure how true this is, See for example: RustCrypto/elliptic-curves#59, RustCrypto/elliptic-curves#82

[LLFourn]

The best rust impl to try this approach for would be k256 since it is a completely independent code base and even uses different algorithms for ECC (it uses projective addition formula from https://eprint.iacr.org/2015/1060.pdf).

I'm not sure how true this is, See for example: RustCrypto/elliptic-curves#59, RustCrypto/elliptic-curves#82

Right. To be clear I think they use different ECC addition/doubling formula -- I guess field/scalar arithmetic could be pretty similar. I wouldn't be the best judge of that. Still I think it's the best candidate if you want to try cross testing against a rust codebase.

[real-or-random]

This logic exists for a good reason in CF but the corollary is that it can miss certain types of bugs. I do want to address this at some point in the future but for now having a separate test suite is still valuable.

Can you elaborate what these good reasons are? Maybe we could help.

edit: Let me clarify that even if cryptofuzz would be perfect, I still believe it's useful to have simple cross tests in our test suite. cryptofuzz is nothing we will integrate in make check (naturally a lot of dependencies, etc). I think it's good to have something which is easy enough to be run by not only by us but also by our users, packagers, etc. It should ideally just work out of the box without any dependencies.

[guidovranken]

The "good reason" is that I allow every library to fail executing an operation for any or no reason. Reasons include:

• In some libraries I induce random allocation failures, to test its resiliency. If a malloc() fails, then the operation should be allowed to fail.
• In some libraries I hook the PRNG that a library is using (for example for ECDSA signing). For particular outputs of the PRNG, it should be allowed to fail.
• Some libraries have fixed constraints, such as a predefined bignum size. Therefore it is normal that some operations, like multiplication, will fail.
• A library might be implementing only a subset of a primitive in a way that is adequate for its intended usage domain.

In some cases it is dubious whether a certain function failing is signalling some specific information.
For example, if a function which computes a modular inverse fails, is it due to an internal error (e.g. malloc failure) or is it signalling that the inverse does not exist?
I need to review these on a case-by-case basis, so I cannot simply interpret failure as a bug by default.

Currently, the ECC point operations all return a std::optional<component::ECC_Point>. The component::ECC_Point struct is something like this:

struct {
	std::string X;
	std::string Y;
};

In hindsight it would have been better if this struct also included a field bool is_infinity. I could change this, but I would have to do it for all modules, otherwise the whole thing won't compile anymore, so that will take some time.

As a workaround I've started to add asserts to various libraries to ensure certain operations conform to certain expectations.

For example, in secp256k1, I now have:

• Multiplication of valid point must succeed except if scalar is 0 (or multiple of order): https://github.com/guidovranken/cryptofuzz/blob/1cacacc30c43ef5ff9d726eeede90831d55a40e0/modules/secp256k1/module.cpp#L1121-L1127

• Negation of valid point must yield valid point: https://github.com/guidovranken/cryptofuzz/blob/1cacacc30c43ef5ff9d726eeede90831d55a40e0/modules/secp256k1/module.cpp#L1191-L1194

I want to add similar asserts for point addition and point doubling, where the logic will be:

• Addition of two valid points must produce a valid point UNLESS both points are negations of eachother, in which case it must produce point at infinity
• Point doubling of a valid point must always succeed

Feel free to specify additional invariants for any secp256k1 function/operation and I will implement it in the fuzzer.

[real-or-random]

@guidovranken Makes sense. Here's another random thought (that may be stupid): Did you ever consider adding an old version of libsecp256k1? We have done so many changes that this may be interesting. On the other hand, I don't know if this adds much to the diversity of implementations. (Maybe it's useful to cross-test new libsecp256k1 against old libsecp256k1 but not if you're anyway testing in parallel against all the other libraries?)