Funcions
de hash
“Curs d'Introducció a la criptografia”
by Jordi Íñigo Griera is licensed under a
Creative Commons Attribution 4.0 International License.
Project hosted at github.com/jig/crypto
Funció de hash: objectius
resumeix una cadena de longitud arbitrària $m$,
a un valor de mida fixa $r$ (el resum):
$r = h(m)$
addicionalment, cal que la funció dongui resums diferents per missatges diferents...
Col·lisions
...és impossible garantir que una funció generi valors diferents per missatges diferents ja que
l'espai de resums és molt inferior a l'espai de missatges:
$\|r\| \ll \|m\|$
per exemple si:
$\left.
\begin{aligned}
\|r\| & = 256\text{b} \Rightarrow |r| = 2^{256}\text{b} \\
\|m\| & \approx 10^6\text{B} \Rightarrow |m| = 2^{2^{23}}\text{b}
\end{aligned}
\right\} \frac{|m|}{|r|} = \frac{2^{2^{23}}}{2^{256}} = 2^{2^{23}-256} \approx 2^{8·10^6}$
Funció de hash: objectius
tot i que per a cada resum $r$ hi ha una enorme quantitat de missatges que el comparteixen (hi col·lisionen) una funció de hash segura ha de fer que sigui infactible trobar-los
donat un missatge $m$ amb un resum $r = h(m)$ trobar un missatge amb el mateix resum $m$ la manera més eficient ha de ser generar missatges fins a trobar una altre amb el mateix resum $r$
e.g. si el resum és de $\|r\| = 256$ llavors haurem de fer unes $\frac{2^{256}}{2} = 2^{255}$ operacions de hash fins a trobar-ne un d'igual
Problema de l'aniversari
(Birthday paradox)
hi ha un atac millor que l'anterior de força bruta, que deriva de
la paradoxa de l'aniversari:
“si tenim un grup de 23 persones, la probabilitat de tenir un parell amb la mateixa data d'aniversari és del 50%”
només cal un grup de 70 persones per a que la probabilitat augmenti al 99%
en general, $p=0.5$ si el nombre d'experiments és $x \approx 1,25 \sqrt{\text{elements}}$
Atac de l'aniversari
(Birthday attack)
si tenim un hash de mida $\|r\|$ la probabilitat de col·lisió serà molt alta quan ens apropem a les $\sqrt{|r|}$ operacions
e.g per a $\|r\| = 256\text{ b}$ això són unes $2^{128}$ operacions
això implica que per a un hash cal resums el doble de llargs del que calia per les claus per a obtenir el mateix nivell de seguretat
(la security strength d'una funció de hash de longitud $b$ bits és $b/2$)
exemples
els hashos recomenats en l'actualitat són els SHA-2 i el SHA-3
- SHA-2: longituds de $256$ b i $512$ b (amb variants truncades de $224$ b i $384$ b)
- SHA-3: longituds entre $224$ b a $512$ b
longituds aproximadament el doble que les longituds de claus que les claus de l'AES ($128$ b, $192$ b, $256$ b) per a una seguretat equivalent
SHA-2 ò SHA-3?
els primers estan dissenyats per l'NSA, i els segons escollits pel NIST després d'organitzar una competició per a definir el següent hash a utilitzar
el SHA-3 s'ha desenvolupat tenint en compte l'eficiència i com a backup cas de trobar vulnerabilitats en el SHA-2 (disseny totalment diferent)
SHA-2 ara per ara té un treball d'anàlisi molt superior
al SHA-3
HMAC
MAC basat en funcions Hash
MAC: objectiu
prova d'integritat:
impedeix que un atacant pugui modificar el missatge sense que el receptor se n'adoni
aquesta funcionalitat és ortogonal amb el xifrat:
xifrat i MAC es fan servir juntes per a obtenir confidencialitat i integritat
Nota sobre el xifrat: un atacant pot modificar el missatge, encara que no el pugui
llegir
(fins hi tot en alguns casos pot realitzar operacions: e.g. $\oplus$ en xifrat de flux)
MAC: casos d'ús
- en una transmissió, volem validar que el que ens envien no ha estat modificat per un atacant
(cal acordar una clau $k$ prèviament) - en una sistema de fitxers, volem saber que els fitxers que varem guardar-hi no han estat
alterats per un atacant, virus, etc. quan hi tornem a accedir
(cal recordar la clau $k$)
MAC: funcionament
ens caldrà una clau secreta que aplicarem al missatge amb la funció $\text{MAC}$:
$t = \text{MAC}(k, m)$
HMAC basat en Hash+MAC
si fem servir un MAC per missatges de mida fixa
(directament xifrant un bloc)
podem fer un HMAC així:
$t = \text{MAC}(k, h(m))$
SHA2-HMAC
el HMAC que es fa servir habitualment fa servir com a xifrat el propi hash i $\oplus$
$\begin{aligned} k_\text{o} = k \oplus \text{opad} \; &| \; \text{opad} = \text{5C5C}\cdots \\ k_\text{i} = k \oplus \text{ipad} \; &| \; \text{ipad} = \text{3636}\cdots \\ \end{aligned}$
$t = \color{red}{h}( k_\text{o} \, \| \, \color{red}{h}( k_\text{i} \| m ) )$
Nota: $\|$ denota concatenació
Nota: variants òbvies com $t = h(k \| m)$ són insegures [9.64][9.65]
xifrar i autenticar
(Authenticated Encryption)
aquestes dues funcions es fan servir juntes molt sovint
enviarem la concatenació $(c, t)$ on:
$\begin{aligned}
c &= e(k_e, m) \\
t &= \text{MAC}(k_t, c)
\end{aligned}$
Nota: fer $t = \text{MAC}(k_t, \color{red}{m})$ no garanteix que la funció MAC no reveli cap detall d'$m$ (en realitat ho fa: si dos missatges són iguals, un atacant ho sabrà simplement inspeccionant $t$ i $t'$
seguretat en conjunts de missatges
cal vigilar que la seguretat amb la que protegim els missatges individuals, cal extrapolar-la a seqüències de missatges (sessions)
si no fem res més del que hem comentat fins ara, seriem vulnerables a atacs:
- de rèplica (replay attacks)
- de reordenat
- de reflexió