Biți relative de securitate ale funcțiilor mai lente

Lăsând deoparte ipotezele privind duritatea memoriei, unele funcții hash lente sunt versiuni repetate de lanț hash sărat ale hashurilor criptografice obișnuite. Aceasta este de obicei definită de a rundă parametru, adică în PBKDF2. Există vreo hârtie de criptografie care abordează definiția biților de securitate pe baza factorului de runde de invocări liniare succesive (nu paralele) pentru un calcul de ieșire?

Adică, un exemplu concret: este spargerea unei imagini prealabile a sha3(sare_proaspătă, valoare_intrată) mai usor decat sha3(sha3(sha3(sha3(sare_proaspătă, valoare_de intrare)))) pentru o entropie scăzută valoare_intrare (adică, 64 de biți), iar dacă da acesta din urmă oferă 2 biți de securitate suplimentară, deoarece efortul relativ cerut de atacator este de 4 ori mai mare? Orice lucrare de cercetare care discută acest lucru (efortul contradictoriu relativ necesar între funcțiile independente sau dependente liniar vs. bucăți pragmatice de securitate oferită)?

• Această întrebare este similară cu Implicațiile de securitate ale hash-urilor slow-by-design asupra securității relative față de dimensiunea hash-ului, dar sunt mai ales interesat de un răspuns legat de dovada de securitate.

Au existat noțiuni rafinate despre ce înseamnă să aibă un protocol $\lambda$-biti de securitate. Cel mai cunoscut este probabil Micciancio-Walter Despre securitatea biților a primitivelor criptografice.

Noțiunea de securitate a biților este diferită dacă se lucrează cu a

• joc de decizie, unde este $\min_A\log_2 \frac{T(A)}{(\mathsf{adv}^A)^2}$, adică cântare pătratic cu avantajul contradictoriu, sau

• joc de căutare, unde este $\min_A \log_2 \frac{T(A)}{\mathsf{adv}^A}$, adică cântare liniar cu avantajul contradictoriu.

The $\min_A$ este minimizarea asupra tuturor adversarilor care atacă un primitiv și $T(A)$ este timpul de rulare al $A$. Rețineți că avantajele pentru jocurile de căutare/de decizie sunt definite diferit (pentru jocurile de căutare, este aproximativ probabilitatea de succes, pentru jocurile de decizie, este $2\delta-1$, Unde $\delta$ este probabilitatea de succes).

Oricum, în acest cadru ai putea încerca să demonstrezi ceva de genul

Dacă $H(\cdot)$ este o funcție hash care este $\kappa$-bit rezistent la pre-imagine, atunci $H^{\circ k}(\cdot)$, cel $k$-compoziţia pliului de $H$, este $(\log_2(k) + \kappa)$-biți rezistent la pre-imagine.

Dovada este aproximativ după cum urmează

1. Începe cu $\min_A \log_2 \frac{T(A)}{\mathsf{adv}_H^A}\geq \kappa$, Unde $\mathsf{adv}^A_H$ este avantajul $A$ într-un joc care definește rezistența pre-imagine.

2. Stabiliți un fel de avantaj legat $\mathsf{adv}_{H^{\circ k}}^A \leq \mathsf{adv}_H^A$, ținând evidența timpului de rulare al noului adversar $B$ se construiește (implicit) ca parte a acesteia.Pentru simplitate, presupuneți că $\mathsf{adv}_{H^{\circ k}}^B \leq \mathsf{adv}_H^A$, și $T(B) = kT(A)$ --- nu îmi este clar că acest lucru este adevărat, dar cred că această presupunere este implicită în întrebarea dvs.

3. Apoi, avem asta $\min_B \frac{T(B)}{\mathsf{adv}_{H^{\circ k}}^B} \geq \min_A\frac{kT(A)}{\mathsf{adv}_{ H}^A} = \log_2 k + \kappa$.

După cum subliniază numărul 2 de mai sus, acest lucru se reduce cu adevărat la afișarea unui avantaj (tradițional) legat de formă.

Pentru orice adversar $B$ împotriva $SHA3^{\circ k}$, există un adversar $A$ împotriva $SHA3$ cu

• $T(B) = kT(A)$, și
• $\mathsf{adv}^B_{SHA3^{\circ k}} \leq \mathsf{adv}^A_{SHA3}$.

Aceasta înseamnă că cadrul MW permite să discutăm cât de mult este timpul de rulare mai mare $B$ are un impact asupra securității (care este întrebarea dvs.), dar trebuie totuși să dovediți un avantaj legat.

Câteva gânduri despre asta, nu sunt chiar sigur dacă răspunsul meu vă va acoperi și probabil că are defecte.

Mai întâi câteva lucruri despre securitate. Când spunem că o schemă criptografică are $λ$ biți de securitate ceea ce vrem să spunem de obicei este că singura modalitate de a o sparge este să forțați cu forță brută informațiile din trapă și așa să încercați $2^λ$ combinatii. Bineînțeles că nu luăm în considerare niciun alt tip de atacuri, atacuri cu canale laterale etc. Apoi luăm în considerare un model advers, de ex. mărginit computaţional. Și dacă demonstrăm că schema este sigură împotriva acestui adversar, atunci spunem că este sigură $λ$ bucăți de securitate.

Din moment ce vă referiți la securitatea teoretică, răspunsul este Nu. Probabil că da dacă te-ai referi la securitate cantitativă. Voi încerca să ofer un contraexemplu foarte intuitiv.

În loc să luați în considerare o funcție hash, luați în considerare Textbook RSA cu umplutură adecvată, de exemplu. Să-i definim securitatea doar în termeni de securitate semantică. Deci este sigur și așa spunem că este $1^λ$ bucăți de siguranță, dacă există $PPT$ adversar (pe parametrul de securitate) orice pereche de mesaje de aceeași lungime $m_1, m_2$, textele lor cifrate corespoding nu se pot distinge din punct de vedere computațional. Dacă ipoteza RSA este valabilă, știm că RSA este sigură din punct de vedere semantic.

Acum luați în considerare o nouă schemă în care $c=Enc_k(Enc_k(x))$. Dacă ultima schemă de criptare ar fi mai sigură decât prima, aceasta ar însemna că adversarul ar putea obține un avantaj neneglijabil într-un joc în care i se oferă câte două texte cifrate, fiecare criptat cu cele două scheme, de ex. distribuțiile ar trebui să fie deloc de neglijat apropiate. Din ipoteza RSA, acest lucru nu poate fi cazul.