RSA signature verification with 1017 bit key crashes

[mneffgen]

The Reason is an insufficient buffer size created at pk_ops.cpp:

std::vector<uint8_t> PK_Ops::Encryption_with_EME::encrypt(std::span<const uint8_t> msg, RandomNumberGenerator& rng) {
   const size_t max_raw = max_ptext_input_bits();
   secure_vector<uint8_t> eme_output((max_raw + 7) / 8);  // insufficient size
   size_t written = m_eme->pad(eme_output, msg, max_raw, rng);
   return raw_encrypt(std::span{eme_output}.first(written), rng);
}

The check BOTAN_ASSERT_NOMSG(output.size() >= input.size()); in EME_Raw::pad() fails.

Changing the buffer size to (max_raw + 7) / 8 + 1 fixes the problem.

Probably the error occurs for all keys with size % 8 = 1.
We use various and exotic key sizes for testing purposes.

[randombit]

Can you post a complete test case? Checking a set of vectors generated by OpenSSL with keys in range 1024..1056 I cannot replicate this.

[mneffgen]

Here is our example with the 1017 bit key:

// 1017 bit key
const std::vector<uint8_t> modulus = {
    0x01, 0x5f, 0xe1, 0x78, 0x87, 0x4e, 0xa5, 0xaa, 0x90, 0x58, 0x5a, 0x9d, 0x47, 0x16, 0x4a, 0x7a, 0x90, 0x03, 0xc8, 0x65, 0x32, 0x00, 0x81, 0x33, 0x0e, 0xec, 0x7d, 0x96, 0x94, 0xac, 0x82, 0xe1,
    0x39, 0x28, 0x13, 0xf8, 0x43, 0x72, 0x61, 0xe4, 0x0f, 0x23, 0x7f, 0x49, 0x28, 0x2d, 0x9f, 0x8b, 0x94, 0xf1, 0x81, 0x37, 0x86, 0xf1, 0xcf, 0x67, 0x70, 0xab, 0xf5, 0xb5, 0x01, 0xe0, 0x1b, 0x2c,
    0x8f, 0xbd, 0xdb, 0x28, 0x2e, 0x75, 0x5f, 0x67, 0x84, 0x86, 0x22, 0x1b, 0x86, 0x0b, 0xa0, 0x8d, 0x02, 0x50, 0x3f, 0x35, 0xcb, 0x52, 0x6d, 0xa5, 0xd5, 0x3c, 0x9f, 0xb3, 0x47, 0xb0, 0x31, 0x33,
    0x94, 0xac, 0xcc, 0xa2, 0x9b, 0x49, 0xff, 0x0c, 0x90, 0x1b, 0xbe, 0xb2, 0x67, 0xbc, 0x34, 0x02, 0x01, 0x85, 0x95, 0x73, 0x34, 0x8e, 0xa0, 0x0b, 0xec, 0x56, 0x5f, 0x93, 0xe6, 0x7b, 0x07, 0x0d
};

const std::vector<uint8_t> publicExponent = {
    0x01, 0x00, 0x01
};
const std::vector<uint8_t> dsi = {
 0x66,0xCA,0xC5,0x69,0x95,0x46,0xE6,0x68,0xD2,0x05,0x11,0x7E,0x42,0x2F,0x21,0x03,
 0x53,0x97,0x33,0x26,0x72,0x60,0x74,0xC2,0xEF,0xFE,0x6E,0x87,0x46,0x39,0xE0,0x51,
 0xD3,0x5B,0x6D,0xFC,0xA1,0xA1,0x5F,0xB0,0x1D,0x9B,0xF6,0x7F,0x39,0x2A,0xA7,0x57,
 0x23,0x65,0x0D,0xE6,0x6A,0x69,0xFE,0x36,0xD0,0xED,0xBE,0xFC,0x3B,0xF4,0x52,0x53,
 0xD8,0x2B,0x63,0xF0,0x6E,0xF6,0xE5,0x4E,0xEF,0x8A,0x77,0xA0,0x55,0xD7,0x42,0xEA,
 0x20,0x88,0xCB,0x61,0x04,0xAC,0xF8,0x49,0xEF,0xD7,0x99,0x5B,0x8C,0x83,0x17,0x65,
 0xD6,0xA7,0x4B,0xB9,0x3B,0xDA,0x8D,0x79,0x5B,0x6D,0x59,0xE4,0xC3,0x7D,0x52,0xE8,
 0xAB,0x6D,0x2D,0x98,0x73,0xB6,0x76,0x46,0x18,0x65,0xB0,0x5A,0x4F,0xEE,0xBC
};

const std::vector<uint8_t> signature = {
        0x01,0x41,0x38,0x62,0x11,0xF7,0xF5,0x81,0xBD,0x81,0x8B,0xBE,0x22,0x81,0xF4,0xD0,
        0xCD,0x4F,0x1C,0x27,0x6F,0x68,0x83,0x9D,0x10,0x6F,0x3C,0x76,0xC6,0x5F,0xFD,0x4F,
        0x04,0xB6,0x14,0x22,0xA9,0x3A,0x22,0x33,0x21,0xFF,0xAE,0xA0,0x06,0x2D,0x1B,0x7A,
        0xA8,0xF2,0xBC,0xA6,0x2E,0xF9,0x64,0x6B,0x8B,0xD1,0x0D,0x93,0x40,0xF6,0x56,0x31,
        0xA1,0x65,0xD4,0xDC,0x0E,0x75,0xBA,0xBC,0x64,0x88,0x32,0x18,0x05,0x65,0x51,0x75,
        0xFB,0x5F,0x36,0xB2,0x41,0x7A,0x4A,0x97,0xF3,0x53,0xA0,0xCF,0x43,0xE0,0x32,0x39,
        0xA4,0x30,0x69,0xC8,0x39,0xAE,0xE1,0x99,0x91,0xBB,0xEE,0x2E,0x0F,0x9B,0xED,0xF8,
        0x08,0x70,0x97,0xC1,0x48,0xFA,0x9A,0xE0,0x88,0xEA,0x57,0xAC,0x88,0x44,0x25,0x99
};
const Botan::RSA_PublicKey botanKey(Botan::BigInt::from_bytes(modulus), Botan::BigInt::from_bytes(publicExponent));
Botan::AutoSeeded_RNG rng;
Botan::PK_Encryptor_EME encoder(botanKey, rng, std::string("Raw"));
const std::vector<uint8_t> receivedDSI = encoder.encrypt(signature, rng);

[randombit]

Use PK_Verifier to verify signatures, the encryption == verification thing is true for (unpadded) RSA on a mathematical level but it is not treated the same in practice.

Also do note that we already support ISO 9796 signature verification: either of these work already

   Botan::PK_Verifier ver(botanKey, "Raw");
   printf("accept = %d\n", ver.verify_message(dsi, signature));

   Botan::PK_Verifier iso_ver(botanKey, "ISO_9796_DS2(SHA-256,imp,32)");
   printf("accept = %d\n", iso_ver.verify_message({}, signature));

[mneffgen]

We need it for testing purposes. That is why we use the low level algorithm and unusual key sizes.

[randombit]

That’s fine. But you can’t expect to use PK_Encryptor for this purpose, it places limits on the bitlength of encrypted inputs which is needed for other padding schemes to work correctly. #4467 changes this so that the error is Invalid_Argument instead of Internal_Error so it’s more clear what is happening.