Avoid const-time modulo in DSA verification

It has a substantial perf hit and is not necessary. It may not
be really necessary for signatures either but leave that as it,
with a comment explaining.

1 files changed, 11 insertions, 1 deletions

diff --git a/src/lib/pubkey/dsa/dsa.cpp b/src/lib/pubkey/dsa/dsa.cpp
index bece42d06..4da347c5e 100644
--- a/src/lib/pubkey/dsa/dsa.cpp
+++ b/src/lib/pubkey/dsa/dsa.cpp
@@ -125,6 +125,15 @@ DSA_Signature_Operation::raw_sign(const uint8_t msg[], size_t msg_len,
 
    const BigInt k_inv = m_group.inverse_mod_q(k);
 
+   /*
+   * It may not be strictly necessary for the reduction (g^k mod p) mod q to be
+   * const time, since r is published as part of the signature, and deriving
+   * anything useful about k from g^k mod p would seem to require computing a
+   * discrete logarithm.
+   *
+   * However it only increases the cost of signatures by about 7-10%, and DSA is
+   * only for legacy use anyway so we don't care about the performance so much.
+   */
    const BigInt r = ct_modulo(m_group.power_g_p(k, m_group.q_bits()), m_group.get_q());
 
    /*
@@ -193,7 +202,8 @@ bool DSA_Verification_Operation::verify(const uint8_t msg[], size_t msg_len,
 
    s = m_group.multi_exponentiate(si, m_y, sr);
 
-   return (m_group.mod_q(s) == r);
+   // s is too big for Barrett, and verification doesn't need to be const-time
+   return (s % m_group.get_q() == r);
    }
 
 }