Image

Imagesharpc

Listens: Lana Lane — [Red Planet Boulevard #03] Capture The Sun

Categories:

KCC3 :: Эдиториал, задача 1

Дежавю в Гидронете
Условия: http://esci.ru/kcc3/kcc3_t.php

Эдиториал был написан через долгое время после составления задачи, без подглядывания в шпаргалку, поэтому можно считать, что задача была решена без подсказок.


Вход:
4D 53 00 81 DD 46 00 00 00 00 00 00 1E E7 80 00 A0 00 00 00 00 00 00 04 91 08 A1 00 FF FF 00 00 00 00 00 00 1E E7 20 00 A0 00 00 00 00 00 00 00 1E E7 60 00 A0 00 00 00 00 00 00 00 1E E7 A0 00 FF FF

Выход:
[04/09/2007 15:45:00] Attacked 13.
[04/09/2007 15:59:59] Attacked 5, damaged 1, 3, 4.

Этот пакет означает, что 15 минут назад злобные хакеры уронили сервер №13, а всего секунду назад — №5. Причем второй унес в могилу сервера №1, №3 и №4.

Вход:
4D 53 D0 F1 D8 46 00 00 00 00 00 04 95 08 A0 00 00 00 00 00 00 00 00 04 95 08 20 00 60 00 00 00 00 00 00 04 95 08 00 00 FF FF 00 00 00 00 00 04 95 08 C0 00 00 00 00 00 00 00 00 04 95 08 60 00 FF FF 00 00 00 00 00 04 95 08 40 00 60 00

Выход:
[01/09/2007 04:00:00] Attacked 0, damaged 5, 6.
[01/09/2007 04:00:00] Attacked 3, damaged 1, 2.

А здесь атаковали сервер №0 и №3 одновременно, причем первый уронил №5 и №6, а второй №1 и №2. И сделано это было 1 сентября 2007 года ровно в 4 утра.


Первым делом отметим знакомую еще с KCC2 сигнатуру Macrosoft — MS (4D 53).

В первом пакете сразу бросаются в глаза повторяющиеся 4 раза двухбайтовые последовательности 1E E7, а во втором попытка найти подобным образом повторяющиеся фрагменты приводит к обнаружению 04 95, повторяющиеся 6 раз.

Логично предположить, что в пакете должны как-то незримо присутствовать время и номера хостов. Судя по пакетам, время представлено в бинарном формате, а не текстовом. Одним из наиболее популярных машинных форматов представления времени является unix timestamp. Поищем что-нибудь похожее на него: 4 высокоэнтропийных байта, первый (big endian) или последний (little endian) из которых равен 4x. Кандидатов немного: packet + 0x02 в обоих, равный 00 81 DD 46 в первом и D0 F1 D8 46 во втором. Они соответствуют little endian датам 4 сентября 2007 16:00:00 (UTC) и 1 сентября 2007 05:00:00 (UTC), что по сюжету соответствует текущему моменту времени.

Поскольку в пакете больше ничего, напоминающего таймстамп, нету, можно поискать смещение относительно текущего времени для события атаки на хост №13 в первом пакете — 15 минут (900 секунд, 84 03). Хм, безуспешно.

Размер первого пакета 0x42 (66), а второго 0x4D (78), разность 12 байт. В первом упомянуто 5 хостов, а во втором 6. Если вычесть из размера пакета 2 байта заголовка + 4 байта таймстампа, как раз получится 5 12-байтных последовательностей в первом пакете и 6 во втором. Разобьем пакет на части и будем их разглядывать.

4D 53
00 81 DD 46
00 00 00 00 00 00 1E E7 80 00 A0 00
00 00 00 00 00 04 91 08 A1 00 FF FF
00 00 00 00 00 00 1E E7 20 00 A0 00
00 00 00 00 00 00 1E E7 60 00 A0 00
00 00 00 00 00 00 1E E7 A0 00 FF FF


4D 53
D0 F1 D8 46
00 00 00 00 00 04 95 08 A0 00 00 00
00 00 00 00 00 04 95 08 20 00 60 00
00 00 00 00 00 04 95 08 00 00 FF FF
00 00 00 00 00 04 95 08 C0 00 00 00
00 00 00 00 00 04 95 08 60 00 FF FF
00 00 00 00 00 04 95 08 40 00 60 00


Сразу в глаза бросается, что первые 5 байт «подпакета» нулевые, 6-й байт либо 00, либо 04, последние два байта либо FF FF (количество таких совпадает с числом изначально атакованных хостов) либо A0 00 в первом и 60 00 или 00 00 во втором.

Посмотрим на второй пакет. Если где-то здесь и зашиты номера хостов, то только в разных 9-х байтах подпакета (отметим, что для представления номера любого хоста потребуется 2 байта). Они равны A0, 20, 00, C0, 60, 40, все разные, и все «несложные», как и номера хостов от 0 до 6, исключая 4.

Предположим, что FF как-то связано с тем, что хост был атакован извне, тогда это 00 и 60, что должно соответствовать хостам №0 и №3. Замечаем, что если сопоставить их по формуле n * 0x20, то среди этих байтов присутствуют все хосты. Вспоминаем, что нужно 2 байта и пробуем сопоставить:

Атакован 0: подпакет 3, +0x08 = 00 00, +0x10 = FF FF
Атакован 3: подпакет 5, +0x08 = 60 00, +0x10 = FF FF
0 повредил 5: подпакет 1, +0x08 = A0 00, +0x10 = 00 00
0 повредил 6: подпакет 4, +0x08 = C0 00, +0x10 = 00 00
3 повредил 1: подпакет 2, +0x08 = 20 00, +0x10 = 60 00
3 повредил 2: подпакет 6, +0x08 = 40 00, +0x10 = 60 00

Пока сходится, но посмотрим на первый пакет. 20 00, 60 00, 80 00, A0 00 сразу определяются как хосты 1, 3, 4, 5, но 13-й хост кодируется как A1 00. 260 = 0x104, зато вот 26 = 0x1A. Это приводит к мысли, что для получения двухбайтового кода хоста надо поменять порядок полубайтов в байтах.

Попробуем применить эту мысль к непонятным числам 00 00 1E E7, 00 04 91 08, 00 04 95 08:

00 00 1E E7 → 00 00 E1 7E
00 04 91 08 → 00 40 19 80
00 04 95 08 → 00 40 59 80


Хм, фигня какая-то получилась.

Отметим странное сходство 00 04 91 08, что должно соответствовать времени атаки на 13-й сервер в первом пакете (15 минут назад) и 00 04 95 08 во втором (только что), а так же удивительную непохожесть 00 00 1E E7 из первого пакета (секунду назад) на "только что". Что нам это дает? Да ничего, в общем-то, не дает.

Что-то здесь не так, подумает мозг и отключится. Если повезет, в отключенном состоянии он вспомнит, что на прошлом KCC надо было что-то делать с битами. Действительно, умножение на 0x20 номера хоста соответствует сдвигу на 5 бит и куда логичнее выглядит, чем невесть откуда взявшаяся константа. Впрочем, это не объясняет ненулевых младших битов. А объясняет их циклический сдвиг! Выпишем битовое представление подпакетов (отбросим нулевой dword слева) и произведем циклический сдвиг в каждом байте влево на 3 бита:

00 00 1E E7 80 00 A0 00 | 00000000 00000000 00011110 11100111 10000000 00000000 10100000 00000000
00 04 91 08 A1 00 FF FF | 00000000 00000100 10010001 00001000 10100001 00000000 11111111 11111111
00 00 1E E7 20 00 A0 00 | 00000000 00000000 00011110 11100111 00100000 00000000 10100000 00000000
00 00 1E E7 60 00 A0 00 | 00000000 00000000 00011110 11100111 01100000 00000000 10100000 00000000
00 00 1E E7 A0 00 FF FF | 00000000 00000000 00011110 11100111 10100000 00000000 11111111 11111111

00 04 95 08 A0 00 00 00 | 00000000 00000100 10010101 00001000 10100000 00000000 00000000 00000000
00 04 95 08 20 00 60 00 | 00000000 00000100 10010101 00001000 00100000 00000000 01100000 00000000
00 04 95 08 00 00 FF FF | 00000000 00000100 10010101 00001000 00000000 00000000 11111111 11111111
00 04 95 08 C0 00 00 00 | 00000000 00000100 10010101 00001000 11000000 00000000 00000000 00000000
00 04 95 08 60 00 FF FF | 00000000 00000100 10010101 00001000 01100000 00000000 11111111 11111111
00 04 95 08 40 00 60 00 | 00000000 00000100 10010101 00001000 01000000 00000000 01100000 00000000


после циклического сдвига

00 00 F0 3F 04 00 05 00
00 20 8C 40 0D 00 FF FF
00 00 F0 3F 01 00 05 00
00 00 F0 3F 03 00 05 00
00 00 F0 3F 05 00 FF FF


00 20 AC 40 05 00 00 00
00 20 AC 40 01 00 03 00
00 20 AC 40 00 00 FF FF
00 20 AC 40 06 00 00 00
00 20 AC 40 03 00 FF FF
00 20 AC 40 02 00 03 00


Номера хостов сразу стали на свои места:

5 → 4
извне → 13
5 → 1
5 → 3
извне → 5

0 → 5
3 → 1
извне → 0
0 → 6
извне → 3
3 → 2

А вот со временем по-прежнему непонятно. Вспомним, что кроме 4-байтового int есть еще 4-байтовый float. Хм, не похоже, что это чему-то соответствует. О! Мы же выкинули 4 нулевых байта. Может, это что-то 8-байтовое? Потрясающе! Double дает что-то, похожее на осмысленные цифры.

00 00 00 00 00 00 F0 3F 1.0
00 00 00 00 00 20 8C 40 900.0
00 00 00 00 00 20 AC 40 3600.0


Вот и все, можно писать код

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <cassert>
#include <algorithm>
#include <ctime>
#include <boost/format.hpp>

using namespace std;

int hex2dec(char c) { return c <= '9' ? c - '0' : c - 'A' + 10; }
unsigned char rol(unsigned char c, int shift) { return (c << shift) + (c >> (8 - shift)); }

void dfs(const map<int, vector<int> >& log, int c, vector<int>& damaged)
{
    if (log.find(c) != log.end()) {
        const vector<int>& l = log.find(c)->second;
        for (int i = 0, len = l.size(); i < len; ++i) {
            damaged.push_back(l[i]);
            dfs(log, l[i], damaged);
        }
    }
}

int main()
{
    assert(sizeof(double) == 8 && sizeof(int) == 4 && sizeof(short) == 2);

    // Ввод последовательности байтов
    string in, inb;
    getline(cin, in);
    int bytes = in.length() / 3 + (in.length() % 3 ? 1 : 0);
    inb.assign(bytes, 0);
    for (int i = 0; i < bytes; ++i) inb[i] = hex2dec(in[3*i]) * 16 + hex2dec(in[3*i+1]);

    map<int, map<int, vector<int> > > events;

    // Текущее время и количество подпакетов
    int curts = *((int *) &inb[2]);
    int packets = (bytes - 6) / 12;
    for (int p = 0; p < packets; ++p) {
        // ROL
        for (int byte = 0; byte < 12; ++byte) {
            int off = 6 + p * 12 + byte;
            inb[off] = rol(inb[off], 3);
        }
        // Разбор подпакета
        double time = *((double *) &inb[6 + p * 12]);
        int ts = curts - (int) time;
        short from = *((short *) &inb[6 + p * 12 + 10]), to = *((short *) &inb[6 + p * 12 + 8]);
        events[ts][from].push_back(to);
    }

    // Вывод
    for (map<int, map<int, vector<int> > >::iterator i_m = events.begin(), i_end = events.end(); i_m != i_end; ++i_m) {
        vector<int>& attacked = i_m->second[-1];
        sort(attacked.begin(), attacked.end());
        for (int i = 0, len = attacked.size(); i < len; ++i) {
            // Построение списка задетых компьютеров
            vector<int> damaged;
            dfs(i_m->second, attacked[i], damaged);
            sort(damaged.begin(), damaged.end());
            // Преобразование таймстампа
            tm tstm;
            time_t ts = i_m->first;
            gmtime_s(&tstm, &ts);
            // Вывод времени и атакованного компьютера
            cout << "[" <<
                (boost::format("%02d/%02d/%04d %02d:%02d:%02d") %
                    tstm.tm_mday % (tstm.tm_mon + 1) % (tstm.tm_year + 1900) %
                    tstm.tm_hour % tstm.tm_min % tstm.tm_sec).str()
                << "] Attacked " << attacked[i];
            // Вывод списка задетых компьютеров
            if (!damaged.empty()) {
                cout << ", damaged ";
                for (int j = 0, dlen = damaged.size(); j < dlen; ++j) {
                    if (j != 0) cout << ", ";
                    cout << damaged[j];
                }
            }
            cout << ".\r\n";
        }
    }
}

олимпиады

LJ Video