A timing attack is a type of side-channel cyber attack that exploits the time taken by a system to process various inputs to identify security vulnerabilities. By analyzing these response times, an attacker can indirectly gather information leaked by the application. This technique can be used for malicious purposes, such as guessing a user's password or breaking encryption methods.
Side-channel attacks exploit unintended information leakage from a system. These attacks pose significant threats not only to classical cryptographic systems, but also to post-quantum cryptography, including quantum-resistant mechanisms like the Kyber key encapsulation mechanism (KEM). By leveraging subtle timing discrepancies, attackers can uncover critical weaknesses in even the most advanced cryptographic protocols.
What are side-channel attacks?
A side-channel attack is any attack based on information gained from the implementation of a computer system, rather than weaknesses in the implemented algorithm (e.g. cryptanalysis and software bugs). An attacker uses the data gained from monitoring patterns in physical parameters such as EMF radiation, power consumption, response times, and acoustic emissions during cryptographic operations performed by the system. The attacker can then break encryption by leveraging this information to discover the associated key. Surprisingly detailed sensitive information is being leaked out from a few high-profile, top-of-the-line web applications in healthcare, taxation, investment and web search despite HTTPS protection.
Real-world example: Apple M-Chip Vulnerability
To illustrate the real-world dangers of side-channel attacks, let’s look at a recent vulnerability discovered in Apple’s M1, M2 and M3 chips.
It leverages a hardware component called a data memory-dependent prefetcher (DMP) designed to improve performance by pre-loading memory addresses. However, in these chips, the DMP can misinterpret encryption keys as pointers to memory addresses, creating a side-channel.
Attackers can exploit this side-channel by running a program like “GoFetch,” which tricks the DMP into treating key values as memory addresses, which can be leaked. These values are then pieced together through repeated executions, eventually revealing the entire encryption key. This vulnerability can compromise several cryptographic algorithms, including both traditional and quantum-resistant encryption.
SSL/TLS Certificates and Their Prevalence on the Dark Web
How do timing attacks work?
Timing characteristics of cryptographic operations vary depending on the encryption key. Different systems require different amounts of time to process different inputs. The variables that influence the timing characteristics include performance optimizations, branching and conditional statements, processor instructions, RAM and cache hits.
A timing attack looks at how long it takes a system to do something, and uses statistical analysis to find the right decryption key and gain access. The only information needed by the attacker is the timing information revealed by the algorithms of the application. By supplying various inputs to the application, timing the processing and statistically analyzing the information, the attacker can guess the valid input.
The most notable vulnerabilities involving timing attacks are Meltdown and Spectre, which were discovered in 2017 and affected most CPUs. In fact, Spectre is considered the most powerful timing attack in history. Further information about these vulnerabilities can be found on the website created by the researchers who discovered them.
How do timing attacks threaten encryption?
Timing attacks, when successful, can undermine any type of encryption, including both classical and post-quantum algorithms.
Classical Example: Exposing RSA without breaking RSA
The canonical example of a timing attack was designed by cryptographer Paul Kocher. He was able to expose the private decryption keys used by RSA encryption without breaking RSA. In his paper, Kocher mentions:
“By carefully measuring the amount of time required to perform private key operations, attackers may be able to find fixed Diffie-Hellman exponents, factor RSA keys, and break other cryptosystems. Against a vulnerable system, the attack is computationally inexpensive and often requires only known ciphertext. Actual systems are potentially at risk, including cryptographic tokens, network-based cryptosystems, and other applications where attackers can make reasonably accurate timing measurements.”
The general belief was that timing attacks were only applied in the context of hardware security tokens such as smartcards. The assumption was that timing attacks could not be used to attack general purpose servers, since decryption times are masked by many concurrent processes running on the system. However, research by David Brumley and Dan Boneh of Stanford University challenged this assumption. The two researchers demonstrated that they “can extract private keys from an OpenSSL-based web server running on a machine in the local network. Our results demonstrate that timing attacks against network servers are practical and therefore security systems should defend against them.”
Post-Quantum Example: KyberSlash
Although a quantum computer with the ability to break RSA encryption is still a ways off, businesses are becoming increasingly concerned with “steal now, decrypt later” attacks—which makes the December 2023 “KyberSlash” vulnerability so concerning.
The KyberSlash vulnerability involves sending fabricated ciphertext and measuring how long it takes the system to decipher it. Based on this, a threat actor has the ability to infer timing and reverse engineer key pairs. Even the official NIST implementation of Kyber, CRYSTALS-Kyber, was found vulnerable prior to this, in February 2023, when a Swedish team used a complicated, deep learning-based side channel attack on it.
The team responsible for developing the Kyber KEM immediately issued a patch, as versions of this standard had already been adopted by Google, Signal, and Mullvad VPN. (Though Mullvad has openly stated its services weren’t impacted.)
- Google: Used in its hybrid efforts to protect TLS traffic on its Chrome browser.
- Signal: Used to help guarantee end-to-end encryption of Whatsapp and Google messages
How to protect against timing attacks
The basic idea behind counter timing attacks is to ensure that information related to the execution time doesn’t have a pattern that would enable the adversary to predict the key. As Kocher mentions in his paper: “The most obvious way to prevent timing attacks is to make all operations take exactly the same amount of time. Unfortunately, this is often difficult. Making software run in fixed time, especially in a platform-independent manner, is hard.”
Brumley and Doneh offer three possible solutions to the classical problem: “The most widely accepted defense against timing attacks is to perform RSA blinding.” And they continue saying that “Two other possible defenses are suggested often but are a second choice to blinding. The first is to try and make all RSA decryptions not dependent upon the input ciphertext… Another alternative is to require all RSA computations to be quantized, i.e., always take a multiple of some pre-defined time quantum.” (See paper here.)
Conclusion
Timing attacks and other side-channel attacks are often overlooked while designing an algorithm. Poor implementations of these cryptographic algorithms can make them vulnerable to an adversary. They can leak vital information, disclose the encryption key and compromise the encryption mechanism. The root causes of such vulnerabilities are the efforts to reduce execution time and improve performance of cryptographic algorithms. The best way to mitigate these vulnerabilities is to pay attention during the implementation of the algorithms to make them resistant to these attacks, even if it comes at the cost of a reduction in overall performance. This is especially important where security is top of the priority list.