Атаки по времени — сказка или реальная угроза?

Результат этого небольшого эксперимента под катом.

Суть атаки заключается в том что злоумышленник знает, или хотя бы догадывается, о алгоритме проверки подлинности и пробует подобрать ключ постепенно. Подставляя различные значения и замеряя время проверки, можно заметить, что для некоторых вариантов ключей время выполнения дольше (или быстрее) чем для других.

В начале хотел сделать клиент и сервер, чтоб по настоящему как в Интернете, но решил обойтись без сложностей, ведь хотелось проверить саму идею, на сколько она работает хотя бы в лабораторных условиях. Для проведения эксперимента в качестве подопытного будет использоваться функция проверки подлинности, в которой будем просто сравнивать два ключа поэлементно.

        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 

Очень похоже на то, как подбирают пароли в фильмах, а я всегда думал что это игра на публику, а оказывается в этом есть зерно правды.

В заключение

Возможно такой способ атаки уже не совсем актуален (в сети очень много узлов и каждый вносит свою случайную величину), и защититься от него вроде как не сложно, но возможно в каком-нибудь хитром, на первый взгляд, алгоритме хеширования это будет более ярко выражено и может быть использовано злоумышленником в своих целях.
Хотя может быть актуально для подбора серийных номеров для оффлайн программ.

Спасибо за внимание!

Ссылки на вики

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();             }         }     } }