miscomputation of ECP::ScalarMultiply() using 5.6.4-9

[Mark Esler]

This issue was reported to the Security team over email and originally posted to https://github.com/weidai11/cryptopp/issues/1269

> I typically never use Crypto++, but I had to yesterday, and I then experienced a strange behavior that I felt I had to somehow report. Having read your [security policy](https://github.com/weidai11/cryptopp/security/policy), I decided that the appropriate course of action was to open an issue here.
>
> ### Background
>
> I used the default Crypto++ package provided by [Ubuntu 20.04.6 LTS (Focal Fossa)](https://releases.ubuntu.com/focal/) running on a computer with a 64-bit Intel CPU.
>
> More specifically, Crypto++ was installed on the machine via `apt` as follows:
>
> ```
> $ sudo apt update && sudo apt upgrade
> (..)
> $ sudo apt install libcrypto++-dev
> (..)
> libcrypto++-dev is already the newest version (5.6.4-9build1).
> ```
>
> The package version 5.6.4 leads me to think that it installs the (old) v5.6.4 release of Crypto++ from [this GitHub repository](https://github.com/weidai11/cryptopp), although it is not entirely clear from the metadata for the package.
> ### The issue
>
> When using Crypto++ as provided by the above package, it seems `ECP::ScalarMultiply()` may miscompute. Specifically, it seems to miscompute if the scalar is on [2, 32), i.e. of bit length less than or equal to 5. This would appear to be related to the difference in behavior induced by the branching on [this line](https://github.com/weidai11/cryptopp/blob/782057f5f18fbdad2bd2b291fb1ec558a8ab8225/ecp.cpp#L387) in the source code for Crypto++.
>
> To exemplify, I obtain the below result:
>
> ```
> Q1.x = 33306590390930540189669946118275349837741820479536661896440526521039379673897.
> Q1.y = 51671163428562425671907826722938384860953039014408454870632045822359784767650.
>
> >> Q1 is *NOT* as expected.
> >> Q1 is *NOT* on E.
>
> Q2.x = 33898744863829483362161709717034397769364896634277352921440311777960767108802.
> Q2.y = 23483645583050324501141112153509270605088748325709409281081826839369927198174.
>
> >> Q2 is as expected.
> >> Q2 is on E.
>
> >> T1 is equal to T2 for d = 1.
> >> T1 is *NOT* equal to T2 for d = 2.
> >> T1 is *NOT* equal to T2 for d = 3.
> >> T1 is *NOT* equal to T2 for d = 4.
> >> T1 is *NOT* equal to T2 for d = 5.
> >> T1 is *NOT* equal to T2 for d = 6.
> >> T1 is *NOT* equal to T2 for d = 7.
> >> T1 is *NOT* equal to T2 for d = 8.
> >> T1 is *NOT* equal to T2 for d = 9.
> >> T1 is *NOT* equal to T2 for d = 10.
> >> T1 is *NOT* equal to T2 for d = 11.
> >> T1 is *NOT* equal to T2 for d = 12.
> >> T1 is *NOT* equal to T2 for d = 13.
> >> T1 is *NOT* equal to T2 for d = 14.
> >> T1 is *NOT* equal to T2 for d = 15.
> >> T1 is *NOT* equal to T2 for d = 16.
> >> T1 is *NOT* equal to T2 for d = 17.
> >> T1 is *NOT* equal to T2 for d = 18.
> >> T1 is *NOT* equal to T2 for d = 19.
> >> T1 is *NOT* equal to T2 for d = 20.
> >> T1 is *NOT* equal to T2 for d = 21.
> >> T1 is *NOT* equal to T2 for d = 22.
> >> T1 is *NOT* equal to T2 for d = 23.
> >> T1 is *NOT* equal to T2 for d = 24.
> >> T1 is *NOT* equal to T2 for d = 25.
> >> T1 is *NOT* equal to T2 for d = 26.
> >> T1 is *NOT* equal to T2 for d = 27.
> >> T1 is *NOT* equal to T2 for d = 28.
> >> T1 is *NOT* equal to T2 for d = 29.
> >> T1 is *NOT* equal to T2 for d = 30.
> >> T1 is *NOT* equal to T2 for d = 31.
> >> T1 is equal to T2 for d = 32.
> >> T1 is equal to T2 for d = 33.
> >> T1 is equal to T2 for d = 34.
>
> >> T1 is equal to T2 for d = 4838386420901692723041175965060989195194280026704430236348655611663611748562.
> ```
>
> The source code in `main.cpp` is as follows:
>
> ```c++
> #include <iostream>
>
> using std::cout;
> using std::endl;
>
> #include "cryptopp/ecp.h"
>
> using CryptoPP::Integer;
> using CryptoPP::ECPPoint;
> using CryptoPP::ECP;
>
> int main() {
> const Integer p("68563679381982577622739666783671143994995151030968464702867583019834252739659");
>
> const Integer a("38340410290425650555291103033366954895786709470949111520317038818740559472271");
> const Integer b("61862461829344747002414367293848044144907923329445405487651446734863421214369");
>
> const ECP E = ECP(p, a, b);
>
> const Integer q("17140919845495644405684916695917785998672015991198074381415721324869292128811");
>
> /* Note: The curve E has order r = 2^2 * q where q is prime. */
>
> const Integer x("49783729659862894673603312242618433622969024866008586212478256625771510792958");
> const Integer y("18916745246771588809190938755787142016135405279727789454979776401687407939506");
>
> const ECPPoint P = ECP::Point(x, y);
>
> /* Note: The point P is on E and of order r so it generates all of E. */
>
> /* Note: Let us now compute the point Q = [4] P of prime order q. */
>
> const Integer expected_Qx("33898744863829483362161709717034397769364896634277352921440311777960767108802");
> const Integer expected_Qy("23483645583050324501141112153509270605088748325709409281081826839369927198174");
>
> const Integer cofactor(4);
>
> const ECPPoint Q1 = E.ScalarMultiply(P, cofactor);
>
> std::cout << "Q1.x = " << Q1.x << std::endl;
> std::cout << "Q1.y = " << Q1.y << std::endl << std::endl;
>
> if ((expected_Qx == Q1.x) && (expected_Qy == Q1.y)) {
> std::cout << ">> Q1 is as expected." << std::endl;
> } else {
> std::cout << ">> Q1 is *NOT* as expected." << std::endl;
> }
>
> if (E.VerifyPoint(Q1)) {
> std::cout << ">> Q1 is on E." << std::endl;
> } else {
> std::cout << ">> Q1 is *NOT* on E." << std::endl;
> }
>
> std::cout << std::endl;
>
> /* Let us compute Q by a different function call and compare: */
>
> ECPPoint Q2;
> E.SimultaneousMultiply(&Q2, P, &cofactor, 1);
>
> std::cout << "Q2.x = " << Q2.x << std::endl;
> std::cout << "Q2.y = " << Q2.y << std::endl << std::endl;
>
> if ((expected_Qx == Q2.x) && (expected_Qy == Q2.y)) {
> std::cout << ">> Q2 is as expected." << std::endl;
> } else {
> std::cout << ">> Q2 is *NOT* as expected." << std::endl;
> }
>
> if (E.VerifyPoint(Q2)) {
> std::cout << ">> Q2 is on E." << std::endl;
> } else {
> std::cout << ">> Q2 is *NOT* on E." << std::endl;
> }
>
> std::cout << std::endl;
>
> /* It seems Crypto++ treats the case where the scalar is of bit length <= 5
> * differently from the case where it is of longer length, see:
> *
> * https://github.com/weidai11/cryptopp/blob/782057f5f18fbdad2bd2b291fb1ec558a8ab8225/ecp.cpp#L387
> *
> * Could this be the issue? Let us perform the below tests: */
>
> for (unsigned int i = 1; i <= 34; i++) {
> Integer d(i);
>
> /* Compute T = [d] P by two different function calls and compare: */
>
> const ECPPoint T1 = E.ScalarMultiply(P, d);
>
> ECPPoint T2;
> E.SimultaneousMultiply(&T2, P, &d, 1);
>
> if (T1 == T2) {
> std::cout << ">> T1 is equal to T2 for d = " << d << std::endl;
> } else {
> std::cout << ">> T1 is *NOT* equal to T2 for d = " << d << std::endl;
> }
> }
>
> std::cout << std::endl;
>
> /* Let us also try with a large scalar uniformly sampled from [0, r). */
>
> {
> Integer d("4838386420901692723041175965060989195194280026704430236348655611663611748562");
>
> /* Compute T = [d] P by two different function calls and compare: */
>
> const ECPPoint T1 = E.ScalarMultiply(P, d);
>
> ECPPoint T2;
> E.SimultaneousMultiply(&T2, P, &d, 1);
>
> if (T1 == T2) {
> std::cout << ">> T1 is equal to T2 for d = " << d << std::endl;
> } else {
> std::cout << ">> T1 is *NOT* equal to T2 for d = " << d << std::endl;
> }
> }
> }
> ```
>
> To confirm that there was no issue with the specific Ubuntu installation, I setup a clean virtual Ubuntu 20.04.6 LTS machine and repeated the above steps. I was thus able to reproduce the erroneous behavior.
>
> To check whether this issue extends to other releases and architectures, I furthermore compiled `main.cpp` and ran the resulting executable under Ubuntu 22.04 LTS for ARM64 in a virtual machine. The correct expected output was then produced:
>
> ```
> $ g++ main.cpp -lcryptopp -o test
> $ ./test
> Q1.x = 33898744863829483362161709717034397769364896634277352921440311777960767108802.
> Q1.y = 23483645583050324501141112153509270605088748325709409281081826839369927198174.
>
> >> Q1 is as expected.
> >> Q1 is on E.
>
> Q2.x = 33898744863829483362161709717034397769364896634277352921440311777960767108802.
> Q2.y = 23483645583050324501141112153509270605088748325709409281081826839369927198174.
>
> >> Q2 is as expected.
> >> Q2 is on E.
>
> >> T1 is equal to T2 for d = 1.
> >> T1 is equal to T2 for d = 2.
> >> T1 is equal to T2 for d = 3.
> >> T1 is equal to T2 for d = 4.
> >> T1 is equal to T2 for d = 5.
> >> T1 is equal to T2 for d = 6.
> >> T1 is equal to T2 for d = 7.
> >> T1 is equal to T2 for d = 8.
> >> T1 is equal to T2 for d = 9.
> >> T1 is equal to T2 for d = 10.
> >> T1 is equal to T2 for d = 11.
> >> T1 is equal to T2 for d = 12.
> >> T1 is equal to T2 for d = 13.
> >> T1 is equal to T2 for d = 14.
> >> T1 is equal to T2 for d = 15.
> >> T1 is equal to T2 for d = 16.
> >> T1 is equal to T2 for d = 17.
> >> T1 is equal to T2 for d = 18.
> >> T1 is equal to T2 for d = 19.
> >> T1 is equal to T2 for d = 20.
> >> T1 is equal to T2 for d = 21.
> >> T1 is equal to T2 for d = 22.
> >> T1 is equal to T2 for d = 23.
> >> T1 is equal to T2 for d = 24.
> >> T1 is equal to T2 for d = 25.
> >> T1 is equal to T2 for d = 26.
> >> T1 is equal to T2 for d = 27.
> >> T1 is equal to T2 for d = 28.
> >> T1 is equal to T2 for d = 29.
> >> T1 is equal to T2 for d = 30.
> >> T1 is equal to T2 for d = 31.
> >> T1 is equal to T2 for d = 32.
> >> T1 is equal to T2 for d = 33.
> >> T1 is equal to T2 for d = 34.
>
> >> T1 is equal to T2 for d = 4838386420901692723041175965060989195194280026704430236348655611663611748562.
> ```
>
> To better try to understand what is going on, I [downloaded Crypto++ releases](https://github.com/weidai11/cryptopp/releases) from [this GitHub repository](https://github.com/weidai11/cryptopp), and proceeded to compile and link against them manually. I did this on the Ubuntu 20.04.6 LTS machine that produced the erroneous output, in the hope of thus being able to reproduce the error. But as it turned out, I could not reproduce the error in this way. Instead, the correct expected output was produced for all of the GitHub releases that I have tried thus far (namely v5.6.3, v5.6.4, v5.6.5, v6.0.0, v6.1.0, v7.0.0, v8.0.0, v8.2.0, v8.3.0, v8.4.0 and v8.9.0) — but not for Crypto++ as provided by the Ubuntu package repository.
>
> I did expect to be able to reproduce the error at least for v5.6.4, if this is the version from which the Ubuntu package was built. When I could not, I computed a diff between the header files installed by the Ubuntu package and the header files for the v5.6.4 release from this GitHub repository, and there appears to be some differences.
>
> So in conclusion, I am not entirely sure which version of Crypto++ is in the Ubuntu repository, and how it was compiled, tested, etc. But it seems that it is not working properly? I find this all a bit surprising. Could someone else please confirm this? Or let me know if I am making some mistake in my code, given that I usually never use Crypto++. Assuming I did not make a mistake and that this really is an issue, further actions may then of course be necessary.
>
> (On a side note, I would expect there to be unit tests that cover the small scalar case, since the code branches depending on the bit length of the scalar. Assuming that this is the case, and that these tests were run, it seems strange to me that this issue would not have been detected when the Ubuntu package was built.)

[Mark Esler (eslerm)]

With fresh amd64 VMs using the latest Ubuntu point releases, I was able to reproduce your report on Ubuntu Focal 20.04.06 (`libcrypto++` version 5.6.4-9build1). Both Bionic 18.04.06 (`libcrypto++` version 5.6.4-8) and Jammy 22.04.04 (`libcrypto++` version 8.6.0-2ubuntu1) had the expected result.

Also on Ubuntu Focal 20.04.04, I installed [Debian's `libcrypto++` version 5.6.4-9](https://snapshot.debian.org/package/libcrypto++/5.6.4-9/) directly. This version also has the error. Debian's `libcrypto++` version immediately prior [5.6.4-8](https://snapshot.debian.org/package/libcrypto++/5.6.4-8/) is not affected. The Debian version afterwards, [5.6.4-10](https://snapshot.debian.org/package/libcrypto++/5.6.4-10/), is affected, but [6.1.0-1](https://snapshot.debian.org/package/libcrypto++/6.1.0-1/) is not.

So, the issue is only known to affect packages based on Debian `libcrypto++` 5.6.4-9 and 5.6.4-10.

[Mark Esler (eslerm)]

Debian `libcrypto++` 5.6.4-9 introduced a security patch for CVE-2019-14318.

According to a post in 2019 , https://github.com/weidai11/cryptopp/issues/869, the CVE-2019-14318 patch for 5.6.4 was incomplete. A comment in a later 2020 issue mentions that the 2019 8.3 patch was broken: https://github.com/weidai11/cryptopp/issues/994#issuecomment-752399981

Debian's 5.6.4-9 uses the 2019 patch which likely contains a regression. It does not appear that a fully working fix for CVE-2019-14318 in 5.6.4 was made.

[Mark Esler (eslerm)]

There is a strong chance that https://bugs.launchpad.net/ubuntu/+source/libcrypto++/+bug/1893934 is related to the incomplete CVE-2019-14318 patch regression.

I plan to propose an SRU to effectively downgrade this regressed package to 5.6.4-8.

Please see https://github.com/weidai11/cryptopp/issues/1269 for more details.