Cryptopals zestaw 1 ćwiczenie 6

przez | 6 kwietnia 2020

Pierwsze większe wyzwanie i z tego co piszą autorzy pomyśle jego rozwiązanie oznacza, że powinniśmy sobie poradzić z wszystkimi ćwiczeniami aż do zestawu 6. Warto się spiąć i rozwiązać je samodzielnie, dlatego zanim przejdę do opisania mojego rozwiązania omówię to na co warto szczególnie zwrócić uwagę.

Pierwsze co moim zdaniem należy zrobić to funkcja o której jest mowa w punkcie 2., czyli obliczającą odległość Hamminga (https://pl.wikipedia.org/wiki/Odleg%C5%82o%C5%9B%C4%87_Hamminga) pomiędzy dwoma ciągami bajtów. Nie ma sensu zabierać się za dalszą część zadania, jeżeli wyliczona przez nasza funkcję odległość nie wynosi tyle ile podali autorzy dla przykładowych wartości wejściowych.

Druga sprawa to sugerowany zakres długości klucza, kiedy rozwiązywałem to zadanie skupiłem się na punkcie 2. i zapomniałem o tym, że autorzy zalecają sprawdzić klucze o długościach od 2 do 40.

Funkcja obliczająca odległość Hamminga potrzebna jest nam do wyznaczania długości klucza użytego do zakodowania tekstu. Zanim opiszę swoją implementację tej funkcji polecam bardzo ciekawy film z instrukcją jak można wyznaczyć długość klucza w sposób graficzny: https://youtu.be/fBEe8DGZL5o?t=1281 (Polecam zapoznać się z innymi filmami autora).

def getHammingDistance(input1, input2):
    distance = abs(len(input1) - len(input2))*8
    for idx in range(0, min([len(input1), len(input2)])):
        xorval = input1[idx]^input2[idx]
        while xorval > 0:
            if xorval & 0x1:
                distance += 1
            xorval = xorval >> 1
    return distance

Funkcja zwraca wartość zmiennej distance, zmienna ta na początku jest inicjalizowana wartością 0 jeżeli dwa ciągi śą tej samej długości, w przeciwnym wypadku ma wartość równą różnicy ich długości pomnożoną przez 8 (Jeden bajt to 8 bitów różnicy). Następnie wykonuje się pętla for tyle razy ile bajtów ma krótszy z podanych ciągów. W każdej iteracji obliczana jest wartość operacji XOR na bajtach pod tym samym indeksem w obydwu danych wejściowych i zapisywan do zmiennej xorval. W ostatnim kroku wykonuje się pętla while, która sprawdza najmłodszy bit zmiennej xorval i jeżeli jest on róży od 0 to zmienna distance jest zwiększana o 1, wartość xorval jest przesuwana bitowo w prawo o 1 bit (albo jak kto woli dzielona przez 2). Kiedy wartość zmiennej xorval spadnie do 0, wykonuje się kolejny krok pętli for.

Mamy już funkcję obliczającą dystans Hamminga, teraz czas zrobić z nią coś użytecznego. Wiemy, że długość klucza mieści się w przedziale [2:40]. Po raz kolejny posłużymy się statystyką, policzymy jaka jest średnia odległość Hamminga dla różnych długości klucza a następnie wybierzemy długość, dla której ta wartość jest najmniejsza.

def getKeySize(input_data):
    results = {}
    max_chunk_size = 41
    if max_chunk_size > (len(input_data)/2):
        max_chunk_size = (len(input_data)/2)
    for i in range(2, max_chunk_size):
        results[i] = 0
        chunks = [input_data[x:x+i] for x in range(0, len(input_data), i)]
        for j in range(1, len(chunks)-2):
            results[i] += getHammingDistance(chunks[j-1], chunks[j])
        results[i] /= i*(len(chunks)-2)
    print(results)
    key_length = min(results, key=results.get)
    return key_length

Funkcja jako parametr wejściowy przyjmuje zakodowany tekst dla którego chcemy znaleźć długość użytego klucza. W pętli for, która wykonuje się dla wszystkich możliwych długości klucza, wejściowe dane rozbijane są na mniejsze bloki o długości równej sprawdzanej długości klucza. Obliczana jest suma odległości Hamminga pomiędzy kolejnymi blokami a następnie normalizowana względem długości klucza. Normalizacja polega na podzieleniu uzyskanego wyniku przez długość klucza, gdybyśmy tego nie zrobili najkrótsze klucze miały by najlepsze wyniki ponieważ np. klucz o długości 2 bajtów nie może mieć wyniku gorszego niż 16, dla 3 bajtów to już 24, dla 4 – 32 i tak dalej. W ostatnim kroku zwracana jest długość klucza z najmniejszym wynikiem. PS. W ramach optymalizacji, można by pomijać te długości klucza, których wielokrotnością nie jest długość całego tekstu.

Ostatni krok w tym zadaniu to wykorzystanie kodu z poprzednich zadań i wiedzy na temat długości klucza. Teraz jak już wiemy jaką długość ma klucz, moglibyśmy sprawdzać wszystkie możliwe kombinacje bajtów, ale dla dłuższych kluczy staje się to bardzo czasochłonne. W zadaniu numer 3 odgadywaliśmy wartość baju którym był zaszyfrowany dany ciąg znaków, teraz problemem jest to, że klucz jest dłuższy. Możemy jednak zrobić coś co sprawi, że będziemy mieli kilka bloków zaszyfrowanych kluczem jedno bajtowym. Przykładowo, mamy 4 bloki:
[a, b, c, d]
[e, f, g, h]
[i, j, k, l]
[m, n, o, p]
I klucz:
[x1, x2, x3, x4]
Wiemy, że wszystkie były zaszyfrowane tym samym kluczem, a więc pierwszy bajt każdego z czterech bloków był zaszyfrowany był pierwszym bajtem klucza x1, każdy drugi bajt był szyfrowany x2 itd. Jeżeli zgrupujemy bajty szyfrowane tym samym bajtem klucza dostaniemy:
[a, e, i, m]. [b, f, j, n], [c, g, k, o] oraz [d, h, l, p]. Teraz mamy cztery ciągi znaków, każdy zaszyfrowany tak jak w zadaniu numer 3. Teraz możemy wykorzystać kod, który już napisaliśmy i powtórzyć tyle razy z ilu bajtów składa się klucz użyty w tym zadaniu.

def getKeyValue(input_data):
    key_size = getKeySize(input_data)
    print("Key length: ", key_size, " Data length: ", len(input_data))
    chunks = [input_data[x:x+key_size] for x in range(0, len(input_data), key_size)]
    tmpRows = {}
    for chunk in chunks:
        for i in range(0, len(chunk)):
            if i in tmpRows:
                tmpRows[i].append(chunk[i])
            else:
                tmpRows[i] = [chunk[i]]
    tmpKey = []
    for row in tmpRows:
        tmpKey.append(find_best_key_bytes(bytes(tmpRows[row])))
    return bytes(tmpKey)

No i wszystko złożone w całość:

def s1challenge6():
    with open('testfiles/6.txt') as f:
        file_string_b64 = f.read().replace('\n', '')
        print(file_string_b64);
        file_data = bytes_from_base64(file_string_b64)
        print(file_data)
        secret_key = getKeyValue(file_data)
        print("Secret key: ", secret_key)
        print("Secret message: ")
        print(''.join([chr(x) for x in bytes_xor_key(file_data, secret_key)]))

Tak jak napisali autorzy zadania, samo w sobie nie jest ono trudne, natomiast składa się z wielu małych kroków a w związku z tym jest wiele miejsc gdzie można popełnić błąd.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *