Crypto-IT

• bez wcześniejszego uwierzytelnienia

Algorytm Puzzli Merkle'a umożliwia wynegocjowanie sekretnego klucza przez dowolne dwie osoby. Sekretny klucz będzie współdzielony przez obie zainteresowane strony i wykorzystany do ochrony dalszej komunikacji. Zakłada się, że obie osoby mogły wcześniej nie mieć ze sobą żadnego kontaktu i niczego między sobą nie ustalały.

Jest to jeden z pierwszych algorytmów szyfrowania za pomocą klucza publicznego. Został odkryty przez Ralph'a Merkle'a w roku 1974 i opublikowany cztery lata później.

Algorytm puzzli Merkle'a opisuje komunikację pomiędzy dwoma zainteresowanymi stronami, która umożliwia ustalenie wspólnego sekretnego klucza, w taki sposób, że nie jest możliwe jego podsłuchanie przez trzecią osobę. Klucz ten może być potem używany podczas dalszej komunikacji, chronionej przy użyciu szyfrowania symetrycznego.

Poniżej przedstawiono protokół wymiany informacji pomiędzy dwoma użytkownikami, nazwanymi zwyczajowo Alice i Bob. Aby wynegocjować wspólny sekretny klucz, należy wykonać poniższe kroki:

1. Pierwsza ze stron (Alice) przygotowuje dużą liczbę wiadomości, które składają się z unikalnego losowego identyfikatora wiadomości oraz unikalnego klucza.
2. Następnie Alice szyfruje każdą z tych wiadomości za pomocą słabego szyfru (na przykład szyfru symetrycznego z sekretnym kluczem o długości 20 bitów), a potem wysyła wszystkie zaszyfrowane wiadomości do drugiej ze stron (czyli do Boba).
3. Bob wybiera losowo jedną z otrzymanych zaszyfrowanych wiadomości i łamie jej zabezpieczenia za pomocą ataku siłowego.
4. Bob informuje Alice, jaką wartość ma identyfikator w wybranej przez niego wiadomości.
5. Obie strony dysponują teraz wspólnym kluczem, który znajdował się w wybranej przez Boba wiadomości. Będą go wykorzystywać podczas dalszej komunikacji.

Głównym założeniem algorytmu puzzli Merkle'a jest to, że początkowa duża liczba wiadomości szyfrowana jest za pomocą szyfru, na tyle prostego, że możliwego do złamania za pomocą ataku siłowego przez odbiorcę.

Sekretny unikalny klucz jest określany przez przesyłany tekstem otwartym identyfikator wiadomości. Ewentualny napastnik, który chce go odkryć i podsłuchuje całą komunikację, musiałby odszyfrować za pomocą ataków siłowych dużą część przesyłanych na początku algorytmu wiadomości. Liczyłby na to, że trafi na wiadomość losowo wybraną przez Boba i po jej odszyfrowaniu zdobędzie wiedzę o sekretnym kluczu. Wobec tego klucz, który szyfruje te wiadomości musi być na tyle długi, żeby odszyfrowanie dużej ich ilości było praktycznie niewykonalne.

Zakładając, że odszyfrowanie jednej wiadomości metodą ataku siłowego wymaga n kroków oraz, że wysłanych jest m wiadomości, wynegocjowanie sekretnego klucza zajmuje Alice i Bobowi w sumie O(n+m) czasu. Z drugiej strony, intruz próbujący podsłuchać komunikację pomiędzy nimi, w celu odkrycia wybranego klucza musi przeprowadzić ilość obliczeń o złożoności rzędu O(n*m).

Złożoność kwadratowa obliczeń dla napastnika nie jest obecnie uznawana za w zupełności wystarczającą w praktycznym zastosowaniu. Zbyt długi klucz (czyli zbyt duża wartość n) powoduje, że użytkowanie tego protokołu staje się uciążliwe dla komunikujących się stron. Obecnie, stosowane są bardziej wydajne i wygodne sposoby wykorzystujące ideę szyfrowania z kluczem publicznym i prywatnym.

Ze względu na brak początkowego uwierzytelnienia uczestników, protokół ten jest podatny na ataki typu man-in-the-middle. Napastnik może rozpocząć dwie sesje protokołu (z Alice i z Bobem) i podając się za przeciwne strony, ustalić dwa klucze symetryczne wykorzystywane potem w dalszej komunikacji z nimi za pomocą szyfrowania symetrycznego.

Duża liczba wiadomości, która wysyłana jest na początku protokołu, musi zostać zaszyfrowana przez pierwszą ze stron przy użyciu szyfru symetrycznego.

Używany jest wtedy jeden z typowych i skutecznych algorytmów szyfrowania symetrycznego. Jedyną zmianą jaką się wprowadza, jest celowe osłabienie siły szyfru, poprzez wykorzystanie krótszych rzeczywistych kluczy symetrycznych. Zwykle zastępuje się oryginalny losowy klucz o długości powiedzmy 128 bitów, za pomocą klucza składającego się z 98 bitów zerowych połączonych z 30 losowymi bitami rzeczywistego klucza. To właśnie te 30 losowych bitów musi być złamanych przez odbiorcę wiadomości.