Annotation
This article will provide an overview of timing attacks, including how they work, how to avoid them, and a simple code example in C#. The code used in this article can be found on the following GitHub repository: www.github.com/menaruben/timingattacks.
Introduction
Consider a scenario in which you are standing in front of a locked door that requires the correct 4-digit password to be entered to gain access. It is possible to open the door without knowing the password. In fact, all that is required is a stopwatch. The password can be determined digit by digit by observing the amount of time taken to process the input. This is known as a timing attack.
The following video, available at https://youtu.be/2-zQp26nbY8, provides an excellent illustration of this concept, as demonstrated by Joe Grand.
To validate the input, the software must compare the input to the actual secret (or its hash). In Java, for instance, we use the String.equals method to determine if two strings are equal:
String.equals calls StringLatin1.equals to determine equality. If the strings are not the same length, we return false. Otherwise, we check each character and return true if there is no mismatch. If a mismatch is found, we return false. We can also write this in C#:
But how can a string comparison be dangerous?
It is worth noting that string comparisons are susceptible to timing attacks. Timing attacks are a form of side-channel attack, where the attacker attempts to gain insight into a system or secret by analysing the time taken for a function or program to execute on different inputs. To illustrate this, we can consider the following example:
The _secret field contains the user’s password, while the _cmp field contains a function that takes two Strings and returns a Boolean value. Upon trying to log in, the _cmp function is evaluated with the guess and secret as arguments. If the result is true, this indicates that the two strings are identical, thereby allowing the user to be logged in. Conversely, if the result is false, this indicates that the two strings are not identical, and therefore the user is not logged in.
On closer examination of the CompareEarlyExit method, it becomes evident that the greater the extent of similarity between the two strings, the longer the process will take, because it iterates over a greater number of characters. To illustrate this, consider the evaluation of CompareEarlyExit(„Hello“, „Hallo“). In this case, the function would return false on the second iteration, as the character „e“ is not equal to the character „a“.
By exploiting this behaviour, we can obtain the length of the secret and the actual characters of the secret. This demonstrates that the timing variation of the String.equals method in Java is data dependent. This is a universal principle that applies to any method, function, or operator in any language that uses this type of comparison.
For the sake of simplicity, we will assume that we already have the length of the secret and the character set. We will now define a character set ranging from 0 to 9 and define our secret. We will also create a new account using the CompareEarlyExit function mentioned above.
We will now introduce a new Attacker class that contains the FindSecret method.
In the FindSecret method, we create a new StringBuilder object with the secretLength number of dashes (represented by the character „–“). We then iterate through each character of the current guess and call the FindNextChar method.
The FindNextChar method iterates through every character in the charset, replacing the current index with the current character and adding the time it takes to login to a dictionary called charTimes. The more similar the strings, the longer it takes to compare them. The „correct“ character is therefore the one that took the longest in total.
We then return to the FindSecret method, which replaces the current index with the character found and prints the current guess to the terminal. This process is repeated until the end of the secret guess is reached.
Let us create a new Attacker and test our ability to guess the result.
The attacker was able to gain access to the system. This is an unfortunate outcome. If the time required to complete a function is dependent on the input, we refer to this as a data-dependent timing variation.
One possible solution would be to avoid early return and continue iterating through each character, even in the event of a mismatch:
This method is less optimal in terms of performance but does eliminate some data dependency. It is not completely data independent because we still have data-dependent control flow, since we only assign result to false if there is a mismatch.
Additionally, some compilers would „optimize“ this code and transform it back to the CompareEarlyExit method, therefore returning as soon as the result is false, because once the result is false it never is true again.
The optimization is known as “short-circuiting”. This is a technique employed by compilers and interpreters to ensure that unnecessary expressions are not evaluated. To illustrate this, consider the following example:
The if statement would evaluate the first expression, “a is not null”. If that is false, it means that a is null and the second condition, “a.Add(b) > 5”, would not be evaluated since the and (&&) condition will never be satisfied.
However, if the condition „a is not null“ is true, the second condition would also be evaluated. Many compilers do short-circuiting, but this can also introduce new security vulnerabilities, such as side channels.
It is necessary to add an annotation to prevent the compiler from optimising this method, as this may result in unintended changes. It is important to note that the compiler optimizes in different ways, and therefore it is not always possible to predict its actions.
It is also important to highlight that the produced .NET IL code of CompareFullscan is not being optimized to behave in the same way as CompareEarlyExit. However, there is a possibility that this may occur, depending on the language and its compiler and version.
Let us create a new account using the CompareFullscan function to determine whether the attacker can correctly guess the secret:
As can be seen, this solution proved effective for our example. However, we still advise against using this approach because the CompareFullscan method has data-dependent control flow.
OpenSSL has a memcmp function (used in C for comparisons) called CRYPTO_memcmp that provides a secure and reliable way to compare sensitive data.
The OpenSSL implementation makes use of bitwise operations to determine equality. This approach is the most secure compared to CompareFullscan and CompareEarlyExit, as it eliminates the potential for data dependency issues.
Let us test the CRYPTO_memcmp function in C# (here CompareOpenssl) to ensure that the attacker cannot gain access:
The attacker was unable to gain access. In comparing the various options, it was found that CompareOpenssl is the most secure, as it does not return early (unlike CompareEarlyExit) and has no data-dependent control flow (unlike CompareFullscan, which may be optimised by the compiler to behave like CompareEarlyExit).
Discussion
Given the nature of the attack, one might conclude that timing attacks over the network are not possible because of network jitter and its potential to impact the results. However, this is not the case.
In 2005, Daniel J. Bernstein published a paper, „Cache-timing attacks on AES,“ which demonstrated a complete AES key recovery timing of a network server on another computer. Bernstein then explained that this was not an issue with the implementation of AES but rather with its design. [1]
In 2003, David Brumley and Dan Boneh published a paper entitled „Remote Timing Attacks are Practical“. The paper describes how to implement a remote timing attack against OpenSSL. The client was able to extract the private key (RSA) stored on the server. The attack exploits the Chinese remainder theorem [2], a popular optimization for RSA implementations. [3]
A 2024 paper by Moritz Schneider, Daniele Lain, Ivan Puddu, Nicolas Dutly and Srdjan Capkun from ETH Zürich, called „Breaking Bad: How Compilers Break Constant-Time Implementations“, also highlights this issue. Constant-Time implementations are programs/algorithms with a data independent timing variation. This study discovered that “previously-considered safe code-patterns are being transformed into secret-dependent operations at the binary level” and that even includes libraries that were formally verified to be free of side channels. This happened across all processor architectures, compilers and optimization levels. However, it seems like popular processor architectures (for example x86-64) suffer less from that issue. Nonetheless, this still shows that defensive programming patterns can be nullified by compiler optimizations. [4] However, a lot of programming languages have annotations or keywords to let the compiler know not to optimize a function/method.
Closing remarks
I hope this has provided a helpful overview of timing attacks, their potential risks and how to prevent them. Should you have any further questions or identify any errors, please do not hesitate to raise them on the GitHub repository.
It is not always the case that the fastest solution is the most secure. This is something I wanted to highlight with the CompareEarlyExit, CompareFullscan and CompareOpenssl functions. While performance and speed are important factors, they should not be the only criteria when choosing an algorithm. As you can see, there is a risk of leaking information if strings are not compared safely.
It is important to be aware that many cryptographic algorithms are vulnerable to timing attacks, often depending on the implementation. This is particularly relevant when implementing software. However, in some circumstances it may be difficult to implement programs with data-independent timing variations due to compiler optimizations.
If you work with sensitive data, it is essential to ensure that there is no timing variation that could be exploited. It is also crucial to verify that the compiler does not introduce any unintended changes. If libraries are used, it is vital to review their source code. As previously mentioned, even popular and well-tested projects like OpenSSL can have vulnerabilities.
References
1: https://cr.yp.to/antiforgery/cachetiming-20050414.pdf
2: https://en.wikipedia.org/wiki/Chinese_remainder_theorem
