ECP::ScalarMultiply() may seemingly miscompute for small scalars when using Ubuntu 20.04.6 LTS on 64-bit Intel CPUs

[ekera]

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, 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) 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, 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 in the source code for Crypto++.

To exemplify, I obtain the below result:

$ g++ main.cpp -lcryptopp -o test
$ ./test
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:

#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 from this GitHub repository, 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.)

[eslerm]

Thank you @ekera 🙏

I have filed Launchpad Bug against the libcrypto++ on Focal: https://bugs.launchpad.net/ubuntu/+source/libcrypto++/+bug/2060564

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 directly. This version also has the error. Debian's libcrypto++ version immediately prior 5.6.4-8 is not affected. The Debian version afterwards, 5.6.4-10, is affected, but 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.

[eslerm]

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

According to a post in 2019 , #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: #994 (comment)

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.

[eslerm]

On Debian's side, only unstable (Sid) was affected as far as I am aware. Buster received 5.6.4-8, which is the version immediately prior to applying the incomplete patch.

https://security-tracker.debian.org/tracker/CVE-2019-14318
https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=934326

[eslerm]

@ekera I will request a SRU for libcrypto++ to effectively roll it back to 5.6.4-8 in Focal. This will mean that libcrypto++ will remain vulnerable to CVE-2019-14318 in Ubuntu Focal and Debian Buster unless upstream plans to provide a backport.

@weidai1 could you please comment on if a backport security patch will be released. It seems more than reasonable that a complicated backport fix would not be supported.

[ekera]

@eslerm Thank you for taking this issue seriously and for requesting a SRU. You probably meant to ping @weidai11.

[eslerm]

A regression fix was proposed last week. I'll shepherd it through and report back when the fix is live.

https://bugs.launchpad.net/ubuntu/+source/libcrypto++/+bug/2064751