Cryptopals zestaw 3 ćwiczenie 24

No i kończymy tym ćwiczeniem kolejny, trzeci już zestaw ćwiczeń. Nadal pozostajemy przy MT19937. Tym razem na podstawie otrzymanej zaszyfrowanej wiadomości będziemy musieli odgadnąć jaka wartość była użyta do zainicjalizowania naszego generatora liczb pseudolosowych.

Najpierw musimy stworzyć sobie kolejną wyrocznię, tym razem która do „szyfrowania” używa kolejnych wartości z generatora liczb pseudolosowych i XORuje właściwą wiadomość z tymi liczbami. Czyli zachowuje się podobnie jak AES w trybie CTR. Dodatkowo wyrocznia udostępnia funkcję która podany przez nas ciągu znaków doda do nieznanego nam ciągu znaków o nieznanej długości a następnie całość „zaszyfruje” i zwróci nam wynik tej operacji. Wiemy też, że wartość użyta do zainicjalizowania generatora jest 16-bitowa czyli z zakresu od 0 do 65535.

W drugiej części zadania będziemy musieli wykrywać czy wygenerowany przez wyrocznię token jest ciągiem bajtów o wartościach wygenerowanych przez generator liczb pseudolosowych zainicjalizowany wartością aktualnego czasu wyrażoną w sekundach (https://docs.python.org/3/library/datetime.html). W tym wyrocznia losowo decyduje o tym czy token ma użyć aktualnego czasu czy innej wartości. Na potrzeby sprawdzenia czy nasz algorytm działa wyrocznia będzie zwracał nie tylko token, ale również informację czy użyto aktualnego czasu czy innej losowej wartości. Moja implementacja wyroczni poniżej:

class OracleMT19937(object):
    M_MTRNG = None
    M_PAYLOAD = None
    M_SEED = None

    def __init__(self):
        self.M_SEED = abs(randint(0, 0xffff))
        self.M_MTRNG = mtrng.MTRng(self.M_SEED)
        self.M_PAYLOAD = generateRandomDataSize(5, 16)

    def encrypt(self, data):
        if type(data) != type(b''):
            return None
        result = self.M_PAYLOAD + data
        result = bytearray([(x^self.M_MTRNG.extractNumber())&0xff for x in result])
        return result
    
    def getToken(self):
        use_current = (randint(0, 1) == 1)
        tmprng = None
        if (use_current):
            tmprng = mtrng.MTRng(int(datetime.now().timestamp()))
        else:
            tmprng = mtrng.MTRng(randint(0, 0xffff))
        result = bytearray([tmprng.extractNumber()&0xff for _ in range(0, 16)])
        return (use_current, result)

I to ostatnie zdanie jest chyba najlepszą wskazówką jak w łatwy sposób można rozwiązać to zadanie. Mamy tylko około 65 tysięcy możliwości do sprawdzenia, przy obecnej mocy obliczeniowej naszych komputerów nie potrzebujemy używać wyrafinowanych środków, żeby odgadnąć wartość „ziarna” (wartości użytej do inicjalizacji generatora liczb pseudolosowych). Wystarczy sprawdzać wszystkie możliwości od 0 do 65535 aż w końcu znajdziemy prawidłową wartość. O tym, że wartość jest prawidłowa będziemy wiedzieli, bo po XORowaniu zaszyfrowanej wiadomości z wartościami z generatora zainicjalizowanego prawidłowym ziarnem na końcu odkodowanego ciągu znaków będzie znajdowała się nasz wiadomość przekazana do wyroczni. Moje rozwiązanie tej części zadania wygląda następująco:

    oracle = OracleMT19937()
    payload = b'AAAAAAAAAAAAAAAAAA'
    enc_data = oracle.encrypt(b'AAAAAAAAAAAAAAAAAA')
    for i in range(0, 0x80000):
        tmprng = mtrng.MTRng(i)
        tmp = bytearray([(x^tmprng.extractNumber())&0xff for x in enc_data])
        if tmp[-len(payload):] == payload:
            print('Seed: ', i)
            break
    print('Original seed: ', oracle.M_SEED)

Druga część zadania to wykorzystanie tego mechanizmu do wykrycia czy token do resetowania hasła został wygenerowany przy użyciu generatora zainicjalizowanego aktualnym czasem. Możemy to sprawdzić, tak samo jak poprzednio, ale tym razem musimy sprawdzić wartości nie od 0 do 65535 tylko wziąć aktualny czas i zmniejszać tą wartość o jeden do pewnego arbitralnie wybranego przez nas momentu i sprawdzać czy uda nam się wygenerować taki sam token. Ja w swoim rozwiązaniu cofam się maksymalnie o 20. Na potrzeby tego zadania sprawdzam 100 przypadków. Moja implementacja poniżej:

    for idx in range(0, 100):
        sample = oracle.getToken()
        tmp_timestamp = int(datetime.now().timestamp())
        used_timestamp = False
        for seed in range(0, 20):
            tmprng = mtrng.MTRng(tmp_timestamp-seed)
            tmp = bytearray([tmprng.extractNumber()&0xff for _ in range(0, 16)])
            if tmp == sample[1]:
                used_timestamp = True
                break
        print(idx, '.\t: FromTimestamp: ',sample[0],
              '  \tGuess: ',used_timestamp, '   \tPayload: ', sample[1])

Tym razem rozwiązanie było zaskakująco mało finezyjne, klasyczna brutalna siła poprzez wykorzystanie dostępnej mocy obliczeniowej.

Kod dostępny na Gitlabie: https://gitlab.com/akoltys/cryptopals.