Aș dori să înțeleg algebra din spatele securității GCM.
Ei bine, ați scris mecanica modului în care funcționează piesa de autentificare a GCM; totuși, pentru a înțelege de ce acești mecanici funcționează, ar fi util să-l abordăm într-un mod diferit.
GCM folosește aritmetica în $GF(2^{128})$; acesta este un camp; punctul important este că, într-un domeniu, cel mult orice polinom de grad diferit de zero $n$ are cel mult $n$ zerouri; adică pentru orice ecuație:
$$a_n x^n + a_{n-1} x^{n-1} + ... + a_0 x^0 = 0$$
are cel mult $n$ solutii pentru $x$ (presupunând că cel puțin unul dintre $a_i$ valorile nu sunt zero).
De ce acest lucru este critic va fi clar mai târziu.
Acum, ceea ce face GCM pentru a se autentifica este că ia datele criptate (și AAD) și le traduce într-un polinom; apoi convertește nonce ca valoare constantă a polinomului și apoi evaluează acel polinom la o valoare secretă $k$, iar rezultatul acelei evaluări este eticheta; acesta este:
$$tag := a_n k^n + a_{n-1} k^{k-1} + ... + a_1 k^1 + \text{hash}(nonce)$$
Acum, să presupunem că avem o pereche mesaj/etichetă diferită pentru același nonce; acel mesaj/etichetă ar trece verificarea integrității GCM dacă:
$$tag' := a'_n k^n + a'_{n-1} k^{k-1} + ... + a'_1 k^1 + \text{hash}(nonce)$$
Ceea ce putem face este să scădem cele două polinoame (cel corespunzător textului cifrat bun care a fost generat de criptatorul valid și cel corespunzător ghicirii de către atacator); obținem atunci [1]:
$$0 = (a_n-a'_n)k^n + (a_{n-1} - a'_{n-1})k^{n-1} + ... + (a_1 - a'_1) k^1 + (etichetă - etichetă')k^0$$
Această ecuație este valabilă numai dacă a doua pereche text cifrat/etichetă este validă.
Acum, ne întoarcem la observația noastră inițială: acesta este cel mult un polinom de grad $n$ si asa sunt cel mult $n$ valori diferite ale $k$ pentru care această ecuație este adevărată. De asemenea, știm că cel puțin un coeficient al polinomului este diferit de zero (polinomul total zero este adevărat dacă textul cifrat „falsificat” este exact același cu cel valid, care nu este considerat un fals). Si daca $k$ este selectat imprevizibil, apoi există $2^{128}$ valori posibile, deci probabilitatea ca se întâmplă să fie una dintre acestea $n$ valorile este cel mult $n2^{-128}$, care este cu adevărat minuscul.
Acum, pentru a transforma acest argument într-o dovadă reală (care a fost făcută), trebuie să presupunem că a) $k$ este selectat uniform la întâmplare și b) $\text{hash}(nonce)$ de asemenea, este selectat aleatoriu (pentru că, dacă nu, atacatorul poate deduce unele lucruri despre valoarea polinomului, ceea ce ar fi rău); se dovedește că le putem lega pe ambele de puterea criptografică a AES.
Acum, pentru a vă răspunde la întrebări:
- Este corect cele de mai sus?
Închide; ai greșit un detaliu; folosind notația dvs., obținem calculul etichetei ca $tag_k(c_1, c_2,...c_n) = c_0 + \sum k^nc_n$ (Rețineți că $c_0$ nu se inmulteste cu $k$):
- Cum alege AES-GCM $k$?
Criptează blocul total zero folosind AES folosind cheia GCM.
- Dacă $k=0$, $tag(\text{any_ciphertext})=0$
Nu, $c_0$ nu se inmulteste cu $k$, deci avem în acest caz:
$$tag(\text{any_ciphertext}) = c_0$$
Înseamnă în continuare că, în acest caz specific, textul cifrat poate fi modificat în mod arbitrar fără modificarea etichetei, însă nu este evident.
Întrebarea evidentă este: „Nu este încă rău?”. Ei bine, cu o etichetă de 128 de biți, atacatorul are întotdeauna o probabilitate $2^{-128}$ de a ghici orbitor o pereche de text cifrat/etichetă validă - $k=0$ are aceeași probabilitate de a se produce și, prin urmare, nu crește probabilitatea de falsificare.
- Face $c_n=0$ pune o problema?
Nu; dacă treci prin logica de mai sus, $c_n=0$ nu este un caz special.
- Dar dacă $k$ se întâmplă să fie de ordin scăzut, schema va eșua.
Acest scenariu de eșec specific încă se încadrează în probabilitate $n2^{-128}$ așa cum se arată mai sus; dacă (spuneți) testați dacă $k$ a avut o comandă mică și respinge acele valori, de fapt nu vei reduce probabilitatea de falsificare.
[1]: Într-un domeniu uniform caracteristic precum $GF(2^{128})$, adunarea și scăderea sunt aceeași operație, așa că de obicei scriem ambele ca $+$; L-am păstrat ca $-$ a face este ceva mai clar pentru cineva neobișnuit cu asemenea convenții.
