HAJ

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 5. november 2019; checks kræver 3 redigeringer .

HAJ
Skaber	Vincent Rayman , Joan Dymen , Bart Presnel , Antun Bosalers og Eric de Veen
Oprettet	1996 _
offentliggjort	1996 _
Nøglestørrelse	128 bit
Blokstørrelse	64 bit
Antal runder	6 [1] (8 [2] )
Type	Substitution-permutation netværk

SHARK ( Eng. Secure Hash Algorithm Regenerative Keys - en sikker hashing-algoritme med genskabte nøgler) er en symmetrisk blokchifferalgoritme udviklet af en gruppe kryptografer, herunder Vincent Rayman , forfatteren af AES -chifferet . I teorien tillader det brugen af blokke og nøgler af forskellig længde, men forfatterens implementering bruger en 128-bit nøgle og 64-bit blokke. Strukturen ligner den for et permutationsnetværk .

SHARK's historie

SHARK -chifferen er den første i en række af algoritmer udviklet som en del af en undersøgelse for at skabe sikre og effektive blokcifre baseret på Wide Trail-designstrategien [3] . Resultatet af forskningen var senere oprettelsen af standardchifferet AES [2] .

Forfatterne placerede SHARK som en algoritme designet til at erstatte den dengang udbredte DES -chiffer . Følgende krav blev præsenteret for den nye algoritme:

høj ydeevne - et lille antal runder. Til sammenligning brugte DES-chifferet 16 runder. Ifølge forfatteren formåede de at opnå mere end fire gange hurtigere hastighed sammenlignet med SAFER og IDEA -cifrene ;
usårbarhed over for lineær og differentiel kryptoanalyse, som DES var sårbar overfor [1] .

Selvom SP-net- baserede cifre ( MMB, SAFER , 3-Way ) allerede eksisterede før , var SHARK den første til at bruge MDS-koder [4] til lineær transformation, nemlig Reed-Solomon-koder [1] .

Der er to versioner af SHARK-chifferet : SHARK-A ( eng. affine transform ) og SHARK-E ( eng. exor ), opkaldt efter de forskellige måder at introducere runde nøgler på [5] .

Algoritmedesign

SHARK- algoritmen består af tre komponenter:

ikke-lineært lag baseret på S-bokse ;
diffusionslag baseret på MDS-koder [4] ;
nøgleskema til udledning af rundnøgler fra kildenøgle [1] .

Hver komponent i algoritmen betragtes separat, og hver komponent skal have bestemte egenskaber. Diffusionslaget bør således have ensartede og gode diffusionsegenskaber. Det ikke-lineære lag skal også have ensartede ikke-lineære egenskaber, og komponenterne i algoritmen er uafhængige i følgende forstand: hvis implementeringen af f.eks. det ikke-lineære lag ændres (nogle S-bokse erstattes af andre S-bokse med samme egenskaber), forbliver sikkerheden af algoritmen uændret. En sådan strategi er en variant af Wide trail-strategien [3] beskrevet i Joan Dymens doktorafhandling [1] .

SHARK består af runder, et ekstra nøgletilsætningslag og et ekstra omvendt diffusionslag. Hver runde består igen af at tilføje en nøgle, en ikke-lineær erstatning og et diffusionslag. Et ekstra lag med at tilføje en nøgle er nødvendig for at forhindre en angriber i at adskille den sidste runde. Et ekstra lag af inverteret diffusion er nødvendigt for at forenkle dekrypteringsoperationen [1] . $R$

Det ikke-lineære substitutionslag består af S-bokse, som hver er en -bit-permutation. Algoritmen er således i stand til at kryptere blokke af længde [1] . $n$ $m$ $m\cdot n$

Diffusionslag

Diffusionslaget modtager -bit-numre, der kan betragtes som elementer over feltet . Det pågældende lag er nødvendigt for at skabe en lavineeffekt . Denne effekt manifesterer sig i lineære og forskellige sammenhænge: $n$ $m$ $GF(2^{m})$

Lineær kontekst - Der er ingen sammenhæng mellem en lineær kombination af et lille sæt -bit input og en lineær kombination af et lille sæt ( -bit) output. $m$ $m$
Differentiel kontekst - en lille ændring i inputdataene medfører en væsentlig ændring i outputdataene, og omvendt, for en lille ændring i outputdataene skal du ændre inputdataene væsentligt [1] .

Lad være en reversibel lineær transformation , være et element i feltet , være Hamming-afstanden , så kvantitativt estimeres lavineeffekten af springtallet ( eng. grennummer ) [1] . $\theta$ $-en$ $GF(2^{m})$ $w_{h}(a)$ $B(\theta )={\overset {}{\underset {a\neq 0}{min}}}({\displaystyle w_{h}(a)}+{\displaystyle w_{h}(\ theta(a))})$

Hvis , så . kaldes det optimale springtal ( eng. optimalt grennummer ). I hovedartiklen viste forfatterne, at ved hjælp af MDS-koder er det muligt at konstruere en reversibel lineær transformation med et optimalt springtal. Implementeringen bruger Reed-Solomon-koder [1] . $w_{h}(a)=1$ $B\leq n+1$ $B=n+1$ $(2n,n,n+1)$

Ikke-lineært lag (substitutionsblokke)

Ikke-lineære S-bokse giver beskyttelse mod lineær og differentiel kryptoanalyse. En af de vigtige numeriske egenskaber ved sikkerheden af chifferen er matrixen af eksklusive OR ( engelsk exor table ) mappings , hvis elementer er bestemt af formlen , hvor - angiver antallet af elementer, der opfylder betingelsen, - elementerne af feltet . Store værdier af matrixelementer kan føre til chifferens modtagelighed for differentielt angreb [1] . $E$ $\gamma$ $E_{ij}=\sharp (x|\gamma (x)\oplus \gamma (i\oplus x)=j)$ $\skarp$ $x,i,j$ $GF(2^{m})$

Forfatterne valgte S-bokse ud fra kortlægningen over feltet . I dette tilfælde, når lige, har matrixen følgende egenskaber: ${\displaystyle F(x)=x^{-1))$ $GF(2^{m})$ $m$ $E$

Differentiel 4-stabilitet - alle elementer i matrixen overstiger ikke 4. Faktisk er der i hver række af en sådan matrix nøjagtigt et element lig med 4, og resten er lig med 2 eller 0.
Minimumsafstanden for en affin funktion er . $2^{m/2}$
Den ikke-lineære rækkefølge af enhver lineær kombination af outputbit er [1] . $m+1$

For at fjerne fikspunkterne og , bruges en inverterbar affin transformation af outputbittene [1] . $0\rightarrow 0$ $1\rightarrow 1$

Nøgleskema

Nøgleplanlægning giver dig mulighed for at udvide den originale nøgle ved at få runde nøgler . God planlægning giver dig mulighed for at få runde nøgler med maksimal entropi. Forfatterne foreslår to måder at indtaste den runde nøgle på: $K$ $R+1$ $K_{i}$

Exor er en simpel XOR med input i hver runde. Den tilsvarende algoritme er SHARK-E.
Affin transformation er en affin transformation af inputdata, der afhænger af nøglen. Den tilsvarende algoritme er SHARK-A [1] .

Exor

En simpel XOR af input-bits af runden og undernøglen beregnes. Fordelene ved metoden er hastighed og stabilitet: ingen nøgle er stærkere eller svagere end en anden. Ulempen ved metoden er, at den runde nøgles entropi ikke overstiger [1] . $m\cdot n$ $m\cdot n$ $m\cdot n$

Affin transformation

Lad være en ikke-singular matrix over feltet , afhængigt af nøglen (mere præcist, på dens forlængelse). Lad os introducere en nøgleoperation på inputdataene som følger: . Dette er en lineær operation, så den introducerer ikke svage taster. Derudover øges entropien af de runde nøgler til . Denne operation er dog ret dyr med hensyn til ydeevne, så forfatterne foreslår at begrænse underrummet af diagonale matricer . I dette tilfælde bliver entropien af de runde nøgler tæt på [1] . $k_i$ $n\ gange n$ $GF(2^{m})$ $K$ ${\displaystyle Y(X)=k_{i}\cdot X\oplus K_{i))$ $O(mn^{2})$ $k_i$ $2 min$

Generering af undernøgler

I SHARK- algoritmen genereres rundnøgler som følger:

$R+1$ runde -bit nøgler initialiseres med de første poster i substitutionstabellen . $m\cdot n$ $K_{i}$ $R+1$
Matricer initialiseres med identitetsmatricer . $k_i$
Den brugervalgte nøgle er sammenkædet med sig selv, indtil den er lidt lang. $2(R+1)mn$
SHARK -algoritmen anvendes på sekvensen opnået i trin 3 i CFB -tilstand .
De første bits af outputtet bruges til at danne de runde nøgler . $(R+1)mn$ $K_{i}$
De sidste bits af outputdata fortolkes som elementer i feltet og danner de diagonale elementer i matricerne . Hvis et element er lig med nul, så kasseres det, og alle efterfølgende elementer flyttes ned med én. Yderligere krypterede nul-strenge tilføjes i slutningen for at udfylde de resterende diagonale elementer [1] . $(R+1)mn$ $(R+1)n$ $GF(2^{m})$ $k_i$

Undernøglegenereringsmekanismen tillader i princippet brugen af en bitlængdenøgle, men forfatterne anbefaler at bruge en nøgle, der ikke overstiger 128 bit [1] . $2(R+1)mn$

Implementeringsnoter

Udskiftningstabeller

For at opnå høj ydeevne kombineres diffusionslaget og substitutionsblokkene i én operation [1] . Lad betegne rundens inputdata; - output; — permutationsmatricer (S-bokse); er matrixen, der definerer diffusionslaget; og - betegne addition og multiplikation over feltet . Derefter $X_{1},...,X_{n}$ ${\displaystyle Y_{1},...,Y_{n))$ $S_{1},...,S_{n}$ $EN$ $\plus$ $\cdot$ $GF(2^n)$

${\begin{pmatrix}Y_{1}\\...\\Y_{n}\end{pmatrix}}=A\cdot {\begin{pmatrix}S_{1}[X_{1}] \\...\\S_{n}[X_{n}]\end{pmatrix}}={\begin{pmatrix}a_{11}\\...\\a_{n1}\end{pmatrix} }\cdot S_{1}[X_{1}]\oplus ...\oplus {\begin{pmatrix}a_{1n}\\...\\a_{nn}\end{pmatrix}}\cdot S_ {n}[X_{n}]={\begin{pmatrix}a_{11}\cdot S_{1}[X_{1}]\\...\\a_{n1}\cdot S_{1}[ X_{1}]\end{pmatrix}}\oplus ...\oplus {\begin{pmatrix}a_{1n}\cdot S_{n}[X_{n}]\\...\\a_{nn }\cdot S_{n}[X_{n}]\end{pmatrix}}$

Ved at bruge udvidede substitutionstabeller af dimension , bestemt af formlen , kan vi skrive transformationen på en simpel form: $T_{i}$ $m\times mn$ $T_{i}[X]={\begin{pmatrix}a_{1i}\cdot S_{i}[X_{i}]\\...\\a_{ni}\cdot S_{i} [X_{i}]\end{pmatrix}}$ ${\begin{pmatrix}Y_{1}\\...\\Y_{n}\end{pmatrix}}=T_{1}[X_{1}]\oplus T_{2}[X_{ 2}]\oplus ...\oplus T_{n}[X_{n}]$

En runde kræver således tabelopslag og binære operationer. Men på grund af det faktum, at tabellens bits optager en byte for bloklængden, viste algoritmen for blokke med en længde på 128 bit eller mere sig at være ineffektiv for de fleste processorer på den tid (1996), derfor den eksisterende begrænsning på bloklængden på 64 bit ( ) [2] . $n$ $n-1$ $8n$ $n^{2}\times 256$ $n=8,m=8$

MDS-kodematrix

For kan man konstruere en matrix, der definerer diffusionslaget ud fra Reed-Solomon-koden [2] . $n=8$

$A={\begin{pmatrix}CE&E7&B9&D0&52&87&74&0B\\95&FE&DA&9D&A9&28&51&31\\57&05&4D&26&07&3A&15&7F\\82&D2&D1&2C&6C&5A&CF&86\\8A&52&9E&5D&B9&F4&09&BE\\19&C1&17&9F&8F&33&A4&05\\B0&88&83&6D&70&0B&62&83\\01&F1&86&75&17&6C&09&34\end{pmatrix}}$

Dekryptering

For at beskrive dekryptering, overvej 2-runde versionen af SHARK [1] . Lad være en lineær operation, vær en ikke-lineær erstatning, og vær en nøgleadditionsoperation for den runde nøgle . Krypteringsfunktionen er i dette tilfælde lig med , hvor er operationen kombineret fra diffusionslaget og S-bokse. Da tilføjelsestastoperationen og diffusionsoperationen er lineære operationer, kan deres rækkefølge vendes [1] : $l$ $s$ $a_{k_{i))$ $k_i$ $Y=(l^{-1}\circ a_{k_{3}}\circ l\circ s\circ a_{k_{2}}\circ \underbrace {l\circ s} _{r} \circ a_{k_{1}})(X)$ $r$

$(l\circ a_{k})(X)=A\cdot (k\cdot X\oplus K)=(A\cdot k\cdot X)\oplus (A\cdot K)=((A \cdot k\cdot A^{-1})\cdot (A\cdot X))\oplus (A\cdot K)=(a_{k'}\circ l)(X)$ ,

hvor notationen $a_{k'}(X)=k'\cdot X\oplus K'=(A\cdot k\cdot A^{-1})\cdot X\oplus (A\cdot K)$

Vi anvender den resulterende formel til [1] : $l^{-1}\circ a_{k_{3))$

$Y=(a_{k_{3}'}\circ l^{-1}\circ l\circ s\circ a_{k_{2}}\circ r\circ a_{k_{1}}) (X)=(a_{k_{3}'}\circ s\circ a_{k_{2}}\circ r\circ a_{k_{1}})(X)$

Lad os nu vise, at dekrypteringsoperationen har samme struktur. For at gøre dette skal du først vende krypteringsoperationen [1] :

$X=(a_{k_{1}^{-1}}\circ s^{-1}\circ l^{-1}\circ a_{k_{2}^{-1}}\circ s^{-1}\circ l^{-1}\circ a_{k_{3}^{-1}}\circ l)(Y)$

Ved at bytte nøgleadditionsoperationen og diffusionsoperationen får vi den samme struktur som i krypteringsoperationen [1] :

$X=(a_{k_{1}^{-1}}\circ s^{-1}\circ a_{k_{2}^{-1'}}\circ \underbrace {l^{- 1}\circ s^{-1}} _{r'}\circ a_{k_{3}^{-1'}})(Y)$

Bemærkelsesværdige angreb

I øjeblikket er der ikke fundet nogen sårbarheder i den klassiske implementering af algoritmen. Der er kun angreb på variationer af algoritmen:

I 1997 viste Thomas Jacobsen og Lars Knudsen , at en 64-bit implementering af SHARK-E ( SHARK med en exor round key injection strategi) er teoretisk sårbar over for et interpolationsangreb, når den er begrænset til 5 runder, samt en 128 -bit implementering - begrænset til 8 runder. Men de viste også, at der skal mindst 6 runder til for tilstrækkelig sikkerhed [6] .
I 2013 viste Yang Shi og Hongfei Fan , at White-Box-implementeringen [ 7] af SHARK ikke er sikker nok og kan knækkes med en arbejdsfaktor på cirka 1,5*(2^47) [8] .

Noter

↑ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 Vincent Raymen , Joan Dymen , Bart Presnel , Antun Bosalers, Eric de Vin. Cipher SHARK : PDF .
↑ 1 2 3 4 Vincent Raymen , Joan Dymen . Rijndaels design : PDF . - S. 161-165 .
↑ 1 2 Joan Dymen . Cipher- og Hash-funktionsdesignstrategier baseret på lineær og differentiel kryptoanalyse : PDF . Arkiveret fra originalen den 16. maj 2018.
↑ 1 2 MDS-koder - koder med den største kodeafstand
↑ Scans indlæg for Shark . Hentet 16. december 2017. Arkiveret fra originalen 28. januar 2012. (ubestemt)
↑ Thomas Jacobsen , Lars Knudsen . Interpolationsangrebet på blokchiffere . Springer International Publishing AG (17. maj 2006). Hentet 9. februar 2018. Arkiveret fra originalen 14. december 2017. (ubestemt)
↑ White-box-angrebskontekst - angriberen har fuld adgang til softwareimplementeringen af chifferen.
↑ Yang Shi, Hongfei Fan. Om sikkerhed for en White-Box-implementering af SHARK . Hentet 14. december 2017. Arkiveret fra originalen 14. december 2017. (ubestemt)

Litteratur

Vincent Rijmen, Joan Daemen, Bart Preneel, Antoon Bosselaers, Erik De Win The Cipher SHARK. — Chifferen SHARK Arkiveret 14. december 2017 på Wayback Machine .
Joan Daemen, Vincent Rijmen Rijndaels design. — The Design of Rijndael Arkiveret 14. december 2017 på Wayback Machine .
Thomas Jakobsen, Lars R. Knudsen Interpolationsangrebet på blokcifre. — Interpolationsangrebet på blokcifre Arkiveret 14. december 2017 på Wayback Machine .
Yang Shi, Hongfei-fan om sikkerheden ved en White-Box-implementering af SHARK. — Om sikkerheden ved en White-Box-implementering af SHARK Arkiveret 14. december 2017 på Wayback Machine .
Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. Håndbog i anvendt kryptografi . - CRC Press, 1996. - S. 281. - 810 s. — ISBN 9781439821916 .

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