This is about a timing leak in the topmost limb
of the internal result of RSA_private_decrypt,
before the padding check.
There are in fact at least three bugs together that
caused the timing leak:
First and probably most important is the fact that
the blinding did not use the constant time code path
at all when the RSA object was used for a private
decrypt, due to the fact that the Montgomery context
rsa->_method_mod_n was not set up early enough in
rsa_ossl_private_decrypt, when BN_BLINDING_create_param
needed it, and that was persisted as blinding->m_ctx,
although the RSA object creates the Montgomery context
just a bit later.
Then the infamous bn_correct_top was used on the
secret value right after the blinding was removed.
And finally the function BN_bn2binpad did not use
the constant-time code path since the BN_FLG_CONSTTIME
was not set on the secret value.
In order to address the first problem, this patch
makes sure that the rsa->_method_mod_n is initialized
right before the blinding context.
And to fix the second problem, we add a new utility
function bn_correct_top_consttime, a const-time
variant of bn_correct_top.
Together with the fact, that BN_bn2binpad is already
constant time if the flag BN_FLG_CONSTTIME is set,
this should eliminate the timing oracle completely.
In addition the no-asm variant may also have
branches that depend on secret values, because the last
invocation of bn_sub_words in bn_from_montgomery_word
had branches when the function is compiled by certain
gcc compiler versions, due to the clumsy coding style.
So additionally this patch stream-lined the no-asm
C-code in order to avoid branches where possible and
improve the resulting code quality.
Reviewed-by: Paul Dale <pauli@openssl.org>
Reviewed-by: Tomas Mraz <tomas@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/20284)
This reverts commit 43d8f88511991533f53680a751e9326999a6a31f.
Reviewed-by: Paul Dale <pauli@openssl.org>
Reviewed-by: Tomas Mraz <tomas@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/20284)
_umul128() is x86_64 (x64) only, while __umulh() works everywhere, but
doesn't generate optimal code on x64
Reviewed-by: Dmitry Belyavskiy <beldmit@gmail.com>
Reviewed-by: Paul Dale <pauli@openssl.org>
Reviewed-by: Tomas Mraz <tomas@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/20244)
(cherry picked from commit 075652f224479dad2e64b92e791b296177af8705)
A timing based side channel exists in the OpenSSL RSA Decryption
implementation which could be sufficient to recover a plaintext across
a network in a Bleichenbacher style attack. To achieve a successful
decryption an attacker would have to be able to send a very large number
of trial messages for decryption. The vulnerability affects all RSA
padding modes: PKCS#1 v1.5, RSA-OEAP and RSASVE.
Patch written by Dmitry Belyavsky and Hubert Kario
CVE-2022-4304
Reviewed-by: Dmitry Belyavskiy <beldmit@gmail.com>
Reviewed-by: Tomas Mraz <tomas@openssl.org>
Otherwise the alloca can cause an exception.
Issue reported by Jiayi Lin.
Reviewed-by: Tomas Mraz <tomas@openssl.org>
Reviewed-by: Paul Dale <pauli@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/19735)
As of clang-14 the strict aliasing is causing code to magically disappear.
By explicitly inlining the code, the aliasing problem evaporates.
Fixes#18225
Backport of #18258 to 1.1.1.
Reviewed-by: Hugo Landau <hlandau@openssl.org>
Reviewed-by: Tomas Mraz <tomas@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/18948)
BN_one() uses the expand function which calls malloc which may fail.
All other places that reference BN_one() check the return value.
The issue is triggered by a memory allocation failure.
Detected by PR #18355
Reviewed-by: Tomas Mraz <tomas@openssl.org>
Reviewed-by: Paul Dale <pauli@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/18697)
(cherry picked from commit 7fe7cc57af3db1e497877f0329ba17609b2efc8b)
Inspired by BoringSSL fix by David Benjamin.
Reviewed-by: Matt Caswell <matt@openssl.org>
Reviewed-by: Paul Dale <pauli@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/18511)
This partially fixes a bug where, on x86_64, BN_mod_exp_mont_consttime
would sometimes return m, the modulus, when it should have returned
zero. Thanks to Guido Vranken for reporting it. It is only a partial fix
because the same bug also exists in the "rsaz" codepath.
The bug only affects zero outputs (with non-zero inputs), so we believe
it has no security impact on our cryptographic functions.
The fx is to delete lowercase bn_from_montgomery altogether, and have the
mont5 path use the same BN_from_montgomery ending as the non-mont5 path.
This only impacts the final step of the whole exponentiation and has no
measurable perf impact.
See the original BoringSSL commit
https://boringssl.googlesource.com/boringssl/+/13c9d5c69d04485a7a8840c12185c832026c8315
for further analysis.
Original-author: David Benjamin <davidben@google.com>
Reviewed-by: Matt Caswell <matt@openssl.org>
Reviewed-by: Paul Dale <pauli@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/18511)
Fixes#18010.
Reviewed-by: Matt Caswell <matt@openssl.org>
Reviewed-by: Paul Dale <pauli@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/18034)
(cherry picked from commit bc6bac8561ead83d6135f376ffcbbb0b657e64fe)
The calculation in some cases does not finish for non-prime p.
This fixes CVE-2022-0778.
Based on patch by David Benjamin <davidben@google.com>.
Reviewed-by: Paul Dale <pauli@openssl.org>
Reviewed-by: Matt Caswell <matt@openssl.org>
This fixes a bug whereby BN_mod_exp2_mont can dereference a NULL pointer
if BIGNUM argument m represents zero.
Regression test added. Fixes#17648. Backport from master to 1.1.
Reviewed-by: Matt Caswell <matt@openssl.org>
Reviewed-by: Todd Short <todd.short@me.com>
Reviewed-by: Tomas Mraz <tomas@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/17787)
bn_sqr_comba8 does for instance compute a wrong result for the value:
a=0x4aaac919 62056c84 fba7334e 1a6be678 022181ba fd3aa878 899b2346 ee210f45
The correct result is:
r=0x15c72e32 605a3061 d11b1012 3c187483 6df96999 bd0c22ba d3e7d437 4724a82f
912c5e61 6a187efe 8f7c47fc f6945fe5 75be8e3d 97ed17d4 7950b465 3cb32899
but the actual result was:
r=0x15c72e32 605a3061 d11b1012 3c187483 6df96999 bd0c22ba d3e7d437 4724a82f
912c5e61 6a187efe 8f7c47fc f6945fe5 75be8e3c 97ed17d4 7950b465 3cb32899
so the forth word of the result was 0x75be8e3c but should have been
0x75be8e3d instead.
Likewise bn_sqr_comba4 has an identical bug for the same value as well:
a=0x022181ba fd3aa878 899b2346 ee210f45
correct result:
r=0x00048a69 9fe82f8b 62bd2ed1 88781335 75be8e3d 97ed17d4 7950b465 3cb32899
wrong result:
r=0x00048a69 9fe82f8b 62bd2ed1 88781335 75be8e3c 97ed17d4 7950b465 3cb32899
Fortunately the bn_mul_comba4/8 code paths are not affected.
Also the mips64 target does in fact not handle the carry propagation
correctly.
Example:
a=0x4aaac91900000000 62056c8400000000 fba7334e00000000 1a6be67800000000
022181ba00000000 fd3aa87800000000 899b234635dad283 ee210f4500000001
correct result:
r=0x15c72e32272c4471 392debf018c679c8 b85496496bf8254c d0204f36611e2be1
0cdb3db8f3c081d8 c94ba0e1bacc5061 191b83d47ff929f6 5be0aebfc13ae68d
3eea7a7fdf2f5758 42f7ec656cab3cb5 6a28095be34756f2 64f24687bf37de06
2822309cd1d292f9 6fa698c972372f09 771e97d3a868cda0 dc421e8a00000001
wrong result:
r=0x15c72e32272c4471 392debf018c679c8 b85496496bf8254c d0204f36611e2be1
0cdb3db8f3c081d8 c94ba0e1bacc5061 191b83d47ff929f6 5be0aebfc13ae68d
3eea7a7fdf2f5758 42f7ec656cab3cb5 6a28095be34756f2 64f24687bf37de06
2822309cd1d292f8 6fa698c972372f09 771e97d3a868cda0 dc421e8a00000001
Reviewed-by: Paul Dale <pauli@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/17258)
(cherry picked from commit 336923c0c8d705cb8af5216b29a205662db0d590)
There is a problem that appears when calling BN_div(a, c, a, b) with negative b.
In this case, the sign of the remainder c is incorrect. The problem only
occurs if the dividend and the quotient are the same BIGNUM.
Fixes#15982
Reviewed-by: Nicola Tuveri <nic.tuv@gmail.com>
(Merged from https://github.com/openssl/openssl/pull/15991)
(cherry picked from commit 105c83150f15af3f78ea0758859062842bdbe30e)
For example, FreeBSD prepends "FreeBSD" to version string, e.g.,
FreeBSD clang version 11.0.0 (git@github.com:llvm/llvm-project.git llvmorg-11.0.0-rc2-0-g414f32a9e86)
Target: x86_64-unknown-freebsd13.0
Thread model: posix
InstalledDir: /usr/bin
This prevented us from properly detecting AVX support, etc.
CLA: trivial
Reviewed-by: Richard Levitte <levitte@openssl.org>
Reviewed-by: Paul Dale <paul.dale@oracle.com>
Reviewed-by: Ben Kaduk <kaduk@mit.edu>
(Merged from https://github.com/openssl/openssl/pull/12725)
(cherry picked from commit cd84d8832d274357a5ba5433640d7ef76691b1ac)
Closes#12129
As described in https://github.com/openssl/openssl/issues/12129 the
readability of the internal functions providing the two alternative
implementations for `BN_mod_inverse()` is a bit lacking.
Both these functions are now completely internal, so we have the
flexibility needed to slightly improve readability and remove
unnecessary NULL checks.
The main changes here are:
- rename `BN_mod_inverse_no_branch()` as `bn_mod_inverse_no_branch()`:
this function is `static` so it is not even visible within the rest of
libcrypto. By convention upcase prefixes are reserved for public
functions.
- remove `if (pnoinv == NULL)` checks in `int_bn_mod_inverse()`: this
function is internal to the BN module and we can guarantee that all
callers pass non-NULL arguments.
- `bn_mod_inverse_no_branch()` takes an extra `int *pnoinv` argument, so
that it can signal if no inverse exists for the given inputs: in this
way the caller is in charge of raising `BN_R_NO_INVERSE` as it is the
case for the non-consttime implementation of `int_bn_mod_inverse()`.
- `BN_mod_inverse()` is a public function and must guarantee that the
internal functions providing the actual implementation receive valid
arguments. If the caller passes a NULL `BN_CTX` we create a temporary
one for internal use.
- reorder function definitions in `crypto/bn/bn_gcd.c` to avoid forward
declaration of `static` functions (in preparation for inlining)
- inline `bn_mod_inverse_no_branch()`.
(Backport to 1.1.1 from https://github.com/openssl/openssl/pull/12142)
(cherry picked from commit 5d8b3a3ef2941b8822523742a0408ca6896aa65d)
Reviewed-by: Tomas Mraz <tmraz@fedoraproject.org>
(Merged from https://github.com/openssl/openssl/pull/12169)
Although there are platforms where int is 64 bit, 2GiB large BIGNUMs
instead of 4GiB should be "big enough for everybody".
Reviewed-by: Richard Levitte <levitte@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/11857)
(cherry picked from commit 1d05eb55caa8965a151360c2469c463ecd990987)
`BN_copy()` (and indirectly `BN_dup()`) do not propagate the
`BN_FLG_CONSTTIME` flag: the propagation has been turned on and off a
few times in the past years, because in some conditions it has shown
unintended consequences in some code paths.
Without turning the propagation on once more, we can still improve
`BN_copy()` by avoiding to leak `src->top` in case `src` is flagged with
`BN_FLG_CONSTTIME`.
In this case we can instead use `src->dmax` as the number of words
allocated for `dst` and for the `memcpy` operation.
Barring compiler or runtime optimizations, if the caller provides `src`
flagged as const time and preallocated to a public size, no leak should
happen due to the copy operation.
(cherry picked from commit 2d9167ed0b588dacbdd0303fb6041ffe1d8b3a92)
Reviewed-by: Matt Caswell <matt@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/11127)
This should avoid half of the trial divisions in probable_prime_dh_safe
and avoid bn_probable_prime_dh generating primes with special properties.
Reviewed-by: Tomas Mraz <tmraz@fedoraproject.org>
(Merged from https://github.com/openssl/openssl/pull/9387)
If one of the perlasm xlate drivers crashes, OpenSSL's build will
currently swallow the error and silently truncate the output to however
far the driver got. This will hopefully fail to build, but better to
check such things.
Handle this by checking for errors when closing STDOUT (which is a pipe
to the xlate driver).
This is the OpenSSL 1.1.1 version of
https://github.com/openssl/openssl/pull/10883 and
https://github.com/openssl/openssl/pull/10930.
Reviewed-by: Mark J. Cox <mark@awe.com>
Reviewed-by: Paul Dale David Benjamin <davidben@google.com>
(Merged from https://github.com/openssl/openssl/pull/10931)
Configure creates an empty crypto/include which
gets not cleaned up with make distclean.
Reviewed-by: Richard Levitte <levitte@openssl.org>
Reviewed-by: Matthias St. Pierre <Matthias.St.Pierre@ncp-e.com>
(Merged from https://github.com/openssl/openssl/pull/10893)
The New Year has caused various files to appear out of date to "make
update". This causes Travis to fail. Therefore we update those files.
Reviewed-by: Matthias St. Pierre <Matthias.St.Pierre@ncp-e.com>
(Merged from https://github.com/openssl/openssl/pull/10739)
We have always a carry in %rcx or %rbx in range 0..2
from the previous stage, that is added to the result
of the 64-bit square, but the low nibble of any square
can only be 0, 1, 4, 9.
Therefore one "adcq $0, %rdx" can be removed.
Likewise in the ADX code we can remove one
"adcx %rbp, $out" since %rbp is always 0, and carry is
also zero, therefore that is a no-op.
Reviewed-by: Paul Dale <paul.dale@oracle.com>
(Merged from https://github.com/openssl/openssl/pull/10575)
There is an overflow bug in the x64_64 Montgomery squaring procedure used in
exponentiation with 512-bit moduli. No EC algorithms are affected. Analysis
suggests that attacks against 2-prime RSA1024, 3-prime RSA1536, and DSA1024 as a
result of this defect would be very difficult to perform and are not believed
likely. Attacks against DH512 are considered just feasible. However, for an
attack the target would have to re-use the DH512 private key, which is not
recommended anyway. Also applications directly using the low level API
BN_mod_exp may be affected if they use BN_FLG_CONSTTIME.
CVE-2019-1551
Reviewed-by: Paul Dale <paul.dale@oracle.com>
Reviewed-by: Bernd Edlinger <bernd.edlinger@hotmail.de>
(Merged from https://github.com/openssl/openssl/pull/10575)
Signed-off-by: Patrick Steuer <patrick.steuer@de.ibm.com>
Reviewed-by: Paul Dale <paul.dale@oracle.com>
(Merged from https://github.com/openssl/openssl/pull/10454)
(cherry picked from commit 97a986f78289fef71bf8778dc4763458e983750c)
clang imposes some restrictions on the assembler code that
gcc does not.
Signed-off-by: Patrick Steuer <patrick.steuer@de.ibm.com>
Reviewed-by: Richard Levitte <levitte@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/10330)
(cherry picked from commit 6f93f06135cbbd36c3fe98d63717e8303a5d559b)
Conflicts:
crypto/perlasm/s390x.pm (non-existant)
crypto/s390xcpuid.pl (code to be changed non-existant)
