MISJA 004            goo.gl/                     DIFFICULTY: ███░░░░░░░ [3/10]
┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅┅
Jeden z naszych agentów infiltruje siedzibę wrogiego syndykatu, i utknął pod 
drzwiami z elektronicznym zamkiem. Udało mu się dostać do elektroniki i zrzucić
krótki program, który sprawdza wprowadzony kod i otwiera drzwi.

Twoim zadaniem będzie wykonanie analizy poniższego programiku oraz znalezienie
poprawnego kodu.

      #include <stdio.h>
      int check(char*b){char*p;for(p=b;*p;p++);if(((p-b)^42)!=47)return(
      ~0xffffffff);unsigned long long ch=0x1451723121264133ULL;for(p=b;*
      p;p++)ch=((ch<<9)|(ch>>55))^*p;return!!(14422328074577807877ULL==
      ch);}int main(void){char buf[1234];scanf("%1233s",buf);puts("nope"
      "\0good"+check(buf)*(6-1));return 0;}

--

Odzyskaną wiadomość umieśc w komentarzu pod tym video :)
Linki do kodu/wpisów na blogu/etc z opisem rozwiązania są również mile
widziane!

P.S. Rozwiązanie zadania przedstawie na początku kolejnego livestreama.

Kod, jak widać, jest trochę bardzo nieczytelny. Ok, to jest C, ale i tak powinno być lepiej. Dlatego pierwszym krokiem ku rozwiązaniu zadania było jego poprawne sformatowanie. Do tego użyłem http://format.krzaq.cc, mojego webowego frontendu dla clang-format.

Wynik od razu jest zachęcający:

#include <stdio.h>
int check(char* b)
{
    char* p;
    for (p = b; *p; p++)
        ;
    if (((p - b) ^ 42) != 47)
        return (
            ~0xffffffff);
    unsigned long long ch = 0x1451723121264133ULL;
    for (p = b; *p; p++)
        ch = ((ch << 9) | (ch >> 55)) ^ *p;
    return !!(14422328074577807877ULL == ch);
}
int main(void)
{
    char buf[1234];
    scanf("%1233s", buf);
    puts("nope"
         "\0good"
        + check(buf) * (6 - 1));
    return 0;
}

Funkcja main()

Analiza funkcji main nie jest trudna. Mamy bufor o wielkości 1234 znaków, wczytujemy do niego max 1233 + null terminator. Następnie wywołujemy funkcję puts z argumentem będącym wskaźnikiem na “nope” lub “good” w zależności od wyniku funkcji check. Interesującym dla nas wynikiem jest 1.

Funkcja check()

Tę funkcję można podzielić z grubsza na dwie części:

Do pierwszej instrukcji return

#include <stdio.h>
int check(char* b)
{
    char* p;
    for (p = b; *p; p++)
        ;
    if (((p - b) ^ 42) != 47)
        return (
            ~0xffffffff);
    // ...
}

Widoczne tutaj instrukcje przestawiają p na null terminator za stringiem, na który wskazuje b. Tak więc p-b to nic innego jak długość stringa. Idąc dalej, return ~0xFFFFFFFF to nic innego niż return 0, a co za tym idzie, powyższy kod można przedstawić konceptualnie w ten sposób:

if(string_length ⊕ 42 != 47)
    return 0;

Ponieważ 0 jest niepożądaną wartością, musimy znaleźć takie string_length, które spełnia równanie string_length ⊕ 42 == 47. Korzystając z tego, że elementem odwrotnym alternatywy rozłącznej (xora) jest ten sam element (czyli p ⊕ p = 0), a elementem neutralnym jest zero (czyli p ⊕ 0 = p), można obliczyć oczekiwaną długość stringa:
string_length ⊕ 42 ⊕ 42 = 47 ⊕ 42, czyli
string_length ⊕ 0 = 5, czyli
string_length = 5.

Pierwszy sukces odniesiony, znamy długość hasła – 5.

Pozostała część funkcji

int check(char* b)
{
    char* p;
    // ...
    unsigned long long ch = 0x1451723121264133ULL;
    for (p = b; *p; p++)
        ch = ((ch << 9) | (ch >> 55)) ^ *p;
    return !!(14422328074577807877ULL == ch);
}

Jest jakaś zmienna ch z magiczną wartością początkową. Dla każdego znaku wprowadzonego stringa (czyli pięć razy), poddawana jest ona rotacji w prawo o 9 bitów, a następnie xorowana z wartością numeryczną reprezentacji tego znaku. Jeśli wynik równy jest kolejnej magicznej wartości, zwracana jest wartość 1. W przeciwnym wypadku jest to 0.

Ponieważ wiemy już jak odwrócić xorowanie, a odwrócenie rotacji w prawo jest trywialne, możemy odwrócić proces sprawdzania i dla każdych najniższych 8 bitów (uzyskanych przy rotacji o 9 bitów) sprawdzić wymaganą wartość. Trzeba pierw obrócić wartość początkową s o 45 bitów w lewo, a następnie wykonać porównanie. Uwaga: wynik będzie w odwróconej kolejności!

using u64 = uint64_t;
using u8 = uint8_t;
 
template<typename T>
void rol9(T& x) {
    x = ((x << 9) | (x >> 55));
}
template<typename T>
void ror9(T& x) {
    x = ((x << 55) | (x >> 9));
}
 
int main(void)
{
    u64 r = 0xc82666f8975a8a05;
    u64 s = 0x1451723121264133;
 
    for(int i = 0; i < 5; ++i) {
        rol9(s);
    }
 
    for(int i = 0; i < 5; ++i) {
        auto res = r ^ s;
        u8 x = res;
        DBG(x);
        ror9(r); ror9(s);
    }
}

x                                                           !
x                                                           W
x                                                           G
x                                                           W
x                                                           G

[link]

W końcu udało się uzyskać wynik: GWGW!. Po sprawdzeniu otrzymujemy komunikat, że faktycznie jest on poprawny:

> ./p
GWGW!
good

Bonus

Polecam sprawdzenie rozwiązania disconnect3da, które może okazać się dużo ciekawsze. Writep-up tutaj tutaj.