tree 2f3b48f86ebf27ecb1fceff37f53281ff6434109
parent 9f9c938af0affceee30eef308ed2596e1d7f53e0
author David Benjamin <davidben@google.com> 1528385535 -0400
committer CQ bot account: commit-bot@chromium.org <commit-bot@chromium.org> 1529030265 +0000

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>