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

Первую статью на хабр хотел написать совершенно о другом, но в один прекрасный день коллега по работе решил заморочиться и сделать защиту от «Атаки по времени» (Timing attack). Не долго разбираясь в различных материалах на эту тему, Я загорелся и решил написать свой велосипед и покататься на нем по лаборатории поэкспериментировать.

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

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

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

        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) Атака по времени ^[1]
2) Атака по сторонним каналам ^[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();
            }
        }
    }
}

Автор: alex_kir

Источник ^[3]