KHAZAD

KHAZAD

Skaber	Vincent Rayman og Paulo Barreto
Oprettet	2000 _
offentliggjort	2000 _
Nøglestørrelse	128 bit
Blokstørrelse	64 bit
Antal runder	otte
Type	Substitution-permutation netværk

KHAZAD er en symmetrisk blokcifre i kryptografi , udviklet af to kryptografer: belgieren Vincent Raymen (forfatter af Rijndael -cifret ) og brasilianeren Paulo Barreto . Algoritmen bruger datablokke på 64 bit (8 bytes) og nøgler på 128 bit. KHAZAD blev præsenteret ved den europæiske konkurrence for kryptografiske primitiver NESSIE i 2000, hvor det i en modificeret (tweaket) form blev en af finalistalgoritmerne (men ikke vinderen). [en]

Forgængeren til KHAZAD-algoritmen er SHARK -chifferet udviklet i 1995 af Vincent Raymen og Joan Dymen . Forfatterne af KHAZAD hævder, at algoritmen er baseret på strategien for udvikling af kryptografisk stærke krypteringsalgoritmer (Wide-Trail strategi), foreslået af Yoan Dymen. [2]

KHAZAD-algoritmen har konservative parametre og er designet til at erstatte eksisterende 64-bit-cifre såsom IDEA og DES , hvilket giver et højere sikkerhedsniveau ved høj udførelseshastighed.

Chifferen gør udstrakt brug af involutionelle transformationer , hvilket minimerer forskellen mellem krypterings- og dekrypteringsalgoritmer.

Beskrivelse af chifferen

KHAZAD er en iterativ blokchiffer med en blokstørrelse på 64 bit og en 128-bit nøgle. Indgangsdatablokken er repræsenteret som en streng på 8 bytes.

S-boksen og shuffling-matrixen er valgt på en måde, der sikrer, at kryptering og dekryptering er den samme operation ( involution ), bortset fra runde undernøgler.

KHAZAD tilhører ligesom AES (Rijndael) algoritmen en familie af blokcifre afledt af SHARK-chifferen. [3] [4]

De vigtigste forskelle fra SHARK er præsenteret i tabellen [1] :

Hovedforskelle mellem KHAZAD- og SHARK-cifre

	HAJ	KHAZAD
Antal runder	6	otte
Tast til tidsplan (udvidelse).	Affin transformation som følge af driften af chifferen i chiffertekst-feedback-tilstand	Feistel-skema , hvor Feistel-funktionen er chifferens runde funktion
Irreducerbart feltpolynomium $\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-boks implementering	Tilknytning til et felt + affin transformation ${\displaystyle u\rightarrow u^{-1))$ $\mathbb {GF} (2^{8})$	Rekursiv struktur af P- og Q-miniblokke
Implementering af shuffling matrix	Reed-Solomon kode	Involution MDS-kode

Den originale KHAZAD-chiffer (kaldet KHAZAD-0) er nu forældet. Den nuværende (endelige) form for chifferen er blevet ændret ("tweaked") for at tilpasse den til hardwareimplementeringen. I denne form blev KHAZAD anerkendt som NESSIE-finalist. Ændringen påvirkede ikke den grundlæggende struktur af chifferen. I den er S-boksen, som oprindeligt blev genereret fuldstændig tilfældigt (uden en klar definition af nogen intern struktur), erstattet med en rekursiv struktur: en ny 8x8 erstatningsboks består af små pseudo-tilfældigt genererede 4x4 mini-bokse (P- og Q-bokse). [en]

Algoritmestruktur

Ved at anvende nøgleudvidelsesproceduren på nøglen opnås et sæt runde nøgler . $K$ ${\displaystyle k_{0}...k_{8))$

Algoritmen omfatter 8 runder, som hver består af 3 trin:

ikke-lineær transformation $\gamma$
lineær transformation $\theta$
tilføje en rund nøgle $\sigma$

Inden første runde udføres blegning - . Operationen udføres ikke i sidste runde. $\sigma (k_{0})$ $\theta$

I operatorform er algoritmen skrevet som følger:

Kryptering: $(\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}]$

Dekryptering: $(\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}]$

Sættet af runde nøgler opnås ved at anvende nøgleudvidelsesproceduren på krypteringsnøglen. ${\displaystyle k_{0}...k_{8))$ $K$

Runde struktur

Den runde transformation kan skrives som følger: . $\rho [k]=\sigma [k]\circ \theta \circ \gamma$

Ikke-lineær transformation $\gamma$

I hver runde er inputblokken opdelt i 8 bytes, som uafhængigt udsættes for en ikke-lineær transformation (erstatning), det vil sige, at de passerer gennem de samme S-bokse parallelt (hver S-boks er 8x8 bit, dvs. er 8 bits ved indgangen og 8 bits ved udgangen). Erstatningsblokke i den originale og den modificerede (tweakede) chiffer er forskellige. Erstatningsblokken er valgt på en sådan måde, at den ikke-lineære transformation er involutional, det vil sige eller . ${\displaystyle \gamma =\gamma ^{-1))$ $\gamma (\gamma (x))=x$

Lineær transformation $\theta$

En 8-byte datastreng multipliceres byte for byte med en fast 8 x 8 matrix, og bytes multipliceres i et Galois-felt med et irreducerbart polynomium (0x11D). $H$ $\mathbb {GF} (2^{8})$ $x^8+x^4+x^3+x^2+1$

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

Matrix H (hex-format)

en	3	fire	5	6	otte	B	7
3	en	5	fire	otte	6	7	B
fire	5	en	3	B	7	6	otte
5	fire	3	en	7	B	otte	6
6	otte	B	7	en	3	fire	5
otte	6	7	B	3	en	5	fire
B	7	6	otte	fire	5	en	3
7	B	otte	6	5	fire	3	en

I det førnævnte Galois-felt er matrixen symmetrisk ( , ) og ortogonal ( ). Det vil sige , transformationen specificeret af denne matrix er en involution: , hvor er identitetsmatrixen $H$ ${\displaystyle a_{ij}=a_{ji))$ ${\displaystyle H=H^{T))$ ${\displaystyle H^{-1}=H^{T))$ $H^{-1}=H$ ${\tekststil \theta (\theta (x))=x\ gange H\ gange H=x\ gange H\ gange H^{-1}=x\ gange E=x}$ $E$

Overlejring af den runde nøgle $\sigma [k_{i}]$

En bitvis XOR -operation udføres på en 64-bit datablok og en 64-bit rund nøgle .

Nøgleudvidelse

128-bit (16-byte) nøglen er opdelt i 2 lige store dele: $K$

$k_{{-1}}$ - høje 8 bytes (fra 15. til 8.)
$k_{-2}$ - lavere 8 bytes (fra 7. til 0.)

Nøglerne er beregnet efter Feistel-skemaet : ${\displaystyle k_{0}...k_{8))$

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

Her:

$f(x,y)$ er den runde funktion af algoritmen med inputblokken og tasten . $x$ $y$

$C_{i}$ er en 64-bit konstant, hvis byte er . $j$ $C_{i}^{j}=S(8i+j)$

Strukturen af den ikke-lineære transformation og modifikation af chifferen

Original chiffer

I den originale version af chifferen (KHAZAD-0) blev bordudskiftningen repræsenteret af en klassisk S-boks og blev beskrevet af følgende matrix:

Tabeludskiftning af en byte i KHAZAD-0. [5] Her er kolonnenummeret de første 4 bit af input i hex - repræsentation, rækkenummeret er de anden 4 bit. Værdien af cellen ved deres skæringspunkt er output fra S-boksen.

	0	en	2	3	fire	5	6	7	otte	9	EN	B	C	D	E	F
0	A7	D3	E6	71	D0	AC	4D	79	3A	C9	91	FC	1E	47	54	BD
en	8C	A5	7A	Facebook	63	B8	DD	D4	E5	B3	C5	VÆRE	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	tyve	08	8B	5E	AB	7F	78
fire	7C	2C	57	D2	DC	6D	7E	0D	53	94	C3	28	27	06	5F	AD
5	67	5C	55	48	0E	52	EA	42	5B	5D	tredive	58	51	59	3C	4E
6	38	8A	72	fjorten	E7	C6	DE	halvtreds	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
otte	D.B.	CF	EU	CC	C1	A1	C0	D6	1D	F4	61	3B	ti	D8	68	A0
9	B1	0A	69	6C	49	FA	76	C4	9E	9B	6E	99	C2	B7	98	f.Kr
EN	8F	85	1F	B4	F8	elleve	2E	00	25	1C	2A	3D	05	4F	7B	B2
B	32	90	AF	19	A3	F7	73	9D	femten	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	atten	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

Denne tabel svarer fuldstændig til den, der bruges i Anubis- algoritmen (en anden algoritme udviklet og indsendt til NESSIE-konkurrencen af de samme forfattere). [2]

S-boks valgprincip [5]

Enhver boolsk funktion kan repræsenteres som et Zhegalkin-polynomium (algebraisk normalform). Den ikke-lineære rækkefølge af en funktion er rækkefølgen af Zhegalkin-polynomiet, det vil sige maksimum af rækkefølgen af dens medlemmer. $f:GF(2)^{n}\rightarrow GF(2)$ $f$

Hvis vi introducerer funktionen , ${\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)$

Erstatningsblokken er en kortlægning . Det kan også ses som et display . $GF(2^{n})\rightarrow GF(2^{n})$ ${\displaystyle GF(2)^{n}\rightarrow GF(2)^{n))$

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

S-box ikke-lineær rækkefølge - - den mindste ikke-lineære rækkefølge blandt alle lineære kombinationer af komponenter : $S$ ${\displaystyle \nu _{s))$ $S$ $\nu _{s}\equiv \min _{\alpha \in GF(2)^{n))\nu (l_{\alpha }\circ S)$

$\delta$ - S-boks parameter: , værdien kaldes differentiel ensartethed $\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$

Korrelation af to booleske funktioner $c(f,g)\equiv 2^{1-n}\cdot \{x\mid f(x)=g(x)\}-1$

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

KHAZAD-0-chifferet bruger en pseudo-tilfældigt genereret S-boks, der opfylder følgende krav:

må være en involution
$\delta$ -parameter må ikke overstige værdien $8\ gange 2^{-8}$
$\lambda$ -parameter må ikke overstige værdien $16\ gange 2^{-6}$
ikke-lineær rækkefølge skal være maksimum, nemlig lig med 7 $\nu$

Ændret ciffer

Da Khazad-forfatterne benyttede lejligheden til at ændre algoritmen lidt under konkurrencens første runde, foretog Khazad-forfatterne også ændringer i deres algoritme. I den nye version af algoritmespecifikationen hedder den originale Khazad-algoritme Khazad-0, og navnet Khazad er givet til den modificerede algoritme. [2] (Panasenko S.P. "Krypteringsalgoritmer. Særlig opslagsbog")

I den modificerede version af chifferen er 8x8 S-boksen ændret og repræsenteret af en rekursiv struktur bestående af P- og Q-minibokse, som hver er en lille erstatningsblok med 4 input- og outputbits (4x4).

Rekursiv struktur af erstatningsblokken i den modificerede KHAZAD-chiffer: [6]

Overensstemmelse mellem outputværdier og inputværdier for miniblok P

u	0	en	2	3	fire	5	6	7	otte	9	EN	B	C	D	E	F
P(u)	3	F	E	0	5	fire	B	C	D	EN	9	6	7	otte	2	en

Overensstemmelse mellem outputværdier og inputværdier for miniblok Q

u	0	en	2	3	fire	5	6	7	otte	9	EN	B	C	D	E	F
Q(u)	9	E	5	6	EN	2	3	C	F	0	fire	D	7	B	en	otte

Denne struktur af P- og Q-minibokse svarer til en S-boks med følgende substitutionstabel: [1]

Den resulterende S-boks i den modificerede KHAZAD-chiffer. Her er kolonnenummeret de første 4 bit af input, rækkenummeret er de anden 4 bit. Værdien af cellen ved deres skæringspunkt er output fra S-boksen.

	0	en	2	3	fire	5	6	7	otte	9	EN	B	C	D	E	F
0	BA	54	2F	74	53	D3	D2	4D	halvtreds	AC	8D	bf	70	52	9A	4C
en	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	fjorten	C3	63	DA	5D	5F	DC	7D	CD	7F	5A	6C	5C
fire	F7	26	FF	ED	E8	9D	6F	8E	19	A0	F0	89	0F	07	AF	Facebook
5	08	femten	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
otte	FA	96	A7	98	EU	B8	C7	AE	69	4B	AB	A9	67	0A	47	F2
9	B5	22	E5	EE	VÆRE	2B	81	12	83	1B	0E	23	F5	45	21	CE
EN	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	AD	FD	29	tredive	3B	9F	F8
D	C6	13	06	05	C5	elleve	77	7C	7A	78	36	1C	39	59	atten	56
E	B3	B0	24	tyve	B2	92	A3	C0	44	62	ti	B4	84	43	93	C2
F	4A	BD	8F	2D	f.Kr	9C	6A	40	CF	A2	80	4F	1F	CA	AA	42

Det er let at se på tabellerne, at både i den originale version og i den modificerede er S-bokse involutionale, dvs. $S(S(x))=x$

Sikkerhed

KHAZAD antages at være så sikker som en blokcifre med den givne blok- og nøglelængde kan være.

Dette omfatter blandt andet følgende:

Det mest effektive angreb til at finde nøglen til KHAZAD-chifferet er brute force.
ved at hente fra disse par klartekst - chiffertekst kan information om andre sådanne par ikke udføres mere effektivt end at finde nøglen ved en udtømmende søgning.
den forventede kompleksitet ved at søge efter en nøgle med brute force afhænger af bitlængden af nøglen og er lig med KHAZAD-cifret. $2^{127}$

En så stor sikkerhedsmargin var inkluderet i chifferen under hensyntagen til alle kendte angreb. [en]

Der er kun angreb på en afkortet version af chifferen med 5 runder (Frédéric Muller, 2003). [7]

Som du kan se, blev der ikke fundet alvorlige problemer med den kryptografiske styrke af Khazad-algoritmen, hvilket også blev bemærket af eksperterne fra NESSIE-konkurrencen. Derudover bemærkede eksperter en meget høj krypteringshastighed af denne algoritme. Khazad blev anerkendt som en lovende algoritme, meget interessant for yderligere undersøgelse, men blev ikke en af vinderne af konkurrencen på grund af eksperters mistanke om, at strukturen af algoritmen kan indeholde skjulte sårbarheder, som kan blive opdaget i fremtiden.

— Panasenko S. P. "Krypteringsalgoritmer. Særlig opslagsbog" [2]

Tilgængelighed

KHAZAD-chifferet er ikke blevet (og vil aldrig blive) patenteret. Det kan bruges gratis til ethvert formål. [en]

Originaltekst (engelsk)[ Visskjule] KHAZAD er ikke (og vil aldrig blive) patenteret. Den kan bruges gratis til ethvert formål. [en]

Titel

Chifferen er opkaldt efter Khazad-dûm eller Moria , dværgenes enorme underjordiske rige i Midgårds tågede bjerge fra J. R. R. Tolkiens Ringenes Herre-trilogi. [en]

Se også

Noter

↑ 1 2 3 4 5 6 7 8 Paulo Sérgio LM Barreto, Vincent Rijmen. Khazad Block Cipher (utilgængeligt link) . www.larc.usp.br. Hentet 30. november 2016. Arkiveret fra originalen 1. december 2016. (ubestemt)
↑ 1 2 3 4 Panasenko S.P. Krypteringsalgoritmer. Særlig guide .. - St. Petersborg. : BHV-Petersburg, 2009. - S. 282-287. — 576 s. — ISBN 978-5-9775-0319-8 .
↑ 1 2 Lars R. Knudsen, Matthew JB Robshaw. The Block Cipher Companion . - Springer, 2011. - S. 63 . — 267 s. - ISBN 978-3-642-17341-7 .
↑ Joan Daernen, Vincent Rijrnen. Designet af Rijndael. - Springer, 2002. - S. 160. - 238 s. — ISBN 3-540-42580-2 .
↑ 1 2 Beskrivelse af Khazad-cifferet til den første runde af NESSIE-konkurrencen . Hentet 2. december 2016. Arkiveret fra originalen 6. maj 2021. (ubestemt)
↑ Paulo SLM Barreto og Vincent Rijmen. KHAZAD Legacy-Level Block Cipher . Arkiveret fra originalen den 23. februar 2012.
↑ Frederic Muller. Et nyt angreb mod khazad // i Proceedings of ASIACRYPT 2003. — s. 347–358 . Arkiveret fra originalen den 6. marts 2016.

Litteratur

Panasenko S. P. Krypteringsalgoritmer. Særlig guide. - St. Petersborg: BHV-Petersburg, 2009. - 576 s.: ill. ISBN 978-5-9775-0319-8

Links

Officiel side af KHAZAD-chiffer
Paulo SLM Barreto og Vincent Rijmen. KHAZAD Legacy-Level Block Cipher (tweaked, KHAZAD). I First Open NESSIE Workshop, KU-Leuven, 2000. Ændret indsendelse til NESSIE udvalgt til 2. fase.
Paulo SLM Barreto og Vincent Rijmen. KHAZAD Legacy-Level Block Cipher (original, KHAZAD-0). Oprindelig indsendelse til NESSIE.
Alex Biryukov. Analyse af involutionelle chifferer: Khazad og Anubis . I T. Johansson, redaktør, Fast Software Encryption - 2003, Lectures Notes in Computer Science. Springer, 2003.
Frederic Muller. Et nyt angreb mod Khazad. Fremskridt inden for kryptologi
Liste over NESSIE-indsendelser som oprindeligt indsendt
Ændringer af NESSIE-indsendelser valgt til 2. fase
Leverancer af NESSIE-projektet
NESSIE Offentlig rapport D14: Rapport om præstationsevaluering af NESSIE-kandidater I
NESSIE Offentlig rapport D18: Opdatering om udvælgelsen af algoritmer til yderligere undersøgelse i anden runde.

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