Is Your Software Leaking Sensitive Data?

Traditionally, when we think about how to make our software secure, we ask ourselves two questions:

  1. Do we transfer data over secure connections so that no man in the middle can read the transmitted data?
  2. Is our code free from bugs so that it can be exploited in order to gain access to sensitive data, or to execute malware code?

It turns out, however, our software can be insecure even if the answer is yes to both of these questions. In this article, we show you why.

Let’s consider that our application checks whether a user has entered the correct password or not using the following method:

boolean checkPassword(String input) {
  return "ourpassword".equals(input);
}

Let's also consider that the equals method is implemented as follows, which is a common way for most of the programming languages:

(01) class String {
(02)   boolean equals(String other) {
(03)     if (other == null) {
(04)       return false;
(05)     }
(06)     if (this.length() != other.length()) {
(07)       return false;
(08)     }
(09)     for (int i = 0; i < this.length(); ++i) {
(10)       if (this.getCharAt(i) != other.getCharAt(i)) {
(11)         return false;
(12)       }
(13)     }
(14)     return true;
(15)   }
(16) }

If our equals method looks like this, it is insecure, and so is our checkPassword method. Why? Because it leaks out the password! Let's see how.

Consider the following method invocations:

"ourpassword".equals("123");
"ourpassword".equals("badpassword");

The first invocation has as its sole argument a password of incorrect length. Therefore, the execution of the equals method terminates at the line 7. The second invocation has as its sole argument a password of correct length. Thus, the execution of the equals method gets pass the line 7 and terminates at least at the line 11. Hence, the second invocation takes more time than the first one. We can exploit this difference in execution times using the following code:

int length = 0;
int maxDelta = 0;
for (int i = 0; i < maxTriedLength; ++i) {
  String input = // create a dummy string of length i
  long start = getCurrentCPUTime();
  checkPassword(input);
  long end = getCurrentCPUTime();
  long delta = end - start;
  if (delta > maxDelta) {
    maxDelta = delta;
    length = i;
  }
}

We iteratively run checkPassword method with a string of length 0, 1, 2, 3 etc. and measure execution times. The longest execution time will be for the correct password length.

One can object that the difference between the execution times is so small that it cannot be measured. While it is true, we can overcome this obstacle by calling checkPassword method multiple times with the same input.

After obtaining the password length, we use the same idea for getting the first character of the password. If we run checkPassword method with a string of the correct length and the incorrect first character, the equals method will terminate in the first iteration of the for cycle at the line 11. If we run it, however, with a string of both the correct length and the correct first character, the equals method will terminate at least in the second iteration of the for cycle at the line 12. Thus, if the first character is correct, the execution of the checkPassword method takes longer. We can use a code similar to the above-mentioned one to obtain the first character, then the second character, etc.

Even though there is no bug in the equals method in the traditional sense, the method is insecure, because it leaks the string being tested via the execution time of the method.

Note that the above mentioned procedure for getting the password is much more effective than the straightforward procedure of testing every possible string. There is exponentially many strings of a given length, so the straightforward procedure takes exponential time (in terms of string length). The presented procedure, on the other hand, needs only linear time to get the password.

All this shows how important it is to design applications in a way that a user can enter a password incorrectly only small number of times before the application blocks the user account, and requires the user to change the password. Many real-world applications, thankfully, do that. There is, however, large amount of applications that are vulnerable.

Bad news is that there are so many different ways in which your software and hardware can leak data, e.g. via execution time, temperature, noise, etc., that it is almost impossible to create fully secure system. For example, researchers were able to recover 4096-bit RSA key used to decrypt emails just by listening to the sound coming out of a computer.