Первую статью на хабр хотел написать совершенно о другом, но в один прекрасный день коллега по работе решил заморочиться и сделать защиту от «Атаки по времени» (Timing attack). Не долго разбираясь в различных материалах на эту тему, Я загорелся и решил написать свой велосипед и покататься на нем по лаборатории поэкспериментировать.
Результат этого небольшого эксперимента под катом.
Суть атаки заключается в том что злоумышленник знает, или хотя бы догадывается, о алгоритме проверки подлинности и пробует подобрать ключ постепенно. Подставляя различные значения и замеряя время проверки, можно заметить, что для некоторых вариантов ключей время выполнения дольше (или быстрее) чем для других.
В начале хотел сделать клиент и сервер, чтоб по настоящему как в Интернете, но решил обойтись без сложностей, ведь хотелось проверить саму идею, на сколько она работает хотя бы в лабораторных условиях. Для проведения эксперимента в качестве подопытного будет использоваться функция проверки подлинности, в которой будем просто сравнивать два ключа поэлементно.
В этом случае, при совпадении первых элементов ключа операция выполняется дольше, так как переходит к проверке следующих элементов. Алгоритм подбора достаточно прост: перебираем первое число, вариант который выполняется дольше всего — оставляем, потом второе… и так далее.
Подробно рассмотреть алгоритм можно в конце статьи, а желающие могут даже поиграться.
При первых запусках получал практически случайный результат. Начал постепенно увеличивать количество тестов и уже на третьем запуске получил правильные последовательности. И как следствие, в лабораторных условиях способ работает и работает достаточно хорошо.
Какие улучшения можно сделать после некоторого наблюдения:
1) если перебор следующего числа выполняется за время сравнимое с предыдущим, то имеет смысл сделать шаг назад, скорее всего ошиблись;
2) выбирать следующее число не после фиксированного количества тестов, а как-то более интеллектуально, т.к. с увеличением количества правильных элементов время на проверку увеличивается и разница становится менее заметна.
На скриншоте хорошо заметен правильный результат.
Вот что получаем в консоли (в первой строке выводится секретный ключ):
Очень похоже на то, как подбирают пароли в фильмах, а я всегда думал что это игра на публику, а оказывается в этом есть зерно правды.
Возможно такой способ атаки уже не совсем актуален (в сети очень много узлов и каждый вносит свою случайную величину), и защититься от него вроде как не сложно, но возможно в каком-нибудь хитром, на первый взгляд, алгоритме хеширования это будет более ярко выражено и может быть использовано злоумышленником в своих целях.
Хотя может быть актуально для подбора серийных номеров для оффлайн программ.
Спасибо за внимание!
UPD: расчет времени на сколько метод эффективнее полного перебора в данном конкретном случае.
Ключ — массив чисел из n=10 элементов со значениями от 0 до 99 (m = 100) включительно.
Тогда:
для полного перебора количество проверок равно m^n = 100^10 = 10^20;
для реализованной атаки времени n * a * m * b, где a и b это эмпирические константы и равны 1500, получаем 10*1500*100*1500 = 2,25 * 10^9
Как можно видеть, в данном конкретном случае, результат отличается более чем на 10 порядков, что говорит о его эффективности по сравнению с полным перебором.
1) Атака по времени
2) Атака по сторонним каналам
Результат этого небольшого эксперимента под катом.
Суть атаки заключается в том что злоумышленник знает, или хотя бы догадывается, о алгоритме проверки подлинности и пробует подобрать ключ постепенно. Подставляя различные значения и замеряя время проверки, можно заметить, что для некоторых вариантов ключей время выполнения дольше (или быстрее) чем для других.
В начале хотел сделать клиент и сервер, чтоб по настоящему как в Интернете, но решил обойтись без сложностей, ведь хотелось проверить саму идею, на сколько она работает хотя бы в лабораторных условиях. Для проведения эксперимента в качестве подопытного будет использоваться функция проверки подлинности, в которой будем просто сравнивать два ключа поэлементно.
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;
}
В этом случае, при совпадении первых элементов ключа операция выполняется дольше, так как переходит к проверке следующих элементов. Алгоритм подбора достаточно прост: перебираем первое число, вариант который выполняется дольше всего — оставляем, потом второе… и так далее.
Подробно рассмотреть алгоритм можно в конце статьи, а желающие могут даже поиграться.
При первых запусках получал практически случайный результат. Начал постепенно увеличивать количество тестов и уже на третьем запуске получил правильные последовательности. И как следствие, в лабораторных условиях способ работает и работает достаточно хорошо.
Какие улучшения можно сделать после некоторого наблюдения:
1) если перебор следующего числа выполняется за время сравнимое с предыдущим, то имеет смысл сделать шаг назад, скорее всего ошиблись;
2) выбирать следующее число не после фиксированного количества тестов, а как-то более интеллектуально, т.к. с увеличением количества правильных элементов время на проверку увеличивается и разница становится менее заметна.
На скриншоте хорошо заметен правильный результат.
Вот что получаем в консоли (в первой строке выводится секретный ключ):
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
Очень похоже на то, как подбирают пароли в фильмах, а я всегда думал что это игра на публику, а оказывается в этом есть зерно правды.
В заключение
Возможно такой способ атаки уже не совсем актуален (в сети очень много узлов и каждый вносит свою случайную величину), и защититься от него вроде как не сложно, но возможно в каком-нибудь хитром, на первый взгляд, алгоритме хеширования это будет более ярко выражено и может быть использовано злоумышленником в своих целях.
Хотя может быть актуально для подбора серийных номеров для оффлайн программ.
Спасибо за внимание!
UPD: расчет времени на сколько метод эффективнее полного перебора в данном конкретном случае.
Ключ — массив чисел из n=10 элементов со значениями от 0 до 99 (m = 100) включительно.
Тогда:
для полного перебора количество проверок равно m^n = 100^10 = 10^20;
для реализованной атаки времени n * a * m * b, где a и b это эмпирические константы и равны 1500, получаем 10*1500*100*1500 = 2,25 * 10^9
Как можно видеть, в данном конкретном случае, результат отличается более чем на 10 порядков, что говорит о его эффективности по сравнению с полным перебором.
Ссылки на вики
1) Атака по времени
2) Атака по сторонним каналам
Полный листинг подопытного
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<int> key0 = new List<int>();
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();
}
}
}
}