*** This bug is a security vulnerability *** Public security bug reported:
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.) ** Affects: libcrypto++ (Ubuntu) Importance: Undecided Status: New -- You received this bug notification because you are a member of Ubuntu Bugs, which is subscribed to Ubuntu. https://bugs.launchpad.net/bugs/2060564 Title: miscomputation of ECP::ScalarMultiply() using 5.6.4-9 To manage notifications about this bug go to: https://bugs.launchpad.net/ubuntu/+source/libcrypto++/+bug/2060564/+subscriptions -- ubuntu-bugs mailing list ubuntu-bugs@lists.ubuntu.com https://lists.ubuntu.com/mailman/listinfo/ubuntu-bugs
