Discussions from highly respected sources (details below) emphasize the importance of the implementation of cryptographic software to the effective security provided, with one particular case being sensitivity to timing attacks.
Clarification - Context is cryptographic signing of non-secret messages
@poncho's initial answer notes that attackers don't always have the luxury of determining the "user's" implementation.
In fact, I'm interested in this question precisely in the very real situation where the attacker is the user, and has the ability to choose their own implementation - in cryptographic signing of non-secret messages. My citation below is about NaCl, which includes an implementation of ed25519. In the use cases I'm working on, you can assume that the "attacker" / user has the plaintext message, the signature, and the public key. All three are necessary for the signature to even be useful. The only thing they lack is the private key.
Is this not irrelevant? Logically, a cryptographic algorithm is inherently susceptible to timing attacks if the algorithm itself is capable of identifying a validation failure in a fewer number of operations than is required to confirm a validation success. The more distinct points at which validation failure can be mathematically determined, the more susceptible the algorithm is.
- If an algorithm cannot mathematically determine the validity of a set of inputs until the final step, then it is inherently immune to timing attacks. It is my understanding that all NIST-approved SHA algorithms as of FIPS-180-4 are in this group.
- If an algorithm can mathematically identify invalid input at every incremental byte/word/block of some stream processed, it is extremely sensitive to timing attacks.
- In the worst case, the minimum number of operations required to determine success or failure depends on each incremental bit in a secret key.
The ability of any given implementation to avoid or ignore the algorithm's underlying susceptibility to a timing attack is logically irrelevant, because a rational attacker will simply choose to use an implementation that is intentionally sensitive to timing attacks. Even if most attackers lack the skill or motivation to write their own implementation, it only takes one to create and then distribute an implementation that accentuates timing attacks.
Likewise, if an algorithm is inherently immune to timing attacks (e.g. it cannot determine validity or invalidity until the final step), then it is by definition not possible to create an implementation that is susceptible to timing attacks, whether on purpose or on accident.
An author can be proud of any number of qualities of their implementation of an algorithm, but it does not seem that "resistance to timing attacks" is a logically meaningful quality.
Am I missing something here?
Reference: Daniel Bernstein / NaCl
The features section of the docs for Daniel Bernstein's original NaCl library, which is the reference implementation of the ed25519 signature algorithm which he and co-authors invented, makes multiple claims about the superiority of their implementation which makes it resistant to timing attacks (emphasis mine):
No data-dependent branches
... The literature has many examples of successful timing attacks that extracted secret keys from these parts of the CPU. NaCl systematically avoids all data flow from secret information to the instruction pointer and the branch predictor
No data-dependent array indices
... The literature has several examples of successful cache-timing attacks that used secret information leaked through addresses. NaCl systematically avoids all data flow from secret information to the addresses used in load instructions and store instructions