CAST-256

CAST-256
Skaber	Carlisle Adams Stafford Tavares
Oprettet	1998
offentliggjort	1998
Nøglestørrelse	128, 160, 192, 224 eller 256 bit
Blokstørrelse	128 bit
Antal runder	48
Type	Feistel netværk

CAST-256 (eller CAST6 ) i kryptografi er en bloksymmetrisk krypteringsalgoritme baseret på Feistel-netværket , offentliggjort i juni 1998 som en kandidat til AES -konkurrencen . Algoritmen er udviklet af specialister fra det canadiske firma Entrust Technologies.

Grundlæggende information

Denne algoritme er baseret på den tidligere CAST-128 algoritme . Begge cifre er baseret på CAST- metoden foreslået af Carlisle Adams . Carlisle Adams) og Stafford Tavares ( eng. Stafford Tavares), hvoraf de to første bogstaver danner navnet på metoden. Hayes Howard og Michael Wiener deltog også i skabelsen af "designet" af chifferen .

CAST-256 er bygget af de samme elementer som CAST-128, inklusive S-bokse, men blokstørrelsen fordobles til 128 bit. Dette påvirker cifferens diffusionsegenskaber og sikkerhed.

RFC 2612 angiver , at CAST-256 er gratis at bruge på verdensplan til kommercielle og ikke-kommercielle formål.

Egenskaber og struktur af algoritmen

Algoritmen krypterer information i 128-bit blokke og bruger flere faste krypteringsnøglestørrelser: 128, 160, 192, 224 eller 256 bit.

Der er 48 runder i CAST-256-algoritmen. Overvej den første halvdel af chifferen. En 128-bit inputblok kan opdeles i fire 32-bit underblokke Ain , Bin , Cin og Din . Underblokken C in tilføjes modulo 2 med D i modificeret afhængigt af rundfunktionen f. Som et resultat får vi en underblok D ud . Efter at have flyttet input-underblokkene til højre med én position, får vi fire output-subblokke: A out , B out , C out og D out . For den anden halvdel af chifferen overvejes forskydningen af underblokke med en position til venstre.

Ikke- lineære funktioner Sj (hvor 1 < j < 4) er substitutioner fra tabellen (S-boks) 8x32 (som følge heraf erstattes en 8-bit inputværdi med en 32-bit). På grund af deres ikke-lineære natur er S-funktioner en integreret del af en chiffers sikkerhed.

Operationerne "b", "c" og "d" er additions- og subtraktionsoperationer, der udføres modulo 32-bit operander . "a"-operationen er overlejringen af input-32-bit-underblokken og 32-bit-undernøglen (kaldet maskeundernøglen). Denne operation, der bruger en af 3 operationer ("b", "c" eller "d"), udfører en rotation afhængigt af 5-bit undernøglen (kaldet shift undernøglen). CAST-256-rundefunktionerne er forskellige mellem runder, fordi kombinationen af operationer, der bruges til "a", "b", "c" og "d" er forskellig. $2^{32}$

Matematisk ser en typisk rund funktion sådan ud:

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 ]

hvor Xi repræsenterer input 32-bit data, Wj er input 8-bit data i Sj funktionen, Kmi og K ri repræsenterer henholdsvis maskeundernøglen og shift undernøglen, Yi er output 32bit data , efter handlingen af den runde funktion, " " operationer "+" og "-", repræsenterer henholdsvis addition og subtraktion, modulo 2. Notationen " " repræsenterer venstre forskydning af V med hensyn til U. W, X i , Yi og Kmi , alle repræsenterer 32-bit underblokke . K ri er 5 bits lang. Dekryptering udføres analogt med kryptering, med den eneste forskel, at undernøglerne bruges i omvendt rækkefølge. $\plus$ $V \ll U$

Differentielle egenskaber

Et vigtigt kriterium for en kryptografisk chiffer er ikke-degeneration: egenskaben, at alle outputbits afhænger af alle inputbits og omvendt. Indvirkningen af inputbits på outputbits kaldes diffusion. Den runde funktions ikke-degeneration er sandsynlig, da hver S-funktion er ikke-degenereret.

Bemærk, at XOR-operationen ikke er ikke-degenereret, da kun én bit fra hver underblok påvirker outputbitten. Når vi betragter de differentielle egenskaber af CAST-256, finder vi, at output-sub-blok D ud i første runde afhænger af alle input-bits af sub-blok D in . Udgangsbittene for underblokkene A ud , B ud og C ud er uafhængige af de tilsvarende inputbits i underblokkene A ind , B ind og C ind .

Som et resultat får vi en tabel (tabel nr. 1), som viser afhængigheden af outputdatachifferet på de angivne runder. Lad fire 32-bit input underblokke Ain , Bin , Cin og Din svare til P 1 , P 2 , P 3 og P 4 .

Tabel nr. 1: Chifferens afhængighed af runden

Rund
Rund	Afhængigheder
en	$P_{3}$ ( ) $P_{4}$
2	$P_2$ ( , ) $P_{3}$ $P_{4}$
3	$P_1$ ( , , ) $P_2$ $P_{3}$ $P_{4}$
fire	$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}$

Efter en runde er de bit, der svarer til P3 - klartekst-underblokken, nu ikke-degenereret til de transformerede klartekst-bits i P4- underblokken . På lignende måde er underblokken P2 efter to runder ikke-degenereret til bits af de transformerede P3 og P4 . Efter runde 4 afhænger underblokken, der svarer til underblok P 4 , af alle bit i alle tekstunderblokke. Efter runde 7 får vi udgangsbittenes fuldstændige afhængighed af inputtet, da alle fire underblokke P 1 , P 2 , P 3 og P 4 afhænger af alle bits i den transformerede klartekst.

Forsvar mod lineær kryptoanalyse

Lineær kryptoanalyse bruger konstruktionen af relationer mellem klartekst, chiffertekst og nøgle, der er gyldige med høj sandsynlighed i den runde genkrypteringsfunktion. Hovedprincippet i lineær kryptoanalyse er søgningen efter tilnærmelser i formen:

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)

hvor i 1 , i 2 ,..., i a er bitpositionerne for klarteksten P, j 1 , j 2 ,..., j b er positionerne af chifferteksten C og k 1 , k 2 ,..., k c er positioner af nøglen K. Sandsynlighed for nøgletal for runders chiffer vurderes som følger:

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

hvor p L er sandsynligheden for, at det lineære udtryk (2) er opfyldt, p B er sandsynligheden for den bedste lineære tilnærmelse af enhver S-funktion, og a er antallet af S-funktioner, der deltager i den lineære tilnærmelse. Modstanden mod lineær kryptoanalyse er strengt afhængig af det generelle lineære sandsynlighedsgrænseudtryk (også kaldet det "lineære spænd"). Lineære angreb er bygget på basis af et lineært udtryk, der involverer bidder af klartekst og chiffertekst (som vist i venstre side af (2)). På højre side af lighed (2) beregnes XOR summen af nøglebittene. Dette kræver cirka følgende antal klartekster:

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

Den bedste lineære tilnærmelse bestemmes af:

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

hvor m er antallet af input tekstbit og NL min er S-funktionens ikke-linearitet. For CAST-256 S-funktioner er m = 8 og NL min = 74. I hver runde er rundefunktionens outputdatabit XOR summen af alle bits af de 4 inputdataunderblokke (hver underblok af størrelse m). Derfor skal den lineære tilnærmelse af outputbittene bestå af lineære tilnærmelser af bits af alle inputunderblokke. I praksis er sandsynligheden for CAST-256 lineære tilnærmelser meget større end 1/2.

Lad a = r for en r-rund chiffer. For r = 48, NL min = 74 er antallet af kendte klartekster, der kræves til lineær kryptoanalyse, ca. Bemærk, at dette er næsten lig med det samlede antal givne klartekster ( ) og er imod det praktiske i et lineært angreb på den chiffer. $2^{122}$ $2^{128}$

Et mere præcist estimat af antallet af klartekster til lineær kryptoanalyse af CAST-chifferet kan opnås ved at overveje foreningen af S-funktioner i den runde funktion. På grund af foreningen af S-funktioner som et resultat af XOR-operationen er ikke-lineariteten af NL min S-boksen (som består af S-funktioner) højere end 74. Overvej en 32x32 S-boks, så er m= 32 og a=r/4 (da vi tilnærmer runde funktionerne hver 4. runde). Således opnår vi antallet af klartekster, der kræves til lineær kryptoanalyse af en 48-rund chiffer, mere end (større end antallet af givne klartekster). Eksperimentelle beviser tyder på, at kombination af en S-funktion ved hjælp af operationer såsom addition eller subtraktion frem for XOR kan øge S-boksens ikke-linearitet endnu mere. $2^{176}$

Beskyttelse mod differentiel kryptoanalyse

Differentiel krypteringsanalyse er baseret på undersøgelsen af transformationen af forskellene mellem krypterede værdier i forskellige runder af kryptering. Blokcifre er modstandsdygtige over for differentiel krypteringsanalyse, hvis der er et enkelt par af forskelle i hver runde for givne forskelle i input klartekster og output chiffertekster. Sådanne forskelle kaldes karakteristika. Som regel er forskellene mest effektive i tilfælde af at overveje XOR for to datablokke. I en god chiffer bør sandsynligheden for alle forskelle være , hvor N er blokstørrelsen. For at opnå en fælles karakteristik ved inputtet og den tilsvarende karakteristik ved XOR-udgangen, kompileres en række karakteristika, der afhænger af input-outputdataene, der gennemgik XOR-operationen i hver runde. $2^{{-N}}$

Analysen her er baseret på antagelserne om, at alle rundnøgler er uafhængige, og at XOR-outputtet (resultatet opnået efter XOR-operationen af inputtet) svarende til et bestemt XOR-input (input) er uafhængigt på tværs af runder. Under sådanne forhold er den r-runde karakteristik repræsenteret som:

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

hvor p i er sandsynligheden for XOR-udgangsforskellene svarende til XOR-inputforskellen i runde i .

Den R-runde CAST-256-cifre vist i tabel #2 er baseret på en 4-runds funktionsopregning.

Tabel #2: Den bedste r-runde-ydelse af en R-runde-chiffer

(0, 0, 0, ) $\Delta$	$[indtast ~XOR~ til ~ runde ~1]$
$0\venstrepil\Delta$	$[runde 1]$
$0\venstrepil0$	$[runde 2]$
$0\venstrepil0$	$[runde 3]$
$0\venstrepil0$	$[runde 4]$
(0, 0, 0, ) $\Delta$	$[indtast ~XOR~ til~ runde~ 5]$
$0\venstrepil\Delta$	$[runde 5]$
$0\venstrepil0$	$[runde 6]$
$0\venstrepil0$	$[runde 7]$
$0\venstrepil0$	$[runde 8]$
$...$	$gentag~ op ~til~ R/2 ~runder$
(0, 0, 0, ) $\Delta$	$[indtast ~XOR~ til ~rund~ R/2+1]$
$0\venstrepil\Delta$	$[rund R/2+1]$
$0\venstrepil0$	$[rund R/2+2]$
$0\venstrepil0$	$[rund R/2+3]$
$0\venstrepil0$	$[rund R/2+4]$
$...$	$gentag ~op~ til~ r~ runder$

XOR-vektor (0, 0, 0, ) af givne forskelle, for 4 input 32-bit underblokke, hvor de første 3 underblokke (A in , B in og C in ) har nul XOR forskelle, og den 4. input subblok (D i i runde) har en XOR-forskel, der ikke er nul, . $\Delta$ $\Delta$

Tabellen viser karakteristikaene for den generelle R-runde-chiffer, XOR-input af R/2 + 1-runden er en vektor, hvor forskellen mellem en af underblokkene ikke er lig med nul, og forskellene i de resterende tre underblokke er lig nul. Vektoren (0, 0, 0, ) præsenteret i tabellen svarer til CAST-256-chifferet med R = 48. $\Delta$

En XOR inputforskel, der ikke er nul, svarer til en nul XOR outputforskel hver 4. runde af funktionen i tabel 2 (som vist i runder 1, 5 osv.). Sandsynligheden for, at givne forskelle i klartekst og givne ciffertekstforskelle svarer til et enkelt par af forskelle, for CAST . Dette er baseret på det faktum, at alle fire S-funktioner i CAST-rundefunktionen er injektiv, og XOR af klartekst- og chiffertekstparrene har forskelle lig med 0. Som et resultat af, at rundfunktionen bruger en kombination af operationer som addition og chiffertekst. subtraktion, vil sandsynligheden for eksistensen af et par være reduceret forskelle mellem klartekster og chiffertekster. Den bedste r-runde ydeevne, som vist i tabel #2 og baseret på antagelserne beskrevet ovenfor, bestemmes af sandsynligheden: $p\leqslant 2^{-14}$

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

Især for en 40-runders funktion (som potentielt kan bruges til at angribe en 48-runders chiffer), skal sandsynligheden være mindre end eller lig med . Derfor skal antallet af valgte klartekster, der kræves til dette angreb, være større end for en 48-rund chiffer (væsentligt større end antallet af klartekster for en 128-bit blokstørrelse). $2^{-140}$ $2^{140}$

Nøgleudvidelse

Nøgleudvidelsesproceduren er mere kompliceret end selve datakryptering. Lad arrayet af nøgler k = (ABCDEFGH) være en 256-bit blok, hvor fragmenterne A, B,...,H hver er 32 bit lange. Lad "k ← w i (k)", hvor w( ) er en forlængelsesfunktion og kan repræsenteres i følgende 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})

Som et resultat af 4 transformationer af 5 mindst signifikante bit, dannes shift-undernøgler: $k^{(i)}_r \venstrepil 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)

hvor 5LSB(x) betyder genereringen af de 5 mindst signifikante bits som et resultat af x-operationen. Maskeringsundernøgler er dannet på samme måde : $k^{(i)}_m \venstrepil k$

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

Implementering af nøgleudvidelsesproceduren

Hver runde af nøgleudvidelsesfunktionen bruger 8 ekstra variabler og . $T^{(i)}mj$ $T^{(i)}rj$

1. Initialisering

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

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

cr=19

Mr = 17

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

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

2. Udvidelsesnøgle:

k = ABCDEFGH = 256 bit af den indledende nøgle K. Lad « » « », « » « », « » « », « » « »

k\leftarrow w_{2_i}(k)

\sim

W2i(k)

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

\sim

W2i+1(k)

k^{i}_r\venstrepil k

\sim

kr

k^{i}_m \venstrepil k

\sim

km

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

Hvis nøglestørrelsen k er mindre end 256 bit, anses de "ekstra" nøglefragmenter for at være nul:

(|K| =128) \Højrepil\,(E = F = G = H = 0)

(|K| =160) \Højrepil\, (F = G = H = 0)

(|K| =192) \Højrepil\, (G = H = 0)

(|K| =224) \Højrepil\, (H = 0)

Fordele og ulemper ved algoritmen

Som et resultat af en omfattende analyse i første fase af AES-konkurrencen, og ikke kun kryptografiske egenskaber blev undersøgt, såsom modstand mod kendte angreb, fravær af svage nøgler, gode statistiske egenskaber, men også praktiske aspekter af implementering: optimering af kodeudførelseshastighed på forskellige arkitekturer (fra pc til smart-cards og hardwareimplementeringer), muligheden for at optimere kodestørrelsen, muligheden for parallelisering, følgende fordele og ulemper ved CAST-256-chifferet blev afsløret.

De vigtigste fordele er:

ingen sårbarheder.
evnen til hurtigt at udføre nøgleudvidelse, det vil sige under indkodningsoperationen, men ikke afkodning.

En række mangler blev fundet i algoritmen, på grund af hvilke den ikke deltog i anden runde af konkurrencen:

algoritmens krypteringshastighed er lav sammenlignet med en række algoritmer – deltagere i konkurrencen, inklusive alle konkurrencens finalister.
høje krav til operationel og flygtig hukommelse.

Litteratur

Sergey Panasenko. Krypteringsalgoritmer . - St. Petersborg: BHV-Petersburg, 2009. - S. 134-141. - 576 sider. — ISBN 978-5-9775-0319-8 . (Russisk)

Links

Symmetriske kryptosystemer
Stream-cifre	A3 A5 A8 Decim F-FCSR Korn HC-256 KCipher-2 MICKEY MUGI GEDD Phelix RC4 Kanin FORSEGLE SNE SOSEMANUK Salsa 20 STRUMOK Trivium VMPC
Feistel netværk	GOST 28147-89 (Magma) blæsefisk Camellia CAST-128 CAST-256 CIFERUNIKORN-A CIFERUNIKORN-E CLEFIA Cobra DEL DES DESX DFC E2 ENRUPT FEAL HPC IDE KASUMI Khafre Khufu LOKI97 MacGuffin MARS MESH MISTY1 NyDES NDS RC5 RC6 FRØ Simon Sinople skipjack SM4 Speck TE XTEA XXTEA Raiden RTEA Triple DES To fisk
SP netværk	Græshoppe 3 vejs ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Bælte CRYPTON Diamant 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer til stede Regnbue SIKRERE HAJ FIRKANT Slange tre fisk
Andet	FRØ NUSH REDOC SC2000 SHACAL CS-Cipher