Græshoppe (cifre)

Græshoppe
Skaber	FSB i Rusland , InfoTeKS JSC
offentliggjort	2015
Standarder	GOST 34.12-2018 , GOST R 34.12-2015 , RFC 7801
Nøglestørrelse	256 bit
Blokstørrelse	128 bit
Antal runder	ti
Type	Substitution-permutation netværk

Grasshopper ( engelsk Kuznyechik [1] eller engelsk Kuznechik [2] [3] ) er en symmetrisk blokchifferalgoritme med en blokstørrelse på 128 bit og en nøglelængde på 256 bit, som bruger et SP-netværk til at generere runde nøgler .

Generel information

Denne cipher er godkendt (sammen med Magma blok cipher ) som standard i GOST R 34.12-2015 “Informationsteknologi. Kryptografisk beskyttelse af information. Blokcifre" efter kendelse af 19. juni 2015 nr. 749-st [4] . Standarden trådte i kraft den 1. januar 2016 [5] . Chifferen blev udviklet af Center for Information Protection and Special Communications af Federal Security Service of Russia med deltagelse af Information Technologies and Communication Systems JSC ( InfoTeKS JSC ). Indført af den tekniske komité for standardisering TC 26 "Kryptografisk beskyttelse af information" [6] [7] .

Protokol nr. 54 dateret 29. november 2018 , baseret på GOST R 34.12-2015 , vedtog Interstate Council for Metrology, Standardization and Certification den mellemstatslige standard GOST 34.12-2018 . Efter ordre fra det føderale agentur for teknisk regulering og metrologi af 4. december 2018 nr. 1061-st blev GOST 34.12-2018- standarden sat i kraft som den nationale standard for Den Russiske Føderation fra 1. juni 2019 .

Notation

$\mathbb {F}$ er Galois-feltet modulo det irreducible polynomium . $GF(2^{8})$ $x^{8}+x^{7}+x^{6}+x+1$

$Bin_{8}:\mathbb {Z} _{p}\rightarrow V_{8}$ er en bijektiv mapping, der forbinder et element i ringen ( ) med dens binære repræsentation. $\mathbb {Z} _{p}$ $p=2^{8}$

${Bin_{8}}^{-1}:V_{8}\rightarrow \mathbb {Z} _{p}$ er en visning omvendt til . $Bin_{8}$

$\delta :V_{8}\rightarrow \mathbb {F}$ er en bijektiv mapping, der forbinder en binær streng med et element i feltet . $\mathbb {F}$

$\delta ^{-1}:\mathbb {F} \rightarrow V_{8}$ - display omvendt til $\delta$

Beskrivelse af algoritmen

Følgende funktioner bruges til at kryptere, dekryptere og generere en nøgle:

$Tilføj_{2}[k](a)=k\plus a$ , hvor , er binære strenge af formen … ( er strengsammenkædningssymbolet ). $k$ $-en$ $a=a_{{15}}||$ $||a_{{0}}$ $||$

$N(a)=S(a_{15})||$ ... er det omvendte af transformationen. $||S(a_{0}).~~N^{-1}(a)$ $N(a)$

$G(a)=\gamma (a_{15},$ … … $,a_{0})||a_{15}||$ $||a_{{1}}.$

$G^{{-1}}(a)$ - det omvendte til transformationen, og ... ... $G(a)$ $G^{{-1}}(a)=a_{{14}}||a_{{13}}||$ $||a_{0}||\gamma (a_{14},a_{13},$ $,a_{0},a_{15}).$

$H(a)=G^{{16}}(a)$ , hvor er sammensætningen af transformationer mv . $G^{{16}}$ $G^{{15}}$ $G$

$F[k](a_{1},a_{0})=(HNAtilføj_{2}[k](a_{1})\plus a_{0},a_{1}).$

Ikke-lineær transformation

Den ikke-lineære transformation er givet ved substitutionen S = Bin 8 S' Bin 8 −1 .

Substitutionsværdierne S' er givet som et array S' = (S'(0), S'(1), …, S'(255)) :

$S'=(252,238,221,17,207,110,49,22,251,196,250,218,35,197,4,77,233,$ $119,240,219,147,46,153,186,23,54,241,187,20,205,95,193,249,24,101,$ $90,226,92,239,33,129,28,60,66,139,1,142,79,5,132,2,174,227,106,143,$ $160,6,11,237,152,127,212,211,31,235,52,44,81,234,200,72,171,242,42,$ $104,162,253,58,206,204,181,112,14,86,8,12,118,18,191,114,19,71,156,$ $183,93,135,21,161,150,41,16,123,154,199,243,145,120,111,157,158,178,$ $177,50,117,25,61,255,53,138,126,109,84,198,128,195,189,13,87,223,$ $245,36,169,62,168,67,201,215,121,214,246,124,34,185,3,224,15,236,$ $222,122,148,176,188,220,232,40,80,78,51,10,74,167,151,96,115,30,0,$ $98,68,26,184,56,130,100,159,38,65,173,69,70,146,39,94,85,47,140,163,$ $165,125,105,213,149,59,7,88,179,64,134,172,29,247,48,55,107,228,136,$ $217,231,137,225,27,131,73,76,63,248,254,141,83,170,144,202,216,133,$ $97,32,113,103,164,45,43,9,91,203,155,37,208,190,229,108,82,89,166,$ $116,210,230,244,180,192,209,102,175,194,57,75,99,182).$

Lineær transformation

Indstillet efter display : $\gamma$

$\gamma (a_{15},$ … $,a_{0})=\delta ^{-1}~(148*\delta (a_{15})+32*\delta (a_{14})+133*\delta (a_{13})+16 *\delta(a_{12})+$ $194*\delta (a_{11})+192*\delta (a_{10})+1*\delta (a_{9})+251*\delta (a_{8})+1*\delta (a_ {7})+192*\delta (a_{6})+$ $194*\delta (a_{5})+16*\delta (a_{4})+133*\delta (a_{3})+32*\delta (a_{2})+148*\delta (a_{3}) {1})+1*\delta (a_{0})),$

hvor operationerne med addition og multiplikation udføres i marken . $\mathbb {F}$

Nøglegenerering

Nøglegenereringsalgoritmen bruger iterative konstanter , i=1,2,...32. Den delte nøgle er indstillet ... . $C_{i}=H(Bin_{128}(i))$ $K=k_{255}||$ $||k_{0}$

Iterationsnøgler beregnes

$K_{1}=k_{255}||$ … $||k_{128}$

$K_{2}=k_{127}||$ … $||k_{0}$

$(K_{2i+1},K_{2i+2})=F[C_{8(i-1)+8}]$ … $F[C_{8(i-1)+1}](K_{2i-1},K_{2i}),i=1,2,3,4.$

Krypteringsalgoritme

$E(a)=Tilføj_{2}[K_{10}]HNAd_{2}[K_{9}]$ ... hvor a er en 128-bit streng. $HNAad_{2}[K_{2}]HNAad_{2}[K_{1}](a),$

Dekrypteringsalgoritme

$D(a)=Tilføj_{2}[K_{1}]N^{-1}H^{-1}Tilføj_{2}[K_{2}]$ … $N^{-1}H^{-1}Tilføj_{2}[K_{9}]N^{-1}H^{-1}Tilføj_{2}[K_{10}](a) .$

Eksempel [8]

Strengen "a" er angivet i hexadecimal og har en størrelse på 16 bytes, hvor hver byte er angivet med to hexadecimale tal.

Strengmappingstabel i binær og hexadecimal form:

0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	1101	1110	1111
0	en	2	3	fire	5	6	7	otte	9	-en	b	c	d	e	f

N-transform eksempel

$N(00112233445566778899aabbccddeeff)=fc7765aeeaoc9a7ee8d7387d88d86cb6$

G-transform eksempel

$G$

$G(94000000000000000000000000000000001)=a5940000000000000000000000000000000$

$G(a5940000000000000000000000000000000)=64a594000000000000000000000000000$

$G(64a5940000000000000000000000000000)=0d64a59400000000000000000000000000$

H-transform eksempel

$H(64a59400000000000000000000000000)=d456584dd0e3e84cc3166e4b7fa2890d$

Eksempel på nøglegenerering

$K=8899aabbccddeeff0011223344556677fedcba98765432100123456789abcdef.$

$K_{1}=8899aabbccddeeff0011223344556677,$

$K_{2}=fedcba98765432100123456789abcdef.$

$C_{1}=6ea276726c487ab85d27bd10dd849401,$

$Tilføj_{2}[C_{1}](K_{1})=e63bdcc9a09594475d369f2399d1f276,$

$NAd_{2}[C_{1}[(K_{1})=0998ca37a7947aabb78f4a5ae81b748a,$

$HNAd_{2}[C_{1}](K_{1})=3d0940999db75d6a9257071d5e6144a6,$

$F[C_{1}](K_{1},K_{2})=(HNAd_{2}[C_{1}](K_{1})\plus K_{2},K_{1})=( c3d5fa01ebe36f7a9374427ad7ca8949,8899aabbccddeeff0011223344556677).$

$C_{2}=dc87ece4d890f4b3ba4eb92079cbeb02,$

$F[C_{2}]F[C_{1}](K_{1},K_{2})=(37777748e56453377d5e262d90903f87,c3d5fa01ebe36f7a9374427ad7ca8949).$

$C_{3}=b2259a96b4d88e0be7690430a44f7f03,$

$F[C_{3}]F[C_{2}]F[C_{1}](K_{1},K_{2})=(f9eae5f29b2815e31f11ac5d9c29fb01,37777748e56453377d5e20632d807).$

$C_{4}=7bcd1b0b73e32ba5b79cb140f2551504,$

$F[C_{4}]F[C_{3}]F[C_{2}]F[C_{1}](K_{1},K_{2})=(e980089683d00d4be37dd3434699b98f,f9eae5f29b2819acf301c).$

$C_{5}=156f6d791fab511deabb0c502fd18105,$

$F[C_{5}]F[C_{4}]F[C_{3}]F[C_{2}]F[C_{1}](K_{1},K_{2})=(b7bd70acea4460714f4ebe13835cf004, e980089683d00d4be37dd3434699b98f).$

$C_{6}=a74af7efab73df160dd208608b9efe06,$

$F[C_{6}]F[C_{5}]F[C_{4}]F[C_{3}]F[C_{2}]F[C_{1}](K_{1},K_{ 2})=(1a46ea1cf6ccd236467287df93fdf974,b7bd70acea4460714f4ebe13835cf004).$

$C_{7}=c9e8819dc73ba5ae50f5b570561a6a07,$

$F[C_{7}]F[C_{6}]F[C_{5}]F[C_{4}]F[C_{3}]F[C_{2}]F[C_{1}]( K_{1},K_{2})=(3d4553d8e9cfec6815ebadc40a9ffd04,1a46ea1cf6ccd236467287df93fdf974).$

$C_{8}=f6593616e6055689adfba18027aa2a08,$

$(K_{3},K_{4})=F[C_{8}]F[C_{7}]$ … $F[C_{2}]F[C_{1}](K_{1},K_{2})=(db31485315694343228d6aef8cc78c44,3d4553d8e9cfec6815ebadc40a9ffd04).$

Som et resultat får vi iterative nøgler:

$K_{1}=8899aabbccddeeff0011223344556677,$

$K_{2}=fedcba98765432100123456789abcdef,$

$K_{3}=db31485315694343228d6aef8cc78c44,$

$K_{4}=3d4553d8e9cfec6815ebadc40a9ffd04,$

$K_{5}=57646468c44a5e28d3e59246f429f1ac,$

$K_{6}=bd079435165c6432b532e82834da581b,$

$K_{7}=51e640757e8745de705727265a0098b1,$

$K_{8}=5a7925017b9fdd3ed72a91a22286f984,$

$K_{9}=bb44e25378c73123a5f32f73cdb6e517,$

$K_{10}=72e9dd7416bcf45b755dbaa88e4a4043.$

Et eksempel på en krypteringsalgoritme

simpel tekst $a=1122334455667700ffeeddccbbaa9988,$

Sikkerhed

Den nye blokchiffer "Grasshopper" forventes at være modstandsdygtig over for alle former for angreb på blokcifre .

På CRYPTO 2015-konferencen præsenterede Alex Biryukov, Leo Perrin og Alexey Udovenko en rapport, der anførte, at på trods af udviklernes påstande, er værdierne af S-blokken af Grasshopper-chifferet og Stribog-hash-funktionen ikke (pseudo) tilfældige tal , men er genereret baseret på en skjult algoritme, som de formåede at gendanne ved hjælp af reverse engineering metoder [9] . Senere udgav Leo Perrin og Aleksey Udovenko to alternative algoritmer til generering af S-boksen og beviste dens forbindelse med S-boksen i den hviderussiske BelT -chiffer [10] . I denne undersøgelse hævder forfatterne også, at selvom årsagerne til at bruge en sådan struktur forbliver uklare, er brugen af skjulte algoritmer til at generere S-bokse i modstrid med princippet om "ingen trick i hullet" , hvilket kunne tjene som bevis på fraværet af bevidst indlejrede sårbarheder i designet af algoritmen.

Riham AlTawy og Amr M. Youssef beskrev et møde i midterangrebet i 5 runder af Grasshopper-chifferet, som har en beregningsmæssig kompleksitet på 2140 og kræver 2153 hukommelse og 2113 data [11] .

Noter

↑ Ifølge GOST R 34.12-2015 og RFC 7801 kan chifferen omtales på engelsk som Kuznyechik
↑ Ifølge GOST 34.12-2018 kan chifferen omtales på engelsk som Kuznechik .
↑ Nogle softwareimplementeringer af open source -chifferet bruger navnet Grasshopper
↑ "GOST R 34.12-2015" (utilgængeligt link) . Hentet 4. september 2015. Arkiveret fra originalen 24. september 2015. (ubestemt)
↑ "Om introduktionen af nye kryptografiske standarder" . Hentet 4. september 2015. Arkiveret fra originalen 27. september 2016. (ubestemt)
↑ "www.tc26.ru" . Dato for adgang: 14. december 2014. Arkiveret fra originalen 18. december 2014. (ubestemt)
↑ Arkiveret kopi (link ikke tilgængeligt) . Hentet 13. april 2016. Arkiveret fra originalen 24. april 2016. (ubestemt)
↑ http://www.tc26.ru/standard/draft/GOSTR-bsh.pdf Arkiveret 26. december 2014 på Wayback Machine se Test Cases
↑ Alex Biryukov, Leo Perrin, Aleksei Udovenko. Reverse-engineering af S-Box af Streebog, Kuznyechik og STRIBOBr1 (fuld version) (8. maj 2016). Hentet 21. maj 2021. Arkiveret fra originalen 4. marts 2021. (ubestemt)
↑ Leo Perrin, Aleksei Udovenko. Eksponentielle S-bokse: en forbindelse mellem S-bokse i BelT og Kuznyechik/Streebog (3. februar 2017). Hentet 14. september 2017. Arkiveret fra originalen 17. april 2021. (ubestemt)
↑ Riham AlTawy og Amr M. Youssef. Et møde i midten angreb på den reducerede runde Kuznyechik (17. april 2015). Hentet 8. juni 2016. Arkiveret fra originalen 16. juli 2017. (ubestemt)

Links

GOST R 34.12-2015 “Informationsteknologi. Kryptografisk beskyttelse af information. Blokcifre»
GOST 34.12-2018 “Informationsteknologi. Kryptografisk beskyttelse af information. Blokcifre»
I GOST sad "Grasshopper"

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