Pierwsze standardy kryptografii postkwantowej

August 19, 2022September 10, 2022 jakub mielczarek1 Comment

5 lipca bieżącego roku, amerykański Narodowy Instytut Norm i Techniki (National Institute of Standards and Technology – NIST) ogłosił pierwsze wyniki zainicjowanej w 2016 roku procedury wyłonienia postkwantowych standardów kryptograficznych. Wybrano jeden algorytm wymiany klucza oraz trzy algorytmy podpisu elektronicznego. W oparciu o te algorytmy, zostaną opracowane nowe standardy kryptograficzne, zapewniające odporność na możliwe przyszłe ataki przeprowadzane z udziałem komputerów kwantowych. Wyłonione przez NIST postkwantowe algorytmy kryptograficzne, będą w najbliższych latach stopniowo zastępować obecnie stosowane algorytmy kryptografii asymetrycznej, stanowiące podstawę bezpieczeństwa komunikacji w internecie.

Po co nam kryptografia postkwantowa?

Dostępnym obecnie komputerom kwantowym daleko jeszcze do osiągnięcia zdolności umożliwiających skuteczną kryptoanalizę stosowanych współcześnie algorytmów szyfrujących. Niemniej jednak, zagrożenie takie, choć odsunięte w czasie, teoretycznie istnieje i należy je brać pod uwagę w analizie ryzyka. Problem ten dotyczy głównie algorytmów kryptografii klucza publicznego (kryptografii asymetrycznej), w których szyfrowanie i deszyfrowanie odbywa się za pomocą dwóch różnych kluczy: prywatnego i publicznego. Wykorzystując kryptoanalizę kwantową, możliwe staje się efektywne obliczeniowo odzyskiwanie klucza prywatnego w oparciu o znajomość klucza publicznego. Do przykładów kryptografii klucza publicznego należą algorytm RSA (Rivest-Shamir-Adleman), algorytmy kryptografii krzywych eliptycznych (Elliptic Curve Cryptography – ECC) oraz protokół uzgadaniania klucza Diffiego-Hellmana (DH) (także w wersji opartej na krzywych eliptycznych, czyli tzw. Elliptic Curve Diffie-Hellman – ECDH).

Jednym z głównych zastosowań tych algorytmów jest zdalna wymiana sekretnego klucza, służącego następnie do zaszyfrowania wiadomości (tekstu jawnego), już za pomocą algorytmów symetrycznych. W przypadku szyfrów symetrycznych, ten sam klucz jest wykorzystywany do szyfrowania i odszyfrowania wiadomości.

Opisana procedura znajduje szerokie zastosowanie w bezpiecznej wymianie informacji, w tym tych które możemy scharakteryzować jako szczególnie wrażliwe. Co więcej, część tego typu informacji może pozostać wrażliwa przez długi okres czasu, liczony w dziesiątkach lat. Stąd też istnieje uzasadniona obawa, że informacje te (w postaci zaszyfrowanej) mogą zostać przechowywane przez okres nawet kilkudziesięciu lat, po czym zostaną skutecznie odczytane z zastosowaniem kryptoanalizy kwantowej – łamiąc szyfry asymetryczne i uzyskując dostęp do klucza szyfrującego właściwą informację. Warto dodać, że nie pomoże tu nawet własność tzw. utajnienia z wyprzedzeniem (ang. forward secrecy), stosowana dziś powszechnie w szyfrowaniu ruchu w internecie.

W świetle potencjalnego kryzysu jaki taka sytuacja mogłaby wywołać, społeczność kryptograficzna podjęła działania mające na celu opracowanie zbioru rozwiązań kryptograficznych odpornych na znane ataki z wykorzystaniem komputerów kwantowych. Właśnie tę gałąź kryptografii określamy mianem kryptografii postkawntowej (ang. post-quantum cryptography – PQC) [1].

O ile, w świetle obecnego stosunkowo wolnego tempa wzrostu zasobów obliczeniowych komputerów kwantowych i wielu przeszkód technicznych związanych ze skalowaniem procesorów kwantowych, szerokie wprowadzanie kryptografii postkwantowej może stwarzać wrażenie działań nieco przedwczesnych, należy mieć na uwadze złożoność i długotrwałość procesu opracowania, testowania, standaryzacji i szerokiej implementacji algorytmów postkwantowych. Fizyk kwantowy Michele Mosca, ujął ten problem w ramach następującej nierówności [2]: x+y>z, gdzie x to wymagany przez nas czas zapewnienia bezpieczeństwa informacji, y to czas wdrożenia nowych rozwiązań zapewniających bezpieczeństwo przed atakami kwantowymi, z to czas potrzebny na powstanie komputera zdolnego do łamania obecnych szyfrów kryptografii klucza publicznego. Jeśli powyższa nierówność zachodzi, to musimy uznać sytuację za problematyczną.

Oczywiście, dużą niepewnością obarczone jest wyznaczenie wartości parametru z. W niniejszym artykule, koncentruję uwagę na kryptografii postkwantowej i nie jest to miejsce na wnikliwą analizą aspektów fizycznych i technicznych stojących za prognozowaniem wartości parametru z. Uproszczona analiza, przedstawiona w moim wcześniejszym artykule pt. “Technologie kwantowe a cyberbezpieczeństwo” [3], wskazuje, że wartość z może wynosić obecnie około 25 lat. Realistycznie, możemy przyjąć, że szerokie wdrożenie standardów postkwantowych zajmie około 10 lat. Zastosowanie tych wartości do nierówności Mosca, prowadzi do wyrażenia: x > 15 lat. Oznacza, to że wymiana w internecie informacji, którymi nie chcielibyśmy się publicznie dzielić przez okres większy niż 15 lat, przestanie być bezpieczna pod koniec okresu adaptacji kryptografii postkwantowej. Rozważając bardziej optymistyczne scenariusze rozwoju technologii kwantowych, wartość ta ulegnie obniżeniu. Jednakże, już przytoczone tu ograniczenie, stanowi poważne ostrzeżenie w świetle wymiany informacji medycznych, biznesowych czy też komunikacji rządowej.

Konkursy NIST

W styczniu 1977 roku, amerykańskie Narodowe Biuro Standardów (ang. National Bureau of Standards), które w 1988 roku zostało przemianowane w NIST, opublikowało pierwszy powszechnie stosowany standard kryptografii symetrycznej – Digital Encryption Standard (DES). Pomimo wyłonienia projektanta algorytmu na drodze konkursowej, którym został IBM, proces standaryzacji nie przebiegł w sposób transparentny i jego wyniki szybko wzbudziły kontrowersje w środowisku kryptologicznym. Stało się to, w szczególności, za sprawą stosunkowo krótkiego, 56-bitowego, klucza. Na jego długość, jak dzisiaj wiemy, wpływ miała amerykańska National Security Agency (NSA), zaangażowana w przebieg procesu opracowania standardu DES [4]. W konsekwencji, już po dwudziestu latach od wprowadzenia szyfru DES, jego łamanie metodą siłową (ang. brute force) nie nastręczało większych problemów. DES stał się tym samym bezużyteczny (poza jego wykorzystaniem m.in. w algorytmach 3DES czy też DES-X) a NIST rozpoczął procedurę wyboru szyfru blokowego, stanowiącego nowy standard kryptografii symetrycznej. Tym razem jednak, w celu uniknięcia wcześniejszych kontrowersji (związanych również z pochodzeniem tak zwanych S-bloków, stanowiących element budulcowy algorytmu DES), zdecydowano się na w pełni otwartą i transparentną procedurę konkursową. Tak też wyłoniono algorytm Rijndael, który przybrał formę nowego standardu – Advanced Encryption Standard (AES), przyjętego w 2001 roku i obowiązującego do dzisiaj. Co więcej, w wersji z kluczem 256 bitowym jest on klasyfikowany jako algorytm postkwantowy.

W przeciągu ostatnich dwudziestu lat NIST opracował dziesiątki standardów i rekomendacji dotyczących algorytmów kryptograficznych, m.in. dotyczących funkcji skrótu (funkcji haszujących), podpisów elektronicznych, czy też generatorów kluczy. Do najnowszych inicjatyw NIST w zakresie standaryzacji kryptografii należą standardy lekkiej kryptografii (ang. lightweight cryptography), dedykowane dla urządzeń o ograniczonych zasobach obliczeniowych (mikrokontrolery, rozwiązania IoT, itp.), oraz dyskutowana tutaj standaryzacja kryptografii postkwantowej [5].

Procedura wyłonienia standardów kryptografii postkwantowej została zainicjowana w grudniu 2016 roku. Ogłoszony przez NIST konkurs dotyczył wyboru postkwantowego algorytm kryptografii klucza publicznego, mechanizmu enkapsulacji klucza (ang. Key Encapsulation Mechanism – KEM) oraz podpisu elektronicznego. Określono, pięć poziomów bezpieczeństwa dla algorytmów postkwantowych, odpowiadających bezpieczeństwu ze względu na ataki siłowe na szyfr blokowy z kluczem o długości 128, 192 i 256 bitów oraz ze względu na ataki kolizyjne na funkcje skrótu ze skrótem 256 i 384 bitowym. Dalsze, szczegółowe informacje dotyczące wymogów stawianych przed kandydatami zainteresowany Czytelnik znajdzie w dokumencie [6].

Warte podkreślenia, jest, że nowe standardy kryptografii postkwantowej odchodzą od protokołu uzgadniania klucza DH, w którym uczestniczą dwie komunikujące się strony. Nie przewiduje się zatem postkwantowej wersji protokołu Diffiego-Hellmana. Jako alternatywę przyjęto natomiast wspomnianą enkapsulację klucza, w której jedna ze stron wybiera sekretny klucz i dokonuje jego zaszyfrowania postkwantowym algorytmem asymetrycznym, wykorzystując klucz publiczny. Zaszyfrowany klucz jest następnie odzyskiwany przez drugą stronę, za pomocą klucza prywatnego. Rozwiązanie takie uznano za prostsze i łatwiejsze do implementacji i analizy [7].

Warto również podkreślić, że konkurs NIST nie obejmuje nowych standardów funkcji skrótu. Te obecnie stosowane (np. SHA-3) uważane są za odporne na ataki kwantowe. Dzięki temu, znajdują one także zastosowanie w postkwantowych algorytmach podpisu elektronicznego, opartych na funkcjach skrótu (ang. Hash-based signatures).

Postkwantowi zwycięzcy

Z przesłanych wyjściowo osiemdziesięciu dwóch propozycji, po zakończonej trzeciej rundzie, wyłoniono cztery algorytmy. Ponadto, cztery kolejne, zostały zakwalifikowane do, następnej, czwartej rundy [8].

Jako algorytm kryptografii klucza publicznego wyłoniony został CRYSTALS-Kyber [9]. Algorytm ten zapewnia również mechanizm enkapsulacji klucza (KEM). CRYSTALS-Kyber należy do klasy szyfrów kratowych (ang. lattice-based cryptography) [10], w których operacje wykonywane są na wielowymiarowych kratach, podobnych do sieci krystalicznych. Kraty dają możliwość zdefiniowania szeregu problemów, które uważane są za trudne obliczeniowo. Jednym z nich jest problem nauczania z błędami (ang. Learning With Errors – LWE), który w 2005 roku, zaproponował izraelski informatyk-teoretyk Oded Regev. Za swoje odkrycie został On w 2018 roku uhonorowany prestiżową Nagrodą Gödla. Algorytm CRYSTALS-Kyber bazuje na wariancie problemu LWE, w którym krata definiująca problem posiada pewną narzuconą strukturę, tzw. Module-LWE. W uzasadnieniu wyboru tego algorytmu, NIST podkreślił m.in. jego szybkość oraz nieduży rozmiar kluczy, rzędu kilobajta.

Artystyczne ujęcie drzewa Markle’a (stosowanego do tworzenia kluczy publicznych w algorytmach podpisu elektronicznego opartych na funkcjach skrótu) oraz krat. Źródło

Jako algorytmy podpisu elektronicznego zostały wyłonione: CRYSTALS-Dilithium [9], FALCON [11] oraz SPHINCS+ [12]. CRYSTALS-Dilithium, został zaprojektowany przez tę samą grupę co CRYSTALS-Kyber i uznano go za główny algorytm postkwantowego podpisu elektronicznego. Algorytm CRYSTALS-Dilithium oparty został na modyfikacji problemu LWR, tak zwanej nauce z zaokrągleniem (ang. Learning With Rounding – LWR). W problemie tym, zamiast dodawania szumu gaussowskiego (jak w LWE), wprowadza się funkcję zaokrąglającą, utrudniającą odzyskanie sekretnej wiadomości. Co więcej, podobnie jak CRYSTALS-Kyber, tak i CRYSTALS-Kyber, wykorzystuje narzuconą strukturę kraty, co ostatecznie prowadzi do problemu Module-LWR.

Przyszły standard FALCON opiera się na dobrze zbadanym algorytmie NTRU, który w swojej pierwszej wersji, został wprowadzony w 1996 roku [13]. Algorytm jest uznawany za protoplastę szyfrów kratowych. Jest on szybki oraz łatwy w implementacji. O ile wyjściowo, jego działanie można zrozumieć nie odwołując się do krat – bazuje on mianowicie na operacjach wykonywanych na tzw. pierścieniach ilorazowych wielomianów – to już istota jego bezpieczeństwa bezpośrednio wynika z własności krat. Pomimo stosunkowo małych rozmiarów klucza, słabą stroną szyfru FALCON jest brak realizacji stałoczasowej, odpornej na ekstrahowanie klucza prywatnego z pomiaru czasu działania algorytmu. Kolejnym kłopotem jest wymagana szybka arytmetyka o podwójnej precyzji, utrudniająca implementację tego szyfru [14].

W odróżnieniu od wcześniejszych przypadków, szyfr SPHINCS+ nie jest oparty na matematyce krat. Został on wyłoniony przez NIST jako algorytm rezerwowy, na wypadek gdyby czas odsłonił nieznane dotychczas podatności szyfrów kratowych. A o tym, że faktycznie może się tak zdarzyć, piszę w dalszej części tego tekstu. Póki co, należy jeszcze dodać, że algorytm SPHINCS+ opiera się na dobrze poznanych i silnych kryptograficznie funkcjach skrótu. Idea wykorzystania funkcji skrótu do składania podpisu, została zaproponowane jeszcze w 1975 roku przez amerykańskiego informatyka Leslie Lamporta. W podejściu tym, klucz prywatny jest zużywany do tworzenia kluczy publicznych, poprzez utworzenie funkcji skrótu z części jego bitów. W konsekwencji, praktyczne zastosowania algorytmów podpisu elektronicznego opartych na funkcjach skrótu wymagają zastosowania dużych kluczy, których rozmiary mogą sięgać kilkudziesięciu kilobajtów. Jest to główny mankament tego podejścia. Poza tym, algorytmy te są zarówno bezpieczne, jak i łatwe w implementacji, gdyż opierają się na dobrze przetestowanych i szeroko wdrożonych rozwiązaniach.

Kontrowersje na finiszu

4 kwietnia bieżącego roku, na 3 miesiące przed ogłoszeniem wyników przez NIST, kryptolodzy z prestiżowego Center of Encryption and Information Security (MATZOV), będącego głównym zapleczem kryptologicznym Izraela, zatrzęśli światem kryptologicznym, a przynajmniej jego postkwantową częścią, publikując swój raport, będący wynikiem przeprowadzonego audytu głównych kandydatów do standardu kryptografii postkwantowej. Raport zatytułowany jest “Report on the Security of LWE: Improved Dual Lattice Attack” i skupia uwagę na podejściach opartych na LWE oraz LWR [15]. Najlepiej znane techniki kryptoanalityczne dla tego typu szyfrów opierają się na tak zwanych primal lattice attacks oraz dual lattice attacks. Żaden z tych ataków nie uważano jednach dotychczas za realne zagrożenie. W szczególności, drugie z tych podejść wydawało się niepraktyczne. W raporcie MATZOVa wykazno jednak, że istnieje możliwość ulepszenia drugiego typu ataku, co wyraźnie osłabia bezpieczeństwo algorytmów CRYSTALS-Kyber, SABER oraz CRYSTALS-Dilithium. W szczególności, wykazano, że nowa technika kryptoanalityczna osłabia bezpieczeństwo tych algorytmów nieznacznie poniżej progów określonych w wymaganiach konkursowych NIST. Czytelnika zainteresowanego dyskusją środowiska kryptologów postkwantowych na temat raportu MATZOVa odsyłam do referencji [16].

Wyniki raportu MATZOVa ostatecznie nie przeszkodziły w wyborze algorytmów CRYSTALS-Kyber i CRYSTALS-Dilithium. Mogły mieć jednak wpływ na odrzucenie z rywalizacji algorytmu SABER. Warto w tym miejscu wyjaśnić, że nie dysponujemy dowodem bezpieczeństwa algorytmów CRYSTALS-Kyber i CRYSTALS-Dilithium. Stwierdzenia dotyczące ich bezpieczeństwa wiążą się z tzw. problemem najkrótszego wektora (ang. Shortest Vector Problem – SVP) na kratach [17]. Jak dowiedziono, SVP jest tzw. problemem NP-trudnym, co uniemożliwia jego efektywne rozwiązywania (w czasie wielomianowym). Problemy LWE i LWR można zredukować do przybliżonego problemu SVR. Nie istnieje jednakże dowód tego, że są to problemy NP-trudne. Od strony bezpieczeństwa, uzasadnienie zastosowania tych problemów w kryptografii postkwantowej opiera się więc na braku znajomości algorytmów które pozwalałyby na efektywne rozwiązywanie tych problemów. Nie można jednak zagwarantować tego, że takie algorytmy nie zostaną odkryte w przyszłości.

Czwarta runda

Proces wyboru postkwantowych standardów kryptograficznych przez NIST, nie zakończył się wraz z wyborem omówionych powyżej czterech algorytmów. Gra toczy się dalej i do czwartej rundy ewaluacyjnej zakwalifikowano cztery kolejne algorytmy, które wciąż mają szansę dołączyć do grona postkantowych standardów NIST. Mowa to szyfrach: BIKE [18], Classic McEliece [19], HQC [20], oraz SIKE [21].

Zacznijmy od przedstawienia drugiego z listy, szyfru Classic McEliece, należącego do klasy szyfrów asymetrycznych opartych na kodach korekcyjnych. Kody takie, poprzez pewną nadmiarową informację, pozwalają na korekcję błędów powstałych w trakcie transmisji lub magazynowania informacji. W 1978 roku Robert McEliece pokazał, że kody korekcyjne mogą być również użyte do realizacji, wprowadzonej kilka lat wcześniej, kryptografii asymetrycznej. Pomimo, ponad czterdziestu lat prób i dogłębnego poznania algorytmu, nie udało się przeprowadzić na niego skutecznego ataku. Słabą stroną algorytmu jest duży rozmiar klucza – nawet rzędu megabajta. Algorytm BIKE (Bit Flipping Key Encapsulation) jest, podobnie jak Classic McEliece, również oparty na kodach korekcyjnych. W tym przypadku wykorzystywany jest tzw. kod QC-MDPC (Quasi-Cyclic Moderate Density Parity-Check). Także algorytm HQC (Hamming Quasi-Cyclic) opiera swoje działanie na kodach korekcyjnych.

Ostatni z szyfrów, SIKE (Supersinguar Isogeny Key Encapsulation), wykorzystuje zupełnie inne podejście niż trzy poprzednie. A mianowicie, angażuje on morfizmy (pewne powiązania) pomiędzy krzywymi eliptycznymi do budowy kryptosystemu asymetrycznego. Podejście to, pomimo, że jest wymagające obliczeniowo, uważne było do niedawna za bezpieczne i charakteryzujące się wyjątkowo krótkim kluczem. Prognozowało to wykorzystaniem algorytmu SIKE, w obszarach zastosowań specjalnego przeznaczenia. Ku wielkiemu zaskoczeniu społeczności kryptologicznej, 30 lipca tego roku dwójka kryptologów z Uniwersytetu w Leuven, opublikowała receptę skutecznego ataku na algorytm SIKE [22,23]. Wykorzystując nieznaną wcześniej podatność, udało się, wykorzystując komputer osobisty, odzyskać klucz prywatny. Algorytm ten, pomimo wiązanych z nim nadziejami i już testowanych implementacji, nie stanie się z pewnością standardem postkwantowym. Wciąż możliwe jest jednak, że podatność która umożliwiła atak zostanie wyeliminowana w dalszych wcieleniach tego algorytmu.

Co z kryptografią symetryczną?

Współczesne algorytmy kryptografii symetrycznej są uważane za niepodatne na ataki kwantowe. Ich poziom bezpieczeństwa jest zasadniczo określany ze względu na atak siłowy, którego możliwość realizacji determinuje rozmiar przestrzeni klucza. W przypadku algorytmu AES z kluczem 256 bitowym, przestrzeń ta ma wymiar N=2²⁵⁶, co jest porównywalne z liczbą atomów w obserwowanym Wszechświecie.

Najlepszą znaną strategią kwantową w przypadku ataków siłowych jest zastosowanie algorytmu Grovera. Algorytm ten umożliwia przeszukanie kwantowej bazy danych, zawierającej N elementów, nie jak to ma miejsce klasycznie w średnio N/2 krokach, a w średnio N^1/2 krokach. Dla algorytmu AES-256 oznacza to redukcję bezpieczeństwa z poziomu 256 do 128, co jest wciąż wartością uznawaną za bezpieczną postkwantowo. Ponadto, należy podkreślić, że już od strony teoretycznej, samo zaimplementowanie algorytmu przeszukiwania Grovera dla danego algorytmu symetrycznego stanowi duże wyzwanie. Trzeba mianowicie zbudować obwód tzw. kwantowej wyroczni (ang. oracle) dla danego algorytmu symetrycznego. To samo w sobie złożone zadanie, wymagające dokonania reprezentacji danego algorytmy symetrycznego w postaci funkcji binarnej i jej dalszej implementacji jako obwodu kwantowego. Stanowi to ogromne wyzwanie już na poziomie algorytmicznym.

Zaproponowany przez Lova K. Grovera w 1996 algorytm był przez wielu uważany za jedyne kwantowe zagrożenie dla algorytmów symetrycznych. Spojrzenie na kryptoanalizę algorytmów symetrycznych uległo jednak zmianie w 2016 roku, wraz opublikowaniem publikacji pt. “Breaking Symmetric Cryptosystems Using Quantum Period Finding” [24]. Pokazano, mianowicie, że możliwe jest osiągnięcie tzw. przyśpieszenia wykładniczego dla kryptoanalizy pewnych algorytmów symetrycznych. Ma to miejsce za sprawą sprytnego zastosowania kwantowego algorytmu Simona, który jest prostszą wersją algorytmu Shora. Algorytm Shora stanowi zaś podstawowe zagrożenie dla algorytmów asymetrycznych.

Zastosowanie algorytmu Simona umożliwia, w szczególności, efektywną kryptoanalizę prostego szyfru blokowego, jakim jest algorytm Even-Mansoura. Choć algorytm Even-Mansoura jest zbyt prosty by mógł znaleźć praktyczne zastosowanie, jego warianty odnaleźć można w szyfrach lekkiej kryptografii. W szczególności, należą do nich algorytmy Chaskey i Elephant, będący jednym z finalistów procesu NIST standaryzacji kryptografii lekkiej.

Należy zauważyć, że kwantowa kryptoanaliza szyfrów symetrczynych staje się coraz bardziej aktywnym polem badań. Kwestii bezpieczeństwa szyfrów symetrycznych nie należy zatem bagatelizować.

Co dalej?

Jak deklaruje NIST, przygotowanie gotowych standardów na podstawie wybranych algorytmów może zająć kolejne dwa lata. W międzyczasie, agencja zachęca do poznawania i testowania wyłonionych algorytmów. NIST sugeruje również powstrzymanie się z praktycznymi implementacjami na tym etapie, gdyż finalna forma standardów może odbiegać od obecnej specyfikacji algorytmów. Czas ten warto niewątpliwie wykorzystać także na poszerzenie świadomości związanej z wdrażaniem kryptografii postkwantowej i przygotowanie się do działań jakie ogłoszenie nowych standardów pociągnie za sobą w nadchodzących latach. Dotyczy to, w szczególności, działów IT firm i instytucji. Uwagę na kwestię nowych standardów powinny niezwłowcznie zwrócić podmioty działające w obszarach infrastruktury sieciowej, magazynowania danych oraz cyberbezpieczeństwa. Należy mieć także świadomość tego, że w przeciągu najbliższych kilku lat, każdy administrator sieciowy będzie musiał zaznajomić się z nowymi postkwantowymi wersjami protokołu TLS (Transport Layer Security) oraz oferowanymi przez nie postkwantowymi zestawami szyfrów (ang. cipher suites).

Czekamy, ponadto, na wyłonienie ewentualnych dodatkowych standardów, które będą mogły pełnić rolę rezerwową i specjalnego przeznaczenia. Z uwagi na przywołane niedawne doniesienia, z gry najprawdopodobniej wypadł już algorytm SIKE.

Nieodległy czas powinien przynieść również zainicjowanie procedury wyboru postkwantowego standardu szyfrowania homomorficznego (ang. homomorphic encryption). Szyfrowania tego typu zyskuje coraz większe zainteresowanie z uwagi na dynamiczny rozwój usług chmurowych. Kryptografia homomorficzna pozwala mianowicie na wykonywanie dowolnych operacji na zaszyfrowanych danych, nie mając do nich bezpośredniego dostępu.

Referencje

[1] D. Bernstein, T. Lange, Post-quantum cryptography, Nature 549, 188–194 (2017).

[2] M. Mosca, Cybersecurity in an era with quantum computers: will we be ready ?, IEEE Security & Privacy, vol. 16, no. 5, pp. 38-41, (2018).

[3] J. Mielczarek, Technologie kwantowe a cyberbezpieczeństwo, CyberDefence24, (2019).

[4] T. R. Johnson, American Cryptology during the Cold War, 1945-1989 (The Complete Declassified Official Four-Volume History of the NSA), Center for Cryptologic History, Washington DC (1995) – Book III, Rozdział 19, Public Cryptography.

[5] https://www.nist.gov/cryptography

[6] https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf

[7] https://blog.cloudflare.com/towards-post-quantum-cryptography-in-tls/

[8] https://www.nist.gov/news-events/news/2022/07/nist-announces-first-four-quantum-resistant-cryptographic-algorithms

[9] https://pq-crystals.org/

[10] https://itwiz.pl/czym-jest-szyfrowanie-kratowe-jak-zabezpiecza-czasach-quantum-computing/

[11] https://falcon-sign.info/

[12] https://sphincs.org/

[13] J. Hoffstein, J. Pipher, J. H. Silverman, NTRU: A ring-based public key cryptosystem. In: Buhler, J.P. (eds) Algorithmic Number Theory. ANTS 1998. Lecture Notes in Computer Science, vol 1423. Springer, Berlin, Heidelberg (1998).

[14] https://blog.cloudflare.com/nist-post-quantum-surprise/

[15] https://zenodo.org/record/6412487#.Yu2VuexBx4I

[16] https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/Fm4cDfsx65s/m/v5odfcpfBwAJ?pli=1

[17] http://www.deltami.edu.pl/temat/matematyka/kryptologia/2017/11/25/Kryptologia_postkwantowa/

[18] https://bikesuite.org/

[19] https://classic.mceliece.org/

[20] http://pqc-hqc.org/

[21] https://sike.org/

[22] W. Castryck and T. Decru, An efficient key recovery attack on SIDH (preliminary version) (2022)

[23] https://arstechnica.com/information-technology/2022/08/sike-once-a-post-quantum-encryption-contender-is-koed-in-nist-smackdown/

[24] M. Kaplan., G. Leurent., A. Leverrier, M. Naya-Plasencia, Breaking Symmetric Cryptosystems Using Quantum Period Finding. In: Robshaw, M., Katz, J. (eds) Advances in Cryptology – CRYPTO 2016. CRYPTO 2016. Lecture Notes in Computer Science, vol 9815. Springer, Berlin, Heidelberg (2016).

Artykuł został opublikowany na portalu Nauka UJ.

Kosmiczny Szyfr

April 23, 2021April 23, 2021 jakub mielczarekLeave a comment

Każdy z nas intuicyjnie wie, że szyfr służy ukrywaniu wiadomości. Jednak większość z nas nie uświadamia sobie, że z szyframi mamy do czynienia cały czas. Bo to dzięki nim, ukrytym nierzadko głęboko w czeluściach internetu, możemy bezpiecznie poruszać się w sieci. To szyfrom zawdzięczamy dostęp do bankowości elektronicznej, możliwość płacenia kartami chipowymi, jak również zachowanie pewnej dozy prywatności podczas rozmów telefonicznych. Dzięki nim odchodzimy też od ręcznych podpisów na rzecz elektronicznych. Przykłady można mnożyć. Jedno jest pewne – swoją ciężką pracę wykonują, pozostając w cieniu.

Czym właściwie jest szyfr? Jeśli popatrzymy na rzecz z czysto matematycznego punktu widzenia, dojdziemy do wniosku, że szyfrowanie jest odwracalnym przekształceniem – funkcją, której argumentem jest tak zwany tekst jawny. Co więcej, operacja ta jest zaprojektowana tak, żeby otrzymany na jej wyjściu szyfrogram przestawał mieć dla nas jakikolwiek sens i sprawiał wrażenie, jak gdyby początkowa informacja całkiem się rozpłynęła.

Informacja oczywiście nie znika, lecz zostaje ukryta w pozornie przypadkowej kompozycji symboli szyfrogramu. Szyfr, czy też inaczej algorytm szyfrujący, jest przepisem, który mówi nam, co należy zrobić, żeby wiadomość ukryła swoje znaczenie. Niezbędnym elementem jest klucz, który umożliwia wielokrotne korzystanie z tego samego szyfru. W przypadku tak zwanych szyfrów symetrycznych klucz pozwala nam zarówno zaszyfrować wiadomość, jak i ją odszyfrować – wykonując algorytm szyfrujący “wstecz”.

Tak na szyfry patrzą lubujący się w abstrakcji matematycy. Fizycy, do których sam się zaliczam, mają odwrotnie – próbują dopasować każdy element matematyki do otaczającego nas świata. Nie inaczej jest w tym przypadku. Zatem okiem fizyka, szyfr to przykład deterministycznej dynamiki chaotycznej.

Prostym przykładem deterministycznego układu chaotycznego jest wahadło podwójne. Źródło

Dynamika chaotyczna to szczególny typ ewolucji układów fizycznych, w którym bardzo szybko zaciera się informacja o ich stanie początkowym. Innymi słowy, ewolucja układu chaotycznego jest bardzo czuła na warunki początkowe – zachowanie to jest powszechnie znane pod nazwą efektu motyla. Stąd też różnica chociażby jednej litery w szyfrowanej wiadomości może prowadzić do kompletnie innego szyfrogramu. Determinizm gwarantuje nam natomiast, że cały proces jest odwracalny i zawsze możemy odtworzyć stan wyjściowy, nawet kiedy wydaje się to zupełnie nieprawdopodobne, bo powrót ten może być bardzo trudny w realizacji. Bo jak sprawić, by rozbite fragmenty filiżanki wskoczyły z powrotem na stół? Jest to jednak teoretycznie dopuszczalne i można próbować przeprowadzić symulację takiego procesu na komputerze.

Jak odzyskać informację z szyfru?

Algorytmy szyfrujące możemy zatem postrzegać jako pewne szczególne deterministyczne układy chaotyczne, które ewoluują zadany stan początkowych (tekst jawny) do stanu końcowego (szyfrogramu). O ile szyfrogram wydaje się być stanem zupełnie nieuporządkowanym, to poprzez zastosowanie na nim operacji odwrotnej (ewolucji wstecz w czasie), możemy odzyskać skrywaną informację. Oczywiście trzeba w tym celu wiedzieć, ile czasu upłynęło pomiędzy początkiem a końcem ewolucji.

Trudno przypuszczać, że stworzone przez ludzi algorytmy szyfrujące odpowiadają układom chaotycznym spotykanym naturalnie w przyrodzie. Aktywność ludzka jest oczywiście również jej częścią, więc wszytko co tworzymy, wliczając algorytmy szyfrujące, z konieczności staje się jej fragmentem. Nie określamy jednakże naszych tworów mianem naturalnych. Nie to jednak będzie nas tu interesować. Ważne, że dynamika chaotyczna jest szeroko rozpowszechnionym rodzajem zachowania w otaczającym nas świecie. Występuje praktycznie wszędzie tam, gdzie mamy do czynienia z dużą ilością cząstek, związanych poprzez nieliniowe oddziaływania. Idąc dalej tym tokiem rozumowania, można dojść do wniosku, że przeważająca część ewolucji wszechświata przybiera formę dynamiki chaotycznej.

Szyfry w naturze

Istnieją oczywiście pewne regularne trendy, takie jak ruchy planet, gwiazd i ewolucja kosmologiczna, gdzie zachowania chaotyczne nie pełnią obecnie głównej roli. Ale i w tych przypadkach nie zawsze tak musiało być. Na podstawie słynnej hipotezy Belinskiego-Khalatnikowa-Lifszyca (BKL), oczekujemy, że ewolucja wczesnego wszechświata była wręcz w nieunikniony sposób chaotyczna. Przypuszczenie to znalazło poparcie w licznych rozważaniach teoretycznych i symulacjach komputerowych. Także na skali atomowej wszechświat ogarnięty jest totalnym chaosem, a jego złożoną ewolucję można postrzegać jako morze atomowego chaosu z pewnymi regularnościami, falującymi na jego powierzchni.

Chaotyczna ewolucja wszechświata w modelu Belinskiego-Khalatnikowa-Lifszyca (BKL). Źródło

Możemy zatem stwierdzić, że nawet szklanka wody mogłaby pełnić funkcję algorytmu szyfrującego. Oczywiście – o ile tylko potrafilibyśmy określić precyzyjnie położenie cząsteczek wody, moglibyśmy za ich pomocą stworzyć maszynę szyfrującą. Wykracza to jednak poza nasze obecne umiejętności, dlatego w praktyce posługujemy się sztucznie wykreowanymi układami chaotycznymi, istniejącymi jedynie w pamięci naszych komputerów. Jednakże pewne układy chaotyczne występujące naturalnie w przyrodzie wykorzystuje się do projektowania algorytmów szyfrujących. Przykładem jest układ Lorenza, który pojawił się w latach sześćdziesiątych ubiegłego wieku jako opis zjawiska konwekcji termicznej w atmosferze. W modelu tym obserwujemy tak zwany dziwny atraktor, którego chaotyczne własności mają zastosowanie w konstrukcji szyfrów symetrycznych.

Skoro jednak szklanka wody albo zjawiska atmosferyczne mogą posłużyć nam jako szyfrator, to czemu nie moglibyśmy za takowy uznać całego znanego nam wszechświata? Ewolucja kosmosu jest w znacznym stopniu zdeterminowana przez zjawiska chaotyczne, związane z procesami nieliniowymi. Na dużych skalach przykładem jest formowanie się, w toku ewolucji wszechświata, zwartych układów grawitacyjnych, takich jak galaktyki i gwiazdy. Jednak na wczesnym etapie jego ewolucji, zgodnie z przewidywaniem hipotezy BKL, chaotyczne zachowanie dotyczyło największych skal. Oprócz tego na małych dystansach mamy całą mnogość nieliniowych zjawisk atomowych.

Wszechświat jako Kosmiczny Szyfrator

Nieliniowości decydują również o sile współczesnych szyfrów. Tak więc nie popełnimy nadużycia, jeśli do celów naszej popularnonaukowej dyskusji potraktujemy wszechświat jako Kosmiczny Szyfrator, który stale ukrywa przed nami informację o swoim stanie początkowym. Chcąc zaś poznać informację, jaką przed nami skrył, musimy przyjąć rolę kryptoanalityków – specjalistów w łamaniu szyfrów.

Pracę, która jest do wykonania, możemy podzielić na dwie kategorie. Pierwsza z nich to poznanie mechanizmu działania Kosmicznego Szyfratora. Druga to znalezienie sekretnego klucza. Potrzebujemy więc najpierw zrozumieć elementarne kroki, jakie wykonuje gigantyczna maszyna szyfrująca, w której żyjemy. Tym zajmuje się fizyka teoretyczna, opisująca mechanikę wszechświata na coraz to głębszym poziomie, sięgając aż do tak zwanej skali Plancka, gdzie pojęcie czasoprzestrzeni wydaje się tracić sens. W przypadku zwykłych szyfrów mechanizm działania algorytmu szyfrującego jest zazwyczaj znany – zgodnie z Zasadą Kerckhoffsa, która mówi, że szyfr powinien pozostawać bezpieczny nawet w przypadku, kiedy znane są jego wszystkie szczegóły. W konsekwencji działanie szyfru jest często upubliczniane po to, by kryptoanalitycy mogli bez ograniczeń wyszukiwać jego potencjale słabości. To, co pozostaje niejawne to sekretny klucz. Planu działania Kosmicznego Szyfratora niestety nikt nam nie udostępnił, więc musimy sami cierpliwie dokonać jego inżynierii odwrotnej.

Nawet bez dogłębnej znajomości działania szyfru, można podjąć próbę odczytania szyfrogramu stworzonego przez Kosmiczny Szyfrator – czyli obecnego stanu wszechświata. Szyfrogram ten zawzięcie rekonstruują astronomowie i kosmolodzy obserwacyjni, tworząc coraz to dokładniejsze mapy rozkładu materii (zarówno tej widzialnej, jak i ciemnej) w obserwowanym Wszechświecie. Bazując na tych danych oraz na fizyce teoretycznej, kosmolodzy-teoretycy starają się modelować dynamikę Wszechświata wstecz. To zaś w naszym kryptograficznym porównaniu, nic innego jak wykonywanie deszyfracji.

Jednak wciąż brakuje nam klucza. W naszej kosmicznej analogii jest nim przede wszystkim czas. To on mówi nam, ile podstawowych kroków szyfrujących trzeba wykonać. A musimy to wiedzieć, jeśli chcemy odzyskać stan początkowy. Nie znając klucza, musimy próbować z różnymi jego wartościami. W tym jednak zarówno krypktoanalitycy, jak i kosmolodzy są zaprawieni. Łamacze szyfrów zaprzęgają superkomputery, które sprawdzają wszystkie dopuszczalne wartości. To mało wyrafinowane podejście określa się mianem ataku siłowego. Igły w stogu siana szukają także kosmolodzy-teoretycy, analizujący ewolucję kosmologiczną dla różnych modeli, różnych wartości parametrów i różnych czasów. Oczywiście z niesłabnącą nadzieją na “szczęśliwy traf”.

Sukces zależy nie tylko od naszej determinacji. Jeśli ewolucja wszechświata nie jest deterministyczna, jej odszyfrowanie jest z góry skazane na niepowodzenie. Wpływ na to mogą mieć procesy kwantowe, leżące u znanych nam podstaw mechaniki wszechświata. O tym jednak przy innej okazji.

Artykuł został opublikowany na portalu Onet.

Hakowanie satelitów

January 8, 2021January 12, 2021 jakub mielczarekLeave a comment

Współczesne, sztuczne satelity Ziemi można postrzegać jako wyspecjalizowane komputery, przetwarzające informacje i komunikujące się ze stacjami naziemnymi lub innymi satelitami. Z tego punktu widzenia, rysuje się ich podobieństwo do serwerów, będących częstym celem cyberataków. Z uwagi na duży koszt budowy i umieszczenia na orbicie satelitów, oraz ich nierzadko strategiczne przeznaczenie, również one mogą stać się celem hakerów. Motywacje do podejmowania prób takich ataków mogą być różne, wliczając chęć przejęcia satelity w celu otrzymania okupu, czy też działania dywersyjne. Sytuacje takie nie są jedynie hipotetyczne, lecz zostały już odnotowane w przeszłości. Publicznie dostępna lista cyber-incydentów z udziałem satelitów jest już całkiem spora a przypuszczalna faktyczna skala tego procederu jest znacznie szersza [1, 2]. Biorąc pod uwagę obecny dynamiczny rozwój technologii satelitarnych, w szczególności, związany z budową konstelacji satelitarnych dostarczających internet, spodziewać się można narastania tego problemu. Dlatego też, warto temu zagadnieniu poświęcić należytą uwagę. Niniejszy tekst ma na celu zarysowanie zagadnienia cyberbezpieczeństwa rozwiązań satelitarnych i sprowokowanie Czytelnika do dalszych, pogłębionych, studiów w tym obszarze.

Mogłoby się wydawać, że uzyskanie nieautoryzowanego dostępu do systemu operacyjnego satelity, krążącego na wysokości kilkuset kilometrów nad powierzchnią Ziemi, jest zadaniem praktycznie niewykonalnym. Przekonanie takie ma swoje uzasadnienie w tym, iż informacje związane zarówno z systemami samych satelitów, jak i ze sposobami ich komunikacji, zazwyczaj pozostają niedostępne. Jest to klasyczny przykład tzw. security by obscurity (bezpieczeństwa przez niejawność). To, z jednej strony, ma na celu zniechęcenie do podejmowania jakichkolwiek prób ataków. Z drugiej jednak strony, podejście takie może uśpić czujność osób stojących na straży bezpieczeństwa systemów satelitarnych. Biorąc zaś pod uwagę dynamikę wzrostu ilości umieszczanych na orbicie okołoziemskiej satelitów, możliwości wystąpienia błędów i luk w systemach zabezpieczeń nie można wykluczyć. Chętnych do lokalizacji tych podatności i ich późniejszego wykorzystania może być wielu.

Jednym ze sposobów wykrywania słabości zabezpieczeń jest przekonanie tak zwanych “etycznych hakerów” do tego by zechcieli ich poszukać – inaczej mówiąc, włamać się do danego satelity. Działania takie mogą przyjąć formę otwartego konkursu z motywacją (oprócz satysfakcji) w postaci pokaźnej nagrody pieniężnej. W maju ubiegłego roku konkurs taki, pod nazwą Space Security Challenge 2020: HACK-A-SAT, został zorganizowany przez Siły Powietrzne Stanów Zjednoczonych (United States Air force – USAF), wraz z Służbą Obrony Cyfrowej (Defense Digital Service – DDS). Celem rywalizacji było m.in. przywrócenie kontroli nad satelitą, na który przeprowadzono symulowany cyberatak. W konkursie wykorzystano eksperymentalne konstrukcje satelitarne, znajdujące się na Ziemi. Jednakże, najepszym drużynom, udostępniony został również w pełni profesjonalny satelita orbitujący Ziemię. Do konkursu przystąpiło ponad tysiąc drużyn z całego świata. Tym bardziej, godne uznania jest zajęcie drugiego miejsca w tym konkursie przez drużynę “Poland Can Into Space” z Polski.

Należy podkreślić, że przeprowadzenie ataków na systemy satelitarne nie musi wiązać się z użyciem kosztownego sprzętu, co zaś znacząco rozszerza grono potencjalnych atakujących. W szczególności, hakerzy nie muszą być wyposażeni w zaawansowane urządzenia telekomunikacyjne. Celem ataków mogą być bowiem nie koniecznie bezpośrednio same satelity, lecz autoryzowane stacje naziemne, za pośrednictwem których są one kontrolowane. Obejście zabezpieczeń takich stacji może pozwolić na nawiązanie pożądanego połączenia z komputerem satelity i wpłynięcie na jego funkcjonowanie.

W ten sposób, atakujący mogą osiągnąć jeden z wielu możliwych celów, takich jaki np.:

Zainfekowanie komputera satelity złośliwym oprogramowaniem, co może mieć na celu zaburzenie jego pracy. Na przykład, powodując zafałszowanie informacji i wprowadzanie operatora satelity w błąd (również, w sposób trudny do wykrycia).
Zebranie wrażliwych lub cennych informacji. Na przykład, pozyskiwanie danych obrazowych lub sygnałowych.
Szantaż, czy też atak typu ransomware, mający na celu otrzymanie okupu za przywrócenie satelity do działania. Jest to szczególnie kusząca możliwość, z uwagi na typowo ogromne koszty rozwiązań satelitarnych.

Ataki na systemy satelitarne, wykorzystujące podatności stacji naziemnych, są jednak zasadniczo trudne do przeprowadzenia. Wynika to z zastosowania silnych zabezpieczeń w tego typu obiektach. W takiej sytuacji, łatwiejszym celem może okazać się próba ataku bezpośredniego. Uzasadnione jest to tym, że szyfrowanie kanału komunikacji pomiędzy satelitą a stacją naziemną może być stosunkowo słabe. Związane to jest z ograniczeniami na przepustowość wykorzystywanych łączy radiowych oraz kosztem energetycznym transmisji, co zaś wyklucza stosowanie silnych algorytmów szyfrujących. Przykładem tego jest chociażby wykazana możliwość kryptoanalizy algorytmów GMR-1 i GMR-2, stosowanych w telefonii satelitarnej [3]. Ponadto, ograniczenia na rozwiązania kryptograficzne są narzucane przez rozmiary pakietów danych wymienianych radiowo w trakcie przelotu satelity nad stacją naziemną (co nie dotyczy satelitów geostacjonarnych). Te więzy czasowe, wymuszają stosowanie kompromisowych rozwiązań, biorąc z jednej strony ilość przesyłanych danych użytkowych a z drugiej bezpieczeństwo tych danych.

Wykorzystanie podatności otwierających się poprzez bezpośrednie nawiązanie łączności z satelitą urealnione jest przez dostępność i stosunkowo niski koszt niezbędnego sprzętu. W wielu przypadkach, wystarczy do tego celu antena paraboliczna o średnicy około dwóch metrów i układ nadawczo-odbiorczy, zamykające się w kwocie kilkunastu tysięcy złotych. Już takie wyposażenie może pozwolić na podszycie się pod autoryzowaną stację nadawczą (tzw. spoofing) i nawiązanie komunikacji z satelitą. A stąd już krok do zainfekowania systemu operacyjnego satelity, lub przejęcia nad nim kontroli.

Przedmiotem zainteresowania hakerów mogą być także same dane przesyłane z satelitów. Odbieranie takich danych nie wymaga zaś nawiązania dwukierunkowej komunikacji z satelitą. Wystarczyć więc może nawet zwykły tuner i antena satelitarna. Większość z przesyłanych na ziemię danych jest jednak zaszyfrowana. Dotyczy to również telewizji satelitarnej. Z kosmosu trafia do nas jednak cała masa, innych, dużo bardziej wrażliwych danych, takich jak np. rozmowy prowadzone za pomocą telefonów satelitarnych, czy też dane przemysłowe. Za sprawą powstającego globalnego internetu satelitarnego, danych tych będzie znacząco przybywać. To też rodzi obawy, że będą one mogły zostać przechwycone i bezprawnie wykorzystywane (jeśli nie zostaną wystarczająco silnie zabezpieczone). Przykładu takiej możliwości dostarcza wykazana niedawno podatność, zainstalowanych na statkach, satelitarnych systemów VSAT (Very Small Aperture Terminals) [4].

Na styku cyberataków i ataków fizycznych znajdują się również ataki typu DoS (Denial-of-Service), polegające na zablokowaniu danej usługi, na przykład poprzez zawieszenie witryny internetowej. Stosowaną często wersją takiego ataku jest DDoS (Distributed Denial-of-Service), w którym wykorzystuje się masowo zainfekowane komputery do połączenia z danym serwerem w celu jego przeciążenia i w konsekwencji zawieszenia.

Za satelitarny odpowiednik ataku DoS możemy uznać zakłócenie pracy satelity (tzw. jamming). Zakłócany może być zarówno tzw. downlink (komunikacja z satelity na ziemię) oraz tzw. uplink (komunikacja z ziemi do satelity). Zakłócenie radioelektroniczne można przeprowadzić za pomocą naziemnej stacji radiowej, lub też dedykowanego do tego celu satelity. O ile ta druga możliwość dana jest nielicznym, to już ataki typu DoS z powierzchni Ziemi można realizować w oparciu o stosunkowo nieduże zasoby sprzętowe.

Jednymi z najpowszechniejszych przypadków ataków na satelitarną usługę w transmisji downlink są zakłócenia pracy systemów nawigacji satelitarnej (GNSS), takich jak GPS czy Galileo, oraz telewizji satelitarnej. Zakłócenia systemów GNSS mogą uniemożliwić z korzystania z nawigacji satelitarnej w danym obszarze jego stosowania. Ataki tego mają miejsce dosyć często, o czym świadczą udokumentowane przypadki [2]. Licznych przykładów takich działań dostarcza raport “Above Us Only Stars – Exposing GPS Spoofing in Russia and Syria,” (pdf) przygotowany przez ośrodek C4ADS. Raport przytacza również przykładów spoofingu GPS (czyli podszywania się pod system GPS), co może być działaniem jeszcze bardziej niebezpiecznym, gdyż nieświadomy użytkownik może zostać wprowadzony w błąd a jego pojazd (samochód, statek, samolot) może być skierowany np. na kurs kolizyjny z przeszkodą. Sposobem radzenia sobie z takimi sytuacjami jest m.in. kryptograficzne uwierzytelnienie źródeł sygnału.

Warto dodać, że z uwagi na dominujące znaczenie transmisji internetowej, zakłócenie telewizji satelitarnej traci obecnie na znaczeniu. Działania takie miały jednak miejsce w przeszłości. Udokumentowanym incydentem tego typu było np. zakłócenie kurdyjskiego kanału satelitarnego MED-TV w 1995 roku [2].

Podsumowując, cyberataki na systemy satelitarne są realnym zagrożeniem, a ich znaczenie będzie wzrastało, wraz z rozwojem internetu satelitarnego (dostarczanego z niskiej orbity okołoziemskiej) oraz innych usług satelitarnych. Na szczególną uwagę i monitorowanie od strony cyberbezpieczeństwa zasługuje tu konstelacja Starlink, budowana obecnie przez firmę SpaceX.

Konstelacji satelitów Starlink (stan na styczeń 2021). Interaktywna mapa pod adresem: https://satellitemap.space/

Jednym z obiecujących kierunków, który może zmniejszyć ryzyko bezpośrednich ataków na satelity, jest zastąpienie komunikacji radiowej, łącznością laserową. Łączność laserowa wdrażana jest już m.in. w komunikacji międzysatelitarnej w konstelacji Starlink (ale nie w komunikacji ze stacjami naziemnymi). Wykorzystanie satelitarnych łączy optycznych jest obecnie bardzo ważnym kierunkiem rozwoju. Wynika to zarówno, z dużo większych przepustowości, jak i mniejszych strat energetycznych, w przypadku łączy laserowych. Zaletą, w stosunku do komunikacji radiowej, jest także dużo mniejsza podatność na przechwycenie komunikacji, wynikająca z małego kąta rozbieżności wiązki laserowej. Własność ta stanowi zasadniczą trudność przy próbach cyberataków na systemy satelitarne. Równocześnie, wysokie przepustowości łączy optycznych pozwalają na stosowanie silnych algorytmów kryptograficznych, w tym algorytmów kryptografii postkwantowej. Łącza optyczne nie są jednak wolne od słabości. Największym ich wrogiem są czynniki atmosferyczne, takie jak chmury, które są zdolne do tego by skutecznie przeprowadzić atak DoS.

Bibliografia

D. Housen-Couriel, Cybersecurity threats to satellite communications: Towards a typology of state actor responses, Acta Astronautica 128, 409-415 (2016).
A. Ali.Zare Hudaib, Satellite Network Hacking & Security Analysis, International Journal of Computer Science and Security (IJCSS) 10, Issue (1), 8-55 (2016).
B. Driessen, R. Hund, C. Willems, C. Paar, & T. Holz, Don’t Trust Satellite Phones: A Security Analysis of Two Satphone Standards, IEEE Symposium on Security and Privacy, 128-142 (2012).
J. Pavur, I. Martinovic, M. Strohmeier, V. Lenders, & D. Moser, A tale of sea and sky: On the security of maritime VSAT communications, IEEE, 1006–1022 (2020).

Artykuł został opublikowany na portalu Polish Brief.

Rozpinanie kwantowej sieci

December 24, 2020March 1, 2021 jakub mielczarekLeave a comment

Pod koniec lat sześćdziesiątych ubiegłego stulecia w Stanach Zjednoczonych zaczął powstawać ARPANET – prekursor dzisiejszego Internetu. Zamysłem stojącym za stworzeniem pierwszej rozległej sieci komputerowej była decentralizacja zasobów obliczeniowych związanych z kontrolowaniem amerykańskiego arsenału nuklearnego. W czasie zimnej wojny, kiedy ryzyko konfliktu nuklearnego brano bardzo poważnie, konieczne stało się uchronienie przed sytuacją w której jeden precyzyjny atak nieprzyjaciela mógł unicestwić działanie całego systemu i w konsekwencji uniemożliwić kontratak. Rozwiązaniem była decentralizacja, która przyjęła formę, rozpiętej na terenie USA, sieci teleinformatycznej.

Schemat sieci ARPANET z 1977 roku. Warto zwrócić uwagę na istniejące już w tamtym czasie łącza satelitarne z węzłem na Hawajach oraz z centrum detekcji trzęsień Ziemi oraz wybuchów jądrowych NORSAR, zlokalizowanym w Norwegii. Źródło

Pomimo, że motywacja projektu związana była ściśle z obronnością, zdecydowano się na włączenie do sieci również segment cywilny, łączący wiodące amerykańskie uczelnie oraz instytucje naukowe. Dzięki temu, w prace nad rozwojem sieci mogła zaangażować się społeczność akademicka, która wykorzystywała ARPANET m.in. do prowadzenia zdalnej korespondencji oraz do współdzielenia zasobów obliczeniowych. Ta otwarta strona projektu dała również impuls do snucia wizji dotyczących możliwych przyszłych zastosowań sieci komputerowych, wykraczających daleko poza domenę militarną, rządową i naukową.

Jedną z osób zafascynowanych koncepcją publicznego wykorzystania sieci komputerowych był absolwent MIT, niezależny spec od bezpieczeństwa komputerowego Whitfield Diffie. Diffie doskonale zdawał sobie sprawę z tego, że urzeczywistnienie idei publicznej sieci wymagać będzie wcześniejszego rozwiązania dobrze znanego problemu wymiany klucza. A to dlatego, że tylko dzięki efektywnej metodzie wymiany sekretnego klucza, możliwe będzie wdrożenie rozwiązań kryptograficznych, gwarantujących bezpieczeństwo komunikacji w sieci. Problem ten, którego znaczenie miało swoje szerokie konsekwencje dla przebiegu II wojny światowej, uważano jednak za niemożliwy do rozwiązania. Nie zniechęciło to jednak upartego Diffi’ego do własnych badań i poszukiwań. I tak, w 1976 roku, razem z Martinem Hellman’em oraz Ralphem Markle, zaproponował On genialne rozwiązanie w postaci kryptografii asymetrycznej (znanej również jako kryptografia z kluczem publicznym), opartej nie na jednym, lecz na dwóch kluczach – sekretnym oraz publicznym.

Rok później powstał, najpopularniejszy algorytm kryptografii asymetrycznej, słynny RSA. Tak oficjalnie narodziła się kryptografia z kluczem publicznym, bez której trudno byłoby sobie wyobrazić późniejszy rozwój Internetu. Należy w tym miejscu jednak dodać, że kryptografia asymetryczna miała również swoją alternatywną historię narodzin, związaną z brytyjską Centralą Łączności Rządowej (ang. GCHQ – Government Communications Headquarters). Instytucja ta, skupiająca elitę brytyjskiej kryptologii, została utworzona po II wojnie światowej na bazie ośrodka w Bletchley Park (w którym złamano Enigmę). To właśnie w GCHQ, w 1969 roku, znany z nieszablonowego myślenia, inżynier i kryptolog James Ellis wpadł na podobny jak Diffie, Hellman i Markle pomysł. Jego ideę rozwiną zaś Clifford Cocks, matematyk który, w 1973 roku, tuż po wstąpieniu w szeregi GCHQ, zaproponował algorytm “odkryty” kilka lat później przez Ronalda Rivesta, Adi Shamira i Leonarda Adelmana (RSA). O Ellisie i Cocksie świat usłyszał jednak dopiero w drugiej połowie lat 90-tych, po częściowym odtajnieniu ich pracy w GCHQ. W tym czasie, algorytm RSA był już wdrożony na globalną skalę a jego oficjalni Twórcy odnieśli dzięki swojemu odkryciu ogromy sukces komercyjny.

Kiedy kryptografia asymetryczna święciła swoje triumfy, w jej piedestale pojawiła się jednak rysa. W 1994 roku, pracujący dla Bell Labs, amerykański matematyk Peter Shor pokazał, że bezpieczeństwo algorytmów kryptografii asymetrycznej, takich jak RSA, można podważyć z wykorzystaniem komputerów kwantowych. To zaś zrodziło obawy dotyczące możliwych przyszłych ataków kwantowych na kryptografię klucza publicznego. Pewne rozwiązanie tego problemu czekało już jednak na półce, a do odparcia kwantowego zagrożenia, wykorzystywało ten sam, kwantowy, oręż. Chodzi mianowicie o kwantową dystrybucję klucza (ang. Quantum Key Distribution – QKD), metodę zaproponowaną w 1984 roku przez Charles’a Bennett’a i Gilles’a Brassard’a. Warto dodać, że pomysł ten był rozwinięciem idei kwantowego pieniądza, która pojawiła się jeszcze na przełomie lat sześćdziesiątych i siedemdziesiątych za sprawą Stephena Weinera.

Kwantowa dystrybucja klucza umożliwia wymianę sekretnego klucza, wykorzystując stany polaryzacji pojedynczych kwantów światła – fotonów. Te zaś, co wynika z zasad rządzących mikroświatem, nie są skłonne do dzielenia się informacją, którą w sobie niosą. W szczególności, nie jest możliwe wykonanie idealnej kopii (klonu) takiego fotonu, jeśli jego stan nie jej nam wcześniej znany. Algorytmy QKD, takie jak zaproponowany przez Bennett’a i Brassard’a BB84, zaprzęgają tą własność do tego by ukryć przed światem wymieniane bity sekretnego klucza. Obrazowo rzecz ujmując, pomiędzy stronami wymieniającymi sekretny klucz powstaje “kwantowy tunel”, a każda próba jego nieuprawnionej eksploracji kończy się jego zasypaniem. Co więcej, bezpieczeństwo takiego rozwiązania możemy ściśle udowodnić na gruncie mechaniki kwantowej i teorii informacji.

Pomimo niezwykłej atrakcyjności QKD, jako wręcz idealnego sposobu wymiany sekretnego klucza, trudności natury technicznej przez wiele lat skutecznie utrudniały szerokie wdrożenie tego rozwiązania. Sytuacja ta uległa w ostatnim dziesięcioleciu znaczącej poprawie, a obecnie możemy mówić wręcz o rozkwicie technologii QKD. Pozostającym problemem jest wciąż dystans na który kwantowa dystrybucja klucza może zostać pomyślnie przeprowadzona, co jest skutkiem tłumienia fotonów w ośrodku optycznym. W konsekwencji, za pomocą światłowodu, QKD możemy skutecznie realizować na odległościach nie większych niż około 100 km. Dopuszczalnym, lecz zarazem bardzo kosztownym, sposobem ominięcia tej trudności jest wykorzystanie przestrzeni kosmicznej. Dzięki dużo słabszemu tłumieniu fotonów w powietrzu i w próżni, kwantowa dystrybucja klucza może być realizowana na znacznie dłuższych odległościach, co zostało potwierdzone dzięki eksperymentom z wykorzystaniem chińskiego satelity Micius. Alternatywnego rozwiązania dostarczają tak zwane powielacze kwantowe. Wymagają one jednak dalszych prac badawczo-rozwojowych.

Bez ich pomocy, już teraz, zaczynają powstawać pierwsze naziemne sieci realizujące QKD. Nie stanowią one jednak zupełnie odrębnych systemów. Tworzone są równolegle do konwencjonalnych sieci teleinformatycznych, dostarczając im sekretnych kluczy, niezbędnych do prowadzenia bezpiecznej wymiany informacji. A to zapewniane jest już przez bardzo silne szyfry symetryczne, które pozostaną nietknięte, nawet w epoce komputerów kwantowych.

Możemy zatem powiedzieć, że na naszych oczach rodzi się, zupełnie nowy typ (kwantowej) sieci. Sytuacja ta nasuwa skojarzenia z ARPANETem. Podobnie jak ARPANET, sieci kwantowe powstają w odpowiedzi na zagrożenia swoich czasów. W latach siedemdziesiątych ubiegłego stulecia, za największe niebezpieczeństwo uważano atak jądrowy. We współczesnym, coraz bardziej cyfrowym, świecie globalne zagrożenia nie tkwią już jednak tylko w silosach lecz także w serwerach. To w cyberprzestrzeni rozgrywa się wiele ze współczesnych konfliktów i to groźba rozległych ataków w cyberprzestrzeni staje się źródłem największych obaw. Dlatego też tak ważne jest bezpieczeństwo wymiany informacji w sieciach teleinformatycznych, której to fundamentem jest kryptografia. Kryptografia kwantowa, wcielona poprzez QKD, jest sposobem na wyniesienie cyberbezpieczeństwa na zupełnie nowy poziom. Podobnie jak w przypadku ARPANETu, tak i wdrożenie jego współczesnego odpowiednika – nazwijmy go QUANTUMNETem – dotyczyć będzie jednak wyjściowo jedynie zasobów o znaczeniu krytycznym. Przez co należy rozumieć zarówno najbardziej wrażliwe dane, jak i połączoną z siecią teleinformatyczną infrastrukturę o szczególnym znaczeniu (np. elektrownie i banki). Jednakże, już teraz, podobnie jak niegdyś Whitfield Diffie, możemy rozmyślać o korzyściach jakie mogłoby płynąć z upublicznienia sieci, w tym przypadku – sieci kwantowej. Czy zatem współczesne pierwsze sieci realizujące kwantową dystrybucję klucza staną się zalążkiem przyszłego Internetu kwantowego?

Dywagacje na ten, skądinąd fascynujący, temat pozostawmy na inną okazję. Teraz natomiast przyjrzyjmy się wybranym, obecnie rozpinanym, sieciom kwantowym. Do najważniejszych z nich należy bez wątpienia chińska sieć, o długości około 2000 km, łącząca miasta Pekin, Jinan, Hefei i Szanghaj. Sieć ta jest pierwszym etapem powstającej chińskiej kwantowej sieci szkieletowej. W jej skład wchodzą również lokalne kwantowe sieci miejskie.

Schemat chińskiej kwantowej sieci łączącej Pekin i Szanghaj. Żródło: [2]

Jak widać na rysunku powyżej, sieć ta złożona jest z szeregu segmentów. Wynika to ze wspomnianego ograniczenia na dystans na jaki można prowadzić QKD za pośrednictwem światłowodu. Każda z pomarańczowych kropek na schemacie to tak zwany zaufany węzeł, który podaje sekretny klucz przez kolejny segment sieci. Węzły te są klasyczne a informacja przez nie przekazywana pozostaje do dyspozycji operatora sieci. To, w naturalny sposób, rodzi obawy co do bezpieczeństwa takiego systemu i możliwości nieautoryzowanego dostępu do przekazywanej informacji. Temat ten jest dużo bardziej złożony i wykracza poza ramy tego tekstu. Dodam jedynie, że wprowadzenie wspomnianych powyżej powielaczy kwantowych powinno umożliwić zastąpienie zaufanych węzłów węzłami kwantowymi, zapewniającymi wyższe bezpieczeństwo przekazywanej informacji.

Ambicje Chin, wyrastających na światowego lidera technologii kwantowych, pozostają niezaspokojone i już teraz prowadzone są działania w kierunku rozszerzenia “kwantowej autostrady,” pokrywając wszystkie chińskie prowincje i regiony autonomiczne. Wraz z siecią naziemną ma powstać także komplementarny segment satelitarny, który jest już z powodzeniem testowany. Umożliwi on realizację QKD na dużych dystansach, częściowo rozwiązując problem zaufanych węzłów. Plan szkieletu tej sieci można znaleźć poniżej.

Planowana chińska szkieletowa sieć kwantowa. Niebieskie linki odpowiadają zbudowanym już fragmentom sieci. Żródło: [3]

Zarówno Stany Zjednoczone, jak i Unia Europejska (czy też inne rozwinięte technologicznie państwa) nie pozostają bierne i również prowadzą prace nad budową własnych kwantowych sieci. Na naszym europejskim podwórku, na szczególną uwagę zasługuje eksperymentalna kwantowa sieć miejska zbudowana w Madrycie. Sieć ta powstała we współpracy naukowców z Politechniki madryckiej oraz firm Telefonica i Huawei. Dostawcą systemów do kwantowej dystrubucji klucza jest tutaj niemiecki oddział firmy Huawei, natomiast Telefonica do celu projektu udostępnia swoje zasoby sieciowe. Madrycka sieć, której schemat przedstawiono poniżej, zawiera obecnie 13 połączeń i należy do najbardziej rozbudowanych tego typu sieci na świecie.

Schemat kwantowej sieci powstałej w Madrycie. Źródło

Kolejną ważną europejską inicjatywą związaną z QKD jest projekt OpenQKD. W jego ramach, testowane są lokalne komponenty sieci kwantowych oraz ich możliwe obszary zastosowań praktycznych. Sieć madrycka jest jedną z kilku eksperymentalnych sieci wchodzących w skład OpenQKD. Warto dodać, że w projekcie tym uczestniczy również Poznańskie Centrum Superkomputerowo-Sieciowe. Technologia QKD, w kontekście budowy sieci kwantowych, rozwijana jest również w projekcie CiViQ, finansowanym w ramach europejskiej inicjatywy Quantum Flagship.

Jednakże, największe nadzieje na utworzenie rozległej paneuropejskiej kwantowej sieci wiążą się z inicjatywą EuroQCI, koordynowaną przez Komisję Europejską. Zakłada ona, że do końca bieżącej dekady ma powstać w Europie rozbudowana kwantowa sieć, przeznaczona wyjściowo do użytku administracji europejskiej oraz biznesu. W lipcu 2019 roku do inicjatywy Euro QCI włączyła się również Polska. Podobnie jak w przypadku sieci chińskiej, planowany jest również komponent satelitarny, co wiąże się z zaangażowaniem w ten projekt Europejskiej Agencji Kosmicznej.

EuroQCI ma zapewnić Europie wejście na nowy poziom bezpieczeństwa cybernetycznego. Początkowo jednak, również opierać się będzie na zaufanych węzłach klasycznych, co pozostawia pewien niedosyt. Mianowicie, o ile zastosowanie QKD eliminuje możliwość przechwytu informacji na łączach optycznych, obawa związana z przejęciem informacji na węzłach pozostaje realna.

Kryptografia asymetryczna, umożliwiająca realizację tzw. szyfrowania end-to-end daje możliwość uzgodnienia sekretnego klucza nawet przez, powszechnie dostępny, kanał publiczny (stosując tzw. protokół Diffiego-Hellmana). Podejście to jest jednak opiera swoje bezpieczeństwo na złożoności obliczeniowej pewnych problemów matematycznych (podobnie jak RSA). To, z jednej strony, rodzi obawę pod kątem kryptoanalizy kwantowej a z drugiej nie daje nam gwarancji bezpieczeństwa nawet w przypadku ataków klasycznych. O ile nie dysponujemy skutecznymi algorytmami ataków na takie szyfry, nie posiadamy również dowodu na to, że takowe nie istnieją i nie zostaną w bliższej lub dalszej przyszłości odkryte i co gorsza zastosowane.

Implementując sieci kwantowe zmierzamy do odejścia od kryptografii asymetrycznej. Jednakże, w kontekście problemu klasycznych węzłów, konieczne może okazać się “wzmocnienie” takich sieci, uniemożliwiając operatorowi sieci dostęp do wymienianych informacji. Stosowanie współczesnych algorytmów asymetrycznych jest w tym kontekście nieuzasadnione. Nadzieję na wdrożenie takiego rozwiązania dają jednak rozwijane obecnie algorytmy kryptografii postkwantowej, takie jak np. algorytmy oparte na kratach.

Prawdziwie bezwarunkowo bezpiecznego rozwiązania może dostarczyć jednak jedynie zastąpienie węzłów klasycznych, węzłami kwantowymi, urzeczywistniając w pełni koncepcję sieci kwantowych. Teoretycznie, sieci takie mogą zagwarantować absolutną prywatność jej użytkownikom. Trudno być jednak przekonanym co do tego, że globalna kwantowa sieć, w takiej formie, kiedykolwiek powstanie. Wynika to nie z wyzwań technicznych, lecz z dobrze znanej kwestii znalezienia kompromisu pomiędzy prywatnością a bezpieczeństwem. Mianowicie, istotne znaczenie ma nie tylko uniknięcie nieuprawnionego przechwycenia naszej komunikacji w sieci ale również zachowanie odpowiednich standardów aktywności w samej sieci. Całkowicie niepodatna na kontrolę kwantowa sieć mogłaby stać nie tyle przestrzenią uszanowania naszej prywatności i swobody działań, co miejscem ekspresji bezkarności i działalności przestępczej. Dlatego też, nawet jeśli Internet kwantowy stanie się faktem, niezbędne będzie wcześniejsze rozwiązanie problemu tego jak sprawić by nie przeistoczył się on w “Kwantowy Darknet”.

Bibliografia

Simon Signh, The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography, Anchor Boks, New York (2000).
Qiang Zhang, Feihu Xu, Yu-Ao Chen, Cheng-Zhi Peng, and Jian-Wei Pan, Large scale quantum key distribution: challenges and solutions [Invited], Opt. Express 26, 24260-24273 (2018).
Martino Travagnin, Adam Lewis, Quantum Key Distribution in-field implementations, EUR 29865 EN, Publications Office of the European Union, Luxembourg (2019).
H. Kimble, The quantum internet. Nature 453, 1023–1030 (2008).

Artykuł został opublikowany na portalu Nauka UJ.

Technologie kwantowe a cyberbezpieczeństwo

November 25, 2019April 10, 2020 jakub mielczarekLeave a comment

Jednym z najważniejszych filarów bezpieczeństwa w cyberprzestrzeni jest kryptografia. Z punktu widzenia jednostki, m.in. to dzięki kryptografii możliwe jest korzystanie z systemów bankowości elektronicznej, dokonywanie zakupów online, zachowanie prywatności w komunikacji internetowej, czy też zapewnienie poufności naszej dokumentacji medycznej w medycznych systemach teleinformatycznych. Z punktu widzenia Państwa, kryptografia to zaś kluczowy element tarczy chroniącej przed cyberatakami na strategiczne komponenty (zarówno infrastrukturę fizyczną, jak i zasoby cyfrowe) oraz narzędzie umożliwiające wymianę i przechowywanie informacji niejawnej, o podstawowym znaczeniu dla interesu i bezpieczeństwa Państwa.

Rozwój technologii kwantowych, opartych na niezwykłych własnościach mikroświata, ma z punktu widzenia cyberbezpieczeństwa znaczenie dwojakie. Z jednej strony, kwantowe przetwarzanie informacji dostarcza nowej metody prowadzenia ataków na klasyczne systemy kryptograficzne, poprzez tzw. kryptoanalizę kwantową. Państwa lub organizacje, które wejdą w posiadanie zaawansowanych systemów umożliwiających prowadzenie obliczeń kwantowych będą więc dysponowały nowym narzędziem stanowiącym potencjalne zagrożenie dla cyberbezpieczeństwa. Z drugiej zaś strony, technologie kwantowe dostarczają zupełnie nowych rozwiązań kryptograficznych, które mogą pozwolić osiągnąć poziom bezpieczeństwa w wymianie i magazynowaniu informacji, niedostępny z wykorzystaniem kryptografii klasycznej. W szczególności, rozwiązania takie mogą uchronić przed atakami z wykorzystaniem kryptoanalizy kwantowej.

To czy technologie kwantowe ostatecznie obniżą poziom cyberbezpieczeństwa, czy też tylko go wzmocnią, zależy zarówno od tempa i zakresu postępów w rozwoju technologii kwantowych oraz decyzji państw i organizacji międzynarodowych w zakresie wdrażania rozwiązań odpornych na kryptoanalizę kwantową [1]. Z uwagi na wysokie koszty oraz unikalną wiedzę i doświadczenie, które są niezbędne do rozwoju technologii kwantowych, realne są scenariusze w których zarówno zabezpieczenie cyberprzestrzeni przed atakami, jak i wejście w posiadanie kwantowych narzędzi kryptoanalitycznych, będzie postępowało bardzo niejednorodnie. Stanowić to więc może realne zagrożenie dla krajów nie należących do światowej czołówki w obszarze nauki i techniki.

Kryptoanaliza kwantowa

Zagrożenie związane z kryptoanalizą kwantową wynika z możliwości redukcji tak zwanej złożoności obliczeniowej problemów, na których opierają się algorytmy kryptografii klasycznej. Wiąże się to z występowaniem paralelizmu kwantowego (Dodatek A), który jest możliwy do zrealizowania poprzez wykonanie algorytmów kwantowych na odpowiednio zaawansowanych komputerach kwantowych. Kwantowa redukcja złożoności jest teoretycznie możliwa zarówno w przypadku kryptografii symetrycznej (z tajnym kluczem), jak i kryptografii asymetrycznej (z kluczem publicznym). Otrzymywany, dzięki algorytmom kwantowym, stopień redukcji złożoności jest jednak zasadniczo różny dla tych dwóch przypadków. W konsekwencji, niektóre stosowane obecnie algorytmy kryptografii symetrycznej pozostaną niepodatne na kryptoanalizę kwantową. Natomiast, np. wykorzystywane powszechnie w bankowości elektronicznej, systemach płatniczych, czy też rozwiązaniach opartych o technologię Blockchain, algorytmy kryptografii asymetrycznej zostaną wystawione na potencjalne zagrożenie.

Przedyskutujmy powyższą kwestię bardziej szczegółowo. W przypadku kryptografii symetrycznej, siła zabezpieczenia opiera się, w dużej mierze, na wielkości przestrzeni tajnego klucza. Przykładowo, dla stosowanego powszechnie algorytmu symetrycznego AES (Advanced Encryption Standard) z kluczem 256 bitowym, przestrzeń klucza posiada N = 2²⁵⁶ elementów, co jest w przybliżeniu równe jeden i 77 zer. Przeszukanie tak ogromnego zbioru w poszukiwaniu tajnego klucza jest praktycznie niemożliwe, zarówno korzystając z obecnych, jak i możliwych do przewidzenia przyszłych zasobów obliczeniowych.

Zastosowanie algorytmów kwantowych pozwoli przyśpieszyć proces poszukiwania przestrzeni klucza w ataku siłowym (ang. brute force). Mianowicie, jak pokazał w 1996 roku Lov Grover, wykorzystanie obliczeń kwantowych pozwala zredukować średnią ilość prób potrzebnych do znalezienia elementu w nieuporządkowanym N elementowym zbiorze z N/2 do pierwiastka kwadratowego z N, czyli N^1/2. Oznacza to, że w przypadku AES-256, komputer kwantowy będzie wciąż potrzebował wykonać około N^1/2=2¹²⁸ prób w celu znalezienia tajnego klucza. Nawet więc dysponując komputerem kwantowym, na którym zaimplementowany mógłby zostać algorytm Grover’a, siła szyfru pozostanie na poziomie porównywalnym z AES z kluczem 128 bitowym. Jest to zabezpieczenie zupełnie wystarczający dla większości standardowych sytuacji.

Rzecz ma się jednak inaczej w przypadku szyfrów kryptografii asymetrycznej (z kluczem publicznym). Istota kryptografii asymetrycznej opiera się na trudności obliczeniowej pewnych operacji matematycznych, dla których zaś operacja „przeciwna” jest łatwa do przeprowadzenia. Do najbardziej znanych przykładów algorytmów tego typu zaliczają się DH (Diffie-Hellman), RSA (Rivest-Shamir-Adleman) oraz ECC (Elliptic Curve Cryptography). Algorytm DH jest oryginalnie pierwszą propozycją kryptografii z kluczem publicznym a trudnym problemem jest tutaj znajdowanie tak zwanego logarytmu dyskretnego (logarytmu określonego na skończonym zbiorze liczb). Z kolei, popularny algorytm RSA wykorzystuje złożoność obliczeniową rozkładu liczby na czynniki pierwsze (zagadnienie faktoryzacji). Wadą algorytmów DH i RSA jest konieczność stosowania stosunkowo długich kluczy (obecnie powszechnie stosuje się klucze 2048 bitowe). Problem ten rozwiązuje zastosowanie algorytmów ECC, wykorzystujących problem złożoności logarytmu dyskretnego dla działania zdefiniowanego na krzywej eliptycznej. Poziom bezpieczeństwa porównywalny z DH lub RSA z kluczem 2048 bitwym otrzymamy stosując algorytm ECC z kluczem 224 bitowym. Między innymi z tego powodu, algorytmy ECC znalazły szerokie zastosowanie w technologii Blockchain.

Okazuje się, że trudność obliczeniową na której oparte są przytoczone powyżej algorytmy kryptografii asymetrycznej można sprowadzić do zagadnienia znalezienia okresu pewnej funkcji. O ile jednak, znajdowanie okresu funkcji jest z perspektywy komputerów klasycznych zadaniem trudym obliczeniowo, nie jest już takim dla komputerów kwantowych. Mianowicie, jak pokazał w 1994 roku Peter Shor, obliczenia kwantowe pozwalają zredukować złożoność problemu znajdowania okresu funkcji z problemu wykładniczego w funkcji ilości bitów danej liczby do problemu wielomianowego klasy BPQ (Dodatek B). Fakt ten jest głównym źródłem zagrożenia związanego z kryptoanalizą kwantową.

CyberSec — Obwód kwantowy dla algorytmu Shora na tle fragmentu książki Georga Orwella *1984*, zakodowanej za pomocą kolorów przez Hyo Myoung Kima [cała książka].

W optymalnej konfiguracji, Algorytm Shora dla przypadku z kluczem n-bitowym wymaga rejestru kwantowego zawierającego 2n+3 kubity logiczne. Dla algorytmu RSA-2048 są to więc 4099 kubity logiczne. Jednakże, z uwagi na błędy występujące w fizycznych realizacjach komputerów kwantowych, konieczne jest stosowanie rozbudowanych systemów kwantowej korekcji błędów. Zastosowanie korekcji błędów wymaga użycia co najmniej pięciu fizycznych kubitów do zakodowania jednego kubitu logicznego. Absolutnie minimalna liczba fizycznych kubitów, potrzebnych do przeprowadzenia kwantowej kryptoanalizy algorytmu RSA-2048 na komputerze kwantowym, jest więc rzędu 20 000. W praktyce jednak, konieczne może się okazać wykorzystanie dużo większej ilości kubitów pomocniczych, co może zwiększyć tę liczbę do setek tysięcy lub nawet milionów kubitów. Równie ważną kwestią jest osiągnięcie odpowiednio długiego czasu koherencji, gdyż realizacja powyższego algorytmu będzie wymagać przynajmniej 10⁷kroków obliczeniowych.

Oszacowane powyżej wielkości mogą wydawać się zupełnie abstrakcyjne z perspektywy dostępnych dzisiaj możliwości przeprowadzania obliczeń kwantowych. Dla przykładu, najbardziej zaawansowany komputer kwantowy firmy Google posiada 53 kubity i jest w stanie wykonać kilkanaście kroków obliczeniowych. Jednakże, przyjmując hipotetyczny wykładniczy charakter rozwoju technologii kwantowych (analogiczny do prawa Moore’a), osiągnięcie poziomu miliona kubitów jest realne w perspektywie 30 lat. Załóżmy, że skala czasowa podwojenia ilości kubitów w procesorze kwantowym będzie wynosiła około 2 lata (podobnie jak obecnie ma to miejsce w przypadku liczby tranzystorów w procesorach klasycznych). W takim przypadku, w kolejnych latach możemy prognozować wartości: 100 (2021), 200 (2023), 400 (2025), 800 (2027), 1600 (2029), 3200 (2031), 6400 (2033), 12800 (2035), 25600 (2037), 51200 (2039), 102400 (2041), 204800 (2043), 409600 (2045), 819200 (2047), 1638400 (2049), … . Zgodnie z tą naiwną ekstrapolacją, poziom milionów kubitów powinien zostać osiągnięty do roku 2050. Istnieją również bardziej optymistyczne prognozy, wskazujące na możliwość nawet podwójnie wykładniczego rozwoju technologii kwantowych („prawo” Neven’a).

W kontekście kryptoanalizy, warto przywołać także przypadek funkcji skrótu (ang. hash functions), które są nieodzownym elementem współczesnych protokołów kryptograficznych. Do najpowszechniejszych z nich należą: MD4, MD5, SHA-1, SHA-2 i SHA-3. Kryptoanaliza siłowa funkcji skrótu jest zasadniczo podobna do przypadku kryptografii symetrycznej i opiera się na wykorzystaniu algorytmu Grovera. W przypadku SHA-3 ze skrótem 512 bitowym, odporność na tzw. preimage attack jest więc na poziomie algorytmu symetrycznego z kluczem 256 bitowym. Tego samego poziomu jest odporność na ataki kolizyjne. Z uwagi na tę niepodatność na kryptoanalizę kwantową, funkcje skrótu rozpatruje się jako jeden z najbardziej obiecujących komponentów tak zwanej kryptografii postkwantowej.

Kryptografia postkwantowa

Kryptografia postkwantowa [2] jest odpowiedzią na potencjalne zagrożenie związane z kryptoanalizą kwantową algorytmów klasycznej kryptografii asymetrycznej. Z uwagi na to, że kwantowe przyśpieszenie wykładnicze (Dodatek A) nie występuje w przypadku problemu przeszukiwania przestrzeni klucza, nie istnieją obecnie podstawy do obaw o bezpieczeństwo silnych algorytmów kryptografii symetrycznej, takich jaki AES-256, czy też algorytmów opartych na funkcjach skrótu.

Potencjalne zagrożenie związane z kwantową kryptoanalizą algorytmów kryptografii asymetrycznej nie może jednak zostać zbagatelizowane. Nawet jeśli kwantowe możliwości obliczeniowe umożliwiające kryptoanalizę RSA z kluczem 2048 bitowym pojawią się dopiero za 30 lat, należy podejmować działania zapobiegawcze. Po pierwsze, wynika to z faktu, że proces wdrażania (standaryzacja i implementacja) nowych rozwiązań kryptograficznych jest długotrwały, wymagając zarówno prac badawczych, szeroko zakrojonych testów podatności na kryptoanalizę, jak i samej implementacji w ramach istniejących systemów informatycznych. Po drugie, wiele zaszyfrowanych informacji pozostaje wrażliwymi przez okres kilkudziesięciu lat. Ich przechowywanie (jako szyfrogramy) i odszyfrowanie w momencie pojawienia się odpowiednich możliwości obliczeniowych, może doprowadzić nawet do ogólnoświatowego kryzysu. Dla przykładu, dostępne publicznie mogą stać się dane osobowe, transakcje bankowe, dane medyczne milionów osób, co otworzy szereg możliwości działań natury przestępczej. Ponadto, zgodnie z Art. 25 ustawy z dnia 22 stycznia 1999 r. o ochronie informacji niejawnych: „Informacje niejawne stanowiące tajemnicę państwową podlegają ochronie, w sposób określony ustawą, przez okres 50 lat od daty ich wytworzenia.” Biorąc pod uwagę możliwość wykorzystania algorytmów kryptografii asymetrycznej do przetwarzania tego typu informacji (chociażby poprzez wykorzystanie kryptografii asymetrycznej do wymiany klucza), realność kryptoanalizy kwantowej w perspektywie 30 lat stawia pod znakiem zapytania bezpieczeństwo przetwarzanej obecnie informacji niejawnej, stanowiącej tajemnicę państwową.

Z uwagi na zagrożenia powyższego typu, w 2016 roku amerykański Narodowy Instytut Standaryzacji i Technologii (NIST) ogłosił program opracowania standardu kryptografii postkwantowej, odpornego na kryptoanalizę kwantową. Proces ten przebiega na zasadzie konkursu, podobnie jak to wcześniej miało miejsce np. w przypadku standardu AES. Obecnie, w drugiej rundzie, rozważana jest pula 26 propozycji. W pierwszej rundzie, z początkowych 250 zgłoszeń wybranych zostało 69 najbardziej obiecujących rozwiązań. Cały proces ma zostać zakończony do roku 2022. Rozpatrywany wachlarz rozważanych algorytmów kryptografii postkwantowej jest szeroki. Do najbardziej obiecujących kierunków należą zaś:

Algorytmy kratowe (ang. lattice-based cryptography)
Algorytmy oparte na kodach korekcyjnych (ang. code-based cryptography)
Kryptografia wielu zmiennych (ang. multivariate cryptography)
Podpis elektroniczny opary o funkcje skrótu (ang. hash-based signatures)

Z uwagi na subtelną naturę rozwiązań kryptograficznych, standaryzacja jest kluczowym elementem poprzedzającym szeroką implementacji nowych algorytmów. Etap ten jest długotrwały i powiązany jest z badaniem odporności danych rozwiązań na ataki kryptologiczne. Należy mieć jednak na uwadze to, że nawet pomyślne wyłonienie nowego standardu nie gwarantuje późniejszego długotrwałego bezpieczeństwa. Wiązać się to może zarówno z odkryciem niezauważonych wcześniej słabości rozwiązań, z pojawieniem się nowych schematów ataków oraz nowymi możliwościami obliczeniowymi. Dla przykładu, zaprojektowany na zlecenie NIST i stosowany od połowy lat siedemdziesiątych ubiegłego wieku symetryczny szyfr DES (z kluczem efektywnie 56 bitowym), okazał się możliwy do złamania już po 20 latach od jego wprowadzenia.

Fakt iż, możliwości kryptoanalizy szyfrów kryptografii postkwantowej są wciąż stosunkowo słabo poznane, istnienie realna obawa, że nawet wyłonione w procesie standaryzacji rozwiązania będą podatne na pewne typy ataków. Dlatego też, w początkowej fazie implementacji wydaje się zasadne opieranie się w jak największym stopniu na dobrze zbadanych elementach obecnych systemów kryptograficznych, takich jak funkcje skrótu lub kody korekcyjne.

O ile proces standaryzacji prowadzony przez NIST jest w toku, w ramach niezależnych projektów podano już pewne rekomendacje co do algorytmów kryptografii postkwantowej. W szczególności, europejski projekt PQCRYPTO, finansowany w ramach programu Horyzont 2020, rekomendował AES-256 i Salsa20 z kluczem 256 bitowym jako postkwantowe algorytmy kryptografii symetrycznej. Dla kryptografii asymetrycznej, rekomendowany został natomiast szyfr McEliece’a, będący przykładem algorytmu opartego na kodach korekcyjnych [3].

Certyfikowana kwantowa przypadkowość

Jednymi z komponentów systemów kryptograficznych, mającymi fundamentalne znaczenie z punktu widzenia bezpieczeństwa, są generatory liczb losowych. W praktyce, są to generatory liczb pseudolosowych, co na przykład w przypadku szyfrów strumieniowych (wykorzystywanych np. do zabezpieczania transmisji w telefonii komórkowej) jest własnością pożądaną. Jednakże, już w przypadku generowania kluczy (będących ciągami bitów) oczekujemy niepowtarzalnej przypadkowości. Dotyczy to zarówno kluczy wykorzystywanych w kryptografii symetrycznej, jak i asymetrycznej.

Błędy w implementacji generatorów pseudolosowych mogą istotnie wpłynąć na obniżenie bezpieczeństwa, wykorzystujących je algorytmów kryptograficznych. Znanym przykładem jest wykazanie istnienia „tylnej furtki” w generatorze pseudolosowym Dual_EC_DRBG. Ujawnione przez Edwarda Snowdena informacje na temat programu deszyfrażu Bullrun, sugerują, że obecność furtki mogło być działaniem celowym amerykańskiej National Security Agency (NSA) [4]. O ile więc furtki takie mogą być wprowadzane celowo przez agencje dbające o bezpieczeństwo publiczne, ich obecność stwarza również możliwość wykorzystania przez osoby, instytucje i państwa nieprzyjazne.

Probabilistyczna natura mechaniki kwantowej stwarza atrakcyjną możliwość budowy generatorów losowych. Co więcej, rozwiązania takie są już dostępne komercyjnie. Jednakże, otwarte zostaje potencjalne zagrożenie związane z wykorzystaniem możliwych „tylnych furtek” w tego typu rozwiązaniach. Dlatego też, dąży się do opracowania rozwiązań które będą gwarantowały zarówno losowość, jak i niepodatność na ataki, zarówno na poziomie sprzętu, jak i oprogramowania.

Jednym z pojeść do tego zagadnienia jest wykorzystanie trudności obliczeniowej problemu przewidzenia rozkładu prawdopodobieństwa pomiarów dla odpowiednio dużych pseudolosowo-generowanych obwodów kwantowych. Własność tę można wykorzystać do generowania certyfikowanych kwantowo losowych ciągów binarnych (ang. certified quantum randomness) [5]. Losowość otrzymanego ciągu bitów jest zagwarantowana złożonością obliczeniową problemu przewidzenia z jakim prawdopodobieństwem dany ciąg może zostać wygenerowany przez obwód kwantowy. Ponadto, nawet kiedy źródło generatora obwodów zostałoby upublicznione, wygenerowane wartości losowe zachowają prywatność.

Metoda ta może być pomyślnie stosowana już z wykorzystaniem dostępnych obecnie komputerów kwantowych, posiadających kilkadziesiąt (zaszumionych) kubitów fizycznych. Dowodem na to jest niedawny rezultat otrzymany za pomocą komputera kwantowego opracowanego przez firmę Google. Rozważane zagadnienie próbkowaniem (ang. sampling), które przeprowadzono na 53 kubitowym procesorze może zostać zaadoptowane do zapewnienia certyfikowanej kwantowej przypadkowości [6].

Zastosowanie certyfikowanej kwantowej generacji kluczy może istotnie wzmocnić bezpieczeństwo zarówno konwencjonalnej kryptografii (asymetrycznej i symetrycznej) jak i algorytmów kryptografii postkwantowej. Jest to przykład rozwiązania hybrydowego w którym wykorzystuje się połączenie znanych i możliwych do zastosowania algorytmów kryptografii klasycznej z najnowszymi osiągnięciami w obszarze obliczeń kwantowych.

Kwantowa dystrybucja klucza

Nawet jeśli jest to możliwe w niepraktycznie dużych skalach czasowych, algorytmy kryptografii klasycznej, z wyłączeniem szyfru z kluczem jednorazowym (ang. one-time pad), są zawsze możliwe do złamania. Mechanika kwantowa dostarcza jednakże teoretycznie niepodatnej na kryptoanalizę metody szyfrowania informacji. Opracowywaniem tego typu rozwiązań zajmuje się kryptografia kwantowa.

Kwantowa dystrybucja klucza (ang. quantum key distribution – QKD) [7] jest, rozważaną w ramach kryptografii kwantowej, metodą bezpiecznego przesyłania sekretnego klucza za pośrednictwem stanów kwantowych pojedynczych fotonów. Metoda ta wykorzystuje kwantowe własności mikroświata (w szczególności, tak zwane twierdzenie o zakazie klonowania kwantowego) do przesyłania informacji. Ponieważ przepustowość wykorzystywanych do QKD tzw. kanałów kwantowych nie dorównuje tym osiąganym w klasycznych łączach światłowodowych oraz radiowych, łącza kwantowe wykorzystywane są obecnie do przesyłania sekretnych kluczy, pozwalających zaszyfrować (klasyczną) wiadomość, nie zaś do transmisji samej wrażliwej informacji. Udostępniony, za pośrednictwem QKD, klucz może być wykorzystany do zaszyfrowania danych np. z użyciem silnego symetrycznego szyfru AES-256.

Kwantowa dystrybucja klucza jest rozwiązaniem, które zostało już wdrożone do komercyjnego użytku. Jednakże, dostępne obecnie rozwiązania posiadają jedno kluczowe ograniczenie. Mianowicie, jest to dystans, na który możemy przesłać zabezpieczoną kwantowo informację. Wiąże się to z tłumieniem fotonów w światłowodzie i koniecznością stosowania skomplikowanych tzw. powielaczy kwantowych. Obiecującym rozwiązaniem tego problemu jest przesyłanie fotonów z zakodowaną kwantowo informacją poprzez atmosferę oraz przestrzeń kosmiczną. Udane próby międzykontynentalnej QKD z wykorzystaniem kwantowych technologii satelitarnych udało się przeprowadzić w 2017-tym roku. Obecnie trwają prace nad kilkoma projektami satelitarnymi, które mają na celu rozwój kwantowych technologii związanych z łącznością satelitarną.

Połączenie światłowodowej oraz satelitarnej łączności kwantowej może pozwolić urzeczywistnić idę tzw. internetu kwantowego – niepodatnego na kryptoanalizę kanału wymiany informacji. Stworzenie podwalin dla internetu kwantowego to m.in. jeden z filarów, rozpisanego na okres dziesięciu lat (2018-2028), flagowego programu Komisji Europejskiej – Quantum Flagship. Ponadto, w ramach projektu OPENQKD (Open European Quantum Key Distribution Testbed) powstaje obecnie w Europie eksperymentalna sieć do kwantowej dystrybucji klucza, której jeden z węzłów znajdzie się również w Polsce.

Warto w tym miejscu podkreślić, że systemy do kwantowej dystrybucji klucza, choć teoretycznie bezwarunkowo bezpieczne, mogą stać się jednak przedmiotem ataków. Istnieje mianowicie szerokie spektrum możliwych ataków fizycznych, wykorzystujących błędy w implementacji systemów do QKD. Jedną z prób rozwiązania tego problemu jest opracowanie algorytmów kryptografii kwantowej gwarantujących bezpieczeństwo w wymianie informacji, niezależne do wad implementacji fizycznych. Konieczne są jednakże dalsze prace zarówno teoretyczne, jak i eksperymentalne w tym obszarze.

Podsumowanie

Infosfera stała się kluczowym elementem współczesnej aktywności ludzkiej. Jej dynamiczny rozwój doprowadził jednak do pojawienia się zagrożeń zupełnie nowego typu. Dotyczy to zarówno poziomu jednostek, jak i społeczeństw. W konsekwencji, cyberprzestrzeń stała się równoprawnym do wody, lądu, powietrza i przestrzeni kosmicznej, obszarem działań wojennych. Powaga problemu doprowadziła do szerokiego zaangażowania państw i organizacji w obszarze zapewnienia bezpieczeństwa w cyberprzestrzeni. W Polsce, ważnym krokiem stało się sformułowanie w 2015 roku Doktryny Cyberbezpieczeństwa Rzeczypospolitej Polskiej [8]. Elementem realizacji jej założeń jest konsolidacja polskich zasobów w obszarze cyberbezpieczeństwa i kryptologii w ramach utworzonego w 2019 roku Narodowego Centrum Bezpieczeństwa Cyberprzestrzeni (NCBC), funkcjonującego wcześniej jako Narodowe Centrum Kryptologii (NCK).

Technologie kwantowe, które coraz odważniej wychodzą z obszaru badawczego do fazy wdrożeń, stanowią zarówno potencjalne zagrożenie dla cyberbezpieczeństwa, jak i dają narzędzie dla jego wzmocnienia do bezprecedensowego poziomu. Zagrożenie związane jest głównie z możliwością kryptoanalizy algorytmów kryptografii asymetrycznej (w szczególności RSA i ECC). Natomiast, silne algorytmy kryptografii symetrycznej pozostaną odporne na kryptografię kwantową. W mojej ocenie, realistyczna wydaje się możliwość kryptoanalizy algorytmu RSA z kluczem 2048 bitowym w perspektywie czasowej 30 lat. Warto również mieć na uwadze prawdopodobieństwo opracowania nowych algorytmów, które mogą znaleźć zastosowanie w kryptoanalizie kwantowej.

Odpowiedzią na zagrożenie związane z kryptoanalizą kwantową jest kryptografia postkwantowa. Zadaniem które sobie stawia jest opracowanie algorytmów kryptografii z kluczem publicznym, niepodatnych na ataki kwantowe. W toku jest proces standaryzacji algorytmów kryptografii postkwantowej, po zakończeniu którego (około roku 2023) można spodziewać intensyfikacji w implementacji tego typu rozwiązań. Należy jednak zdawać sobie sprawę z faktu, że algorytmy kryptografii postkwantowej wciąż wymagają testów pod kątem kryptoanalizy, zarówno konwencjonalnej, jak i kwantowej.

Z drugiej strony, technologie kwantowe otwierają obiecującą możliwość implementacji rozwiązań kryptografii kwantowej. Jednym z nich jest kwantowa generacja klucza. Rozwiązania takie stają się możliwe do urzeczywistnienia z wykorzystaniem opracowywanych obecnie komputerów kwantowych. W perspektywie nadchodzącej dekady, certyfikowane kwantowe generowanie kluczy pozwoli wzmocnić bezpieczeństwo kryptografii klasycznej, jak również algorytmów postkwantowych. Kolejnym, bardzo obiecującym, rozwiązaniem dostarczanym przez kryptografię kwantową jest kwantowa dystrybucja klucza. Naziemna i satelitarna sieć kanałów kwantowych (tzw. kwantowy internet) pozwoli na bezwarunkowo bezpieczne przekazywanie sekretnych kluczy. Z ich pomocą, możliwe będzie późniejsze przesyłanie informacji kanałami klasycznymi, stosując silne szyfry symetryczne.

Budowa infrastruktury do komunikacji kwantowej, która ostatecznie zapewni nowy poziom bezpieczeństwa w przesyle informacji jest zadaniem niezwykle złożonym i wymagającym integracji wielu zasobów i kompetencji. Jej utworzenie wykreuje zupełnie nowe realia dla cyberbezpieczeństwa. Warto w tym kontekście zaznaczyć, że z uwagi skomplikowaną naturę systemów do komunikacji kwantowych i kryptografii kwantowej, ważnym elementem będzie proces szkolenia specjalistów, którzy będą w stanie analizować subtelności stosowanych rozwiązań i przewidywać możliwość występowania nowych zagrożeń.

Przeprowadzona tu analiza jedynie zarysowuje zagadnienie cyberbezpieczeństwa kwantowego, akcentując podstawowe możliwości i zagrożenia. Dalsza szersza dyskusja, łącząca płaszczyzny: polityczną, akademicką, militarną i przedsiębiorczą, jest konieczna w celu wypracowania optymalnych rozwiązań, które pozwolą na wykorzystanie technologii kwantowych do zapewnienia jeszcze wyższego poziomu cyberbezpieczeństwa w Polsce i na świecie.

Dodatek A – Kwantowy elementarz

Technologie kwantowe tworzy obecnie szerokie spektrum rozwiązań, wykorzystujących kwantową naturę mikroświata, opisywaną przez mechanikę kwantową. Do najważniejszych przykładów należą: systemy przetwarzania informacji kwantowej (komputery kwantowe), systemy łączności kwantowej (oparte o kryptografię kwantową) i systemy metrologii kwantowej (np. kwantowe magnetometry).

Szczególną klasą układów kwantowych, odgrywają kluczową rolę w kwantowym przetwarzaniu informacji, są kubity. Kubity można postrzegać jako kwantowe odpowiedniki klasycznych bitów, mogące występować w kwantowych superpozycjach stanów „0” i „1”. Sytuacja robi się jeszcze ciekawsza kiedy rozważamy wiele oddziałujących ze sobą kubitów. Właśnie takie złożenie kubitów stanowi rejestr komputera kwantowego, na którym, poprzez wykonywanie odpowiednich operacji (unitarnych), przeprowadzane są obliczenia kwantowe. Wyzwaniem związanym z budowaniem tego typu maszyn jest odseparowanie rejestru kwantowego od środowiska zewnętrznego, które zaburza jego kwantową naturę. Wyzwaniem jest również odpowiednie kontrolowanie kubitów i przeprowadzanie na nich operacji. Przez wiele lat, fizycy zmagali się z osiągnięciem odpowiedniego poziomu koherencji kwantowej i sterowalności rejestrów kwantowych. Przełomowe okazało się wykorzystanie nadprzewodzących kubitów, które ostatecznie doprowadziło do eksperymentalnego wykazania przewagi (w wczasie obliczeń) komputera kwantowego nad najsilniejszym dostępnym superkomputerem klasycznym. Udało się to ostatecznie wykazać firmie Google, dla problemu próbkowania ciągów binarnych z zadanym przez obwód kwantowy rozkładem prawdopodobieństwa [6].

Trudność w emulowaniu obliczeń kwantowych na komputerach klasycznych wiąże się z faktem, że stan układu n kubitów opisywany jest w 2ⁿwymiarowej przestrzeni Hilberta. W konsekwencji, na przykład by opisać układ 100 kubitów należy użyć wektora posiadającego około 10³⁰składowych. Próba zapisania takiego wektora zarówno w obecnych jaki i możliwych do wyobrażenia przyszłych komputerach klasycznych jest praktycznie skazana na niepowodzenie. Z drugiej strony, operowanie w 2ⁿwymiarowej przestrzeni Hilberta, dysponując n kubitami umożliwia wykonywanie wykładniczo rosnącej z n liczby operacji. Na własności tej opiera się tzw. paralelizm kwantowy, mogący w pewnych przypadkach doprowadzić do kwantowego przyśpieszenia wykładniczego (ang. exponential speed-up) w rozwiązaniu pewnych problemów. Z sytuacją taką spotykamy się, w szczególności, w przypadku algorytmu faktoryzacji Shora, znajdującym zastosowanie w kryptoanalizie kwantowej.

Dodatek B – Złożoność obliczeniowa

Złożoność obliczeniowa, w uproszczeniu określa poziom trudności rozwiązania danego problemu. Dla przykładu, rozważmy problem znalezienia konkretnego elementu w nieuporządkowanym zbiorze N elementowym. Element taki znajdziemy w średnio N/2 próbach. Czas potrzebny na znalezienie elementu będzie więc skalował się liniowo wraz z liczebnością (mocą) zbioru. Jest to przykład problemu należącego do wielomianowej klasy złożoności – P (ang. Polynomial). Innym przykładem problemu należącego do klasy P jest mnożenie liczb.

Nie wszystkie znane problemy należą jednak do kasy P, a przynajmniej tak się wydaje. Okazuje się mianowicie, że istnieje cały szereg problemów dla których nie udało się, jak dotąd, zaproponować algorytmów ich rozwiązywania które należałyby do klasy P. Problemy takie określamy mianem NP (ang. Nondeterministically Polynomial). Są to takie problemy dla których znając wynik możemy w czasie wielomianowym zweryfikować czy propozycja wyniku jest rozwiązaniem czy też nie. Przykładem takiego problemu, jest rozkład liczby złożonej na czynniki pierwsze (problemu faktoryzacji). Problemy klasy NP znajdują szerokie zastosowanie w kryptologii. Otwartym i jednym z najważniejszych problemów matematycznych jest odpowiedzenie na pytanie czy faktycznie NP≠P?

Uogólnienie rozważań do obliczeń kwantowych wymaga wprowadzenia nowych klas złożoności. Na potrzeby tego artykułu, wprowadzimy jedynie klasę BQP (ang. bounded-error quantum polynomial time). Do klasy tej należą problemy, dla których istnieje możliwość znalezienia rozwiązania w czasie wielomianowym, z prawdopodobieństwem co najmniej 2/3 (czyli błędem nie większym niż 1/3). Okazuje się, że kwantowy algorytm Shora pozwala zredukować złożoność obliczeniową problemu faktoryzacji, klasycznie klasyfikowanego jaki problem wykładniczy, do takiej właśnie złożoności. Jest to przykład kwantowego przyśpieszenia wykładniczego.

Bibliografia

[1] M. Mosca, Cybersecurity in an Era with Quantum Computers: Will We Be Ready? IEEE Security & Privacy, September/October 2018, pp. 38-41, vol. 16
[2] D. J. Bernstein, T. Lange, Post-quantum cryptography, Nature, 549(7671), 188-194.
[3] PQCRYPTO – Post-Quantum Cryptography for Long-Term Security. Initial recommendations of long-term secure post-quantum systems
[4] D. J. Bernstein, T. Lange, R. Niederhagen, Dual EC: A Standardized Back Door. In: Ryan P., Naccache D., Quisquater JJ. (eds) The New Codebreakers. Lecture Notes in Computer Science, vol 9100. Springer, Berlin, Heidelberg
[5] Acín, A., Masanes, L. Certified randomness in quantum physics. Nature 540, 213–219 (2016).
[6] Arute, F., Arya, K., Babbush, R. et al. Quantum supremacy using a programmable superconducting processor. Nature 574, 505–510 (2019)
[7] A. Shenoy-Hejamadi, A. Pathak, S. Radhakrishna, Quantum Cryptography: Key Distribution and Beyond, Quanta 2017; 6: 1–47
[8] Doktryna Cyberbezpieczeństwa Rzeczypospolitej Polskiej, 2015.

Artykuł został opublikowany na portalu CyberDefence24.

Kwantowa dystrybucja klucza

May 8, 2019July 17, 2019 jakub mielczarek1 Comment

W moich wcześniejszych wpisach kilkukrotnie odwoływałem się do kwantowej dystrybucji klucza (KDK), będącej jednym z głównych filarów kryptografii kwantowej. Miało to miejsce w kontekście omawiania takich zagadnień jak: kwantowa łączność satelitarna, internet kwantowy oraz bezpieczeństwo kryptowalut (wpisy: Kwantowa łączność satelitarna, Dwanaście technologii jutra i Kryptowaluty-Kwanty-Kosmos). Niniejszy wpis można potraktować jako uzupełnienie techniczne tych rozważań. Poniżej, przedstawię fizyczne podstawy na których opiera się kwantowa dystrybucja klucza oraz omówię, wprowadzony w 1984 roku, protokół Bennetta-Brassard BB84. Jest to najbardziej znany i historycznie pierwszy przykład protokołu KDK opartego na superpozycji kwantowej. W późniejszych latach, wprowadzono także protokoły oparte na innych własnościach mechaniki kwantowej, m.in. na splątaniu kwantowym (np. protokół E91). Dyskusja szerokiego spektrum rozważanych obecnie protokołów kryptografii kwantowej wykracza poza ramy tego wpisu. Czytelnika zainteresowanego zapoznaniem się z pełniejszym obrazem tematu zachęcam do przestudiowania np. przeglądowego artykułu arXiv:1802.05517. Tytułem wstępu dodam jeszcze, że do zrozumienia niniejszego tekstu przydatna jest znajomość zasad mechaniki kwantowej. Niezapoznanego z nimi Czytelnika zachęcam do przestudiowania mojego wpisu Elementary quantum computing oraz znajdujących się w nim odnośników.

Zacznijmy więc. W największym skrócie, kwantowa dystrybucja klucza pozwala na, jak mówimy, bezwarunkowo bezpieczną wymianę klucza w oparciu o własności mechaniki kwantowej. To w jaki sposób fizyka mikroświata pozwala zapewnić “bezwarunkowe bezpieczeństwo”, postaram się wyjaśnić poniżej. Jak to również zostanie dokładniej omówione w dalszej części tekstu, przepustowość wykorzystywanych do KDK tzw. kanałów kwantowych nie dorównuje tym osiąganym w klasycznych łączach światłowodowych oraz radiowych. Z tego też powodu, łącza kwantowe wykorzystywane są obecnie do przesyłania sekretnych kluczy, pozwalających zaszyfrować (klasyczną) wiadomość, nie zaś do transmisji samej wrażliwej informacji. Udostępniony, za pośrednictwem KDK, klucz może być wykorzystany do zaszyfrowania danych np. z użyciem bardzo silnego symetrycznego szyfru AES 256. Przykładową architekturę systemu do kwantowej dystrybucji klucza, zawierającą zarówno kanał kwantowy (do przesyłania klucza) oraz kanał klasyczny (do przesyłania zaszyfrowanych danych oraz informacji pomocniczych), przedstawia rysunek poniżej:

Przykładowa architektura systemu do kwantowej dystrybucji klucza z kanałem kwantowym oraz kanałem klasycznym. Źródło

W przypadku kanału klasycznego opartego o łącze światłowodowe, zaszyfrowana informacja przesyłana jest za pomocą światła. Do przesłania klucza poprzez kanał kwantowy również wykorzystywane jest pole elektromagnetyczne. Z tą jednak różnicą, że odbywa się to za pośrednictwem nie klasycznych impulsów lecz pojedynczych kwantów światła, czyli fotonów. Do zakodowania informacji kwantowej wykorzystywane są zaś stany polaryzacji światła. Przedyskutujmy to bardziej szczegółowo. Mianowicie, światło docierające do nas, na przykład, ze Słońca lub z żarówki nie jest spolaryzowane. Na poziomie klasycznym, oznacza to, że światło tego typu składa się z fal elektromagnetycznych oscylujących jednakowo we wszystkich kierunkach prostopadłych do osi propagacji światła. Żeby dokonać selekcji fal elektromagnetycznych, których wektor natężenia pola oscyluje w wybranym przez nas kierunku, stosujemy polaryzator. Przepuszczając niespolaryzowane światło przez polaryzator liniowy dokonujemy jego polaryzacji. Jeśli za polaryzatorem liniowym umieścilibyśmy kolejny podobny polaryzator, jednakże z osią polaryzacji ustawioną prostopadle do tej pierwszej, dokonalibyśmy całkowitego wygaszenia światła. Zachęcam do przeprowadzenia tego prostego eksperymentu np. pozyskując dwa polaryzatory liniowe z powierzchni wyświetlaczy ciekłokrystalicznych zepsutego zegarka lub kalkulatorka.

Zgodnie z regułą dodawania wektorów, każdą falę elektromagnetyczną można zapisać jako sumę dwóch fal elektromagnetycznych, prostopadłych do siebie w płaszczyźnie polaryzacji. Czyli inaczej, każdą polaryzację liniową światła można opisać jako superpozycję dwóch normalnych względem siebie polaryzacji, nazwijmy je horyzontalną H (ang. horizontal) oraz wertykalną V (ang. vertical).

Przeprowadźmy teraz następujący eksperyment myślowy. Załóżmy, że dysponujemy źródłem światła niespolaryzowanego oraz zestawem płytek półprzepuszczalnych tłumiących światło. Ustawiające je kolejno na osi optycznej, możemy doprowadzić do sytuacji w której przez zestaw płytek przedostawać się będą jedynie pojedyncze fotony. Możemy w tym miejscu zapytać co się stanie gdy pojedynczy foton napotka polaryzator światła? Okazuje się, że foton taki z pewnym prawdopodobieństwem może przejść przez polaryzator, jak również z pewnym prawdopodobieństwem może zostać przez niego zatrzymany. Jest to konsekwencją kwantowej natury fotonu, co przejawia się istnieniem fotonu w stanie kwantowym $|\Psi \rangle$ , będącym superpozycją kwantową dwóch polaryzacji, co zapisujemy jako:

$|\Psi \rangle = \alpha |H \rangle +\beta |V \rangle$ ,

tak, że $|\alpha |^2+|\beta|^2=1$ . Prawdopodobieństwo znalezienia fotonu w stanie $|H \rangle$ równe jest $P(H)=|\alpha|^2$ , natomiast prawdopodobieństwo znalezienia fotonu w stanie $|V \rangle$ równe jest $P(V)=|\beta|^2$ . Stany bazowe $|H \rangle$ i $|V \rangle$ odpowiadają dwóm prostopadłym względem siebie polaryzacjom. Tak więc, polaryzacja światła ma swoje źródło na poziomie pojedynczych fotonów i związana jest z tym, że są one bezmasowymi bozonami o spinie 1. Dla cząstek takich istnieją dwa możliwe rzuty wektora momentu pędu na kierunek jego propagacji. Te dwa stany tak zwanej skrętności (ang. helicity) fotonów, na poziomie klasycznym, odpowiadają dwóm możliwym polaryzacjom kołowym światła (lewoskrętnej i prawoskrętnej). Stany o polaryzacji lewoskrętnej i prawoskrętnej są superpozycjami stanów o polaryzacji liniowej:

$| L \rangle = \frac{1}{\sqrt{2}}\left(|H \rangle - i |V \rangle \right)$ oraz $| R \rangle = \frac{1}{\sqrt{2}}\left(|H \rangle + i |V \rangle \right)$ .

Fakt, że foton jest opisywany przez kwantową superpozycję dwóch stanów bazowych, czyli jego stan należy do dwuwymiarowej przestrzeni Hilberta ma ogromne znaczenie z punktu widzenia kwantowej teorii informacji. A mianowicie, foton może być wykorzystany jako nośnik najmniejszej porcji informacji kwantowej, tak zwanego kubitu. Z tego też powodu możemy utożsamić stany polaryzacji fotonu ze stanami bazowymi kubitu: $|H \rangle = |0 \rangle$ oraz $|V \rangle = |1 \rangle$ . Oznaczmy tę bazę jako $\mathcal{B}_1 = \{ |0 \rangle, |1 \rangle \}$ .

Do przeprowadzenia kwantowej dystrybucji klucza, w ramach protokołu BB84, będziemy potrzebowali wprowadzić jeszcze jedną bazę. Mianowicie, $\mathcal{B}_2 = \{ |+ \rangle, |- \rangle \}$ , gdzie stany bazowe wyrażają się jako następujące superpozycje:

$|+ \rangle = \frac{1}{\sqrt{2}} \left( | 0 \rangle +| 1 \rangle \right)$ oraz $|- \rangle = \frac{1}{\sqrt{2}} \left( | 0 \rangle -| 1 \rangle \right)$ .

Jeśli stany bazowe $|0 \rangle$ i $|1 \rangle$ opisują stany polaryzacji pod kątami odpowiednio $0^{\circ}$ i $90^{\circ}$ to stany polaryzacji $|+ \rangle$ i $|- \rangle$ opisują polaryzacje liniowe odpowiednio pod kątami $45^{\circ}$ i $-45^{\circ}$ . Warto w tym miejscu również zaznaczyć, że stany $|0 \rangle$ i $|1 \rangle$ są stanami własnymi operatora $\hat{Z}$ do wartości własnych $+1$ i $-1$ odpowiednio. Natomiast, stany $|+ \rangle$ i $|- \rangle$ są stanami własnymi operatora $\hat{X}$ odpowiednio do wartości własnych $+1$ i $-1$ (operatory $\hat{Z}$ i $\hat{X}$ odpowiadają macierzom Pauliego $\sigma_z$ i $\sigma_x$ ). Wszystkie z wprowadzonych tu stanów bazowych można wytworzyć przepuszczając foton przez polaryzator liniowy ustawiony pod jednym z czterech kątów. Ponadto, powyższy dobór baz nie jest przypadkowy i wynika z faktu, że bazy $\mathcal{B}_1$ i $\mathcal{B}_2$ są przykładem tak zwanych wzajemnie nieobciążonych baz (ang. mutually unbiased bases), spełniających warunek:

$|\langle \psi | \phi \rangle |^2 = \frac{1}{2}$ ,

gdzie $| \psi \rangle \in \mathcal{B}_1$ a $| \phi \rangle \in \mathcal{B}_2$ . Oznacza to, że bazy te wykluczają się w sposób maksymalny, uniemożliwiając jednoczesne wykonywanie pomiarów na kubicie w obydwu bazach. W przypadku fotonu ma to następujące konsekwencje: Jeśli przygotujemy foton np. w stanie bazowym $|0 \rangle$ i przepuścimy go przez analizator polaryzacji pod kątami $0^{\circ}$ i $90^{\circ}$ (odpowiadających stanom polaryzacji bazy $\mathcal{B}_1$ ), to po przejściu przez taki analizator nie nastąpi zmiana stanu fotonu. Jednakże, jeśli na drodze tego samego fotony umieścimy analizator polaryzacji pod kątami $45^{\circ}$ i $-45^{\circ}$ (odpowiadających stanom polaryzacji bazy $\mathcal{B}_2$ ), to po przejściu przez taki analizator foton z prawdopodobieństwem $1/2$ znajdzie się w stanie o polaryzacji $|+ \rangle$ i z takim samym prawdopodobieństwem w stanie o polaryzacji $|- \rangle$ . Jeśli foton ten będziemy chcieli zaś ostatecznie przeanalizować wykorzystując analizator ze stanami polaryzacji odpowiadającymi bazie $\mathcal{B}_1$ to z prawdopodobieństwem $1/2$ zaobserwujemy ten foton w stanie $|0 \rangle$ i z prawdopodobieństwem $1/2$ w stanie $|1 \rangle$ (taki sam wynik uzyskalibyśmy jeśli foton byłbym przygotowany w stanie $|1 \rangle$ ). Próba przeanalizowania stanu fotonu we wzajemnie obciążonej bazie wprowadza więc maksymalną niepewność co do stanu początkowego. Własność ta znajduje bezpośrednie zastosowanie w protokole BB84.

Przyjdźmy więc do jego omówienia. Rozważamy nadawcę (A) i odbiorcę (B) których zwyczajowo określamy mianem Alicji i Boba. Alicja ma za zadanie przesłać do Boba klucz (ciąg bitów) wykorzystując stany polaryzacji fotonu. Ma ona do dyspozycji 4 stany polaryzacji fotonu odpowiadające stanom bazowym baz $\mathcal{B}_1$ i $\mathcal{B}_2$ . Klucz stanowi losowy ciąg binarny $0$ i $1$ , który można wygenerować np. wykorzystując kwantowy generator liczb losowych (z artykułu arXiv:1405.0453 można dowiedzieć się jak samemu zbudować taki generator w oparciu o smartfon). Alicja wprowadza następujące kodowanie klasycznych bitów klucza za pomocą kwantowych stanów polaryzacji fotonu. Mianowicie, stany polaryzacji $|0 \rangle$ i $|+ \rangle$ kodują $0$ , natomiast stany polaryzacji $|1 \rangle$ i $|- \rangle$ kodują $1$ . W praktyce, generacja klucza odbywa się przez losowe ustalanie jednej z czterech pozycji polaryzatora Alicji (rysunek poniżej).

qbejE — Przykładowa realizacja protokołu BB84. Źródło

Przesyłane od Alicji spolaryzowane fotony Bob będzie rejestrował za pomocą analizatora który może przyjmować takie same orientacje jak polaryzator Alicji. Stany polaryzatora Alicji nie są publiczne, Bob będzie więc dokonywał analizy polaryzacji fotonów w (wybieranych losowo) bazach $\mathcal{B}_1$ i $\mathcal{B}_2$ . Na podstawie swoich pomiarów, odzyska on pewien ciąg bitów. Następnym krokiem jest publiczne ogłoszenie przez Boba stanów analizatora (baz) w których dokonywał on kolejnych pomiarów. Warto tu podkreślić, że oczywiście nie upublicznia on samych wyników pomiarów. W ramach danej bazy możliwe są wciąż dwie wartości bitu, wartość klucza pozostaje więc ukryta. Następuje teraz tak zwane uzgodnienie baz (ang. basis reconciliation). Mianowicie, Alicja informuje Boba które użyte przez niego bazy są zgodne ze stanami polaryzacji w których przygotowała ona sekretny klucz. Zdekodowane przez Boba, dla uzgodnionych baz, wartości bitów stanowią sekretny klucz. Ostatnim etapem protokołu jest zweryfikowanie czy nie nastąpiła próba “podsłuchania” przesyłanych kanałem kwantowym informacji.

Omówienie tej kwestii zacznijmy od wyartykułowania jednej z fundamentalnych własności mechaniki kwantowej. Mianowicie, nie jest możliwe idealne skopiowanie nieznanego stanu kwantowego. Nie jest więc możliwe “podłączenie się” do kanału kwantowego i skopiowanie przesyłanej informacji. Własność ta jest ucieleśniona w twierdzeniu o zakazie klonowania, którego dowód dla przypadku kubitów przedstawiam poniżej.

Twierdzenie o zakazie klonowania (ang. no-cloning theorem) leży u podstaw bezwarunkowego bezpieczeństwa protokołów kryptografii kwantowej. Mówi ono, że nie jest możliwe wykonanie dokładnej kopii (klonu) nieznanego stanu kwantowego. Sformułowanie tego twierdzenia zawdzięczamy Williamowi Woottersowi oraz Wojciechowi Żurkowi [Ref]. Poniżej przedstawię jego dowód, dla przypadku stanu kubitu.

Rozważmy stan kwantowy $|\Psi \rangle = \alpha | 0 \rangle + \beta | 1 \rangle$ . Naszym celem będzie próba skopiowania tego stanu, czyli chcemy aby pewien inny stan, nazwijmy go $|\Phi \rangle$ , przetransformować (“nadpisać”) w stan $|\Psi \rangle$ , nie zmieniając jednocześnie stanu $|\Psi \rangle$ . Rozważamy więc wyjściowo stan będący następujacym iloczynem tensorowym: $|\Psi \rangle \otimes |\Phi \rangle$ . Ponadto, wprowadźmy (unitarny) operator kopiujący, nazwijmy go $\hat{K}$ , którego działanie powinno być następujące: $\hat{K}(|\Psi \rangle \otimes |\Phi \rangle)=|\Psi \rangle \otimes |\Psi \rangle$ , dla dowolnego stanu $|\Psi \rangle$ . Żeby sprawdzić czy jest to możliwe, zadziałajmy najpierw operatorem $\hat{K}$ na stany bazowe $| 0 \rangle$ i $| 1 \rangle$ . Działanie operatora $\hat{K}$ powinno dawać $\hat{K}(|0 \rangle \otimes |\Phi \rangle)=|0\rangle \otimes |0 \rangle$ oraz $\hat{K}(|1 \rangle \otimes |\Phi \rangle)=|1\rangle \otimes |1 \rangle$ . Zakładając, że powyższe jest spełnione, spróbujmy przeprowadzić kopiowanie stanu $|\Psi \rangle = \alpha | 0 \rangle + \beta | 1 \rangle$ . Skorzystamy w tym miejscu z własności liniowości operatorów rozważanych w mechanice kwantowej (czyli np. $\hat{O}(|a\rangle+|b\rangle)=\hat{O}(|a\rangle)+\hat{O}(|b\rangle)$ , dla dowolnych stanów $|a\rangle$ i $|b\rangle$ ). W konsekwencji, otrzymujemy:

$\hat{K}(|\Psi \rangle \otimes |\Phi \rangle) = \hat{K}((\alpha | 0 \rangle + \beta | 1 \rangle) \otimes |\Phi \rangle) = \alpha \hat{K}(|0 \rangle \otimes |\Phi \rangle)+\beta \hat{K}(|1 \rangle \otimes |\Phi \rangle) = \alpha |0\rangle \otimes |0 \rangle + \beta |1\rangle \otimes |1 \rangle$ .

Stan końcowy jakiego jednak oczekiwalibyśmy w wyniku kopiowania (klonowania) to:

$|\Psi \rangle \otimes |\Psi \rangle = (\alpha |0\rangle + \beta |1\rangle)\otimes (\alpha |0\rangle + \beta |1\rangle) = \alpha^2 |0\rangle \otimes|0\rangle + \alpha \beta |0 \rangle \otimes|1\rangle + \alpha\beta|1\rangle \otimes|0\rangle + \beta^2 |1\rangle \otimes|1\rangle$ ,

który jest odzyskiwany tylko w szczególnych przypadkach stanów bazowych, tzn. kiedy $\alpha=1$ i $\beta=0$ lub $\alpha=0$ i $\beta=1$ . Powyższa analiza dowodzi tego, że nie jest możliwe skopiowanie nieznanego stanu kubitu. Przeprowadzenie dowodu dla przypadku dowolnego stanu $|\Psi \rangle$ pozostawiam Czytelnikowi jako ćwiczenie.

Pomimo zakazu klonowania stanów kwantowych, istnieją pewne strategie ataków na protokoły kryptografii kwantowej. Np. podsłuchujący (nazwijmy ją Ewa) może ustawić na drodze optycznej fotonu analizator i próbować odczytać pewne bity klucza. Jak to już jednak dyskutowaliśmy powyżej, obecność takiego analizatora w sposób nieodłączny wiąże się z wpłynięciem na stany fotonu. W celu wyeliminowania możliwości podsłuchu, Alicja i Bob porównują publicznie część klucza. Jeśli w wybranym ciągu bitów nie zauważą różnić, mają pewność, że nie nastąpiła próba ataku. Oczywiście, w praktyce mogą występować pewne różnice w ciągu bitów wynikające z występowaniem szumu, generującego pewien poziom błędów. Istnieje jednak metoda dokładnego określenia jaki poziom niezgodności porównywanego ciągu bitów jest dopuszczalny dla zachowania poufności wymiany klucza. Metoda ta opiera się na wykorzystaniu teorii informacji i pozwolę sobie zarysować jej uproszczoną postać. Zacznijmy od odpowiedzi na pytanie jak dużo błędów do odczytywanego przez Boba ciągu bitów będzie wprowadzał ustawiony przez Ewę, na drodze fotonu, analizator. Analizator ten może być dostosowany do bazy $\mathcal{B}_1$ lub $\mathcal{B}_2$ . Prosta probabilistyka mówi nam, że prawdopodobieństwo nie zaburzenia przez Ewę pojedynczego bitu przesyłanego klucza wynosi:

$P= \frac{1}{2}\cdot \frac{1}{2}+\frac{1}{2}\cdot 1 = \frac{3}{4}$ .

Czyli, starająca się wykraść sekretny klucz Ewa, w 25 % przypadków wprowadzi błąd do przesyłanego ciągu bitów. Ponadto, ponieważ z prawdopodobieństwem $1/2$ analizuje ona foton we właściwej bazie, z takim też prawdopodobieństwem odczyta ona poprawnie wartość przesyłanego bitu. Ponieważ, wyjściowo, nie zna ona ustawień polaryzatora Alicji, nie jest ona jednak w stanie stwierdzić który bit odczytała prawidłowo a który nie. Odkodowania połowy przesyłanych bitów klucza może dokonać jedynie poznawszy (post factum) ustawienia polaryzatora Alicji. Może to więc zrobić dla bitów dla których następuje sprawdzenie klucza przez Alicję i Boba.

Do skwantyfikowania ilości błędów wprowadzanych podczas kwantowej transmisji informacji używa się wielkości zwanej QBER (Quantum Bit Error Rate) – $e$ która zdefiniowana jest jako stosunek liczby kubitów z błędem ( $N_e$ ) względem całkowitej liczby przesyłanych kubitów $N$ :

$e := \frac{N_e}{N}$ .

Jeśli przez $f \in [0,1]$ oznaczymy część kubitów analizowanych przez Ewę, to wprowadzany przez Nią QBER wynosi $e = \frac{1}{4} f$ , gdzie czynnik $1/4$ wynika z przeprowadzonych powyżej rozważań probabilistycznych. Przywołajmy teraz pojęcie informacji wzajemnej (ang. mutual information), która pozwoli nam skwantyfikować jaka część informacji jest tracona w kanale kwantowym w wyniku ataków Ewy. Jak można pokazać, wzajemna informacja pomiędzy Alicją a Bobem wyraża się jako

$I(A : B) = 1 - h(e)$ , gdzie $h(e) = -e \log_2 e - (1-e) \log_2 (1-e)$

to tak zwana entropia informacyjna Shannona. Wzajemna informacja pomiędzy Alicją a Ewą wynosi zaś

$I(A : E) = \frac{1}{2}f = 2e$ ,

co wynika z faktu, iż Ewa (znając położenie polaryzatorów Ewy) jest w stanie teoretycznie odzyskać wartości połowy “podsłuchiwanych” przez Nią bitów. Jeśli informacja w układzie Alicja-Ewa $I(A : E)$ zaczyna być większa niż pomiędzy Alicją i Bobem $I(A : B)$ , przesyłanie klucza przestaje być bezpieczne. Na tej podstawie, rozpatrując warunek graniczny $I(A : E)=I(A : B)$ , otrzymujemy, że (przy powyższych założeniach) bezpieczeństwo kwantowej dystrybucji klucza zapewnione jest jeśli poziom błędów $e$ jest mniejszy niż około $17 \%$ . Jeśli, porównując wybrane bity klucza, Alicja i Bob zanotują różnicę na wyższym poziomie, nie można zaakceptować przesyłanego klucza i należy powtórzyć całą procedurę.

Przeprowadzona powyżej analiza ma znaczenie praktyczne i znajduje zastosowanie w istniejących systemach do kwantowej dystrybucji klucza. Na rynku istnienie obecnie kilka zestawów które pozwalają przeprowadzić KDK wykorzystując protokoły oparte na superpozycji kwantowej. Na rysunku poniżej przedstawiono przykładowy zestaw wykorzystujący zmodyfikowaną wersję protokołu BB84, tzw. protokół T12.

ToshibaQKD — Przykładowy dostępny komercyjnie zestaw do kwantowej dystrybucji klucza. Źródło

Do przesyłania fotonów, dostępne komercyjnie systemy kryptografii kwantowej stosują światłowody. Niepożądaną cechą takiego rozwiązania jest jednak wykładnicze tłumienie natężenia światła w funkcji przebytego przez światło dystansu. Z uwagi na twierdzenie o zakazie klonowania oraz na fakt posługiwania się w kwantowej dystrybucji klucza pojedynczymi fotonami, nie jest możliwe stosowanie klasycznych wzmacniaczy sygnału. Dlatego też, kwantowa dystrybucja klucza za pośrednictwem światłowodów jest dzisiaj ograniczona do odległości poniżej około 400 km.

BitRate — Wykładniczy zanik przepustowości kwantowej dystrybucji klucza w funkcji odległości. Źródło

Wraz z długością linii transmisyjnej spada jej przepustowość. Na bardzo krótkich dystansach osiągane są obecnie wartości około 10 Mb/s (arXiv:1807.04484). Na odległościach rzędu 50 km wartość ta spada już do około 1 Mb/s. Natomiast, nieubłagana natura zaniku eksponencjalnego sprawia, że na dystansach około 400 km KDK można przeprowadzać w tempie jedynie około 1 bitu na sekundę (co jest wielkością niepraktyczną).

Możliwym rozwiązaniem dla powyższych trudności jest stosowanie powielaczy kwantowych (ang. quantum repeater). Są to jednakże bardzo złożone systemy, będące wciąż w fazie badań. Dużo bardziej obiecującym rozwiązaniem jest wykorzystanie faktu jedynie odwrotnego z kwadratem odległości zaniku natężenia światła w próżni, oraz dużo słabszego niż w ciele stałym tłumienia fotonów w gazach. Rozwiązanie to wiąże się z wykorzystaniem przestrzeni kosmicznej do przeprowadzenia kwantowej dystrybucji klucza. Możliwość taka została pomyślnie potwierdzona eksperymentalnie na skalach międzykontynentalnych w 2017 roku z wykorzystaniem protokołu BB84. Zagadnienie to opisuję bardziej szczegółowo we wpisie Kwantowa łączność satelitarna.

Kryptowaluty-Kwanty-Kosmos

August 11, 2018July 17, 2019 jakub mielczarek2 Comments

Świat zachłysnął się cyfrowym złotem – kryptowalutami. Bitcoin i technologia Blockchain stały się, w mgnieniu oka, częścią naszej codzienności. Choć jeszcze dosłownie kilka lat temu były to nazwy znane głównie entuzjastom nowych technologii oraz postępowym inwestorom. Obecnie, zainteresowanie rynkiem kryptowalut jest ogromne, a sięgające nawet kilkuset procent w skali roku wzrosty kursów kryptowalut wabią okazją zbicia fortuny.

Nie mniej emocji dostarcza nam obecny renesans w eksploracji kosmosu (tzw. NewSpace). Takie momenty jak symultaniczne lądowanie odzyskiwanych po stracie rakiety Falcon Heavy stopni pomocniczych to sceny niczym z filmów science fiction. Spektakularność tych wyczynów pobudza wyobraźnię nie tylko pasjonatów kosmosu, ale i inwestorów, przyśpieszając otwarcie przestrzeni kosmicznej dla coraz ambitniejszych wyzwań. Trochę w cieniu Blockchainu i NewSpace, rozgrywa się obecnie jeszcze jedna niezwykle ważna technologiczna rewolucja, nie robiąca może tyle huku co start rakiety ani nie hipnotyzująca tak jak cyfrowe złoto, ale za to gruntownie transformująca informacyjną tkankę naszego świata. Chodzi mianowicie o przeskok od obecnej fazy przetwarzania informacji klasycznej (bity) do epoki informacji kwantowej (qubity). Nowe technologie kwantowe, bo za ich sprawą ma to miejsce, wpłyną na dalszy rozwój zarówno kryptowalut jak i technologii kosmicznych. Możemy sformułować nawet śmielszą tezę: rozwiązania, które zrodzą się na przecięciu tych trzech obszarów (kryptowalut, technologii kwantowych i eksploracji kosmosu), zrewolucjonizują każdy z nich z osobna jak i wygenerują zupełnie nową jakość.

Ale po kolei. Kryptowaluty opierają się na rozproszonym systemie księgowym typu peer-to-peer, zaproponowanym w artykule Bitcoin: A Peer-to-Peer Electronic Cash System. W rozwiązaniu takim, w przeciwieństwie do standardowych systemów finansowych, nie istnieje centralny podmiot autoryzujący, np. bank. Poprawność obrotu kryptowalutą zapewniona jest natomiast poprzez decentralizację oraz szereg zabezpieczeń kryptograficznych. Należy do nich, w szczególności, podpis elektroniczny za pomocą którego składane są dyspozycje transakcji. Jest to przykład tak zwanej kryptografii asymetrycznej, w której istnieją dwa typy klucza: prywatny oraz publiczny. Wykonanie transakcji wiąże się z podpisaniem, za pomocą klucza prywatnego, dyspozycji transakcji i następnie jej autoryzowanie przez innych użytkowników sieci, na postawie znajomości klucza publicznego. Dokładnie tak samo jak w przypadku składania podpisu elektronicznego. Siła takiego zabezpieczenia opiera się na dużej złożoności obliczeniowej związanej z odtworzeniem postaci klucza prywatnego na podstawie znajomości klucza publicznego. W przypadku Bitcoina, wykorzystywany jest w tym celu algorytm ECDSA (Elliptic Curve Digital Signature Algorithm). Jest on odporny na ataki prowadzone przez komputery klasyczne. Natomiast, okazuje się, że dla uniwersalnych komputerów kwantowych problem ten przestaje być aż tak trudny. Mianowicie, do znalezienia klucza prywatnego (w kryptografii bazującej na ECDSA) możliwe jest zastosowanie zmodyfikowanego kwantowego algorytmu faktoryzacji Shora. Niedawna publikacja Quantum attacks on Bitcoin, and how to protect against them sugeruje, że postęp w rozwoju komputerów kwantowych może umożliwić łamanie obecnych zabezpieczeń opartych o ECDSA już za niespełna 10 lat.

Utrzymanie zdecentralizowanej struktury Blockchainu, na której opary jest Bitcoin, wymaga pracy tak zwanych górników (minerów). Zapłatą za wkład ich mocy obliczeniowej w utrzymywanie systemu są Bitcoiny. Żeby jednak je otrzymać, należy rozwiązać zadanie oparte o tak zwaną funkcję haszującą SHA-256, opracowaną przez National Security Agency. W celu rozwiązania zadania, konieczne jest zbadanie wartość funkcji haszujacej dla bardzo dużej ilości różnych wartości jej argumentu. Jest to, dla komputerów klasycznych, niezwykle żmudne zadanie (energia elektryczna przeznaczana obecnie na tę czynność, tylko w przypadku Bitcoinu, wynosi w skali roku ponad 70 TWh, co jest porównywalne z konsumpcją energii elektrycznej Austrii). Okazuje się jednak, że zadanie to jest jednym z tych z którymi doskonale radzą sobie algorytmy kwantowe. Otóż, można w tym przypadku wykorzystać jeden z najbardziej znanych algorytmów kwantowych, tak zwany algorytm Grovera. Pozwala on zredukować złożoność obliczeniową procesu poszukiwania argumentu funkcji haszującej do pierwiastka kwadratowego z liczby dozwolonych argumentów.

Możemy więc dojść do wniosku, że rozwój technologii kwantowych, w szczególności uniwersalnych komputerów kwantowych (takich jak np. IBM Q), stanowi zagrożenie dla zabezpieczeń na których opierają się obecne kryptowaluty. Z drugiej strony jednak, technologie kwantowe pozwalają również ulepszyć systemy takie jak Blockchain. Miedzy innymi, klasyczne zabezpieczenia kryptograficzne mogą zostać zastąpione przez odpowiednie rozwiązania kryptografii kwantowej. Do najważniejszych z nich należą: kwantowe generatory kluczy oraz tak zwana Kwantowa Dystrybucja Klucza (KDK).

KDK opiera się na takich własnościach mechaniki kwantowej jak zaburzenie stanu układu kwantowego poprzez pomiar i tak zwany zakaz klonowania stanów kwantowych. Na tej podstawie, protokoły kwantowej dystrybucji klucza są w stanie wykryć każdą próbę wykradzenia informacji. Stanowią więc wręcz idealną metodę zabezpieczenia wymiany klucza prywatnego, eliminując tym samym potrzebę stosowania kryptografii asymetrycznej. Warto podkreślić, że KDK osiągnęła poziom technologii dostępnej komercyjnie. Jednakże, jej stosowanie na dużych odległościach (rzędu kilkuset kilometrów) wciąż stanowi wyzwanie. Wiąże się to z koniecznością przesyłania pojedynczych fotów, w których stanach kwantowych zakodowany jest klucz prywatny. Można w tym celu zastosować światłowód. Nie jest to jednak rozwiązanie optymalne gdyż, z uwagi na zakaz klonowania stanów kwantowych, wzmacnianie sygnału przesyłanego tą drogą jest trudnym zadaniem. Żeby zniwelować straty w przesyłanym sygnale, niezbędne jest zastosowanie tak zwanych kwantowych powielaczy, realizujących protokół teleportacji kwantowej. Z uwagi na złożoność techniczną takiego rozwiązania, dużo łatwiejsze okazuje się przesyłanie pojedynczych fotonów w powietrzu lub w próżni. W konsekwencji, jedyny dostępny dzisiaj sposób przeprowadzania kwantowej dystrybucji klucza na odległościach międzykontynentalnych opiera się na wykorzystaniu przestrzeni kosmicznej.

Prace nad takim rozwiązaniem prowadzono już od dłuższego czasu. Ostatecznie, udało się tego dokonać w ubiegłym roku przez chińsko-austriacki zespół naukowców i inżynierów. Wyniki przeprowadzonej na dystansie 7600 km, pomiędzy stacjami w Chinach i Austrii, kwantowej dystrybucji klucza opublikowano w styczniu bieżącego roku na łamach Physical Review Letters [arXiv:1801.04418]. Do zrealizowania kwantowej transmisji wykorzystano satelitę Micius, stanowiącą jednostkę zaufaną dystrybuującą klucz prywatny w protokole BB84 (Bennett-Brassard 1984). Szczegóły tego eksperymentu omawiam w artykule Kwantowa łączność satelitarna.

Sukces chińskiego projektu dowodzi możliwości globalnego wykorzystania kwantowych protokołów kryptograficznych. Otwiera on również drogę do dalszego rozwoju tej technologii, zarówno do celów militarnych jak i komercyjnych. Jedną z niewątpliwie najbardziej fascynujących możliwości jest stworzenie tak zwanego kwantowego internetu:

Kwantowy internet zapewni bezpieczeństwo pracy systemów finansowych. W szczególności, umożliwi rozszerzenie technologii Blockchain do przypadku kwantowego (zabezpieczanego przez KDK). Propozycja takiej modyfikacji technologii Blockchain została niedawno opisana w artykule Quantum-secured blockchain. Internet kwantowy umożliwi również wdrożenie pochodnych do dyskutowanych już na początku lat osiemdziesiątych koncepcji kwantowego pieniądza. W szczególności, takich jak propozycja Weisnera, w której pieniądz jest pewnym stanem kwantowym (np. sekwencją qubitów). Niepodrabialność kwantowego banknotu wynika wprost z zakazu klonowania (nieznanego) stanu kwantowego. Warto zaznaczyć, że realizacja kwantowego pieniądza opartego o propozycję Weisnera została doświadczalnie zademonstrowana w 2016-tym roku przez polsko-czeski zespół fizyków kwantowych i opisana w artykule Experimental quantum forgery of quantum optical money, opublikowanym w Nature. Po więcej informacji na temat kwantowych pieniędzy zachęcam sięgnąć do artykułu Quantum Money.

Quantum-banknote — Kwantowy banknot Weisnera zawierający nieznany użytkownikowi stan kwantowy (np. sekwencja qubitów) oraz numer seryjny. Weryfikacja banknotu (zgodność stanu kwantowego z nadanym numerem seryjnym) następuje poprzez jego przesłanie do instytucji emitującej (mennicy). Źródło

Kwantowo zabezpieczone kryptowaluty czy też kwantowe pieniądze będą mogły, dzięki satelitarnemu internetowi kwantowemu, tworzyć globalny system walutowy. Dzięki wykorzystaniu i tak już stosowanej do tego celu przestrzeni kosmicznej, nie będzie stanowiło żadnego problemu by rozszerzyć obszar obejmowany kwantową siecią poza powierzchnię Ziemi. Nie ma przecież lepszego medium do przesyłania stanów kwantowych niż próżnia.

Ludzie przebywający w kosmosie, czy to na orbicie okołoziemskiej czy też w planowanych stacjach na Księżycu oraz na Marsie, będą mogli dokonywać płatności korzystając z kwantowo zabezpieczonych kryptowalut. Będą oni mogli korzystać również z pozafinansowych zastosowań kwantowej wersji technologii Blockchain, np. w telemedycynie.

Od strony możliwości technicznych, takie wizje stają się dzisiaj jak najbardziej wykonalne. Idąc dalej, naturalnym wydaje się wykorzystanie w przyszłości przestrzeni kosmicznej jako miejsca do przechowywania i przetwarzania informacji kwantowej. Stany kwantowe, będące nośnikiem informacji kwantowej ulegają, poprzez oddziaływanie ze środowiskiem, dekoherencji która stanowi jedną z największych przeszkód w rozwoju technologii kwantowych. Warunki wysokiej próżni i niskich temperatur, redukujące proces dekoherencji, powszechnie występują w przestrzeni kosmicznej. Z tego powodu, możliwe jest więc, że przyszłe centra przetwarzania i magazynowania informacji kwantowej, np. skarbce kwantowych pieniędzy, będą ulokowane nie na Ziemi lecz ukryte zostaną w takich miejscach jak jaskinie lawowe na Księżycu.

Jakub Mielczarek

Theoretical physicist looking into the future

Tag: Kryptologia

Pierwsze standardy kryptografii postkwantowej

Po co nam kryptografia postkwantowa?

Konkursy NIST

Postkwantowi zwycięzcy

Kontrowersje na finiszu

Czwarta runda

Co z kryptografią symetryczną?

Co dalej?

Referencje

Kosmiczny Szyfr

Jak odzyskać informację z szyfru?

Szyfry w naturze

Wszechświat jako Kosmiczny Szyfrator

Hakowanie satelitów

Bibliografia

Rozpinanie kwantowej sieci

Bibliografia

Technologie kwantowe a cyberbezpieczeństwo

Kwantowa dystrybucja klucza

Kryptowaluty-Kwanty-Kosmos