Implement RSASSA-PKCS1-v1_5 as specified.

RFC 3447, section 8.2.2, steps 3 and 4 states that verifiers must encode
the DigestInfo struct and then compare the result against the public key
operation result. This implies that one and only one encoding is legal.

OpenSSL instead parses with crypto/asn1, then checks that the encoding
round-trips, and allows some variations for the parameter. Sufficient
laxness in this area can allow signature forgeries, as described in
https://www.imperialviolet.org/2014/09/26/pkcs1.html

Although there aren't known attacks against OpenSSL's current scheme,
this change makes OpenSSL implement the algorithm as specified. This
avoids the uncertainty and, more importantly, helps grow a healthy
ecosystem. Laxness beyond the spec, particularly in implementations
which enjoy wide use, risks harm to the ecosystem for all. A signature
producer which only tests against OpenSSL may not notice bugs and
accidentally become widely deployed. Thus implementations have a
responsibility to honor the specification as tightly as is practical.

In some cases, the damage is permanent and the spec deviation and
security risk becomes a tax all implementors must forever pay, but not
here. Both BoringSSL and Go successfully implemented and deployed
RSASSA-PKCS1-v1_5 as specified since their respective beginnings, so
this change should be compatible enough to pin down in future OpenSSL
releases.

See also https://tools.ietf.org/html/draft-thomson-postel-was-wrong-00

As a bonus, by not having to deal with sign/verify differences, this
version is also somewhat clearer. It also more consistently enforces
digest lengths in the verify_recover codepath. The NID_md5_sha1 codepath
wasn't quite doing this right.

Reviewed-by: Kurt Roeckx <kurt@roeckx.be>
Reviewed-by: Rich Salz <rsalz@openssl.org>

GH: #1474
(cherry picked from commit 608a026494c1e7a14f6d6cfcc5e4994fe2728836)

1 files changed, 173 insertions, 151 deletions

diff --git a/crypto/rsa/rsa_sign.c b/crypto/rsa/rsa_sign.c
index 8946e19c17..952d24fb8a 100644
--- a/crypto/rsa/rsa_sign.c
+++ b/crypto/rsa/rsa_sign.c
@@ -19,208 +19,230 @@
 /* Size of an SSL signature: MD5+SHA1 */
 #define SSL_SIG_LENGTH  36
 
-int RSA_sign(int type, const unsigned char *m, unsigned int m_len,
-             unsigned char *sigret, unsigned int *siglen, RSA *rsa)
+/*
+ * encode_pkcs1 encodes a DigestInfo prefix of hash |type| and digest |m|, as
+ * described in EMSA-PKCS1-v1_5-ENCODE, RFC 3447 section 9.2 step 2. This
+ * encodes the DigestInfo (T and tLen) but does not add the padding.
+ *
+ * On success, it returns one and sets |*out| to a newly allocated buffer
+ * containing the result and |*out_len| to its length. The caller must free
+ * |*out| with |OPENSSL_free|. Otherwise, it returns zero.
+ */
+static int encode_pkcs1(unsigned char **out, int *out_len, int type,
+                        const unsigned char *m, unsigned int m_len)
 {
     X509_SIG sig;
-    ASN1_TYPE parameter;
-    int i, j, ret = 1;
-    unsigned char *p, *tmps = NULL;
-    const unsigned char *s = NULL;
     X509_ALGOR algor;
+    ASN1_TYPE parameter;
     ASN1_OCTET_STRING digest;
+    uint8_t *der = NULL;
+    int len;
+
+    sig.algor = &algor;
+    sig.algor->algorithm = OBJ_nid2obj(type);
+    if (sig.algor->algorithm == NULL) {
+        RSAerr(RSA_F_ENCODE_PKCS1, RSA_R_UNKNOWN_ALGORITHM_TYPE);
+        return 0;
+    }
+    if (OBJ_length(sig.algor->algorithm) == 0) {
+        RSAerr(RSA_F_ENCODE_PKCS1,
+               RSA_R_THE_ASN1_OBJECT_IDENTIFIER_IS_NOT_KNOWN_FOR_THIS_MD);
+        return 0;
+    }
+    parameter.type = V_ASN1_NULL;
+    parameter.value.ptr = NULL;
+    sig.algor->parameter = &parameter;
+
+    sig.digest = &digest;
+    sig.digest->data = (unsigned char *)m;
+    sig.digest->length = m_len;
+
+    len = i2d_X509_SIG(&sig, &der);
+    if (len < 0)
+        return 0;
+
+    *out = der;
+    *out_len = len;
+    return 1;
+}
+
+int RSA_sign(int type, const unsigned char *m, unsigned int m_len,
+             unsigned char *sigret, unsigned int *siglen, RSA *rsa)
+{
+    int encrypt_len, encoded_len = 0, ret = 0;
+    unsigned char *tmps = NULL;
+    const unsigned char *encoded = NULL;
+
     if (rsa->meth->rsa_sign) {
         return rsa->meth->rsa_sign(type, m, m_len, sigret, siglen, rsa);
     }
-    /* Special case: SSL signature, just check the length */
+
+    /* Compute the encoded digest. */
     if (type == NID_md5_sha1) {
+        /*
+         * NID_md5_sha1 corresponds to the MD5/SHA1 combination in TLS 1.1 and
+         * earlier. It has no DigestInfo wrapper but otherwise is
+         * RSASSA-PKCS1-v1_5.
+         */
         if (m_len != SSL_SIG_LENGTH) {
             RSAerr(RSA_F_RSA_SIGN, RSA_R_INVALID_MESSAGE_LENGTH);
-            return (0);
+            return 0;
         }
-        i = SSL_SIG_LENGTH;
-        s = m;
+        encoded_len = SSL_SIG_LENGTH;
+        encoded = m;
     } else {
-        sig.algor = &algor;
-        sig.algor->algorithm = OBJ_nid2obj(type);
-        if (sig.algor->algorithm == NULL) {
-            RSAerr(RSA_F_RSA_SIGN, RSA_R_UNKNOWN_ALGORITHM_TYPE);
-            return (0);
-        }
-        if (OBJ_length(sig.algor->algorithm) == 0) {
-            RSAerr(RSA_F_RSA_SIGN,
-                   RSA_R_THE_ASN1_OBJECT_IDENTIFIER_IS_NOT_KNOWN_FOR_THIS_MD);
-            return (0);
-        }
-        parameter.type = V_ASN1_NULL;
-        parameter.value.ptr = NULL;
-        sig.algor->parameter = &parameter;
-
-        sig.digest = &digest;
-        sig.digest->data = (unsigned char *)m; /* TMP UGLY CAST */
-        sig.digest->length = m_len;
-
-        i = i2d_X509_SIG(&sig, NULL);
+        if (!encode_pkcs1(&tmps, &encoded_len, type, m, m_len))
+            goto err;
+        encoded = tmps;
     }
-    j = RSA_size(rsa);
-    if (i > (j - RSA_PKCS1_PADDING_SIZE)) {
+
+    if (encoded_len > RSA_size(rsa) - RSA_PKCS1_PADDING_SIZE) {
         RSAerr(RSA_F_RSA_SIGN, RSA_R_DIGEST_TOO_BIG_FOR_RSA_KEY);
-        return (0);
-    }
-    if (type != NID_md5_sha1) {
-        tmps = OPENSSL_malloc((unsigned int)j + 1);
-        if (tmps == NULL) {
-            RSAerr(RSA_F_RSA_SIGN, ERR_R_MALLOC_FAILURE);
-            return (0);
-        }
-        p = tmps;
-        i2d_X509_SIG(&sig, &p);
-        s = tmps;
+        goto err;
     }
-    i = RSA_private_encrypt(i, s, sigret, rsa, RSA_PKCS1_PADDING);
-    if (i <= 0)
-        ret = 0;
-    else
-        *siglen = i;
-
-    if (type != NID_md5_sha1)
-        OPENSSL_clear_free(tmps, (unsigned int)j + 1);
-    return (ret);
-}
+    encrypt_len = RSA_private_encrypt(encoded_len, encoded, sigret, rsa,
+                                      RSA_PKCS1_PADDING);
+    if (encrypt_len <= 0)
+        goto err;
 
-/*
- * Check DigestInfo structure does not contain extraneous data by reencoding
- * using DER and checking encoding against original.
- */
-static int rsa_check_digestinfo(X509_SIG *sig, const unsigned char *dinfo,
-                                int dinfolen)
-{
-    unsigned char *der = NULL;
-    int derlen;
-    int ret = 0;
-    derlen = i2d_X509_SIG(sig, &der);
-    if (derlen <= 0)
-        return 0;
-    if (derlen == dinfolen && !memcmp(dinfo, der, derlen))
-        ret = 1;
-    OPENSSL_clear_free(der, derlen);
+    *siglen = encrypt_len;
+    ret = 1;
+
+err:
+    OPENSSL_clear_free(tmps, (size_t)encoded_len);
     return ret;
 }
 
-int int_rsa_verify(int dtype, const unsigned char *m,
-                   unsigned int m_len,
+/*
+ * int_rsa_verify verifies an RSA signature in |sigbuf| using |rsa|. It may be
+ * called in two modes. If |rm| is NULL, it verifies the signature for digest
+ * |m|. Otherwise, it recovers the digest from the signature, writing the digest
+ * to |rm| and the length to |*prm_len|. |type| is the NID of the digest
+ * algorithm to use. It returns one on successful verification and zero
+ * otherwise.
+ */
+int int_rsa_verify(int type, const unsigned char *m, unsigned int m_len,
                    unsigned char *rm, size_t *prm_len,
                    const unsigned char *sigbuf, size_t siglen, RSA *rsa)
 {
-    int i, ret = 0, sigtype;
-    unsigned char *s;
-    X509_SIG *sig = NULL;
+    int decrypt_len, ret = 0, encoded_len = 0;
+    unsigned char *decrypt_buf = NULL, *encoded = NULL;
 
-    if (siglen != (unsigned int)RSA_size(rsa)) {
+    if (siglen != (size_t)RSA_size(rsa)) {
         RSAerr(RSA_F_INT_RSA_VERIFY, RSA_R_WRONG_SIGNATURE_LENGTH);
-        return (0);
-    }
-
-    if ((dtype == NID_md5_sha1) && rm) {
-        i = RSA_public_decrypt((int)siglen,
-                               sigbuf, rm, rsa, RSA_PKCS1_PADDING);
-        if (i <= 0)
-            return 0;
-        *prm_len = i;
-        return 1;
+        return 0;
     }
 
-    s = OPENSSL_malloc((unsigned int)siglen);
-    if (s == NULL) {
+    /* Recover the encoded digest. */
+    decrypt_buf = OPENSSL_malloc(siglen);
+    if (decrypt_buf == NULL) {
         RSAerr(RSA_F_INT_RSA_VERIFY, ERR_R_MALLOC_FAILURE);
         goto err;
     }
-    if ((dtype == NID_md5_sha1) && (m_len != SSL_SIG_LENGTH)) {
-        RSAerr(RSA_F_INT_RSA_VERIFY, RSA_R_INVALID_MESSAGE_LENGTH);
-        goto err;
-    }
-    i = RSA_public_decrypt((int)siglen, sigbuf, s, rsa, RSA_PKCS1_PADDING);
 
-    if (i <= 0)
+    decrypt_len = RSA_public_decrypt((int)siglen, sigbuf, decrypt_buf, rsa,
+                                     RSA_PKCS1_PADDING);
+    if (decrypt_len <= 0)
         goto err;
-    /*
-     * Oddball MDC2 case: signature can be OCTET STRING. check for correct
-     * tag and length octets.
-     */
-    if (dtype == NID_mdc2 && i == 18 && s[0] == 0x04 && s[1] == 0x10) {
-        if (rm) {
-            memcpy(rm, s + 2, 16);
-            *prm_len = 16;
-            ret = 1;
-        } else if (memcmp(m, s + 2, 16)) {
+
+    if (type == NID_md5_sha1) {
+        /*
+         * NID_md5_sha1 corresponds to the MD5/SHA1 combination in TLS 1.1 and
+         * earlier. It has no DigestInfo wrapper but otherwise is
+         * RSASSA-PKCS1-v1_5.
+         */
+        if (decrypt_len != SSL_SIG_LENGTH) {
             RSAerr(RSA_F_INT_RSA_VERIFY, RSA_R_BAD_SIGNATURE);
-        } else {
-            ret = 1;
+            goto err;
         }
-    } else if (dtype == NID_md5_sha1) {
-        /* Special case: SSL signature */
-        if ((i != SSL_SIG_LENGTH) || memcmp(s, m, SSL_SIG_LENGTH))
-            RSAerr(RSA_F_INT_RSA_VERIFY, RSA_R_BAD_SIGNATURE);
-        else
-            ret = 1;
-    } else {
-        const unsigned char *p = s;
-        sig = d2i_X509_SIG(NULL, &p, (long)i);
 
-        if (sig == NULL)
-            goto err;
+        if (rm != NULL) {
+            memcpy(rm, decrypt_buf, SSL_SIG_LENGTH);
+            *prm_len = SSL_SIG_LENGTH;
+        } else {
+            if (m_len != SSL_SIG_LENGTH) {
+                RSAerr(RSA_F_INT_RSA_VERIFY, RSA_R_INVALID_MESSAGE_LENGTH);
+                goto err;
+            }
 
-        /* Excess data can be used to create forgeries */
-        if (p != s + i || !rsa_check_digestinfo(sig, s, i)) {
-            RSAerr(RSA_F_INT_RSA_VERIFY, RSA_R_BAD_SIGNATURE);
-            goto err;
+            if (memcmp(decrypt_buf, m, SSL_SIG_LENGTH) != 0) {
+                RSAerr(RSA_F_INT_RSA_VERIFY, RSA_R_BAD_SIGNATURE);
+                goto err;
+            }
         }
+    } else if (type == NID_mdc2 && decrypt_len == 2 + 16
+               && decrypt_buf[0] == 0x04 && decrypt_buf[1] == 0x10) {
+        /*
+         * Oddball MDC2 case: signature can be OCTET STRING. check for correct
+         * tag and length octets.
+         */
+        if (rm != NULL) {
+            memcpy(rm, decrypt_buf + 2, 16);
+            *prm_len = 16;
+        } else {
+            if (m_len != 16) {
+                RSAerr(RSA_F_INT_RSA_VERIFY, RSA_R_INVALID_MESSAGE_LENGTH);
+                goto err;
+            }
 
+            if (memcmp(m, decrypt_buf + 2, 16) != 0) {
+                RSAerr(RSA_F_INT_RSA_VERIFY, RSA_R_BAD_SIGNATURE);
+                goto err;
+            }
+        }
+    } else {
         /*
-         * Parameters to the signature algorithm can also be used to create
-         * forgeries
+         * If recovering the digest, extract a digest-sized output from the end
+         * of |decrypt_buf| for |encode_pkcs1|, then compare the decryption
+         * output as in a standard verification.
          */
-        if (sig->algor->parameter
-            && ASN1_TYPE_get(sig->algor->parameter) != V_ASN1_NULL) {
-            RSAerr(RSA_F_INT_RSA_VERIFY, RSA_R_BAD_SIGNATURE);
-            goto err;
+        if (rm != NULL) {
+            const EVP_MD *md = EVP_get_digestbynid(type);
+            if (md == NULL) {
+                RSAerr(RSA_F_INT_RSA_VERIFY, RSA_R_UNKNOWN_ALGORITHM_TYPE);
+                goto err;
+            }
+
+            m_len = EVP_MD_size(md);
+            if (m_len > (size_t)decrypt_len) {
+                RSAerr(RSA_F_INT_RSA_VERIFY, RSA_R_INVALID_DIGEST_LENGTH);
+                goto err;
+            }
+            m = decrypt_buf + decrypt_len - m_len;
         }
 
-        sigtype = OBJ_obj2nid(sig->algor->algorithm);
+        /* Construct the encoded digest and ensure it matches. */
+        if (!encode_pkcs1(&encoded, &encoded_len, type, m, m_len))
+            goto err;
 
-        if (sigtype != dtype) {
-            RSAerr(RSA_F_INT_RSA_VERIFY, RSA_R_ALGORITHM_MISMATCH);
+        if (encoded_len != decrypt_len
+            || memcmp(encoded, decrypt_buf, encoded_len) != 0) {
+            RSAerr(RSA_F_INT_RSA_VERIFY, RSA_R_BAD_SIGNATURE);
             goto err;
         }
-        if (rm) {
-            const EVP_MD *md;
-            md = EVP_get_digestbynid(dtype);
-            if (md && (EVP_MD_size(md) != sig->digest->length))
-                RSAerr(RSA_F_INT_RSA_VERIFY, RSA_R_INVALID_DIGEST_LENGTH);
-            else {
-                memcpy(rm, sig->digest->data, sig->digest->length);
-                *prm_len = sig->digest->length;
-                ret = 1;
-            }
-        } else if (((unsigned int)sig->digest->length != m_len) ||
-                   (memcmp(m, sig->digest->data, m_len) != 0)) {
-            RSAerr(RSA_F_INT_RSA_VERIFY, RSA_R_BAD_SIGNATURE);
-        } else
-            ret = 1;
+
+        /* Output the recovered digest. */
+        if (rm != NULL) {
+            memcpy(rm, m, m_len);
+            *prm_len = m_len;
+        }
     }
- err:
-    X509_SIG_free(sig);
-    OPENSSL_clear_free(s, (unsigned int)siglen);
-    return (ret);
+
+    ret = 1;
+
+err:
+    OPENSSL_clear_free(encoded, (size_t)encoded_len);
+    OPENSSL_clear_free(decrypt_buf, siglen);
+    return ret;
 }
 
-int RSA_verify(int dtype, const unsigned char *m, unsigned int m_len,
+int RSA_verify(int type, const unsigned char *m, unsigned int m_len,
                const unsigned char *sigbuf, unsigned int siglen, RSA *rsa)
 {
 
     if (rsa->meth->rsa_verify) {
-        return rsa->meth->rsa_verify(dtype, m, m_len, sigbuf, siglen, rsa);
+        return rsa->meth->rsa_verify(type, m, m_len, sigbuf, siglen, rsa);
     }
 
-    return int_rsa_verify(dtype, m, m_len, NULL, NULL, sigbuf, siglen, rsa);
+    return int_rsa_verify(type, m, m_len, NULL, NULL, sigbuf, siglen, rsa);
 }