CAST-256

CAST-256
Tvůrce	Carlisle Adams Stafford Tavares
Vytvořeno	1998
zveřejněno	1998
Velikost klíče	128, 160, 192, 224 nebo 256 bitů
Velikost bloku	128 bit
Počet kol	48
Typ	Síť Feistel

CAST-256 (nebo CAST6 ) v kryptografii je blokově symetrický šifrovací algoritmus založený na síti Feistel , publikovaný v červnu 1998 jako kandidát na soutěž AES . Algoritmus byl vyvinut specialisty z kanadské společnosti Entrust Technologies.

Základní informace

Tento algoritmus je založen na dřívějším algoritmu CAST-128 . Obě šifry jsou založeny na metodologii CAST navržené Carlisle Adamsem . Carlisle Adams) a Stafford Tavares ( angl. Stafford Tavares), jehož první dvě písmena tvoří název metodiky. Na vytvoření „návrhu“ šifry se podíleli také Hayes Howard a Michael Wiener .

CAST-256 je postaven ze stejných prvků jako CAST-128, včetně S-boxů, ale velikost bloku je zdvojnásobena na 128 bitů. To ovlivňuje vlastnosti šíření a bezpečnost šifry.

RFC 2612 uvádí , že CAST-256 je zdarma k použití po celém světě pro komerční i nekomerční účely.

Charakteristika a struktura algoritmu

Algoritmus šifruje informace ve 128bitových blocích a používá několik pevných velikostí šifrovacího klíče: 128, 160, 192, 224 nebo 256 bitů.

Algoritmus CAST-256 má 48 kol. Zvažte první polovinu šifry. 128bitový vstupní blok lze rozdělit na čtyři 32bitové dílčí bloky Ain , Bin , Cin a Din . Podblok C in je přidán modulo 2 s D in upraveným v závislosti na kruhové funkci f. V důsledku toho dostaneme podblok D ven . Po posunutí vstupních podbloků doprava o jednu pozici dostaneme čtyři výstupní podbloky: A out , B out , C out a D out . Pro druhou polovinu šifry je uvažován posun podbloků o jednu pozici doleva.

Nelineární funkce Sj (kde 1 < j < 4) jsou substituce z tabulky (S-box) 8x32 (výsledkem je nahrazení 8bitové vstupní hodnoty 32bitovou). Kvůli jejich nelineární povaze jsou S-funkce nedílnou součástí zabezpečení šifry.

Operace "b", "c" a "d" jsou operace sčítání a odčítání, které se provádějí modulo 32bitovými operandy . Operace "a" je překrytím vstupního 32bitového podbloku a 32bitového podklíče (nazývaného podklíč masky). Tato operace pomocí jedné ze 3 operací („b“, „c“ nebo „d“) provede rotaci v závislosti na 5bitovém podklíči (nazývaném podklíč shift). Funkce kola CAST-256 se mezi jednotlivými koly liší, protože kombinace operací používaných pro „a“, „b“, „c“ a „d“ je odlišná. $2^{32}$

Matematicky vypadá typická kruhová funkce takto:

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 ]

kde X i představuje vstupní 32bitová data, Wj jsou vstupní 8bitová data ve funkci Sj, Kmi a Kri představují podklíč masky a podklíč posunu, Yi je výstupní 32bitová data , po akci zaokrouhlovací funkce, „ “ operace „+“ a „-“, představují sčítání a odčítání, respektive modulo 2. Zápis „ “ představuje levý posun V vzhledem k U. W, X i , Y i a Kmi , všechny představují 32bitové podbloky. K ri je 5 bitů dlouhý. Dešifrování se provádí obdobně jako šifrování, pouze s tím rozdílem, že podklíče se používají v opačném pořadí. $\oplus$ $V \ll U$

Diferenciální vlastnosti

Důležitým kritériem pro kryptografickou šifru je nedegenerace: vlastnost, že všechny výstupní bity závisí na všech vstupních bitech a naopak. Vliv vstupních bitů na výstupní bity se nazývá difúze. Nedegenerace kruhové funkce je pravděpodobná, protože každá S-funkce je nedegenerovaná.

Všimněte si, že operace XOR není nedegenerovaná, protože pouze jeden bit z každého dílčího bloku ovlivňuje výstupní bit. Při zvažování diferenciálních vlastností CAST-256 zjistíme, že výstupní podblok Dout v prvním kole závisí na všech vstupních bitech podbloku Din . Výstupní bity dílčích bloků Aout, Bout a Cout jsou nezávislé na odpovídajících vstupních bitech dílčích bloků Ain , Bin a Cin .

Ve výsledku dostaneme tabulku (tabulka č. 1), která ukazuje závislost výstupní datové šifry na zadaných kolech. Nechť čtyři 32bitové vstupní podbloky Ain , Bin , Cin a Din odpovídají P1 , P2 , P3 a P4 .

Tabulka č. 1: Závislost šifry na kole

Kolo
Kolo	Závislosti
jeden	$P_{3}$ ( ) $P_{4}$
2	$P_2$ ( , ) $P_{3}$ $P_{4}$
3	$P_1$ ( , , ) $P_2$ $P_{3}$ $P_{4}$
čtyři	$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}$

Po jednom kole jsou nyní bity odpovídající podbloku P3 otevřeného textu nedegenerované na transformované bity otevřeného textu podbloku P4 . Podobně po dvou kolech je dílčí blok P2 nedegenerovaný na bity transformovaného P3 a P4 . Po kole 4 závisí dílčí blok odpovídající dílčímu bloku P4 na všech bitech všech dílčích textových bloků. Po 7. kole dostaneme úplnou závislost výstupních bitů na vstupu, protože všechny čtyři dílčí bloky P 1 , P 2 , P 3 a P 4 závisí na všech bitech transformovaného otevřeného textu.

Obrana proti lineární kryptoanalýze

Lineární kryptoanalýza využívá konstrukci vztahů mezi holým textem, šifrovým textem a klíčem, které jsou s vysokou pravděpodobností platné ve funkci kulatého opětovného šifrování. Hlavním principem lineární kryptoanalýzy je hledání aproximací ve tvaru:

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)

kde i 1 , i 2 ,…, i a jsou bitové pozice otevřeného textu P, j 1 , j 2 ,…, jb jsou pozice šifrového textu C a k 1 , k 2 ,…, kc jsou pozice klíče K. Pravděpodobnost poměrů pro kruhovou šifru se vyhodnocuje takto:

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

kde p L je pravděpodobnost, že je splněn lineární výraz (2), p B je pravděpodobnost nejlepší lineární aproximace libovolné S-funkce a a je počet S-funkcí účastnících se lineární aproximace. Odolnost vůči lineární kryptoanalýze je přísně závislá na obecném lineárním ohraničujícím výrazu pravděpodobnosti (také nazývaném „lineární rozpětí“). Lineární útoky jsou postaveny na základě lineárního výrazu zahrnujícího bity prostého textu a šifrovaného textu (jak je znázorněno na levé straně (2)). Na pravé straně rovnosti (2) se vypočítá součet XOR klíčových bitů. To vyžaduje přibližně následující počet otevřených textů:

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

Nejlepší lineární aproximace je určena:

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

kde m je počet bitů vstupního textu a NL min je nelinearita S-funkce. Pro CAST-256 S-funkce je m = 8 a NL min = 74. V každém kole je výstupní datový bit kruhové funkce XOR součet všech bitů 4 vstupních datových podbloků (každý podblok velikost m). Proto musí lineární aproximace výstupních bitů sestávat z lineárních aproximací bitů všech vstupních dílčích bloků. V praxi je pravděpodobnost lineárních aproximací CAST-256 mnohem větší než 1/2.

Nechť a = r pro r-kruhovou šifru. Pro r = 48, NL min = 74 je počet známých otevřených textů požadovaných pro lineární kryptoanalýzu přibližně . Všimněte si, že se to téměř rovná celkovému počtu zadaných otevřených textů ( ) a je to proti praktičnosti lineárního útoku na tuto šifru. $2^{122}$ $2^{128}$

Přesnější odhad počtu otevřených textů pro lineární kryptoanalýzu šifry CAST lze získat zvážením spojení S-funkcí v kruhové funkci. V důsledku sjednocení S-funkcí v důsledku operace XOR je nelinearita NL min S-boxu (který se skládá z S-funkcí) vyšší než 74. Uvažujme 32x32 S-box, pak m= 32 a a=r/4 (protože aproximujeme kruhové funkce každé 4. kolo). Získáme tak počet otevřených textů potřebných pro lineární kryptoanalýzu 48kolové šifry, více než (větší než počet daných otevřených textů). Experimentální důkazy naznačují, že kombinování S-funkce pomocí operací, jako je sčítání nebo odčítání spíše než XOR, může ještě dále zvýšit nelinearitu S-boxu. $2^{176}$

Ochrana proti diferenciální kryptoanalýze

Diferenciální kryptoanalýza je založena na studiu transformace rozdílů mezi šifrovanými hodnotami v různých kolech šifrování. Blokové šifry jsou odolné vůči diferenciální kryptoanalýze, pokud existuje jediný pár rozdílů v každém kole pro dané rozdíly ve vstupním otevřeném textu a výstupním šifrovaném textu. Takové rozdíly se nazývají charakteristiky. Rozdíly jsou zpravidla nejúčinnější v případě uvažování XOR dvou datových bloků. V dobré šifře by pravděpodobnost všech rozdílů měla být , kde N je velikost bloku. Pro získání společné charakteristiky na vstupu a odpovídající charakteristiky na výstupu XOR se sestaví řada charakteristik, které závisí na vstupních a výstupních datech, která prošla operací XOR v každém kole. $2^{{-N}}$

Analýza je zde založena na předpokladech, že všechna tlačítka jsou nezávislá a že výstup XOR (výsledek získaný po operaci vstupu XOR) odpovídající konkrétnímu vstupu (vstupu) XOR je nezávislý napříč koly. Za takových podmínek je r-kruhová charakteristika reprezentována jako:

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

kde p i je pravděpodobnost rozdílů na výstupu XOR odpovídajících rozdílu vstupu XOR v kole i .

Šifra R-round CAST-256 uvedená v tabulce č. 2 je založena na 4kolovém výčtu prvků.

Tabulka č. 2: Nejlepší výkon R-round šifry R-round

(0, 0, 0, ) $\Delta$	$[zadejte ~XOR~ do~ kola ~1]$
$0\leftarrow\Delta$	$[kolo 1]$
$0\leftarrow0$	$[kolo 2]$
$0\leftarrow0$	$[kolo 3]$
$0\leftarrow0$	$[kolo 4]$
(0, 0, 0, ) $\Delta$	$[zadejte ~XOR~ to~ kolo~ 5]$
$0\leftarrow\Delta$	$[kolo 5]$
$0\leftarrow0$	$[kolo 6]$
$0\leftarrow0$	$[kolo 7]$
$0\leftarrow0$	$[kolo 8]$
$...$	$opakujte~ až ~ do~ R/2 ~kol$
(0, 0, 0, ) $\Delta$	$[zadejte ~XOR~ do ~round~ R/2+1]$
$0\leftarrow\Delta$	$[kolo R/2+1]$
$0\leftarrow0$	$[kolo R/2+2]$
$0\leftarrow0$	$[kolo R/2+3]$
$0\leftarrow0$	$[kolo R/2+4]$
$...$	$opakujte ~až~ až~ r~ kol$

Vektor XOR (0, 0, 0, ) daných rozdílů pro 4 vstupní 32bitové podbloky, kde první 3 podbloky (A in , B in a C in ) mají nulové rozdíly XOR a 4. vstupní podblok (D in ) v kole) má nějaký nenulový rozdíl XOR, . $\Delta$ $\Delta$

Tabulka ukazuje charakteristiky obecné šifry R-round, vstup XOR kola R/2 + 1 je vektor, ve kterém rozdíl jednoho z podbloků není roven nule, a rozdíly zbývajících tři dílčí bloky se rovnají nule. Vektor (0, 0, 0, ) uvedený v tabulce odpovídá šifře CAST-256 s R = 48. $\Delta$

Nenulový vstupní rozdíl XOR odpovídá nulovému výstupnímu rozdílu XOR každé 4. kolo funkce v tabulce 2 (jak je uvedeno v kolech 1, 5 atd.). Pravděpodobnost, že dané rozdíly v otevřeném textu a dané rozdíly v šifrovém textu odpovídají jedinému páru rozdílů pro CAST . To je založeno na skutečnosti, že všechny čtyři S-funkce ve funkci CAST round jsou injektivní a XOR párů holého textu a šifrového textu mají rozdíly rovné 0. Výsledkem zaokrouhlení funkce pomocí kombinace operací, jako je sčítání a odečtením se pravděpodobnost existence páru sníží rozdíly mezi otevřenými a šifrovými texty. Nejlepší výkon v r-kole, jak je uvedeno v tabulce č. 2 a na základě předpokladů popsaných výše, je určen pravděpodobností: $p\leqslant 2^{-14}$

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

Konkrétně u 40kolového prvku (který by mohl být potenciálně použit k útoku na 48kolovou šifru) musí být pravděpodobnost menší nebo rovna . Počet vybraných otevřených textů požadovaných pro tento útok proto musí být větší než u 48kolové šifry (podstatně větší než počet otevřených textů pro velikost bloku 128 bitů). $2^{-140}$ $2^{140}$

Rozšíření klíče

Postup rozšíření klíče je složitější než samotné šifrování dat. Nechť pole klíčů k = (ABCDEFGH) je 256bitový blok, kde fragmenty A, B,…,H mají každý 32 bitů. Nechť "k ← w i (k)", kde w( ) je rozšiřující funkce a může být reprezentována v následujícím tvaru: $\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})

V důsledku 4 transformací po 5 nejméně významných bitech se vytvoří podklíče posunu: $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)

kde 5LSB(x) znamená generování 5 nejméně významných bitů jako výsledek operace x. Maskovací podklíče se tvoří podobně : $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

Implementace procedury rozšíření klíče

Každé kolo funkce rozšíření klíče používá 8 dalších proměnných a . $T^{(i)}mj$ $T^{(i)}rj$

1. Inicializace

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

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

cr=19

Pan = 17

Nechť = 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 = Cr Cr = (Cr + Mm)mod32 }

2. Klíč rozšíření:

k = ABCDEFGH = 256 bitů počátečního klíče K. Nechť « » « », « » « », « » « », « » « »

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

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

Pokud je velikost klíče k menší než 256 bitů, pak se „extra“ fragmenty klíče považují za nulové:

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

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

(|K| =192) \Rightarrow\, (G = H = 0)

(|K| =224) \Rightarrow\, (H = 0)

Výhody a nevýhody algoritmu

Jako výsledek komplexní analýzy v první fázi soutěže AES byly studovány nejen kryptografické vlastnosti, jako je odolnost proti známým útokům, absence slabých klíčů, dobré statistické vlastnosti, ale také praktické aspekty implementace: optimalizace rychlost provádění kódu na různých architekturách (od PC po smart -cards a hardwarové implementace), možnost optimalizace velikosti kódu, možnost paralelizace, byly odhaleny následující výhody a nevýhody šifry CAST-256.

Hlavní výhody jsou:

žádné zranitelnosti.
schopnost rychle provést rozšíření klíče, to znamená během operace kódování, ale ne dekódování.

V algoritmu byla zjištěna řada nedostatků, kvůli kterým nepostoupil do druhého kola soutěže:

rychlost šifrování algoritmu je nízká ve srovnání s řadou algoritmů - účastníků soutěže, včetně všech finalistů soutěže.
vysoké požadavky na operační a volatilní paměť.

Literatura

Sergej Panasenko. Šifrovací algoritmy . - Petrohrad: BHV-Petersburg, 2009. - S. 134-141. — 576 str. — ISBN 978-5-9775-0319-8 . (Ruština)

Odkazy

Symetrické kryptosystémy
Streamové šifry	A3 A5 A8 Decim F-FCSR Obilí HC-256 KCipher-2 MICKEY MUGI ŠTIKA Phelix RC4 Králičí TĚSNĚNÍ SNÍH SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Síť Feistel	GOST 28147-89 (Magma) nafukovací ryba Kamélie CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra OBCHOD DES DESX DFC E2 EnRUPT FEAL HPC IDEA KASUMI Khafre Chufu LOKI97 MacGuffin MARS PLETIVO MISTY1 NewDES NDS RC5 RC6 SEMÍNKO Simone Sinople skipjack SM4 Smítko ČAJ XTEA XXTEA Raiden RTEA Trojitý DES Dvě ryby
Síť SP	Saranče 3 způsob ABC ÁRIE AES (Rijndael) Akelarre Anubis BaseKing Bass Omatic Pás KRYPTON Diamant 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer současnost, dárek Duha BEZPEČNĚJŠÍ ŽRALOK NÁMĚSTÍ Had tři ryby
jiný	ŽÁBA NUSH REDOC SC2000 SHACAL CS-Cipher