Úvod do kryptografie

Toto jsou moje poznámky z předmětu “Úvod do kryptografie,” který přednášel Mgr. Martin Mareš, Ph.D. Výuka probíhala v angličtině, je tedy dost možné, že jsou některé termíny v mých poznámkách přeloženy nepřesně.

Více informací o předmětu naleznete zde.

Kryptografické útoky

Druhy útoků

  1. known ciphertext
    • známe jen zašifrovaný text
    • chceme zjistit plaintext
  2. known plaintext
    • známe nějaký plaintext a jeho zašifrovanou verzi
    • chceme zjistit klíč
  3. chosen plaintext
    • oproti known plaintextu si jej můžeme zvolit
    • chceme zjistit klíč
  4. rozlišovací útoky
    • chceme zjistit, jestli zašifrovaný text koresponduje s určitým typem plaintextu
    • např. když šifra leakuje délku plaintextu

Jak měřit obtížnost útoku

„Narozeninové” útoky

Challenge–response autentikace

$$ \begin{align*} e^{-\frac{m(m-1)}{2n}} &= \frac{1}{2}\\ -\frac{m(m-1)}{2n} &= \ln{\frac{1}{2}}\\ \frac{m(m-1)}{n} &=-2 \ln{\frac{1}{2}} \approx 1.38 \end{align*} $$

Welcome message

Welcome message

$$ \begin{aligned} P[Im(f) \cap A = \empty] &= (1-\frac a n)^m \\ &= e^{-\frac{m\cdot a}n} \end{aligned} $$

Jednorázové klíče

Věta: pokud má perfektně bezpečná šifra $n$-bitové zprávy a $k$-bitové klíče, pak $k \ge n$​

Důkaz:

$$ \begin{align*} y \in \{0,1\}^n\;,\exists x, x' \in \{0,1\}^n :&\; \exists k :\; E(x,k) = y \\ &\; \forall k' :\; E(x',k') \ne y \end{align*} $$

Dělení tajemství

$(k,l)$​-prahové schéma

$(k,2)$

(k,2)-prahové schéma

Obecně

Symetrické šifry

Proudové

keystream

Blokové

Bezpečnost

Iterovaná šifra

iterovaná šifra

substitučně-permutační sítě

substitučne permutační síť

Feistelovy sítě

kolo Feistelovy sítě

  1. zprávu rozdělíme na 2 poloviny
  2. pravou polovinu zakódujeme pomocí neinvertibilní $f$ a tajného klíče $K_i$
    • Feistelova funkce – může být libovolná
  3. prohodíme pravou a levou polovinu a pokračujeme od bodu 2

DES (Digital Encryption Standard)

Struktura DESu

DES

DES klíče

Kritika DESu

Útoky na DES

Pokusy o záchranu DESu

AES (Advanced Encryption Standard)

Struktura

Iterace

  1. ByteSub:

    • bajty stavu proženeme identickými S-boxy
      • S-box je inverze v galoisově tělese $GF(2^8)$ + afinní transformace z rotací a XORů

  2. ShiftRow – $i$-tý řádek rotujeme o nějaký počet bajtů doleva

  3. MixColumn – na každý sloupec aplikujeme stejnou invertibilní lineární transformaci

    • není v poslední iteraci

  4. AddRoundKey – XOR s klíčem

    • před 1. iterací dám navíc jeden AddRoundKey

Inverzní iterace

  1. InvMixColumn
  2. AddRoundKey (s nahrazeným klíčem)
    • InvMixColumn komutuje s AddRoundKey, pokud $K_i$ nahradíme jeho mixem
  3. InvByteSub
    • InvShiftRow komutuje s InvByteSub
  4. InvShiftRow

Rozvrh klíčů

rozvrh AES klíčů

Kritika AES

Použití blokových šifer

Padding

Módy blokových šifer

ECB

ECB

CBC

CBC

Leaking

$$ \begin{align*} Y_i &= Y_j \\ E_K(X_i \oplus Y_{i-1}) &= E_K(X_j \oplus Y_{j-1}) \\ X_i \oplus Y_{i-1} &= X_j \oplus Y_{j-1} \\ X_i \oplus Y_{i-1} \oplus Y_{i-1} \oplus X_j &= X_j \oplus Y_{j-1} \oplus Y_{i-1} \oplus X_j \\ X_i \oplus X_j &= Y_{i-1} \oplus Y_{j-1} \end{align*} $$

CTR

CTR

Leaking

$$ \begin{align*} \forall i,j (i \ne j) &: C_i \ne C_j \implies C_i \oplus C_j \ne 0 \\ \\ Y_i \oplus Y_j &= (X_i \oplus C_i) \oplus (X_j \oplus C_j) \\ &= (X_i \oplus X_j) \oplus (C_i \oplus C_j) \\ \\ X_i \oplus X_j &\ne Y_i \oplus Y_j \end{align*} $$$$ \begin{align*} b - \log(2^b - 1) &= \log{\frac{2^b}{2^b-1}} \\ &= \log{\left(1 + \frac 1 {2^b - 1}\right)} \\ &\approx \frac 1 {2^b - 1} \approx \frac 1 {2^b} \end{align*} $$

OFB

OFB

Padding Oracle Attack

Další zajímavé blokové šifry z finále AES

Serpent

Twofish

Proudové šifry

LFSR

LFSR

eSTREAM project

RC4

ChaCha20

Hashovací funkce

Merkle–Damgårdova konstrukce

Věta: pokud je $f$ bezkolizní, $h$ je bezkolizní

Length extension attack

Collision attack

Multi-Collisions

Parametrizované zprávy

Innocent/Evil messages

Daviesova-Meyerova konstrukce

Esencialita xorování

Proč nepoužívat s DES

Merkle Trees

  1. rozdělíme data do bloků a zahashujeme každý blok
  2. bloky konkatenujeme do větších bloků a zahashujeme
  3. iterujem ke kořeni

Sakura

Používané hashovací funkce

MD5

SHA-1

SHA-2 family

SHA-3

Sponge construction

Keccak permutation

XOF

Message Authentication Codes

Způsoby implementace

HMAC

Kombinování šifer a MAC

Encrypt and MAC

MAC then encrypt

Encrypt then MAC

Konstrukce MAC bez hashovací funkce

CBC-MAC

Shannonovsky bezpečný MAC

$$ \begin{align*} P_{h\in\mathcal H}[h(x') = s' \;|\;h(x)=s] &= \frac{P[h(x)=s \;\and\; h(x')=s']}{P[h(x) = s]} \\ &= \frac{\frac 1 {|Y|^2}}{\sum_{y' \in Y}(P[h(x)=s \;\and\; h(x')=s'])}\\ &= \frac 1 {|Y|^2} \end{align*} $$

Hashovací funkce

Př.: Lineární funkce

Polynomiální MAC

$$ \begin{align*} P_{h\in\mathcal H}[h(x') = s' \;|\;h(x)=s] &= \frac{P[h(x)=s \;\and\; h(x')=s']}{P[h(x) = s]} \\ \vdots \\ & = \frac n {|\mathbb F|} \end{align*} $$

GCM

Poly 1305

Náhodné generátory

Možná řešení

  1. PRNG – pseudo-random number generator
    • např. AES v CTR módu
      • statisticky ok, pokud není vstupní posloupnost moc dlouhá
      • stačí po nějaké době vygenerovat klíč pro AES znova
  2. physical randomness
    • rádiový šum
      • útočník může přijít a poslouchat ten samý noise, co já používám pro generování
    • šum na rezistoru/diodě – termální
      • útočník může generátor výrazně zchladit nebo zahřát a nechat tak ADCčko generovat dlouhé monotónní stringy
      • actually se to děje docela často (imagine polít platební kartu tekutým dusíkem)
    • radioaktivní zářič
      • měření intervalů mezi zachycenými vyzářenými $\beta$-částicemi
      • uhhh, tenhle generátor asi nebude úplně nejčastější :skull:
    • video $\rightarrow$ hash
      • snímání lávové lampy (cloudflare moment)
      • když vypnu světlo v místnosti tak dostanu samý nuly (lol)
    • kruhový oscilátor
      • útočník může měnit napětí na zdroji tak, aby napětí oscilovalo stejně, jako kruhový oscilátor
    • timing kláves/disku/sítě
      • budeme timing měřit velmi veelmi přesně a jako výstup brát nejnižší bity výsledku
      • měření sítě – útočník může měřit taky
  3. kombinace obojího
    • $1)$ a $2)$ samostatně nefungují moc spolehlivě
    • /dev/random a spol.
      • kombinace několika fyzických zdrojů + PRNG na základě ChaCha20
    • RDRAND – nestabilní oscilátor procesoru
      • pokud by se někdo pokusil ovlivnit, procesor by to pravděpodobně poznal a na něčem kolosálně umřel
      • velmi příhodné místo, kam dát do procesoru backdoor

Problémy

Fortuna

Generátor

Akumulátor

Bezpěčný kanál (symetrický)

Algoritmická teorie čísel

složitost aritmetiky

OperaceSložitost
$+$$\mathcal{O}(b)$
$\cdot$$\mathcal{O}(b^2)$ (lze v $\mathcal{O}(b)$, ale s obří konstantou)
$/$ a $\%$$\mathcal{O}(b^2)$
$x^y \mod{n}$$\mathcal{O}(b^3)$

GCD: Euklidův algoritmus

Bézoutovy koeficienty

Počítání modulo $N$​

Věta: $x \in \Z_N$ má multiplikativní inverzi $\iff$ $x \perp N$​

Důkaz:

$$ \begin{align*} \exist t : xy - 1 &= tN \\ xy - tN &= 1 \\ \end{align*} $$

Malá Fermatova věta

Eulerova věta

Věta: mějme $\varphi(N) := |\Z^*_N|$, pak pokud $x \perp N$, pak $x^{\varphi(N)} \equiv 1 \mod{N}$​

Důkaz:

Teorie čísel

Čínská zbytková věta (CRT)

Věta: mějme $N_1, N_2 \dots , N_k$ navzájem nesoudělné a $N = \prod_i N_i$, pak $\Z_N \equiv \Z_{N_1} \times \Z_{N_2} \times \cdot \times \Z_{N_k} $

Důkaz 1

Důkaz 2

Výpočet $\varphi(n)$​

  1. $\varphi(p) = p-1$​
    • víme z definice tělesa $\Z_p$
  2. $\varphi(p^k) = p^k - \frac {p^k} p = (p-1) \cdot p^{k-1}$
    • ptáme se, kolik čísel od z $1, 2, \dots, p^k-1$ není soudělné s $p^k$
      • to je to samé, jako se ptát na nesoudělnost s $p$
    • každé $p$-té číslo je dělitelné a žádné jiné není
  3. pro $x \perp y$ máme $\varphi(xy) = \varphi(x) \cdot \varphi(y)$
    • lze vidět z CRT
    • zvolíme $f: \Z_{xy} \to \Z_x \times \Z_y$​
    • pro číslo $a \in \Z_{xy}$ platí, že $a \perp xy \iff a \perp x \;\and\; a \perp y$
      • v obrazu máme $\varphi(x)$ řádkových indexů nesoudělných s $x$ a $\varphi(y)$ sloupcových indexů nesoudělných s $y$​ (z definice)
      • počet splňujících dvojic v obrazu je $\varphi(x)\cdot\varphi(y)$ a jelikož je $f$ bijekce, pak je tento počet roven počtu splňujících dvojic v předobrazu

Faktorizace

Testy prvočíselnosti

Fermatův test

Carmichaelova čísla

Pravděpodobnost

Rabin-Millerův test

  1. vybereme náhodně $x \in_R \Z_N$

  2. pokud $\gcd(x, N) \ne 1$, $x$ je složené – Eulerův svědek

  3. spočítáme $x^{N-1} \mod N$

    • pokud výsledek není 1, $x$ je složené – Fermatův svědek

    spočítáme $x^\frac{{N-1}}{2} \mod N$

    spočítáme $x^\frac{{N-1}}{4} \mod N$

    spočítáme $x^{\frac {N-1} {2^k}} \mod N$

    …

    dokud není exponent lichý

Správnost

Věta Rabin:

Věta Miller:

Generování velkých prvočísel

Diskrétní logaritmus

Věta: $\Z_p^*$ je cyklická grupa (pro prvočíselné $p$)

Diskrétní odmocniny

Modulo prvočíslo

Kvadratické zbytky

Eulerovo kritérium

Věta: $x \ne 0$ je QR $\iff x^{\frac {p-1}2} \equiv 1$

Důkaz:

  1. $x = g^{2k}$
    • $g^{2k \cdot \frac{p-1}2} \equiv g^{k \cdot (p-1)} \equiv (g^{p-1})^k \equiv 1^k \equiv 1$
  2. $x = g^{2k+1}$
    • $g^{(2k + 1) \cdot \frac{p-1}2} \equiv g^{2k\cdot \frac{p-1}2 + \frac{p-1}2} \equiv 1 \cdot g^{\frac{p-1}2} \equiv 1 \cdot (-1) \equiv -1$​

Důsledek:

Modulo složené číslo

RSA

Klíč

Šifrování

Korektnost

Efektivita

Zrychlovací triky

Důležité vlastnosti

Slepé podpisy

Útoky

Špatná volba parametrů

$$ \begin{align*} n &= pq \\ \varphi(n) &= (p-1)(q-1) = pq - p -q + 1 \end{align*} $$

Meet in the middle attack

Podobné zprávy

Podobná prvočísla $p$ a $q$

Několik klíčů se stejným $n$​

Tatáž zpráva zašifrována klíči s různými $n$​

Chyba při výpočtu

RSA leaks

Leak Jacobiho symbolu

Sémantická bezpečnost RSA

Věta: pokud máme orákulum pro $\text{parity}$ nebo pro $\text{half}$, pak umíme dešifrovat v $\mathcal{O}(\text{poly}(b))$

Orákulum pro half

Orákulum pro parity

Padding Schemes

PKCS#1 v1.5

PKCS#1 v1.5

Bleichenbacherův útok

PKCS#1 v2.0

PKCS#1 v2.0

Diffie-Hellman

Útoky na DH

Man-in-the-middle attack

Útok na veřejné parametry

Man-in-the-middle na veřejných parametrech

Information leak

Podgrupy

Jak se vyhnout velkým exponentům

Sémantická bezpečnost

ElGamalův kryptosystém

Eliptické křivky

Asymetrické podpisy

Útoky

RSA podpis

Existenční padělání

Cílené padělání

ElGamalův podpis

DSA

Kryptografické protokoly

Implementační pasti

Side channels

Remote attacker

In the same room

Physical access

Run my code

Cache-based AES attack

Udržování tajemství

Hesla

Uchovávání hesel

Předpočítávání hashů hesel

graph LR
	password1 -- h --> hash -- sampling function --> password2

graph LR
	p1 --> p2 --> p3 --> mid:::hidden --> pn

Rainbow tables

Rainbow table

Ochrana proti brute-force útokům

PBKDF2

Challenge-response autentikace

sequenceDiagram
	participant c as client
	participant s as server
	
	c ->> s: login
	s ->> c: nonce, salt
	c ->> s: HMAC( h( passwd || salt ), nonce )
	
	note right of c: znalost HMAC podpisu nám nepomůže v získávání hashe hesla
	note right of c: podpis závisí na nonci, imunní vůči replay útokům

SCRAM

sequenceDiagram
	participant c as client
	participant s as server
	
	c ->> s: login a client-nonce
	s ->> c: salt, server-nonce, #iterací
	c ->> s: client-proof
	note right of c: client-proof = Kc XOR HMAC( h(Kc), transkript )
	s ->> c : server-proof
	note left of s: server-proof = HMAC( Ks, transkript )
	note left of s: nepovinné (myslim)

DNSSEC

Záznamy

Ta jakože security část

TODO: tady chybí docela velká část o PKI a chain-KDF (a už se mi nechce ji dopisovat, sry)

TLS

TLS 1.3

Record protokol

Key schedule

TLS Key Shedule z tabule

Handshake

sequenceDiagram
	participant c as client
	participant s as server
	
	c ->> s: Client Hello
	Note right of c: key share, nabízené parametry, nabídka PSK
	
	s ->> c: Server Hello
	Note left of s: key share, vybrané parametry, vybrané PSK
	
	alt šifrovaná část
		s ->> c: Certificate
		s ->> c: (Cert Request)
		Note left of s: někdy chceme i autentikaci klienta
		s ->> c: Cert Verify
		Note left of s: podpis dosavadních zpráv certifikovaným klíčem
		s ->> c: Finished
		s ->> c: Začíná posílat aplikační data
		Note left of s: pokud nepotřebujeme autentikaci klienta
		
		c ->> s: <br/><br/><br/> Certificate
		c ->> s: Cert Verify
		c ->> s: Finished
		c ->> s: Začíná posílat aplikační data
		
	end

Rozšíření

Internet PKI

Motivace

Obsah certifikátu

Zneplatňování certifikátů

CRL

Custom revocation list

OCSP

OCSP Stapling

Limited lifetime

Certificate Transparency project