I am trying to understand why it is a hard problem to have formally verified constant time arithmetic for DSA when compared with ECDSA. For instance, in ECDSA implementations of OpenSSL, we have specialized constant time ECC curve-specific implementation for NIST curves which are optimized per architecture. Similarly, EverCrypt and fiat-crypto have formally verified constant time arithmetic implementation specific to the curve.

This is particularly interesting in the case of applying nonce padding as a remote timing side-channel countermeasure for EC(DSA). While fixing the nonce bit length does fix timing attack vulnerability in the case of ECDSA, a curve-specific constant-time implementation if done properly does not actually require a nonce padding. In the case of DSA, I am trying to understand, why we cannot have group-specific arithmetic and only stuck with nonce padding as the solution. I can understand the fundamental difference that they operate on different groups, but why DSA groups are stuck with a generic implementation when compared to ECC groups?

  • 2
    $\begingroup$ I don't feel I can give a full answer (hence this comment), however for ECDSA, one usually works with a special form modulus (most typically a NIST curve, possibly an Edwards curve), which makes the modulo operation especially easy. For DSA, we are effectively working with a random large modulus, hence there are no 'group specific' optimizations available to take advantage of. $\endgroup$ – poncho Nov 3 '20 at 20:45
  • 2
    $\begingroup$ Useful links: Thomas Pornin's BearSSL pages on constant-time crypto and constant-time MUL. $\endgroup$ – fgrieu Nov 3 '20 at 21:08
  • 1
    $\begingroup$ @fgrieu: Regarding the question, I guess what I am trying to ask is related to a very specific problem i.e. applying nonce padding as a timing side-channel countermeasure OR to have a group-specific implementation that does not require nonce padding since we can write the code in a way that we guarantee the nonce is fixed to the bit size of group order. In DSA we still have constant-time implementation of modular exponentiation, but that is a generic implementation for different prime groups. $\endgroup$ – sohu Nov 4 '20 at 7:35
  • $\begingroup$ @poncho makes sense what you said, but I am trying to understand the random part here > For DSA, we are effectively working with a random large modulus $\endgroup$ – sohu Nov 4 '20 at 7:39
  • $\begingroup$ I slightly better understand the question. But if we assume "constant-time implementation of modular exponentiation" for any modulus, I still fail to see what's hard in making DSA signature generation constant-time. $k^{-1}\bmod q$ is $k^{p-2}\bmod q$, the rest is modular addition, modular reduction, modular exponentiation. And all I see that's not modexp also exists in ECDSA, with the possible exception of the second reduction in $(g^k\bmod p)\bmod q$ which is identity with overwhelming probability in ECDSA, not in DSA. What is the operation in DSA that would be the trouble spot? $\endgroup$ – fgrieu Nov 4 '20 at 8:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.