Constant time/cache PKCS#1 RSA decryptiontmp-fix-CVE-2018-16868

This patch tries to make the code have the same time and memory access
aptterns across all branches of the decryption function so that timining
or cache side channels are minimized or neutralized.

To do so it uses a new nettle rsa decryption function that is
side-channel silent.

Signed-off-by: Simo Sorce <simo@redhat.com>

19 files changed, 386 insertions, 58 deletions

diff --git a/NEWS b/NEWS
index 4efc209fdd..e0f31df0e0 100644
--- a/NEWS
+++ b/NEWS
@@ -41,6 +41,15 @@ See the end for copying conditions.
 ** certtool: Add parameter --no-text that prevents certtool from outputting
    text before PEM-encoded private key, public key, certificate, CRL or CSR.
 
+** libgnutls: Change RSA decryption to use a new side-channel silent function.
+   This addresses a security issue where memory access patterns as well as timing
+   on the underlying Nettle rsa-decrypt function could lead to new Bleichenbacher
+   attacks. Side-channel resistant code is slower due to the need to mask
+   access and timings. When used in TLS the new functions cause RSA based
+   handshakes to be between 13% and 28% slower on average (Numbers are indicative,
+   the tests where performed on a relatively modern Intel CPU, results vary
+   depending on the CPU and architecture used).
+
 ** API and ABI modifications:
 GNUTLS_AUTO_REAUTH: Added
 GNUTLS_CIPHER_AES_128_CFB8: Added
@@ -57,6 +66,7 @@ gnutls_anti_replay_init: Added
 gnutls_anti_replay_deinit: Added
 gnutls_anti_replay_set_window: Added
 gnutls_anti_replay_enable: Added
+gnutls_privkey_decrypt_data2: Added
 
 
 * Version 3.6.4 (released 2018-09-24)
diff --git a/configure.ac b/configure.ac
index d864b3bf97..0926ed1094 100644
--- a/configure.ac
+++ b/configure.ac
@@ -553,6 +553,15 @@ if test "$enable_non_suiteb" = "yes";then
 fi
 AM_CONDITIONAL(ENABLE_NON_SUITEB_CURVES, test "$enable_non_suiteb" = "yes")
 
+# We MUST require a Nettle version that has rsa_sec_decrypt now.
+save_LIBS=$LIBS
+LIBS="$LIBS $HOGWEED_LIBS"
+AC_CHECK_FUNCS(nettle_rsa_sec_decrypt,
+    [],
+    [AC_MSG_ERROR([Nettle lacks the required rsa_sec_decrypt function])]
+)
+LIBS=$save_LIBS
+
 # Check if nettle has CFB8 support
 save_LIBS=$LIBS
 LIBS="$LIBS $NETTLE_LIBS"
diff --git a/doc/Makefile.am b/doc/Makefile.am
index e6d5e14c6e..8a9a712091 100644
--- a/doc/Makefile.am
+++ b/doc/Makefile.am
@@ -1579,6 +1579,8 @@ FUNCS += functions/gnutls_priority_string_list
 FUNCS += functions/gnutls_priority_string_list.short
 FUNCS += functions/gnutls_privkey_decrypt_data
 FUNCS += functions/gnutls_privkey_decrypt_data.short
+FUNCS += functions/gnutls_privkey_decrypt_data2
+FUNCS += functions/gnutls_privkey_decrypt_data2.short
 FUNCS += functions/gnutls_privkey_deinit
 FUNCS += functions/gnutls_privkey_deinit.short
 FUNCS += functions/gnutls_privkey_export_dsa_raw
diff --git a/doc/manpages/Makefile.am b/doc/manpages/Makefile.am
index 3bac791f3e..7db892d880 100644
--- a/doc/manpages/Makefile.am
+++ b/doc/manpages/Makefile.am
@@ -591,6 +591,7 @@ APIMANS += gnutls_priority_set_direct.3
 APIMANS += gnutls_priority_sign_list.3
 APIMANS += gnutls_priority_string_list.3
 APIMANS += gnutls_privkey_decrypt_data.3
+APIMANS += gnutls_privkey_decrypt_data2.3
 APIMANS += gnutls_privkey_deinit.3
 APIMANS += gnutls_privkey_export_dsa_raw.3
 APIMANS += gnutls_privkey_export_dsa_raw2.3
diff --git a/lib/abstract_int.h b/lib/abstract_int.h
index 5eaf6e9460..d920486597 100644
--- a/lib/abstract_int.h
+++ b/lib/abstract_int.h
@@ -39,6 +39,7 @@ struct gnutls_privkey_st {
 			gnutls_privkey_sign_data_func sign_data_func;
 			gnutls_privkey_sign_hash_func sign_hash_func;
 			gnutls_privkey_decrypt_func decrypt_func;
+			gnutls_privkey_decrypt_func2 decrypt_func2;
 			gnutls_privkey_deinit_func deinit_func;
 			gnutls_privkey_info_func info_func;
 			void *userdata;
diff --git a/lib/auth/rsa.c b/lib/auth/rsa.c
index 6afc91ae67..488569d3b7 100644
--- a/lib/auth/rsa.c
+++ b/lib/auth/rsa.c
@@ -155,12 +155,13 @@ static int
 proc_rsa_client_kx(gnutls_session_t session, uint8_t * data,
 		   size_t _data_size)
 {
-	gnutls_datum_t plaintext = {NULL, 0};
+	const char attack_error[] = "auth_rsa: Possible PKCS #1 attack\n";
 	gnutls_datum_t ciphertext;
 	int ret, dsize;
-	int use_rnd_key = 0;
 	ssize_t data_size = _data_size;
-	gnutls_datum_t rndkey = {NULL, 0};
+	volatile uint8_t ver_maj, ver_min;
+	volatile uint8_t check_ver_min;
+	volatile uint32_t ok;
 
 #ifdef ENABLE_SSL3
 	if (get_num_version(session) == GNUTLS_SSL3) {
@@ -184,75 +185,73 @@ proc_rsa_client_kx(gnutls_session_t session, uint8_t * data,
 		ciphertext.size = dsize;
 	}
 
-	rndkey.size = GNUTLS_MASTER_SIZE;
-	rndkey.data = gnutls_malloc(rndkey.size);
-	if (rndkey.data == NULL) {
+	ver_maj = _gnutls_get_adv_version_major(session);
+	ver_min = _gnutls_get_adv_version_minor(session);
+	check_ver_min = (session->internals.allow_wrong_pms == 0);
+
+	session->key.key.data = gnutls_malloc(GNUTLS_MASTER_SIZE);
+	if (session->key.key.data == NULL) {
 		gnutls_assert();
 		return GNUTLS_E_MEMORY_ERROR;
 	}
+	session->key.key.size = GNUTLS_MASTER_SIZE;
 
-	/* we do not need strong random numbers here.
-	 */
-	ret = gnutls_rnd(GNUTLS_RND_NONCE, rndkey.data,
-			  rndkey.size);
+	/* Fallback value when decryption fails. Needs to be unpredictable. */
+	ret = gnutls_rnd(GNUTLS_RND_NONCE, session->key.key.data,
+			 GNUTLS_MASTER_SIZE);
 	if (ret < 0) {
+                gnutls_free(session->key.key.data);
+                session->key.key.data = NULL;
+                session->key.key.size = 0;
 		gnutls_assert();
-		goto cleanup;
+		return ret;
 	}
 
 	ret =
-	    gnutls_privkey_decrypt_data(session->internals.selected_key, 0,
-					&ciphertext, &plaintext);
-
-	if (ret < 0 || plaintext.size != GNUTLS_MASTER_SIZE) {
-		/* In case decryption fails then don't inform
-		 * the peer. Just use a random key. (in order to avoid
-		 * attack against pkcs-1 formating).
-		 */
-		_gnutls_debug_log("auth_rsa: Possible PKCS #1 format attack\n");
-		if (ret >= 0) {
-			gnutls_free(plaintext.data);
-			plaintext.data = NULL;
-		}
-		use_rnd_key = 1;
-	} else {
-		/* If the secret was properly formatted, then
-		 * check the version number.
-		 */
-		if (_gnutls_get_adv_version_major(session) !=
-		    plaintext.data[0]
-		    || (session->internals.allow_wrong_pms == 0
-			&& _gnutls_get_adv_version_minor(session) !=
-			plaintext.data[1])) {
-			/* No error is returned here, if the version number check
-			 * fails. We proceed normally.
-			 * That is to defend against the attack described in the paper
-			 * "Attacking RSA-based sessions in SSL/TLS" by Vlastimil Klima,
-			 * Ondej Pokorny and Tomas Rosa.
-			 */
-			_gnutls_debug_log("auth_rsa: Possible PKCS #1 version check format attack\n");
-		}
-	}
+	    gnutls_privkey_decrypt_data2(session->internals.selected_key,
+					 0, &ciphertext, session->key.key.data,
+					 session->key.key.size);
+	/* After this point, any conditional on failure that cause differences
+	 * in execution may create a timing or cache access pattern side
+	 * channel that can be used as an oracle, so tread very carefully */
+
+	/* Error handling logic:
+	 * In case decryption fails then don't inform the peer. Just use the
+	 * random key previously generated. (in order to avoid attack against
+	 * pkcs-1 formating).
+	 *
+	 * If we get version mismatches no error is returned either. We
+	 * proceed normally. This is to defend against the attack described
+	 * in the paper "Attacking RSA-based sessions in SSL/TLS" by
+	 * Vlastimil Klima, Ondej Pokorny and Tomas Rosa.
+	 */
 
-	if (use_rnd_key != 0) {
-		session->key.key.data = rndkey.data;
-		session->key.key.size = rndkey.size;
-		rndkey.data = NULL;
+	/* ok is 0 in case of error and 1 in case of success. */
+
+	/* if ret < 0 */
+	ok = CONSTCHECK_EQUAL(ret, 0);
+	/* session->key.key.data[0] must equal ver_maj */
+	ok &= CONSTCHECK_EQUAL(session->key.key.data[0], ver_maj);
+	/* if check_ver_min then session->key.key.data[1] must equal ver_min */
+	ok &= CONSTCHECK_NOT_EQUAL(check_ver_min, 0) &
+	        CONSTCHECK_EQUAL(session->key.key.data[1], ver_min);
+
+	if (ok) {
+		/* call logging function unconditionally so all branches are
+		 * indistinguishable for timing and cache access when debug
+		 * logging is disabled */
+		_gnutls_no_log("%s", attack_error);
 	} else {
-		session->key.key.data = plaintext.data;
-		session->key.key.size = plaintext.size;
+		_gnutls_debug_log("%s", attack_error);
 	}
 
 	/* This is here to avoid the version check attack
 	 * discussed above.
 	 */
-	session->key.key.data[0] = _gnutls_get_adv_version_major(session);
-	session->key.key.data[1] = _gnutls_get_adv_version_minor(session);
+	session->key.key.data[0] = ver_maj;
+	session->key.key.data[1] = ver_min;
 
-	ret = 0;
- cleanup:
-	gnutls_free(rndkey.data);
-	return ret;
+	return 0;
 }
 
 
diff --git a/lib/crypto-backend.h b/lib/crypto-backend.h
index ff8f39616e..19f705e14d 100644
--- a/lib/crypto-backend.h
+++ b/lib/crypto-backend.h
@@ -344,10 +344,15 @@ typedef struct gnutls_crypto_pk {
 	int (*encrypt) (gnutls_pk_algorithm_t, gnutls_datum_t * ciphertext,
 			const gnutls_datum_t * plaintext,
 			const gnutls_pk_params_st * pub);
-	int (*decrypt) (gnutls_pk_algorithm_t, gnutls_datum_t * plaintext,
+	int (*decrypt) (gnutls_pk_algorithm_t,
+                        gnutls_datum_t * plaintext,
 			const gnutls_datum_t * ciphertext,
 			const gnutls_pk_params_st * priv);
-
+	int (*decrypt2) (gnutls_pk_algorithm_t,
+			 const gnutls_datum_t * ciphertext,
+                         unsigned char * plaintext,
+                         size_t paintext_size,
+			 const gnutls_pk_params_st * priv);
 	int (*sign) (gnutls_pk_algorithm_t, gnutls_datum_t * signature,
 		     const gnutls_datum_t * data,
 		     const gnutls_pk_params_st *priv,
diff --git a/lib/crypto-selftests-pk.c b/lib/crypto-selftests-pk.c
index e42367a93f..65de8916f5 100644
--- a/lib/crypto-selftests-pk.c
+++ b/lib/crypto-selftests-pk.c
@@ -116,6 +116,7 @@ static int test_rsa_enc(gnutls_pk_algorithm_t pk,
 	gnutls_datum_t raw_rsa_key = { (void*)rsa_key2048, sizeof(rsa_key2048)-1 };
 	gnutls_privkey_t key;
 	gnutls_pubkey_t pub = NULL;
+	unsigned char plaintext2[sizeof(DATASTR) - 1];
 
 	ret = gnutls_privkey_init(&key);
 	if (ret < 0)
@@ -165,6 +166,18 @@ static int test_rsa_enc(gnutls_pk_algorithm_t pk,
 		goto cleanup;
 	}
 
+	ret = gnutls_privkey_decrypt_data2(key, 0, &enc, plaintext2,
+					   signed_data.size);
+	if (ret < 0) {
+		gnutls_assert();
+		goto cleanup;
+	}
+	if (memcmp(plaintext2, signed_data.data, signed_data.size) != 0) {
+		ret = GNUTLS_E_SELF_TEST_ERROR;
+		gnutls_assert();
+		goto cleanup;
+	}
+
 	ret = 0;
       cleanup:
 	if (pub != NULL)
diff --git a/lib/errors.h b/lib/errors.h
index e0f6b906c2..baadc0e67e 100644
--- a/lib/errors.h
+++ b/lib/errors.h
@@ -108,6 +108,7 @@ void _gnutls_mpi_log(const char *prefix, bigint_t a);
 #define _gnutls_write_log(...) LEVEL(11, __VA_ARGS__)
 #define _gnutls_io_log(...) LEVEL(12, __VA_ARGS__)
 #define _gnutls_buffers_log(...) LEVEL(13, __VA_ARGS__)
+#define _gnutls_no_log(...) LEVEL(INT_MAX, __VA_ARGS__)
 #else
 #define _gnutls_debug_log _gnutls_null_log
 #define _gnutls_assert_log _gnutls_null_log
@@ -119,6 +120,7 @@ void _gnutls_mpi_log(const char *prefix, bigint_t a);
 #define _gnutls_dtls_log _gnutls_null_log
 #define _gnutls_read_log _gnutls_null_log
 #define _gnutls_write_log _gnutls_null_log
+#define _gnutls_no_log _gnutle_null_log
 
 void _gnutls_null_log(void *, ...);
 
diff --git a/lib/gnutls_int.h b/lib/gnutls_int.h
index 16881d8827..50a9208346 100644
--- a/lib/gnutls_int.h
+++ b/lib/gnutls_int.h
@@ -1564,4 +1564,8 @@ inline static bool _gnutls_has_negotiate_ctypes(gnutls_session_t session)
 	return session->internals.flags & GNUTLS_ENABLE_CERT_TYPE_NEG;
 }
 
+/* Macros to aide constant time/mem checks */
+#define CONSTCHECK_NOT_EQUAL(a, b) ((-((uint32_t)(a) ^ (uint32_t)(b))) >> 31)
+#define CONSTCHECK_EQUAL(a, b) (1U - CONSTCHECK_NOT_EQUAL(a, b))
+
 #endif				/* GNUTLS_INT_H */
diff --git a/lib/includes/gnutls/abstract.h b/lib/includes/gnutls/abstract.h
index 5fa0fb99db..d69e30ca51 100644
--- a/lib/includes/gnutls/abstract.h
+++ b/lib/includes/gnutls/abstract.h
@@ -75,6 +75,12 @@ typedef int (*gnutls_privkey_decrypt_func) (gnutls_privkey_t key,
 					    const gnutls_datum_t *ciphertext,
 					    gnutls_datum_t * plaintext);
 
+typedef int (*gnutls_privkey_decrypt_func2) (gnutls_privkey_t key,
+					     void *userdata,
+					     const gnutls_datum_t *ciphertext,
+					     unsigned char * plaintext,
+					     size_t plaintext_size);
+
 /* to be called to sign pre-hashed data. The input will be
  * the output of the hash (such as SHA256) corresponding to
  * the signature algorithm. The algorithm GNUTLS_SIGN_RSA_RAW
@@ -542,12 +548,17 @@ int gnutls_privkey_sign_hash2(gnutls_privkey_t signer,
 			      const gnutls_datum_t * hash_data,
 			      gnutls_datum_t * signature);
 
-
 int gnutls_privkey_decrypt_data(gnutls_privkey_t key,
 				unsigned int flags,
 				const gnutls_datum_t * ciphertext,
 				gnutls_datum_t * plaintext);
 
+int gnutls_privkey_decrypt_data2(gnutls_privkey_t key,
+				 unsigned int flags,
+				 const gnutls_datum_t * ciphertext,
+				 unsigned char * plaintext,
+                                 size_t plaintext_size);
+
 int
 gnutls_privkey_export_rsa_raw(gnutls_privkey_t key,
 				    gnutls_datum_t * m, gnutls_datum_t * e,
diff --git a/lib/libgnutls.map b/lib/libgnutls.map
index 06181f04ee..bfb447ccfd 100644
--- a/lib/libgnutls.map
+++ b/lib/libgnutls.map
@@ -1261,6 +1261,7 @@ GNUTLS_3_6_5
 	gnutls_anti_replay_deinit;
 	gnutls_anti_replay_set_window;
 	gnutls_anti_replay_enable;
+	gnutls_privkey_decrypt_data2;
 } GNUTLS_3_6_4;
 
 GNUTLS_FIPS140_3_4 {
diff --git a/lib/nettle/pk.c b/lib/nettle/pk.c
index 4d945c89ad..38c098d8d5 100644
--- a/lib/nettle/pk.c
+++ b/lib/nettle/pk.c
@@ -529,6 +529,57 @@ _wrap_nettle_pk_decrypt(gnutls_pk_algorithm_t algo,
 	return ret;
 }
 
+/* Note: we do not allocate in this function to avoid asymettric
+ * unallocation (which creates a side channel) in case of failure
+ * */
+static int
+_wrap_nettle_pk_decrypt2(gnutls_pk_algorithm_t algo,
+			 const gnutls_datum_t * ciphertext,
+			 unsigned char * plaintext,
+			 size_t plaintext_size,
+			 const gnutls_pk_params_st * pk_params)
+{
+	struct rsa_private_key priv;
+	struct rsa_public_key pub;
+	bigint_t c;
+	uint32_t is_err;
+	int ret;
+
+	if (algo != GNUTLS_PK_RSA || plaintext == NULL) {
+		gnutls_assert();
+		return GNUTLS_E_INTERNAL_ERROR;
+	}
+
+	_rsa_params_to_privkey(pk_params, &priv);
+	ret = _rsa_params_to_pubkey(pk_params, &pub);
+	if (ret < 0)
+		return gnutls_assert_val(ret);
+
+	if (ciphertext->size != pub.size)
+		return gnutls_assert_val(GNUTLS_E_DECRYPTION_FAILED);
+
+	if (_gnutls_mpi_init_scan_nz(&c, ciphertext->data,
+				     ciphertext->size) != 0) {
+		return gnutls_assert_val (GNUTLS_E_MPI_SCAN_FAILED);
+	}
+
+	ret = rsa_sec_decrypt(&pub, &priv, NULL, rnd_nonce_func,
+			     plaintext_size, plaintext, TOMPZ(c));
+	/* after this point, any conditional on failure that cause differences
+	 * in execution may create a timing or cache access pattern side
+	 * channel that can be used as an oracle, so thread very carefully */
+	_gnutls_mpi_release(&c);
+	/* Here HAVE_LIB_ERROR() should be fine as it doesn't have
+	 * branches in it and returns a bool */
+	is_err = HAVE_LIB_ERROR();
+	/* if is_err != 0 */
+	is_err = CONSTCHECK_NOT_EQUAL(is_err, 0);
+	/* or ret == 0 */
+	is_err |= CONSTCHECK_EQUAL(ret, 0);
+	/* then return GNUTLS_E_DECRYPTION_FAILED */
+	return (int)((is_err * UINT_MAX) & GNUTLS_E_DECRYPTION_FAILED);
+}
+
 #define CHECK_INVALID_RSA_PSS_PARAMS(dig_size, salt_size, pub_size, err) \
 	if (unlikely(dig_size + salt_size + 2 > pub_size)) \
 		return gnutls_assert_val(err)
@@ -2780,6 +2831,7 @@ int crypto_pk_prio = INT_MAX;
 gnutls_crypto_pk_st _gnutls_pk_ops = {
 	.encrypt = _wrap_nettle_pk_encrypt,
 	.decrypt = _wrap_nettle_pk_decrypt,
+	.decrypt2 = _wrap_nettle_pk_decrypt2,
 	.sign = _wrap_nettle_pk_sign,
 	.verify = _wrap_nettle_pk_verify,
 	.verify_priv_params = wrap_nettle_pk_verify_priv_params,
diff --git a/lib/pk.h b/lib/pk.h
index c365eece20..f6872f823d 100644
--- a/lib/pk.h
+++ b/lib/pk.h
@@ -28,6 +28,7 @@ extern gnutls_crypto_pk_st _gnutls_pk_ops;
 
 #define _gnutls_pk_encrypt( algo, ciphertext, plaintext, params) _gnutls_pk_ops.encrypt( algo, ciphertext, plaintext, params)
 #define _gnutls_pk_decrypt( algo, ciphertext, plaintext, params) _gnutls_pk_ops.decrypt( algo, ciphertext, plaintext, params)
+#define _gnutls_pk_decrypt2( algo, ciphertext, plaintext, size, params) _gnutls_pk_ops.decrypt2( algo, ciphertext, plaintext, size, params)
 #define _gnutls_pk_sign( algo, sig, data, params, sign_params) _gnutls_pk_ops.sign( algo, sig, data, params, sign_params)
 #define _gnutls_pk_verify( algo, data, sig, params, sign_params) _gnutls_pk_ops.verify( algo, data, sig, params, sign_params)
 #define _gnutls_pk_verify_priv_params( algo, params) _gnutls_pk_ops.verify_priv_params( algo, params)
diff --git a/lib/pkcs11_int.h b/lib/pkcs11_int.h
index 8facfa8686..a5187636ed 100644
--- a/lib/pkcs11_int.h
+++ b/lib/pkcs11_int.h
@@ -219,6 +219,13 @@ _gnutls_pkcs11_privkey_decrypt_data(gnutls_pkcs11_privkey_t key,
 				    gnutls_datum_t * plaintext);
 
 int
+_gnutls_pkcs11_privkey_decrypt_data2(gnutls_pkcs11_privkey_t key,
+				     unsigned int flags,
+				     const gnutls_datum_t * ciphertext,
+			             unsigned char * plaintext,
+			             size_t plaintext_size);
+
+int
 _pkcs11_privkey_get_pubkey (gnutls_pkcs11_privkey_t pkey, gnutls_pubkey_t *pub, unsigned flags);
 
 static inline int pk_to_mech(gnutls_pk_algorithm_t pk)
diff --git a/lib/pkcs11_privkey.c b/lib/pkcs11_privkey.c
index f643a69a66..bf69b69ce4 100644
--- a/lib/pkcs11_privkey.c
+++ b/lib/pkcs11_privkey.c
@@ -715,6 +715,121 @@ _gnutls_pkcs11_privkey_decrypt_data(gnutls_pkcs11_privkey_t key,
 	return ret;
 }
 
+/*-
+ * _gnutls_pkcs11_privkey_decrypt_data2:
+ * @key: Holds the key
+ * @flags: should be 0 for now
+ * @ciphertext: holds the data to be signed
+ * @plaintext: a preallocated buffer that will be filled with the plaintext
+ * @plaintext_size: size of the plaintext
+ *
+ * This function will decrypt the given data using the public key algorithm
+ * supported by the private key.
+ * Unlike with _gnutls_pkcs11_privkey_decrypt_data the plaintext size is known
+ * and provided by the caller, if the plaintext size differs from the requested
+ * one, the operation fails and the provided buffer is left unchanged.
+ * NOTE: plaintext_size must be exactly the size of the payload in the
+ * ciphertext, otherwise an error is returned and the plaintext buffer is left
+ * unchanged.
+ *
+ * Returns: On success, %GNUTLS_E_SUCCESS (0) is returned, otherwise a
+ *   negative error value.
+ -*/
+int
+_gnutls_pkcs11_privkey_decrypt_data2(gnutls_pkcs11_privkey_t key,
+				     unsigned int flags,
+				     const gnutls_datum_t * ciphertext,
+				     unsigned char * plaintext,
+				     size_t plaintext_size)
+{
+	ck_rv_t rv;
+	int ret;
+	struct ck_mechanism mech;
+	unsigned long siglen = ciphertext->size;
+	unsigned req_login = 0;
+	unsigned login_flags = SESSION_LOGIN|SESSION_CONTEXT_SPECIFIC;
+	unsigned char *buffer;
+	volatile unsigned char value;
+	unsigned char mask;
+
+	PKCS11_CHECK_INIT_PRIVKEY(key);
+
+	if (key->pk_algorithm != GNUTLS_PK_RSA)
+		return gnutls_assert_val(GNUTLS_E_INVALID_REQUEST);
+
+	mech.mechanism = CKM_RSA_PKCS;
+	mech.parameter = NULL;
+	mech.parameter_len = 0;
+
+	ret = gnutls_mutex_lock(&key->mutex);
+	if (ret != 0)
+		return gnutls_assert_val(GNUTLS_E_LOCKING_ERROR);
+
+	buffer = gnutls_malloc(siglen);
+	if (!buffer) {
+		gnutls_assert();
+		return GNUTLS_E_MEMORY_ERROR;
+	}
+
+	/* Initialize signing operation; using the private key discovered
+	 * earlier. */
+	REPEAT_ON_INVALID_HANDLE(
+		rv = pkcs11_decrypt_init(key->sinfo.module, key->sinfo.pks,
+					 &mech, key->ref)
+	);
+	if (rv != CKR_OK) {
+		gnutls_assert();
+		ret = pkcs11_rv_to_err(rv);
+		goto cleanup;
+	}
+
+ retry_login:
+	if (key->reauth || req_login) {
+		if (req_login)
+			login_flags = SESSION_FORCE_LOGIN|SESSION_LOGIN;
+		ret =
+		    pkcs11_login(&key->sinfo, &key->pin,
+				 key->uinfo, login_flags);
+		if (ret < 0) {
+			gnutls_assert();
+			_gnutls_debug_log("PKCS #11 login failed, trying operation anyway\n");
+			/* let's try the operation anyway */
+		}
+	}
+
+	ret = 0;
+	siglen = ciphertext->size;
+	rv = pkcs11_decrypt(key->sinfo.module, key->sinfo.pks,
+			    ciphertext->data, ciphertext->size,
+			    buffer, &siglen);
+	if (unlikely(rv == CKR_USER_NOT_LOGGED_IN && req_login == 0)) {
+		req_login = 1;
+		goto retry_login;
+	}
+
+	/* NOTE: These branches are not side-channel silent */
+	if (rv != CKR_OK) {
+		gnutls_assert();
+		ret = pkcs11_rv_to_err(rv);
+	} else if (siglen != plaintext_size) {
+		gnutls_assert();
+		ret = GNUTLS_E_INVALID_REQUEST;
+	}
+
+	/* conditionally copy buffer in a side-channel silent way */
+	/* on success mask is 0xFF, on failure it is 0 */
+	mask = ((uint32_t)ret >> 31) - 1U;
+	for (size_t i = 0; i < plaintext_size; i++) {
+		value = (buffer[i] & mask) + (plaintext[i] & ~mask);
+		plaintext[i] = value;
+	}
+
+      cleanup:
+	gnutls_mutex_unlock(&key->mutex);
+	gnutls_free(buffer);
+	return ret;
+}
+
 /**
  * gnutls_pkcs11_privkey_export_url:
  * @key: Holds the PKCS 11 key
diff --git a/lib/privkey.c b/lib/privkey.c
index 26e3cee893..55bd3181ab 100644
--- a/lib/privkey.c
+++ b/lib/privkey.c
@@ -1555,6 +1555,82 @@ gnutls_privkey_decrypt_data(gnutls_privkey_t key,
 }
 
 /**
+ * gnutls_privkey_decrypt_data2:
+ * @key: Holds the key
+ * @flags: zero for now
+ * @ciphertext: holds the data to be decrypted
+ * @plaintext: a preallocated buffer that will be filled with the plaintext
+ * @plaintext_size: in/out size of the plaintext
+ *
+ * This function will decrypt the given data using the algorithm
+ * supported by the private key. Unlike with gnutls_privkey_decrypt_data()
+ * this function operates in constant time and constant memory access.
+ *
+ * Returns: On success, %GNUTLS_E_SUCCESS (0) is returned, otherwise a
+ * negative error value.
+ *
+ * Since: 3.6.5
+ **/
+
+int
+gnutls_privkey_decrypt_data2(gnutls_privkey_t key,
+			     unsigned int flags,
+			     const gnutls_datum_t * ciphertext,
+			     unsigned char * plaintext,
+			     size_t plaintext_size)
+{
+	/* Note: except for the backwards compatibility function, no
+	 * conditional code should be called after the decryption
+	 * function call, to avoid creating oracle attacks based
+	 * on cache/timing side channels */
+
+	/* backwards compatibility */
+	if (key->type == GNUTLS_PRIVKEY_EXT &&
+	    key->key.ext.decrypt_func2 == NULL &&
+	    key->key.ext.decrypt_func != NULL) {
+		gnutls_datum_t plain;
+		int ret;
+		ret = key->key.ext.decrypt_func(key,
+						key->key.ext.userdata,
+						ciphertext,
+						&plain);
+		if (plain.size != plaintext_size) {
+			ret = gnutls_assert_val(GNUTLS_E_INVALID_REQUEST);
+		} else {
+			memcpy(plaintext, plain.data, plain.size);
+		}
+		gnutls_free(plain.data);
+		return ret;
+	}
+
+	switch (key->type) {
+	case GNUTLS_PRIVKEY_X509:
+		return _gnutls_pk_decrypt2(key->pk_algorithm, ciphertext,
+					   plaintext, plaintext_size,
+					   &key->key.x509->params);
+#ifdef ENABLE_PKCS11
+	case GNUTLS_PRIVKEY_PKCS11:
+		return _gnutls_pkcs11_privkey_decrypt_data2(key->key.pkcs11,
+							    flags,
+							    ciphertext,
+							    plaintext,
+							    plaintext_size);
+#endif
+	case GNUTLS_PRIVKEY_EXT:
+		if (key->key.ext.decrypt_func2 == NULL)
+			return gnutls_assert_val(GNUTLS_E_INVALID_REQUEST);
+
+		return key->key.ext.decrypt_func2(key,
+						  key->key.ext.userdata,
+						  ciphertext, plaintext,
+						  plaintext_size);
+	default:
+		gnutls_assert();
+		return GNUTLS_E_INVALID_REQUEST;
+	}
+}
+
+/**
  * gnutls_privkey_import_x509_raw:
  * @pkey: The private key
  * @data: The private key data to be imported
diff --git a/symbols.last b/symbols.last
index 820821219e..7b547b7117 100644
--- a/symbols.last
+++ b/symbols.last
@@ -567,6 +567,7 @@ gnutls_priority_set@GNUTLS_3_4
 gnutls_priority_set_direct@GNUTLS_3_4
 gnutls_priority_sign_list@GNUTLS_3_4
 gnutls_priority_string_list@GNUTLS_3_4
+gnutls_privkey_decrypt_data2@GNUTLS_3_6_5
 gnutls_privkey_decrypt_data@GNUTLS_3_4
 gnutls_privkey_deinit@GNUTLS_3_4
 gnutls_privkey_export_dsa_raw2@GNUTLS_3_6_0
diff --git a/tests/rsa-encrypt-decrypt.c b/tests/rsa-encrypt-decrypt.c
index 374684388c..95fdc64fb0 100644
--- a/tests/rsa-encrypt-decrypt.c
+++ b/tests/rsa-encrypt-decrypt.c
@@ -165,6 +165,15 @@ void doit(void)
 		if (memcmp(out2.data, hash_data.data, hash_data.size) != 0)
 			fail("Decrypted data don't match original (2)\n");
 
+                /* try again with fixed length API */
+                memset(out2.data, 'A', out2.size);
+		ret = gnutls_privkey_decrypt_data2(privkey, 0, &out, out2.data, out2.size);
+		if (ret < 0)
+			fail("gnutls_privkey_decrypt_data\n");
+
+		if (memcmp(out2.data, hash_data.data, hash_data.size) != 0)
+			fail("Decrypted data don't match original (2b)\n");
+
 		gnutls_free(out.data);
 		gnutls_free(out2.data);
 
@@ -183,6 +192,15 @@ void doit(void)
 		if (memcmp(out2.data, raw_data.data, raw_data.size) != 0)
 			fail("Decrypted data don't match original (4)\n");
 
+                /* try again with fixed length API */
+                memset(out2.data, 'A', out2.size);
+		ret = gnutls_privkey_decrypt_data2(privkey, 0, &out, out2.data, out2.size);
+		if (ret < 0)
+			fail("gnutls_privkey_decrypt_data\n");
+
+		if (memcmp(out2.data, raw_data.data, raw_data.size) != 0)
+			fail("Decrypted data don't match original (4b)\n");
+
 		if (debug)
 			success("ok\n");