Złożoność ataku meet in the middle

Witam,
Zastanawiam się w jaki sposób można osiągnąć naraz pesymistyczną złożność obliczeniową 2*2^56 i pesymistyczną złożność pamięciową 2^56 w przypadku ataku meet in the middle na dane zaszyfrowane dwukrotnie algorytmem DES. Dla przykładu załóżmy, że dysponuję dwoma parami tekstów jawnych i zaszyfrowanych, które mają te same klucze (dane są podane jako liczby heksadecymalne, klucze mają ustawione bity parzystości).

Tekst jawny 1:
1111111111111111

Tekst jawny 2:
2222222222222222

Tekst zaszyfrowany 1:
54C99F28781CED9F

Tekst zaszyfrowany 2:
F0E0C4236687BE79

Klucze do odgadnięcia:
ABABABABABABABAB
CDCDCDCDCDCDCDCD

Z tego co zrozumiałem czytając ten artykuł na wikipedii: https://pl.wikipedia.org/wiki/Meet_in_the_middle to należy najpierw przygotować tablicę, w której zaszyfruję tekst jawny 1111111111111111 wszystkimi możliwymi kluczami DES. Jej początek powinien wyglądać tak:

Klucz | Tekst zaszyfrowany

• | -
  0101010101010101 | 89B07B35A1B3F47E
• | -
  0101010101010102 | A52E042B7956BDBB
• | -
  0101010101010104 | C6C93339DD7070DD
• | -
  0101010101010107 | 0150F71195A68027
• | -
  0101010101010108 | F734FB85C3B62799
• | -
  010101010101010B | 53E9B7DC7D06E348
• | -
  ... | ...
  Ilość wierszy wynosi 2^56.

Następnie próbuję odszyfrować tekst zaszyfrowany 54C99F28781CED9F po kolei każdym możliwym kluczem DES i wyszukać otrzymany (potencjalnie nieprawidłowy) tekst jawny w tablicy z poprzedniego kroku.

Próba #1: klucz 0101010101010101 daje 84CF6B79C6683406, wyszukuję go w tablicy z poprzedniego kroku, jeżeli znalazłem ten tekst to sprawdzam poprawność 2 kluczy szyfrując drugi tekst jawny (powinno się niepowieść albo na etapie wyszukiwania, albo na etapie szyfrowania drugiego tekstu jawnego)
Próba #2: klucz 0101010101010102 daje 3295F05FC26482B6, wyszukuję go w tablicy z poprzedniego kroku, jeżeli znalazłem ten tekst to sprawdzam poprawność 2 kluczy szyfrując drugi tekst jawny (powinno się niepowieść albo na etapie wyszukiwania, albo na etapie szyfrowania drugiego tekstu jawnego)
Próba #3: klucz 0101010101010104 daje D90DAB5658129502, wyszukuję go w tablicy z poprzedniego kroku, jeżeli znalazłem ten tekst to sprawdzam poprawność 2 kluczy szyfrując drugi tekst jawny (powinno się niepowieść albo na etapie wyszukiwania, albo na etapie szyfrowania drugiego tekstu jawnego)
Próba #4: klucz 0101010101010107 daje FB06F0BE85BD8A6D, wyszukuję go w tablicy z poprzedniego kroku, jeżeli znalazłem ten tekst to sprawdzam poprawność 2 kluczy szyfrując drugi tekst jawny (powinno się niepowieść albo na etapie wyszukiwania, albo na etapie szyfrowania drugiego tekstu jawnego)
Próba #5: klucz 0101010101010108 daje 585BFE568AA4A87F, wyszukuję go w tablicy z poprzedniego kroku, jeżeli znalazłem ten tekst to sprawdzam poprawność 2 kluczy szyfrując drugi tekst jawny (powinno się niepowieść albo na etapie wyszukiwania, albo na etapie szyfrowania drugiego tekstu jawnego)
Próba #6: klucz 010101010101010B daje 244140483E4437FB, wyszukuję go w tablicy z poprzedniego kroku, jeżeli znalazłem ten tekst to sprawdzam poprawność 2 kluczy szyfrując drugi tekst jawny (powinno się niepowieść albo na etapie wyszukiwania, albo na etapie szyfrowania drugiego tekstu jawnego)
...
Próba #57873028282430311: klucz CDCDCDCDCDCDCDCD daje A202EE26F8A71460, wyszukuję go w tablicy z poprzedniego kroku, jeżeli znalazłem ten tekst to sprawdzam poprawność 2 kluczy szyfrując drugi tekst jawny (powinno się udać zarówno na etapie wyszukiwania, jak i na etapie szyfrowania drugiego tekstu jawnego)

I teraz zasadnicze pytanie: żeby szybko wyszukać tekst w tablicy, to mogę ją najpierw posortować i potem użyć wyszukiwania binarnego, ale wtedy złożoność obliczeniowa dla długości klucza n bitów wyniesie 2^nlog(2^n)=n2^n, złożoność pamięciowa wyniesie c2^56, gdzie c jest stałą wynoszącą 56+64=120 bitów, ale ta stała nie jest istotna. Dowiedziałem się, że można użyć tablicy z haszowaniem, żeby złożność czasowa wyniosła 22^56, ale czy wtedy złożność pamięciowa nadal będzie wynosić 2^56? Przez złożoność pamięciową mam na myśli, że dodatkowa ilość danych potrzebna do stworzenia tej struktury danych (względem prostej tablicy z kluczami i tekstami zaszyfrowanymi) jest stała i niezależna od długości klucza i może wynieść np. 1000000 bitów, ale jakbym użył innego algorytmu zamiast DES (np. IDEA o tej samej długości bloku, ale 128 bitowej długości klucza) to ta ilość nadal wynosiłaby 1000000 bitów. Jak można zrealizować taką tablicę z haszowaniem w pamięci?

ale czy wtedy złożność pamięciowa nadal będzie wynosić 2^56

Tak, bo hashmapa nie ma specjalnie wielkiego narzutu. W najbardziej trywialnej opcji to jest goła tablica.

Jak można zrealizować taką tablicę z haszowaniem w pamięci?

Najprościej? Jako tablicę! Trik hashmapy polega na tym, że indeks w tablicy jest wyliczany na podstawie funkcji hashujacej klucz. Tzn masz pewną funkcje h(x) która dla klucza zwraca indeks w tablicy są dane. Wtedy wyciagniecie danych z hashmapy to po prostu tablica[h(klucz)]. Oczywiście jest tu pewien problem, którym są konflikty, tzn trudno zrobić taką funkcje h która nie generuje nigdy konfliktów (dla dwóch kluczy zwróci to samo).

Jeśli szukasz implementacji łatwiejszej, to wygodniej zrobić tablicę list, tzn każdy element tablicy jest listą która przechowuje wszystkie wartości dla których funkcja h dała taki sam indeks.

Oczywiście praktycznie każdy język programowania ma wbudowane takie podstawowe struktury danych i nie trzeba ich pisać od zera.

Ok, to piszę to, co zrozumiałem. W przypadku ataku meet in the middle gdzie szukam K1 i K2 z tego równania: C = E(E(P, K1), K2) gdzie C to znany tekst zaszyfrowany, E to funkcja szyfrująca DES, P to znany tekst jawny, a K1 i K2 to szukane klucze; przekształcam to równanie do takiej postaci: D(C, K2) = E(P, K1) teraz D to funkcja deszyfrująca DES. Następnie w pętli po wszystkich możliwych 56-bitowych kluczach (oznaczanych jako k_ i czyli i-ty klucz) wstawiam do tablicy z haszowaniem następującą wartość (format: {klucz_tablicy => wartość}) {E(P, k_ i) => k_ i}. Później w następnej pętli po wszystkich możliwych 56-bitowych kluczach (oznaczanych jako k_ j czyli j-ty klucz) obliczam D(C, k_ j) i odczytuję wartość k_ i z tab[h(D(C, K_ j))] (tutaj mam 1. problem: D(C, K_ j) może nie być równe żadnemu z E(P, k_ i) z poprzedniego kroku, wtedy powinnienem przejść do następnego klucza i nie kontynuować tej iteracji); mając k_ j i k_ i sprawdzam dodatkowy blok teksu jawnego (P') i zaszyfrowanego (C'): C' = E(E(P, k_ i), k_ j), jeżeli to równanie jest prawidłowe to kończę całość i zwracam klucze K1 = k_ i i K2 = k_ j. I teraz 2. problem mam taki: w jaki sposób skonstruować funkcję h? I czy da to się zrobić w locie w czasie lepszym niż n * log(n) gdzie n = 2^56 przy zachowaniu złożoności pamięciowej n ? (Taką złożoność dla całego algorytmu mogę osiągnąć np. przez heapsort, wtedy złożoność obliczeniowa całego procesu łamania podwójnego DES to n*log(n) a pamięciowa to n; a według wikipedii mogę mieć naraz czasową n i pamięciową n)

1. Nie do końca rozumiem twoją notacje, więc napiszmy to zwyczajnie kodem:

def cpu_goes_brrrr(plaintext, ciphertext):
    mapa = {}
    for key in possible_keys():
        mapa[encrypt(plaintext,key)] = key

    for key in possible_keys():
        d = decrypt(ciphertext,key)
        if d in mapa:
            return key, mapa[d],

I voila, cały meet i the middle zrobiony. Czyli w mapie trzymasz sobie jako klucz wynik jednego deszyfrowania a jako wartość użyty klucz. Następnie w pętli dla wszystkich kluczy sprawdzasz czy zaszyfrowanie danych dało nam coś co mamy w mapie. Nie wiem co miałeś na myśli pisząc

wtedy powinnienem przejść do następnego klucza i nie kontynuować tej iteracji

w jaki sposób skonstruować funkcję h

Możesz po prostu zdać się na twórców języka w którym piszesz ;) Zwykle samo liczenie hasha jest zależne jedynie od rozmiaru wartości dla której tego hasha liczysz, a w twoim przypadku rozmiar bloku jest stały i bardzo mały. Trywialny przykład hasha ze stringa to np. potraktować bity tego stringa jako jednego długiego inta a potem zrobić modulo rozmiar tablicy i tyle. Czyli np. masz stringa AA czyli 0100000101000001 i jak potraktujesz to na pałe jako inta to masz 16705 i voila, mamy hasha.

Dzięki za odpowiedź.
To pytanie było tylko teoretyczne, bo jakiś czas temu zacząłem sobie czytać o kryptografii i ten typ ataku na podwójne szyfrowanie danych tym samym algorytmem mnie po prostu zainteresował. I tak do praktycznego zastosowania raczej przez wiele lat nie wystarczy mi pamięci w komputerze :)

I tak do praktycznego zastosowania raczej przez wiele lat nie wystarczy mi pamięci w komputerze

Hmm no to już zależy od konkretnego przypadku. Meet-in-the-middle to jest pewna klasa ataków, niekoniecznie musisz mieć jakieś podwójne szyfrowanie! Na dobrą sprawę szukanie kolizji przez birthday paradox to jest dokładnie ten sam mechanizm. Pepełniłem kiedyś takie zadanie na CTFa:

import random

from Crypto.Util.number import getStrongPrime


def main():
    secret_bits = 48
    challenges = [generate_challenge(secret_bits) for _ in range(10)]
    solvable = [(N, ct, M, is_solvable) for (N, ct, M, is_solvable) in challenges if is_solvable]
    assert len(solvable) > 0  # it's just a hint that it's a common property
    N, ct, M, is_solvable = solvable[0]
    print("N = " + str(int(N)))
    print("ct = " + str(int(ct)))
    # print("M = " + str(int(M))) # you wish!


def generate_challenge(secret_bits):
    N, e = generate_RSA_pubkey()
    M, is_solvable = generate_secret(secret_bits)
    ct = pow(M, e, N)
    return N, ct, M, is_solvable


def generate_RSA_pubkey():
    modulus_bitsize = 1024
    e = 65537
    p = getStrongPrime(modulus_bitsize // 2)
    q = getStrongPrime(modulus_bitsize // 2)
    N = p * q
    return N, e


def generate_secret(secret_bits):
    M = random.randint(2 ** (secret_bits - 1), 2 ** secret_bits - 1)
    import solver
    return M, solver.is_solvable(M, secret_bits)


main()

output:

N = 153925444825266405404296016820285889603681378402101336589329464961842012940371297301469649536111734999742714528709986215141965333810224830951469172716482545603364835583008550352222409796386064187919756548219280351127895602093980834522234748558225565031789941976740702306994823666953834995809100560973279991349
ct = 49258828688785826524053919049564557666797485380495142303571636718918855493745914425713948834302673401076375934795749020812927013205536426034127582877462948222553013533585166583151597238498630324268224723834865042941120996943852347638817146251845274398870427359031601825221080729264001112118956450061653065411

Mozesz spróbować się z nim zmierzyć ;) Oczywiście fakt ze już wiesz że chodzi o jakieś meet-in-the-middle ułatwia mocno sprawę...