Свою первую статью на Хабре я хотел написать совсем о другом, но в один прекрасный день коллега по работе решил запутаться и создать защиту от «Тайминговой атаки».
После недолгого изучения различных материалов по этой теме я загорелся и решил написать свой велосипед и кататься на нем по лаборатории, чтобы экспериментировать.
Результат этого небольшого эксперимента ниже.
Суть атаки заключается в том, что злоумышленник знает или, по крайней мере, догадывается об алгоритме аутентификации и пытается постепенно угадать ключ.
Подставляя разные значения и измеряя время проверки, вы заметите, что для некоторых ключевых опций время выполнения больше (или быстрее), чем для других.
В начале я хотел сделать клиент и сервер, чтобы действительно было как в интернете, но решил обойтись без сложностей, так как хотелось проверить саму идею, насколько хорошо она работает, хотя бы в лаборатории.
условия.
Для проведения эксперимента в качестве подопытного мы будем использовать функцию аутентификации, в которой мы будем просто сравнивать два ключа поэлементно.
В этом случае, если первые элементы ключа совпадают, операция занимает больше времени, так как переходит к проверке следующих элементов.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
Это очень похоже на то, как в кино подбирают пароли, и я всегда думал, что это игра для зрителей, но оказывается, в этом есть доля истины.
Окончательно
Возможно, этот метод атаки уже не совсем актуален (узлов в сети много и каждый вносит свое случайное значение), и защититься от него вроде бы не сложно, но, возможно, в каком-нибудь хитром, на первых порах, На первый взгляд, алгоритм хеширования при этом будет более выраженным и может быть использован злоумышленником в своих целях.Хотя может быть актуально для выбора серийных номеров для оффлайн программ.
Спасибо за внимание! УПД: расчет, насколько метод эффективнее перебора в данном конкретном случае.
Ключ представляет собой массив чисел из 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();
}
}
}
}
Теги: #C++ #безопасность #Алгоритмы #анализ сложности алгоритмов #криптоанализ #Криптография #информационная безопасность #Криптография #Алгоритмы
-
Где Купить Бубен В Киеве?
19 Oct, 24 -
Габриэль Гарсиа Маркес - 13 Фраз О Жизни
19 Oct, 24 -
Prflr, Или Как Работает Ваш Код В Продакшене
19 Oct, 24
