Атаки за часом - казка чи реальна загроза?

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


Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.