Merge pull request #1136 from yanesca/fix-marvin-attack-backport
Fix for the Marvin attack - BACKPORT
diff --git a/ChangeLog.d/fix-Marvin-attack.txt b/ChangeLog.d/fix-Marvin-attack.txt
new file mode 100644
index 0000000..017f7b1
--- /dev/null
+++ b/ChangeLog.d/fix-Marvin-attack.txt
@@ -0,0 +1,6 @@
+Security
+ * Fix a timing side channel in RSA private operations. This side channel
+ could be sufficient for a local attacker to recover the plaintext. It
+ requires the attacker to send a large number of messages for decryption.
+ For details, see "Everlasting ROBOT: the Marvin Attack", Hubert Kario.
+ Reported by Hubert Kario, Red Hat.
diff --git a/include/mbedtls/rsa.h b/include/mbedtls/rsa.h
index 667e625..1779775 100644
--- a/include/mbedtls/rsa.h
+++ b/include/mbedtls/rsa.h
@@ -712,6 +712,10 @@
* It is the generic wrapper for performing a PKCS#1 decryption
* operation using the \p mode from the context.
*
+ * \warning When \p ctx->padding is set to #MBEDTLS_RSA_PKCS_V15,
+ * mbedtls_rsa_rsaes_pkcs1_v15_decrypt() is called, which is an
+ * inherently dangerous function (CWE-242).
+ *
* \note The output buffer length \c output_max_len should be
* as large as the size \p ctx->len of \p ctx->N (for example,
* 128 Bytes if RSA-1024 is used) to be able to hold an
@@ -761,6 +765,11 @@
* \brief This function performs a PKCS#1 v1.5 decryption
* operation (RSAES-PKCS1-v1_5-DECRYPT).
*
+ * \warning This is an inherently dangerous function (CWE-242). Unless
+ * it is used in a side channel free and safe way (eg.
+ * implementing the TLS protocol as per 7.4.7.1 of RFC 5246),
+ * the calling code is vulnerable.
+ *
* \note The output buffer length \c output_max_len should be
* as large as the size \p ctx->len of \p ctx->N, for example,
* 128 Bytes if RSA-1024 is used, to be able to hold an
diff --git a/include/psa/crypto_values.h b/include/psa/crypto_values.h
index a398249..c25fda6 100644
--- a/include/psa/crypto_values.h
+++ b/include/psa/crypto_values.h
@@ -1659,6 +1659,13 @@
0)
/** RSA PKCS#1 v1.5 encryption.
+ *
+ * \warning Calling psa_asymmetric_decrypt() with this algorithm as a
+ * parameter is considered an inherently dangerous function
+ * (CWE-242). Unless it is used in a side channel free and safe
+ * way (eg. implementing the TLS protocol as per 7.4.7.1 of
+ * RFC 5246), the calling code is vulnerable.
+ *
*/
#define PSA_ALG_RSA_PKCS1V15_CRYPT ((psa_algorithm_t) 0x07000200)
diff --git a/library/bignum.c b/library/bignum.c
index 3e1c48c..fadd9e9 100644
--- a/library/bignum.c
+++ b/library/bignum.c
@@ -30,6 +30,7 @@
#include "mbedtls/platform_util.h"
#include "mbedtls/error.h"
#include "constant_time_internal.h"
+#include "bignum_internal.h"
#include <limits.h>
#include <string.h>
@@ -1907,48 +1908,24 @@
/*
* Fast Montgomery initialization (thanks to Tom St Denis)
*/
-static void mpi_montg_init(mbedtls_mpi_uint *mm, const mbedtls_mpi *N)
+mbedtls_mpi_uint mbedtls_mpi_montmul_init(const mbedtls_mpi_uint *N)
{
- mbedtls_mpi_uint x, m0 = N->p[0];
- unsigned int i;
+ mbedtls_mpi_uint x = N[0];
- x = m0;
- x += ((m0 + 2) & 4) << 1;
+ x += ((N[0] + 2) & 4) << 1;
- for (i = biL; i >= 8; i /= 2) {
- x *= (2 - (m0 * x));
+ for (unsigned int i = biL; i >= 8; i /= 2) {
+ x *= (2 - (N[0] * x));
}
- *mm = ~x + 1;
+ return ~x + 1;
}
-/** Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
- *
- * \param[in,out] A One of the numbers to multiply.
- * It must have at least as many limbs as N
- * (A->n >= N->n), and any limbs beyond n are ignored.
- * On successful completion, A contains the result of
- * the multiplication A * B * R^-1 mod N where
- * R = (2^ciL)^n.
- * \param[in] B One of the numbers to multiply.
- * It must be nonzero and must not have more limbs than N
- * (B->n <= N->n).
- * \param[in] N The modulo. N must be odd.
- * \param mm The value calculated by `mpi_montg_init(&mm, N)`.
- * This is -N^-1 mod 2^ciL.
- * \param[in,out] T A bignum for temporary storage.
- * It must be at least twice the limb size of N plus 2
- * (T->n >= 2 * (N->n + 1)).
- * Its initial content is unused and
- * its final content is indeterminate.
- * Note that unlike the usual convention in the library
- * for `const mbedtls_mpi*`, the content of T can change.
- */
-static void mpi_montmul(mbedtls_mpi *A,
- const mbedtls_mpi *B,
- const mbedtls_mpi *N,
- mbedtls_mpi_uint mm,
- const mbedtls_mpi *T)
+void mbedtls_mpi_montmul(mbedtls_mpi *A,
+ const mbedtls_mpi *B,
+ const mbedtls_mpi *N,
+ mbedtls_mpi_uint mm,
+ const mbedtls_mpi *T)
{
size_t i, n, m;
mbedtls_mpi_uint u0, u1, *d;
@@ -1996,7 +1973,8 @@
/*
* Montgomery reduction: A = A * R^-1 mod N
*
- * See mpi_montmul() regarding constraints and guarantees on the parameters.
+ * See mbedtls_mpi_montmul() regarding constraints and guarantees on the
+ * parameters.
*/
static void mpi_montred(mbedtls_mpi *A, const mbedtls_mpi *N,
mbedtls_mpi_uint mm, const mbedtls_mpi *T)
@@ -2007,7 +1985,7 @@
U.n = U.s = (int) z;
U.p = &z;
- mpi_montmul(A, &U, N, mm, T);
+ mbedtls_mpi_montmul(A, &U, N, mm, T);
}
/**
@@ -2039,6 +2017,20 @@
return ret;
}
+int mbedtls_mpi_get_mont_r2_unsafe(mbedtls_mpi *X,
+ const mbedtls_mpi *N)
+{
+ int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
+
+ MBEDTLS_MPI_CHK(mbedtls_mpi_lset(X, 1));
+ MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(X, N->n * 2 * biL));
+ MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(X, X, N));
+ MBEDTLS_MPI_CHK(mbedtls_mpi_shrink(X, N->n));
+
+cleanup:
+ return ret;
+}
+
/*
* Sliding-window exponentiation: X = A^E mod N (HAC 14.85)
*/
@@ -2076,7 +2068,7 @@
/*
* Init temps and window size
*/
- mpi_montg_init(&mm, N);
+ mm = mbedtls_mpi_montmul_init(N->p);
mbedtls_mpi_init(&RR); mbedtls_mpi_init(&T);
mbedtls_mpi_init(&Apos);
mbedtls_mpi_init(&WW);
@@ -2130,10 +2122,10 @@
j = N->n + 1;
/* All W[i] including the accumulator must have at least N->n limbs for
- * the mpi_montmul() and mpi_montred() calls later. Here we ensure that
- * W[1] and the accumulator W[x_index] are large enough. later we'll grow
- * other W[i] to the same length. They must not be shrunk midway through
- * this function!
+ * the mbedtls_mpi_montmul() and mpi_montred() calls later. Here we ensure
+ * that W[1] and the accumulator W[x_index] are large enough. later we'll
+ * grow other W[i] to the same length. They must not be shrunk midway
+ * through this function!
*/
MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&W[x_index], j));
MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&W[1], j));
@@ -2153,9 +2145,7 @@
* If 1st call, pre-compute R^2 mod N
*/
if (prec_RR == NULL || prec_RR->p == NULL) {
- MBEDTLS_MPI_CHK(mbedtls_mpi_lset(&RR, 1));
- MBEDTLS_MPI_CHK(mbedtls_mpi_shift_l(&RR, N->n * 2 * biL));
- MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&RR, &RR, N));
+ mbedtls_mpi_get_mont_r2_unsafe(&RR, N);
if (prec_RR != NULL) {
memcpy(prec_RR, &RR, sizeof(mbedtls_mpi));
@@ -2171,7 +2161,7 @@
MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&W[1], A, N));
/* This should be a no-op because W[1] is already that large before
* mbedtls_mpi_mod_mpi(), but it's necessary to avoid an overflow
- * in mpi_montmul() below, so let's make sure. */
+ * in mbedtls_mpi_montmul() below, so let's make sure. */
MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&W[1], N->n + 1));
} else {
MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&W[1], A));
@@ -2179,7 +2169,7 @@
/* Note that this is safe because W[1] always has at least N->n limbs
* (it grew above and was preserved by mbedtls_mpi_copy()). */
- mpi_montmul(&W[1], &RR, N, mm, &T);
+ mbedtls_mpi_montmul(&W[1], &RR, N, mm, &T);
/*
* W[x_index] = R^2 * R^-1 mod N = R mod N
@@ -2205,7 +2195,7 @@
MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&W[j], &W[1]));
for (i = 0; i < window_bitsize - 1; i++) {
- mpi_montmul(&W[j], &W[j], N, mm, &T);
+ mbedtls_mpi_montmul(&W[j], &W[j], N, mm, &T);
}
/*
@@ -2215,7 +2205,7 @@
MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&W[i], N->n + 1));
MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&W[i], &W[i - 1]));
- mpi_montmul(&W[i], &W[1], N, mm, &T);
+ mbedtls_mpi_montmul(&W[i], &W[1], N, mm, &T);
}
}
@@ -2251,7 +2241,7 @@
* out of window, square W[x_index]
*/
MBEDTLS_MPI_CHK(mpi_select(&WW, W, w_table_used_size, x_index));
- mpi_montmul(&W[x_index], &WW, N, mm, &T);
+ mbedtls_mpi_montmul(&W[x_index], &WW, N, mm, &T);
continue;
}
@@ -2270,7 +2260,7 @@
for (i = 0; i < window_bitsize; i++) {
MBEDTLS_MPI_CHK(mpi_select(&WW, W, w_table_used_size,
x_index));
- mpi_montmul(&W[x_index], &WW, N, mm, &T);
+ mbedtls_mpi_montmul(&W[x_index], &WW, N, mm, &T);
}
/*
@@ -2278,7 +2268,7 @@
*/
MBEDTLS_MPI_CHK(mpi_select(&WW, W, w_table_used_size,
exponent_bits_in_window));
- mpi_montmul(&W[x_index], &WW, N, mm, &T);
+ mbedtls_mpi_montmul(&W[x_index], &WW, N, mm, &T);
state--;
nbits = 0;
@@ -2291,13 +2281,13 @@
*/
for (i = 0; i < nbits; i++) {
MBEDTLS_MPI_CHK(mpi_select(&WW, W, w_table_used_size, x_index));
- mpi_montmul(&W[x_index], &WW, N, mm, &T);
+ mbedtls_mpi_montmul(&W[x_index], &WW, N, mm, &T);
exponent_bits_in_window <<= 1;
if ((exponent_bits_in_window & ((size_t) 1 << window_bitsize)) != 0) {
MBEDTLS_MPI_CHK(mpi_select(&WW, W, w_table_used_size, 1));
- mpi_montmul(&W[x_index], &WW, N, mm, &T);
+ mbedtls_mpi_montmul(&W[x_index], &WW, N, mm, &T);
}
}
diff --git a/library/bignum_internal.h b/library/bignum_internal.h
new file mode 100644
index 0000000..5435ebb
--- /dev/null
+++ b/library/bignum_internal.h
@@ -0,0 +1,71 @@
+/**
+ * Low level bignum functions
+ *
+ * Copyright The Mbed TLS Contributors
+ * SPDX-License-Identifier: Apache-2.0 OR GPL-2.0-or-later
+ */
+
+#ifndef MBEDTLS_BIGNUM_INTERNAL_H
+#define MBEDTLS_BIGNUM_INTERNAL_H
+
+#include "mbedtls/bignum.h"
+
+/**
+ * \brief Calculate the square of the Montgomery constant. (Needed
+ * for conversion and operations in Montgomery form.)
+ *
+ * \param[out] X A pointer to the result of the calculation of
+ * the square of the Montgomery constant:
+ * 2^{2*n*biL} mod N.
+ * \param[in] N Little-endian presentation of the modulus, which must be odd.
+ *
+ * \return 0 if successful.
+ * \return #MBEDTLS_ERR_MPI_ALLOC_FAILED if there is not enough space
+ * to store the value of Montgomery constant squared.
+ * \return #MBEDTLS_ERR_MPI_DIVISION_BY_ZERO if \p N modulus is zero.
+ * \return #MBEDTLS_ERR_MPI_NEGATIVE_VALUE if \p N modulus is negative.
+ */
+int mbedtls_mpi_get_mont_r2_unsafe(mbedtls_mpi *X,
+ const mbedtls_mpi *N);
+
+/**
+ * \brief Calculate initialisation value for fast Montgomery modular
+ * multiplication
+ *
+ * \param[in] N Little-endian presentation of the modulus. This must have
+ * at least one limb.
+ *
+ * \return The initialisation value for fast Montgomery modular multiplication
+ */
+mbedtls_mpi_uint mbedtls_mpi_montmul_init(const mbedtls_mpi_uint *N);
+
+/** Montgomery multiplication: A = A * B * R^-1 mod N (HAC 14.36)
+ *
+ * \param[in,out] A One of the numbers to multiply.
+ * It must have at least as many limbs as N
+ * (A->n >= N->n), and any limbs beyond n are ignored.
+ * On successful completion, A contains the result of
+ * the multiplication A * B * R^-1 mod N where
+ * R = (2^ciL)^n.
+ * \param[in] B One of the numbers to multiply.
+ * It must be nonzero and must not have more limbs than N
+ * (B->n <= N->n).
+ * \param[in] N The modulo. N must be odd.
+ * \param mm The value calculated by
+ * `mbedtls_mpi_montg_init(&mm, N)`.
+ * This is -N^-1 mod 2^ciL.
+ * \param[in,out] T A bignum for temporary storage.
+ * It must be at least twice the limb size of N plus 2
+ * (T->n >= 2 * (N->n + 1)).
+ * Its initial content is unused and
+ * its final content is indeterminate.
+ * Note that unlike the usual convention in the library
+ * for `const mbedtls_mpi*`, the content of T can change.
+ */
+void mbedtls_mpi_montmul(mbedtls_mpi *A,
+ const mbedtls_mpi *B,
+ const mbedtls_mpi *N,
+ mbedtls_mpi_uint mm,
+ const mbedtls_mpi *T);
+
+#endif /* MBEDTLS_BIGNUM_INTERNAL_H */
diff --git a/library/rsa.c b/library/rsa.c
index 84403c4..0a0c2e3 100644
--- a/library/rsa.c
+++ b/library/rsa.c
@@ -34,6 +34,7 @@
#include "mbedtls/error.h"
#include "constant_time_internal.h"
#include "mbedtls/constant_time.h"
+#include "bignum_internal.h"
#include <string.h>
@@ -805,6 +806,46 @@
}
/*
+ * Unblind
+ * T = T * Vf mod N
+ */
+static int rsa_unblind(mbedtls_mpi *T, mbedtls_mpi *Vf, const mbedtls_mpi *N)
+{
+ int ret = MBEDTLS_ERR_ERROR_CORRUPTION_DETECTED;
+ const size_t nlimbs = N->n;
+ const size_t tlimbs = 2 * (nlimbs + 1);
+
+ mbedtls_mpi_uint mm = mbedtls_mpi_montmul_init(N->p);
+
+ mbedtls_mpi RR, M_T;
+
+ mbedtls_mpi_init(&RR);
+ mbedtls_mpi_init(&M_T);
+
+ MBEDTLS_MPI_CHK(mbedtls_mpi_get_mont_r2_unsafe(&RR, N));
+ MBEDTLS_MPI_CHK(mbedtls_mpi_grow(&M_T, tlimbs));
+
+ MBEDTLS_MPI_CHK(mbedtls_mpi_grow(T, nlimbs));
+ MBEDTLS_MPI_CHK(mbedtls_mpi_grow(Vf, nlimbs));
+
+ /* T = T * Vf mod N
+ * Reminder: montmul(A, B, N) = A * B * R^-1 mod N
+ * Usually both operands are multiplied by R mod N beforehand, yielding a
+ * result that's also * R mod N (aka "in the Montgomery domain"). Here we
+ * only multiply one operand by R mod N, so the result is directly what we
+ * want - no need to call `mpi_montred()` on it. */
+ mbedtls_mpi_montmul(T, &RR, N, mm, &M_T);
+ mbedtls_mpi_montmul(T, Vf, N, mm, &M_T);
+
+cleanup:
+
+ mbedtls_mpi_free(&RR);
+ mbedtls_mpi_free(&M_T);
+
+ return ret;
+}
+
+/*
* Exponent blinding supposed to prevent side-channel attacks using multiple
* traces of measurements to recover the RSA key. The more collisions are there,
* the more bits of the key can be recovered. See [3].
@@ -867,7 +908,7 @@
/* Temporaries holding the initial input and the double
* checked result; should be the same in the end. */
- mbedtls_mpi I, C;
+ mbedtls_mpi input_blinded, check_result_blinded;
RSA_VALIDATE_RET(ctx != NULL);
RSA_VALIDATE_RET(input != NULL);
@@ -904,8 +945,8 @@
mbedtls_mpi_init(&TP); mbedtls_mpi_init(&TQ);
#endif
- mbedtls_mpi_init(&I);
- mbedtls_mpi_init(&C);
+ mbedtls_mpi_init(&input_blinded);
+ mbedtls_mpi_init(&check_result_blinded);
/* End of MPI initialization */
@@ -915,8 +956,6 @@
goto cleanup;
}
- MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&I, &T));
-
if (f_rng != NULL) {
/*
* Blinding
@@ -968,6 +1007,9 @@
#endif /* MBEDTLS_RSA_NO_CRT */
}
+ /* Make a copy of the input (after blinding if there was any) */
+ MBEDTLS_MPI_CHK(mbedtls_mpi_copy(&input_blinded, &T));
+
#if defined(MBEDTLS_RSA_NO_CRT)
MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&T, &T, D, &ctx->N, &ctx->RN));
#else
@@ -995,21 +1037,20 @@
MBEDTLS_MPI_CHK(mbedtls_mpi_add_mpi(&T, &TQ, &TP));
#endif /* MBEDTLS_RSA_NO_CRT */
+ /* Verify the result to prevent glitching attacks. */
+ MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&check_result_blinded, &T, &ctx->E,
+ &ctx->N, &ctx->RN));
+ if (mbedtls_mpi_cmp_mpi(&check_result_blinded, &input_blinded) != 0) {
+ ret = MBEDTLS_ERR_RSA_VERIFY_FAILED;
+ goto cleanup;
+ }
+
if (f_rng != NULL) {
/*
* Unblind
* T = T * Vf mod N
*/
- MBEDTLS_MPI_CHK(mbedtls_mpi_mul_mpi(&T, &T, &ctx->Vf));
- MBEDTLS_MPI_CHK(mbedtls_mpi_mod_mpi(&T, &T, &ctx->N));
- }
-
- /* Verify the result to prevent glitching attacks. */
- MBEDTLS_MPI_CHK(mbedtls_mpi_exp_mod(&C, &T, &ctx->E,
- &ctx->N, &ctx->RN));
- if (mbedtls_mpi_cmp_mpi(&C, &I) != 0) {
- ret = MBEDTLS_ERR_RSA_VERIFY_FAILED;
- goto cleanup;
+ MBEDTLS_MPI_CHK(rsa_unblind(&T, &ctx->Vf, &ctx->N));
}
olen = ctx->len;
@@ -1041,8 +1082,8 @@
mbedtls_mpi_free(&TP); mbedtls_mpi_free(&TQ);
#endif
- mbedtls_mpi_free(&C);
- mbedtls_mpi_free(&I);
+ mbedtls_mpi_free(&check_result_blinded);
+ mbedtls_mpi_free(&input_blinded);
if (ret != 0 && ret >= -0x007f) {
return MBEDTLS_ERROR_ADD(MBEDTLS_ERR_RSA_PRIVATE_FAILED, ret);
diff --git a/visualc/VS2010/mbedTLS.vcxproj b/visualc/VS2010/mbedTLS.vcxproj
index 1ffc1f6..18b613e 100644
--- a/visualc/VS2010/mbedTLS.vcxproj
+++ b/visualc/VS2010/mbedTLS.vcxproj
@@ -260,6 +260,7 @@
<ClInclude Include="..\..\tests\include\test\drivers\signature.h" />
<ClInclude Include="..\..\tests\include\test\drivers\size.h" />
<ClInclude Include="..\..\tests\include\test\drivers\test_driver.h" />
+ <ClInclude Include="..\..\library\bignum_internal.h" />
<ClInclude Include="..\..\library\check_crypto_config.h" />
<ClInclude Include="..\..\library\common.h" />
<ClInclude Include="..\..\library\constant_time_internal.h" />