CODEWITHSUNDEEP
clinuxencryptionopensslrsa
Ulrik
Ulrik

Reputation: 1141

Possible bug in RSA_private_encrypt

In the following example, we use an RSA 256-bit private key to encrypt a 32-byte message without padding and store the result in the same memory block.

#include <openssl/ssl.h>
unsigned char    err[256],
                 msg[] = "This is a message of some sort.",
                 key[] = "-----BEGIN RSA PRIVATE KEY-----\n"\
"MIGrAgEAAiEA6sZFpHqqFkpskc2GNMl6RHdiEuOqlX3LcW1TnYVgQFECAwEAAQIh\n"\
"AKqoe8FHJVJUwTzvMAo5FrU/t6Cc6GwYDELpU3xxs4nBAhEA+TwHM5ArwBgTtB2y\n"\
"AKlEKQIRAPElwlKWyde1KqHRCjOWX+kCEQDqWYZP9rUcp8cHKpDwTDiZAhBPldOd\n"\
"KDCzJRJN10yTm/RJAhANYsX4BteC/W7VRUjV5jSH\n"\
"-----END RSA PRIVATE KEY-----\n";
void main()
{
    //msg[0] = 255;
    if (RSA_private_encrypt(32, msg, msg,
    PEM_read_bio_RSAPrivateKey(BIO_new_mem_buf(key, -1), NULL, NULL, NULL),
    RSA_NO_PADDING) != 32)
    {
        ERR_load_crypto_strings();
        ERR_error_string(ERR_get_error(), err);
        puts(err);
    }
}

When we change the value of the 0-th message character by removing the comment, the encryption fails with message:

rsa routines:RSA_EAY_PRIVATE_ENCRYPT:data too large for modulus

Note that the very short RSA key and hard-coded message length are used just to demonstrate the problem. The key is generated using openssl binary, and the function fails with different sized keys as well (for 4096-bit key, the msg[0] = 192 causes failure).

It seems like the function is interpreting the beginning of the message as a length descriptor, even if RSA_NO_PADDING is explicitly stated. Is this a bug?

Upvotes: 2

Views: 864

Answers (1)

Artjom B.
Artjom B.

Reputation: 61952

In RSA, the modulus array and the data arrays are interpreted as large integers. The data integer must be smaller than the modulus integer. Otherwise, the encrypted value cannot be recovered.

I've decoded your private key. The first byte of your modulus is 0xEA. Which means that your data that you sign cannot begin with a byte larger than 0xEA (234). If you assign msg[0] = 235; it will lead to an error again.

That's where the padding comes it. The first byte of the padded data is usually 0x00 (or even 0x0001 depending on the padding scheme) which makes it impossible for the padded data to be numerically larger than the modulus.

So, no, you haven't found a bug. You're just using crypto wrong. I suggest that you use some higher-level API to sign messages.

Note that padding is crucial for RSA. Without it, there are ways to recover the plaintext or forge signatures. Please use OAEP for encryption and PSS for signing. Also, the key size is important. Nowadays, 4096-bit keys should be used. A 256-bit key is a toy size which can probably be broken by a smartphone nowadays.

Upvotes: 5

Related Questions