CAST-256

CAST-256
Luoja	Carlisle Adams Stafford Tavares
Luotu	1998
julkaistu	1998
Avaimen koko	128, 160, 192, 224 tai 256 bittiä
Lohkon koko	128 bittinen
Kierrosten lukumäärä	48
Tyyppi	Feistelin verkko

CAST-256 (tai CAST6 ) kryptografiassa on Feistel-verkkoon perustuva lohkosymmetrinen salausalgoritmi , joka julkaistiin kesäkuussa 1998 AES -kilpailun ehdokkaana . Algoritmin ovat kehittäneet kanadalaisen Entrust Technologies -yrityksen asiantuntijat.

Perustiedot

Tämä algoritmi perustuu aikaisempaan CAST-128- algoritmiin . Molemmat salaukset perustuvat Carlisle Adamsin ehdottamaan CAST -metodologiaan . Carlisle Adams) ja Stafford Tavares ( eng. Stafford Tavares), jonka kaksi ensimmäistä kirjainta muodostavat menetelmän nimen. Hayes Howard ja Michael Wiener osallistuivat myös salauksen "suunnittelun" luomiseen .

CAST-256 on rakennettu samoista elementeistä kuin CAST-128, mukaan lukien S-laatikot, mutta lohkokoko on kaksinkertaistettu 128 bittiin. Tämä vaikuttaa salauksen diffuusio-ominaisuuksiin ja turvallisuuteen.

RFC 2612:ssa todetaan , että CAST-256 on vapaasti käytettävissä maailmanlaajuisesti kaupallisiin ja ei-kaupallisiin tarkoituksiin.

Algoritmin ominaisuudet ja rakenne

Algoritmi salaa tiedot 128-bittisiksi lohkoiksi ja käyttää useita kiinteitä salausavainkokoja: 128, 160, 192, 224 tai 256 bittiä.

CAST-256-algoritmissa on 48 kierrosta. Harkitse salauksen ensimmäistä puoliskoa. 128-bittinen tulolohko voidaan jakaa neljään 32-bittiseen alilohkoon A in , B in , C in ja D in . Osalohkoon C in lisätään modulo 2, jossa D in on modifioitu pyöreän funktion f mukaan. Tämän seurauksena saamme alilohkon D out . Kun syöttöalilohkoja on siirretty oikealle yhden pisteen verran, saadaan neljä lähtöalilohkoa: A out , B out , C out ja D out . Salauksen toisella puoliskolla otetaan huomioon alilohkojen siirtyminen yhden sijainnin verran vasemmalle.

Epälineaariset funktiot S j (jossa 1 < j < 4) ovat substituutioita taulukosta (S-laatikko) 8x32 (tämän seurauksena 8-bittinen tuloarvo korvataan 32-bittisellä). Epälineaarisen luonteensa vuoksi S-funktiot ovat olennainen osa salauksen turvallisuutta.

Operaatiot "b", "c" ja "d" ovat yhteen- ja vähennysoperaatioita, jotka suoritetaan modulo 32-bittisinä operandiina . Toiminto "a" on 32-bittisen syötealilohkon ja 32-bittisen aliavaimen (kutsutaan maskin aliavaimeksi) päällekkäisyys. Tämä toiminto, jossa käytetään yhtä kolmesta operaatiosta ("b", "c" tai "d"), suorittaa kierron 5-bittisen aliavaimen mukaan (kutsutaan vaihto-aliavaimeksi). CAST-256:n kierrostoiminnot eroavat kierrosten välillä, koska "a", "b", "c" ja "d" -toimintojen yhdistelmä on erilainen. $2^{32}$

Matemaattisesti tyypillinen pyöreä funktio näyttää tältä:

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

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

jossa Xi edustaa 32-bittistä syötetietoa, Wj on 8-bittistä syötetietoa Sj - funktiossa, K mi ja Kri edustavat maskin aliavainta ja Shift-aliavainta, Y i on 32-bittistä lähtötietoa , pyöreän funktion toiminnon jälkeen " "-toiminnot "+" ja "-", edustavat yhteen- ja vähennyslaskua, vastaavasti, modulo 2. Merkintä " " edustaa V:n siirtymää vasemmalle suhteessa U. W, X i , Y i ja K mi , ne kaikki edustavat 32-bittisiä alilohkoja. K ri on 5 bittiä pitkä. Salauksen purku suoritetaan analogisesti salauksen kanssa sillä ainoalla erolla, että aliavaimia käytetään käänteisessä järjestyksessä. $\oplus$ $V \ll U$

Differentiaaliominaisuudet

Tärkeä kriteeri kryptografiselle salaukselle on rappeutumattomuus: ominaisuus, että kaikki lähtöbitit riippuvat kaikista tulobiteistä ja päinvastoin. Tulobittien vaikutusta lähtöbitteihin kutsutaan diffuusioksi. Pyöreän funktion ei-degeneroituminen on todennäköistä, koska jokainen S-funktio on ei-degeneroitunut.

Huomaa, että XOR-toiminto ei ole ei-degeneroitunut, koska vain yksi bitti kustakin alilohkosta vaikuttaa lähtöbittiin. Kun tarkastellaan CAST-256:n differentiaalisia ominaisuuksia, havaitsemme, että lähtöalilohko D out ensimmäisellä kierroksella riippuu kaikista alilohkon D in tulobiteistä . Alilohkojen A out , B out ja C out lähtöbitit ovat riippumattomia alilohkojen A in , B in ja C in vastaavista tulobiteistä .

Tuloksena saamme taulukon (taulukko nro 1), joka näyttää lähtötietosalauksen riippuvuuden määritetyistä kierroksista. Olkoon neljä 32-bittistä tuloalilohkoa A in , B in , C in ja D in vastaavat P 1 , P 2 , P 3 ja P 4 .

Taulukko 1: Salauksen riippuvuus kierroksesta

Pyöristää
Pyöristää	Riippuvuudet
yksi	$P_{3}$ ( ) $P_{4}$
2	$P_2$ ( , ) $P_{3}$ $P_{4}$
3	$P_1$ ( , , ) $P_2$ $P_{3}$ $P_{4}$
neljä	$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}$

Yhden kierroksen jälkeen P3-plaintext-alilohkoa vastaavat bitit ovat nyt ei-degeneroituneita P4-alilohkon muunnetuiksi selvätekstibiteiksi . Vastaavasti kahden kierroksen jälkeen alilohko P2 on ei-degeneroitunut muunnettujen P3:n ja P4 : n biteiksi . Kierroksen 4 jälkeen alilohkoa P4 vastaava alilohko riippuu kaikkien tekstialilohkojen kaikista biteistä. Kierroksen 7 jälkeen saadaan lähtöbittien täydellinen riippuvuus syötteestä, koska kaikki neljä alilohkoa P 1 , P 2 , P 3 ja P 4 ovat riippuvaisia kaikista muunnetun selkeän tekstin biteistä.

Suojaus lineaarista kryptausanalyysiä vastaan

Lineaarinen kryptausanalyysi käyttää selkeiden tekstin, salatekstin ja avaimen välisten suhteiden rakentamista, jotka ovat suurella todennäköisyydellä kelvollisia pyöreässä uudelleensalaustoiminnossa. Lineaarisen kryptaanalyysin pääperiaate on likiarvojen etsiminen muodossa:

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)

missä i 1 , i 2 ,…, i a ovat selkeän tekstin P bittipaikat, j 1 , j 2 ,…, j b ovat salatekstin C paikat ja k 1 , k 2 ,…, k c ovat avaimen K paikat. Kierroslukujen suhteiden todennäköisyys arvioidaan seuraavasti:

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

missä p L on todennäköisyys, että lineaarinen lauseke (2) täyttyy, p B on minkä tahansa S-funktion parhaan lineaarisen approksimoinnin todennäköisyys ja a on lineaariseen approksimaatioon osallistuvien S-funktioiden lukumäärä. Lineaarisen krypta-analyysin vastustuskyky riippuu tiukasti yleisestä lineaarista todennäköisyyttä rajoittavasta lausekkeesta (kutsutaan myös "lineaariseksi jänneväliksi"). Lineaariset hyökkäykset rakennetaan lineaarisen lausekkeen perusteella, joka sisältää bittejä selkeää tekstiä ja salatekstiä (kuten näkyy (2) vasemmalla puolella). Yhtälön (2) oikealla puolella lasketaan avainbittien XOR-summa. Tämä vaatii noin seuraavan määrän selkeitä tekstejä:

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

Paras lineaarinen approksimaatio määräytyy:

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

missä m on syöttötekstibittien lukumäärä ja NL min on S-funktion epälineaarisuus. CAST-256 S-funktioille m = 8 ja NL min = 74. Jokaisella kierroksella kierrosfunktion lähtödatabitti on XOR neljän tulodata-alilohkon kaikkien bittien summa (kukin alilohko koko m). Tästä syystä lähtöbittien lineaarisen approksimoinnin tulee koostua kaikkien tuloalilohkojen bittien lineaarisista approksimaatioista. Käytännössä CAST-256:n lineaaristen approksimaatioiden todennäköisyys on paljon suurempi kuin 1/2.

Olkoon a = r r-kierrokselle. Kun r = 48, NL min = 74, lineaariseen krypta-analyysiin tarvittavien tunnettujen selkotekstien määrä on noin . Huomaa, että tämä on melkein yhtä suuri kuin annettujen selkeiden tekstien kokonaismäärä ( ) ja on vastoin tätä salauskoodia vastaan tehtävän lineaarisen hyökkäyksen käytännöllisyyttä. $2^{122}$ $2^{128}$

Tarkempi arvio selkeiden tekstien lukumäärästä CAST-salauksen lineaarista kryptausanalyysiä varten voidaan saada ottamalla huomioon pyöreän funktion S-funktioiden liitto. XOR-operaation seurauksena S-funktioiden liitosta johtuen NL min S-laatikon (joka koostuu S-funktioista) epälineaarisuus on suurempi kuin 74. Tarkastellaan 32x32 S-laatikkoa, jolloin m= 32 ja a=r/4 (koska arvioimme kierrosfunktioita joka 4. kierros). Siten saamme 48 kierroksen salauksen lineaariseen krypta-analyysiin tarvittavien selkeiden tekstien lukumäärän, enemmän kuin (suurempi kuin annettujen selkeiden tekstien määrä). Kokeellinen näyttö viittaa siihen, että S-funktion yhdistäminen käyttämällä operaatioita, kuten yhteen- tai vähennyslaskua XOR:n sijaan, voi lisätä S-laatikon epälineaarisuutta entisestään. $2^{176}$

Suojaus differentiaalista kryptausanalyysiä vastaan

Differentiaalinen kryptausanalyysi perustuu salattujen arvojen erojen muuntamisen tutkimukseen eri salauskierroksilla. Lohkosalaukset kestävät differentiaalista kryptausanalyysiä, jos jokaisella kierroksella on yksi eropari syötettävien selkeiden ja tulostettujen salatekstien eroille. Tällaisia eroja kutsutaan ominaisuuksiksi. Pääsääntöisesti erot ovat tehokkaimpia, kun otetaan huomioon kahden tietolohkon XOR. Hyvässä salauksessa kaikkien erojen todennäköisyyden tulisi olla , missä N on lohkon koko. Yhteisen ominaisuuden saamiseksi sisääntulossa ja vastaavan ominaisuuden saamiseksi XOR-lähdössä kootaan sarja ominaisuuksia, jotka riippuvat sisääntulo-, lähtötiedoista, jotka läpikäytiin XOR-operaatio kullakin kierroksella. $2^{{-N}}$

Analyysi perustuu tässä oletukseen, että kaikki kierroksen näppäimet ovat riippumattomia ja että XOR-lähtö (tulon XOR-operaation jälkeen saatu tulos), joka vastaa tiettyä XOR-syötettä (syöte), on riippumaton kierrosten välillä. Tällaisissa olosuhteissa r-kierroksen ominaisuus esitetään seuraavasti:

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

jossa p i on XOR-lähtöerojen todennäköisyys, joka vastaa XOR-tuloeroa kierroksella i .

Taulukossa #2 esitetty R-kierroksen CAST-256-salaus perustuu neljän kierroksen ominaisuusluetteloon.

Taulukko 2: R-round-salauksen paras r-kierroksen suorituskyky

(0, 0, 0, ) $\Delta$	$[syötä ~XOR~ kierrokselle ~1]$
$0\leftarrow\Delta$	$[erä 1]$
$0\leftarrow0$	$[kierros 2]$
$0\leftarrow0$	$[kierros 3]$
$0\leftarrow0$	$[kierros 4]$
(0, 0, 0, ) $\Delta$	$[syötä ~XOR~ kierrokselle~ 5]$
$0\leftarrow\Delta$	$[kierros 5]$
$0\leftarrow0$	$[kierros 6]$
$0\leftarrow0$	$[kierros 7]$
$0\leftarrow0$	$[kierros 8]$
$...$	$toista ~ R/2:een asti$
(0, 0, 0, ) $\Delta$	$[syötä ~XOR~ ~ pyöreäksi~ R/2+1]$
$0\leftarrow\Delta$	$[kierros R/2+1]$
$0\leftarrow0$	$[kierros R/2+2]$
$0\leftarrow0$	$[kierros R/2+3]$
$0\leftarrow0$	$[kierros R/2+4]$
$...$	$toista ~jopa~ r~ kierroksia$

Tiettyjen erojen XOR-vektori (0, 0, 0, ) 4 sisääntulon 32-bittiselle alilohkolle, jossa ensimmäisillä 3 alilohkolla (A in , B in ja C in ) on nolla XOR-eroa ja 4. tuloalilohkolla (D in ) pyöreässä) on jokin nollasta poikkeava XOR-ero, . $\Delta$ $\Delta$

Taulukossa on esitetty yleisen R-kierroksen salauksen ominaisuudet, R/2 + 1 kierroksen XOR-syöte on vektori, jossa yhden alilohkon erotus ei ole yhtä suuri kuin nolla, ja jäljellä olevien alilohkojen erot. kolme alilohkoa on yhtä suuri kuin nolla. Taulukossa esitetty vektori (0, 0, 0, ) vastaa CAST-256-salausta, jonka R = 48. $\Delta$

Nollasta poikkeava XOR-tuloero vastaa nollaa XOR-lähtöeroa joka 4. taulukon 2 ominaisuuden kierros (kuten kierroksilla 1, 5 jne.). Todennäköisyys, että tietyt selkeän tekstin erot ja tietyt salatekstin erot vastaavat yhtä eroparia CAST:lle . Tämä perustuu siihen tosiasiaan, että kaikki neljä CAST-kierrosfunktion S-funktiota ovat injektiokykyisiä ja selväteksti- ja salatekstiparien XOR-arvojen erot ovat 0. Seurauksena on pyöreä funktio käyttämällä toimintojen yhdistelmää, kuten yhteen- ja vähennyslaskulla parin olemassaolon todennäköisyys pienenee selvätekstien ja salatekstien välisiä eroja. Paras r-kierroksen suorituskyky, joka näkyy taulukossa #2 ja perustuu yllä kuvattuihin oletuksiin, määräytyy todennäköisyydellä: $p\leqslant 2^{-14}$

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

Erityisesti 40 kierroksen ominaisuuden (jota voitaisiin mahdollisesti käyttää 48 kierroksen salauksen hyökkäämiseen) todennäköisyyden on oltava pienempi tai yhtä suuri kuin . Siksi tähän hyökkäykseen vaadittavien valittujen selkeiden tekstien määrän on oltava suurempi kuin 48-kierroksen salakirjoituksessa (oleellisesti suurempi kuin selkeiden tekstien määrä 128-bittisessä lohkokoossa). $2^{-140}$ $2^{140}$

Avaimen laajennus

Avaimen laajennusprosessi on monimutkaisempi kuin itse tietojen salaus. Olkoon avainten ryhmä k = (ABCDEFGH) 256-bittinen lohko, jossa fragmentit A, B,…,H ovat kukin 32 bittiä pitkiä. Olkoon "k ← w i (k)", missä w( ) on laajennusfunktio ja se voidaan esittää seuraavassa muodossa: $\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})

Neljän 5 vähiten merkitsevän bitin muunnoksen tuloksena muodostuu siirto-aliavaimia: $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)

jossa 5LSB(x) tarkoittaa 5 vähiten merkitsevän bitin generointia x-operaation tuloksena. Peittoaliavaimet muodostetaan samalla tavalla : $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

Avaimen laajennusmenettelyn toteutus

Jokainen näppäinlaajennusfunktion kierros käyttää 8 lisämuuttujaa ja . $T^{(i)}mj$ $T^{(i)}rj$

1. Alustus

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

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

cr=19

herra = 17

Olkoon = 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. Laajennusavain:

k = ABCDEFGH = 256 bittiä alkuavaimesta K. Olkoon « » « », « » « », « » « », « » « »

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 }

Jos avaimen koko k on pienempi kuin 256 bittiä, "ylimääräisten" avainfragmenttien katsotaan olevan nolla:

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

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

(|K| =192) \nuoli oikealle\, (G = H = 0)

(|K| =224) \nuoli oikealle\, (H = 0)

Algoritmin edut ja haitat

AES-kilpailun ensimmäisessä vaiheessa tehdyn kattavan analyysin tuloksena ei tutkittu vain kryptografisia ominaisuuksia, kuten vastustuskykyä tunnettuja hyökkäyksiä vastaan, heikkojen avainten puuttuminen, hyvät tilastolliset ominaisuudet, vaan myös toteutuksen käytännön näkökohdat: koodin suoritusnopeus eri arkkitehtuureissa (PC:stä älykortteihin ja laitteistototeutuksiin), koodin koon optimointimahdollisuus, rinnakkaismahdollisuuden mahdollisuus, seuraavat CAST-256-salauksen edut ja haitat paljastettiin.

Tärkeimmät edut ovat:

ei haavoittuvuuksia.
kyky suorittaa nopeasti avaimen laajennus, toisin sanoen koodaustoiminnon aikana, mutta ei dekoodauksen aikana.

Algoritmista löydettiin useita puutteita, joiden vuoksi se ei päässyt kilpailun toiselle kierrokselle:

algoritmin salausnopeus on alhainen verrattuna useisiin algoritmeihin - kilpailun osallistujat, mukaan lukien kaikki kilpailun finalistit.
korkeat vaatimukset operatiiviselle ja haihtuvalle muistille.

Kirjallisuus

Sergei Panasenko. Salausalgoritmit . - Pietari: BHV-Petersburg, 2009. - S. 134-141. - 576 s. — ISBN 978-5-9775-0319-8 . (Venäjän kieli)

Linkit

Symmetriset salausjärjestelmät
Suoratoista salauksia	A3 A5 A8 Desim F-FCSR Vilja HC-256 KCipher-2 MIKKI MUGI HAUKI Phelix RC4 Kani TIIVISTE LUMI SOSEMANUK Salsa 20 STRUMOK Trivium VMPC
Feistelin verkko	GOST 28147-89 (Magma) blowfish Camellia CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra SOPIMUS DES DESX DFC E2 enRUPT FEAL HPC IDEA KASUMI Khafre Khufu LOKI97 MacGuffin MARS MESH MISTY1 UusiDES NDS RC5 RC6 SIEMEN Simon Sinopoli jätkä SM4 Speck TEE XTEA XXTEA Raiden RTEA Kolminkertainen DES Kaksi kalaa
SP verkko	Heinäsirkka 3 tapaa ABC AARIA AES (Rijndael) Akelarre Anubis BaseKing Basso Omatic Vyö CRYPTON Timantti 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer esittää Sateenkaari TURVALLISTA HAI NELIÖ Käärme kolme kalaa
muu	SAMMAKKO NUSH REDOC SC2000 SHACAL CS-Cipher