A timing attack is a sophisticated way to circumvent security mechanisms and discover vulnerabilities by studying how long it takes the system to respond to different inputs. In a timing attack, the attacker gains information that is indirectly leaked by the application. This information is then used for malicious purposes, such as guessing the password of a user. Timing attacks are part of a wider family of attacks, called 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 utilizes 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.
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 that is 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 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.”
The most notable vulnerability 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.
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 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.)
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.