Kryptografiske hashfunksjoner

En kryptografisk hashfunksjon $H: \{0,1\}^* \to \{0,1\}^n$ tar en vilkårlig lang melding og produserer en fast $n$-bits hash (digest). Tre kryptografiske krav:

Forhåndsbildemotstand (preimage resistance): Gitt $h$, er det beregningsmessig ugjørlig å finne $m$ slik at $H(m) = h$. (Én-veis)
Andre forhåndsbildemotstand (second preimage resistance): Gitt $m_1$, er det beregningsmessig ugjørlig å finne $m_2 \ne m_1$ slik at $H(m_1) = H(m_2)$.
Kollisjonsmotstand: Det er beregningsmessig ugjørlig å finne NOEN $m_1 \ne m_2$ slik at $H(m_1) = H(m_2)$.

Hierarki: Kollisjonsmotstand ⟹ andre forhåndsbildemotstand ⟹ forhåndsbildemotstand (implikasjonene holder én vei).

Bursdagsparadokset og angrepskompleksitet

For en hashfunksjon med $n$-bits output:

Forhåndsbildeangrep: $O(2^n)$ operasjoner
Kollisjonsangrep (bursdagsangrep): $O(2^{n/2})$ operasjoner

SHA-256 (256 bits) gir 128-bits kollisjonssikkerhet, SHA-512 gir 256-bits. SHA-1 (160 bits) gir 80-bits effektiv kollisjons-sikkerhet — brutt i praksis (SHAttered, 2017).

SHA-2 og SHA-3

SHA-2: Merkle-Damgård-konstruksjon (iterativ kompresjon). Familien inkluderer SHA-256 og SHA-512. Svakhet: Length extension attack — gitt $H(m)$ og lengden av $m$, kan angriperen beregne $H(m \| \text{pad} \| m')$ uten å kjenne $m$. Dette gjør $H(k \| m)$ utrygg som MAC.

SHA-3 (Keccak): Basert på sponge-konstruksjon. Immun mot length extension attacks. Bruker absorber-fase (input) + press-fase (output). Valgt som alternativ standard, ikke erstatning for SHA-2.

HMAC

HMAC er en message authentication code (MAC) basert på en hashfunksjon:

$$\text{HMAC}_k(m) = H\bigl((K \oplus \text{opad}) \| H\bigl((K \oplus \text{ipad}) \| m\bigr)\bigr)$$

Der $\text{ipad} = \texttt{0x36}$ gjentatt, $\text{opad} = \texttt{0x5C}$ gjentatt. Den doble hashing-strukturen beskytter mot length extension attacks. HMAC-SHA256 brukes i TLS, JWT og IPsec.

Hash vs MAC vs signatur

Primitiv	Nøkkel	Gir	Ikke-avvisning?
Hash (SHA-256)	Ingen	Integritet (ikke autentisitet)	Nei
MAC (HMAC)	Symmetrisk	Integritet + autentisitet	Nei (delt nøkkel)
Digital signatur	Asymmetrisk	Integritet + autentisitet	Ja

Autentisert kryptering (AEAD)

AEAD kombinerer kryptering og MAC: gir konfidensialitet OG integritet+autentisitet. Associated Data (AD) autentiseres men krypteres ikke. AES-GCM er AEAD: CTR-kryptering + GHASH-tag. ChaCha20-Poly1305 er et alternativ (TLS 1.3).

Eksempel 1 — Length extension attack mot SHA-256

En server verifiserer $H(k \| \text{kommando})$ med SHA-256 og ukjent nøkkel $k$. Angriperen kjenner $H(k \| \texttt{delete=false})$. Kan angriperen forfalske?

Ja. SHA-256 er Merkle-Damgård. Angriperen kan beregne $H(k \| \texttt{delete=false} \| \text{padding} \| \texttt{\&delete=true})$ uten å kjenne $k$, kun fra den kjente hashverdien og kjent meldingslengde.

Løsning: bruk HMAC i stedet for $H(k \| m)$.

Studieguide: Hashfunksjoner og meldingsautentisering (MAC)