Analiza diferențială a SPN

Referință: Tutorial de HM Heys

Dacă găsim un traseu diferențial care se menține cu o probabilitate deloc neglijabilă pentru n-1 runde pentru o structură SPN de n runde, atunci putem recupera o parte din biții subcheii ultimei runde.

Ce se întâmplă atunci când gestionăm doar un traseu diferențial care se menține cu o probabilitate deloc neglijabilă doar pentru câteva dintre rundele R unde R < n-1? Cum procedăm în acest caz pentru a face un atac de recuperare cheie?

Voi aprecia cu adevărat câteva sfaturi pentru a mă gândi la asta.

auto-studiu

Nu aș fi de acord cu răspunsul lui @kodlu. În criptoanaliza diferențială clasică, nu plătim „probabilitate” pentru ultimele runde, ci mai degrabă plătim pentru enumerarea biților cheie implicați. Cu alte cuvinte, decriptarea nu este statistică.

Și asta face utilizarea mai mică $R$ dificil: presupunerile cheie. Cifrele au o difuzie bună și cu fiecare rundă suplimentară pentru a decripta parțial în cele din urmă, numărul de biți de cheie care trebuie ghicit pentru a verifica diferența de ieșire (acum, statistic, pentru fiecare estimare a cheii) crește foarte repede.

In plus formă contează și diferența de ieșire: dacă are o greutate mare (activează multe S-box în rundele ulterioare), sunt necesare mai multe ghiciri de biți cheie.

Rețineți că $R$ iar numărul de biți cheie de ghicit sunt într-un compromis: mai mic $R$ crește probabilitatea diferențială, dar crește și numărul de biți cheie de ghicit. De obicei, câștigul în probabilitate diferențială mergând de la $R=n-1$ la $R=n-2$ nu depășește creșterea complexității ipotezei cheii atunci când se decriptează parțial 2 runde în loc de 1.

Motivul $R=n-1$ (sau $R=1,$ aplicat mapării de decriptare) este utilizat este următorul. Toate aproximările diferențiale individuale, precum și traseul diferențial care este ales peste $R$ randamentul rundelor statistic relatii.

Cu toate acestea, acum se poate folosi ieșirea textului cifrat, rula Sbox-urile în ultima rundă în sens invers și condiționat de fiecare presupunere pentru tastele rotunde XOR introduse în intrările de $n^{th}$ Sbox-urile rotunde au presupuneri non-aleatoare și exacte pentru ieșirile Sbox-urilor vizate din rundă $n-1.$ Aceasta înseamnă că se poate desfășura un experiment statistic de încredere și probabilitatea diferențială empirică a diferenței de intrare și ieșire aleasă poate fi calculată în mod fiabil.

În această etapă, având în vedere suficiente perechi P/C, estimarea cheie care are ca rezultat cea mai mare probabilitate empirică este declarată estimarea cheie cea mai probabilă.

Vezi răspunsul meu la următoarea întrebare pentru mai multe detalii concrete.

Tutorial de criptoanaliza diferențială al lui Howard M. Heys

Editați | ×: Mulțumesc lui @fractalice pentru că a prins ultima parte neglijentă a răspunsului meu. Într-adevăr, complexitatea computațională de a parcurge presupunerile cheie ale Sbox-urilor „active” în ultima rundă este semnificativă. Deci probabilitatea diferențială a $\epsilon$ al $n-1$ caracteristica diferențială înseamnă că trebuie să utilizați aproximativ $c/\epsilon$ Perechile P/C pentru ca caracteristica să fie empiric cea dominantă, iar dacă există $k$ Sbox-urile active în ultima rundă va trebui să le încercați 2$^{4k}$ (deoarece Sbox-urile au o lățime de 4 biți) chei ghicite în timp ce încercați să decideți care chei ghicite sunt cele mai probabile.