Kryptograficzne funkcje skrótu

W tej lekcji przyjrzymy się kryptograficznym funkcjom skrótu, które są szeroko stosowane do szybkiej walidacji i uwierzytelniania.

Po ukończeniu lekcji omówimy:

• Czym są kryptograficzne funkcje skrótu
• Przykłady kodu w Python demonstrujące użycie funkcji skrótu
• Zastosowania kryptograficznego haszowania
• Bezpieczeństwo kryptograficznego haszowania
• Zagrożenia dla tych algorytmów ze strony komputerów klasycznych i kwantowych

Introduction to cryptographic hashing

Funkcje skrótu stanowią cenny element kryptografii, ponieważ umożliwiają walidację z zachowaniem poufności. Funkcje skrótu są ważnym składnikiem mechanizmów uwierzytelniania i integralności danych, takich jak kody uwierzytelniania wiadomości oparte na skrócie (HMAC) oraz podpisy cyfrowe. Ten artykuł omawia podstawowe koncepcje i zagadnienia bezpieczeństwa leżące u podstaw kryptograficznych funkcji skrótu oraz wskazuje potencjalne podatności wynikające z pojawienia się komputerów kwantowych.

Basic rationale and design of hash functions

Istnieje wiele sytuacji, w których uwierzytelnianie i weryfikacja integralności muszą być przeprowadzane tanio i bez ujawniania prywatnych informacji stronie wykonującej walidację.

Na przykład podczas pobierania oprogramowania ze zdalnego serwera potrzebny jest wydajny mechanizm weryfikacji, że pobrane oprogramowanie nie zostało zmodyfikowane od momentu jego stworzenia przez oryginalnego autora. Podobnie, podczas uwierzytelniania użytkowników aplikacji webowych, pożądane byłoby stosowanie mechanizmu, który nie wymaga fizycznego przechowywania ani przesyłania rzeczywistych haseł, co mogłoby potencjalnie naruszyć ich poufność.

Kryptograficzne funkcje skrótu (CHF) efektywnie i bezpiecznie odpowiadają na takie potrzeby.

Zasadniczo kryptograficzna funkcja skrótu przyjmuje dane wejściowe (lub wiadomość) o dowolnej długości i zwraca ciąg bitów o stałym rozmiarze n jako wynik. Wynik działania CHF jest również określany jako digest. Użyteczna CHF powinna spełniać kilka kluczowych właściwości:

1. Jednolitość: Wartości digest produkowane przez CHF powinny być rozłożone jednostajnie i wyglądać losowo. Celem jest zapewnienie, że wynik nie ujawnia żadnych informacji o danych wejściowych.
2. Determinizm: Dla danego wejścia CHF musi zawsze produkować ten sam digest, czyli musi być deterministyczna.
3. Nieodwracalność: CHF jest funkcją jednokierunkową, co oznacza, że mając digest, powinno być niewykonalne odwrócenie procesu haszowania i odtworzenie danych wejściowych.
4. Przybliżona injektywność: Choć CHF są funkcjami wiele-do-jednego, powinny wyglądać jak funkcje jeden-do-jednego. Osiąga się to przez połączenie ogromnego rozmiaru przestrzeni wyjściowej z efektem lawinowym, w którym drobne zmiany na wejściu prowadzą do zupełnie różnych wartości digest. Ta właściwość jest znana jako przybliżona injektywność.

Mając to na uwadze, można zweryfikować kawałek danych względem oryginału, porównując digest tych danych z digest oryginału.

• Jeśli dwa digesty są zgodne, możemy z dużym prawdopodobieństwem być pewni, że dane są identyczne z oryginałem.
• Jeśli digesty różnią się, możemy być pewni, że dane zostały zmodyfikowane lub są w inny sposób nieautentyczne.

Ponieważ same wartości digest CHF nie ujawniają rzeczywistej zawartości danych ani oryginału, umożliwiają walidację przy jednoczesnym zachowaniu prywatności.

Mathematical description

A hash function $H$ can be defined as:

$H : Σ^* \rightarrow \{0,1\}^n$

where $Σ^*$ is the set of all possible strings which we may consider to be binary strings of any length.

Fakt, że rozmiar dziedziny wejściowej $Σ^*$ funkcji $H$ jest nieograniczony, podczas gdy ko-dziedzina $\{0,1\}^n$ jest ograniczona, oznacza, że $H$ jest z konieczności odwzorowaniem wiele-do-jednego, przyporządkowując nieskończenie wiele wejść do dowolnego n-bitowego ciągu.

Właściwości jednorodności i determinizmu są ładnie ujęte w modelu losowej wyroczni kryptograficznego haszowania.

Example of cryptographic hashing in Python with SHA-256

Ten prosty przykład demonstruje kryptograficzne haszowanie przy użyciu popularnego algorytmu SHA-256 dostarczonego przez bibliotekę cryptography dla Python. Najpierw pokazujemy, jak niewielka różnica w tekstach jawnych prowadzi do bardzo dużej różnicy w wartościach digest.

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

# Begin by importing some necessary modules
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import hashes

# Helper function that returns the number of characters different in two strings
def char_diff(str1, str2):
    return sum(str1[i] != str2[i] for i in range(len(str1)))

# Messages to be hashed
message_1 = b"Buy 10000 shares of WXYZ stock now!"
message_2 = b"Buy 10000 shares of VXYZ stock now!"

print(f"The two messages differ by { char_diff(message_1, message_2)} characters")

The two messages differ by 1 characters

Obie wiadomości różnią się dokładnie jednym znakiem.

Następnie tworzymy obiekty hash, aby umożliwić proces haszowania, który obejmuje wywołania dwóch metod: update i finalize.

Widzimy, że dzięki efektowi lawinowemu w SHA-256 CHF, różnica jednego znaku w wiadomościach wejściowych daje dwie zupełnie różne wartości digest.

# Create new SHA-256 hash objects, one for each message
chf_1 = hashes.Hash(hashes.SHA256(), backend=default_backend())
chf_2 = hashes.Hash(hashes.SHA256(), backend=default_backend())

# Update each hash object with the bytes of the corresponding message
chf_1.update(message_1)
chf_2.update(message_2)

# Finalize the hash process and obtain the digests
digest_1 = chf_1.finalize()
digest_2 = chf_2.finalize()

# Convert the resulting hash to hexadecimal strings for convenient printing
digest_1_str = digest_1.hex()
digest_2_str = digest_2.hex()

# Print out the digests as strings
print(f"digest-1: {digest_1_str}")
print(f"digest-2: {digest_2_str}")

print(f"The two digests differ by { char_diff(digest_1_str, digest_2_str)} characters")

digest-1: 6e0e6261b7131bd80ffdb2a4d42f9d042636350e45e184b92fcbcc9646eaf1e7
digest-2: 6b0abb368c3a1730f935b68105e3f3ae7fd43d7e786d3ed3503dbb45c74ada46
The two digests differ by 57 characters

Applications of cryptographic hashing

Unikalne właściwości CHF sprawiają, że nadają się one do szerokiego wachlarza zastosowań:

• Sprawdzanie integralności danych: Funkcje hash można wykorzystać do tworzenia sumy kontrolnej dla zestawu danych. Wszelkie modyfikacje danych, celowe lub nie, spowodują powstanie innej sumy kontrolnej, alertując systemy lub użytkowników o zmianie. Suma kontrolna jest też zazwyczaj znacznie bardziej zwarta niż oryginalne dane, co sprawia, że porównywanie sum kontrolnych jest bardzo szybkie.

Rysunek 1. Bezpieczne haszowanie na potrzeby sprawdzania integralności danych

• Podpisy cyfrowe: Kryptograficzne hasze są niezbędne do działania podpisów cyfrowych, ponieważ wiążą się z porównywaniem kryptograficznie zahaszowanych wiadomości w celu potwierdzenia autentyczności i integralności przy jednoczesnym zachowaniu prywatności.

Rysunek 2. Podpisy cyfrowe

• Blockchain i kryptowaluty: Kryptowaluty takie jak Bitcoin w dużym stopniu opierają się na CHF, szczególnie przy tworzeniu integralności transakcji i umożliwianiu mechanizmów konsensusu, takich jak proof of work.

Security of cryptographic hashing

Bezpieczeństwo CHF jest zazwyczaj oceniane na podstawie odporności na dwa typy ataków: pre-image i collision.

Pre-image resistance

Pre-image resistance oznacza, że mając dany digest, znalezienie danych wejściowych powinno być niewykonalne obliczeniowo.

Wiąże się to z właściwością jednokierunkowości CHF.

Dobrze zaprojektowana CHF jest skonstruowana w taki sposób, że podmiot chcący przeprowadzić atak pre-image nie ma lepszej opcji niż podejście brute force, które ma złożoność czasową $2^n$.

szczegóły matematyczne

Dana CHF $H$ i digest $g$: znalezienie dowolnego wejścia $m$ z pre-image wartości $g$, dla którego $H(m) = g$, powinno być obliczeniowo niewykonalne.

Collision resistance

Collision resistance oznacza, że znalezienie dwóch różnych danych wejściowych, które dają ten sam digest, jest trudne.

Kryptograficzna kolizja hash (cryptographic hash collision) zachodzi, gdy dwa wejścia dają ten sam digest. Choć kolizje nieuchronnie istnieją ze względu na charakter „wiele do jednego" CHF, dobra CHF sprawia, że znalezienie kolizji na żądanie jest niewykonalne.

Collision resistance jest kluczowa w zastosowaniach takich jak podpisy cyfrowe i certyfikaty, gdzie katastrofalne byłoby, gdyby złośliwy podmiot był w stanie stworzyć fałszywy dokument dający ten sam wynik haszowania.

szczegóły matematyczne kolizji hash

$m_1, m_2$ można znaleźć takie, że $H(m_1) = H(m_2)$.

Hash length

Collision resistance jest trudniejszym wymogiem niż pre-image resistance i wymaga długości wyjściowych dwa razy dłuższych niż te potrzebne do pre-image resistance. Wynika to z faktu, że atak brute force znany jako birthday attack (atak urodzinowy), który może służyć do identyfikowania kolizji hash, ma złożoność czasową $2^{n/2}$.

Przy braku słabości kryptoanalitycznych bezpieczeństwo funkcji hash jest zatem determinowane przede wszystkim przez jej długość. Im dłuższy hash, tym jest bardziej bezpieczny, ponieważ przeprowadzenie ataków brute force staje się trudniejsze.

Commonly used cryptographic hash functions

Poniższa tabela zawiera listę często używanych kryptograficznych funkcji hash wraz z ich długościami oraz głównymi obszarami zastosowań:

Funkcja hash	Długość wyjścia (bity)	Typowe zastosowania
MD5	128	Sprawdzanie integralności plików, starsze systemy, zastosowania niekryptograficzne
SHA-1	160	Starsze systemy, Git do kontroli wersji
SHA-256	256	Kryptowaluty (Bitcoin), podpisy cyfrowe, certyfikaty
SHA-3	Zmienna (do 512)	Różne zastosowania kryptograficzne, następca SHA-2
Blake2	Zmienna (do 512)	Kryptografia, zastępowanie MD5/SHA-1 w niektórych systemach
Blake3	Zmienna (do 256)	Kryptografia, haszowanie plików, integralność danych

• MD5 i SHA-1, choć wciąż spotykane w mniej wrażliwych zastosowaniach, są uznawane za przestarzałe pod względem collision resistance i nie są zalecane w nowych systemach. SHA-256, będący częścią rodziny SHA-2, jest szeroko stosowany i aktualnie bezpieczny dla większości zastosowań.
• SHA-3 to nowszy standard wybrany przez NIST w 2015 roku jako zwycięzca konkursu NIST na funkcję hash. Jest zaprojektowany jako bezpośredni zamiennik SHA-2, ale ma też inne wewnętrzne cechy i jest odporny na pewne typy ataków, które mogą być skuteczne przeciwko SHA-2.
• Blake2 i Blake3 to kryptograficzne funkcje hash szybsze niż MD5, SHA-1, SHA-2 i SHA-3, lecz co najmniej tak samo bezpieczne jak aktualny standard, SHA-3. Są coraz częściej stosowane w nowych systemach, szczególnie tam, gdzie liczy się szybkość.

Quantum risks to traditional cryptographic hashing

Główne zagrożenie kwantowe dla kryptograficznego haszowania stanowią ataki brute force.

Mając określony digest, atakujący wypróbowuje losowe wejścia, dopóki nie znajdzie takiego, które generuje ten sam digest.

Przy $n$ bitach wejścia istnieje $2^n$ możliwych wartości. Atakujący musi zatem wypróbować około $2^{n-1}$ wejść, aby mieć ponad 50% szans na sukces.

Grover's algorithm

W takim nieustrukturyzowanym kontekście wyszukiwania algorytm Grovera może zapewnić kwadratowe przyspieszenie dzięki technice zwanej kwantowym wzmocnieniem amplitudy, redukując złożoność czasową ataku pre-image do $2^{n/2}$.

W praktyce oznacza to, że 256-bitowa CHF, która jest obecnie uważana za bezpieczną przed atakami pre-image przez klasyczne komputery, zapewniałaby ten sam poziom bezpieczeństwa co 128-bitowa CHF w obliczu atakującego kwantowego korzystającego z algorytmu Grovera.

Sam algorytm Grovera nie jest znany z tego, by zapewniał dodatkowe kwantowe przyspieszenie w odniesieniu do ataków collision poza limit wyznaczony przez birthday attack (atak urodzinowy), który można przeprowadzić na klasycznych komputerach. Ponieważ klasyczny atak urodzinowy już wymaga, by CHF stosowały długości hashy dwa razy dłuższe niż te potrzebne do pre-image resistance, fakt, że wyszukiwanie Grovera efektywnie zmniejsza o połowę długość hash w odniesieniu do ataków pre-image, nie stanowi praktycznego zagrożenia.

Na przykład w przypadku SHA-256 wykonanie rzędu $2^{128}$ operacji w celu przeprowadzenia wspomaganego Groverem ataku pre-image nadal byłoby niewykonalne w dającej się przewidzieć przyszłości.

BHT algorithm

Algorytm kwantowy łączący aspekty birthday attack z wyszukiwaniem Grovera został zaproponowany w 1997 roku przez Brassarda, Høyera i Tappa (BHT) i zapewnia teoretyczne skalowanie $O(2^{n/3})$ dla znajdowania kolizji hash. Jednak to ulepszone skalowanie jest uzależnione od istnienia technologii kwantowej pamięci o dostępie swobodnym QRAM, która obecnie nie istnieje.

Bez QRAM osiągalne skalowanie wynosi $\tilde{O}(2^{2n/5})$ i dla długości hashy aktualnie stosowanych to marginalne ulepszenie zdolności znajdowania kolizji względem birthday attack nie stanowi krytycznego zagrożenia.

Summary

Kryptograficzne funkcje hash są niezbędnym elementem zapewniającym integralność danych i prywatność w cyfrowych systemach informacyjnych i znajdują szerokie zastosowanie w wielu kontekstach.

Wymagania bezpieczeństwa CHF są rozumiane głównie w kategoriach ich odporności na ataki pre-image i collision. W przypadku dobrze zaprojektowanych CHF długość hash jest dobrym przybliżeniem poziomu bezpieczeństwa.

Choć pojawienie się komputerów kwantowych wykonujących algorytmy Grovera i BHT teoretycznie wpływa na pre-image resistance i collision resistance tradycyjnych CHF, długie hasze już dzisiaj stosowane oznaczają, że nowoczesne algorytmy kryptograficznego haszowania, takie jak SHA-3, prawdopodobnie pozostaną bezpieczne, o ile nie zostaną odkryte dotąd nieznane ataki kryptoanalityczne.