Vreun avantaj pentru un cifru bloc care nu este inversabil eficient?

Definiția clasică a unui PRP include invertibilitatea eficientă.

Având în vedere că multe moduri de criptare moderne (bazate pe CTR, de exemplu, GCM) utilizează numai direcția înainte a cifrului bloc, se pare că partea eficientă a invertibilității a definiției nu este de fapt necesară în scopuri practice.

O astfel de relaxare ne-ar câștiga ceva? adică există construcții practice PRP care pot fi calculate eficient în direcția înainte, dar nu în direcția inversă? Și care sunt mai eficiente în direcția înainte decât cifrurile bloc actuale cu securitate echivalentă?

Aș susține că pentru mulți criptografi argumentul merge chiar mai departe. Având în vedere că modurile de streaming cu criptare bloc sunt preferate pentru criptarea în bloc, este necesară inversibilitatea? Dacă urmează acest raționament de linie, se poate vedea de ce a existat o renaștere a popularității cifrurilor în flux, ChaCha20 fiind un exemplu evident. Deși ChaCha20 produce o ieșire de 512 biți dintr-o stare de 512 biți și actualizează starea cu un contor simplu (la fel ca modurile CTR și GCM), procesul nu este (credem) inversabil. De asemenea, este adevărat că ChaCha20 este un design foarte eficient (presupunând că hardware-ul acceptă adăugarea eficientă a cuvintelor pe 32 de biți).

Rețineți că, pentru multe implementări ale AES, funcția rotundă de decriptare este mai puțin eficientă decât funcția rotundă de criptare, deoarece inversează MixCol procesul este mai implicat din punct de vedere computațional.

Un PRP este Permutarea pseudo-aleatorie și vrem să nu se distingă de permutările aleatorii. AES și toate cifrurile bloc ar trebui să fie PRP. Permutarea înseamnă că există un invers și sunt proiectați să aibă unul și într-adevăr să aibă unul eficient.

Avem nevoie de un mod de operare pentru cifrurile bloc și am părăsit CBC din cauza numeroaselor atacuri care au avut loc deși are Ind-CPA securizat.În prezent, toate cifrurile TLS 1.3 utilizează în mod intern modul CTR securizat Ind-CPA (suitele de criptare TLS 1.3 sunt mai mult decât atât, toate sunt moduri de criptare autentificată cu date autentificate)

O astfel de relaxare ne-ar câștiga ceva?

Ne oferă o mulțime de oportunități. Nu trebuie să ne limităm la PRP în modul CTR - a fost deja conceput pentru Funcții pseudo-aleatorie (PRF); Modul CTR nu are nevoie de inversul funcției. Cu PRF putem folosi o gamă largă de funcții care nu trebuie să aibă inverse (Există $2^n!$ PRP-uri și $(2^n)^{2^n}$ PRF pentru cifrurile bloc de n biți. Chiar și noi putem lua o funcție hash și o convertim în criptare CTR ca în Salsa. Putem proiecta și un program cheie la costuri aproape zero.

Utilizarea PRP în modul CTR poate cauza deosebitorul mesajului lung și putem elimina acest lucru folosind un PRF. Dacă folosim PRP în modul CTR, atunci trebuie să restricționăm numărul de blocuri de criptare din cauza lemei de comutare PRP-PRF.

Modul CTR, de asemenea, nu necesită umplutură, așa că sunt imuni la atacurile oracolului de umplutură.

ChaCha20 și Salsa20 sunt exemple binecunoscute care au costuri zero ale programului cheie, design ARX cu CPU prietenos. Au modul CTR încorporat și sunt foarte rapide în software.

Într-adevăr, un PRF este mai potrivit decât un PRP pentru diferite moduri, cum ar fi CTR.Problema este că nu știm cum să construim PRF-uri bune altfel decât dintr-un PRP.

1. O modalitate este pur și simplu să pretindem că PRP-ul nostru este un PRF: și acest lucru este adevărat, se oferă până la o anumită cantitate de date (limita zilei de naștere, vezi lema de comutare PRP/PRF).

2. O altă modalitate des folosită este de a calcula PRP/permutația și de a adăuga intrare la ieșire. Nu îmbunătățește legarea zilei de naștere, dar acest truc face ca funcția să nu fie inversabilă, ceea ce este crucial în unele utilizări (cum ar fi ChaCha menționat de @Daniel S). De asemenea, este folosit în funcțiile hash în stilul Merkle-Damgard pentru a construi funcția de compresie (Davis-Meyer).

3. Adăugarea/surarea a două permutări este un PRF bun, dar este costisitor.

4. Trunchierea suficientă a ieșirii este, de asemenea, un PRF bun, dar din nou este costisitor.

Merită menționată criptografia pe bază de burete, care se bazează pe permutări publice, care sunt evaluate doar în direcția înainte. Cu alte cuvinte, nu este necesar ca permutarea să fie inversabilă foarte eficient.