Schematy podpisów oparte na hashach to techniki kryptograficzne, które łączą funkcje haszujące z algorytmami podpisu cyfrowego w celu zapewnienia integralności, autentyczności i weryfikowalności wiadomości lub danych. W takich schematach hash jest używany jako skrót (czyli skrócona reprezentacja) wiadomości, a podpisy są generowane i weryfikowane na podstawie tego skrótu, a nie na samej wiadomości.
Rozwój komputerów kwantowych wstrząsnął światem na tyle mocno, że tradycyjne algorytmy asymetryczne, nie są już uważane za aż tak bezpieczne. Instytucje, takie jak NIST, są w trakcie definiowania nowych standardów dla alternatywnych algorytmów. Dlatego dzisiejszy wpis postanowiliśmy w całości poświęcić podpisom opartym na skrótach i ich odporności kwantowej.
Schematy podpisów oparte na skrótach (hashach)
Oprócz procesu standaryzacji PQC, NIST, BSI i CNSA 2.0 uznają już dwa algorytmy za odporne na kwanty. W swojej publikacji 800-208 NIST zatwierdził dwa schematy podpisów oparte na hashach dla kryptografii postkwantowej są to:
- XMSS (eXtended Merkle Signature Scheme) i wariant XMSS-MT (XMSS with Merkle Trees)
- LMS (Leighton-Micali Signatures) i wariant HSS (Hierarchical Signature Scheme).
Gdzie XMSS i LMS są schematami podpisów Merkle.
Generowanie podpisu
Po obliczeniu skrótu wiadomości, podpisujący używa swojego klucza prywatnego do podpisania tego skrótu. Używanie hasha pozwala na oszczędność zasobów, ponieważ podpisywanie krótszego skrótu jest znacznie szybsze niż podpisywanie pełnej wiadomości. Algorytm jest następnie stosowany do podpisywania skrótu wiadomości, a nie samej wiadomości.
Jak to działa?
Kryptografia oparta na funkcjach hash polega na generowaniu klucza publicznego poprzez kilkukrotne skrócenie wartości x0, np. do x3.
Pracując z tablicą wartości skrótu, podpisujący, znając wszystkie wartości, może użyć x1 jako klucza prywatnego i podpisać nim wiadomość. Znając x3 – klucz publiczny – odbiorca może zweryfikować, czy klucz prywatny jest ważny, haszując x1 i sprawdzając, czy jest to x3. Jednak podpis ten może być użyty tylko raz, więc schemat ten jest schematem podpisu jednokrotnego (OTS).
Wygodniej jest mieć tylko jeden klucz publiczny i wiele kluczy prywatnych, bo podpisy Merkle są budowane na strukturze drzewa skrótów, jak poniżej:
Struktura drzewa skrótów pozwala na podpisanie ograniczonej liczby wiadomości, które mają zostać zweryfikowane za pomocą tego samego klucza publicznego. Liczba wiadomości musi być potęgą dwójki (np. 2, 4, 8 itd.). Wysokość drzewa jest logarytmem liczby kluczy (wiele kluczy, które tworzą stosunkowo płaskie drzewo). Aby utworzyć klucz publiczny, najpierw generowanych jest kilka par kluczy prywatnych/publicznych metody podpisu jednorazowego. Następnie obliczane są wartości skrótu klucza publicznego dla każdej pary kluczy.
W kolejnym kroku budowane jest drzewo haszujące (lub drzewo Merkle’a) przy użyciu tych wartości haszujących. Wartości hash są liśćmi drzewa i są łączone w pary i wielokrotnie hashowane w celu utworzenia drzewa binarnego. Całe drzewo może zostać upublicznione (oczywiście z wyjątkiem kluczy prywatnych). Klucz publiczny jest korzeniem drzewa, a jego węzły służą jako niezbędne informacje i są dołączane do podpisu. Odbiorca może następnie zweryfikować podpis tylko za pomocą klucza publicznego (ponieważ dane pomocnicze są częścią podpisu).
Tego rodzaju podpisy są najlepsze spośród wszystkich podpisów PQC i dlatego zalecane w kontekście bezpieczeństwa postkwantowego przez NIST, NSA i Niemiecki Federalny Urząd ds. Bezpieczeństwa Informacji – jak poniżej:
- NIST: Special Publication 800-208
- NSA: Commercial National Security Security Algorithm
- BSI: Quantum-safe cryptography – fundamentals, current development and recommendations
Zalety i wady podpisów opartych na skrótach
Jeśli schematy podpisów oparte na hashach są na tyle znormalizowane i odporne na kwanty, to dlaczego istnieje potrzeba stosowania innych alternatyw, obecnie ocenianych i wybieranych w procesie standaryzacji NIST PQC?
Odpowiedź jest prosta – podpisy te mają swoje wady i zalety i nie będą odpowiednie dla każdego przypadku użycia.
Przyjrzyjmy się najpierw zaletom schematów podpisów opartych na hashach:
- Ich filarem są stabilne i sprawdzone algorytmy (tzw. „dojrzałe”)
- Zapewniają wysoki poziom bezpieczeństwa
- Stosunkowo małe rozmiary kluczy czynią je prostymi, szybkimi i wydajnymi
- Są skalowalne – podpisywanie krótkich skrótów pozwala na łatwe podpisywanie dużych plików lub wiadomości
- Podpisywanie i weryfikacja wymagają minimalnego wysiłku obliczeniowego
- Mogą być używane jako samodzielny algorytm (nie ma potrzeby implementacji hybrydowej).
Dlatego algorytmy podpisu oparte na hashach, takie jak LMS lub XMSS, są idealne do przypadków użycia, w których podpisy cyfrowe muszą być odporne na kwanty już na chwilę obecną.
Do wad schematów podpisów opartych na hashach zaliczyć można:
- Utrudnione śledzenie, czyli które klucze OTS zostały użyte
- Przypadkowe ponowne użycie klucza OTS może prowadzić do fałszerstwa
- Istnieje ryzyko wyczerpania kluczy (podpisów)
- Liczba potrzebnych podpisów powinna być szacowana z wyprzedzeniem
- Uważane przez NIST tylko za odpowiednie do zastosowań, w których użycie klucza prywatnego może być dokładnie kontrolowane.
Istnieją jednak sposoby na rozwiązanie większości z tych niedogodności.
Rekomendacje
W obydwu przypadkach tj. XMSS i LMS, idea polega na tym, by zamiast jednego dużego drzewa Merkle, używać struktury hierarchicznej lub wielu niezależnych drzew, co pozwala na lepsze zarządzanie kluczami oraz zwiększa odporność na potencjalne ataki. W kontekście podpisów postkwantowych, obie te metody oferują rozwiązania odporne na ataki ze strony komputerów kwantowych, co czyni je bardzo obiecującymi w długoterminowej perspektywie.
Poniżej wymieniliśmy kilka rekomendacji, które uznaliśmy za istotne.
Krok 1: Zbuduj “las”
Rozszerzenie struktury drzewa o kolejną warstwę kluczy (klucze podpisujące nie podpisują wiadomości, ale klucz, który jest korzeniem innego klucza). Spowoduje to jednak utworzenie większych podpisów, a tym samym niższą wydajność.
Zarówno LMS, jak i XMSS oferują sprawdzone warianty wielodrzewne: HSS i XMSS-MT.
Krok 2: Zmieniaj klucze publiczne
Ustanowienie bezpiecznej i niezawodnej procedury zastępowania klucza publicznego.
Krok 3: Dobierz odpowiednią architekturę HSM
Większość uprzednio wymienionych wad wynika z wyzwania dotyczącego śledzenia, które klucze OTS zostały już użyte. Ponadto samo zarządzanie kopiami zapasowymi może przeszkadzać w procesie śledzenia np. w procesie tworzenia kopii zapasowej i przywracania, stare klucze OTS mogą zostać przywrócone, mimo że zostały już użyte. Jeśli zostaną one ponownie użyte, wzrasta ryzyko fałszerstwa. W efekcie kopia zapasowa musi być dostosowywana za każdym razem, gdy tworzony jest podpis, poprzez usunięcie kluczy OTS lub oznaczenie ich jako „używane”. Ta ciągła adaptacja może być bardzo złożona i stanowi szczególne wyzwanie w organizacjach rozproszonych.
Utimaco opracowało na ten problem doskonałe rozwiązanie. Zestaw wartości OTS może być dystrybuowany do odpowiednich modułów HSM w różnych lokalizacjach. Dzięki temu HSM i poszczególne lokalizacje są od siebie niezależne bez konieczności ciągłej wymiany informacji o tym, które wartości OTS zostały już wykorzystane. A jeśli w jednej lokalizacji zabraknie kluczy OTS, można uruchomić transfer.
Moduły Utimaco HSM ogólnego przeznaczenia tzw. General Purpose HSM zostały zaprojektowane zgodnie z zasadami cryptoagility, co umożliwia im aktualizacje oprogramowania układowego w celu dodania nowych algorytmów PQC, gdy tylko zostaną one znormalizowane i sprawdzone.
HSM tego typu obsługują takie algorytmy kwantowe jak:
- XMSS and XMSS-MT
- LMS and HSS
- CRYSTALS-KYBER
- CRYSTALS-Dilithium
Sprzętowe moduły bezpieczeństwa Utimaco są nieustannie rozwijane i aktualizowane z uwzględnieniem procesu standaryzacji NIST.
Podsumowując, podpisy oparte na skrótach są obecnie najlepszym rozwiązaniem w kontekście odpornych na ataki kwantowe podpisów cyfrowych. Dzięki zastosowaniu funkcji haszującej w połączeniu z kryptografią klucza publicznego, proces podpisywania i weryfikacji jest zarówno bezpieczny, jak i skalowalny.