Attacks in time - a fairy tale or a real threat?

I wanted to write the first article on Habr completely about something else, but one fine day my work colleague decided to get bogged down and make protection against Timing attack. Not long understood in various materials on this topic, I caught fire and decided to write my bike and ride it around the laboratory to experiment.



The result of this small experiment under the cut.

The essence of the attack is that the attacker knows, or at least guesses, the authentication algorithm and tries to pick up the key gradually. Substituting different values ​​and measuring the test time, you can see that for some variants of keys, the execution time is longer (or faster) than for others.
')
In the beginning, I wanted to make a client and a server, so that I really wanted to do it on the Internet, but I decided to do without difficulties, because I wanted to check the very idea of ​​how much it works at least in the laboratory. For the experiment, an authentication function will be used as a test subject, in which we will simply compare two keys element by element.

static bool check_secret_key(int[] key) { for (int i = 0; i < _secret_key.Length && i < key.Length; i++) if (key[i] != _secret_key[i]) return false; return _secret_key.Length == key.Length; } 

In this case, if the first key elements coincide, the operation takes longer, since it proceeds to check the following elements. The selection algorithm is quite simple: we look through the first number, the variant that lasts the longest - we leave, then the second ... and so on.
You can look at the algorithm in detail at the end of the article, and those who wish can even play around.

At the first start-up, he received an almost random result. I began to gradually increase the number of tests and on the third run I received the correct sequences. And as a result, in the laboratory, the method works and works quite well.

What improvements can be made after some observation:
1) if the enumeration of the next number is performed in a time comparable to the previous one, then it makes sense to take a step back, most likely made a mistake;
2) to choose the next number not after a fixed number of tests, but somehow more intellectually, since with an increase in the number of correct elements, the time to check increases and the difference becomes less noticeable.


The screenshot clearly shows the correct result.

Here is what we get in the console (the secret key is displayed in the first line):

 21,87,70,6,40,46,49,4,25,68 21 21,87 21,87,70 21,87,70,6 21,87,70,6,40 21,87,70,6,40,46 21,87,70,6,40,46,49 21,87,70,6,40,46,49,4 21,87,70,6,40,46,49,4,25 Found: 21,87,70,6,40,46,49,4,25,68 

It is very similar to how passwords are selected in films, and I always thought that this was a game for the public, but it turns out that there is a grain of truth in this.

Finally

Perhaps this method of attack is no longer entirely up to date (there are a lot of nodes in the network and each one contributes its own random value), and it seems not difficult to defend against it, but perhaps in some tricky, at first glance, hashing algorithm this will be more pronounced and can be used by the attacker for their own purposes.
Although it may be relevant for the selection of serial numbers for offline programs.

Thanks for attention!

UPD: time calculation on how much a method is more effective than a complete iteration in this particular case.
The key is an array of numbers of n = 10 elements with values ​​from 0 to 99 (m = 100) inclusive.
Then:
for a full search, the number of checks is m ^ n = 100 ^ 10 = 10 ^ 20;
for the realized time attack n * a * m * b, where a and b are empirical constants and are equal to 1500, we get 10 * 1500 * 100 * 1500 = 2.25 * 10 ^ 9
As you can see, in this particular case , the result differs by more than 10 orders of magnitude , which speaks of its effectiveness as compared with brute force.

Wiki Links

1) Attack on time
2) Attack on third-party channels