Blokkchiffer — grunnprinsipper

Et blokkchiffer er en deterministisk funksjon $E_k: \{0,1\}^n \to \{0,1\}^n$ som tar en $n$-bits klartekstblokk og en nøkkel og produserer en $n$-bits chiffertekst. Sikkerhet er basert på to prinsipp (Shannon):

Konfusjon: Gjøre forholdet mellom nøkkel og chiffertekst så komplekst som mulig (S-bokser).
Diffusjon: Spre effekten av ett klartekst-bit over mange chiffertekst-bit (permutasjoner, MixColumns).

DES (Data Encryption Standard)

DES er en 16-runders Feistel-nettverkschiffer med 64-bits blokk og 56-bits effektiv nøkkel. Feistel-strukturen tillater kryptering og dekryptering med identisk hardware (bytt bare rekkefølgen på undernøklene).

Feistel-rund:

L_{i+1} = R_i
R_{i+1} = L_i XOR f(R_i, K_i)

Rundefunksjonen $f$ inkluderer ekspansjon (32→48 bit), XOR med undernøkkel, 8 S-bokser (6→4 bit, ikke-lineær) og P-permutasjon (32→32 bit).

Svakheter: 56-bits nøkkel er for kort — DES ble brutt med exhaustive search i 1998 (EFF DES cracker: under 23 timer). Triple-DES (3DES) $= E_{k_1}(D_{k_2}(E_{k_1}(m)))$ fikser nøkkellengde men er treg.

AES (Advanced Encryption Standard)

AES er en substitusjons-permutasjons-nettverkschiffer (ikke Feistel) med 128-bits blokk og 128, 192 eller 256-bits nøkkel (10, 12 eller 14 runder). Standarden siden 2001.

AES opererer på en $4 \times 4$ matrise av bytes («state»), fire operasjoner per runde:

SubBytes: Erstatt hvert byte med oppslaget i AES S-boksen (ikke-lineær, basert på invers i $GF(2^8)$).
ShiftRows: Skift rad $i$ syklisk med $i$ posisjoner til venstre (diffusjon på tvers av kolonner).
MixColumns: Multipliser hver kolonne med en fast matrise over $GF(2^8)$ (diffusjon mellom rader).
AddRoundKey: XOR state med en 128-bits undernøkkel avledet fra hovednøkkelen.

Siste runde mangler MixColumns. Dekryptering bruker inverse operasjoner: InvSubBytes, InvShiftRows, InvMixColumns.

Krypteringsmodi

Et blokkchiffer krypterer én blokk. For å håndtere vilkårlig lange meldinger brukes en driftsmodus:

Modus	Kryptering	Paralleliserbar enc/dec	IV?	Padding?
ECB	$C_i = E_k(P_i)$	Ja/Ja	Nei	Ja
CBC	$C_i = E_k(P_i \oplus C_{i-1})$	Nei/Ja	Ja	Ja
CTR	$C_i = P_i \oplus E_k(\text{nonce}\\|i)$	Ja/Ja	Ja (nonce)	Nei
GCM	CTR + GHASH-autentisering	Ja/Ja	Ja (nonce)	Nei

ECB-problemet: ECB krypterer identiske blokker til identiske chiffertekstblokker — strukturen i klarteksten lekkes. Det berømte «ECB penguin»-eksemplet (Linux-pingvinens silhuett er fortsatt synlig etter AES-ECB-kryptering av bitmap) illustrerer dette.

CTR: Gjør blokkchifferet til et strømchiffer. IV/nonce + teller krypteres og XORs med klartekst. KRITISK: Nonce må aldri gjenbrukes med samme nøkkel — nonce-reuse ødelegger konfidensialiteten ($C_1 \oplus C_2 = P_1 \oplus P_2$).

GCM (Galois/Counter Mode): CTR + polynomial MAC over $GF(2^{128})$ (GHASH). Gir autentisert kryptering (AEAD). Brukes i TLS 1.3.

Eksempel 1 — CBC-kryptering og -dekryptering

Blokkstørrelse = 64 bit. Nøkkel $k$, IV $= C_0$. Klartekst $P_1, P_2$. Vis kryptering og dekryptering.

Kryptering: $C_1 = E_k(P_1 \oplus C_0)$; $C_2 = E_k(P_2 \oplus C_1)$.

Dekryptering: $P_1 = D_k(C_1) \oplus C_0$; $P_2 = D_k(C_2) \oplus C_1$.

Kryptering er sekvensiell (kjenner ikke $C_1$ før $P_1$ er kryptert). Dekryptering er paralleliserbar (alle $C_i$ kjent).

Eksempel 2 — Analyse av en ikke-standard modus (klassisk skriftlig oppgave 2)

En modus likner CTR men er ulik: $C_t = O_t \oplus P_t \oplus C_{t-1}$, der $O_t = E_k(T_t)$, $T_t = N \| t$ (nonce og blokknummer) og $C_0 = 0$. (a) Finn dekrypteringslikningen. (b) Hvor mange blokker forplantes hvis ett bit i $C_t$ endres under overføring? (c) Kan kryptering/dekryptering paralleliseres?

(a) Løs for $P_t$: $P_t = C_t \oplus O_t \oplus C_{t-1}$, der $O_t = E_k(N\|t)$. Merk at $O_t$ ikke avhenger av klartekst, kun av nonce og teller.

(b) Ett endret bit i $C_t$ påvirker (i) blokk $t$ direkte (samme bitposisjon flippes i $P_t$, fordi $O_t$ og $C_{t-1}$ er uendret) og (ii) blokk $t{+}1$, fordi $C_t$ inngår i $P_{t+1} = C_{t+1}\oplus O_{t+1}\oplus C_t$. Til sammen to blokker, hver med ett bit feil — feilen forplantes ikke videre.

(c) Kryptering er sekvensiell ($C_{t-1}$ må være kjent). Dekryptering er paralleliserbar: alle $O_t$ kan forhåndsberegnes uavhengig, og alle $C_t, C_{t-1}$ er kjent fra start.

Padding

PKCS#7 padding: Legg til $n$ bytes, hver med verdien $n$, der $n$ er antall bytes som mangler for å fylle blokken (alltid minst 1 byte padding). Eksempel: 3 bytes mangler → append $\texttt{03 03 03}$.

Padding oracle attack: Angriperen tester om dekryptert chiffertekst har gyldig PKCS#7 padding. Med tilstrekkelig mange «orakel»-forespørsler kan angriperen dekryptere vilkårlig chiffertekst byte for byte. Viser at kryptering uten autentisering (MAC) er farlig — løsningen er autentisert kryptering (AEAD).

Studieguide: Symmetrisk blokkryptering (DES og AES)