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

в 7:26, , рубрики: Алгоритмы, безопасность, информационная безопасность, криптоанализ, криптография, метки: , , , ,

Первую статью на хабр хотел написать совершенно о другом, но в один прекрасный день коллега по работе решил заморочиться и сделать защиту от «Атаки по времени» (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) Атака по времени
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

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js