Skip to content

Miscomputations of elliptic curve scalar multiplications in Nettle

The Nettle library is a library for basic cryptographic functions. Its most prominent user is GnuTLS.

Through fuzzing of elliptic curve scalar multiplications (multiplying a point on an elliptic curve with a scalar number) I discovered two carry propagation bugs that would lead the cauculations to produce wrong results. They affect the NIST P-256 and P-384 curves. The P-256 bug is in the C code and affects multiple architectures. The P-384 bug is in the assembly code and only affects 64 bit x86. Both bugs were found with the help of american fuzzy lop.

While analyzing these bugs Nettle developer Niels Möller discovered another carry propagation bug in P-256 that was fixed in the same commit (CVE-2015-8805). Nettle 3.2 fixes all three bugs.

The impact is currently unclear, but miscalculations in cryptographic functions should generally be considered security issues. I'd like to encourage cryptographers to try to analyze whether these bugs can lead to cryptographic breaks.

I have published a code example on how to fuzz elliptic curve multiplications. It can compare the output of OpenSSL with either Nettle or NSS. It currently works only with prime field curves, but it can probably be adapted to other curves.

P-256 bug:
Mailing list post with code sample
Commit / fix for P-256 bug

P-384 bug:
Mailing list post with code sample
Commit / fix for P-384 bug

Nettle 3.2 release notes