Rozmiar klucza - Key size
W szyfrowania , klucz wielkości , długości klucza albo kluczy, odnoszą się do liczby bitów w klucza używanego przez kryptograficznego algorytmu (na przykład jako szyfru ).
Długość klucza określa górną granicę bezpieczeństwa algorytmu (tj. logarytmiczną miarę najszybszego znanego ataku na algorytm), ponieważ bezpieczeństwo wszystkich algorytmów może zostać naruszone przez ataki siłowe . Idealnie, dolna granica bezpieczeństwa algorytmu jest z założenia równa długości klucza (to znaczy, że bezpieczeństwo jest całkowicie określone przez długość klucza lub innymi słowy, konstrukcja algorytmu nie umniejsza stopnia bezpieczeństwa związanego z długość klucza). Rzeczywiście, większość algorytmów z kluczem symetrycznym zaprojektowano tak, aby zapewnić bezpieczeństwo równe długości ich klucza. Jednak po zaprojektowaniu może zostać odkryty nowy atak. Na przykład potrójny DES został zaprojektowany tak, aby mieć 168-bitowy klucz, ale obecnie znany jest atak o złożoności 2 112 (tj. potrójny DES ma teraz tylko 112 bitów bezpieczeństwa, a ze 168 bitów w kluczu, które atak spowodował, 56 „nieskuteczne” wobec bezpieczeństwa). Niemniej jednak, o ile zabezpieczenia (rozumiane jako „nakład pracy potrzebny do uzyskania dostępu”) są wystarczające dla określonej aplikacji, nie ma znaczenia, czy długość klucza i zabezpieczenia są zbieżne. Jest to ważne w przypadku algorytmów z kluczem asymetrycznym , ponieważ żaden taki algorytm nie jest znany z tej właściwości; Kryptografia krzywych eliptycznych jest najbliższa ze skutecznym zabezpieczeniem wynoszącym mniej więcej połowę długości klucza.
Znaczenie
Przyciski służą do sterowania pracą szyfr tak, że tylko prawidłowa klucz może konwertować zaszyfrowanego tekstu ( szyfrogram ) do zwykłego tekstu . Wiele szyfrów jest faktycznie opartych na powszechnie znanych algorytmach lub jest typu open source, więc tylko trudność w uzyskaniu klucza decyduje o bezpieczeństwie systemu, pod warunkiem, że nie ma ataku analitycznego (tj. „słabości strukturalnej” w algorytmach lub protokołach używany) i zakładając, że klucz nie jest dostępny w inny sposób (np. poprzez kradzież, wymuszenie lub włamanie do systemów komputerowych). Powszechnie akceptowany pogląd, że bezpieczeństwo systemu powinno zależeć od samego klucza, sformułowali wprost Auguste Kerckhoffs (w latach 80. XIX wieku) i Claude Shannon (w latach 40.); twierdzenia te znane są odpowiednio jako zasada Kerckhoffsa i Maxim Shannona.
Klucz powinien zatem być na tyle duży, aby atak brute-force (możliwy przeciwko dowolnemu algorytmowi szyfrowania) był niewykonalny – tzn. jego wykonanie trwałoby zbyt długo. Praca Shannona nad teorią informacji wykazała, że aby osiągnąć tak zwaną „ doskonałą tajemnicę ”, długość klucza musi być co najmniej tak duża, jak wiadomość i być użyta tylko raz (algorytm ten nazywa się jednorazowym padem ). W świetle tego oraz praktycznych trudności w zarządzaniu tak długimi kluczami, współczesna praktyka kryptograficzna odrzuciła pojęcie doskonałej tajemnicy jako wymogu szyfrowania, a zamiast tego koncentruje się na bezpieczeństwie obliczeniowym , w ramach którego muszą być spełnione wymagania obliczeniowe łamania zaszyfrowanego tekstu. niewykonalne dla atakującego.
Rozmiar klucza i system szyfrowania
Systemy szyfrowania są często grupowane w rodziny. Wspólne rodziny obejmują systemy symetryczne (np. AES ) i systemy asymetryczne (np. RSA ); alternatywnie można je pogrupować według stosowanego algorytmu centralnego (np. kryptografia krzywych eliptycznych ).
Ponieważ każdy z nich ma inny poziom złożoności kryptograficznej, zwykle stosuje się różne rozmiary kluczy dla tego samego poziomu bezpieczeństwa , w zależności od użytego algorytmu. Na przykład zabezpieczenia dostępne z 1024-bitowym kluczem używającym asymetrycznego RSA są uważane za w przybliżeniu równe pod względem bezpieczeństwa 80-bitowemu kluczowi w algorytmie symetrycznym.
Rzeczywisty stopień bezpieczeństwa osiągany w czasie zmienia się w miarę dostępności większej mocy obliczeniowej i potężniejszych matematycznych metod analitycznych. Z tego powodu kryptolodzy mają tendencję do patrzenia na wskaźniki wskazujące, że algorytm lub długość klucza wykazuje oznaki potencjalnej podatności, aby przejść do dłuższych rozmiarów klucza lub trudniejszych algorytmów. Na przykład, w maju 2007 r. 1039-bitowa liczba całkowita została uwzględniona w specjalnym sicie z polem liczbowym przy użyciu 400 komputerów w ciągu 11 miesięcy. Faktorowana liczba miała specjalną formę; specjalne sito z polem numerycznym nie może być używane na kluczach RSA. Obliczenie jest w przybliżeniu równoważne złamaniu 700-bitowego klucza RSA. Może to jednak być ostrzeżeniem, że 1024-bitowe RSA używane w bezpiecznym handlu internetowym powinny zostać wycofane , ponieważ w najbliższej przyszłości mogą stać się możliwe do złamania. Profesor kryptografii Arjen Lenstra zauważył, że „ostatnim razem zajęło nam dziewięć lat, aby uogólnić liczbę ze specjalnej na niespecjalną, trudną do rozłożenia na czynniki”, a na pytanie, czy 1024-bitowe klucze RSA są martwe, odpowiedział: „Odpowiedź na to pytanie jest bezwarunkowym „tak”.
Atak Logjam z 2015 r. ujawnił dodatkowe niebezpieczeństwa związane z używaniem wymiany kluczy Diffie-Helman, gdy używany jest tylko jeden lub kilka popularnych 1024-bitowych lub mniejszych modułów pierwszych. Ta powszechna praktyka umożliwia narażenie dużej ilości komunikacji kosztem ataku na niewielką liczbę liczb pierwszych.
Brutalny atak
Nawet jeśli szyfr symetryczny jest obecnie niemożliwy do złamania dzięki wykorzystaniu słabości strukturalnych swojego algorytmu, możliwe jest przejście przez całą przestrzeń kluczy w tak zwanym ataku brute-force. Ponieważ dłuższe klucze symetryczne wymagają wykładniczo więcej pracy do wyszukiwania metodą brute force, wystarczająco długi klucz symetryczny sprawia, że ta linia ataku jest niepraktyczna.
W przypadku klucza o długości n bitów możliwe są 2 n kluczy. Ta liczba rośnie bardzo szybko wraz ze wzrostem n . Duża liczba operacji (2 128 ) wymaganych do wypróbowania wszystkich możliwych 128-bitowych kluczy jest powszechnie uważana za nieosiągalną w przewidywalnej przyszłości dla konwencjonalnych technik komputerowych. Eksperci przewidują jednak alternatywne technologie komputerowe, które mogą mieć moc obliczeniową wyższą od obecnej technologii komputerowej. Jeśli komputer kwantowy o odpowiedniej wielkości, zdolny do niezawodnego działania algorytmu Grovera, stanie się dostępny, zredukuje 128-bitowy klucz do 64-bitowych zabezpieczeń, mniej więcej odpowiednik DES . Jest to jeden z powodów, dla których AES obsługuje klucz o długości 256 bitów.
Długość klucza algorytmu symetrycznego
Polityka eksportowa rządu USA od dawna ogranicza „siłę” kryptografii, którą można wysyłać z kraju. Przez wiele lat limit wynosił 40 bitów . Obecnie klucz o długości 40 bitów zapewnia niewielką ochronę nawet przed przypadkowym napastnikiem z jednym komputerem. W odpowiedzi, do roku 2000, większość głównych amerykańskich ograniczeń dotyczących używania silnego szyfrowania została złagodzona. Jednak nie wszystkie przepisy zostały usunięte, a rejestracja szyfrowania w Biurze Przemysłu i Bezpieczeństwa USA jest nadal wymagana do eksportu „masowych towarów szyfrujących, oprogramowania i komponentów z szyfrowaniem przekraczającym 64 bity” (75 FR 36494 ).
Szyfr Lucyfera IBM został wybrany w 1974 roku jako podstawa tego, co miało stać się standardem szyfrowania danych . Długość klucza Lucyfera została zmniejszona ze 128 bitów do 56 bitów , co zdaniem NSA i NIST było wystarczające. NSA ma duże zasoby obliczeniowe i duży budżet; niektórzy kryptolodzy, w tym Whitfield Diffie i Martin Hellman, skarżyli się, że czyni to szyfr tak słabym, że komputery NSA byłyby w stanie złamać klucz DES w ciągu jednego dnia za pomocą obliczeń równoległych metodą brute force. NSA zakwestionowała to, twierdząc, że brutalne DES zajęłoby im około 91 lat. Jednak pod koniec lat 90. stało się jasne, że DES można złamać w ciągu kilku dni za pomocą niestandardowego sprzętu, który może kupić duża korporacja lub rząd. Książka Cracking DES (O'Reilly and Associates) opowiada o udanej próbie złamania 56-bitowego DES w 1998 r. w wyniku brutalnego ataku zorganizowanego przez cybernetyczną grupę praw obywatelskich z ograniczonymi zasobami; zobacz krakers EFF DES . Jeszcze przed demonstracją 56 bitów uznano za niewystarczającą długość dla kluczy algorytmu symetrycznego ; DES został zastąpiony w wielu aplikacjach przez Triple DES , który ma 112 bitów bezpieczeństwa przy użyciu 168-bitowych kluczy (potrójny klucz). W 2002 roku Distributed.net i jego ochotnicy złamali 64-bitowy klucz RC5 po kilku latach starań, używając około siedemdziesięciu tysięcy (głównie domowych) komputerów.
Opublikowany w 2001 r. Advanced Encryption Standard wykorzystuje klucze o rozmiarach 128, 192 lub 256 bitów. Wielu obserwatorów uważa, że 128 bitów jest wystarczające w przewidywalnej przyszłości dla algorytmów symetrycznych o jakości AES , dopóki komputery kwantowe nie staną się dostępne. Jednak od 2015 r. Amerykańska Agencja Bezpieczeństwa Narodowego wydała wytyczne, że planuje przejść na algorytmy odporne na obliczenia kwantowe i teraz wymaga 256-bitowych kluczy AES dla danych sklasyfikowanych jako ściśle tajne .
W 2003 r. amerykański Narodowy Instytut Standardów i Technologii, NIST zaproponował wycofanie kluczy 80-bitowych do 2015 r. W 2005 r. klucze 80-bitowe były dozwolone tylko do 2010 r.
Od 2015 r. wytyczne NIST mówią, że „używanie kluczy, które zapewniają mniej niż 112 bitów siły bezpieczeństwa do uzgadniania kluczy, jest teraz zabronione”. Algorytmy szyfrowania symetrycznego zatwierdzone przez NIST obejmują trójkluczowe Triple DES i AES . Aprobaty dla dwukluczowych Triple DES i Skipjack zostały wycofane w 2015 roku; NSA algorytm Skipjack jest stosowany w Fortezza programu wykorzystuje klucze 80-bitowych.
Długości kluczy algorytmów asymetrycznych
Skuteczność kryptosystemów klucza publicznego zależy od nierozwiązywalności (obliczeniowej i teoretycznej) pewnych problemów matematycznych, takich jak faktoryzacja liczb całkowitych . Te problemy są czasochłonne, ale zwykle szybsze niż próbowanie wszystkich możliwych kluczy brutalną siłą. Dlatego klucze asymetryczne muszą być dłuższe, aby zapewnić równoważną odporność na ataki niż klucze algorytmów symetrycznych. Zakłada się, że najpopularniejsze metody będą w przyszłości słabe w porównaniu z wystarczająco potężnymi komputerami kwantowymi .
Od 2015 r. NIST zaleca co najmniej 2048-bitowe klucze dla RSA , aktualizacja szeroko akceptowanego zalecenia minimum 1024-bitowego od co najmniej 2002 r.
1024-bitowe klucze RSA są równoważne 80-bitowym kluczom symetrycznym, 2048-bitowym kluczom RSA 112-bitowym kluczom symetrycznym, 3072-bitowym kluczom RSA 128-bitowym kluczom symetrycznym i 15360-bitowym kluczom RSA 256-bitowi klucze symetryczne. W 2003 r. firma RSA Security twierdziła, że klucze 1024-bitowe prawdopodobnie staną się możliwe do złamania w latach 2006-2010, podczas gdy klucze 2048-bitowe wystarczą do 2030 r. Od 2020 r. największym publicznie znanym kluczem RSA, który został złamany, jest RSA-250 z 829 bitów.
Algorytm skończonego pola Diffiego-Hellmana ma mniej więcej taką samą siłę klucza jak RSA dla tych samych rozmiarów klucza. Czynnik pracy dla przełamania Diffie-Hellmana jest oparty na problemie logarytmu dyskretnego , który jest powiązany z problemem faktoryzacji liczb całkowitych, na którym opiera się siła RSA. Zatem 2048-bitowy klucz Diffie-Hellmana ma mniej więcej taką samą siłę jak 2048-bitowy klucz RSA.
Kryptografia krzywych eliptycznych (ECC) to alternatywny zestaw algorytmów asymetrycznych, który jest równoważnie bezpieczny przy krótszych kluczach, wymagający tylko około dwa razy więcej bitów niż równoważny algorytm symetryczny. 256-bitowy klucz ECDH ma w przybliżeniu taki sam współczynnik bezpieczeństwa jak 128-bitowy klucz AES. Wiadomość zaszyfrowana algorytmem eliptycznego klucza przy użyciu 109-bitowego klucza została złamana w 2004 roku.
NSA wcześniej zalecano 256 bitów ECC ochrony informacji poufnych do poziomu klucz tajny, i 384-bitowy TOP poufne; W 2015 r. ogłosił plany przejścia na algorytmy kwantowe do 2024 r. i do tego czasu zaleca 384-bitowe dla wszystkich informacji niejawnych.
Wpływ ataków na komputery kwantowe na siłę klucza
Dwie najlepsze znane ataki kwantowe obliczanie w oparciu o algorytm faktoryzacji shora i Algorytm Grovera . Spośród tych dwóch, Shora oferuje większe ryzyko dla obecnych systemów bezpieczeństwa.
Powszechnie przypuszcza się, że pochodne algorytmu Shora są skuteczne przeciwko wszystkim głównym algorytmom z kluczem publicznym, w tym RSA , Diffie-Hellmanowi i kryptografii krzywych eliptycznych . Według profesora Gillesa Brassarda, eksperta w dziedzinie obliczeń kwantowych: „Czas potrzebny na rozłożenie liczby całkowitej RSA jest tego samego rzędu, co czas potrzebny do użycia tej samej liczby całkowitej jako modułu dla pojedynczego szyfrowania RSA. Innymi słowy, nie zajmuje to więcej czas, aby złamać RSA na komputerze kwantowym (do stałej multiplikatywnej), niż używać go zgodnie z prawem na klasycznym komputerze." Ogólny konsensus jest taki, że te algorytmy klucza publicznego są niepewne przy dowolnym rozmiarze klucza, jeśli dostępne będą wystarczająco duże komputery kwantowe zdolne do uruchomienia algorytmu Shora. Konsekwencją tego ataku jest to, że wszystkie dane zaszyfrowane przy użyciu systemów bezpieczeństwa opartych na obecnych standardach, takich jak wszechobecny protokół SSL używany do ochrony handlu elektronicznego i bankowości internetowej oraz SSH używany do ochrony dostępu do wrażliwych systemów komputerowych, są zagrożone. Zaszyfrowane dane chronione za pomocą algorytmów klucza publicznego mogą być archiwizowane i mogą zostać złamane w późniejszym czasie.
Powszechnie przypuszcza się, że popularne szyfry symetryczne (takie jak AES lub Twofish ) i odporne na kolizje funkcje mieszające (takie jak SHA ) zapewniają większe bezpieczeństwo przed znanymi atakami opartymi na obliczeniach kwantowych. Powszechnie uważa się, że są najbardziej podatne na algorytm Grovera . Bennett, Bernstein, Brassard i Vazirani udowodnili w 1996 roku, że brutalne wyszukiwanie kluczy na komputerze kwantowym nie może być szybsze niż około 2 n /2 wywołań podstawowego algorytmu kryptograficznego, w porównaniu z około 2 n w przypadku klasycznym. Tak więc, w obecności dużych komputery kwantowe n klucz-bitowe może zapewnić co najmniej n / 2 bitów bezpieczeństwa. Brutalną siłę kwantową można łatwo pokonać, podwajając długość klucza, co przy zwykłym użyciu wiąże się z niewielkimi dodatkowymi kosztami obliczeniowymi. Oznacza to, że co najmniej 256-bitowy klucz symetryczny jest wymagany do osiągnięcia 128-bitowej oceny bezpieczeństwa w stosunku do komputera kwantowego. Jak wspomniano powyżej, NSA ogłosiła w 2015 r., że planuje przejść na algorytmy kwantowe.
Według NSA:
„Wystarczająco duży komputer kwantowy, jeśli zostanie zbudowany, byłby w stanie podważyć wszystkie szeroko stosowane algorytmy klucza publicznego używane do ustanawiania kluczy i podpisów cyfrowych. ... Ogólnie przyjmuje się, że techniki obliczeń kwantowych są znacznie mniej skuteczne w przypadku algorytmów symetrycznych niż w przypadku obecnie szeroko stosowane algorytmy klucza publicznego.Podczas gdy kryptografia klucza publicznego wymaga zmian w podstawowym projekcie w celu ochrony przed potencjalnym przyszłym komputerem kwantowym, uważa się, że algorytmy z kluczem symetrycznym są bezpieczne pod warunkiem, że używany jest wystarczająco duży rozmiar klucza.... W dłuższej perspektywie , NSA zwraca się do NIST w celu zidentyfikowania szeroko akceptowanego, znormalizowanego zestawu komercyjnych algorytmów klucza publicznego, które nie są podatne na ataki kwantowe”.
Od 2016 r. zestaw algorytmów Commercial National Security Algorithm Suite NSA obejmuje:
| Algorytm | Stosowanie |
|---|---|
| RSA 3072-bitowy lub większy | Ustanowienie klucza, podpis cyfrowy |
| Diffie-Hellman (DH) 3072-bitowy lub większy | Kluczowa placówka |
| ECDH z NIST P-384 | Kluczowa placówka |
| ECDSA z NIST P-384 | Podpis cyfrowy |
| SHA-384 | Integralność |
| AES-256 | Poufność |
Zobacz też
Uwagi
Bibliografia
Ogólny
- Zalecenie dotyczące zarządzania kluczami — część 1: ogólna, specjalna publikacja NIST 800-57. Marzec 2007
- Blaze, Mat; Diffiego, Whitfielda; Rivest, Ronald L.; i in. „Minimalne długości klucza dla szyfrów symetrycznych w celu zapewnienia odpowiedniego bezpieczeństwa komercyjnego”. Styczeń 1996
- Arjen K. Lenstra, Eric R. Verheul: Wybór rozmiarów kluczy kryptograficznych. J. Cryptology 14(4): 255-293 (2001) — link do Citeseer