7.14 Securely Signing and Encrypting with RSA

7.14.1 Problem

You need to both sign and encrypt data using RSA.

7.14.2 Solution

Sign the concatenation of the public key of the message recipient and the data you actually wish to sign. Then concatenate the signature to the plaintext, and encrypt everything, in multiple messages if necessary.

7.14.3 Discussion

Naïve implementations where a message is both signed and encrypted with public key cryptography tend to be insecure. Simply signing data with a private key and then encrypting the data with a public key isn't secure, even if the signature is part of the data you encrypt. Such a scheme is susceptible to an attack called surreptitious forwarding. For example, suppose that there are two servers, S1 and S2. The client C signs a message and encrypts it with S1's public key. Once S1 decrypts the message, it can reencrypt it with S2's public key and make it look as if the message came from C.

In a connection-oriented protocol, it could allow a compromised S1 to replay a key transport between C and S1 to a second server S2. That is, if an attacker compromises S1, he may be able to imitate C to S2. In a document-based environment such as an electronic mail system, if Alice sends email to Bob, Bob can forward it to Charlie, making it look as if it came from Alice instead of Bob. For example, if Alice sends important corporate secrets to Bob, who also works for the company, Bob can send the secrets to the competition and make it look as if it came from Alice. When the CEO finds out, it will appear that Alice, not Bob, is responsible.

There are several strategies for fixing this problem. However, encrypting and then signing does not fix the problem. In fact, it makes the system far less secure. A secure solution to this problem is to concatenate the recipient's public key with the message, and sign that. The recipient can then easily determine that he or she was indeed the intended recipient.

One issue with this solution is how to represent the public key. The important thing is to be consistent. If your public keys are stored as X.509 certificates (see Chapter 10 for more on these), you can include the entire certificate when you sign. Otherwise, you can simply represent the public modulus and exponent as a single binary string (the DER-encoding of the X.509 certificate) and include that string when you sign.

The other issue is that RSA operations such as encryption tend to work on small messages. A digital signature of a message will often be too large to encrypt using public key encryption. Plus, you will need to encrypt your actual message as well! One way to solve this problem is to perform multiple public key encryptions. For example, let's say you have a 2,048-bit modulus, and the recipient has a 1,024-bit modulus. You will be encrypting a 16-byte secret and your signature, where that signature will be 256 bytes, for a total of 272 bytes. The output of encryption to the 1,024-bit modulus is 128 bytes, but the input can only be 86 bytes, because of the need for padding. Therefore, we'd need four encryption operations to encrypt the entire 272 bytes.

In many client-server architectures where the client initiates a connection, the client won't have the server's public key in advance. In such a case, the server will often send a copy of its public key at its first opportunity (or a digital certificate containing the public key). In this case, the client can't assume that public key is valid; there's nothing to distinguish it from an attacker's public key! Therefore, the key needs to be validated using a trusted third party before the client trusts that the party on the other end is really the intended server. See Recipe 7.1.

Here is an example of generating, signing, and encrypting a 16-byte secret in a secure manner using OpenSSL, given a private key for signing and a public key for the recipient. The secret is placed in the buffer pointed to by the final argument, which must be 16 bytes. The encrypted result is placed in the third argument, which must be big enough to hold the modulus for the public key.

Note that we represent the public key of the recipient as the binary representation of the modulus concatenated with the binary representation of the exponent. If you are using any sort of high-level key storage format such as an X.509 certificate, it makes sense to use the canonical representation of that format instead. See Recipe 7.16 and Recipe 7.17 for information on converting common formats to a binary string.

#include <openssl/sha.h>
#include <openssl/rsa.h>
#include <openssl/objects.h>
#include <openssl/rand.h>
#include <string.h>
   
#define MIN(x,y) ((x) > (y) ? (y) : (x))
   
unsigned char *generate_and_package_128_bit_secret(RSA *recip_pub_key,
                      RSA *signers_key, unsigned char *sec, unsigned int *olen) {
  unsigned char *tmp = 0, *to_encrypt = 0, *sig = 0, *out = 0, *p, *ptr;
  unsigned int  len, ignored, b_per_ct;
  int           bytes_remaining; /* MUST NOT BE UNSIGNED. */
  unsigned char hash[20];
   
  /* Generate the secret. */
  if (!RAND_bytes(sec, 16)) return 0;
   
  /* Now we need to sign the public key and the secret both. 
   * Copy the secret into tmp, then the public key and the exponent.
   */
  len = 16 + RSA_size(recip_pub_key) + BN_num_bytes(recip_pub_key->e);
  if (!(tmp = (unsigned char *)malloc(len))) return 0;
  memcpy(tmp, sec, 16);
  if (!BN_bn2bin(recip_pub_key->n, tmp + 16)) goto err;
  if (!BN_bn2bin(recip_pub_key->e, tmp + 16 + RSA_size(recip_pub_key))) goto err;
  
  /* Now sign tmp (the hash of it), again mallocing space for the signature. */
  if (!(sig = (unsigned char *)malloc(BN_num_bytes(signers_key->n)))) goto err;
  if (!SHA1(tmp, len, hash)) goto err;
  if (!RSA_sign(NID_sha1, hash, 20, sig, &ignored, signers_key)) goto err;
   
  /* How many bytes we can encrypt each time, limited by the modulus size
   * and the padding requirements.
   */
  b_per_ct = RSA_size(recip_pub_key) - (2 * 20 + 2);
  
  if (!(to_encrypt = (unsigned char *)malloc(16 + RSA_size(signers_key))))
    goto err;
   
  /* The calculation before the mul is the number of encryptions we're
   * going to make.  After the mul is the output length of each
   * encryption.
   */
  *olen = ((16 + RSA_size(signers_key) + b_per_ct - 1) / b_per_ct) *
          RSA_size(recip_pub_key);
  if (!(out = (unsigned char *)malloc(*olen))) goto err;
   
  /* Copy the data to encrypt into a single buffer. */
  ptr = to_encrypt;
  bytes_remaining = 16 + RSA_size(signers_key);
  memcpy(to_encrypt, sec, 16);
  memcpy(to_encrypt + 16, sig, RSA_size(signers_key));
  p = out;
   
  while (bytes_remaining > 0) {
    /* encrypt b_per_ct bytes up until the last loop, where it may be fewer. */
    if (!RSA_public_encrypt(MIN(bytes_remaining,b_per_ct), ptr, p,
                           recip_pub_key, RSA_PKCS1_OAEP_PADDING)) {
        free(out);
        out = 0;
        goto err;
    }
    bytes_remaining -= b_per_ct;
    ptr += b_per_ct;
    /* Remember, output is larger than the input. */
    p += RSA_size(recip_pub_key);
  }
   
err:
  if (sig) free(sig);
  if (tmp) free(tmp);
  if (to_encrypt) free(to_encrypt);
  return out;
}

Once the message generated by this function is received on the server side, the following code will validate the signature on the message and retrieve the secret:

#include <openssl/sha.h>
#include <openssl/rsa.h>
#include <openssl/objects.h>
#include <openssl/rand.h>
#include <string.h>
   
#define MIN(x,y) ((x) > (y) ? (y) : (x))
   
/* recip_key must contain both the public and private key. */
int validate_and_retreive_secret(RSA *recip_key, RSA *signers_pub_key,
                                 unsigned char *encr, unsigned int inlen,
                                 unsigned char *secret) {
  int           result = 0;
  BN_CTX        *tctx;
  unsigned int  ctlen, stlen, i, l;
  unsigned char *decrypt, *signedtext, *p, hash[20];
   
  if (inlen % RSA_size(recip_key)) return 0;
  if (!(p = decrypt = (unsigned char *)malloc(inlen))) return 0;
  if (!(tctx = BN_CTX_new(  ))) {
    free(decrypt);
    return 0;
  }
  RSA_blinding_on(recip_key, tctx);
  for (ctlen = i = 0;  i < inlen / RSA_size(recip_key);  i++) {
    if (!(l = RSA_private_decrypt(RSA_size(recip_key), encr, p, recip_key,
                                  RSA_PKCS1_OAEP_PADDING))) goto err;
    encr += RSA_size(recip_key);
    p += l;
    ctlen += l;
  }
  if (ctlen != 16 + RSA_size(signers_pub_key)) goto err;
  stlen = 16 + BN_num_bytes(recip_key->n) + BN_num_bytes(recip_key->e);
  if (!(signedtext = (unsigned char *)malloc(stlen))) goto err;
  memcpy(signedtext, decrypt, 16);
  if (!BN_bn2bin(recip_key->n, signedtext + 16)) goto err;
  if (!BN_bn2bin(recip_key->e, signedtext + 16 + RSA_size(recip_key))) goto err;
  if (!SHA1(signedtext, stlen, hash)) goto err;
  if (!RSA_verify(NID_sha1, hash, 20, decrypt + 16, RSA_size(signers_pub_key),
                  signers_pub_key)) goto err;
  memcpy(secret, decrypt, 16);
  result = 1;
   
err:
  RSA_blinding_off(recip_key);
  BN_CTX_free(tctx);
  free(decrypt);
  if (signedtext) free(signedtext);
  return result;
}

7.14.4 See Also

Recipe 7.1, Recipe 7.16, Recipe 7.17