| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
| |
ok jsing
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Provide bn_rand_in_range() which is a slightly tweaked version of what was
previously called bn_rand_range().
The way bn_rand_range() is called in libcrypto, the lower bound is always
expressible as a word. In fact, most of the time it is 1, the DH code uses
a 2, the MR tests in BPSW use 3 and an exceptinally high number appears in
the Tonelli-Shanks implementation where we use 32. Converting these lower
bounds to BIGNUMs on the call site is annoying so let bn_rand_interval()
do that internally and route that through bn_rand_in_range(). This way we
can avoid using BN_sub_word().
Adjust the bn_isqrt() test to use bn_rand_in_range() since that's the
only caller that uses actual BIGNUMs as lower bounds.
ok jsing
|
| |
|
|
|
|
|
| |
This is more accurate and improves readability a bit. Apart from a comment
tweak this is sed + knfmt (which resulted in four wrapped lines).
Discussed with beck and jsing
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
The behavior of the BPSW primality test for numbers > 2^64 is not very
well understood. While there is no known composite that passes the test,
there are heuristics that indicate that there are likely infinitely many.
Therefore it seems appropriate to harden the test. Having a settable
number of MR rounds before doing a version of BPSW is also the approach
taken by Go's primality check in math/big.
This adds a new implementation of the old MR test that runs before running
the strong Lucas test. I like to imagine that it's slightly cleaner code.
We're effectively at about twice the cost of what we had a year ago. In
addition, it adds some non-determinism in case there actually are false
positives for the BPSW test.
The implementation is straightforward. It could easily be tweaked to use
the additional gcds in the "enhanced" MR test of FIPS 186-5, but as long
as we are only going to throw away the additional info, that's not worth
much.
This is a first step towards incorporating some of the considerations in
"A performant misuse-resistant API for Primality Testing" by Massimo and
Paterson. Further work will happen in tree. In particular, there are plans
to crank the number of Miller-Rabin tests considerably so as to have a
guaranteed baseline. The manual will be updated shortly.
positive feedback beck
ok jsing
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Libcrypto currently has a mess of *_lcl.h, *_locl.h, and *_local.h names
used for internal headers. Move all these headers we inherited from
OpenSSL to *_local.h, reserving the name *_internal.h for our own code.
Similarly, move dtls_locl.h and ssl_locl.h to dtls_local and ssl_local.h.
constant_time_locl.h is moved to constant_time.h since it's special.
Adjust all .c files in libcrypto, libssl and regress.
The diff is mechanical with the exception of tls13_quic.c, where
#include <ssl_locl.h> was fixed manually.
discussed with jsing,
no objection bcook
|
| | |
|
| | |
|
| |
|
|
|
| |
a shortcut bypassing expensive computation, so change goto err to
goto done. Bug introduced in last refactoring before commit.
|
| | |
|
| | |
|
| | |
|
|
|
It has long been known that pure Miller-Rabin primality tests are
insufficient. "Prime and Prejudice: Primality Testing Under Adversarial
Conditions" https://eprint.iacr.org/2018/749 points out severe flaws
in many widely used libraries. In particular, they exhibited a method to
generate 2048-bit composites that bypass the default OpenSSL (and hence
LibreSSL) primality test with a probability of 1/16 (!).
As a remedy, the authors recommend switching to using BPSW wherever
possible. This possibility has always been there, but someone had to
sit down and actually implement a properly licensed piece of code.
Fortunately, espie suggested to Martin Grenouilloux to do precisely this
after asking us whether we would be interested. Of course we were!
After a good first implementation from Martin and a lot of back and
forth, we came up with the present version.
This implementation is ~50% slower than the current default Miller-Rabin
test, but that is a small price to pay given the improvements.
Thanks to Martin Grenouilloux <martin.grenouilloux () lse ! epita ! fr>
for this awesome work, to espie without whom it wouldn't have happened,
and to djm for pointing us at this problem a long time back.
ok jsing
|
