How To Find and Fix Timing Attacks in Your Java Code
Prevent timing attacks with CodeQL
A message authentication code (MAC) or a digital signature may be used to authenticate a message and to protect its integrity.
When checking a signature, it is better to use a constant-time algorithm. Otherwise, an attacker may be able to forge a valid signature for an arbitrary message by running a timing attack.
Although it is a pretty sophisticated attack, sometimes it can be a real threat. Let’s see how such issues may be detected with CodeQL in Java applications.
Signing A Message
Here is an example scenario that shows how a signature can be used.
A sender and a receiver share a secret key. The sender calculates a signature over a message using the key. Next, the sender sends both the message and the signature. Then, the receiver calculates a signature over the received message and compares the calculated signature with the received one. If the signatures match, the receiver knows that the message was created by the sender who knows the key, and therefore accepts the message. If the signature doesn’t match, the receiver rejects the message.
If an attacker doesn’t know the key, they can’t create a signature for an arbitrary message. Therefore, the attacker’s messages are going to be rejected assuming that replay attacks are out of scope.
Timing Attack Against Signature
The problem occurs when an application doesn’t use a constant-time algorithm for validating a signature. Here is an example of vulnerable code:
The method Arrays.equals() returns false right away when it sees that one of the input's bytes are different. It means that the comparison time depends on the contents of the arrays. This little thing may allow an attacker to forge a valid signature for an arbitrary message byte by byte. If you want to learn more, check out this video by Dan Boneh. By the way, if you don't know much about cryptography, but you are interested to learn more, I'd recommend his free course on Coursera.
Preventing Timing Attacks
It is usually a one-line fix: just use MessageDigest.isEqual() for validating a signature. The above code may be fixed just by replacing Arrays.equals() with MessageDigest.isEqual():
Even though timing attacks are quite difficult to run, it may be better to stay on the safe side and apply such one-line fixes to make sure timing attacks are not possible. It looks quite unlikely that such a fix can introduce a serious issue. Maybe you’re going to notice some performance degradation since MessageDigest.isEqual() literally examines all the bytes, but the impact should be pretty small.
Besides Arrays.equals() there are many other methods that don't use a constant-time algorithm. For example, String.equals(). Here CodeQL comes into play.
Detecting Timing Attacks With CodeQL
In case you don’t know, CodeQL is a code analysis engine. It lets you write queries for your code to detect various issues including security ones.
Recently, I wrote a couple of CodeQL queries that can detect opportunities for timing attacks in Java applications.
The first query PossibleTimingAttackAgainstSignature.ql is pretty simple:
It looks for the following data flows:
- A source of a data flow is methods of
MAC,SignatureandCipherclasses that can produce a signature. Strictly speaking,Cipheris used for encryption/decryption but it can be used to implement a custom MAC as well. That's why it is also considered here. Such sources are defined in theCryptoOperationSourceclass and its subclasses. - A sink is one of the methods that doesn’t use a constant-time algorithm for comparing inputs. It covers not only
Array.equals()but many other methods.NonConstantTimeComparisonSinkdefines such sinks.
The above is implemented in NonConstantTimeCryptoComparisonConfig for tracking data flows with CodeQL:
Strictly speaking, it is not enough for a successful timing attack that just a non-constant-time algorithm uses for validating a signature. Additionally, an attacker has to be able to send to the receiver both a message and a signature. The query PossibleTimingAttackAgainstSignature.ql does not check that. But the second query TimingAttackAgainstSignature.ql does:
The difference is that it calls includesUserInput() predicate on both source and sink:
CryptoOperationSource.includesUserInput()checks whether untrusted data is used to calculate a signature withMAC,SignatureorCipherclasses.NonConstantTimeComparisonSink.includesUserInput()checks whether untrusted data is used in the comparison procedure.
That makes the query much stricter than the first one, therefore it should produce fewer false positives. But of course, it is more likely to skip some true positives.
