Dlaczego nie jest to skuteczny algorytm wymiany kluczy? [duplikować]

Nov 21 2020

Zastanawiałem się tylko, dlaczego tego rodzaju algorytm nie może być używany zamiast, powiedzmy, Diffiego-Hellmana do wymiany kluczy:

  1. Alicja decyduje się na klucz, którym chce się podzielić z Bobem.
  2. Alicja generuje strumień bajtów o tej samej długości co klucz (powiedzmy bezpiecznie za pomocą CSPRNG).
  3. Alicja wysyła do Boba:
    C1 = (key ^ alice_random_bytes)
    
  4. Bob generuje strumień losowych bajtów w sposób podobny do Alice.
  5. Bob wraca do Alicji:
    C2 = (C1 ^ bob_random_bytes)
    
  6. Alice XOR C2ponownie wykonuje swoją losową sekwencję bajtów, pozostawiając tylko w ten key ^ bob_random_bytessposób i wysyła to do Boba:
    C3 = (C2 ^ alice_random_bytes)
       = (C1 ^ bob_random_bytes ^ alice_random_bytes)
       = (key ^ alice_random_bytes ^ bob_random_bytes ^ alice_random_bytes)
       = (key ^ bob_random_bytes)
    
  7. Bob XORs C3ze swoimi losowymi bajtami i uzyskuje klucz:
    K = (C3 ^ bob_random_bytes)
      = (key ^ bob_random_bytes ^ bob_random_bytes) 
      = key
    

Wydaje się to o wiele prostsze niż Diffie Hellman, więc zastanawiałem się: na czym polega problem z takim algorytmem?

Odpowiedzi

34 kelalaka Nov 21 2020 at 18:38

Uprościłem losowe bajty Alice do losowych bajtów ARB i Boba do BRB. Następnie protokół jest następujący;

Alice wie $key$ i $ARB$i wysyła $$C_1 = key \oplus ARB$$

Bob wie $C_1$ i $BRB$i wysyła

$$C_2 = C_1 \oplus BRB = key \oplus ARB \oplus BRB$$

Alice oblicza $C_2 \oplus key \oplus ARB = key \oplus key \oplus ARB \oplus BRB = BRB$

Alice wie $key, ARB,$ i $BRB$i wysyła

$$C_3 = (C_2 \oplus ARB) = key \oplus ARB \oplus BRB \oplus ARB = key \oplus BRB$$

Przede wszystkim wymaga to protokołu trójprzebiegowego.

Teraz obserwator widzi

\begin{align} C_1 & = key \oplus ARB \oplus {}\\ C_2 & = key \oplus ARB \oplus BRB\\ C_3 & = key \oplus \phantom{ARB}\oplus BRB \\ \end{align}

Bierny obserwator (podsłuchiwacz) po prostu poddaje wszystko, aby uzyskać klucz $$key = C_1 \oplus C_2 \oplus C_3.$$Dlatego jest niepewny wobec słabego założenia o napastniku; bierny!.

Więc polegasz na xor, jednak nie sprawdziłeś, co obserwator może uzyskać i obliczyć z nich.

Z drugiej strony dochodzi do przecieków wymiany kluczy Diffiego – Hellmana (DHKE)$g^a$ i $g^b$ gdzie Alicja wybiera losową liczbę całkowitą $a$i wysyła $g^a$ a Bob wybiera losową liczbę całkowitą $b$i wysyła $g^b$. Odkrycie$a$ lub $b$z nich wynika problem z logarytmem dyskretnym . Z drugiej strony założenie Computational Diffie – Hellman (CDH) ma znaleźć$g^{ab}$ dany $g^a$ i $g^b$, a DHKE jest na tym przekazywana. Jeśli logarytm dyskretny jest łatwy, to CDH jest łatwe. W ogólnym przypadku nie znamy odwrotnej sytuacji.

1 JasonGoemaat Nov 23 2020 at 21:10

Algorytmy wymiany kluczy starają się chronić przed podsłuchem. Musisz założyć, że to, co wysyłasz przez przewód (C1, C2 i C3), zostanie przechwycone. To jest problem z tą metodą, ponieważ C2 to po prostu losowe bajty C1 xor Boba, a C3 to po prostu klucz xor losowe bajty Boba.

Atakujący z C1, C2 i C3 może wziąć C1 x lub C2, aby uzyskać losowe bajty Boba, a następnie xorować je za pomocą C3, aby uzyskać klucz, tak jak zrobiłby to Bob.