Kryptografické hašovací funkce

V této lekci se podíváme na kryptografické hašovací funkce, které nacházejí rozsáhlé uplatnění při rychlé validaci a ověřování.

Na konci lekce budeš mít přehled o:

• Co jsou kryptografické hašovací funkce
• Ukázkách kódu v Pythonu demonstrujících použití hašovacích funkcí
• Aplikacích kryptografického hašování
• Bezpečnosti kryptografického hašování
• Hrozbách pro tyto algoritmy ze strany klasických i kvantových počítačů

Úvod do kryptografického hašování

Hašovací funkce představují cenný konstrukt v kryptografii, protože umožňují validaci s důvěrností. Hašovací funkce tak tvoří důležitou součást mechanismů pro ověřování a integritu dat, jako jsou kódy pro ověřování zpráv na základě hašování (HMAC) a digitální podpisy. Tento článek pojednává o základních myšlenkách a bezpečnostních aspektech kryptografických hašovacích funkcí a nastiňuje potenciální zranitelnosti plynoucí z nástupu kvantových počítačů.

Základní principy a návrh hašovacích funkcí

Existuje mnoho situací, kdy je potřeba provést ověřování a kontrolu integrity levně a bez odhalení soukromých informací straně provádějící validaci.

Například při stahování softwaru ze vzdáleného serveru je potřeba efektivní mechanismus k ověření, že stažený software nebyl od svého vytvoření původním autorem pozměněn. Podobně při ověřování uživatelů webových aplikací by bylo vhodné použít mechanismus, který nevyžaduje fyzické ukládání ani přenos skutečných hesel, což by mohlo ohrozit jejich důvěrnost.

Kryptografické hašovací funkce (CHF) tyto potřeby řeší efektivně a bezpečně.

V zásadě kryptografická hašovací funkce přijme vstup (nebo zprávu) libovolné délky a vrátí řetězec fixní délky n bitů jako výstup. Výstup CHF se také označuje jako digest. Užitečná CHF by měla splňovat několik klíčových vlastností:

1. Rovnoměrnost: Digesty produkované CHF by měly být rozloženy rovnoměrně a měly by vypadat náhodně. Cílem je zajistit, aby výstup neodhaloval žádné informace o vstupu.
2. Determinismus: Pro daný vstup musí CHF vždy produkovat stejný digest, tedy musí být deterministická.
3. Nevratnost: CHF je jednosměrná funkce v tom smyslu, že pro daný digest by mělo být neproveditelné hašování obrátit a získat vstup.
4. Přibližná injektivita: Přestože CHF jsou funkce mnoho-na-jeden, měly by vypadat jako funkce jedna-na-jednu. Toho je dosaženo kombinací obrovské velikosti výstupního prostoru s lavinovým efektem, kdy drobné změny na vstupu vedou k drasticky odlišným digestům. Tato vlastnost se nazývá přibližná injektivita.

Díky tomu je možné ověřit část dat vůči původní instanci porovnáním digestu dat s digestem originálu.

• Pokud se oba digesty shodují, můžeme s vysokou pravděpodobností věřit, že data jsou totožná s originálem.
• Pokud se digesty liší, můžeme si být jisti, že data byla pozměněna nebo jsou jinak nepůvodní.

Protože samotné digesty CHF neodhalují skutečný obsah dat ani originál, umožňují validaci při zachování soukromí.

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.

Skutečnost, že velikost vstupní domény $Σ^*$ funkce $H$ je neomezená, zatímco ko-doména $\{0,1\}^n$ je omezená, znamená, že $H$ je nutně zobrazením mnoho-na-jeden, mapujícím nekonečně mnoho vstupů na libovolný n-bitový řetězec.

Vlastnosti uniformity a determinismu jsou pěkně zachyceny v modelu náhodného orákula kryptografického hašování.

Příklad kryptografického hašování v Pythonu s SHA-256

Tento jednoduchý příklad ukazuje kryptografické hašování pomocí oblíbeného algoritmu SHA-256 poskytnutého knihovnou Python cryptography. Nejprve ukážeme, jak drobný rozdíl v prostých textech vede k velmi velkému rozdílu v hašových digestech.

# 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

Obě zprávy se liší přesně v jednom znaku.

Dále vytvoříme objekty hash pro umožnění procesu hašování, který zahrnuje volání dvou metod: update a finalize.

Vidíme, že díky lavinovému efektu v CHF SHA-256 vede jednoznakový rozdíl ve vstupních zprávách ke dvěma velmi odlišným digestům.

# 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

Aplikace kryptografického hašování

Jedinečné vlastnosti CHF je činí vhodnými pro širokou škálu aplikací:

• Kontroly integrity dat: Hašovací funkce lze použít k vytvoření kontrolního součtu pro sadu dat. Jakékoli úpravy dat, úmyslné či náhodné, budou mít za následek jiný kontrolní součet, který upozorní systémy nebo uživatele na změnu. Kontrolní součet je také typicky mnohem kompaktnější než původní data, což kontrolní porovnání velmi urychluje.

Obrázek 1. Bezpečné hašování pro kontroly integrity dat

• Digitální podpisy: Kryptografické haše jsou nezbytné pro fungování digitálních podpisů, protože zahrnují porovnávání kryptograficky hašovaných zpráv za účelem prokázání pravosti a integrity při zachování soukromí.

Obrázek 2. Digitální podpisy

• Blockchain a kryptoměny: Kryptoměny jako Bitcoin silně spoléhají na CHF, zejména při zajišťování integrity transakcí a umožňování konsenzuálních mechanismů jako proof of work.

Bezpečnost kryptografického hašování

Bezpečnost CHF se typicky hodnotí na základě odolnosti vůči dvěma typům útoků: pre-image a kolizním.

Odolnost vůči pre-image útoku

Odolnost vůči pre-image útoku znamená, že pro daný digest by mělo být neproveditelné najít vstup.

To souvisí s jednosměrnou vlastností CHF.

Dobrá CHF je navržena tak, aby strana, která chce provést pre-image útok, neměla jinou možnost než hrubou silou, která má časovou složitost $2^n$.

mathematical details

Pro danou CHF $H$ a digest $g$ by mělo být výpočetně neproveditelné nalézt jakýkoli vstup $m$ z pre-image hodnoty $g$ takový, že $H(m) = g$.

Odolnost vůči kolizím

Odolnost vůči kolizím znamená, že je obtížné najít dva různé vstupy, které se hašují na stejný digest.

Kryptografická hašovací kolize nastane, když se dva vstupy hašují na stejný digest. Přestože kolize nevyhnutelně existují vzhledem k povaze CHF jako funkcí mnoho-na-jeden, dobrá CHF přesto znemožňuje jejich libovolné nalezení.

Odolnost vůči kolizím je klíčová pro aplikace jako digitální podpisy a certifikáty, kde by bylo katastrofální, kdyby zlomyslná strana dokázala vytvořit padělat, který se hašuje na stejnou hodnotu.

mathematical details of hash collisions

$m_1, m_2$ can be found such that $H(m_1) = H(m_2)$.

Délka haše

Odolnost vůči kolizím je náročnější požadavek než odolnost vůči pre-image útoku a vyžaduje délky výstupu dvakrát delší než ty, které jsou potřebné pro odolnost vůči pre-image útoku. Je to proto, že útok hrubou silou známý jako narozeninový útok, který lze použít k identifikaci hašových kolizí, má časovou složitost $2^{n/2}$.

Bez kryptanalytických slabin je bezpečnost hašovací funkce tedy primárně ovlivněna délkou haše. Čím delší je haš, tím je bezpečnější, protože je těžší provést útoky hrubou silou.

Běžně používané kryptografické hašovací funkce

Následující tabulka uvádí některé běžně používané kryptografické hašovací funkce spolu s délkami jejich hašů a primárními oblastmi použití:

Hash Function	Output Length (bits)	Common Applications
MD5	128	File integrity checking, older systems, non-crypto uses
SHA-1	160	Legacy systems, Git for version control
SHA-256	256	Cryptocurrency (Bitcoin), digital signatures, certificates
SHA-3	Variable (up to 512)	Various cryptographic applications, successor to SHA-2
Blake2	Variable (up to 512)	Cryptography, replacing MD5/SHA-1 in some systems
Blake3	Variable (up to 256)	Cryptography, file hashing, data integrity

• MD5 a SHA-1, ačkoli se stále vyskytují v méně citlivých aplikacích, jsou považovány za zastaralé z hlediska odolnosti vůči kolizím a nedoporučují se pro nové systémy. SHA-256, součást rodiny SHA-2, je široce používán a aktuálně bezpečný pro většinu aplikací.
• SHA-3 je novější standard, který byl vybrán institutem NIST v roce 2015 jako vítěz soutěže NIST o hašovací funkci. Je navržen jako přímá náhrada za SHA-2, ale má také některé odlišné vnitřní vlastnosti a je odolný vůči určitým typům útoků, které by mohly být účinné proti SHA-2.
• Blake2 a Blake3 jsou kryptografické hašovací funkce, které jsou rychlejší než MD5, SHA-1, SHA-2 a SHA-3, ale alespoň tak bezpečné jako nejnovější standard SHA-3. Stále více se používají v nových systémech, zejména tam, kde je důležitá rychlost.

Kvantová rizika pro tradiční kryptografické hašování

Primární kvantová hrozba pro kryptografické hašování pochází z útoků hrubou silou.

Pro daný digest se útočník bude pokoušet o náhodné vstupy, dokud nenajde takový, který produkuje stejný digest.

Při $n$ bitech na vstupu existuje $2^n$ možných hodnot. Útočník tedy musí vyzkoušet přibližně $2^{n-1}$ vstupů, aby měl více než 50% šanci na úspěch.

Groverův algoritmus

Pro takový nestrukturovaný vyhledávací kontext může Groverův algoritmus poskytnout kvadratické zrychlení pomocí techniky známé jako kvantová amplifikace amplitudy, čímž snižuje časovou složitost pre-image útoku na $2^{n/2}$.

V praktickém vyjádření to znamená, že 256bitová CHF, která je v současnosti považována za bezpečnou vůči pre-image útokům ze strany klasických počítačů, by poskytovala stejnou úroveň bezpečnosti jako 128bitová CHF při čelení kvantovému útočníkovi využívajícímu Groverův algoritmus.

Groverův algoritmus sám o sobě nezajišťuje další kvantová zrychlení s ohledem na kolizní útoky nad rámec limitu stanoveného narozeninovým útokem, který lze provést na klasických počítačích. Jelikož klasický narozeninový útok již vyžaduje, aby CHF používaly délky hašů dvakrát delší, než je potřeba pro odolnost vůči pre-image útoku, skutečnost, že Groverovo vyhledávání efektivně halvuje délku haše s ohledem na pre-image útoky, nepředstavuje praktickou hrozbu.

Například v případě SHA-256 by provedení přibližně $2^{128}$ operací k provedení pre-image útoku s pomocí Grovera bylo stále v dohledné budoucnosti neproveditelné.

BHT algoritmus

Kvantový algoritmus, který kombinuje aspekty narozeninového útoku s Groverovým vyhledáváním, byl navržen v roce 1997 Brassardem, Høyerem a Tappem (BHT) a poskytuje teoretické škálování $O(2^{n/3})$ pro hledání hašových kolizí. Toto zlepšené škálování je však podmíněno existencí technologie kvantové paměti s náhodným přístupem QRAM, která v současnosti neexistuje.

Bez QRAM je realizovatelné škálování $\tilde{O}(2^{2n/5})$ a pro délky hašů v současném použití toto marginální zlepšení ve schopnosti hledat kolize ve srovnání s narozeninovým útokem nepředstavuje kritickou hrozbu.

Shrnutí

Kryptografické hašovací funkce jsou nezbytnou součástí pro zajištění integrity dat a soukromí v digitálních informačních systémech a nacházejí rozsáhlé uplatnění v mnoha kontextech.

Bezpečnostní požadavky CHF jsou chápány hlavně z hlediska jejich odolnosti vůči pre-image a kolizním útokům. Pro dobře navržené CHF je délka haše dobrým ukazatelem úrovně bezpečnosti.

Přestože nástup kvantových počítačů provádějících Groverovy a BHT algoritmy teoreticky ovlivňuje odolnost tradičních CHF vůči pre-image a kolizím, dlouhé délky hašů, které jsou dnes již v použití, znamenají, že moderní algoritmy kryptografického hašování, jako je SHA-3, budou pravděpodobně zůstávat bezpečné, pokud nedojde k objevení dosud neznámých kryptanalytických útoků.

Relevance CHF spočívá v jejich roli jako základního stavebního kamene pro kvantově odolná kryptografická schémata, která zajišťují, že digitální informace zůstanou bezpečné i tváří v tvář potenciálním budoucím pokrokům v algoritmech a technologiích kvantových počítačů.