Gräshoppa (chiffer)

gräshoppa
Skapare	Rysslands FSB , InfoTeKS JSC
publiceras	2015
Standarder	GOST 34.12-2018 , GOST R 34.12-2015 , RFC 7801
Nyckelstorlek	256 bitar
Block storlek	128 bitar
Antal omgångar	tio
Sorts	Substitution-permutationsnätverk

Grasshopper ( engelska Kuznyechik [1] eller engelska Kuznechik [2] [3] ) är en symmetrisk blockchifferalgoritm med en blockstorlek på 128 bitar och en nyckellängd på 256 bitar, som använder ett SP-nätverk för att generera runda nycklar .

Allmän information

Detta chiffer är godkänt (tillsammans med Magma-blockchifferet ) som standard i GOST R 34.12-2015 "Informationsteknologi. Kryptografiskt skydd av information. Blockchiffer" genom order av den 19 juni 2015 nr 749-st [4] . Standarden trädde i kraft den 1 januari 2016 [5] . Chifferet utvecklades av Center for Information Protection and Special Communications av Federal Security Service of Russia med deltagande av Information Technologies and Communication Systems JSC ( InfoTeKS JSC ). Infört av den tekniska kommittén för standardisering TC 26 "Kryptografiskt skydd av information" [6] [7] .

Protokoll nr 54 daterat den 29 november 2018 , baserat på GOST R 34.12-2015 , antog Interstate Council for Metrology, Standardization and Certification den mellanstatliga standarden GOST 34.12-2018 . Genom order från Federal Agency for Technical Regulation and Metrology daterad 4 december 2018 nr 1061-st, sattes GOST 34.12-2018- standarden i kraft som den nationella standarden för Ryska federationen från 1 juni 2019 .

Notation

$\mathbb {F}$ är Galois-fältet modulo det irreducerbara polynomet . $GF(2^{8})$ $x^{8}+x^{7}+x^{6}+x+1$

$Bin_{8}:\mathbb {Z} _{p}\rightarrow V_{8}$ är en bijektiv mappning som associerar ett element i ringen ( ) med dess binära representation. $\mathbb {Z} _{p}$ $p=2^{8}$

${Bin_{8}}^{-1}:V_{8}\rightarrow \mathbb {Z} _{p}$ är en visning omvänd till . $Bin_{8}$

$\delta :V_{8}\rightarrow \mathbb {F}$ är en bijektiv mappning som associerar en binär sträng med ett element i fältet . $\mathbb {F}$

$\delta ^{-1}:\mathbb {F} \rightarrow V_{8}$ - visa inverterad till $\delta$

Beskrivning av algoritmen

Följande funktioner används för att kryptera, dekryptera och generera en nyckel:

$Add_{2}[k](a)=k\oplus a$ , där , är binära strängar av formen … ( är strängsammansättningssymbolen ) . $k$ $a$ $a=a_{{15}}||$ $||a_{{0}}$ $||$

$N(a)=S(a_{15})||$ ... är det omvända till omvandlingen. $||S(a_{0}).~~N^{-1}(a)$ $N(a)$

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

$G^{{-1}}(a)$ - det omvända till omvandlingen, och ... ... $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)$ , var är sammansättningen av transformationer osv . $G^{{16}}$ $G^{{15}}$ $G$

$F[k](a_{1},a_{0})=(HNAdd_{2}[k](a_{1})\oplus a_{0},a_{1}).$

Icke-linjär transformation

Den olinjära transformationen ges av substitutionen S = Bin 8 S' Bin 8 −1 .

Substitutionsvärdena S' ges som en 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).$

Linjär transformation

Ställ in 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_ {1})+1*\delta (a_{0})),$

där operationerna addition och multiplikation utförs i fält . $\mathbb {F}$

Nyckelgenerering

Nyckelgenereringsalgoritmen använder iterativa konstanter , i=1,2,...32. Den delade nyckeln är inställd ... . $C_{i}=H(Bin_{128}(i))$ $K=k_{255}||$ $||k_{0}$

Iterationsnycklar beräknas

$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.$

Krypteringsalgoritm

$E(a)=Lägg till_{2}[K_{10}]HNAd_{2}[K_{9}]$ ... där a är en 128-bitars sträng. $HNAdd_{2}[K_{2}]HNAdd_{2}[K_{1}](a),$

Dekrypteringsalgoritm

$D(a)=Lägg till_{2}[K_{1}]N^{-1}H^{-1}Lägg till_{2}[K_{2}]$ … $N^{-1}H^{-1}Lägg till_{2}[K_{9}]N^{-1}H^{-1}Lägg till_{2}[K_{10}](a) .$

Exempel [8]

Strängen "a" anges i hexadecimal och har en storlek på 16 byte, med varje byte specificerad av två hexadecimala tal.

Strängmappningstabell i binär och hexadecimal form:

0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	1101	1110	1111
0	ett	2	3	fyra	5	6	7	åtta	9	a	b	c	d	e	f

N-transform exempel

$N(00112233445566778899aabbccddeeff)=fc7765aeeaoc9a7ee8d7387d88d86cb6$

Exempel på G-transform

$G$

$G(94000000000000000000000000000000001)=a5940000000000000000000000000000000$

$G(a5940000000000000000000000000000000)=64a594000000000000000000000000000$

$G(64a5940000000000000000000000000000)=0d64a59400000000000000000000000000$

H-transform exempel

$H(64a59400000000000000000000000000)=d456584dd0e3e84cc3166e4b7fa2890d$

Exempel på nyckelgenerering

$K=8899aabbccddeeff0011223344556677fedcba98765432100123456789abcdef.$

$K_{1}=8899aabbccddeeff0011223344556677,$

$K_{2}=fedcba98765432100123456789abcdef.$

$C_{1}=6ea276726c487ab85d27bd10dd849401,$

$Add_{2}[C_{1}](K_{1})=e63bdcc9a09594475d369f2399d1f276,$

$NAdd_{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})\oplus 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,37777748e56453377d59e2062d80).$

$C_{4}=7bcd1b0b73e32ba5b79cb140f2551504,$

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

$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 ett resultat får vi iterativa nycklar:

$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.$

Ett exempel på en krypteringsalgoritm

oformatterad text $a=1122334455667700ffeeddccbbaa9988,$

Säkerhet

Det nya blockchifferet "Grasshopper" förväntas vara resistent mot alla typer av attacker på blockchiffer .

På CRYPTO 2015-konferensen presenterade Alex Biryukov, Leo Perrin och Alexey Udovenko en rapport som säger att trots utvecklarnas påståenden är värdena för S-blocket för Grasshopper-chifferet och Stribog-hashfunktionen inte (pseudo)slumptal. , men genereras baserat på en dold algoritm, som de lyckades återställa med omvänd ingenjörsteknik [9] . Senare publicerade Leo Perrin och Aleksey Udovenko två alternativa algoritmer för att generera S-boxen och bevisade dess koppling till S-boxen i det vitryska BelT- chifferet [10] . I denna studie hävdar författarna också att, även om skälen till att använda en sådan struktur förblir oklara, strider användningen av dolda algoritmer för att generera S-boxar mot principen "ingen trick i hålet" , vilket skulle kunna tjäna som bevis på frånvaron av medvetet inbäddade sårbarheter i utformningen av algoritmen.

Riham AlTawy och Amr M. Youssef beskrev ett möte i mittenattacken under 5 omgångar av Grasshopper-chifferet, som har en beräkningskomplexitet på 2140 och kräver 2153 minne och 2113 data [11] .

Anteckningar

↑ Enligt GOST R 34.12-2015 och RFC 7801 kan chifferet på engelska kallas Kuznyechik
↑ Enligt GOST 34.12-2018 kan chifferet på engelska kallas Kuznechik .
↑ Vissa programvaruimplementationer av chiffer med öppen källkod använder namnet Grasshopper
↑ "GOST R 34.12-2015" (otillgänglig länk) . Hämtad 4 september 2015. Arkiverad från originalet 24 september 2015. (obestämd)
↑ "Om införandet av nya kryptografiska standarder" . Hämtad 4 september 2015. Arkiverad från originalet 27 september 2016. (obestämd)
↑ "www.tc26.ru" . Datum för åtkomst: 14 december 2014. Arkiverad från originalet 18 december 2014. (obestämd)
↑ Arkiverad kopia (länk ej tillgänglig) . Hämtad 13 april 2016. Arkiverad från originalet 24 april 2016. (obestämd)
↑ http://www.tc26.ru/standard/draft/GOSTR-bsh.pdf Arkiverad 26 december 2014 på Wayback Machine se testfall
↑ Alex Biryukov, Leo Perrin, Aleksei Udovenko. Reverse-engineering the S-Box of Streebog, Kuznyechik and STRIBOBr1 (fullversion) (8 maj 2016). Hämtad 21 maj 2021. Arkiverad från originalet 4 mars 2021. (obestämd)
↑ Leo Perrin, Aleksei Udovenko. Exponentiella S-boxar: en länk mellan S-boxarna i BelT och Kuznyechik/Streebog (3 februari 2017). Hämtad 14 september 2017. Arkiverad från originalet 17 april 2021. (obestämd)
↑ Riham AlTawy och Amr M. Youssef. A Meet in the Middle Attack på Reduced Round Kuznyechik (17 april 2015). Hämtad 8 juni 2016. Arkiverad från originalet 16 juli 2017. (obestämd)

Länkar

GOST R 34.12-2015 “Informationsteknik. Kryptografiskt skydd av information. Blockchiffer»
GOST 34.12-2018 "Informationsteknik. Kryptografiskt skydd av information. Blockchiffer»
I GOST satt "Grasshopper"

Symmetriska kryptosystem
Streama chiffer	A3 A5 A8 Decim F-FCSR Spannmål HC-256 KCipher-2 MICKEY MUGI GÄDDA Phelix RC4 Kanin TÄTA SNÖ SOSEMANUK Salsa20 STRUMOK Trivium VMPC
Feistel nätverk	GOST 28147-89 (Magma) blåsfisk Kamelia CAST-128 CAST-256 CIFERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra HANDLA DES DESX DFC E2 ENRUPT FEAL HPC ANING KASUMI Khafre Khufu LOKI97 MacGuffin MARS MASKA DIMMIG1 Ny DES NDS RC5 RC6 UTSÄDE Simon Sinople skipjack SM4 Fläck TE XTEA XXTEA Raiden RTEA Trippel DES Tvåfisk
SP nätverk	gräshoppa 3 sätt ABC ARIA AES (Rijndael) Akelarre Anubis BaseKing Bas Omatic Bälte CRYPTON Diamant2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna djävulen närvarande Regnbåge SÄKRARE HAJ FYRKANT Orm tre fiskar
Övrig	GRODA NUSH REDOC SC2000 SHACAL CS-Chiffer