tree 6bc92ca0bff0b565501529be3b1751097cb6677f
parent 8d9ee7d1fe89f424ad36b9f389692e777e9ba782
author David Benjamin <davidben@google.com> 1520141880 -0500
committer Adam Langley <alangley@gmail.com> 1522439608 +0000

Compute p - q in constant time.

Expose the constant-time abs_sub functions from the fixed Karatsuba code
in BIGNUM form for RSA to call into. RSA key generation involves
checking if |p - q| is above some lower bound.

BN_sub internally branches on which of p or q is bigger. For any given
iteration, this is not secret---one of p or q is necessarily the larger,
and whether we happened to pick the larger or smaller first is
irrelevant. Accordingly, there is no need to perform the p/q swap at the
end in constant-time.

However, this stage of the algorithm picks p first, sticks with it, and
then computes |p - q| for various q candidates. The distribution of
comparisons leaks information about p. The leak is unlikely to be
problematic, but plug it anyway.

Median of 29 RSA keygens: 0m0.210s -> 0m0.212s
(Accuracy beyond 0.1s is questionable.)

Bug: 238
Change-Id: I024b4e51b364f5ca2bcb419a0393e7be13249aec
Reviewed-on: https://boringssl-review.googlesource.com/26368
Reviewed-by: Adam Langley <alangley@gmail.com>