Wymiana klucza Diffie-Hellmana była jednym z najważniejszych osiągnięć w kryptografii klucza publicznego i nadal jest często implementowana w wielu dzisiejszych różnych protokołach bezpieczeństwa.
Pozwala ona dwóm stronom, które nie spotkały się wcześniej, na bezpieczne ustalenie klucza, który mogą wykorzystać do zabezpieczenia swojej komunikacji. W tym artykule wyjaśnimy, do czego służy, jak działa krok po kroku, jakie są jej różne odmiany, a także na co należy zwrócić uwagę, aby bezpiecznie ją wdrożyć.
Co to jest wymiana klucza Diffiego-Hellmana?
Wymiana klucza Diffiego-Hellmana była pierwszą szeroko stosowaną metodą bezpiecznego tworzenia i wymiany kluczy przez niezabezpieczony kanał.
Może to nie wydawać się tak ekscytujące lub przełomowe w powyższych terminach, więc podajmy przykład, który wyjaśnia, dlaczego wymiana kluczy Diffie-Hellmana była tak ważnym kamieniem milowym w świecie kryptografii i dlaczego jest nadal tak często używana dzisiaj.
Powiedzmy, że jesteś ściśle tajnym szpiegiem i musisz wysłać kilka ważnych informacji do swojej siedziby. Jak uniemożliwić wrogom zdobycie tej wiadomości?
Najczęstszym rozwiązaniem jest zaszyfrowanie jej za pomocą kodu. Najłatwiejszym sposobem jest wcześniejsze ustalenie, jakiego rodzaju kodu i klucza zamierzasz użyć, lub zrobienie tego za pośrednictwem bezpiecznego kanału komunikacyjnego.
Powiedzmy, że jesteś szczególnie złym szpiegiem i razem z centralą zdecydujecie się użyć słabego szyfru Shift do zaszyfrowania wiadomości. W tym szyfrze każde „a” staje się „b”, każde „b” staje się „c”, każde „c” staje się „d” i tak dalej, aż do „z”, które staje się „a”.
Pod tym szyfrem, wiadomość „Chodźmy na kolację” staje się „Mfu’t hfu ejoofs”. Na szczęście w naszej hipotetycznej sytuacji przeciwnicy są tak samo niekompetentni jak ty i nie są w stanie złamać tak prostego szyfru, co uniemożliwia im dostęp do treści wiadomości.
Ale co by się stało, gdybyś nie mógł wcześniej ustalić szyfru ze swoim odbiorcą?
Powiedzmy, że chcesz się porozumieć ze szpiegiem z sojuszniczego kraju, którego nigdy wcześniej nie spotkałeś. Nie masz bezpiecznego kanału, przez który mógłbyś z nim rozmawiać. Jeśli nie zaszyfrujesz swojej wiadomości, to każdy przeciwnik, który ją przechwyci, będzie mógł odczytać jej treść. Jeśli zaszyfrujesz wiadomość bez podania sojusznikowi kodu, wróg nie będzie w stanie jej odczytać, ale sojusznik też nie.
Ten problem był jednym z największych problemów kryptografii aż do lat 70-tych XX wieku:
Jak bezpiecznie wymieniać z kimś informacje, jeśli nie mieliśmy okazji wcześniej podzielić się kluczem?
Wymiana kluczy Diffiego-Hellmana była pierwszym publicznie stosowanym mechanizmem rozwiązania tego problemu. Algorytm ten pozwala osobom, które nigdy wcześniej się nie spotkały, bezpiecznie utworzyć wspólny klucz, nawet przez niezabezpieczony kanał, który może być monitorowany przez przeciwników.
Historia wymiany kluczy Diffie-Hellmana
Wymiana kluczy Diffie-Hellmana ma swoje korzenie w latach siedemdziesiątych XX wieku. XX wieku, jednak postępy te dotyczyły głównie kryptografii z kluczami symetrycznymi.
Agregaty z kluczami publicznymi pojawiły się w sferze publicznej dopiero w 1976 roku, kiedy Whitfield Diffie i Martin Hellman opublikowali pracę New Directions in Cryptography. Przedstawili w niej mechanizmy działania nowego systemu, który stał się znany jako wymiana kluczy Diffie-Hellman.
Praca ta była częściowo zainspirowana wcześniejszymi osiągnięciami Ralpha Merkle. Tak zwane zagadki Merkle’a polegają na tym, że jedna strona tworzy i wysyła do drugiej pewną liczbę zagadek kryptograficznych. Zagadki te wymagałyby umiarkowanej ilości zasobów obliczeniowych do rozwiązania.
Odbiorca losowo wybierałby jedną zagadkę do rozwiązania, a następnie wkładałby wysiłek niezbędny do jej ukończenia. Po rozwiązaniu zagadki, identyfikator i klucz sesji są ujawnione do odbiorcy. Odbiorca następnie przesyła identyfikator z powrotem do oryginalnego nadawcy, który pozwala nadawcy wiedzieć, który puzzle został rozwiązany.
Odkąd oryginalny nadawca stworzył puzzle, identyfikator pozwala im wiedzieć, który klucz sesji odbiorca odkrył, a dwie strony mogą korzystać z tego klucza do komunikowania się bardziej bezpiecznie. Jeśli atakujący podsłuchuje interakcję, będzie miał dostęp do wszystkich zagadek, jak również identyfikatora, który odbiorca przesyła z powrotem do oryginalnego nadawcy.
Identyfikator nie mówi atakującemu, który klucz sesji jest używany, więc najlepszym podejściem do odszyfrowania informacji jest rozwiązanie wszystkich zagadek, aby odkryć prawidłowy klucz sesji. Ponieważ atakujący będzie musiał rozwiązać średnio połowę zagadek, odkrycie klucza będzie dla niego o wiele trudniejsze niż dla odbiorcy.
Takie podejście zapewnia większe bezpieczeństwo, ale jest dalekie od idealnego rozwiązania. Wymiana kluczy Diffie-Hellmana wykorzystała niektóre z tych pomysłów i uczyniła je bardziej złożonymi, aby stworzyć bezpieczną metodę kryptografii klucza publicznego.
Ale chociaż algorytm ten stał się znany jako wymiana kluczy Diffie-Hellmana, Martin Hellman zaproponował, aby nazwać go wymianą kluczy Diffie-Hellmana-Merkle’a, aby odzwierciedlić pracę, jaką Ralph Merkle włożył w kryptografię klucza publicznego.
Publicznie uważano, że Merkle, Hellman i Diffie byli pierwszymi osobami, które opracowały kryptografię z kluczem publicznym, aż do roku 1997, kiedy to rząd brytyjski odtajnił prace wykonane na początku lat 70. przez Jamesa Ellisa, Clifforda Coxa i Malcolma Williamsona.
Okazuje się, że trio to wymyśliło pierwszy schemat szyfrowania z kluczem publicznym w latach 1969-1973, ale ich praca była utajniona przez dwie dekady. Były one prowadzone w ramach Government Communication Headquarters (GCHQ), brytyjskiej agencji wywiadowczej.
Jego odkryciem był tak naprawdę algorytm RSA, więc Diffie, Hellman i Merkle nadal byli pierwszymi, którzy opracowali wymianę kluczy Diffie-Hellman, ale już nie pierwszymi wynalazcami kryptografii z kluczem publicznym.
Gdzie stosowana jest wymiana kluczy Diffiego-Hellmana?
Głównym celem wymiany kluczy Diffiego-Hellmana jest bezpieczne opracowanie wspólnych sekretów, które mogą być użyte do uzyskania kluczy. Klucze te mogą być następnie użyte w algorytmach z kluczami symetrycznymi do przesyłania informacji w sposób chroniony. Algorytmy symetryczne są zwykle używane do szyfrowania większości danych, ponieważ są bardziej wydajne niż algorytmy klucza publicznego.
Technicznie wymiana kluczy Diffiego-Hellmana może być używana do ustanawiania kluczy publicznych i prywatnych. Jednak w praktyce, zamiast tego używa się zwykle RSA. Dzieje się tak dlatego, że algorytm RSA jest również zdolny do podpisywania certyfikatów klucza publicznego, podczas gdy wymiana kluczy Diffie-Hellmana nie jest możliwa.
Algorytm ElGamal, który był często używany w PGP, jest oparty na wymianie kluczy Diffie-Hellmana, więc każdy protokół, który go używa, skutecznie implementuje rodzaj Diffie-Hellmana.
Jako jedna z najbardziej powszechnych metod bezpiecznej dystrybucji kluczy, wymiana kluczy Diffie-Hellmana jest często implementowana w protokołach bezpieczeństwa takich jak TLS, IPsec, SSH, PGP i wielu innych. To sprawia, że jest ona integralną częścią naszej bezpiecznej komunikacji.
Jako część tych protokołów, wymiana klucza Diffie-Hellmana jest często używana do zabezpieczenia połączenia ze stroną internetową, do zdalnego dostępu do innego komputera oraz do wysyłania zaszyfrowanych wiadomości e-mail
Jak działa wymiana klucza Diffie-Hellmana?
Wymiana klucza Diffie-Hellmana jest złożona i może być trudno zrozumieć jej działanie. Wykorzystuje ona bardzo duże liczby i dużo matematyki, czyli coś, czego wielu z nas wciąż się boi z powodu długich i nudnych lekcji w szkole średniej.
Aby ułatwić zrozumienie, zaczniemy od wyjaśnienia wymiany klucza Diffiego-Hellmana za pomocą analogii. Gdy już będziesz miał ogólne pojęcie o tym, jak to działa, przejdziemy do bardziej technicznego opisu procesów leżących u podstaw tego procesu.
Najlepszą analogią dla schematu Diffiego-Hellmana jest myślenie o dwóch osobach mieszających farbę. Użyjmy standardu kryptografii i powiedzmy, że ich imiona to Alice i Bob. Oboje zgadzają się na losowy kolor na początek. Powiedzmy, że wysyłają do siebie wiadomość i decydują się na żółty jako wspólny kolor, tak jak na poniższym schemacie:
Ustalają swój własny kolor. Nie informują drugiej strony o swoim wyborze. Załóżmy, że Alicja wybiera kolor czerwony, a Bob lekko zielonkawy niebieski.
Następnym krokiem jest zmieszanie przez Alicję i Boba ich tajnego koloru (czerwonego dla Alicji, zielonkawo-niebieskiego dla Boba) z żółtym, który wspólnie ustalili. Zgodnie z diagramem, Alicja uzyskuje oranżowy kolor, a Bob głębszy niebieski.
Po zakończeniu mieszania wysyłają wynik do drugiej strony. Alicja otrzymuje głębszy niebieski, podczas gdy Bob otrzymuje pomarańczową farbę.
Po otrzymaniu wymieszanego wyniku od partnera, dodają do niego swój tajny kolor. Alice bierze głębszy niebieski i dodaje swoją sekretną czerwoną farbę, podczas gdy Bob dodaje swój sekretny zielonkawo-niebieski do pomarańczowej mieszanki, którą właśnie otrzymał.
Wynik? Oboje wychodzą z tym samym kolorem, który w tym przypadku jest obrzydliwym brązem. To może nie być rodzaj koloru, że chcesz malować swój pokój dzienny z, ale to jest wspólny kolor niemniej jednak. Ten wspólny kolor jest określany jako wspólny sekret.
Krytyczną częścią wymiany kluczy Diffie-Hellmana jest to, że obie strony kończą z tym samym wynikiem, bez potrzeby wysyłania całego wspólnego sekretu przez kanał komunikacyjny. Wybór wspólnego koloru, ich własnych tajnych kolorów, wymiana mieszanki, a następnie dodanie jeszcze raz własnego koloru, daje obu stronom sposób na dojście do tego samego wspólnego sekretu bez konieczności przesyłania całości.
Jeśli atakujący podsłuchuje wymianę, wszystko, do czego może uzyskać dostęp, to wspólny żółty kolor, z którym Alice i Bob zaczynają, jak również mieszane kolory, które są wymieniane. Ponieważ jest to naprawdę zrobione z ogromnymi liczbami zamiast farby, te informacje nie są wystarczające do ataku, aby odkryć jeden z początkowych tajnych kolorów lub wspólny sekret (technicznie możliwe jest obliczenie wspólnego sekretu z tych informacji, ale w bezpiecznej implementacji wymiany kluczy Diffie-Hellmana, zajęłoby to niewykonalną ilość czasu i zasobów obliczeniowych, aby to zrobić).
Ta struktura wymiany kluczy Diffie-Hellmana jest tym, co czyni ją tak użyteczną. Pozwala ona dwóm stronom komunikować się za pomocą potencjalnie niebezpiecznego połączenia i nadal wymyślać wspólny sekret, który mogą wykorzystać do tworzenia kluczy szyfrujących dla ich przyszłej komunikacji. Nie ma znaczenia, czy napastnicy podsłuchują, ponieważ kompletny wspólny sekret nigdy nie jest przesyłany przez połączenie.
Szczegóły techniczne wymiany kluczy Diffie-Hellmana
Czas na trochę matematyki…
Nie martw się, zrobimy to powoli i postaramy się, aby cały proces był tak łatwy do zrozumienia, jak to tylko możliwe. Schemat Diffiego-Hellmana opiera się na podobnym założeniu, co analogia przedstawiona powyżej, ale zamiast mieszania i przesyłania kolorów, schemat Diffiego-Hellmana wykonuje obliczenia na wyjątkowo dużych liczbach pierwszych, a następnie przesyła je dalej.
Aby zapewnić bezpieczeństwo, zaleca się, aby liczba pierwsza (p) miała długość co najmniej 2048 bitów, co jest binarnym odpowiednikiem liczby dziesiętnej o tym rozmiarze:
415368757628736598425938247569843765827634879128375827365928736 84273684728938572983759283475934875938475928475928739587249587 29873958729835792875982795837529876348273685729843579348795827 93857928739548772397592837592478593867045986792384737826735267 3547623568734869386945673456827659498063849024875809603947902 7945982730187439759284620950293759287049502938058920983945872 0948602984912837502948019371092480193581037995810937501938507913 95710937597019385089103951073058710393701934701938091803984091804 98109380198501398401983509183501983091079180395810395190395180935 8109385019840193580193840198340918093851098309180019
Aby nikomu nie eksplodowała głowa, przećwiczymy to wyjaśnienie na dużo mniejszych liczbach. Należy pamiętać, że wymiana klucza Diffie-Hellmana byłaby niezabezpieczona, gdyby używano w niej liczb tak małych jak te w naszym przykładzie. Używamy tak małych liczb tylko po to, aby zademonstrować tę koncepcję w prostszy sposób.
W najbardziej podstawowej formie wymiany klucza Diffie-Hellmana, Alice i Bob zaczynają od wzajemnego ustalenia dwóch liczb na początek, w przeciwieństwie do pojedynczej wspólnej farby w powyższym przykładzie. Są to modulus (p) i podstawa (g).
W praktycznym użyciu modulus (p) jest bardzo dużą liczbą pierwszą, podczas gdy podstawa (g) jest stosunkowo mała, aby uprościć obliczenia. Podstawa (g) pochodzi z grupy cyklicznej (G), która jest zwykle generowana na długo przed wykonaniem innych kroków.
Dla naszego przykładu, powiedzmy, że modulus (p) wynosi 17, podczas gdy podstawa (g) wynosi 4.
Po wspólnym ustaleniu tych liczb, Alice ustala tajną liczbę (a) dla siebie, podczas gdy Bob wybiera swoją tajną liczbę (b). Powiedzmy, że wybierają:
a = 3
b = 6
Alice wykonuje następnie następujące obliczenia, aby otrzymać liczbę, którą wyśle do Boba:
A = ga mod p
W powyższym obliczeniu mod oznacza operację modulo. Są to zasadniczo obliczenia mające na celu określenie reszty po podzieleniu lewej strony przez prawą. Na przykład:
15 mod 4 = 3
Jeśli rozumiesz, jak działają operacje modulo, możesz je wykonać samodzielnie w poniższych obliczeniach, w przeciwnym razie możesz skorzystać z kalkulatora online.
Wstawmy więc nasze liczby do wzoru:
A = 43 mod 17
A = 64 mod 17
A = 13
Gdy zrobimy to samo dla Boba, otrzymamy:
B = 46 mod 17
B = 4096 mod 17
B = 16
Alice następnie wysyła swój wynik (A) do Boba, a Bob wysyła swoją liczbę (B) do Alice. Następnie Alice oblicza wspólny sekret (s), używając liczby, którą otrzymała od Boba (B) i swojej tajnej liczby (a), korzystając z następującego wzoru:
s = Ba mod p
s = 163 mod 17
s = 4,096 mod 17
s = 16
Bob następnie wykonuje to, co jest zasadniczo tym samym obliczeniem, ale z liczbą, którą wysłała mu Alice (A), jak również z jego własną tajną liczbą (b):
s = Ab mod p
s = 136 mod 17
s = 4,826,809 mod 17
s = 16
Jak widać, obie strony skończyły z tym samym wynikiem dla s, 16. To jest wspólny sekret, który znają tylko Alice i Bob. Mogą go następnie użyć do ustanowienia klucza do szyfrowania symetrycznego, pozwalając im bezpiecznie przesyłać informacje między sobą w taki sposób, że tylko oni mogą uzyskać do nich dostęp.
Zauważ, że chociaż B i s są takie same w powyższym przykładzie, jest to tylko zbieg okoliczności oparty na małych liczbach, które zostały wybrane do tej ilustracji. Normalnie, wartości te nie byłyby takie same w prawdziwej implementacji wymiany kluczy Diffie-Hellmana.
Mimo, że wiele z powyższych danych jest przesyłanych przez kanał w postaci czystego tekstu (p, g, A i B) i mogą być odczytane przez potencjalnych napastników, wspólny sekret (s) nigdy nie jest przesyłany. Nie byłoby praktyczne dla atakującego, aby obliczyć wspólny sekret (s) lub którykolwiek z tajnych numerów (a i b) z informacji, które są przesyłane w cleartext.
Oczywiście, to zakłada, że wymiana klucza Diffie-Hellman jest prawidłowo zaimplementowane i wystarczająco duże liczby są używane. Tak długo, jak te postanowienia są przestrzegane, wymiana klucza Diffie-Hellmana jest uważana za bezpieczny sposób ustanowienia współdzielonego sekretu, który może być użyty do zabezpieczenia przyszłej komunikacji.
Ustanawianie współdzielonego klucza pomiędzy wieloma stronami
Wymiana klucza Diffie-Hellmana może być również użyta do ustanowienia współdzielonego klucza z większą liczbą uczestników. Działa to w ten sam sposób, z tą różnicą, że kolejne rundy obliczeń są potrzebne, aby każda ze stron dodała swój tajny numer i w końcu uzyskała ten sam wspólny sekret.
Tak jak w dwupartyjnej wersji wymiany kluczy Diffiego-Hellmana, niektóre części informacji są przesyłane przez niezabezpieczone kanały, ale nie na tyle, aby atakujący był w stanie obliczyć wspólny sekret.
Dlaczego wymiana kluczy Diffiego-Hellmana jest bezpieczna?
Na poziomie matematycznym, wymiana kluczy Diffiego-Hellmana opiera się na funkcjach jednokierunkowych jako podstawie jej bezpieczeństwa. Są to obliczenia, które są proste do wykonania w jedną stronę, ale znacznie trudniejsze do obliczenia w drugą.
A dokładniej, opiera się ona na problemie Diffie-Hellmana, który zakłada, że przy odpowiednich parametrach obliczenie gab z oddzielnych wartości g, ga i gb jest niewykonalne. Obecnie nie ma publicznie znanego sposobu na łatwe odnalezienie gab z pozostałych wartości, dlatego wymiana klucza Diffie-Hellmana jest uważana za bezpieczną, pomimo tego, że atakujący mogą przechwycić wartości p, g, A i B.
Uwierzytelnianie & wymiana klucza Diffie-Hellmana
W świecie rzeczywistym wymiana klucza Diffie-Hellmana rzadko jest używana samodzielnie. Głównym tego powodem jest to, że nie zapewnia ona żadnego uwierzytelniania, co pozostawia użytkowników podatnymi na ataki typu man-in-the-middle.
Ataki te mogą mieć miejsce, gdy wymiana kluczy Diffie-Hellman jest zaimplementowana samodzielnie, ponieważ nie posiada ona żadnych środków weryfikacji, czy druga strona w połączeniu jest naprawdę tym, za kogo się podaje. Bez jakiejkolwiek formy uwierzytelnienia, użytkownicy mogą w rzeczywistości łączyć się z atakującymi, gdy myślą, że komunikują się z zaufaną stroną.
Z tego powodu, wymiana kluczy Diffie-Hellmana jest zazwyczaj implementowana wraz z jakimiś środkami uwierzytelniania. Często wiąże się to z wykorzystaniem certyfikatów cyfrowych i algorytmu klucza publicznego, takiego jak RSA, do weryfikacji tożsamości każdej ze stron.
Odmiany wymiany klucza Diffie-Hellmana
Wymiana klucza Diffie-Hellmana może być zaimplementowana na wiele różnych sposobów, a także stała się podstawą dla kilku innych algorytmów. Niektóre z tych implementacji zapewniają autoryzację, podczas gdy inne mają różne cechy kryptograficzne, takie jak doskonała tajemnica przekazu.
Elliptic-curve Diffie-Hellman
Elliptic-curve Diffie-Hellman wykorzystuje algebraiczną strukturę krzywych eliptycznych, aby umożliwić swoim implementacjom osiągnięcie podobnego poziomu bezpieczeństwa przy mniejszym rozmiarze klucza. Klucz 224-bitowy o krzywej eliptycznej zapewnia taki sam poziom bezpieczeństwa jak 2048-bitowy klucz RSA. Dzięki temu wymiana kluczy może być bardziej wydajna, a zapotrzebowanie na pamięć masową mniejsze.
Oprócz mniejszej długości klucza i faktu, że opiera się na właściwościach krzywych eliptycznych, eliptyczno-klawiszowa metoda Diffie-Hellmana działa w podobny sposób jak standardowa wymiana kluczy Diffie-Hellmana.
TLS
TLS, który jest protokołem używanym do zabezpieczenia dużej części Internetu, może używać wymiany Diffie-Hellmana na trzy różne sposoby: anonimowy, statyczny i efemeryczny. W praktyce, tylko efemeryczny Diffie-Hellman powinien być zaimplementowany, ponieważ pozostałe opcje mają problemy z bezpieczeństwem.
- Anonimowy Diffie-Hellman – Ta wersja wymiany klucza Diffie-Hellman nie używa żadnego uwierzytelniania, pozostawiając ją podatną na ataki man-in-the-middle. Nie powinna być używana ani implementowana.
- Static Diffie-Hellman – Static Diffie-Hellman używa certyfikatów do uwierzytelniania serwera. Domyślnie nie uwierzytelnia klienta, ani nie zapewnia tajemnicy przekazu.
- Ephemeral Diffie-Hellman – Jest uważany za najbezpieczniejszą implementację, ponieważ zapewnia doskonałą tajemnicę przekazu. Jest ona zazwyczaj połączona z algorytmem takim jak DSA lub RSA w celu uwierzytelnienia jednej lub obu stron połączenia. Ephemeral Diffie-Hellman używa różnych par kluczy za każdym razem, gdy protokół jest uruchamiany. Dzięki temu połączenie jest doskonale zabezpieczone, ponieważ nawet jeśli klucz zostanie złamany w przyszłości, nie może być użyty do odszyfrowania wszystkich wiadomości z przeszłości.
ElGamal
ElGamal jest algorytmem klucza publicznego zbudowanym na bazie wymiany kluczy Diffie-Hellmana. Podobnie jak Diffie-Hellman, nie zawiera on żadnych przepisów dotyczących uwierzytelniania i jest zazwyczaj łączony z innymi mechanizmami służącymi do tego celu.
ElGamal był głównie używany w PGP, GNU Privacy Guard i innych systemach, ponieważ jego główny rywal, RSA, został opatentowany. Patent RSA wygasł w 2000 roku, co pozwoliło na jego swobodną implementację po tej dacie. Od tego czasu ElGamal nie jest już tak często implementowany.
STS
Protokół Station-to-Station (STS) jest również oparty na wymianie kluczy Diffie-Hellmana. Jest to kolejny schemat uzgadniania kluczy, jednak zapewnia on ochronę przed atakami typu man-in-the-middle, jak również idealną tajemnicę przekazu.
Wymaga on, aby obie strony w połączeniu posiadały już parę kluczy, która jest używana do uwierzytelniania każdej ze stron. Jeśli strony nie są jeszcze sobie znane, certyfikaty mogą być użyte do potwierdzenia tożsamości obu stron.
Wymiana klucza Diffie-Hellmana & RSA
Jak rozmawialiśmy wcześniej, wymiana klucza Diffie-Hellmana jest często implementowana wraz z RSA lub innymi algorytmami w celu zapewnienia uwierzytelnienia dla połączenia. Jeśli jesteś zaznajomiony z RSA, możesz się zastanawiać, dlaczego ktoś miałby zawracać sobie głowę używaniem wymiany kluczy Diffie-Hellmana, skoro RSA umożliwia bezpieczną komunikację stronom, które nigdy wcześniej się nie spotkały.
RSA pozwala użytkownikom szyfrować wiadomości kluczem publicznym korespondenta, tak że mogą one zostać odszyfrowane tylko za pomocą pasującego klucza prywatnego. Jednak w praktyce RSA nie jest używana do szyfrowania całej komunikacji – byłoby to zbyt nieefektywne.
Zamiast tego, RSA jest często używana tylko jako środek do uwierzytelniania obu stron. Odbywa się to za pomocą cyfrowych certyfikatów każdej ze stron, które zostały zweryfikowane przez urząd certyfikacji, aby udowodnić, że właściciel certyfikatu jest naprawdę tym, za kogo się podaje i że klucz publiczny na certyfikacie rzeczywiście należy do niego.
W celu wzajemnego uwierzytelnienia każda ze stron podpisze wiadomość przy użyciu swojego klucza prywatnego, a następnie wyśle ją do swojego partnera komunikacyjnego. Każdy odbiorca może następnie zweryfikować tożsamość drugiej strony, sprawdzając podpisane wiadomości z kluczem publicznym na certyfikacie cyfrowym swojego partnera komunikacyjnego (więcej szczegółów na temat tego, jak to działa, można znaleźć w wyżej wymienionym artykule na temat RSA, zwłaszcza w sekcji Podpisywanie wiadomości).
Teraz, gdy obie strony zostały uwierzytelnione, jest technicznie możliwe kontynuowanie używania RSA do bezpiecznego przesyłania zaszyfrowanych wiadomości między sobą, jednak skończyłoby się to zbyt nieefektywnie.
Aby obejść tę nieefektywność, wiele protokołów bezpieczeństwa używa algorytmu takiego jak wymiana klucza Diffie-Hellmana, aby wymyślić wspólny sekret, który może być użyty do ustanowienia wspólnego klucza symetrycznego. Ten klucz symetryczny jest następnie używany w algorytmie klucza symetrycznego, takim jak AES, do szyfrowania danych, które dwie strony zamierzają bezpiecznie przesyłać między sobą.
Może się to wydawać skomplikowanym i zagmatwanym procesem, ale w końcu jest on znacznie szybszy i mniej wymagający w stosunku do zasobów w porównaniu z użyciem algorytmu klucza publicznego do całej wymiany. Dzieje się tak dlatego, że szyfrowanie z kluczem symetrycznym jest o rząd wielkości bardziej wydajne niż szyfrowanie z kluczem publicznym.
Oprócz nieefektywności, o których właśnie wspomnieliśmy, istnieje kilka innych minusów, które wynikają z używania wyłącznie RSA. RSA potrzebuje paddingu, aby uczynić go bezpiecznym, więc dodatkowy algorytm musiałby być odpowiednio zaimplementowany obok niego, aby uczynić go bezpiecznym.
RSA nie zapewnia również idealnej tajemnicy, co jest kolejną wadą w porównaniu z efemeryczną wymianą kluczy Diffie-Hellmana. Łącznie, z tych powodów, w wielu sytuacjach najlepiej jest stosować RSA tylko w połączeniu z wymianą klucza Diffie-Hellman.
Alternatywnie, wymiana klucza Diffie-Hellman może być połączona z algorytmem takim jak Digital Signature Standard (DSS) w celu zapewnienia uwierzytelnienia, wymiany klucza, poufności i sprawdzenia integralności danych. W takiej sytuacji RSA nie jest konieczna do zabezpieczenia połączenia.
Zagadnienia bezpieczeństwa wymiany kluczy Diffie-Hellmana
Bezpieczeństwo wymiany kluczy Diffie-Hellmana zależy od sposobu jej implementacji, a także od tego, jakie liczby są do niej dobierane. Jak już wspomnieliśmy, nie ma ona możliwości uwierzytelnienia drugiej strony, ale w praktyce stosuje się inne mechanizmy, aby upewnić się, że druga strona połączenia nie jest oszustem.
Parametry doboru liczb
Gdyby w rzeczywistej implementacji wymiany klucza Diffiego-Hellmana używano liczb tak małych, jak te w naszym przykładzie, proces wymiany byłby trywialny do złamania przez atakującego. Ale nie tylko rozmiar liczb ma znaczenie – liczby te muszą być również wystarczająco losowe. Jeśli generator liczb losowych daje przewidywalne dane wyjściowe, może całkowicie podważyć bezpieczeństwo wymiany kluczy Diffiego-Hellmana.
Liczba p powinna mieć długość 2048 bitów, aby zapewnić bezpieczeństwo. Podstawa, g, może być stosunkowo małą liczbą, taką jak 2, ale musi pochodzić z rzędu G, który ma duży czynnik pierwszy
Atak Logjam
Wymiana kluczy Diffiego-Hellmana została zaprojektowana w oparciu o trudny do rozwiązania problem logarytmu dyskretnego. Najskuteczniejszym publicznie znanym mechanizmem znajdowania rozwiązania jest algorytm sita pola liczbowego.
Możliwości tego algorytmu były brane pod uwagę przy projektowaniu wymiany kluczy Diffiego-Hellmana. Do 1992 roku wiadomo było, że dla danej grupy G trzy z czterech kroków algorytmu mogą być potencjalnie obliczone wcześniej. Jeśli ten postęp zostałby zapisany, ostatni krok mógłby zostać obliczony w stosunkowo krótkim czasie.
Nie było to zbyt niepokojące, dopóki nie zdano sobie sprawy, że znaczna część ruchu internetowego wykorzystuje te same grupy, które mają 1024 bity lub mniej. W 2015 roku zespół akademicki przeprowadził obliczenia dla najbardziej powszechnego 512-bitowego prime’u używanego przez wymianę klucza Diffie-Hellmana w TLS.
Byli oni również w stanie zdegradować 80% serwerów TLS, które obsługiwały DHE-EXPORT, tak aby akceptowały 512-bitową wymianę klucza Diffie-Hellmana dla połączenia. Oznacza to, że każdy z tych serwerów jest podatny na atak ze strony dobrze przygotowanego przeciwnika.
Badacze dokonali ekstrapolacji swoich wyników, szacując, że państwo narodowe mogłoby złamać 1024-bitowy klucz główny. Poprzez złamanie pojedynczego, najczęściej używanego 1024-bitowego prime’a, zespół akademicki oszacował, że przeciwnik może monitorować 18% z miliona najpopularniejszych stron HTTPS.
Potwierdzili, że drugi prime umożliwiłby przeciwnikowi odszyfrowanie połączeń 66% serwerów VPN i 26% serwerów SSH. W dalszej części raportu naukowcy zasugerowali, że NSA może już mieć takie możliwości.
„Dokładna lektura opublikowanych przecieków NSA pokazuje, że ataki agencji na VPN-y są spójne z osiągnięciem takiego złamania.”
Mimo tej luki, wymiana klucza Diffie-Hellmana może być nadal bezpieczna, jeśli jest poprawnie zaimplementowana. Tak długo jak używany jest klucz 2048-bitowy, atak Logjam nie zadziała. Zaktualizowane przeglądarki są również zabezpieczone przed tym atakiem.
Czy wymiana klucza Diffie-Hellmana jest bezpieczna?
Mimo że wymiana klucza Diffie-Hellmana może wydawać się skomplikowana, jest ona fundamentalną częścią bezpiecznej wymiany danych online. Tak długo, jak jest ona zaimplementowana wraz z odpowiednią metodą uwierzytelniania, a liczby zostały odpowiednio dobrane, nie jest ona uważana za podatną na atak.
Wymiana klucza Diffie-Hellmana była innowacyjną metodą pomagającą dwóm nieznanym stronom bezpiecznie się komunikować, kiedy została opracowana w latach 70-tych. Chociaż obecnie wdrażamy nowsze wersje z większymi kluczami, aby chronić przed nowoczesną technologią, sam protokół wygląda na bezpieczny aż do nadejścia obliczeń kwantowych i zaawansowanych ataków, które z nimi nadejdą.
Jak obliczenia kwantowe wpłyną na wymianę klucza Diffie-Hellmana?
Obliczenia kwantowe to wschodząca gałąź informatyki, która wciąż dokonuje przełomów. Specyfika działania komputerów kwantowych jest skomplikowana i wykracza poza zakres tego artykułu, jednak technologia ta stwarza istotne problemy w dziedzinie kryptografii.
Prostym wyjaśnieniem jest to, że oczekuje się, iż komputery kwantowe będą w stanie rozwiązać pewne problemy, które obecnie są niewykonalne dla komputerów klasycznych. Otworzy to wiele drzwi i przyniesie nowe możliwości. Wystarczająco silne komputery kwantowe będą w stanie uruchamiać algorytmy kwantowe, które mogą skuteczniej rozwiązywać różne problemy matematyczne.
Mimo że brzmi to świetnie, bezpieczeństwo wielu naszych obecnych mechanizmów kryptograficznych opiera się na tym, że problemy te są trudne do rozwiązania. Jeśli te problemy matematyczne staną się łatwiejsze do obliczenia, łatwiej będzie również złamać te mechanizmy kryptograficzne.
Jednym z takich algorytmów kwantowych jest algorytm Grovera. Gdy komputery kwantowe staną się wystarczająco potężne, przyspieszą ataki na szyfry z kluczem symetrycznym, takie jak AES. Można to jednak łatwo złagodzić, podwajając rozmiar klucza.
Największe obawy budzi to, jak algorytm Shora wpłynie na kryptografię z kluczem publicznym. Dzieje się tak dlatego, że bezpieczeństwo większości popularnych algorytmów klucza publicznego opiera się na ogromnej trudności rozwiązania jednego z tych trzech obliczeń:
- Problem dyskretnego logarytmu
- Problem faktoryzacji liczb całkowitych
- Problem eliptycznego dyskretnego logarytmu
Szczegóły każdego z nich nie mają większego znaczenia, ale możesz podążać za linkami, jeśli chcesz uzyskać dodatkowe informacje. Ważne jest to, że gdy pojawią się wystarczająco potężne komputery kwantowe, rozwiązywanie tych problemów za pomocą algorytmu Shora stanie się o wiele bardziej praktyczne. W miarę jak problemy te staną się łatwiejsze do rozwiązania, systemy kryptograficzne, które na nich bazują, staną się mniej bezpieczne.
Kryptografia z kluczem publicznym odgrywa fundamentalną rolę w ochronie naszej komunikacji, dlatego też obliczenia kwantowe stanowią ogromne wyzwanie dla kryptografów.
W przypadku wymiany kluczy Diffiego-Hellmana jej bezpieczeństwo opiera się na niepraktyczności możliwości rozwiązania problemu logarytmu dyskretnego przy użyciu obecnej technologii i zasobów. Jednak zagrożenie ze strony algorytmu Shora staje się coraz bliższe z każdym postępem w dziedzinie obliczeń kwantowych.
Trudno jest określić przybliżony czas, kiedy obliczenia kwantowe poważnie zagrożą wymianie kluczy Diffiego-Hellmana, ponieważ niektórzy badacze są o wiele bardziej optymistyczni niż inni. Mimo to opracowywane są zamienniki dla wymiany klucza Diffiego-Hellmana i innych algorytmów klucza publicznego, aby upewnić się, że jesteśmy przygotowani na nadejście takiego czasu.
Potencjalne zamienniki dla wymiany klucza Diffiego-Hellmana
Zagrożenie ze strony komputerów kwantowych nie jest bezpośrednie, więc społeczność kryptograficzna nie ustaliła jeszcze konkretnych alternatyw dla wymiany klucza Diffiego-Hellmana. Niemniej jednak, wiele ścieżek jest w trakcie opracowywania. Należą do nich:
- Kryptografia oparta na kratach
- Kryptografia wielowymiarowa
- Kryptografia izogenezy krzywej eliptycznej
Nadal nie wiemy dokładnie, jak będzie wyglądał świat post-kwantowy dla kryptografii, ale społeczność zajmująca się bezpieczeństwem aktywnie pracuje nad problemami i nadąża za postępem w świecie obliczeń kwantowych. Podczas gdy w przyszłości nastąpią duże zmiany, nie jest to nic, czego przeciętny człowiek powinien się obawiać – prawdopodobnie nawet nie zauważysz, kiedy jakiekolwiek zmiany będą miały miejsce.