Editing Timing attack (section)

== Avoidance ==
Many cryptographic algorithms can be implemented (or masked by a proxy) in a way that reduces or eliminates data-dependent timing information, known as a '''constant-time algorithm'''. An implementation of such an algorithm is sometimes called a '''timing-safe implementation'''.<ref>{{cite web |title=timingsafe_bcmp|url=https://man.openbsd.org/timingsafe_bcmp.3 |access-date=2024-11-11}}</ref> Consider an implementation in which every call to a subroutine always returns in exactly x seconds, where x is the maximum time it ever takes to execute that routine on every possible authorized input. In such an implementation, the timing of the algorithm is less likely to leak information about the data supplied to that invocation.<ref>{{cite web |title=A beginner's guide to constant-time cryptography |url=https://www.chosenplaintext.ca/articles/beginners-guide-constant-time-cryptography.html |access-date=2021-05-09}}</ref> The downside of this approach is that the time used for all executions becomes that of the [[Best, worst and average case|worst-case]] performance of the function.

The data-dependency of timing may stem from one of the following:<ref name=BearSSL/>
* Non-local memory access, as the CPU may [[CPU cache|cache]] the data. Software run on a CPU with a data cache will exhibit data-dependent timing variations as a result of memory looks into the cache.
* [[Conditional jump]]s. Modern CPUs try to [[Speculative execution|speculatively execute]] past conditional jumps by guessing. Guessing wrongly (not uncommon with essentially random secret data) entails a measurable large delay as the CPU tries to backtrack. This requires writing [[Branch (computer science)#Branch-free code|branch-free code]].
* Some "complicated" mathematical operations, depending on the actual CPU hardware:
** Integer division is almost always non-constant time. The CPU uses a [[microcode]] loop that uses a different code path when either the divisor or the dividend is small.
** CPUs without a [[barrel shifter]] runs [[Bitshift|shifts]] and [[Bit rotate|rotations]] in a loop, one position at a time. As a result, the amount to shift must not be secret.
** Older CPUs run multiplications in a way similar to division.