Make BN_num_bits_word constant-time.

(The BN_num_bits_word implementation was originally written by Andy
Polyakov for OpenSSL. See also
https://github.com/openssl/openssl/pull/5154.)

BN_num_bits, by way of BN_num_bits_word, currently leaks the
most-significant word of its argument via branching and memory access
pattern.

BN_num_bits is called on RSA prime factors in various places. These have
public bit lengths, but all bits beyond the high bit are secret. This
fully resolves those cases.

There are a few places where BN_num_bits is called on an input where
the bit length is also secret. The two left in BoringSSL are:

- BN_mod_exp_mont_consttime calls it on the RSA private exponent.

- The timing "fix" to add the order to k in DSA.

This does *not* fully resolve those cases as we still only look at the
top word. Today, that is guaranteed to be non-zero, but only because of
the long-standing bn_correct_top timing leak. Once that is fixed (I hope
to have patches soon), a constant-time BN_num_bits on such inputs must
count bits on each word.

Instead, those cases should not call BN_num_bits at all. The former uses
the bit width to pick windows, but it should be using the maximum bit
width. The next patch will fix this.  The latter is the same "fix" we
excised from ECDSA in a838f9dc7e6cc091237f0acbbe4953104104e815.  That
should be excised from DSA after the bn_correct_top bug is fixed.

Thanks to Dinghao Wu, Danfeng Zhang, Shuai Wang, Pei Wang, and Xiao Liu
for reporting this issue.

Change-Id: Idc3da518cc5ec18bd8688b95f959b15300a57c14
Reviewed-on: https://boringssl-review.googlesource.com/25184
Reviewed-by: Adam Langley <agl@google.com>
2 files changed
tree: 95b3704fabb97a8b62cd1f2b3fdde48ccfc022ba
  1. .clang-format
  2. .github/
  3. .gitignore
  4. API-CONVENTIONS.md
  5. BUILDING.md
  6. CMakeLists.txt
  7. CONTRIBUTING.md
  8. FUZZING.md
  9. INCORPORATING.md
  10. LICENSE
  11. PORTING.md
  12. README.md
  13. STYLE.md
  14. codereview.settings
  15. crypto/
  16. decrepit/
  17. fipstools/
  18. fuzz/
  19. include/
  20. infra/
  21. sources.cmake
  22. ssl/
  23. third_party/
  24. tool/
  25. util/
README.md

BoringSSL

BoringSSL is a fork of OpenSSL that is designed to meet Google's needs.

Although BoringSSL is an open source project, it is not intended for general use, as OpenSSL is. We don't recommend that third parties depend upon it. Doing so is likely to be frustrating because there are no guarantees of API or ABI stability.

Programs ship their own copies of BoringSSL when they use it and we update everything as needed when deciding to make API changes. This allows us to mostly avoid compromises in the name of compatibility. It works for us, but it may not work for you.

BoringSSL arose because Google used OpenSSL for many years in various ways and, over time, built up a large number of patches that were maintained while tracking upstream OpenSSL. As Google's product portfolio became more complex, more copies of OpenSSL sprung up and the effort involved in maintaining all these patches in multiple places was growing steadily.

Currently BoringSSL is the SSL library in Chrome/Chromium, Android (but it's not part of the NDK) and a number of other apps/programs.

There are other files in this directory which might be helpful: