Занимательная криптоматика
Недели две назад, на выездном заседании нашей глобальной аналитической
группы, нормальный процесс пищеварения в мюнхенских пивных, был нарушен
одной задачкой, которую мой мозг вывалил на собравшихся, предложив
буквально по-быстрому посчитать на салфетках следующее:
Если
Conficker.C генерирует 50 000 доменов, а коннектится пытается только к
500 из них, то сколько доменов надо зарегистрировать авторам Кидо,
чтобы отдать команды хотя бы 1% ботнета ?
Мозг взорвался.
Немцы, румыны, русские и англичане, вспоминали основы высшей
математики, вычисляли логарифмы и извлекали корни. Бесполезно.
Результаты варьировались от 42, минуя 1700 и доходя до двух в
тринадцатой.
Мозговой вирус выполз за пределы ЛК и пошел гулять по умам других исследователей. В понедельник он поразил Микрософт.
Под катом перевод их вычислений.
Birthday Problem and Conficker
"Проблема
дня рождения" или парадокс вероятности, заключается в том, что в
определенной группе людей двое имеют день рождения в один и тот же
день. Парадокс состоит в том, что результат бросает вызов здравому
смыслу. Для группы из 23 человек, вероятность того что у двух из них
совпадут дни — составляет более чем 50%, а для группы из 57 человек —
более чем 99%.
Самое известное использование этого парадокса,
возможно существует в криптографии и известно как "Birthday Attack".
Эта атака использует математическую уязвимость описанную в парадоксе и
позволяет искать коллизии в маленьких группах данных, с гораздо большей
вероятностью, чем ожидалось.
Недавно я столкнулся с другим
использованием этого же парадокса — в случае с печально известным
Conficker. Тут использование статистического парадокса отличается — с
целью сделать борьбу против червя более тяжелой.
Суть проблемы:
каждый день они обладают пулом в 50 000 URLs, из которых каждый
инфицированный компьютер выбирает 500. Общее число возможных выборок —
гигантское. Это число имеет 1,215 цифр в десятичном представлении и его
даже трудно привести здесь полностью.
Регистрация всех этих
доменов является невероятно трудной задачей и здесь лежит сила
упомянутого статистического парадокса. Проблема заключается в том, что
надо найти вероятность того, что в случайной группе из 500 доменов,
найдется хотя бы один из более маленького набора.
Тут идут примерно такие непереводимые формулы:
As
we see, the second element is a product of sub-unitary numbers, which
decreases towards 0 as we increase the number of elements (m). As a
matter of fact, each element in the product is smaller than the first
element (n–k)/n (trivial to prove under the assumption 1=j=m=n-k)
resulting in the following approximation,
that is closing to 0 faster than an exponential. This means that our probability can be approximated with the following formula
В
общем, результат наших вычислений довольно удивителен. Если
зарегистрировать 50 доменов, то шанс составит 39,514%, а если
зарегистрировать 500, он составит 99,359%.
Таким образом, имея только 1% из общего пула (50 000) возможных доменных имен, вы имеете доступ к 99% ботнета Кидо.
По
горизонтальной оси указано количество доменов, а по вертикальной —
шансы на то, что компьютер инфицированный Kido, попробует получить
доступ к одному из доменов в данной выборке.
Это показывает
важность блокирования возможных доменов, как можно большего числа из
всех возможных 50000 каждый день. Один пропущенный URL уже дает
вероятность в 1%.
Выборочная блокировка некоторых URL имеет
ограниченные преимущества, из-за того что общий пул крайне велик, а
число URL необходимых для использования 100% ботнета — относительно
мало (отличается минимум на два порядка).
"Хорошие парни" могут
использовать знание этого парадокса "Дня Рождения" в своих целях — он
может дать средства для оценки реальных размеров эпидемии Кидо в мире.
Регистрируя ограниченное число доменов можно наблюдать за входящими
запросами и зная шанс на коннект именно с этим URL, можно
экстраполировать эти данные в общее число зараженных машин.
Продолжение статьи с математическими формулами и таблицей вероятностей — по ссылке.
P.S. Все равно, 500-600 доменов в день — это дофига. Основные дела будут делаться через P2P.
|
| Категория: Общие Статьи | Добавил: aka_kludge (30.04.2009)
|
| Просмотров: 2922
| Рейтинг: 0.0/0 |
Добавлять комментарии могут только зарегистрированные пользователи. [ Регистрация | Вход ] |
