aboutsummaryrefslogtreecommitdiffstats
path: root/src/lib/math
Commit message (Collapse)AuthorAgeFilesLines
* Add script for running TLS fuzzerJack Lloyd2019-05-241-2/+2
| | | | Fix a few minor issues found thereby
* Use C++ raw strings in inline asmJack Lloyd2019-05-032-72/+64
|
* Fix feature macro checks.Jack Lloyd2019-04-262-4/+5
| | | | Add a checker script.
* Fix warningJack Lloyd2019-01-241-3/+6
|
* Doc updatesJack Lloyd2019-01-241-1/+3
|
* Revamp BigInt encoding and decoding.Jack Lloyd2019-01-244-103/+130
| | | | Deprecate some crufty functions. Optimize binary encoding/decoding.
* Fix some warnings from PVS-StudioJack Lloyd2019-01-171-2/+5
| | | | No real bugs, but pointed out some odd constructs and duplicated logic
* Fix use of macroJack Lloyd2018-12-311-1/+1
| | | | Assumed to be 0/1
* Simplifications in BigIntJack Lloyd2018-12-291-7/+1
| | | | | Use ct_is_zero instead of more complicated construction, and avoid duplicated size check/resize - Data::set_word will handle it.
* Make bigint_sub_abs const timeJack Lloyd2018-12-271-6/+3
|
* Fix Barrett reduction input boundJack Lloyd2018-12-262-5/+5
| | | | | | | | | | | | In the long ago when I wrote the Barrett code I must have missed that Barrett works for any input < 2^2k where k is the word size of the modulus. Fixing this has several nice effects, it is faster because it replaces a multiprecision comparison with a single size_t compare, and now the branch does not reveal information about the input or modulus, but only their word lengths, which is not considered sensitive. Fixing this allows reverting the change make in a57ce5a4fd2 and now RSA signing is even slightly faster than in 2.8, rather than 30% slower.
* Avoid size-based bypass of the comparison in Barrett reduction.Jack Lloyd2018-12-241-1/+1
| | | | As it would leak if an input was > p^2, or just close to it in size.
* Avoid conditional branch in Barrett for negative inputsJack Lloyd2018-12-241-4/+27
|
* In NIST P-xxx reductions unpoison S before using itJack Lloyd2018-12-241-8/+10
| | | | | | | | Was already done in P-256 but not in P-{192,224,384}. This is a cache-based side channel which would be good to address. It seems like it would be very difficult to exploit even with perfect recovery, but crazier things have worked.
* Unpoison result of high_bits_freeJack Lloyd2018-12-241-0/+1
| | | | | Previously we unpoisoned the input to high_bit but this is no longer required. But still the output should be unpoisoned.
* Make ctz and high_bit faster and const-time-ishJack Lloyd2018-12-221-5/+0
| | | | | | | They get compiled as const-time on x86-64 with GCC but I don't think this can be totally relied on. But it is anyway an improvement. And, faster, because we compute it recursively
* Use consistent logic for OAEP and PKCS1v15 decodingJack Lloyd2018-12-212-6/+3
| | | | | | | | | | | | The decoding leaked some information about the delimiter index due to copying only exactly input_len - delim_idx bytes. I can't articulate a specific attack that would work here, but it is easy enough to fix this to run in const time instead, where all bytes are accessed regardless of the length of the padding. CT::copy_out is O(n^2) and thus terrible, but in practice it is only used with RSA decryption, and multiplication is also O(n^2) with the modulus size, so a few extra cycles here doesn't matter much.
* Unroll const_time_lookup by 2Jack Lloyd2018-12-141-6/+10
| | | | | We know the lookup table is some power of 2, unrolling a bit allows more IPC
* Merge GH #1780 Use constant time algorithm for monty_inverseJack Lloyd2018-12-092-39/+23
|\
| * Use a const time algorithm for monty_inverseJack Lloyd2018-12-092-39/+23
| | | | | | | | | | Previous EEA leaked information about the low word of the prime, which is a problem for RSA.
* | Fix typoJack Lloyd2018-12-091-1/+1
| |
* | Avoid doing a variable time division during Montgomery setupJack Lloyd2018-12-093-4/+9
|/ | | | | | Instead require the inputs be reduced already. For RSA-CRT use Barrett which is const time already. For SRP6 inputs were not reduced, use the Barrett hook available in DL_Group.
* Move Miller-Rabin t param inside the blockJack Lloyd2018-12-091-2/+2
| | | | This var is not used if we use Baile-PSW instead
* Avoid repeated size checks when setting words in NIST reductionJack Lloyd2018-12-081-25/+33
| | | | This is a tiny thing but it saves over 100K cycles for P-384 ECDSA
* Merge GH #1774 Const time BigInt shiftsJack Lloyd2018-12-086-98/+83
|\
| * Avoid early exitJack Lloyd2018-12-071-4/+3
| |
| * Fix bug and avoid allocations in left shiftJack Lloyd2018-12-075-22/+36
| |
| * Const time the behavior of shifts [WIP]Jack Lloyd2018-12-063-87/+59
| | | | | | | | | | | | | | | | | | They would previously leak for example if the requested shift was 0. However, that should only happen in two situations: very dumb code explicitly requested a shift of zero (in which case we don't care if performance is poor, your code is dumb) or a variable shift that just happens to be zero, in which case the variable may be a secret, for instance this can be seen in the GCD computation.
* | In calc_sig_words save the size of m_reg before the loopJack Lloyd2018-12-081-3/+4
| |
* | Merge GH #1773 Add BigInt::ct_reduce_belowJack Lloyd2018-12-073-3/+39
|\ \ | |/ |/|
| * Add BigInt::ct_reduce_belowJack Lloyd2018-12-063-3/+39
| |
* | Better logic in BigInt::bits wrt valgrind const time checksJack Lloyd2018-12-061-2/+3
|/
* Do swaps in PointGFp instead of copiesJack Lloyd2018-12-051-1/+1
| | | | Saves 5% for ECDSA
* Avoid needless is_zero check in set_signJack Lloyd2018-12-051-4/+4
| | | | If not negative we don't need to check the size
* Fix Doxygen errors [ci skip]Jack Lloyd2018-12-051-1/+0
|
* Make BigInt::cond_flip_sign constant timeJack Lloyd2018-12-051-3/+9
|
* Use BigInt::cond_flip_signJack Lloyd2018-12-053-7/+4
|
* Don't leak if x is zero eitherJack Lloyd2018-12-051-39/+37
|
* Remove some conditional branches from divisionJack Lloyd2018-12-053-22/+27
|
* Reduce the base in the fixed window exponentiatorJack Lloyd2018-12-041-1/+1
| | | | | | | | | | | Otherwise we can end up calling the Barrett reducer with an input that is more than the square of the modulus, which will make it fall back to the (slow) const time division. This only affected even moduli, and only when the base was larger than the modulus. OSS-Fuzz 11750
* Make binary extended Euclidean algorithm less branchyJack Lloyd2018-12-033-12/+62
| | | | This is still leaky, but much less than before.
* Extend ct_modulo to handle negative inputsJack Lloyd2018-12-031-8/+17
| | | | Unfortunately Barrett reductions API allows negative inputs
* Use const time reductions in Barrett and LCM computationsJack Lloyd2018-12-033-4/+23
|
* Fix shift operatorJack Lloyd2018-12-031-1/+1
| | | | This would continually reallocate to larger sizes which is bad news.
* Add ct_modulo and BigInt::ct_cond_swapJack Lloyd2018-12-034-7/+62
|
* Merge GH #1759 Add constant time divide by uint8_tJack Lloyd2018-12-033-7/+59
|\
| * Add a constant time divide variant for dividing by uint8_tJack Lloyd2018-12-023-7/+59
| | | | | | | | | | | | | | | | | | Originally wrote it for div-by-word but that ends up requiring a dword type which we don't always have. And uint8_t covers the most important cases of n = 10 and n = 58 (whenever I get around to writing base58). We could portably support up to div-by-uint32, but I don't think we need it. Nicely for n = 10, this is actually faster than the variable time division.
* | Make variable time division less branchyJack Lloyd2018-12-021-53/+46
|/ | | | This is still leaky, but better than nothing.
* Add a const-time division algorithmJack Lloyd2018-12-024-8/+69
| | | | | | | | It is stupid and slow (~50-100x slower than variable time version) but still useful for protecting critical algorithms. Not currently used, waiting for OSS-Fuzz to test it for a while before we commit to it.
* Fix a bug in bigint_sub_absJack Lloyd2018-12-021-0/+7
| | | | | | | If one of the values had leading zero words, this could end up calling bigint_sub with x_size < y_size. OSS-Fuzz 11664 and 11656
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-29 03:53:24 +0000