Algorithm implementation is one of the key parts of ensuring your data is secure. If you have implemented a certain protocol, but you use vulnerable operations such as scanf in c, then all the work you put in has essentially gone out of the window.
In light of this, a new area of cryptographic implementation has arisen. This is branchless programming. In branchless programming, the fundamental idea of if..else is avoided. Now, in many cases this has been brought in for optimisation, not just for purely cryptographic reasons, but it does carry over.
Although, new(ish) research has shed light on how branching in cryptographic functions can cause timing attacks. A timing attack occurs when the time spent inside the cryptographic algorithm is analysed to determine how long it takes to execute the entire algorithm. To avoid this, you would try to make the function run in constant time, another very interesting area in code optimisation. In essence, Constant, or O(1), time dictates that no matter what the input, the timing of execution won’t change. In the below examples, the inputs are very small, but no matter how long the input, it will always go through every element. Now, this would be classes as constant due to the testing of all characters. An alternative to constant time would be linear time, or O(n). This means that depending on the size of the input, depends on the length of time the algorithm will take.
One example of converting a function from branched, to branchless constant would be a string comparison algorithm. Take this pseudocode:
In this example, if we tested HELLO and HELP, it will return after 4 loops. This would change depending on the data, meaning it is not constant. However, if we consider the following pseudocode:
This way, it will test every character and return when the entire string has been evaluated. This example was adapted from another article.
Despite this, timing attacks are a very situation-specific attack and depend on the attacker knowing the hardware. To avoid this, follow Kerkchoff’s Principles and do not rely on security through obscurity in your implementation.
One real-world example of an algorithm being vulnerable to a Timing Attack was displayed in 2003 by Boneh and Brumley. In this attack they managed to obtain a servers private key through SSL as it was shown to have correlation between the private key and the time taken to encrypt data. So, to counter this, blinding techniques were used. This article will not go further into depth in this area but in this case blinding was used to remove the aforementioned correlation.
Despite the Boneh and Brumley attack happening nearly 20 years ago, Timing Attacks do still happen. For example, a new version of timing attacks has been shown to work against HTTP/2 and is also remote. However, this type of attack differs slightly from traditional Timing Attacks as it is what is known as a Timeless Timing Attack (paradoxical right?). In this new form, researchers have been able to leverage the fact that many networks use a form of concurrent processing and this allows for the analysis of the order of responses. The researchers involved said:
“These concurrency-based timing attacks infer a relative timing difference by analyzing the order in which responses are returned, and thus do not rely on any absolute timing information”
Arguably, this makes the attack slightly more dangerous due to the fact that less information is required about the system.
For further information about branchless programming please visit: https://www.chessrogramming.org/Avoiding_Branches
For further information about timing attacks please visit: https://tlseminar.github.io/timing-attacks/
Written by Isaac