| Age | Commit message (Collapse) | Author |
|---|
|
|
|
|
|
This code is full of problematic C and is also otherwise of questionable
quality. It is far from constant time and jsing informs me it also isn't
faster. Good riddance.
|
|
|
|
|
|
ok jsing
|
|
ok jsing
|
|
ok jsing
|
|
ok jsing, and kind of tb an earlier version
|
|
Pull a number of invariants into variables, which avoids repeated loading
from memory on architectures where sufficient registers are available.
Also keep track of the per-iteration carry in a variable, rather than
unnecessarily reading from and writing to memory.
This gives a reasonable performance gain on some architectures (e.g. armv7)
|
|
ok tb@
|
|
|
|
No functional change.
|
|
|
|
This removes a bunch of incomplete and scary code, which potentially leaks
secrets and is not constant time. A performance gain is achieved on arm64
for sizes that we care about, while a minimal decrease in performance is
noted for larger sizes on some other platforms.
While we will potentially reimplement Karatsuba (or Toom-Cook) at a later
date, it will be easier and safer to do it from a clean slate.
ok tb@
|
|
No functional change.
|
|
|
|
This supports a mostly forgotten, seemingly unused and long retired
standard. No need for this in our public API Dyson sphere.
ok jsing
|
|
This is unused outside of the library and could do with some reworking.
That's easier without having to care about outside consumers.
ok jsing
|
|
With the corresponding structs now being opaque, the only thing they are
good for outside the library are memory leaks. They will be removed
completely or become internal only.
ok jsing
|
|
The faster nist code is rife with problematic C. While this is generally
considered to be a pleonasm nowadays, here it specifically refers to
aliasing issues and other flavors of undefined behavior. With compilers
and standardization committees becoming seemingly more determined about
making C even more unusable than it already is, this code has resulted
in miscompilations and generally is a target rich environment for fuzzers
to feast on. We're better off without it. Go look while it's still there.
It's some of the very worst we have to offer.
ok jsing
|
|
|
|
This file primarily contains the various BN_bn2*() and BN_*2bn() functions
(along with BN_print() and BN_options()). More function shuffling will
follow.
Discussed with tb@
|
|
This is simpler than the current code, while still being well optimised by
compilers, across a range of architectures. In many cases we even get a
performance gain for the BN sizes that we primarily care about.
Joint work with tb@
|
|
This is a reimplementation from scratch of the Tonelli-Shanks algorithm
based on Henri Cohen "A Course in Computational Algebraic Number Theory",
Springer GTM 138, section 1.5.1. It is API compatible with the previous
implementation, so no documentation change is required.
Contrary to the old implementation, this does not have any infinite loops
and has various additional sanity checks to prevent misbehavior in case
the input modulus is not a prime. It contains extensive comments and the
individual parts of the algorithm are split into digestible chunks instead
of having one huge function.
One difference of note is that it BN_mod_sqrt() now always returns the
smaller of the two possible answers. In other words, while its core is
non-deterministic, its answer is not.
ok jsing
|
|
|
|
|
|
This function is spread out over way too many lines and has too much
repetition. Once this is made a little more compact, it becomes clearer
that this is a somewhat obfuscated version of binary gcd (it is not
constant time therefore cryptographically unsound. It is not used
internally). This will likely go away later.
ok jsing
|
|
Also use C99 initializers for readability.
discussed with jsing
|
|
|
|
The only consumer of euclid() is BN_gcd(), which, in turn is only
used by BN_gcd_nonct(). Group them together rather than having
parts of the constant time implementation separate them.
This moves two functions to a different place in the file.
|
|
BN_copy() forgot to copy the flags from the source to the target. Fix
this by copying the flags. In fact, only copy BN_FLG_CONSTTIME since
propagating BN_FLG_MALLOCED and BN_FLG_STATIC_DATA is wrong. Ignore the
BN_FLG_FREE flag "used for debugging" which of course means "unused"
like a lot of other debug code that somehow ended up in public headers.
Also: make BN_FLG_CONSTTIME sticky on the target, i.e., don't clear the
flag when copying from a non-constant time BIGNUM to a constant time one
for the following reason: if a is constant time, BN_sqr(a, a, ctx) would
use a BIGNUM without the flag internally, then copy the result to a in
which process a would lose its constant time flag.
Fixing this would be a lot of pointless work since someone had the good
sense of not relying on a fragile flag for something this important.
Rather, libcrypto always uses the constant time paths instead of the
faster, cryptographically inadequate paths.
Before this was changed, this was a pretty bad bug. The RSA code uses the
horrible BN_with_flags() function to create local versions of the private
moduli and set BN_FLG_CONSTTIME on them. If the RSA_FLAG_CACHE_PRIVATE for
caching moduli is set on the RSA, which it is by default, it attempts to
set these constant time versions on the RSA's internal Montgomery contexts.
Since it is called BN_MONT_CTX_set(), the setter doesn't set a BIGNUM on
the BN_MONT_CTX, rather it copies it over, losing the BN_FLG_CONSTTIME flag
in the process and make all the horrible leaky RSA code leak some more.
Good job.
This is all harmless and is mostly a cosmetic fix. BN_FLG_CONSTTIME should
be removed internally. It will be kept since various language bindings of
course picked it up and expose it.
ok beck jsing
|
|
bn_copy() does the right thing if source and target are the same, so
there is no need for an additional check.
Requested by jsing
|
|
This mostly only cleans up the mess that it was - which doesn't stand out
because of the horror that lurks in the rest of this file. It avoids
copying the partial calculation out on error and does away with some
other weirdness.
with/ok jsing
|
|
ok jsing
|
|
ok jsing
|
|
ok jsing
|
|
ok jsing
|
|
ok jsing
|
|
Like everything else in this file, the use of BN_copy() needs to be ...
special. Simplify using the new bn_copy().
ok jsing
|
|
ok jsing
|
|
|
|
This removes a potential branch in a sensitive function and makes the
code a lot simpler. It is a really bad idea optimize here for what
davidben aptly calls "calculator" purposes.
ok jsing
|
|
Negative bases could result in a negative modulus being returned. This is
not strictly speaking incorrect but slightly surprising. This is all a
consequence of the shortcut of defining BN_mod() as a macro using BN_div().
Fixes ossfuzz #55997
ok jsing
|
|
|
|
|
|
Use a style more resembling KNF and drop lots of parentheses. Simplify
a few things. No change in generated output on success.
|
|
commented-out license stub in a HERE document.
|
|
|
|
script is run. This is more of an issue with uint16_t now than it
was with prime_t aka BN_ULONG before r1.6.
|
