Luați în considerare o variantă a algoritmului DES, numită DES-WEAK. În DES-WEAK,
nu există nicio permutare P într-o rundă și toate S-box-urile sunt înlocuite. Noile cutii S sunt toate
identice și definite după cum urmează. Fie b0, . . ., b5 reprezintă cei șase biți de intrare la o cutie S și a0,
a1, a2 și a3 cei patru biți de ieșire. Apoi, a0 = b3 â b0b1b5, a1 = b0 â b1b3b5, a2 = b1 â b2b3b5,
și a3 = b2 â b4 â b1b3b5.
⢠Proiectați un algoritm pentru a sparge 16 runde DES-WEAK cât mai eficient posibil.
Am abordat acest design așa cum am menționat mai jos.
Folosim criptoanaliza diferențială pentru a recupera cheia. Considera
diferențial 000100 intră în S-box S2. Lasă unul dintre cei doi
intrări cu diferenţialul dat
fie b0b1b2b3b4b5 și ieșirea corespunzătoare să fie a0a1a2a3. Lasă
ieșire pentru a doua intrare (= b0b1b2b2(b3 â 1)b4b5) fie a 0 0 a 0 1 a 0 2
a 0 3 . Atunci, a0 â a 0 0 = 1, a1 â a 0 1 = b1b5, a2 â a 0 2 = b2b5
iar a3 â a 0 3 = b1b5. Prin urmare, diferența de ieșire este de 1000 pe
diferenţial de intrare dat cu
probabilitatea 1 2 + 1 2 · 1 4 = 5 8 (fie b5 este zero, fie b5 este unul și
ambele b1, b2 sunt zero).
Problema cu această ieșire diferențială este că, în runda următoare,
după extindere, două S-box-uri vor obține diferenţial diferit de zero. Să presupunem
că, în prima rundă, diferența în S1 este 000000 și
diferența de jumătate din stânga este, de asemenea, toate zerourile. Apoi, în runda următoare,
diferența în S1 ar fi 000001 și în S2 ar fi 010000. Fie
le analizăm pe amândouă. Luați în considerare mai întâi S1. Cu aceeași notație pentru primul
intrare și cele două ieșiri (acum a doua intrare este b0b1b2b3b4(b5 â
1)), obținem a0 â a 0 0 = b0b1, a1 â a 0 1 = b1b3, a2 â a 0 2 = b2b3
şi a3 â a 0 3 = b1b3. De aici rezultatul
diferențial este 0000 cu probabilitate 1 2 · 3 4 + 1 2 · 1 4 = 1 2
(fie b3 este zero și unul dintre b0, b1 este zero sau
b3 este unul și ambele b1, b2 sunt zero). Luați în considerare S2. Acum a doua intrare
este b0(b1 â 1)b2b3b4b5, și astfel obținem a0 â a 0 0 = b0b5,
a1 â a 0 1 = b3b5, a2 â a 0 2 = 1 și a3 â a 0 3 = b3b5. De aici
diferenţialul de ieşire este 0010 cu
probabilitatea 1 2 + 1 2 · 1 4 = 5 8 (fie b5 este zero, fie b5 este unul și
ambele b0, b3 sunt zero). În runda următoare, după aplicarea expansiunii,
diferența dintre aceste două cutii S devine 000000 000100, ceea ce este
exact același diferențial care a intrat în prima rundă în
acestea doua! Folosind această analiză, putem deduce acum o caracteristică
cu mare probabilitate după cum urmează. Fie că Z reprezintă diferența zero pe
32 de biți, P reprezintă diferențial 0000 0010 0000 0000 0000 0000 0000
0000
, și PË reprezintă diferenţial
0000 1000 0000 0000 0000 0000 0000 0000
. Analiza de mai sus arată următoarea secvență de transformare a
diferențiale: [P, Z] p=1 âââ [Z, P] p= 5 8 ââââ [P, PË] p= 5 16 ââââ
[P , Z Ë ] p=1 âââ [Z, PË] p= 5 16 ââââ [P , P Ë ] p= 5 8 ââââ [P, Z].
Probabilitatea globală a caracteristicii de mai sus este 5 4 2 14 .
Repetând acest lucru încă o dată și apoi luând doar primele două runde
din aceasta, obținem o caracteristică de paisprezece runde cu probabilitate 5 9 2
31 â 9 Ã 10â4
. Prin urmare, folosind câteva mii de perechi de text simplu, DES-WEAK poate fi rupt.
Acum avem o nouă provocare și suntem blocați în ea. Designul menționat mai jos este o ușoară modificare a întrebării menționate mai sus la care am lucrat. Designul merge după cum urmează..
Luați în considerare o variantă a algoritmului DES în care sunt toate casetele S
înlocuit. Noile cutii S sunt toate identice și definite după cum urmează.
Fie b1, b2, · · · , b6 reprezintă cei șase biți de intrare într-o cutie S. Este
ieșirea este b1 â(b2 · b3 · b4), (b3 · b4 · b5) â b6, b1 â (b4 · b5 ·
b2), (b5 · b2 · b3) â b6. Aici âââ este operația XOR pe biți și â·â
este înmulțirea pe biți. Proiectați un algoritm pentru a sparge DES cu 16 runde
cu noi S-box cât mai eficient posibil.
În acest design, operația de permutare este încă prezentă și ieșirea S-box este diferită. Așadar, cum putem aborda asta ca cea pe care am făcut-o mai sus, având în vedere că Cutia de permutare este încă acolo.
