Introduction to Timing Attacks!
There is an ever-increasing need for speed in the digital world, which has lead to the software & hardware development process being aimed at improving the performance by inculcating several optimization methods during implementation. While these optimizations are significant at achieving much better efficiency, they also introduce subtle security loopholes that are, at times, ignored or overlooked. A timing attack is one such exploit that takes advantage of implementation flaws, which can have a catastrophic impact in critical scenarios, resulting in compromised security.
A timing attack is a security exploit that enables an attacker to spot vulnerabilities in a local or a remote system to extract potentially sensitive or secret information by observing the concerned system's response time to various inputs. A timing attack is a type of a broader class of attacks called Side-channel attacks!
What is a Side-Channel Attack?
Side-Channel Attack (SCA) refers to any attack which exploits implementation flaws in a computer system to retrieve sensitive information such as passwords. SCAs are a form of reverse engineering that takes advantage of information exhaust from the computer. Specifically, it 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 break the encryption system by using the acquired information to discover the associated encryption key.
How does a Timing Attack work?
Let us consider a simple example of implementing a string compare function, where we have to return true if the strings match and return false if they don’t.
In the above function, we first compare the two strings' lengths and then compare the individual characters if they are of equal length. While iterating over the loop, if we encounter two different characters, we return false. If we do not find any difference, we return true.
Although it looks fine, there is a flaw in this implementation which most of us don’t realize immediately!
Consider the scenario where this function is used for authenticating users on a website (or any app for that matter).
- One of the two strings would be the password entered by the user (let’s say it’s assigned to s1), and the other string, s2, would contain the correct password (or it’s respective hash value in practical implementations) of the user from the database.
- Assuming the required password to be a ten-digit integer, it would take an attacker 10¹⁰ possible combinations to use brute force to find it.
But this is where things get interesting!
Let us assume that the correct password is 5263987149, and the attacker starts guessing from the first digit (beginning from 0000000000). He measures that the system returns false after x seconds. After getting the same response time x for the first five guesses (i.e., from 0000000000 to 4000000000), he notices that the system takes a slightly longer time to respond ( x + ∆ x) when he tries 5000000000. This is because the for loop during its first iteration doesn’t return false since the first digit of the user input and the stored password is equal. Hence, the loop runs another iteration, thereby taking more time (∆x). Therefore, the attacker knows that the first digit he tried now is correct. He can repeat the same procedure to guess the remaining digits by observing the pattern of ∆x. In this way, it would take the attacker only 10*10 guesses at the maximum to find the correct password, compared to 10¹⁰ possible combinations while trying to brute force it…
To fix this flaw, we need to prevent the leakage of information about the pattern in execution time, enabling the attacker to know which character in the array differs. This implies that the loop needs to run a fixed number of times, irrespective of the number of correct/wrong elements between the two strings.
To do that, we have a variable flag which is initialized to True (after comparing the string lengths). Inside the for loop, we have the same if statement as before, but this time we store the boolean value in a flag variable instead of returning it as soon as we encounter a wrong digit. This ensures that the loop iterates through every element of the array and takes a constant amount of time, regardless of how many digits match. Therefore the timing-attack vulnerability in the concerned function is resolved.
Although real-world implementations wouldn’t be as easy to exploit (and counter) as shown above, this small function illustrates the essence of a basic timing-attack and helps understanding it in a simple manner.
That is the logic behind a simple Timing Attack!
Timing attacks in real-time scenarios…
Many encryption algorithms such as RSA, ElGamal, and Digital Signature Algorithm are practically vulnerable to timing attacks. In particular, RSA implementation uses square and multiply algorithm for modular exponentiation in one of the steps, whose execution time has a linear dependency on the number of high bits in the key, making the system prone to timing attack. Though this doesn’t readily reveal the key, statistical analysis of timing information corresponding to a large set of inputs can make it possible for the attacker to retrieve the complete key.
There are numerous occasions in which timing attacks have been successfully executed in real-time. The attack on RSA implementation has been demonstrated across a network, on SSL enabled web servers. The most notable vulnerability involving timing attacks are Meltdown & Spectre (in 2017), which affected most CPUs. In fact, Spectre is the most powerful timing attack in history.
Protection against timing attacks
The basic idea to counter timing attacks is that we need to ensure information regarding execution time doesn’t have a pattern that would enable the adversary to predict the key. In general, we can say that execution time shouldn’t have any direct or indirect data dependency.
In the case of RSA, we can use two techniques to avert time-data dependency. Firstly, we can use a padding scheme called OAEP (Optimal Asymmetric Encryption Padding), which prevents chosen ciphertext attack ( it refers to the analysis of plaintext & the corresponding ciphertext of the concerned system). Then, a randomness algorithm is used before decryption to prevent non-fixed time computation in RSA.
Conclusion
Timing attacks and other side-channel attacks are often overlooked while designing an algorithm, and poor implementations leave it defenceless against an adversary. They can potentially leak vital information, leading to the revelation of the key, thereby compromising the crypto-system. Compiler optimizations and many other methods aimed at reducing execution time & improving performance are the root causes for the emergence of flaws that are vulnerable to side-channel attacks.
Therefore, extra attention must be given during the implementation of the crypto algorithm to make it resistant to these attacks, even if it comes at the cost of a reduction in performance, especially in circumstances where security is of utmost priority.
Resources
Have a Happy Learning Ahead!
This article is published as a part of the ‘Hacker Series’ under Spider Research and Development Club, NIT Trichy on a Web Wednesday!
