CAST-256

CAST-256
Creator	Carlisle Adams Stafford Tavares
Creată	1998
publicat	1998
Dimensiunea cheii	128, 160, 192, 224 sau 256 de biți
Dimensiunea blocului	128 de biți
Numărul de runde	48
Tip de	Rețeaua Feistel

CAST-256 (sau CAST6 ) în criptografie este un algoritm de criptare bloc simetric bazat pe rețeaua Feistel , publicat în iunie 1998 ca candidat pentru competiția AES . Algoritmul a fost dezvoltat de specialiști de la compania canadiană Entrust Technologies.

Informații de bază

Acest algoritm se bazează pe algoritmul CAST-128 anterior . Ambele cifruri se bazează pe metodologia CAST propusă de Carlisle Adams . Carlisle Adams) și Stafford Tavares ( ing. Stafford Tavares), ale căror primele două litere formează numele metodologiei. Hayes Howard și Michael Wiener au luat parte și la crearea „designului” cifrului .

CAST-256 este construit din aceleași elemente ca și CAST-128, inclusiv S-box-uri, dar dimensiunea blocului este dublată la 128 de biți. Acest lucru afectează proprietățile de difuzie și securitatea cifrului.

RFC 2612 afirmă că CAST-256 poate fi utilizat gratuit în întreaga lume în scopuri comerciale și necomerciale.

Caracteristicile și structura algoritmului

Algoritmul criptează informațiile în blocuri de 128 de biți și utilizează mai multe dimensiuni fixe de chei de criptare: 128, 160, 192, 224 sau 256 de biți.

Există 48 de runde în algoritmul CAST-256. Luați în considerare prima jumătate a cifrului. Un bloc de intrare de 128 de biți poate fi împărțit în patru subblocuri de 32 de biți A in , B in , C in și D in . Subblocul C in este adăugat modulo 2 cu D in modificat în funcție de funcția rotundă f. Ca rezultat, obținem un subbloc D. După deplasarea subblocurilor de intrare la dreapta cu o poziție, obținem patru subblocuri de ieșire: A out , B out , C out și D out . Pentru a doua jumătate a cifrului, se ia în considerare deplasarea subblocurilor cu o poziție spre stânga.

Funcțiile neliniare S j (unde 1 < j < 4) sunt substituții din tabelul (S-box) 8x32 (ca urmare, o valoare de intrare de 8 biți este înlocuită cu una de 32 de biți). Datorită naturii lor neliniare, funcțiile S sunt parte integrantă a securității unui cifr.

Operațiile „b”, „c” și „d” sunt operații de adunare și scădere care sunt efectuate modulo operanzi pe 32 de biți . Operația „a” este suprapunerea subblocului de intrare pe 32 de biți și a subcheii de 32 de biți (numită subcheie masca). Această operație, folosind una dintre cele 3 operații ("b", "c" sau "d"), efectuează o rotație în funcție de subcheia de 5 biți (numită subcheie de shift). Funcțiile de rundă CAST-256 diferă între runde, deoarece combinația de operații utilizate pentru „a”, „b”, „c” și „d” este diferită. $2^{32}$

Din punct de vedere matematic, o funcție rotundă tipică arată astfel:

W = ((K_{m_i}+X_i) \lll K_{r_i}) ~~~(1)

Y_i = (( S_1 \left [ W_1 \right ] \oplus S_2 \left [ W_2 \right ] )+S_3 \left [ W_3 \right ]-S_4 \left [ W_4 \right ]

unde X i reprezintă datele de intrare pe 32 de biți, W j sunt datele de intrare pe 8 biți în funcția S j , K mi și Kri reprezintă subcheia masca și respectiv subcheia de schimbare, Y i este datele de ieșire pe 32 de biți , după acțiunea funcției rotunjite, operațiile „ ” „+” și „-”, reprezintă adunare și, respectiv, scădere, modulo 2. Notația „ ” reprezintă deplasarea la stânga a lui V față de U. W, X i , Y i și K mi , toate reprezintă subblocuri pe 32 de biți. K ri are 5 biți lungime. Decriptarea se realizează prin analogie cu criptarea, cu singura diferență că subcheile sunt folosite în ordine inversă. $\oplus$ $V \ll U$

Proprietăți diferențiale

Un criteriu important pentru un cifru criptografic este non-degenerarea: proprietatea că toți biții de ieșire depind de toți biții de intrare și invers. Influența biților de intrare asupra biților de ieșire se numește difuzie. Nedegenerarea funcției rotunde este probabilă, deoarece fiecare funcție S este nedegenerată.

Rețineți că operația XOR nu este nedegenerată, deoarece doar un bit din fiecare subbloc afectează bitul de ieșire. Când luăm în considerare proprietățile diferențiale ale CAST-256, constatăm că subblocul de ieșire D out în prima rundă depinde de toți biții de intrare ai subblocului D în . Biții de ieșire ai subblocurilor A out , B out și C out sunt independenți de biții de intrare corespunzători ai subblocurilor A in , B in și C in .

Ca rezultat, obținem un tabel (tabelul nr. 1), care arată dependența cifrului datelor de ieșire de rundele specificate. Fie că patru subblocuri de intrare pe 32 de biți A în , B în , C în și D în corespund cu P 1 , P 2 , P 3 și P 4 .

Tabelul nr. 1: Dependența cifrului de rundă

Rundă
Rundă	Dependente
unu	$P_{3}$ ( ) $P_{4}$
2	$P_2$ ( , ) $P_{3}$ $P_{4}$
3	$P_1$ ( , , ) $P_2$ $P_{3}$ $P_{4}$
patru	$P_{4}$ ( , , , ) $P_1$ $P_2$ $P_{3}$ $P_{4}$
5	$P_{3}$ ( , , , ) $P_1$ $P_2$ $P_{3}$ $P_{4}$
6	$P_2$ ( , , , ) $P_1$ $P_2$ $P_{3}$ $P_{4}$
7	$P_1$ ( , , , ) $P_1$ $P_2$ $P_{3}$ $P_{4}$

După o rundă, biţii corespunzători subblocului de text simplu P3 sunt acum nedegeneraţi în biţii de text clar transformaţi ai subblocului P4 . În mod similar, după două runde , subblocul P2 este nedegenerat în biţii P3 şi P4 transformaţi . După runda 4, sub-blocul corespunzător sub-blocului P4 depinde de toți biții din toate sub-blocurile de text. După runda 7, obținem dependența completă a biților de ieșire de intrare, deoarece toate cele patru subblocuri P 1 , P 2 , P 3 și P 4 depind de toți biții textului simplu transformat.

Apărare împotriva criptoanalizei liniare

Criptanaliza liniară folosește construirea de relații între text simplu, text cifrat și cheie care sunt valabile cu mare probabilitate în funcția de re-criptare rotundă. Principiul principal al criptoanalizei liniare este căutarea aproximărilor sub forma:

P_{i_1} \oplus P_{i_2} \oplus... \oplus P_{i_a} \oplus C_{j_1} \oplus C_{j_2} \oplus... \oplus C_{i_b} = K_{k_1} \ oplus K_{k_2} \oplus... \oplus K_{k_c} ~~~(2)

unde i 1 , i 2 ,…, i a sunt pozițiile de biți ale textului simplu P, j 1 , j 2 ,…, j b sunt pozițiile textului cifrat C și k 1 , k 2 ,…, k c sunt pozițiile cheii K. Probabilitatea rapoartelor pentru cifrul rundelor este evaluată după cum urmează:

|p_L - \frac{1}{2}| \leqslant 2^{a-1}\cdot|p_B - \frac{1}{2}|~~~(3)

unde p L este probabilitatea ca expresia liniară (2) să fie satisfăcută, p B este probabilitatea celei mai bune aproximări liniare a oricărei S-funcții și a este numărul de S-funcții care participă la aproximarea liniară. Rezistența la criptoanaliza liniară este strict dependentă de expresia generală a limitelor de probabilitate liniară (numită și „interval liniar”). Atacurile liniare sunt construite pe baza unei expresii liniare care implică biți de text simplu și text cifrat (așa cum se arată în partea stângă a (2)). În partea dreaptă a egalității (2), este calculată suma XOR a biților cheie. Acest lucru necesită aproximativ următorul număr de texte clare:

N_L = |p_L - \frac{1}{2}|^{-2}~~~~~~~~~~~~~~~~(4)

Cea mai bună aproximare liniară este determinată de:

|p_B - \frac{1}{2}| = \frac{2^{m-1}-NL_min}{2^{m}} ~~~(5)

unde m este numărul de biți de text de intrare și NL min este neliniaritatea funcției S. Pentru funcțiile S CAST-256, m = 8 și NL min = 74. În fiecare rundă, bitul de date de ieșire al funcției rotunde este XOR suma tuturor biților din cele 4 subblocuri de date de intrare (fiecare subbloc de dimensiunea m). Prin urmare, aproximarea liniară a biților de ieșire trebuie să constea din aproximări liniare ale biților tuturor subblocurilor de intrare. În practică, probabilitatea aproximărilor liniare CAST-256 este mult mai mare decât 1/2.

Fie a = r pentru un cifru rotund r. Pentru r = 48, NL min = 74, numărul de texte clare cunoscute necesare pentru criptoanaliza liniară este de aproximativ . Rețineți că acesta este aproape egal cu numărul total de texte clare date ( ) și este împotriva caracterului practic al unui atac liniar asupra acelui cifr. $2^{122}$ $2^{128}$

O estimare mai precisă a numărului de texte clare pentru criptoanaliza liniară a cifrului CAST poate fi obținută luând în considerare unirea funcțiilor S în funcția rotundă. Datorită unirii funcțiilor S ca rezultat al operației XOR, neliniaritatea casetei S NL min (care constă din funcții S) este mai mare decât 74. Luați în considerare o casetă S de 32x32, atunci m= 32 și a=r/4 (deoarece aproximăm funcțiile rundei la fiecare a 4-a rundă). Astfel, obținem numărul de texte clare necesare pentru criptoanaliza liniară a unui cifr de 48 de runde, mai mult decât (mai mare decât numărul de texte clare date). Dovezile experimentale sugerează că combinarea unei funcții S folosind operații precum adunarea sau scăderea mai degrabă decât XOR poate crește neliniaritatea cutiei S și mai mult. $2^{176}$

Protecție împotriva criptoanalizei diferențiale

Criptanaliza diferențială se bazează pe studiul transformării diferențelor dintre valorile criptate în diferite runde de criptare. Cifrurile bloc sunt rezistente la criptoanaliza diferențială dacă există o singură pereche de diferențe în fiecare rundă pentru diferențele date în textele simple de intrare și textele cifrate de ieșire. Astfel de diferențe se numesc caracteristici. De regulă, diferențele sunt cele mai eficiente în cazul luării în considerare a XOR a două blocuri de date. Într-un cifr bun, probabilitatea tuturor diferențelor ar trebui să fie , unde N este dimensiunea blocului. Pentru a obține o caracteristică comună la intrare și caracteristica corespunzătoare la ieșire XOR, se compila o serie de caracteristici care depind de datele de intrare, de ieșire care au fost supuse operației XOR în fiecare rundă. $2^{{-N}}$

Analiza aici se bazează pe ipotezele că toate cheile rotunde sunt independente și că ieșirea XOR (rezultatul obținut după operarea XOR a intrării) corespunzătoare unei anumite intrări XOR (intrare) este independentă între runde. În astfel de condiții, caracteristica r-round este reprezentată ca:

p_{w_r} = \prod_{i=1}^{r} p_i ~~~(6)

unde p i este probabilitatea diferențelor de ieșire XOR corespunzătoare diferenței de intrare XOR în runda i .

Cifrul CAST-256 R-round prezentat în Tabelul #2 se bazează pe o enumerare a caracteristicilor cu 4 runde.

Tabelul #2: Cea mai bună performanță r-round a unui cifr R-round

(0, 0, 0, ) $\Delta$	$[introduceți ~XOR~ pentru a ~ rotunji ~1]$
$0\săgeată la stânga\Delta$	$[runda 1]$
$0\leftarrow0$	$[runda 2]$
$0\leftarrow0$	$[runda 3]$
$0\leftarrow0$	$[runda 4]$
(0, 0, 0, ) $\Delta$	$[introduceți ~XOR~ la~ rotunjiți~ 5]$
$0\săgeată la stânga\Delta$	$[runda 5]$
$0\leftarrow0$	$[runda 6]$
$0\leftarrow0$	$[runda 7]$
$0\leftarrow0$	$[runda 8]$
$...$	$repetă~ până la ~ R/2 ~ runde$
(0, 0, 0, ) $\Delta$	$[introduceți ~XOR~ la ~rotunzi~ R/2+1]$
$0\săgeată la stânga\Delta$	$[rundă R/2+1]$
$0\leftarrow0$	$[rundă R/2+2]$
$0\leftarrow0$	$[rundă R/2+3]$
$0\leftarrow0$	$[rundă R/2+4]$
$...$	$repeta ~up~ la~ r~ runde$

Vector XOR (0, 0, 0, ) al diferențelor date, pentru 4 subblocuri de intrare pe 32 de biți, unde primele 3 subblocuri (A în , B în și C în ) au diferențe XOR zero și al 4-lea subbloc de intrare (D în în rundă) are o diferență XOR diferită de zero, . $\Delta$ $\Delta$

Tabelul arată caracteristicile cifrului general R-round, intrarea XOR a rundei R/2 + 1 este un vector în care diferența unuia dintre sub-blocuri nu este egală cu zero, iar diferențele celorlalte trei subblocuri sunt egale cu zero. Vectorul (0, 0, 0, ) prezentat în tabel corespunde cifrului CAST-256 cu R = 48. $\Delta$

O diferență de intrare XOR diferită de zero corespunde unei diferențe de ieșire XOR zero la fiecare a patra rundă a caracteristicii din Tabelul 2 (așa cum se arată în rundele 1, 5 etc.). Probabilitatea ca diferențele de text simplu date și diferențele de text cifrat date să corespundă unei singure perechi de diferențe, pentru CAST . Acest lucru se bazează pe faptul că toate cele patru funcții S din funcția de rotunjire CAST sunt injective și XOR-ul perechilor de text simplu și de text cifrat au diferențe egale cu 0. Ca rezultat al funcției de rotunjire folosind o combinație de operații precum adăugarea și scădere, probabilitatea existenței unei perechi va fi redusă diferențele dintre texte clare și texte cifrate. Cea mai bună performanță r-round, așa cum se arată în tabelul #2 și pe baza ipotezelor descrise mai sus, este determinată de probabilitatea: $p\leqslant 2^{-14}$

p_{w_r}\leqslant(2^{-14})^{r/4}~~~~(4)

În special, pentru o caracteristică de 40 de runde (care ar putea fi utilizată pentru a ataca un cifr de 48 de runde), probabilitatea trebuie să fie mai mică sau egală cu . Prin urmare, numărul de texte clare alese necesare pentru acest atac trebuie să fie mai mare decât pentru un cifr de 48 de runde (substanțial mai mare decât numărul de texte clare pentru o dimensiune de bloc de 128 de biți). $2^{-140}$ $2^{140}$

Extensie cheie

Procedura de extindere a cheii este mai complicată decât criptarea datelor în sine. Fie matricea de chei k = (ABCDEFGH) să fie un bloc de 256 de biți, unde fragmentele A, B,…,H au fiecare 32 de biți. Fie „k ← w i (k)”, unde w( ) este o funcție de extensie și poate fi reprezentată în următoarea formă: $\cdot$

G = G \oplus f_1(H, t_{r_0}, t_{m_0})

F = F \oplus f_2(G, t_{r_1}, t_{m_1})

E = E \oplus f_3(F, t_{r_2}, t_{m_2})

D = D \oplus f_1(E, t_{r_3}, t_{m_3})

C = C \oplus f_2(D, t_{r_4}, t_{m_4})

B = B \oplus f_3(C, t_{r_5}, t_{m_5})

A = A \oplus f_1(B, t_{r_6}, t_{m_6})

H = H \oplus f_2(A, t_{r_7}, t_{m_7})

Ca rezultat a 4 transformări a 5 biți cel mai puțin semnificativi, se formează subchei de shift: $k^{(i)}_r \leftarrow k$

k^{(i)}_{r_0} = 5LSB(A), k^{(i)}_{r_1} = 5LSB(C), k^{(i)}_{r_2} = 5LSB(E) , k^{(i)}_{r_3} = 5LSB(G)

unde 5LSB(x) înseamnă generarea celor 5 biți cei mai puțin semnificativi ca rezultat al operației x. Subcheile de mascare sunt formate în mod similar : $k^{(i)}_m \leftarrow k$

k^{(i)}_{m_0} = H, k^{(i)}_{m_1} = F, k^{(i)}_{m_2} = D, k^{(i)}_ {m_3} = B

Implementarea procedurii de extindere a cheilor

Fiecare rundă a funcției de extindere a tastelor folosește 8 variabile suplimentare și . $T^{(i)}mj$ $T^{(i)}rj$

1. Inițializare

cm = 2^{30}\sqrt{2} = 5A827999_16

Mm = 2^{30}\sqrt{3} = 6ED9EBA1_16

cr=19

Domnul = 17

Fie = Tmij, = Trij. $T^{(i)}mj$ $T^{(i)}rj$

pentru(i=0; i<24; i++) pentru(j=0; j<8; j++){ Tmij = Cm Cm = (Cm + Mm)mod2^32 Trij = Cr Cr = (Cr + Mm)mod32 }

2. Tasta de extensie:

k = ABCDEFGH = 256 de biți ai cheii inițiale K. Fie « » « », « » « », « » « », « » « »

k\leftarrow w_{2_i}(k)

\sim

W2i(k)

k \leftarrow w_{2i+1}(k)

\sim

W2i+1(k)

k^{i}_r\leftarrow k

\sim

kr

k^{i}_m \leftarrow k

\sim

km

pentru(j=0; j<12; j++){ W2i(k) W2i+1(k) kr km }

Dacă dimensiunea cheii k este mai mică de 256 de biți, atunci fragmentele de cheie „extra” sunt considerate a fi zero:

(|K| =128) \Săgeată la dreapta\,(E = F = G = H = 0)

(|K| =160) \Săgeată dreapta\, (F = G = H = 0)

(|K| =192) \Săgeată la dreapta\, (G = H = 0)

(|K| =224) \săgeată la dreapta\, (H = 0)

Avantajele și dezavantajele algoritmului

Ca urmare a unei analize cuprinzătoare în prima etapă a competiției AES, și nu numai proprietățile criptografice au fost studiate, precum rezistența la atacuri cunoscute, absența cheilor slabe, proprietăți statistice bune, dar și aspecte practice ale implementării: optimizarea Viteza de execuție a codului pe diferite arhitecturi (de la PC la smart -carduri și implementări hardware), posibilitatea de optimizare a dimensiunii codului, posibilitatea de paralelizare, au fost dezvăluite următoarele avantaje și dezavantaje ale cifrului CAST-256.

Principalele avantaje sunt:

fara vulnerabilitati.
capacitatea de a efectua rapid extinderea cheii, adică în timpul operațiunii de codificare, dar nu și decodare.

Au fost găsite o serie de deficiențe în algoritm, din cauza cărora nu a intrat în a doua rundă a competiției:

viteza de criptare a algoritmului este scăzută în comparație cu un număr de algoritmi - participanți la competiție, inclusiv toți finaliștii competiției.
cerințe ridicate pentru memoria operațională și volatilă.

Literatură

Serghei Panasenko. Algoritmi de criptare . - Sankt Petersburg: BHV-Petersburg, 2009. - P. 134-141. — 576 p. — ISBN 978-5-9775-0319-8 . (Rusă)

Link -uri

Criptosisteme simetrice
Cifruri în flux	A3 A5 A8 Decim F-FCSR Cereale HC-256 KCipher-2 MICKEY MUGI ŞTIUCĂ Phelix RC4 Iepure SIGILIU ZĂPADĂ SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Rețeaua Feistel	GOST 28147-89 (Magma) blowfish Camelia CAST-128 CAST-256 CIFERUNICORN-A CIFERUNICORN-E CLEFIA Cobra AFACERE DES DESX DFC E2 ENRUPT FEAL HPC IDEE KASUMI Khafre Khufu LOKI97 MacGuffin MARTE PLASĂ CEȚA1 NewDES NDS RC5 RC6 SEMINTA Simon Sinople lista SM4 Speck CEAI XTEA XXTEA Raiden RTEA Triplu DES Doi pești
Rețeaua SP	Lăcustă 3 căi ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Centura CRYPTON Diamant2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer prezent Curcubeu MAI SIGUR RECHIN PĂTRAT Şarpe trei pești
Alte	BROASCĂ NUSH REDOC SC2000 SHACAL CS-Cipher