Misja Gynvaela 001

Gynvael rozpoczął nową świecką tradycję podrzucania prostych zadanek programistycznych na końcu swoich streamów. W tym poście opiszę jak doszedłem do rozwiązania i dlaczego zajęło mi to więcej czasu niż powinno.

Zadanie pierwsze polega na złamaniu części klucza na podstawie kilku wiadomości “zaszyfrowanych” xorem przy użyciu jednakowego klucza. Wiadomości to pojedyncze słowa w języku angielskim, a dane wejściowe wyglądają tak:

1f9111
1799
0790001226d8
0a9e1e5c3ada
1f
099e195e
0a97075a21dac1
0a9710
199e075131d3
1199
12961350

Uwaga, niżej są spoilery.

Przygotowanie danych

Uznałem, że do rozwiązania użyję C++. Aby to zrobić musiałem doprowadzić dane wejściowe do akceptowalnej postaci. Użyłem do tego prostego (i zapewne brzydkiego) skryptu w ruby:

data = <<X
1f9111
1799
0790001226d8
0a9e1e5c3ada
1f
099e195e
0a97075a21dac1
0a9710
199e075131d3
1199
12961350
X
 
puts data.lines.map(&:strip).map{|l|
    '"%s"' %
    l.chars.each_slice(2).map(&:join).map{|x| "\\x#{x}" }.join
}.join(", \n")

Na jego wyjściu otrzymałem tablicę gotową do wklejenia do programu w C++:

"\x1f\x91\x11", 
"\x17\x99", 
"\x07\x90\x00\x12\x26\xd8", 
"\x0a\x9e\x1e\x5c\x3a\xda", 
"\x1f", 
"\x09\x9e\x19\x5e", 
"\x0a\x97\x07\x5a\x21\xda\xc1", 
"\x0a\x97\x10", 
"\x19\x9e\x07\x51\x31\xd3", 
"\x11\x99", 
"\x12\x96\x13\x50"

Algorytm

Uznałem, że najszybszą metodą będzie iteracyjne ręczne sprawdzanie kolejnych znaków klucza. Znając pierwszą literę, liczba dwuliterowych poprawnych słów jest ograniczona. Ponadto, pierwsze dwie litery muszą być poprawnymi pierwszymi dwoma literami angielskich słów dla wszystkich pozostałych wyrazów (czyli np. xx odpada).

Jeśli zaś chodzi o pierwszy znak klucza, to sprawa wydawała się oczywista – w końcu jest tylko jedno jednoliterowe słowo: I, więc pierwszym znakiem klucza powinno być 1f16 ⊕ 4916, gdzie 1f16 to jedyny jednoznakowy string w danych, a 4916 to kod ASCII litery I.

Implementacja

Utworzyłem tablicę stringów wejściowych poprawiając jednocześnie trzeci string (ponieważ zawiera on zero tradycyjnie kończące C-stringa):

static const string foo[] = {
    "\x1f\x91\x11",
    "\x17\x99",
    string("\x07\x90\x00\x12\x26\xd8", 6),
    "\x0a\x9e\x1e\x5c\x3a\xda",
    "\x1f",
    "\x09\x9e\x19\x5e",
    "\x0a\x97\x07\x5a\x21\xda\xc1",
    "\x0a\x97\x10",
    "\x19\x9e\x07\x51\x31\xd3",
    "\x11\x99",
    "\x12\x96\x13\x50"
};

Napisałem prostą funkcję xorującą:

string decrypt(string const& s, string const& k)
{
    string ret(s.size(), '?');
    for(size_t i{}; i < s.size(); ++i) {
        auto c = s[i] ^ k[i % k.size()];
        if(isprint(c))
            ret[i] = c;
    }
    return ret;
}

Pożyczyłem ze Stacka funkcję do ładnego printowania hexów:

std::string string_to_hex(const std::string& input)
{
    static const char* const lut = "0123456789ABCDEF";
    size_t len = input.length();
 
    std::string output;
    output.reserve(2 * len);
    for (size_t i = 0; i < len; ++i)
    {
        const unsigned char c = input[i];
        output.push_back(lut[c >> 4]);
        output.push_back(lut[c & 15]);
    }
    return output;
}

Obliczyłem pierwszy znak klucza: 1f16 ⊕ 4916 = 5616. Ustawiłem go w kodzie:

const string key = "\x56" "*******************";

I przystąpiłem do rozwiązywania:

int main()
{
    for(auto const& s : foo) {
        cout << setw(20) << left << string_to_hex(s) << decrypt(s, key) << endl;
    }
}

Odpaliłem program i… Pojawił się drobny problem: część wyrazów zaczynała się od znaków \ i _. Wyjście przedstawiało się następująco:

1F9111              I?;
1799                A?
0790001226D8        Q?*8??
0A9E1E5C3ADA        \?4v??
1F                  I
099E195E            _?3t
0A97075A21DAC1      \?-p???
0A9710              \?:
199E075131D3        O?-{??
1199                G?
12961350            D?9z

Co poszło nie tak?

Po długich minutach szukania błędu w trywialnej implementacji poszedłem po rozum do głowy i zastanowiłem się, czy na pewno I jest jedynym angielskim jednoliterowym słowem. Spoiler: nie jest, przedimek a również jest kwalifikowany jako słowo.

Rozwiązanie

Po zmianie pierwszego znaku klucza na 1f16 ⊕ 6116 = 7e16, otrzymane wyniki były znacznie bardziej zachęcające:

1F9111              a?;
1799                i?
0790001226D8        y?*8??
0A9E1E5C3ADA        t?4v??
1F                  a
099E195E            w?3t
0A97075A21DAC1      t?-p???
0A9710              t?:
199E075131D3        g?-{??
1199                o?
12961350            l?9z

Uzyskanie kolejnego znaku było już bardzo proste. Oba dwuliterowe wyrazy miały tę samą drugą literę (9916 po xorowaniu z kluczem), więc mogły to być tylko pary in/on oraz if/of (ale już np. or odpada, bo ir nie jest słowem).

Podstawienie pod drugi znak 9916 ⊕ 6616 = ff16 (6616 to kod ASCII litery f) dało niepożądane rezultaty:

1F9111              af;
1799                in
0790001226D8        yg*8??
0A9E1E5C3ADA        ti4v??
1F                  a
099E195E            wi3t
0A97075A21DAC1      t`-p???
0A9710              t`:
199E075131D3        gi-{??
1199                on
12961350            la9z

Tak więc drogą dedukcji doszedłem do wartości drugiego znaku klucza. 9916 ⊕ 6e16 = f716 (6e16 to kod ASCII litery n):

1F9111              an;
1799                if
0790001226D8        yo*8??
0A9E1E5C3ADA        ta4v??
1F                  a
099E195E            wa3t
0A97075A21DAC1      th-p???
0A9710              th:
199E075131D3        ga-{??
1199                of
12961350            li9z

Wynik

Powtarzając powyższe kroki aż do wyczerpania znaków w wyrazach uzyskałem początek klucza o wartości: 7E FF 75 35 54 BD A9, a odczytane słowa układają się w cytat z piosenki Iron Maiden:

1F9111              and
1799                if
0790001226D8        you're
0A9E1E5C3ADA        taking
1F                  a
099E195E            walk
0A97075A21DAC1      through
0A9710              the
199E075131D3        garden
1199                of
12961350            life

Cały kod można znaleźć tutaj.

Leave a Reply

Your email address will not be published.