Regression in Elliptic Curve Operation on brainpoolP256r1

[Philippe Antoine]

Hi cryptopp users,

My same is Philippe Antoine.

I have been doing differential fuzzing about elliptic curve cryptography with different libraries including cryptopp.

On August the 6th, oss-fuzz found the first regression after about one year.

I think this is dut to commit https://github.com/weidai11/cryptopp/commit/c9ef9420e762b91cc06463d349cf06e04c749b9d

My output is the following

point=04202020202020ffffff2020202020200020ffffffff20202020ff20ff20ff200104c8423eb699c3ace2e623855cb9238cb43971464f4b6686765c46ed4ce035dc

bignum=000000000000000000000000000000000000000000000000000000000000000a

mbedlts:045de6bae41907dbe3f0aa32b272add6b92fb2b79fdc49af35fb844be1c4c629e899295109c41cfe76a9c06c23d95b2d4be3b6f61a476acf1a67a0d848abba89e1

libecc:045de6bae41907dbe3f0aa32b272add6b92fb2b79fdc49af35fb844be1c4c629e899295109c41cfe76a9c06c23d95b2d4be3b6f61a476acf1a67a0d848abba89e1

libecc:045de6bae41907dbe3f0aa32b272add6b92fb2b79fdc49af35fb844be1c4c629e899295109c41cfe76a9c06c23d95b2d4be3b6f61a476acf1a67a0d848abba89e1

openssl:045de6bae41907dbe3f0aa32b272add6b92fb2b79fdc49af35fb844be1c4c629e899295109c41cfe76a9c06c23d95b2d4be3b6f61a476acf1a67a0d848abba89e1

gcrypt:045de6bae41907dbe3f0aa32b272add6b92fb2b79fdc49af35fb844be1c4c629e899295109c41cfe76a9c06c23d95b2d4be3b6f61a476acf1a67a0d848abba89e1

cryptopp:0407f16bad8b16f5441f1a15f8e7eca364d97bb3a3c09b320bb9807ee26857b66f882ba526e55ebbf22342ae5a0186ed0ca1db8870fd001c63ae36dc72ee15f6e7

That means when I multiply by 10 the point on the curve brainpoolP256r1

x = 202020202020ffffff2020202020200020ffffffff20202020ff20ff20ff2001

y = 04c8423eb699c3ace2e623855cb9238cb43971464f4b6686765c46ed4ce035dc

I get a different result than all the other libraries

I will look into it a bit more, but I already wanted to let you know this...

Best regards,

Philippe

[Jeffrey Walton]

Thanks Philippe.

Yeah, that's not good. Does your test include a fresh check-out and
build of the Crypto++ library?

Jeff

[Philippe Antoine]

Hi Jeffrey,

Yes, version commit is 8fa8ec9913ccd2ce44f71014322ddb7e198fef68 from yesterday.
It used to work before

Regression range is Cryptopp: b3eb4c6a690d6dfb342856f2a66a71dcec8c429b:a01711e347df30a994609537ce9be2926a366a44

Regards,
Philippe

[Jeffrey Walton]

Ugh, I can duplicate it with:

Integer x("0x202020202020ffffff2020202020200020ffffffff20202020ff20ff20ff2001");
Integer y("0x04c8423eb699c3ace2e623855cb9238cb43971464f4b6686765c46ed4ce035dc");
Integer s("0x000000000000000000000000000000000000000000000000000000000000000a");

GroupParameters params(ASN1::brainpoolP256r1());
ECP::Element p(x, y);

ECP::Element t = params.GetCurve().ScalarMultiply(p, s);
std::cout << std::hex << t.x << std::endl;
std::cout << std::hex << t.y << std::endl;   

[Jeffrey Walton]

I've got it isolated to Double(P). Restoring the previous Double() fixes the issue.

I hope to have a fix tonight or tomorrow.

Jeff

[Jeffrey Walton]

On Monday, August 26, 2019 at 4:42:58 PM UTC-4, Philippe Antoine wrote:

Hi Jeffrey,

Yes, version commit is 8fa8ec9913ccd2ce44f71014322ddb7e198fef68 from yesterday.
It used to work before

https://github.com/weidai11/cryptopp/commit/8fa8ec9913cc is a documentation update. Probably happened before that.

Regression range is Cryptopp: b3eb4c6a690d6dfb342856f2a66a71dcec8c429b:a01711e347df30a994609537ce9be2926a366a44

https://github.com/weidai11/cryptopp/commit/c9ef9420e762. is the problem. Things work fine at:

    $git checkout c9ef9420e762

    $git checkout HEAD~1  # rewind by 1 commit

I'm not sure why our self tests did not detect the failure. I think that is a bigger problem.

We're tracking it at https://github.com/weidai11/cryptopp/issues/878

Jeff

[Jeffrey Walton]

Thanks again Phillipe.

Can you give https://github.com/weidai11/cryptopp/commit/e06e3bd7a998 a try?

Jeff

[Philippe Antoine]

Hi Jeffrey,

Can you give https://github.com/weidai11/cryptopp/commit/e06e3bd7a998 a try?

This temporary fix makes it ok again :-)

Congratulations for getting this quickly, I am glad I could help.

I'm not sure why our self tests did not detect the failure. I think that is a bigger problem.

I can share with you the fuzzer generated corpus.

This way, you can find out different cases (even if there are ones not especially related to cryptopp)

Best regards,

Philippe

PS : I forgot to mention that this bug was found by oss-fuzz

[Philippe Antoine]

Hi,

The fix does not seem complete.

Here is another reproducer found by oss-fuzz

Integer x("0x20ffff2020ff000020ff2020202020ff20ff20ff202020ffffff20200020ffff");
Integer y("0xba1a84de8fe276f1d082e3e7c10f35e0baca90baca7c9502044854dba0ecdebc");
Integer s("0x0000000000000000000000000000000000000000000000000000000000000007");

GroupParameters params(ASN1::brainpoolP256r1());
ECP::Element p(x, y);

ECP::Element t = params.GetCurve().ScalarMultiply(p, s);
std::cout << std::hex << t.x << std::endl;
std::cout << std::hex << t.y << std::endl;

Result should be

04a171dbcb9c038c01ebd7635e4302f87d38c5cc3babb819239b52572d6fb4490804ed340e0d0f7a2e47cf1f48273dc2d40434c295254c55ae420912e4d2c5be02

Instead, we get

0400000000000000000000000000000000000000000000000000000000000000003238e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e38e06aa8539

Best of luck,

Philippe    

--
You received this message because you are subscribed to "Crypto++ Users". More information about Crypto++ and this group is available at http://www.cryptopp.com and http://groups.google.com/forum/#!forum/cryptopp-users.
---
You received this message because you are subscribed to the Google Groups "Crypto++ Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to cryptopp-user...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/cryptopp-users/1BA21383-E3A1-4E56-9C59-607245ED7A71%40catenacyber.fr.

[Jeffrey Walton]

On Friday, August 30, 2019 at 12:08:58 PM UTC-4, Philippe Antoine wrote:

Hi,

The fix does not seem complete.

Here is another reproducer found by oss-fuzz

Integer x("0x20ffff2020ff000020ff2020202020ff20ff20ff202020ffffff20200020ffff");
Integer y("0xba1a84de8fe276f1d082e3e7c10f35e0baca90baca7c9502044854dba0ecdebc");
Integer s("0x0000000000000000000000000000000000000000000000000000000000000007");

Thanks Phillipe.

So it looks like the problem is limited to brainpool curves at the moment. I'm guessing it may apply to custom curves, too.

I found oss-fuzz at https://github.com/google/oss-fuzz. Is this your GitHub with the sources? If so, could you point out the program of interest?

Jeff

[Philippe Antoine]

Hi Jeffrey,

So it looks like the problem is limited to brainpool curves at the moment. I'm guessing it may apply to custom curves, too.

That is indeed the reproducer given by oss-fuzz.

I am not sure if oss-fuzz would give another reproducer with another curve (or treat it as duplicate)

I can download and send you the whole corpus so that you can run tests on it if you wish.

My fuzzer does not do custom curves, only standard ones from TLS standard (see the sources from the link below).

I found oss-fuzz at https://github.com/google/oss-fuzz. Is this your GitHub with the sources? If so, could you point out the program of interest?

For the sources, you can indeed check out 

https://github.com/google/oss-fuzz/tree/master/projects/ecc-diff-fuzzer

But this contains about only the compile script.

So, I think you want rather this :

https://github.com/catenacyber/elliptic-curve-differential-fuzzer

All the best,

Philippe

[Jeffrey Walton]

On Monday, September 9, 2019 at 2:06:51 AM UTC-4, Philippe Antoine wrote:

Hi Jeffrey,

So it looks like the problem is limited to brainpool curves at the moment. I'm guessing it may apply to custom curves, too.

That is indeed the reproducer given by oss-fuzz.

I am not sure if oss-fuzz would give another reproducer with another curve (or treat it as duplicate)

I can download and send you the whole corpus so that you can run tests on it if you wish.

My fuzzer does not do custom curves, only standard ones from TLS standard (see the sources from the link below).

Thanks again Philippe. I've got some free time and want to loop back around to this again.

Have you noticed any patterns to the failures? I think the first step is to generate some test data and wire it into our self tests. Known answer tests where we arrive at the expected answer are OK, but I really want the ones like you are finding.

Based on the two failures, does this only happen when x gets large, like within a certain range of p? Or maybe with the high bit set?

Jeff