Lably
Skip to content

Timing attack

Cryptographic attack

  • 7 min read
  • 2 chapters

Related on Lably

Through Best, worst and average case, Bitwise operation and Error detection and correction

Lab · Class 8–12Algorithms & SortingLab · Class 11Algorithm VisualizerLab · Class 11Binary and Logic GatesLab · Class 9–11Python Sandbox

Information can leak from a system through measurement of the time it takes to respond to certain queries. How much this information can help an attacker depends on many variables such as cryptographic system design, the CPU running the system, the algorithms used, assorted implementation details, timing attack countermeasures, and accuracy of the timing measurements. Any algorithm that has data-dependent timing variation is vulnerable to timing attacks. Removing timing-dependencies is difficult since varied execution time can occur at any level.

Vulnerability to timing attacks is often overlooked in the design phase and can be introduced unintentionally with compiler optimizations. Countermeasures include blinding and constant-time functions.

Constant-time challenges

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. A trivial "timing-safe implementation" can be found here. Imagine an implementation in which every call to a subroutine always returns exactly after time T has elapsed, where T is the maximum time it takes to execute that routine on every possible authorized input. Such a hypothetical implementation would leak no information about the data supplied to that invocation (in reality, non-data-dependent timing variations are unavoidable). The downside of such an approach is that the time used for all executions becomes that of the worst-case performance of the function. It would appear that blinding should be applied to avoid vulnerability to timing attacks.

The data-dependency of timing may stem from one of the following:

  • Non-local memory access, as the CPU may cache the data. Software run on a CPU with a data cache will exhibit data-dependent timing variations as a result of memory lookups into the cache.
  • Conditional jumps. Modern CPUs try to 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-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 run shifts and 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.

Sign in to keep reading

One more chapter is free with a Lably account.

More in Computing and communication

ISBNUnique numeric book identifier since 1970X (social network)American social networking serviceWayback MachineDigital archive by the Internet ArchivePython (programming language)General-purpose programming languageMacOSOperating system for Apple computersUnicodeCharacter encoding standard