Attacks on time - a fairy tale or a real threat?
I wanted to write the first article on Habr about completely different, but one fine day the colleague on work decided to be confused and to make protection against "Timing attack". Not long understanding various materials on this subject, I caught fire and decided to write my bike and ride it in the laboratory to experiment.
The result of this little experiment under the cut.
The essence of the attack is that the attacker knows, or even guesses, about the authentication algorithm and tries to pick up the key gradually. Substituting various values and measuring the verification time, you will notice that for some key options, the execution time is longer (or faster) than for others.
In the beginning, I wanted to make a client and a server, so that it was truly on the Internet, but I decided to do without difficulties, because I wanted to test the idea itself, how much it works even in laboratory conditions. For the experiment, an authentication function will be used as a test subject, in which we will simply compare the two keys element by element.
In this case, when the first elements of the key match, the operation takes longer, as it proceeds to check the following elements. The selection algorithm is quite simple: iterate over the first number, the option that runs the longest - leave, then the second ... and so on.
You can consider the algorithm in detail at the end of the article, and those who wish can even play around.
At the first launches I got an almost random result. He began to gradually increase the number of tests and already on the third launch he received the correct sequences. And as a result, in laboratory conditions, the method works and works quite well.
What improvements can be made after some observation:
1) if the search for the next number is performed in a time comparable to the previous one, then it makes sense to take a step back, most likely they were mistaken;
2) choose the next number not after a fixed number of tests, but somehow more intellectually, because with an increase in the number of correct elements, the verification time increases and the difference becomes less noticeable.
The correct result is clearly visible in the screenshot.
Here's what we get in the console (the secret key is displayed on the first line):
It is very similar to how passwords are selected in films, but I always thought that this was a game for the public, but it turns out that this has a grain of truth.
Perhaps this method of attack is no longer quite relevant (there are a lot of nodes in the network and each contributes its own random value), and it seems like it is not difficult to defend against it, but it will be more pronounced in some tricky, at first glance, hashing algorithm and can be used by an attacker for their own purposes.
Although it may be relevant for the selection of serial numbers for offline programs.
Thanks for attention!
UPD: calculating the time by how much the method is more effective than exhaustive search 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 complete search, the number of checks is m ^ n = 100 ^ 10 = 10 ^ 20;
for the implemented time attack n * a * m * b, where a and b are empirical constants and equal to 1500, we get 10 * 1500 * 100 * 1500 = 2.25 * 10 ^ 9
As you can see, in this particular case , the result is different more than 10 orders of magnitude , which indicates its effectiveness compared to exhaustive search.
1) Time Attack
2) Side Channel Attack
The result of this little experiment under the cut.
The essence of the attack is that the attacker knows, or even guesses, about the authentication algorithm and tries to pick up the key gradually. Substituting various values and measuring the verification time, you will notice that for some key options, the execution time is longer (or faster) than for others.
In the beginning, I wanted to make a client and a server, so that it was truly on the Internet, but I decided to do without difficulties, because I wanted to test the idea itself, how much it works even in laboratory conditions. For the experiment, an authentication function will be used as a test subject, in which we will simply compare the 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, when the first elements of the key match, the operation takes longer, as it proceeds to check the following elements. The selection algorithm is quite simple: iterate over the first number, the option that runs the longest - leave, then the second ... and so on.
You can consider the algorithm in detail at the end of the article, and those who wish can even play around.
At the first launches I got an almost random result. He began to gradually increase the number of tests and already on the third launch he received the correct sequences. And as a result, in laboratory conditions, the method works and works quite well.
What improvements can be made after some observation:
1) if the search for the next number is performed in a time comparable to the previous one, then it makes sense to take a step back, most likely they were mistaken;
2) choose the next number not after a fixed number of tests, but somehow more intellectually, because with an increase in the number of correct elements, the verification time increases and the difference becomes less noticeable.
The correct result is clearly visible in the screenshot.
Here's what we get in the console (the secret key is displayed on 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, but I always thought that this was a game for the public, but it turns out that this has a grain of truth.
Finally
Perhaps this method of attack is no longer quite relevant (there are a lot of nodes in the network and each contributes its own random value), and it seems like it is not difficult to defend against it, but it will be more pronounced in some tricky, at first glance, hashing algorithm and can be used by an attacker for their own purposes.
Although it may be relevant for the selection of serial numbers for offline programs.
Thanks for attention!
UPD: calculating the time by how much the method is more effective than exhaustive search 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 complete search, the number of checks is m ^ n = 100 ^ 10 = 10 ^ 20;
for the implemented time attack n * a * m * b, where a and b are empirical constants and equal to 1500, we get 10 * 1500 * 100 * 1500 = 2.25 * 10 ^ 9
As you can see, in this particular case , the result is different more than 10 orders of magnitude , which indicates its effectiveness compared to exhaustive search.
Wiki Links
1) Time Attack
2) Side Channel Attack
Subject's full listing
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
namespace timing_attack
{
class Program
{
const int _max_value = 100;
static int[] _secret_key = new int[10];
static void generate_secret_key()
{
var rand = new Random();
for (int i = 0; i < _secret_key.Length; i++)
_secret_key[i] = rand.Next(_max_value);
}
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;
}
static void print_key(int[] key)
{
Console.WriteLine(string.Join(",", key.Select(it => it.ToString())));
}
private static void crack_key()
{
int n = 1500;
List key0 = new List();
while (key0.Count <= _secret_key.Length)
{
TimeSpan[] times = new TimeSpan[_max_value];
for (int j = 0; j < n; j++)
{
for (int i = 0; i < _max_value; i++)
{
int[] key1 = key0.Concat(new int[] { i }).ToArray();
Stopwatch stop = new Stopwatch();
stop.Start();
for (int k = 0; k < n; k++)
{
if (check_secret_key(key1))
{
Console.WriteLine("Found:");
print_key(key1);
return;
}
}
stop.Stop();
times[i] = times[i] + stop.Elapsed;
}
}
int index_max = times
.Select((value, index) => new { Value = value, Index = index })
.Aggregate((a, b) => (a.Value > b.Value) ? a : b)
.Index;
key0.Add(index_max);
print_key(key0.ToArray());
}
}
static void Main(string[] args)
{
while (true)
{
generate_secret_key();
print_key(_secret_key);
crack_key();
}
}
}
}