# Timing attack

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Timing_attack
> Markdown URL: https://mediated.wiki/source/Timing_attack.md
> Source: https://en.wikipedia.org/wiki/Timing_attack
> Source revision: 1352680894
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Cryptographic attack

An example of a timing attack being performed on a [web cache](/source/Web_cache). The left graph denotes a timing attack successfully detecting a cached image whereas the right one shows an attack that fails to do the same.

In [cryptography](/source/Cryptography), a **timing attack** is a [side-channel attack](/source/Side-channel_attack) in which the attacker attempts to compromise a [cryptosystem](/source/Cryptosystem) by analyzing the time taken to execute cryptographic algorithms. Every logical operation in a computer takes time to execute, and the time can differ based on the input; with precise measurements of the time for each operation, an attacker may be able to work backwards to the input.

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](/source/Compiler_optimizations). [Countermeasures](/source/Side-channel_attack#Countermeasures) include [blinding](/source/Blinding_(cryptography)) and [constant-time](/source/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.[1] 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](/source/Best%2C_worst_and_average_case) performance of the function.[2] It would appear that [blinding](/source/Blinding_(cryptography)) should be applied to avoid vulnerability to timing attacks.

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

- Non-local memory access, as the CPU may [cache](/source/CPU_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](/source/Conditional_jump). Modern CPUs try to [speculatively execute](/source/Speculative_execution) 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](/source/Branch_(computer_science)#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](/source/Microcode) loop that uses a different code path when either the divisor or the dividend is small. - CPUs without a [barrel shifter](/source/Barrel_shifter) run [shifts](/source/Bitshift) and [rotations](/source/Bit_rotate) 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.

## Examples

The execution time for the [square-and-multiply algorithm](/source/Square-and-multiply_algorithm) used in [modular exponentiation](/source/Modular_exponentiation) depends linearly on the number of '1' bits in the key. While the number of '1' bits alone is not nearly enough information to make finding the key easy, repeated executions with the same key and different inputs can be used to perform statistical correlation analysis of timing information to recover the key completely, even by a passive attacker. Observed timing measurements often include noise (from such sources as network latency, or disk drive access differences from access to access, and the [error correction](/source/Error_correction) techniques used to recover from transmission errors). Nevertheless, timing attacks are practical against a number of encryption algorithms, including [RSA](/source/RSA_(algorithm)), [ElGamal](/source/ElGamal_encryption), and the [Digital Signature Algorithm](/source/Digital_Signature_Algorithm).

In 2003, [Boneh](/source/Dan_Boneh) and [Brumley](/source/David_Brumley) demonstrated a practical network-based timing attack on [SSL](/source/Secure_Sockets_Layer)-enabled web servers, based on a different vulnerability having to do with the use of RSA with [Chinese remainder theorem](/source/Chinese_remainder_theorem) optimizations. The actual network distance was small in their experiments, but the attack successfully recovered a server private key in a matter of hours. This demonstration led to the widespread deployment and use of [blinding](/source/Blinding_(cryptography)) techniques in SSL implementations. In this context, blinding is intended to remove correlations between key and encryption time.[4][5]

Some versions of [Unix](/source/Unix) use a relatively expensive implementation of the *crypt* library function for hashing an 8-character password into an 11-character string. On older hardware, this computation took a deliberately and measurably long time: as much as two or three seconds in some cases.[*[citation needed](https://en.wikipedia.org/wiki/Wikipedia:Citation_needed)*] The *login* program in early versions of Unix executed the crypt function only when the login name was recognized by the system. This leaked information through timing about the validity of the login name, even when the password was incorrect. An attacker could exploit such leaks by first applying [brute-force](/source/Brute-force_attack) to produce a list of login names known to be valid, then attempt to gain access by combining only these names with a large set of passwords known to be frequently used. Without any information on the validity of login names the time needed to execute such an approach would increase by orders of magnitude, effectively rendering it useless. Later versions of Unix have fixed this leak by always executing the crypt function, regardless of login name validity.[*[citation needed](https://en.wikipedia.org/wiki/Wikipedia:Citation_needed)*]

Two otherwise securely isolated processes running on a single system with either [cache memory](/source/Cache_memory) or [virtual memory](/source/Virtual_memory) can communicate by deliberately causing [page faults](/source/Page_fault) and/or [cache misses](/source/Cache_miss) in one process, then monitoring the resulting changes in access times from the other. Likewise, if an application is trusted, but its paging/caching is affected by branching logic, it may be possible for a second application to determine the values of the data compared to the branch condition by monitoring access time changes; in extreme examples, this can allow recovery of cryptographic key bits.[6][7]

The 2017 [Meltdown](/source/Meltdown_(security_vulnerability)) and [Spectre](/source/Spectre_(security_vulnerability)) attacks which forced CPU manufacturers (including Intel, AMD, ARM, and IBM) to redesign their CPUs both rely on timing attacks.[8] As of early 2018, almost every computer system in the world is affected by Spectre.[9][10][11]

In 2018, many internet servers were still vulnerable to slight variations of the original timing attack on RSA, two decades after the original vulnerability was discovered.[12]

### String comparison algorithms

The following [C](/source/C_(programming_language)) code demonstrates a typical insecure string comparison which stops testing as soon as a character doesn't match. For example, when comparing "ABCDE" with "ABxDE" it will return after 3 loop iterations:

#include <stddef.h>

bool insecure_string_compare(const void *a, const void *b, size_t length) {
  const char *ca = a, *cb = b;
  for (size_t i = 0; i < length; i++)
    if (ca[i] != cb[i])
      return false;
  return true;
}

By comparison, the following version runs in constant-time by testing all characters and using a [bitwise operation](/source/Bitwise_operation) to accumulate the result:

#include <stddef.h>

bool constant_time_string_compare(const void *a, const void *b, size_t length) {
  const char *ca = a, *cb = b;
  bool result = true;
  for (size_t i = 0; i < length; i++)
    result &= ca[i] == cb[i];
  return result;
}

In the world of C library functions, the first function is analogous to memcmp(), while the latter is analogous to NetBSD's consttime_memequal() or[13] OpenBSD's timingsafe_bcmp() and timingsafe_memcmp. On other systems, the comparison function from cryptographic libraries like [OpenSSL](/source/OpenSSL) and [libsodium](/source/Libsodium) can be used.

## Notes

Timing attacks are easier to mount if the adversary knows the internals of the hardware implementation, and even more so, the cryptographic system in use. Since cryptographic security should never depend on the obscurity of either (see [security through obscurity](/source/Security_through_obscurity), specifically both Shannon's Maxim and [Kerckhoffs's principle](/source/Kerckhoffs's_principle)), resistance to timing attacks should not either. If nothing else, an exemplar can be purchased and reverse engineered. Timing attacks and other side-channel attacks may also be useful in identifying, or possibly reverse-engineering, a cryptographic algorithm used by some device.

## See also

- [Power analysis](/source/Power_analysis)

- [Pixel stealing attack](/source/Pixel_stealing_attack)

## References

1. **[^](#cite_ref-1)** ["timingsafe_bcmp"](https://man.openbsd.org/timingsafe_bcmp.3). Retrieved 11 November 2024.

1. **[^](#cite_ref-2)** ["A beginner's guide to constant-time cryptography"](https://www.chosenplaintext.ca/articles/beginners-guide-constant-time-cryptography.html). Retrieved 9 May 2021.

1. **[^](#cite_ref-BearSSL_3-0)** ["Constant-Time Crypto"](https://www.bearssl.org/constanttime.html). *BearSSL*. Retrieved 10 January 2017.

1. **[^](#cite_ref-4)** David Brumley and Dan Boneh. [Remote timing attacks are practical.](http://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf) USENIX Security Symposium, August 2003.

1. **[^](#cite_ref-5)** Kocher, Paul C. (1996). ["Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems"](https://link.springer.com/chapter/10.1007/3-540-68697-5_9). In Koblitz, Neal (ed.). *Advances in Cryptology — CRYPTO '96*. Lecture Notes in Computer Science. Vol. 1109. Berlin, Heidelberg: Springer. pp. 104–113. [doi](/source/Doi_(identifier)):[10.1007/3-540-68697-5_9](https://doi.org/10.1007%2F3-540-68697-5_9). [ISBN](/source/ISBN_(identifier)) [978-3-540-68697-2](https://en.wikipedia.org/wiki/Special:BookSources/978-3-540-68697-2).

1. **[^](#cite_ref-6)** See Percival, Colin, [Cache Missing for Fun and Profit](http://www.daemonology.net/papers/htt.pdf), 2005.

1. **[^](#cite_ref-7)** Bernstein, Daniel J., [Cache-timing attacks on AES](http://cr.yp.to/antiforgery/cachetiming-20050414.pdf), 2005.

1. **[^](#cite_ref-8)** Horn, Jann (3 January 2018). ["Reading privileged memory with a side-channel"](https://googleprojectzero.blogspot.com/2018/01/reading-privileged-memory-with-side.html). googleprojectzero.blogspot.com.

1. **[^](#cite_ref-9)** ["Spectre systems FAQ"](https://spectreattack.com/#faq-systems-spectre). *Meltdown and Spectre*.

1. **[^](#cite_ref-10)** ["Security flaws put virtually all phones, computers at risk"](https://www.reuters.com/article/us-cyber-intel-idUSKBN1ES1BO). *Reuters*. 4 January 2018.

1. **[^](#cite_ref-11)** ["Potential Impact on Processors in the POWER Family"](https://www.ibm.com/blogs/psirt/potential-impact-processors-power-family/). *IBM PSIRT Blog*. 14 May 2019.

1. **[^](#cite_ref-12)** Kario, Hubert. ["The Marvin Attack"](https://people.redhat.com/~hkario/marvin/). *people.redhat.com*. Retrieved 19 December 2023.

1. **[^](#cite_ref-13)** ["Consttime_memequal"](https://www.freebsd.org/cgi/man.cgi?query=consttime_memequal&manpath=NetBSD+7.0).

## Further reading

- [Lipton, Richard](/source/Richard_J._Lipton); Naughton, Jeffrey F. (March 1993). "Clocked adversaries for hashing". *Algorithmica*. **9** (3): 239–252. [doi](/source/Doi_(identifier)):[10.1007/BF01190898](https://doi.org/10.1007%2FBF01190898). [S2CID](/source/S2CID_(identifier)) [19163221](https://api.semanticscholar.org/CorpusID:19163221).

- Reparaz, Oscar; Balasch, Josep; Verbauwhede, Ingrid (March 2017). ["Dude, is my code constant time?"](https://eprint.iacr.org/2016/1123.pdf) (PDF). *Design, Automation & Test in Europe Conference & Exhibition (DATE), 2017*. pp. 1697–1702. [doi](/source/Doi_(identifier)):[10.23919/DATE.2017.7927267](https://doi.org/10.23919%2FDATE.2017.7927267). [ISBN](/source/ISBN_(identifier)) [978-3-9815370-8-6](https://en.wikipedia.org/wiki/Special:BookSources/978-3-9815370-8-6). [S2CID](/source/S2CID_(identifier)) [35428223](https://api.semanticscholar.org/CorpusID:35428223). Describes [dudect](https://github.com/oreparaz/dudect), a simple program that times a piece of code on different data.

v t e Block ciphers (security summary) Common algorithms AES Blowfish DES (internal mechanics, Triple DES) Serpent SM4 Twofish Less common algorithms ARIA Camellia CAST-128 GOST IDEA LEA RC5 RC6 SEED Skipjack TEA XTEA Other algorithms 3-Way Adiantum Akelarre Anubis Ascon BaseKing BassOmatic BATON BEAR and LION CAST-256 Chiasmus CIKS-1 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA CMEA Cobra COCONUT98 Crab Cryptomeria/C2 CRYPTON CS-Cipher DEAL DES-X DFC E2 FEAL FEA-M FROG G-DES Grand Cru Hasty Pudding cipher Hierocrypt ICE IDEA NXT Intel Cascade Cipher Iraqi Kalyna KASUMI KeeLoq KHAZAD Khufu and Khafre KN-Cipher Kuznyechik Ladder-DES LOKI (97, 89/91) Lucifer M6 M8 MacGuffin Madryga MAGENTA MARS Mercy MESH MISTY1 MMB MULTI2 MultiSwap New Data Seal NewDES Nimbus NOEKEON NUSH PRESENT Prince Q QARMA RC2 REDOC Red Pike S-1 SAFER SAVILLE SC2000 SHACAL SHARK Simon Speck Spectr-H64 Square SXAL/MBAL Threefish Treyfer UES xmx XXTEA Zodiac Design Feistel network Key schedule Lai–Massey scheme Product cipher S-box P-box SPN Confusion and diffusion Round Avalanche effect Block size Key size Key whitening (Whitening transformation) Attack (cryptanalysis) Brute-force (EFF DES cracker) MITM Biclique attack 3-subset MITM attack Algebraic Cube attack Gröbner attack Linear (Piling-up lemma) Differential Impossible Truncated Higher-order Differential-linear Distinguishing (Known-key) Integral/Square Boomerang Mod n Related-key Slide Rotational Side-channel Timing Power-monitoring Electromagnetic Acoustic Differential-fault XSL Interpolation Partitioning Rubber-hose Black-bag Davies Rebound Weak key Tau Chi-square Time/memory/data tradeoff Standardization AES process CRYPTREC NESSIE NSA Suite B CNSA Utilization Initialization vector Mode of operation Padding v t e Cryptography General History of cryptography Outline of cryptography Classical cipher Cryptographic protocol Authentication protocol Cryptographic primitive Cryptanalysis Cryptocurrency Cryptosystem Cryptographic nonce Cryptovirology Hash function Cryptographic hash function Key derivation function Secure Hash Algorithms Digital signature Kleptography Key (cryptography) Key exchange Key generator Key schedule Key stretching Keygen Machines Ransomware Random number generation Cryptographically secure pseudorandom number generator (CSPRNG) Pseudorandom noise (PRN) Secure channel Insecure channel Subliminal channel Encryption Decryption End-to-end encryption Harvest now, decrypt later Information-theoretic security Plaintext Codetext Ciphertext Shared secret Trapdoor function Trusted timestamping Key-based routing Onion routing Garlic routing Kademlia Mix network Mathematics Cryptographic hash function Block cipher Stream cipher Symmetric-key algorithm Authenticated encryption Public-key cryptography Quantum key distribution Quantum cryptography Post-quantum cryptography Message authentication code Random numbers Steganography Category

---
Adapted from the Wikipedia article [Timing attack](https://en.wikipedia.org/wiki/Timing_attack) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Timing_attack?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.