Fix some timing leaks in the DSA code.

The DSA code is deprecated and will, hopefully, be removed in the future.
Nonetheless, this is easy enough to fix. It's the analog of the work we'd
already done for ECDSA.

- Document more clearly that we don't care about the DSA code.

- Use the existing constant-time modular addition function rather than
  the ad-hoc code.

- Reduce the digest to satisfy modular operations' invariants. (The
  underlying algorithms could accept looser bounds, but we reduce for
  simplicity.) There's no particular reason to do this in constant time,
  but we have the code for it, so we may as well.

- This additionally adds a missing check that num_bits(q) is a multiple
  of 8. We otherwise don't compute the right answer. Verification
  already rejected all 160-, 224-, and 256-bit keys, and we only
  generate DSA parameters where the length of q matches some hash
  function's length, so this is unlikely to cause anyone trouble.

- Use Montgomery reduction to perform the modular multiplication. This
  could be optimized to save a couple Montgomery reductions as in ECDSA,
  but DSA is deprecated, so I haven't bothered optimizing this.

- The reduction from g^k (mod p) to r = g^k (mod p) (mod q) is left
  in variable time, but reversing it would require a discrete log
  anyway. (The corresponding ECDSA operation is much easier to make
  constant-time due to Hasse's theorem, though that's actually still a
  TODO. I need to finish lifting EC_FELEM up the stack.)

Thanks to Keegan Ryan from NCC Group for reporting the modular addition issue
(CVE-2018-0495). The remainder is stuff I noticed along the way.

Update-Note: See the num_bits(q) change.

Change-Id: I4f032b041e2aeb09f9737a39f178c24e6a7fa1cb
Reviewed-on: https://boringssl-review.googlesource.com/29145
Commit-Queue: Adam Langley <agl@google.com>
Reviewed-by: Adam Langley <agl@google.com>
CQ-Verified: CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org>
2 files changed
tree: 2f3b48f86ebf27ecb1fceff37f53281ff6434109
  1. .clang-format
  2. .github/
  3. .gitignore
  4. API-CONVENTIONS.md
  5. BREAKING-CHANGES.md
  6. BUILDING.md
  7. CMakeLists.txt
  8. CONTRIBUTING.md
  9. FUZZING.md
  10. INCORPORATING.md
  11. LICENSE
  12. PORTING.md
  13. README.md
  14. STYLE.md
  15. codereview.settings
  16. crypto/
  17. decrepit/
  18. fipstools/
  19. fuzz/
  20. include/
  21. infra/
  22. sources.cmake
  23. ssl/
  24. third_party/
  25. tool/
  26. 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: