KHAZAD

KHAZAD

Luoja	Vincent Rayman ja Paulo Barreto
Luotu	2000_ _
julkaistu	2000_ _
Avaimen koko	128 bittinen
Lohkon koko	64-bittinen
Kierrosten lukumäärä	kahdeksan
Tyyppi	Korvaus-permutaatioverkko

KHAZAD on symmetrinen lohkosalaus kryptografiassa , jonka ovat kehittäneet kaksi kryptografia: belgialainen Vincent Raymen ( Rijndael -salauksen kirjoittaja ) ja brasilialainen Paulo Barreto . . Algoritmi käyttää 64 bitin (8 tavua) datalohkoja ja 128 bitin avaimia. KHAZAD esiteltiin eurooppalaisessa kryptografisten primitiivien kilpailussa NESSIE vuonna 2000, jossa siitä tuli muunneltuna (viritettynä) yksi finalistialgoritmeista (mutta ei voittaja). [yksi]

KHAZAD-algoritmin edeltäjä on Vincent Raymenin ja Joan Dymenin vuonna 1995 kehittämä SHARK - salaus . KHAZADin kirjoittajat väittävät, että algoritmi perustuu Yoan Dymenin ehdottamaan kryptografisesti vahvojen salausalgoritmien kehittämisstrategiaan (Wide-Trail-strategia). [2]

KHAZAD-algoritmilla on konservatiiviset parametrit, ja se on suunniteltu korvaamaan olemassa olevat 64-bittiset salaukset, kuten IDEA ja DES , mikä tarjoaa korkeamman suojaustason suurella suoritusnopeudella.

Salaus käyttää laajasti involuutiomuunnoksia , mikä minimoi eron salaus- ja salauksenpurkualgoritmien välillä.

Salauksen kuvaus

KHAZAD on iteratiivinen lohkosalaus, jonka lohkokoko on 64 bittiä ja 128-bittinen avain. Syötetietolohko esitetään 8 tavun merkkijonona.

S-laatikko ja sekoitusmatriisi valitaan siten, että salaus ja salauksen purku ovat samat toiminnot ( involuutio ), lukuun ottamatta pyöreitä aliavaimia.

KHAZAD, kuten AES (Rijndael) -algoritmi , kuuluu SHARK -salauksesta johdettujen lohkosalausten perheeseen . [3] [4]

Tärkeimmät erot SHARKista on esitetty taulukossa [1] :

Tärkeimmät erot KHAZAD- ja SHARK-salausten välillä

	HAI	KHAZAD
Kierrosten lukumäärä	6	kahdeksan
Aikataulu (laajennus) -avain	Affiinimuunnos, joka johtuu salauksen toiminnasta salatekstin palautetilassa	Feistel-kaavio , jossa Feistel-funktio on salauksen pyöreä funktio
Pelkistymättömän kentän polynomi $\mathbb {GF} (2^{8})$	$x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{2}+1$ (0x1F5)	$x^8+x^4+x^3+x^2+1$ (0x11D)
S-box toteutus	Kentän kartoitus + affiinimuunnos ${\displaystyle u\rightarrow u^{-1))$ $\mathbb {GF} (2^{8})$	P- ja Q-minilohkojen rekursiivinen rakenne
Sekoitusmatriisin toteutus	Reed-Solomon koodi	Involution MDS-koodi

Alkuperäinen KHAZAD-salaus (nimeltään KHAZAD-0) on nyt vanhentunut. Salauksen nykyistä (lopullista) muotoa on muokattu ("viritetty") sen mukauttamiseksi laitteistototeutukseen. Tässä muodossa KHAZAD tunnustettiin NESSIE-finalistiksi. Muutos ei vaikuttanut salauksen perusrakenteeseen. Siinä alun perin täysin satunnaisesti luotu S-laatikko (ilman selkeää sisäistä rakennetta) korvataan rekursiivisella rakenteella: uusi 8x8-korvauslaatikko koostuu pienistä näennäissatunnaisesti luoduista 4x4-minilaatikoista. (P- ja Q-laatikot). [yksi]

Algoritmin rakenne

Soveltamalla avaimen laajennusmenettelyä avaimeen saadaan sarja pyöreitä avaimia . $K$ ${\displaystyle k_{0}...k_{8))$

Algoritmi sisältää 8 kierrosta, joista jokainen koostuu 3 vaiheesta:

epälineaarinen muunnos $\gamma$
lineaarinen muunnos $\theta$
pyöreän avaimen lisääminen $\sigma$

Ennen ensimmäistä kierrosta suoritetaan valkaisu - . Leikkausta ei suoriteta viimeisellä kierroksella. $\sigma (k_{0})$ $\theta$

Operaattorimuodossa algoritmi kirjoitetaan seuraavasti:

Salaus: $(\sigma [k_{8}]\circ \gamma )\circ (\sigma [k_{7}]\circ \theta \circ \gamma )\circ ...\circ (\sigma [k_{ 1}]\circ \theta \circ \gamma )\circ \sigma [k_{0}]$

Salauksen purku: $(\sigma [k_{0}]\circ \gamma )\circ (\sigma [\theta (k_{1})]\circ \theta \circ \gamma )\circ ...\circ (\ sigma [\theta (k_{7})]\circ \theta \circ \gamma )\circ \sigma [k_{8}]$

Pyöreän avaimen joukko saadaan soveltamalla avaimen laajennusmenettelyä salausavaimeen. ${\displaystyle k_{0}...k_{8))$ $K$

Pyöreä rakenne

Pyöreä muunnos voidaan kirjoittaa seuraavasti: . $\rho [k]=\sigma [k]\circ \theta \circ \gamma$

Epälineaarinen muunnos $\gamma$

Jokaisella kierroksella syöttölohko jaetaan 8 tavuun, joille tehdään itsenäisesti epälineaarinen muunnos (korvaus), eli ne kulkevat samojen S-laatikoiden läpi rinnakkain (jokainen S-laatikko on 8x8 bittiä, on 8 bittiä sisääntulossa ja 8 bittiä lähdössä). Korvauslohkot alkuperäisessä ja muokatussa (viritetyssä) salauksessa ovat erilaisia. Korvauslohko valitaan siten, että epälineaarinen muunnos on involuutio, eli tai . ${\displaystyle \gamma =\gamma ^{-1))$ ${\näyttötyyli \gamma (\gamma (x))=x}$

Lineaarinen muunnos $\theta$

8-tavuinen datamerkkijono kerrotaan tavu tavulta kiinteällä 8 x 8 matriisilla, ja tavut kerrotaan Galois'n kentässä pelkistymättömällä polynomilla (0x11D). $H$ $\mathbb {GF} (2^{8})$ $x^8+x^4+x^3+x^2+1$

$\theta (x)=x\times H$

Matrix H (heksadesimaalimuoto)

yksi	3	neljä	5	6	kahdeksan	B	7
3	yksi	5	neljä	kahdeksan	6	7	B
neljä	5	yksi	3	B	7	6	kahdeksan
5	neljä	3	yksi	7	B	kahdeksan	6
6	kahdeksan	B	7	yksi	3	neljä	5
kahdeksan	6	7	B	3	yksi	5	neljä
B	7	6	kahdeksan	neljä	5	yksi	3
7	B	kahdeksan	6	5	neljä	3	yksi

Edellä mainitussa Galois'n kentässä matriisi on symmetrinen ( , ) ja ortogonaalinen ( ). Eli tämän matriisin määrittelemä muunnos on involuutio: , missä on identiteettimatriisi $H$ ${\displaystyle a_{ij}=a_{ji))$ ${\displaystyle H=H^{T))$ ${\displaystyle H^{-1}=H^{T))$ $H^{-1}=H$ ${\textstyle \theta (\theta (x))=x\times H\times H=x\times H\times H^{-1}=x\times E=x}$ $E$

Pyöreän näppäimen peitto $\sigma [k_{i}]$

Bittikohtainen XOR -toiminto suoritetaan 64-bittiselle datalohkolle ja 64-bittiselle pyöreälle avaimelle .

Avaimen laajennus

128-bittinen (16-tavuinen) avain on jaettu kahteen yhtä suureen osaan: $K$

$k_{{-1}}$ - korkea 8 tavua (15. - 8.)
$k_{-2}$ - alempi 8 tavua (7. 0:sta)

Avaimet lasketaan Feistelin kaavion mukaan : ${\displaystyle k_{0}...k_{8))$

${\displaystyle k_{i}=f(C_{i},k_{i-1})\oplus k_{i-2))$

Tässä:

$f(x,y)$ on algoritmin pyöreä funktio syöttölohkolla ja näppäimellä . $x$ $y$

$C_{i}$ on 64-bittinen vakio, jonka tavu on . $j$ $C_{i}^{j}=S(8i+j)$

Salauksen epälineaarisen muunnoksen ja modifioinnin rakenne

Alkuperäinen salaus

Alkuperäisessä salausversiossa (KHAZAD-0) taulukon vaihtoa edusti klassinen S-laatikko, ja se kuvattiin seuraavalla matriisilla:

Taulukon yhden tavun korvaaminen KHAZAD-0:ssa. [5] Tässä sarakkeen numero on syötteen 4 ensimmäistä bittiä heksadesimaalimuodossa , rivin numero on toiset 4 bittiä. Niiden leikkauskohdassa olevan solun arvo on S-laatikon lähtö.

	0	yksi	2	3	neljä	5	6	7	kahdeksan	9	A	B	C	D	E	F
0	A7	D3	E6	71	D0	AC	4D	79	3A	C9	91	FC	1E	47	54	BD
yksi	8C	A5	7A	Facebook	63	B8	DD	D4	E5	B3	C5	OLLA	A9	88	0C	A2
2	39	D.F.	29	DA	2B	A8	CB	4C	4B	22	AA	24	41	70	A6	F9
3	5A	E2	B0	36	7D	E4	33	FF	60	kaksikymmentä	08	8B	5E	AB	7F	78
neljä	7C	2C	57	D2	DC	6D	7E	0D	53	94	C3	28	27	06	5F	ILMOITUS
5	67	5C	55	48	0E	52	EA	42	5B	5D	kolmekymmentä	58	51	59	3C	4E
6	38	8A	72	neljätoista	E7	C6	DE	viisikymmentä	8E	92	D1	77	93	45	9A	CE
7	2D	03	62	B6	B9	bf	96	6B	3F	07	12	AE	40	34	46	3E
kahdeksan	D.B.	CF	EU	CC	C1	A1	C0	D6	1D	F4	61	3B	kymmenen	D8	68	A0
9	B1	0A	69	6C	49	FA	76	C4	9E	9B	6E	99	C2	B7	98	eKr
A	8F	85	1F	B4	F8	yksitoista	2E	00	25	1C	2A	3D	05	4F	7B	B2
B	32	90	AF	19	A3	F7	73	9D	viisitoista	74	EE	CA	9F	0F	1B	75
C	86	84	9C	4A	97	1A	65	F6	ED	09	BB	26	83	EB	6F	81
D	04	6A	43	01	17	E1	87	F5	8D	E3	23	80	44	16	66	21
E	F.E.	D5	31	D9	35	kahdeksantoista	02	64	F2	F1	56	CD	82	C8	BA	F0
F	EF	E9	E8	FD	89	D7	C7	B5	A4	2F	95	13	0B	F3	E0	37

Tämä taulukko vastaa täysin Anubis -algoritmissa käytettyä taulukkoa (toinen algoritmi, jonka samat kirjoittajat ovat kehittäneet ja lähettäneet NESSIE-kilpailuun). [2]

S-boxin valintaperiaate [5]

Mikä tahansa Boolen funktio voidaan esittää Zhegalkin-polynomina (algebrallinen normaalimuoto). Funktion epälineaarinen järjestys on Zhegalkin-polynomin järjestys, eli sen jäsenten kertalukujen maksimi. $f:GF(2)^{n}\rightarrow GF(2)$ $f$

Jos esittelemme funktion , ${\displaystyle \alpha \in GF(2)^{n))$ ${\displaystyle l_{\alpha }=\bigoplus _{i=0}^{n-1}\alpha _{i}\cdot x_{i))$ $l_{\alpha }:GF(2)^{n}\rightarrow GF(2)$

Korvaava lohko on kartoitus . Sitä voidaan myös tarkastella näyttönä . $GF(2^{n})\rightarrow GF(2^{n})$ ${\displaystyle GF(2)^{n}\rightarrow GF(2)^{n))$

$S[x]=(s_{0}(x),...,s_{n-1}(x))$ , missä $s_{i}:GF(2)^{n}\rightarrow GF(2),0\leqslant i\leqslant n-1$

S-boxin epälineaarinen järjestys - - pienin epälineaarinen järjestys kaikkien lineaaristen komponenttien yhdistelmien joukossa : $S$ ${\näyttötyyli \nu _{s))$ $S$ $\nu _{s}\equiv \min _{\alpha \in GF(2)^{n))\nu (l_{\alpha }\circ S)$

$\delta$ - S-box-parametri: , arvoa kutsutaan differentiaaliseksi yhtenäisyydeksi $\delta _{S}\equiv 2^{-n}\cdot \max _{a\neq 0,b}\{c\in GF(2^{n})\mid S[c\oplus a]\oplus S[c]=b\}$ $2^{n}\cdot \delta$ $S$

Kahden Boolen funktion korrelaatio $c(f,g)\equiv 2^{1-n}\cdot \{x\mid f(x)=g(x)\}-1$

$\lambda$ - S-lohkon parametri: $\lambda _{S}\equiv \max _{(i,j)\neq (0,0)}\left\vert c(l_{i},l_{j}\circ S)\right\ vert$

KHAZAD-0 salaus käyttää näennäissatunnaisesti luotua S-laatikkoa, joka täyttää seuraavat vaatimukset:

täytyy olla involuutio
$\delta$ -parametri ei saa ylittää arvoa $8\times 2^{-8}$
$\lambda$ -parametri ei saa ylittää arvoa $16\times 2^{-6}$
epälineaarisen järjestyksen tulee olla suurin, nimittäin yhtä suuri kuin 7 $\nu$

Muokattu salaus

Khazadin kirjoittajat tekivät myös muutoksia algoritmiinsa käyttämällä tilaisuutta muuttaa hieman algoritmia kilpailun ensimmäisen kierroksen aikana. Algoritmimäärittelyn uudessa versiossa alkuperäinen Khazad-algoritmi on nimeltään Khazad-0 ja muokatulle algoritmille annetaan nimi Khazad. [2] (Panasenko S.P. "Salausalgoritmit. Erikoisviitekirja")

Salauksen muokatussa versiossa 8x8 S-laatikko on muutettu ja sitä edustaa rekursiivinen rakenne, joka koostuu P- ja Q-minilaatikoista, joista jokainen on pieni korvaava lohko, jossa on 4 tulo- ja lähtöbittiä (4x4).

Korvaavan lohkon rekursiivinen rakenne muokatussa KHAZAD-salauksessa: [6]

Lähtöarvojen vastaavuus minilohkon P tuloarvojen kanssa

u	0	yksi	2	3	neljä	5	6	7	kahdeksan	9	A	B	C	D	E	F
P(u)	3	F	E	0	5	neljä	B	C	D	A	9	6	7	kahdeksan	2	yksi

Lähtöarvojen vastaavuus minilohkon Q tuloarvojen kanssa

u	0	yksi	2	3	neljä	5	6	7	kahdeksan	9	A	B	C	D	E	F
Q(u)	9	E	5	6	A	2	3	C	F	0	neljä	D	7	B	yksi	kahdeksan

Tämä P- ja Q-minilaatikoiden rakenne vastaa S-laatikkoa seuraavalla korvaustaulukolla: [1]

Tuloksena oleva S-laatikko muokatussa KHAZAD-salauksessa. Tässä sarakkeen numero on syötteen 4 ensimmäistä bittiä, rivin numero on toiset 4 bittiä. Niiden leikkauskohdassa olevan solun arvo on S-laatikon lähtö.

	0	yksi	2	3	neljä	5	6	7	kahdeksan	9	A	B	C	D	E	F
0	BA	54	2F	74	53	D3	D2	4D	viisikymmentä	AC	8D	bf	70	52	9A	4C
yksi	EA	D5	97	D1	33	51	5B	A6	DE	48	A8	99	D.B.	32	B7	FC
2	E3	9E	91	9B	E2	BB	41	6E	A5	CB	6B	95	A1	F3	B1	02
3	CC	C4	1D	neljätoista	C3	63	DA	5D	5F	DC	7D	CD	7F	5A	6C	5C
neljä	F7	26	FF	ED	E8	9D	6F	8E	19	A0	F0	89	0F	07	AF	Facebook
5	08	viisitoista	0D	04	01	64	D.F.	76	79	DD	3D	16	3F	37	6D	38
6	B9	73	E9	35	55	71	7B	8C	72	88	F6	2A	3E	5E	27	46
7	0C	65	68	61	03	C1	57	D6	D9	58	D8	66	D7	3A	C8	3C
kahdeksan	FA	96	A7	98	EU	B8	C7	AE	69	4B	AB	A9	67	0A	47	F2
9	B5	22	E5	EE	OLLA	2B	81	12	83	1B	0E	23	F5	45	21	CE
A	49	2C	F9	E6	B6	28	17	82	1A	8B	F.E.	8A	09	C9	87	4E
B	E1	2E	E4	E0	EB	90	A4	1E	85	60	00	25	F4	F1	94	0B
C	E7	75	EF	34	31	D4	D0	86	7E	ILMOITUS	FD	29	kolmekymmentä	3B	9F	F8
D	C6	13	06	05	C5	yksitoista	77	7C	7A	78	36	1C	39	59	kahdeksantoista	56
E	B3	B0	24	kaksikymmentä	B2	92	A3	C0	44	62	kymmenen	B4	84	43	93	C2
F	4A	BD	8F	2D	eKr	9C	6A	40	CF	A2	80	4F	1F	CA	AA	42

Taulukoista on helppo nähdä, että sekä alkuperäisessä että muunnelmassa S-laatikot ovat involutionaalisia eli . $S(S(x))=x$

Turvallisuus

KHAZADin oletetaan olevan yhtä turvallinen kuin lohkosalauksen annetulla lohkolla ja avaimen pituudella.

Tämä sisältää muun muassa seuraavat:

Tehokkain hyökkäys KHAZAD-salauksen avaimen löytämiseksi on raaka voima.
saada näistä pareista selväteksti - salateksti, tietoa muista vastaavista pareista ei voida suorittaa tehokkaammin kuin avaimen löytäminen kattavalla haulla.
raa'alla voimalla avaimen etsimisen odotettu monimutkaisuus riippuu avaimen bitin pituudesta ja on yhtä suuri kuin KHAZAD-salaus. $2^{127}$

Salaukseen sisältyi niin suuri turvamarginaali ottaen huomioon kaikki tunnetut hyökkäykset. [yksi]

On olemassa hyökkäyksiä vain lyhennettyä versiota salauksesta, jossa on 5 patruunaa (Frédéric Muller, 2003). [7]

Kuten näette, vakavia ongelmia Khazad-algoritmin kryptografisessa vahvuudessa ei löydetty, minkä myös NESSIE-kilpailun asiantuntijat totesivat. Lisäksi asiantuntijat havaitsivat tämän algoritmin erittäin suuren salausnopeuden. Khazad tunnustettiin lupaavaksi algoritmiksi, erittäin kiinnostavaksi jatkotutkimuksen kannalta, mutta siitä ei tullut yksi kilpailun voittajista, koska asiantuntijat epäilivät, että algoritmin rakenne saattaa sisältää piilotettuja haavoittuvuuksia, joita saattaa löytyä tulevaisuudessa.

— Panasenko S. P. "Salausalgoritmit. Erityinen hakuteos" [2]

Saatavuus

KHAZAD-salausta ei ole (eikä koskaan tule) patentoitu. Sitä voidaan käyttää ilmaiseksi mihin tahansa tarkoitukseen. [yksi]

Alkuperäinen teksti (englanniksi)[ näytäpiilottaa] KHAZAD ei ole (eikä koskaan tule) patentoitua. Sitä voidaan käyttää ilmaiseksi mihin tahansa tarkoitukseen. [yksi]

Otsikko

Salaus on nimetty J. R. R. Tolkienin Taru sormusten herrasta -trilogiasta Khazad-dûmin tai Morian mukaan, joka on kääpiöiden valtava maanalainen valtakunta Keski-Maan sumuisilla vuorilla . [yksi]

Katso myös

Muistiinpanot

↑ 1 2 3 4 5 6 7 8 Paulo Sérgio LM Barreto, Vincent Rijmen. Khazad Block Cipher (linkki ei saatavilla) . www.larc.usp.br. Haettu 30. marraskuuta 2016. Arkistoitu alkuperäisestä 1. joulukuuta 2016. (määrätön)
↑ 1 2 3 4 Panasenko S.P. Salausalgoritmit. Erikoisopas .. - Pietari. : BHV-Petersburg, 2009. - S. 282-287. — 576 s. — ISBN 978-5-9775-0319-8 .
↑ 1 2 Lars R. Knudsen, Matthew JB Robshaw. Block Cipher Companion . - Springer, 2011. - s . 63 . — 267 s. - ISBN 978-3-642-17341-7 .
↑ Joan Daernen, Vincent Rijrnen. Rijndaelin suunnittelu. - Springer, 2002. - S. 160. - 238 s. — ISBN 3-540-42580-2 .
↑ 1 2 NESSIE-kilpailun ensimmäisen kierroksen Khazad-salauksen kuvaus . Haettu 2. joulukuuta 2016. Arkistoitu alkuperäisestä 6. toukokuuta 2021. (määrätön)
↑ Paulo SLM Barreto ja Vincent Rijmen. KHAZAD-perintötason lohkosalaus . Arkistoitu alkuperäisestä 23. helmikuuta 2012.
↑ Frederic Muller. Uusi hyökkäys khazadia vastaan // julkaisussa Proceedings of ASIACRYPT 2003. — s. 347–358 . Arkistoitu alkuperäisestä 6. maaliskuuta 2016.

Kirjallisuus

Panasenko S. P. Salausalgoritmit. Erikoisopas. - Pietari: BHV-Petersburg, 2009. - 576 s.: ill. ISBN 978-5-9775-0319-8

Linkit

KHAZAD-salauksen virallinen sivu
Paulo SLM Barreto ja Vincent Rijmen. KHAZAD Legacy-Level Block Cipher (viritetty, KHAZAD). Ensimmäisessä avoimessa NESSIE-työpajassa, KU-Leuven, 2000. Muokattu lähetys NESSIE:lle valittu 2. vaiheeseen.
Paulo SLM Barreto ja Vincent Rijmen. KHAZAD Legacy-Level Block Cipher (alkuperäinen, KHAZAD-0). Alkuperäinen lähetys NESSIElle.
Aleksi Biryukov. Involutionaalisten salakirjoitusten analyysi: Khazad ja Anubis . Teoksessa T. Johansson, toimittaja, Fast Software Encryption - 2003, Lectures Notes in Computer Science. Springer, 2003.
Frederic Muller. Uusi hyökkäys Khazadia vastaan. Kryptologian edistysaskel
Luettelo NESSIE-lähetyksistä alun perin lähetetyssä muodossa
Toiseen vaiheeseen valitut NESSIE-lähetysten muutokset
NESSIE-projektin toimitukset
NESSIE:n julkinen raportti D14: Raportti NESSIE-ehdokkaiden suoritusarvioinnista I
NESSIE:n julkinen raportti D18: Päivitys algoritmien valinnasta lisätutkimuksia varten toisen kierroksen aikana.

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
Muut	SAMMAKKO NUSH REDOC SC2000 SHACAL CS-Cipher