EC2N::DecodePoint can crash if exponents are not in descending order

[roadicing]

Hi, recently I found a security issue in the Crypto++ library that would cause a segmentation fault when parsing DER public key files of the F(2^m) class curves, an attacker could potentially craft a malformed DER public key file, and any user or server attempting to read this public key file in processes such as ECDSA may be susceptible to a DOS attack.

Issue

The main reason of this issue is that when parsing the DER public key file of the F(2^m) class curve (EC2N::DecodePoint), there is no check that the degree of each term in the polynomial is strictly decreasing.

For example, for curve sect193r1, it uses polynomial f(x) = x^193 + x^15 + 1, then under normal circumstances, DER public key file would store their exponents in the following sequential order in ASN.1 format:

35:d=5  hl=2 l=   2 prim: INTEGER           :C1 
39:d=5  hl=2 l=   9 prim: OBJECT            :tpBasis 
50:d=5  hl=2 l=   1 prim: INTEGER           :0F

The above snippet is taken from a regular sect193r1 public key file. However, if we reverse the order of the exponents, for instance, if we swap the positions of C1 and 0F, and repackage it into a DER file, then any attempt to read and parse this DER file in Crypto++ will trigger a segmentation fault immediately.

To figure out the exact location, I debugged it using gdb, and here is the result:

Program terminated with signal SIGSEGV, Segmentation fault.
#0  0x00007fb8458e34fc in CryptoPP::GF2NT::Reduced(CryptoPP::PolynomialMod2 const&) const ()
   from /usr/lib/x86_64-linux-gnu/libcrypto++.so.8
(gdb) bt
#0  0x00007fb8458e34fc in CryptoPP::GF2NT::Reduced(CryptoPP::PolynomialMod2 const&) const ()
   from /usr/lib/x86_64-linux-gnu/libcrypto++.so.8
#1  0x00007fb8458e5440 in CryptoPP::GF2NT::Square(CryptoPP::PolynomialMod2 const&) const ()
   from /usr/lib/x86_64-linux-gnu/libcrypto++.so.8
#2  0x00007fb8458ad844 in CryptoPP::EC2N::DecodePoint(CryptoPP::EC2NPoint&, CryptoPP::BufferedTransformation&, unsigned long) const () from /usr/lib/x86_64-linux-gnu/libcrypto++.so.8
#3  0x00007fb8458ad696 in CryptoPP::EC2N::DecodePoint(CryptoPP::EC2NPoint&, unsigned char const*, unsigned long) const ()
   from /usr/lib/x86_64-linux-gnu/libcrypto++.so.8
#4  0x00007fb8458ae360 in CryptoPP::EC2N::BERDecodePoint(CryptoPP::BufferedTransformation&) const ()
   from /usr/lib/x86_64-linux-gnu/libcrypto++.so.8
#5  0x00007fb84587b542 in CryptoPP::DL_GroupParameters_EC<CryptoPP::EC2N>::BERDecode(CryptoPP::BufferedTransformation&) ()
   from /usr/lib/x86_64-linux-gnu/libcrypto++.so.8
#6  0x00007fb84587b9fd in CryptoPP::DL_KeyImpl<CryptoPP::X509PublicKey, CryptoPP::DL_GroupParameters_EC<CryptoPP::EC2N>, CryptoPP::OID>::BERDecodeAlgorithmParameters(CryptoPP::BufferedTransformation&) () from /usr/lib/x86_64-linux-gnu/libcrypto++.so.8
#7  0x00007fb845816488 in CryptoPP::X509PublicKey::BERDecode(CryptoPP::BufferedTransformation&) ()
   from /usr/lib/x86_64-linux-gnu/libcrypto++.so.8
#8  0x000055a6c6c1fd92 in CryptoPP::ASN1CryptoMaterial<CryptoPP::PublicKey>::Load (this=0x7ffebe95d0e8, bt=...)
    at /usr/include/crypto++/asn.h:697
#9  0x000055a6c6c1d453 in main () at poc.cpp:14

From the debugging results of gdb, we can see that the function that actually triggers the problem is GF2NT::Reduced, since this function will only be called when the point is in the form of compression encoding, we need to ensure that the points in the constructed DER file are in compressed form (start with 02 or 03).

Fix

To fix this issue, the simplest method is to check whether the coefficients of the polynomial satisfy strict decreasing, which should at least close the entry point that triggers this issue.

However, based on the gdb debugging results, it seems that the issue ultimately arises in . Therefore, fixing the actual cause of the segmentation fault from this function is also a feasible option, but it is still advisable to check whether the coefficients of the polynomial meet our requirements.

Update

The current fix of this issue can be seen here, thanks for @noloader 's help.

[noloader]

Thanks @roadicing.

I got to thinking about things... I don't think we should try to fix things for the user, like sorting exponents in descending order. The problem is, we can 'fix' the PolynomialMod2 objects, but then there's GP2NT, GP2NPP and friends. Also see gf2n.cpp:

GF2NT::GF2NT(unsigned int c0, unsigned int c1, unsigned int c2)
    : GF2NP(PolynomialMod2::Trinomial(c0, c1, c2))
    , t0(c0), t1(c1)
    , result((word)0, m)
{
    // Asserts and checks due to Bing Shi
    CRYPTOPP_ASSERT(c0 > c1 && c1 > c2 && c2==0);

    // The test is relaxed because of ECIES<EC2N>. The high order exponent is t0,
    // but the other exponents are not in descending order.
    if (c1 > c0 || c2 > c0)
        throw InvalidArgument("GF2NT: exponents must be in descending order");
}

What we added was a check to ensure other exponents were less that t0 since t0 drives the degree of the polynomial. If the check fails, then throw an exception. Also see Commit 641ae35258de and Commit 93208e83937a.

[roadicing]

Yes, and this should be sufficient to fix this issue, thank you for your assistance.