Kryptografinen muunnosalgoritmi GOST 28147 89:n mukaan. Kotimainen tietojen salausstandardi

Salausalgoritmi GOST 28147-89, sen käyttö ja ohjelmistototeutus Intel x86 -alustan tietokoneille.

Algoritmin kuvaus.

Termit ja nimitykset.

Venäjän federaation salausstandardin kuvaus sisältyy erittäin mielenkiintoiseen asiakirjaan, jonka otsikko on "GOST 28147-89 Cryptographic Transformation Algorithm". Se, että sen otsikossa sanan "salaus" sijaan yleisempi käsite " kryptografinen muunnos ' ei ole sattumaa. Useiden läheisesti liittyvien salaustoimenpiteiden lisäksi dokumentissa kuvataan yksi generointialgoritmi jäljitelmät lisäkkeet . Jälkimmäinen ei ole muuta kuin kryptografinen ohjausyhdistelmä, eli koodi, joka on generoitu alkuperäisestä tiedosta salaisella avaimella jäljitelmäsuojaus tai suojaa tietoja luvattomilta muutoksilta.

GOST-algoritmien eri vaiheissa dataa, jolla ne toimivat, tulkitaan ja käytetään eri tavoin. Joissakin tapauksissa tietoelementtejä käsitellään itsenäisten bittien taulukoina, toisissa etumerkittömänä kokonaislukuna, toisissa monimutkaisena rakenteena, joka koostuu useista yksinkertaisemmista elementeistä. Siksi sekaannusten välttämiseksi on tarpeen sopia käytetystä merkinnästä.

Tämän artikkelin tietoelementit on merkitty isoilla latinalaisilla kirjaimilla ja kursiivilla (esim. X). kautta | X| ilmaisee tietoelementin koon X bitteinä. Jos siis tulkitsemme tietoelementin X ei-negatiivisena kokonaislukuna voimme kirjoittaa seuraavan epäyhtälön:

Jos tietoelementti koostuu useista pienempikokoisista elementeistä, tämä tosiasia ilmoitetaan seuraavasti: X=(X 0 ,X 1 ,…,X n –1)=X 0 ||X 1 ||…||X n-yksi . Proseduuria useiden tietoelementtien yhdistämiseksi yhdeksi kutsutaan ketjuttaminen tiedot ja se on merkitty symbolilla "||". Luonnollisesti tietoelementtien koolle tulee päteä seuraava suhde: | X|=|X 0 |+|X 1 |+…+|X n-1 |. Kun määritetään monimutkaisia ​​tietoelementtejä ja ketjutusoperaatiota, osatietoelementit luetellaan nousevassa tärkeysjärjestyksessä. Toisin sanoen, jos tulkitsemme yhdistelmäelementin ja kaikki siihen sisältyvät tietoelementit etumerkittämättöminä kokonaislukuina, voimme kirjoittaa seuraavan yhtälön:

Algoritmissa tietoelementti voidaan tulkita yksittäisten bittien joukoksi, jolloin bitit merkitään samalla kirjaimella kuin taulukko, mutta pienellä kirjaimella, kuten seuraavassa esimerkissä näkyy:

X=(x 0 ,x 1 ,…,x n –1)=x 0 +2 1 x 1 +…+2 n-yksi · x n –1 .

Jos siis kiinnitit huomiota, ns. numeroiden "little-endian" numerointi, ts. monibittisissä datasanoissa yksittäiset binäärinumerot ja niiden ryhmät pienemmillä numeroilla ovat vähemmän tärkeitä. Tämä on nimenomaisesti todettu standardin kohdassa 1.3: "Kun lisätään ja syklisesti siirretään binäärivektoreita, suurimmat bitit ovat suurilukuisten akkujen bitit." Edelleen standardin 1.4, 2.1.1 ja muut kohdat määräävät, että virtuaalisen salauslaitteen tallennusrekisterit on alettava täyttää tiedoilla alemmista eli alemmista tiedoista. vähemmän merkittäviä rivejä. Täsmälleen sama numerointijärjestys on otettu käyttöön Intel x86 -mikroprosessoriarkkitehtuurissa, minkä vuoksi salauksen ohjelmistototeutus tässä arkkitehtuurissa ei vaadi ylimääräisiä bittien permutaatioita datasanojen sisällä.

Jos jokin operaatio suoritetaan dataelementeille, joilla on looginen merkitys, niin oletetaan, että tämä toimenpide suoritetaan elementtien vastaaville biteille. Toisin sanoen A B=(a 0 b 0 ,a 1 b 1 ,…,a n –1 b n-1), missä n=|A|=|B|, ja symboli " " tarkoittaa mielivaltaista binaarista loogista toimintoa; viittaa yleensä operaatioon yksinomainen tai , joka on myös summausmoduulin 2 operaatio:

Salauksen rakentamisen logiikka ja GOST:n avaintietojen rakenne.

Jos tutkit huolellisesti alkuperäistä GOST 28147–89:ää, huomaat, että se sisältää kuvauksen useiden tasojen algoritmeista. Huipulla ovat käytännölliset algoritmit, jotka on suunniteltu salaamaan tietotaulukoita ja kehittämään niille väärennettyjä lisäyksiä. Ne kaikki perustuvat kolmeen alemman tason algoritmiin, joita kutsutaan tekstissä GOSTiksi syklit . Näihin perusalgoritmeihin viitataan tässä artikkelissa nimellä perussyklit erottamaan ne kaikista muista silmukoista. Niillä on seuraavat nimet ja nimitykset, viimeksi mainitut on annettu suluissa ja niiden merkitys selitetään myöhemmin:

• salausjakso (32-3);
• salauksenpurkujakso (32-P);
• jäljitelmälisäkkeen (16-Z) generointisykli.

Jokainen perussykli puolestaan ​​on yhden toimenpiteen moninkertainen toisto, jota vaaditaan tarkemmin tässä artikkelissa kryptomuunnoksen päävaihe .

Joten GOST:n ymmärtämiseksi sinun on ymmärrettävä seuraavat kolme asiaa:

• mitä on tapahtunut perusaskel kryptomuunnokset;
• miten perussyklit muodostuvat päävaiheista;
• kuin kolmesta perussyklit laske yhteen kaikki GOSTin käytännön algoritmit.

Ennen kuin jatkamme näiden asioiden tutkimista, meidän tulisi puhua GOST-algoritmien käyttämistä keskeisistä tiedoista. Kirchhoff-periaatteen mukaisesti, jonka tyydyttävät kaikki nykyaikaiset suuren yleisön tuntemat salaukset, sen salassapito takaa salatun viestin salaisuuden. GOST:ssa avaintieto koostuu kahdesta tietorakenteesta. Lisäksi avain tarvitaan kaikille salakirjoille, se sisältää myös korvaustaulukko . Alla on GOSTin avainrakenteiden pääominaisuudet.

Kryptomuunnoksen päävaihe.

Pääasiallinen kryptomuunnosvaihe on pohjimmiltaan operaattori, joka määrittelee 64-bittisen datalohkon muuntamisen. Tämän operaattorin lisäparametri on 32-bittinen lohko, jota käytetään avaimen minkä tahansa elementtinä. Pääaskelalgoritmin kaavio on esitetty kuvassa 1.

Kuva 1. Kaavio GOST 28147-89 -algoritmin kryptomuunnoksen päävaiheesta.

Alla on selitykset päävaihealgoritmista:

Vaihe 0

• N– 64-bittinen muunnettava datalohko, jonka vaiheen suorituksen aikana se on vähiten merkittävä ( N 1) ja vanhempi ( N 2) osia käsitellään erillisinä 32-bittisinä etumerkittöminä kokonaislukuina. Näin ollen voi kirjoittaa N=(N 1 ,N 2).
• X– 32-bittinen avainelementti;

Vaihe 1

Lisäys avaimella. Muunnetun lohkon alempaan puoliskoon lisätään modulo 2 32 vaiheessa käytetty avainelementti, tulos siirretään seuraavaan vaiheeseen;

Vaihe 2

Lohkon vaihto. Edellisessä vaiheessa saatu 32-bittinen arvo tulkitaan kahdeksan 4-bittisen koodilohkon joukoksi: S=(S 0 , S 1 , S 2 , S 3 , S 4 , S 5 , S 6 , S 7), ja S 0 sisältää 4 pienintä ja S 7 - 4 tärkeintä bittiä S.

Seuraavaksi kunkin kahdeksan lohkon arvo korvataan uudella, joka valitaan korvaustaulukosta seuraavasti: lohkon arvo Si muuttuu Si- peräkkäinen elementti (numerointi nollasta) i-korvaussolmun (ts. i-korvaustaulukon rivi, numerointi myös nollasta). Toisin sanoen lohkoarvon korvaamiseksi korvaustaulukosta valitaan elementti, jonka rivinumero on yhtä suuri kuin korvauslohkonumero ja sarakkeen numero, joka vastaa korvauslohkon arvoa 4-bittisenä ei-negatiivisena kokonaislukuna. Tästä selviää korvaavan taulukon koko: siinä olevien rivien määrä on yhtä suuri kuin 4-bittisten elementtien lukumäärä 32-bittisessä tietolohkossa, eli kahdeksan, ja sarakkeiden lukumäärä on yhtä suuri kuin 4-bittisen datalohkon erillisten arvojen lukumäärä, jonka tiedetään olevan 2 4, kuusitoista.

Vaihe 3

Kierrä vasemmalle 11 bittiä. Edellisen vaiheen tulosta siirretään syklisesti 11 bittiä kohti korkeampia bittejä ja siirretään seuraavaan vaiheeseen. Algoritmikaaviossa symboli tarkoittaa argumenttinsa syklisen siirron funktiota 11 bittiä vasemmalle, ts. kohti korkeampia tasoja.

Vaihe 4

Bitittainen lisäys: Vaiheessa 3 saatu arvo lisätään modulo 2 bitti kerrallaan muunnettavan lohkon ylimpään puolikkaaseen.

Vaihe 5

Siirto ketjua pitkin: muunnetun lohkon alaosa siirretään vanhemman paikalle, ja edellisen vaiheen tulos asetetaan sen paikalle.

Vaihe 6

Tuloksena oleva muunnettavan lohkon arvo palautetaan pääsalausmuunnosvaiheen algoritmin suorittamisen tuloksena.

Salausmuunnosten perussyklit.

Kuten tämän artikkelin alussa todettiin, GOST kuuluu lohkosalausten luokkaan, eli siinä oleva tietojenkäsittelyyksikkö on tietolohko. Siksi on varsin loogista odottaa, että se määrittelee algoritmit kryptografisille muunnoksille, eli salaukselle, salauksen purkamiselle ja "kirjanpidolle" yhden tietolohkon ohjausyhdistelmässä. Näitä algoritmeja kutsutaan perussyklit GOST, joka korostaa niiden perustavaa merkitystä tämän salauksen rakentamisessa.

Perussyklit on rakennettu perusvaiheet edellisessä osiossa käsitelty kryptografinen muunnos. Päävaiheen suorittamisen aikana käytetään vain yhtä 32-bittistä avainelementtiä, kun taas GOST-avain sisältää kahdeksan tällaista elementtiä. Siksi, jotta avainta voidaan käyttää täysin, jokaisen perussilmukan on suoritettava toistuvasti päävaihe eri elementeineen. Samalla vaikuttaa aivan luonnolliselta, että jokaisessa perussyklissä avaimen kaikkia elementtejä tulee käyttää yhtä monta kertaa, salauksen vahvuussyistä tämän lukumäärän tulisi olla enemmän kuin yksi.

Kaikki yllä tehdyt, yksinkertaisesti terveeseen järkeen perustuvat oletukset osoittautuivat oikeiksi. Perussilmukat ovat toistuvia suorituksia päävaihe käyttämällä avaimen eri elementtejä ja eroavat toisistaan ​​vain vaiheen toistojen määrässä ja avainelementtien käyttöjärjestyksessä. Tämä järjestys on annettu alla eri sykleille.

Salausjakso 32-3:

K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 .

Kuva 2a. Salausjakson 32-Z kaavio

Salauksen purkujakso 32-P:

K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 .

Kuvio 2b. 32-P-salauksenpurkukaavio

Jäljitelmälisäkkeen 16-З valmistussykli:

K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 .

Kuvio 2c. Jäljitelmälisäkkeen 16-З tuotantosyklin kaavio.

Jokaisella syklillä on oma aakkosnumeerinen merkintä, joka vastaa kuviota " n-X", jossa nimityksen ensimmäinen osa ( n), määrittää syklin päävaiheen toistojen lukumäärän ja merkinnän toisen elementin ( X), kirjain, määrittää salausjärjestyksen ("З") tai salauksen purkamisen ("Р") avainelementtien käytössä. Tämä tilaus vaatii lisäselvitystä:

Salauksen purkujakson on oltava salausjakson käänteinen, eli näiden kahden jakson peräkkäisen soveltamisen mielivaltaiseen lohkoon täytyy johtaa alkuperäiseen lohkoon, mikä näkyy seuraavalla suhteella: C 32-R ( C 32-З ( T))=T, missä T- mielivaltainen 64-bittinen tietolohko, C X( T) on silmukan tulos X tietolohkon yläpuolella T. Tämän ehdon täyttämiseksi GOST:n kaltaisille algoritmeille on välttämätöntä ja riittävää, että järjestys, jossa vastaavat syklit käyttävät avainelementtejä, on keskenään käänteinen. Kirjallisen ehdon pätevyys tarkasteltavassa tapauksessa on helppo varmistaa vertaamalla yllä olevia jaksoja jaksoille 32-3 ja 32-R. Edellisestä seuraa yksi mielenkiintoinen seuraus: syklin ominaisuus olla käänteinen toiselle jaksolle on molemminpuolinen, eli jakso 32-3 on käänteinen syklin 32-P suhteen. Toisin sanoen tietolohkon salaus voitaisiin teoriassa tehdä salauksenpurkusilmukalla, jolloin tietolohkon salauksen purku olisi tehtävä salaussilmukalla. Kahdesta keskenään käänteisestä syklistä jompaakumpaa voidaan käyttää salaukseen, sitten toista on käytettävä tietojen salauksen purkamiseen, mutta GOST28147-89-standardi määrittää jaksoille roolit, eikä anna käyttäjälle oikeutta valita tässä asiassa. .

Lisäysjäljitelmän generointijakso on puolet salausjaksoista pitempi, avainelementtien käyttöjärjestys siinä on sama kuin salaussyklin 16 ensimmäisessä vaiheessa, mikä on helppo nähdä yllä olevat sekvenssit huomioon ottaen, joten tämä järjestys syklin nimeämisessä on koodattu samalla kirjaimella "Z".

Perussyklien kaaviot on esitetty kuvissa 2a-c. Jokainen niistä ottaa argumenttina ja palauttaa tuloksena 64-bittisen tietolohkon, joka on merkitty kaavioihin N. Symboli Step( N,X) tarkoittaa pääsalauksen muunnosvaiheen suorittamista datalohkolle N käyttämällä avainelementtiä X. Simulaatiolisäyksen salaus- ja laskentajaksojen välillä on vielä yksi ero, jota ei mainita yllä: salauksen perusjaksojen lopussa tuloslohkon ylä- ja alaosat vaihdetaan, tämä on välttämätöntä niiden keskinäisen palautuvuuden vuoksi. .

Perussalaustilat.

GOST 28147-89 tarjoaa seuraavat kolme tietojen salaustilaa:

• yksinkertainen vaihto,
• pelaaminen,
• palaute gamma,

ja yksi lisämuoto jäljitelmän lisäyksen tuottamiseksi.

Kaikissa näissä tiloissa dataa käsitellään 64-bittisinä lohkoina, joihin matriisi jaetaan ja joille tehdään kryptografinen muunnos, minkä vuoksi GOST viittaa lohkosalauksiin. Kahdessa pelitilassa on kuitenkin mahdollista käsitellä alle 8 tavun epätäydellinen tietolohko, mikä on välttämätöntä salattaessa mielivaltaisen kokoisia tietoryhmiä, jotka eivät saa olla 8 tavun kerrannaisia.

Ennen kuin siirrytään tarkastelemaan tiettyjä kryptografisia muunnosalgoritmeja, on tarpeen selventää kaavioissa käytettyä merkintää seuraavissa kohdissa:

T Oi T w ovat avoimen ja salatun datan ryhmiä;

, – i- 64-bittiset avoimen ja salatun tiedon lohkot: , , viimeinen lohko voi olla epätäydellinen: ;

n– 64-bittisten lohkojen määrä tietotaulukossa;

C X on funktio 64-bittisen datalohkon muuntamiseksi perussyklin "X" algoritmin mukaisesti.

Kuvataan nyt tärkeimmät salaustilat:

Yksinkertainen vaihto.

Salaus tässä tilassa koostuu 32-3-syklin soveltamisesta avoimiin tietolohkoihin, salauksen purkamiseen - 32-P-jakson soveltamiseen salattuihin tietolohkoihin. Tämä on muodoista yksinkertaisin, siinä käsitellään 64-bittisiä datalohkoja toisistaan ​​riippumatta. Salaus- ja salauksenpurkualgoritmien kaaviot yksinkertaisessa korvaustilassa on esitetty kuvioissa 3a ja b, vastaavasti, ne ovat triviaaleja eivätkä kaipaa kommentteja.

Piirustus. 3a. Tietojen salausalgoritmi yksinkertaisessa vaihtotilassa

Piirustus. 3b. Tietojen salauksen purkualgoritmi yksinkertaisessa korvaustilassa

Salauksen tai salauksen purkamisen kohteena olevan avoimen tai salatun tiedon joukon koon on oltava 64 bitin kerrannainen: | T o |=| T w |=64 n , toiminnon suorittamisen jälkeen vastaanotetun datataulukon koko ei muutu.

Yksinkertaisessa korvaavassa salaustilassa on seuraavat ominaisuudet:

• Koska tietolohkot salataan toisistaan ​​riippumatta ja niiden sijainnista datataulukossa, kun kaksi identtistä selkotekstilohkoa salataan, saadaan identtiset salatekstilohkot ja päinvastoin. Mainitun ominaisuuden avulla kryptaanalyytikko voi päätellä, että alkuperäisen datan lohkot ovat identtisiä, jos hän kohtaa identtiset lohkot salatussa datataulukossa, mikä ei ole hyväksyttävää vakavalle salaukselle.
• Jos salatun datataulukon pituus ei ole 8 tavun tai 64 bitin kerrannainen, syntyy ongelma, miten ja miten taulukon viimeinen epätäydellinen datalohko täytetään täyteen 64 bittiin. Tämä tehtävä ei ole niin yksinkertainen kuin miltä näyttää ensi silmäyksellä. Ilmeiset ratkaisut, kuten "täytä epätäydellinen lohko nollabitillä" tai yleisemmin "täytä epätäydellinen lohko kiinteällä nollan ja yhden bitin yhdistelmällä", voivat tietyissä olosuhteissa antaa kryptaanalyytikolle mahdollisuuden määrittää tämän sisällön. erittäin epätäydellinen lohko luettelointimenetelmillä, ja tämä tosiasia tarkoittaa suojaussalauksen vähenemistä. Lisäksi salatekstin pituus muuttuu ja kasvaa lähimpään 64 bitin kokonaislukukerrokseen, mikä on usein ei-toivottavaa.

Ensi silmäyksellä yllä luetellut ominaisuudet tekevät yksinkertaisen korvaustilan käyttämisen käytännössä mahdottomaksi, koska sillä voidaan salata vain 64 bitin kerrannaisia ​​dataryhmiä, jotka eivät sisällä toistuvia 64-bittisiä lohkoja. Näyttää siltä, ​​että näiden ehtojen täyttymistä on mahdotonta taata minkään todellisen tiedon osalta. Tämä on melkein totta, mutta on yksi erittäin tärkeä poikkeus: muista, että avaimen koko on 32 tavua ja korvaavan taulukon koko on 64 tavua. Lisäksi toistuvien 8-tavuisten lohkojen läsnäolo avain- tai korvaustaulukossa osoittaa niiden erittäin huonoa laatua, joten todellisissa avainelementeissä ei voi olla tällaista toistoa. Siten havaitsimme, että yksinkertainen korvaustila on varsin sopiva avaintietojen salaamiseen, varsinkin kun muut tilat ovat vähemmän käteviä tähän tarkoitukseen, koska ne vaativat ylimääräisen synkronointitietoelementin - synkronointiviestin (katso seuraava osa). Oletuksemme on oikea, GOST määrää yksinkertaisen korvaustilan käytön yksinomaan avaintietojen salaamiseen.

Uhkapelit.

Kuinka pääset eroon yksinkertaisen vaihtotilan puutteista? Tätä varten on tarpeen mahdollistaa alle 64 bitin lohkojen salaus ja varmistaa, että salatekstilohko riippuu sen lukumäärästä, toisin sanoen satunnaistaa salausprosessi. GOST:ssa tämä saavutetaan kahdella eri tavalla kahdessa salaustilassa, tarjoten skaalaus . Uhkapelit - tämä on salausalueen asettaminen (poistaminen) avoimelle (salatulle) datalle, toisin sanoen tietoelementtien sarja, joka on luotu käyttämällä jotakin kryptografista algoritmia salatun (avoimen) tiedon saamiseksi. Vastavuoroisesti käänteisiä binäärioperaatioita on käytettävä gamman päällekkäisyyteen salauksen aikana ja sen poistamiseen salauksen purkamisen aikana, esimerkiksi yhteen- ja vähennysmodulo 2 64 64-bittisille tietolohkoille. GOST:ssa tähän tarkoitukseen käytetään bittikohtaista lisäystä modulo 2, koska se on käänteinen itselleen ja lisäksi se on yksinkertaisimmin toteutettu laitteistossa. Gamming ratkaisee molemmat yllä mainitut ongelmat: ensinnäkin kaikki gammaelementit ovat erilaisia ​​todellisissa salatuissa taulukoissa, ja siksi jopa kahden identtisen lohkon salaustulos yhdessä datataulukossa on erilainen. Toiseksi, vaikka gamma-elementit tuotetaan yhtä suurena 64 bitin osuuksina, voidaan käyttää myös sellaisen lohkon osaa, jonka koko on yhtä suuri kuin salatun lohkon koko.

Siirrytään nyt suoraan gammatilan kuvaukseen. Tämän tilan gamma saadaan seuraavasti: käyttämällä jotakin algoritmista toistuvan numerosekvenssin generaattoria (RGCH) luodaan 64-bittiset tietolohkot, joille suoritetaan sitten 32-3-muunnos, eli salaus yksinkertaisessa korvaustilassa, jolloin tuloksena on gammalohkoissa. Koska päällekkäisyys ja gamman poistaminen suoritetaan käyttämällä samaa bittikohtaista XOR-toimintoa, salaus- ja salauksenpurkualgoritmit gammatilassa ovat identtisiä, niiden yleinen kaavio on esitetty kuvassa 4.

Asteikon luomiseen käytetty RGHR on toistuva toiminto: – toistuvan sekvenssin elementit, f on muunnosfunktio. Siksi väistämättä herää kysymys sen alustamisesta, eli elementistä, itse asiassa tämä tietoelementti on algoritmiparametri gammamoodille, se on merkitty kaavioihin S, ja sitä kutsutaan kryptografiassa synkronoida viesti ja GOSTissamme - alkutäyttö yksi kooderirekistereistä. Tietyistä syistä GOST:n kehittäjät päättivät käyttää RGHR:n alustamiseen ei suoraan synkronointiviestiä, vaan sen muuntamisen tulosta 32-3-syklin mukaisesti: . RGHR:n luoma elementtien järjestys riippuu täysin sen alkuperäisestä täytöstä, eli tämän sekvenssin elementit ovat lukumääränsä ja RGHR:n alkutäytön funktio: missä fi(X)=f(fi –1 (X)), f 0 (X)=X. Kun otetaan huomioon muunnos yksinkertaisen korvausalgoritmin mukaan, lisätään myös riippuvuus avaimesta:

missä G i– i- asteikon elementti, K- avain.

Siten gamma-tilassa käytettävien gammaelementtien järjestys määräytyy yksiselitteisesti avaindatan ja synkronointisanoman perusteella. Luonnollisesti salauksen purku- ja purkuprosesseissa on käytettävä samaa synkronointisanomaa, jotta salausprosessi olisi palautuva. Alueen ainutlaatuisuuden vaatimuksesta, jonka epäonnistuminen johtaa salauksen voimakkuuden katastrofaaliseen heikkenemiseen, seuraa, että kahden eri tietoryhmän salaamiseksi samalla avaimella on varmistettava erilaisia ​​synkronointiviestejä. Tämä johtaa tarpeeseen tallentaa tai lähettää synkronointiviesti viestintäkanavia pitkin yhdessä salatun datan kanssa, vaikka joissakin erikoistapauksissa se voidaan määrittää ennalta tai laskea erityisellä tavalla, jos kahden taulukon salaus samalla avaimella on poissuljettu.

Katsotaanpa nyt tarkemmin RGHR:ää, jota käytetään GOST:ssa gammaelementtien luomiseen. Ensinnäkin on huomattava, että generoidusta numerosarjasta ei vaadita tilastollisia ominaisuuksia. GOST-kehittäjät suunnittelivat RGHR:n seuraavien ehtojen täyttymisen perusteella:

• RGHR:n generoiman numerosarjan toistojakson ei tulisi poiketa suuresti (prosentteina) suurimmasta mahdollisesta arvosta 2 64 tietylle lohkokoolle;
• RGHR:n tuottamien naapuriarvojen tulee erota toisistaan ​​jokaisessa tavussa, muuten kryptanalyytikon tehtävä yksinkertaistuu;
• RGHR:n pitäisi olla melko helppo toteuttaa sekä laitteistossa että ohjelmistossa yleisimmissä prosessoreissa, joista useimmat ovat, kuten tiedät, 32-bittisiä.

Näiden periaatteiden perusteella GOSTin luojat suunnittelivat erittäin onnistuneen RGHR:n, jolla on seuraavat ominaisuudet:

Missä C 0 =1010101 16 ;

Missä C 1 =1010104 16 ;

Luvun merkinnässä oleva alaindeksi tarkoittaa sen numerojärjestelmää, joten tässä vaiheessa käytetyt vakiot kirjoitetaan heksadesimaalilukujärjestelmään.

Toinen lauseke tarvitsee kommentteja, koska GOST-tekstissä annetaan jotain muuta: , samalla vakion arvolla C yksi . Mutta edelleen standardin tekstissä annetaan kommentti, että käy ilmi, että operaatiossa otetaan loput modulo 2 32 -1 siellä ei ymmärretä samalla tavalla kuin matematiikassa. Ero on siinä, että GOST:n (2 32 -1) mukaan mod(2 32 –1)=(2 32 –1), ei 0. Itse asiassa tämä yksinkertaistaa kaavan toteutusta, ja matemaattisesti oikea lauseke sille on annettu yllä.

• sarjan toistojakso nuoremmalle osalle on 2 32, vanhemmalle osalle 2 32 -1, koko jaksolle jakso on 2 32 (2 32 -1), todiste tästä tosiasiasta, hyvin yksinkertainen, tulet Hanki itsellesi. Ensimmäinen kaava kahdesta on toteutettu yhdellä käskyllä, toinen, ilmeisestä vaivallisuudestaan ​​huolimatta, kahdella käskyllä ​​kaikissa nykyaikaisissa 32-bittisissä prosessoreissa - ensimmäinen käsky on tavallinen additio modulo 2 32 siirtobitin tallennuksella, ja toinen käsky lisää siirtobitin vastaanotettuun arvoon.

Salausalgoritmin kaavio gammatilassa on esitetty kuvassa 4, alla on kaavion selitykset:

Kuva 4. Datan salausalgoritmi (salauksen purku) gammatilassa.

Vaihe 0

Määrittää alkutiedot pääsalausmuunnosvaiheelle:

• T o(w) - mielivaltaisen kokoisen avoimen (salatun) datan joukko, jolle suoritetaan salaus (salauksen purku) proseduurin aikana, taulukko muunnetaan 64 bitin osissa;
• S – synkronoida viesti 64-bittinen dataelementti, joka tarvitaan gammageneraattorin alustamiseen;

Vaihe 1

Synkronointisanoman alkumuunnos, joka suoritetaan sen "satunnaistamiseksi" eli siinä olevien tilastollisten kuvioiden eliminoimiseksi, tulosta käytetään RGHR:n alkutäyttönä;

Vaihe 2

Yksi askel RGHR:n työstä, joka toteuttaa sen toistuvan algoritmin. Tämän vaiheen aikana vanhempi ( S 1) ja nuorempi ( S 0) datasekvenssin osat muodostetaan toisistaan ​​riippumatta;

Vaihe 3

Uhkapelit. Seuraava RGHR:n tuottama 64-bittinen elementti alistetaan 32-3-salaukseen, jonka tulosta käytetään gamma-elementtinä seuraavan samankokoisen avoimen (salatun) tiedon lohkon salaamiseen (purkaa salaus).

Vaihe 4

Algoritmin tulos on salattu (salauksesta purettu) tietojoukko.

Seuraavat ovat gamman ominaisuudet salaustilana:

1. Identtiset lohkot avoimessa datataulukossa antavat salattuna erilaisia ​​salatekstilohkoja, mikä mahdollistaa niiden henkilöllisyyden piilottamisen.
2. Koska gamma suoritetaan bitti kerrallaan, epätäydellisen datalohkon salaus onnistuu helposti tämän epätäydellisen lohkon bittien salauksena, johon käytetään gammalohkon vastaavia bittejä. Joten epätäydellisen 1 bitin lohkon salaamiseen standardin mukaan tulee käyttää vähiten merkitsevää bittiä gammalohkosta.
3. Salauksessa käytetty synkronointiviesti on jotenkin välitettävä, jotta sitä voidaan käyttää salauksen purkamisessa. Tämä voidaan saavuttaa seuraavilla tavoilla:

• tallentaa tai lähettää synkronointiviestin yhdessä salatun datataulukon kanssa, mikä kasvattaa dataryhmän kokoa salauksen aikana synkronointiviestin koolla eli 8 tavulla;
• käyttää synkronointisanoman ennalta määrättyä arvoa tai generoi se synkronisesti lähteen ja vastaanottimen toimesta tietyn lain mukaisesti, jolloin lähetettävän tai tallennetun dataryhmän koko ei muutu;

Molemmat menetelmät täydentävät toisiaan, ja niissä harvoissa tapauksissa, joissa ensimmäinen, yleisin niistä ei toimi, voidaan käyttää toista, eksoottisempaa. Toinen menetelmä on paljon vähemmän hyödyllinen, koska on mahdollista tehdä synkronointiviesti ennalta määrätyksi vain, jos vain yksi tietojoukko on salattu tietylle avaintietojoukolle, mitä ei tapahdu kovin usein. Synkronointiviestiä ei myöskään aina ole mahdollista generoida synkronisesti datataulukon lähteellä ja vastaanottajalla, koska se vaatii kovaa yhteyttä johonkin järjestelmässä. Joten näennäisen järkevä ajatus käyttää lähetetyn viestin numeroa synkronointisanomana salattujen viestien välitysjärjestelmässä ei sovellu, koska viesti saattaa kadota eikä pääse vastaanottajalle, jolloin lähteen salausjärjestelmät ja vastaanotin ei ole synkronoitu. Siksi tarkasteltavassa tapauksessa ei ole vaihtoehtoa synkronointiviestin lähettämiselle salatun viestin mukana.

Toisaalta voidaan antaa myös päinvastainen esimerkki. Oletetaan, että tietojen salausta käytetään suojaamaan levyllä olevia tietoja, ja se on toteutettu alhaisella tasolla, tiedot salataan sektoreittain riippumattoman pääsyn varmistamiseksi. Tässä tapauksessa synkronointiviestin tallentaminen salatun tiedon mukana on mahdotonta, koska sektorin kokoa ei voi muuttaa, mutta se voidaan laskea levyn lukupään numeron, raidan (sylinterin) numeron funktiona, ja sektorin numero radalla. Tässä tapauksessa synkronointiviesti on sidottu levyllä olevan sektorin sijaintiin, joka tuskin voi muuttua ilman levyn alustamista eli tuhoamatta sillä olevia tietoja.

Gamma-tilassa on toinen mielenkiintoinen ominaisuus. Tässä tilassa datataulukon bitit salataan toisistaan ​​riippumatta. Siten jokainen salatekstin bitti riippuu vastaavasta selkeän tekstin bitistä ja tietysti bitin järjestysnumerosta taulukossa: . Tästä seuraa, että salatekstin bitin muuttaminen päinvastaiseksi johtaa samanlaiseen selkeän tekstin bitin muutokseen päinvastaiseksi:

jossa tarkoittaa käänteistä suhteessa t bitin arvo ().

Tämä ominaisuus antaa hyökkääjälle mahdollisuuden salakirjoitusbittejä manipuloimalla tehdä ennustettavia ja jopa kohdennettuja muutoksia vastaavaan salauksen purkamisen jälkeen saatuun selkeään tekstiin ilman, että hänellä on hallussaan salaista avainta. Tämä havainnollistaa kryptologiassa hyvin tunnettua tosiasiaa, että salaisuus ja aitous ovat eri ominaisuuksia kryptografiset järjestelmät . Toisin sanoen salausjärjestelmän ominaisuudet, jotka tarjoavat suojan luvattomalta pääsyltä viestin sisältöön ja viestin luvattomilta muutoksilta, ovat riippumattomia ja voivat risteytyä vain joissakin tapauksissa. Tämä tarkoittaa, että on olemassa salausalgoritmeja, jotka tarjoavat tietyn salaisuuden salatuille tiedoille eivätkä samalla suojaa muutoksilta, ja päinvastoin, varmistavat tietojen aitouden eivätkä rajoita mahdollisuutta tutustua niihin. Tästä syystä gammatilan harkittua ominaisuutta ei pitäisi pitää sen haittana.

Uhkapeli palautteen kera.

Tämä tila on hyvin samanlainen kuin gammatila ja eroaa siitä vain gamma-elementtien luontitavassa - seuraava gamma-elementti syntyy muunnoksen tuloksena edellisen salatun datalohkon 32-3-jaksolla, ja salaa tietotaulukon ensimmäinen lohko, gamma-elementti generoidaan muunnoksen tuloksena saman synkronointijakson mukaisesti. Tällä saavutetaan lohkolinkitys - jokainen salatekstin lohko tässä tilassa riippuu vastaavista ja kaikista aikaisemmista selkeän tekstin lohkoista. Siksi tätä tilaa kutsutaan joskus skaalaus verkkopaloilla . Se, että lohkot on linkitetty, ei vaikuta salauksen turvallisuuteen.

Palaute-gamma-moodin dekoodauksen ja salauksen purkamisen algoritmikaavio on esitetty kuvassa 5, eikä se yksinkertaisuutensa vuoksi kaipaa kommentteja.

Kuva 5. Algoritmi tietojen salaukselle (salauksen purkamiselle) gammatilassa palautteen kanssa.

Suljetun silmukan gammatilan salauksella on samat ominaisuudet kuin salauksella normaalissa gammatilassa, lukuun ottamatta salatekstin vioittumisen vaikutusta vastaavaan selkeään tekstiin. Vertailun vuoksi kirjoitetaan lohkon salauksenpurkutoiminnot molemmille mainituille moodeille:

Peli;

Pelaaminen palautteen avulla;

Kun normaalissa skaalaustilassa muutokset tietyissä salatekstin bitteissä vaikuttavat vain vastaaviin puhtaan tekstin bitteihin, palauteskaalaustilassa kuva on hieman monimutkaisempi. Kuten vastaavasta yhtälöstä voidaan nähdä, avattaessa datalohkon salausta suljetun silmukan gammatilassa avoin datalohko riippuu vastaavasta ja aikaisemmasta salatusta datalohkosta. Siksi, jos tuomme vääristymiä salattuun lohkoon, niin salauksen purkamisen jälkeen kaksi avoimen datan lohkoa vääristyy - vastaava ja sitä seuraava, ja ensimmäisessä tapauksessa vääristymät ovat luonteeltaan samanlaisia ​​kuin gammassa. tilassa, ja toisessa tapauksessa - kuten tilassa yksinkertainen vaihto. Toisin sanoen vastaavassa avoimessa datalohkossa samat bitit korruptoituvat kuin salatussa datalohkossa ja seuraavassa avoimessa datalohkossa kaikki bitit ovat toisistaan ​​riippumattomia todennäköisyydellä 1 / 2 muuttaa arvojaan.

Lisäyssimulaation kehittäminen datajoukolle.

Aiemmissa osioissa olemme käsitelleet salattujen tietojen korruption vaikutusta vastaavaan selkeään dataan. Havaitsimme, että yksinkertaisessa korvaustilassa avattaessa vastaava avoimen datan lohko vääristyy arvaamattomalla tavalla, ja lohkon salausta purettaessa gammatilassa muutokset ovat ennakoitavissa. Suljetussa skaalaustilassa kaksi lohkoa vääristyy, toinen ennustettavasti ja toinen arvaamattomalla tavalla. Tarkoittaako tämä sitä, että väärän tiedon pakottamista vastaan ​​suojautumisen kannalta gammatila on huono, kun taas yksinkertaisen vaihto- ja palautegammatilat ovat hyviä? - Ei missään tapauksessa. Analysoitaessa tätä tilannetta on tarpeen ottaa huomioon se, että ennakoimattomia muutoksia puretussa tietolohkossa voidaan havaita vain näiden samojen tietojen redundanssin tapauksessa, ja mitä suurempi redundanssiaste on, sitä todennäköisemmin on havaita vääristymä. Erittäin suuri redundanssi tapahtuu esimerkiksi luonnollisilla ja keinotekoisilla kielillä oleville teksteille, jolloin vääristymä on lähes väistämätöntä. Kuitenkin muissa tapauksissa, esimerkiksi vääristäessään pakattuja digitoituja äänikuvia, saamme yksinkertaisesti toisenlaisen kuvan, jonka korvamme voi havaita. Vääristymä jää tässä tapauksessa havaitsematta, ellei luonnollisesti ole ennakkotietoa äänen luonteesta. Johtopäätös tästä on seuraava: koska joidenkin salausmoodien kyky havaita salattuun dataan tuotuja vääristymiä riippuu suuresti salatun datan olemassaolosta ja redundanssin asteesta, tämä kyky ei ole vastaavien tilojen immanentti ominaisuus, eikä sitä voida pitää heidän etunsa.

Ongelman ratkaisemiseksi, joka koskee vääristymien havaitsemista salatussa tietojoukossa tietyllä todennäköisyydellä, GOST tarjoaa ylimääräisen salausmuunnostavan - jäljitellyn lisäyksen luomisen. Väärennetty liite on ohjausyhdistelmä, joka riippuu avoimesta datasta ja salaisen avaimen tiedoista. Lisäysmimiikan käytön tarkoituksena on havaita kaikki vahingossa tapahtuneet tai tahalliset muutokset tietojoukossa. Edellisessä kappaleessa kuvattu ongelma voidaan ratkaista onnistuneesti lisäämällä jäljitelty lisäys salattuihin tietoihin. Potentiaaliselle hyökkääjälle seuraavat kaksi tehtävää ovat käytännössä ratkaisemattomia, jos hän ei omista avainta:

• lisäyssimuloinnin laskeminen tietylle avoimelle informaatiojoukolle;
• avoimen datan valinta tietylle simulaatioinserteelle;

Simuloidun liitteen generointialgoritmin kaavio on esitetty kuvassa 6.

Kuva 6. Algoritmi simuloidun lisäyksen luomiseksi datataulukolle.

Lähdössä vastaanotettu lohkon osa otetaan jäljitelmälisäkkeeksi, yleensä sen 32 vähiten merkitsevää bittiä. Simuloidun lisäyksen kokoa valittaessa tulee ottaa huomioon, että todennäköisyys väärän tiedon asettamiseen onnistuneesti on 2 –| minä | brute force -yritystä kohti, ellei hyökkääjällä ole tehokkaampaa raa'an voiman menetelmää kuin yksinkertainen arvaus. Käytettäessä 32-bittistä väärennettyä lisäosaa tämä todennäköisyys on

Keskustelu GOST-salausalgoritmeista.

GOSTin kryptografinen vahvuus.

Valittaessa kryptografista algoritmia käytettäväksi tietyssä kehitystyössä, yksi määräävistä tekijöistä on sen vahvuus eli vastustuskyky vastustajan yrityksille paljastaa se. Kysymys salauksen vahvuudesta, lähemmin tarkasteltuna, tiivistyy kahteen toisiinsa liittyvään kysymykseen:

• onko tämä salaus ollenkaan mahdollista avata;
• jos on, kuinka vaikeaa se on käytännössä;

Salauksia, joita ei voi rikkoa ollenkaan, kutsutaan ehdottoman tai teoreettisesti turvallisiksi. Tällaisten salausten olemassaolon todistaa Shannonin lause, mutta tämän vahvuuden hinta on tarve käyttää avainta, joka ei ole pienempi kuin itse viesti salaamaan jokainen viesti. Kaikissa tapauksissa, lukuun ottamatta useita erityisiä, tämä hinta on kohtuuton, joten käytännössä käytetään pääasiassa salauksia, joilla ei ole absoluuttista turvallisuutta. Siten yleisimmin käytetyt salausmenetelmät voidaan ratkaista rajallisessa ajassa tai tarkemmin sanottuna äärellisessä määrässä vaiheita, joista jokainen on jokin lukujen operaatio. Heille tärkein käsite on käytännön vakauden käsite, joka ilmaisee niiden paljastamisen käytännön vaikeutta. Tämän vaikeuden kvantitatiivinen mitta voi olla aritmeettisten ja loogisten perusoperaatioiden lukumäärä, jotka on suoritettava salauksen ratkaisemiseksi, toisin sanoen vastaavan selkeän tekstin määrittämiseksi tietylle salatekstille todennäköisyydellä, joka on vähintään tietty arvo. Samanaikaisesti kryptanalyytikolla voi olla salatun tietojoukon lisäksi avoimen datan lohkoja ja sitä vastaavaa salattua dataa tai jopa mahdollisuus saada vastaava salattu data mihin tahansa valitsemaansa avoimeen dataan - riippuen listatuista ja monista muut määrittelemättömät olosuhteet erotetaan erilliset kryptaanalyysityypit.

Kaikki nykyaikaiset kryptojärjestelmät on rakennettu Kirchhoff-periaatteen mukaan, eli salattujen viestien salassapito määräytyy avaimen salassapitoisuuden mukaan. Tämä tarkoittaa, että vaikka itse salausalgoritmi olisi kryptanalyytikon tiedossa, hän ei silti pysty purkamaan viestiä, jos hänellä ei ole vastaavaa avainta. Salausta pidetään hyvin suunniteltuna, jos sitä ei voida murtaa tehokkaammin kuin raa'alla voimalla etsimällä koko avainavaruudesta, ts. yli kaikkien mahdollisten avainarvojen. GOST todennäköisesti vastaa tätä periaatetta - vuosien intensiivisen tutkimuksen aikana ei ole ehdotettu yhtä tehokasta menetelmää sen krypta-analyysiin. Vahvuudeltaan se on monta suuruusluokkaa parempi kuin entinen amerikkalainen salausstandardi DES.

GOST käyttää 256-bittistä avainta ja avaintilan koko on 2256 . Mikään tällä hetkellä olemassa olevista tai lähitulevaisuudessa otettavissa olevista elektronisista laitteista ei pysty poimimaan avainta alle monessa sadassa vuodessa. Tästä arvosta on tullut nykyään symmetristen salausalgoritmien de facto avaimen kokostandardi, ja myös uusi Yhdysvaltain salausstandardi tukee sitä. Entinen amerikkalainen standardi DES, jonka todellinen avainkoko on 56 bittiä ja avaintilan koko vain 256, ei ole enää tarpeeksi vahva nykyaikaisten laskentatyökalujen ominaisuuksien valossa. Tämän osoittivat 1990-luvun lopulla useat onnistuneet raa'an voiman hyökkäykset DES:ää vastaan. Lisäksi DES joutui erityisiin kryptausanalyysimenetelmiin, kuten differentiaaliseen ja lineaariseen. Tässä suhteessa DES voi olla enemmän tutkimusta tai tieteellistä mielenkiintoa kuin käytännön merkitystä. Vuonna 1998 sen kryptografinen heikkous tunnustettiin virallisesti - Yhdysvaltain kansallinen standardointiinstituutti suositteli kolminkertaisen DES-salauksen käyttöä. Ja vuoden 2001 lopussa hyväksyttiin virallisesti uusi yhdysvaltalainen AES-salausstandardi, joka on rakennettu eri periaatteille ja vapaa edeltäjänsä puutteista.

Huomautuksia GOST-arkkitehtuurista.

Tiedetään hyvin, että kotimainen salausstandardi edustaa kokonaista salausperhettä, joka on rakennettu samoilla periaatteilla. Sen tunnetuin "sukulainen" on entinen amerikkalainen salausstandardi, DES-algoritmi. Kaikki nämä salaukset, kuten GOST, sisältävät kolmen tason algoritmeja. Pohja on aina tietty "perusaskel", jonka pohjalta rakennetaan samalla tavalla "perussyklit", joiden pohjalle rakennetaan jo käytännön menettelyt salaukseen ja jäljitelmän lisäyksen kehittämiseen. Siten tämän perheen jokaisen salauksen spesifisyys on juuri sen päävaiheessa tai pikemminkin jopa sen osassa. Vaikka klassisten lohkosalausten arkkitehtuuri, johon GOST kuuluu, on kaukana tämän artikkelin soveltamisalasta, on silti syytä sanoa muutama sana siitä.

Algoritmit "salauksen muuntamisen perusvaiheille" salauksille, kuten GOST, on rakennettu samalla tavalla, ja tämä arkkitehtuuri on ns. tasapainoinen Feistelin verkko (tasapainoinen Feistel-verkko), joka on nimetty sitä ensimmäisenä ehdottajan mukaan. Datan muunnosmalli yhdellä syklillä tai, kuten sitä yleisesti kutsutaan, pyöristää , näkyy kuvassa 7.

Kuva 7. Pääsalausvaiheen sisältö GOST:n kaltaisille lohkosalauksille.

Pääaskelman tuloon syötetään tasakokoinen lohko, jonka ylä- ja alapuoliskot käsitellään erikseen toisistaan. Muunnoksen aikana lohkon alempi puolisko asetetaan vanhemman tilalle ja vanhempi yhdistetään käyttämällä bittikohtaista " yksinomainen tai » jonkin funktion laskennan tuloksella nuoremman tilalle. Tämä funktio, joka ottaa argumenttina lohkon alaosan ja avaininformaation elementin ( X), on salauksen sisältöosa ja sitä kutsutaan nimellä salaustoiminto . Eri syistä osoittautui edulliseksi jakaa salattu lohko kahteen samankokoiseen osaan: | N 1 |=|N 2 | - tämä tosiasia heijastaa sanaa "tasapainoinen" arkkitehtuurin nimessä. Kuitenkin myös salauksen epätasapainoisia verkkoja käytetään ajoittain, joskaan ei niin usein kuin balansoituja. Lisäksi salauksen vahvuus edellyttää, että avainelementin koko on vähintään puolet lohkosta: GOST:ssa kaikki kolme kokoa ovat 32 bittiä. .

Jos sovellamme yllä olevaa GOST-algoritmin päävaiheen kaavioon, tulee ilmeiseksi, että algoritmin lohkot 1,2,3 (katso kuva 1) määrittävät sen salausfunktion laskennan ja lohkot 4 ja 5 asettuvat. päävaiheen lähtölohkon muodostus tulolohkon sisällön ja salausfunktion arvon perusteella. Tarkempia tietoja nykyaikaisten salaisen avaimen lohkosalausten arkkitehtuurista löytyy klassikoista tai muokattuna teoksistani.

Edellisessä osiossa verrattiin jo DES:ää ja GOST:ia kestävyyden suhteen, nyt verrataan niitä toiminnallisen sisällön ja toteutuksen helppouden suhteen. GOST-salausjaksoissa päävaihe toistetaan 32 kertaa, DES:lle tämä arvo on 16. Itse GOST-salaustoiminto on kuitenkin paljon yksinkertaisempi kuin vastaava DES-toiminto, jossa on monia epäsäännöllisiä bittipermutaatioita. Nämä toiminnot toteutetaan erittäin tehottomasti nykyaikaisissa erikoistumattomissa prosessoreissa. GOST ei sisällä tällaisia ​​​​toimintoja, joten se on paljon kätevämpi ohjelmistojen toteuttamiseen.

Yksikään kirjoittajan Intel x86 -alustalle harkitsemista DES-toteutuksista ei saavuta edes puolta tässä artikkelissa sinulle tarjotun GOST-toteutuksen suorituskyvystä huolimatta kaksi kertaa lyhyemmästä syklistä. Kaikki yllä oleva osoittaa, että GOST-kehittäjät ottivat huomioon sekä DES:n positiiviset että negatiiviset puolet ja arvioivat myös realistisemmin kryptausanalyysin nykyisiä ja tulevia mahdollisuuksia. DES:n käyttäminen perustana salaustoteutusten suorituskyvyn vertailussa ei kuitenkaan ole enää relevanttia. Uusi yhdysvaltalainen salausstandardi pärjää huomattavasti tehokkaammin - samalla avainkoolla kuin GOST 256-bittisessä AES toimii sitä nopeammin noin 14 % - tätä verrataan "alkeistoimintojen" lukumäärään. Lisäksi GOST on käytännössä mahdoton rinnastaa, kun taas AES:llä on paljon enemmän mahdollisuuksia tässä suhteessa. Joissakin arkkitehtuureissa tämä AES:n hyöty voi olla pienempi, toisissa enemmän. Joten Intel Pentium -prosessorilla se saavuttaa 28%. Yksityiskohdat löytyvät osoitteesta.

Keskeiset tiedon laatuvaatimukset ja keskeiset lähteet.

Kaikki avaimet ja korvaustaulukot eivät tarjoa maksimaalista salauksen voimakkuutta. Jokaisella salausalgoritmilla on omat kriteerinsä avaintietojen arvioimiseksi. Joten DES-algoritmille ns. heikot näppäimet ”, jossa avoimen ja salatun tiedon välinen yhteys ei ole tarpeeksi peitetty ja salaus on suhteellisen helppo murtaa.

Tyhjentävä vastaus kysymykseen avainten ja GOST-korvaustaulukoiden laatukriteereistä, jos voit saada sen mistä tahansa, on vain algoritmin kehittäjiltä. Asiaa koskevia tietoja ei julkaistu avoimessa lehdistössä. Vakiintuneen menettelyn mukaan valtuutetulta organisaatiolta saatuja avaintietoja on kuitenkin käytettävä leimattujen tietojen salaamiseen. Epäsuorasti tämä voi viitata menetelmien olemassaoloon avaintietojen tarkistamiseksi "täiden" varalta. Jos heikkojen avainten esiintyminen GOST:ssa on kiistanalainen ongelma, heikkojen korvaussolmujen läsnäolo on kiistaton. On selvää, että "triviaali" korvaustaulukko, jonka mukaan mikä tahansa arvo korvataan itsestään, on niin heikko, että sitä käytettäessä salaus yksinkertaisesti katkeaa, olipa avain mikä tahansa.

Kuten edellä todettiin, keskeisten tietojen arviointikriteereitä ei ole saatavilla, mutta joitain yleisiä huomioita niistä voidaan silti tehdä.

Avain

Avaimen tulee olla joukko tilastollisesti riippumattomia bittejä, jotka saavat arvot 0 ja 1 yhtä suurella todennäköisyydellä. Ei voida täysin sulkea pois sitä mahdollisuutta, että jotkin tietyt avainarvot voivat osoittautua "heikoiksi", eli salaus ei välttämättä tarjoa tiettyä suojaustasoa, jos niitä käytetään. Oletettavasti tällaisten arvojen osuus kaikkien mahdollisten avainten kokonaismassasta on kuitenkin mitätön. Intensiivinen salaustutkimus ei ole ainakaan vielä paljastanut mitään sellaista avainta millekään tunnetulle (eli FAPSI:n ehdottamalle) korvaustaulukolle. Siksi tietyn todella satunnaislukugeneraattorin avulla generoidut avaimet ovat korkealaatuisia todennäköisyydellä, joka eroaa yksiköstä merkityksettömän pienellä määrällä. Jos avaimet luodaanla, käytetyn generaattorin on tarjottava yllä olevat tilastolliset ominaisuudet, ja lisäksi sillä on oltava korkea kryptografinen vahvuus, vähintään itse GOST:n. Toisin sanoen generaattorin luoman elementtisarjan puuttuvien jäsenten määrittäminen ei saisi olla helpompaa kuin salauksen murtaminen. Lisäksi erilaisia ​​tilastollisia kriteerejä voidaan käyttää hylkäämään avaimia, joiden tilastollinen suorituskyky on heikko. Käytännössä yleensä riittää kaksi kriteeriä - avainbittien tasatodennäköisen jakautumisen tarkistamiseksi arvojen 0 ja 1 välillä käytetään yleensä Pearsonin kriteeriä ("chi square") ja avainbittien riippumattomuuden tarkistamiseen sarjakriteeri on käytetty. Mainituista kriteereistä voit lukea matemaattisten tilastojen oppikirjoista tai hakuteoista.

Paras tapa avainten luomiseen olisi käyttää laitteistollisia MF-antureita, mutta tämä ei ole aina hyväksyttävää taloudellisista syistä. Luotaessa pientä joukkoa avaintietoa järkevä vaihtoehto tällaisen anturin käytölle on ja on laajalti käytössä käytännössä "elektroninen ruletti" -menetelmä, jolloin seuraava satunnaisten bittien generoitu osa riippuu hetkestä, jolloin käyttäjä painaa tiettyä näppäintä. tietokoneen näppäimistöllä. Tässä mallissa satunnaisten tietojen lähde on tietokoneen käyttäjä, tarkemmin sanottuna hänen reaktionsa ajalliset ominaisuudet. Tässä tapauksessa vain muutama bitti satunnaista dataa voidaan generoida yhtä näppäinpainallusta kohden, joten avaintietojen generoinnin kokonaisnopeus on alhainen - jopa useita bittejä sekunnissa. Ilmeisesti tämä lähestymistapa ei sovellu suurten avainryhmien hankkimiseen.

Siinä tapauksessa, että on tarpeen kehittää suuri joukko avaintietoja, on mahdollista ja erittäin laajalle levinnyt käyttää erilaisia ​​näennäissatunnaisten lukujen ohjelmistoantureita. Koska tällainen anturi vaatii suurta salausvoimakkuutta, on luonnollista käyttää itse salauksen gammageneraattoria sellaisenaan - "leikataan" salauksen tuottama gamma halutun kokoisiksi "paloiksi", GOST:lle - 32 tavua kukin. . Tietenkin tätä lähestymistapaa varten tarvitsemme "pääavaimen", jonka voimme saada käyttämällä yllä kuvattua elektronista rulettimenetelmää, ja sen avulla, käyttämällä salausta gammageneraattoritilassa, saamme joukon avaintietoja. tarvitsemamme volyymi. Joten nämä kaksi tapaa luoda avaimet - "manuaalinen" ja "algoritminen" - toimivat rinnakkain täydentäen toisiaan. Avainten luontijärjestelmät "pienen budjetin" tiedon kryptografisissa suojausjärjestelmissä rakennetaan lähes aina tämän periaatteen mukaisesti.

Korvaustaulukko

Korvaustaulukko on pitkän aikavälin avainelementti, eli se on voimassa paljon pidempään kuin yksi avain. Oletetaan, että se on yhteinen kaikille salaussolmuille yhden kryptografisen suojausjärjestelmän sisällä. Vaikka korvaustaulukon luottamuksellisuutta rikotaan, salauksen vahvuus pysyy erittäin korkeana eikä laske sallitun rajan alapuolelle. Siksi ei ole erityistä tarvetta pitää taulukkoa salassa, ja useimmissa GOSTin kaupallisissa sovelluksissa se tehdään näin. Toisaalta korvaustaulukko on kriittinen elementti koko salauksen vahvuuden varmistamiseksi. Väärän taulukon valinta voi johtaa siihen, että salaus rikkoutuu helposti tunnetuilla kryptausanalyysimenetelmillä. Korvaussolmujen kehittämiskriteerit ovat seitsemän sinetin salaisuus, ja FAPSI ei todennäköisesti jaa sitä yleisölle lähitulevaisuudessa. Lopulta, jotta voit sanoa, onko tämä korvaustaulukko hyvä vai huono, sinun on käytettävä valtava määrä työtä - useita tuhansia mies- ja konetunteja. Kun taulukko on valittu ja käytetty, se voidaan vaihtaa, jos ja vain, jos salaus sen käytössä osoittautui haavoittuvaksi jollekin toiselle kryptausanalyysille. Siksi paras valinta salauksen keskimääräiselle käyttäjälle on valita yksi useista julkisiksi tulleista taulukoista. Esimerkiksi hash-funktiostandardista se on myös "keskuspankkitoimintaa"; tietoa näistä taulukoista löytyy avoimesta lehdestä ja jopa Internetistä, jos etsit hyvin.

Niille, jotka eivät ole tottuneet ottamaan helpointa tietä, alla on yleinen kaavio laatutaulukoiden hankkimiseksi:

1. Ympärillä tai toisella menetelmällä kehität kahdeksan korvaavan solmun joukon, joilla on taatut epälineaarisuusominaisuudet. Tällaisia ​​menetelmiä on useita, yksi niistä on ns. taivutettujen funktioiden käyttö.
2. Tarkistat yksinkertaisimpien "laatukriteerien" toteutumisen - esimerkiksi ne, jotka on julkaistu DES-korvaussolmuille. Tässä on joitain yleisempiä huomioita tästä pistemäärästä: Jokainen korvaussolmu voidaan kuvata neljällä loogisella funktiolla neljästä loogisesta argumentista. Jos nämä toiminnot ovat kirjoitettu minimaalinen muoto(eli pienimmällä mahdollisella lausekkeen pituudella) eivät ole tarpeeksi monimutkaisia, tällainen korvaava solmu hylätään. Lisäksi koko korvaustaulukon yksittäisten funktioiden tulee erota toisistaan ​​riittävästi. Tässä vaiheessa monet tarkoituksellisesti huonolaatuiset pöydät poistetaan.
3. Valitsemasi taulukot sisältävää salausta varten rakenna erilaisia ​​pyöreitä malleja, jotka vastaavat erilaisia ​​kryptausanalyysityyppejä, ja mittaa vastaavat "profiilin" ominaisuudet. Joten lineaarista kryptausanalyysiä varten rakenna salauskierroksen lineaarinen tilastollinen analogi ja laske "profiilin" ominaisuus - epälineaarisuusindeksi. Jos se osoittautuu riittämättömäksi, korvaustaulukko hylätään.
4. Lopuksi, käyttämällä edellisen kappaleen tuloksia, kohdista salaus valitsemasi taulukon kanssa intensiiviseen tutkimukseen - yritä kryptausanalyysiä kaikilla tunnetuilla menetelmillä. Tämä vaihe on vaikein ja aikaa vievin. Mutta jos se tehdään laadukkaasti, niin suurella todennäköisyydellä voidaan todeta, ettei pelkkä kuolevainen avaa salausta valitsemillasi taulukoilla, ja on mahdollista, että se on liian kovaa. erikoispalvelut.

On kuitenkin mahdollista tehdä paljon helpommin. Asia on siinä, että mitä enemmän salauskierroksia on, sitä vähemmän yhden kierroksen turvallisuusominaisuuksilla on vaikutusta koko salauksen turvallisuuteen. GOSTissa on jopa 32 kierrosta - enemmän kuin melkein kaikissa samanlaisen arkkitehtuurin salakirjoissa. Siksi useimmissa kotimaisissa ja kaupallisissa sovelluksissa riittää korvaussolmujen hankkiminen itsenäisinä satunnaisina lukujen 0-15 permutaatioina. Tämä voidaan käytännössä toteuttaa esimerkiksi sekoittamalla kuudentoista kortin pakkaa, joista jokaiselle on määritetty yksi määritellyn alueen arvoista.

Korvaustaulukon osalta on syytä huomata vielä yksi mielenkiintoinen seikka. 32-3- ja 32-R-salausjaksojen palautuvuus ei edellytä, että korvaavat solmut ovat lukujen permutaatioita välillä 0-15. Kaikki toimii, vaikka korvaavassa solmussa olisi päällekkäisiä elementtejä ja korvauksen määrää tällainen solmu. , on peruuttamaton - tässä tapauksessa salauksen vahvuus kuitenkin heikkenee. Miksi näin on, sitä ei käsitellä tässä artikkelissa, mutta itse tosiasian tarkistaminen ei ole vaikeaa. Tätä varten riittää, että yrität ensin salata ja sitten purkaa tietolohko käyttämällä tällaista "alempi" korvaustaulukkoa, jonka solmut sisältävät päällekkäisiä arvoja.

Muunnelmia GOST-teemaan

Hyvin usein salaustietojen suojausjärjestelmässä käytettäväksi tarvitaan algoritmi, jonka toteutusnopeus on suurempi kuin GOST:n, eikä niin suurta kryptografista vahvuutta tarvita. Tyypillinen esimerkki tällaisista tehtävistä ovat erilaiset sähköiset pörssikaupankäyntijärjestelmät, jotka hallitsevat kaupankäyntiistuntoja reaaliajassa. Tässä tarvitaan salausalgoritmeja, jotta järjestelmän toimintatietojen salauksen purkaminen istunnon aikana (tiedot tehdyistä tilauksista, tehdyistä kaupoista jne.) olisi mahdotonta, mutta sen jälkeen nämä tiedot ovat pääsääntöisesti jo hyödyttömiä. hyökkääjille. Toisin sanoen vaaditaan vain muutaman tunnin taattua sinnikkyyttä, mikä on kaupankäyntiistunnon tyypillinen pituus. On selvää, että täysimittaisen GOST:n käyttö tässä tilanteessa olisi tykin ampumista varpusiin.

Miten tässä ja vastaavissa tapauksissa edetä salauksen nopeuden lisäämiseksi? Vastaus on pinnalla - käytä salauksen muunnelmaa, jossa on vähemmän perusvaiheita (kierroksia) perusjaksoissa. Kuinka monta kertaa vähennämme salauskierrosten määrää, suorituskyky kasvaa saman verran. Tämä muutos voidaan saavuttaa kahdella tavalla - lyhentämällä avaimen pituutta ja vähentämällä avaimen "hakujaksojen" määrää. Muista, että perussalausjaksojen perusvaiheiden määrä on N=n m, missä n on avaimen 32-bittisten elementtien lukumäärä, m- avainelementtien käyttöjaksojen lukumäärä standardissa n=8, m=4. Voit pienentää mitä tahansa näistä numeroista, mutta yksinkertaisin vaihtoehto on lyhentää avaimen pituutta vaikuttamatta sen käyttöjärjestelmään.

On selvää, että työn nopeuttamisen hinta on salauksen vahvuuden heikkeneminen. Suurin vaikeus on siinä, että tämän laskun suuruutta on melko vaikea arvioida enemmän tai vähemmän tarkasti. Ilmeisesti ainoa mahdollinen tapa tehdä tämä on tutkia salausmuunnoksia, joissa on "täysin" rajoitetut kryptografisen muunnosjaksot. On selvää, että ensinnäkin tämä edellyttää turvaluokiteltujen tietojen käyttöä, jotka vain GOSTin kehittäjät omistavat, ja toiseksi se on erittäin työlästä. Siksi yritämme nyt antaa erittäin, hyvin karkean arvion, joka perustuu vain yleisiin kaavoihin.

Mitä tulee salauksen kestävyyteen "laajuisilla" menetelmillä tapahtuvalle murtamiselle eli "raakavoiman" hyökkäykselle, kaikki on täällä enemmän tai vähemmän selvää: 64-bittinen avain on jossain partaalla, että se on tämän tyyppisen saatavilla. hyökkäyksen salaus, jonka avain on vähintään 96 bittiä (muista, että avaimen tulee sisältää kokonaislukumäärä 32-bittisiä elementtejä) on varsin vahva sitä vastaan. Todellakin, muutama vuosi sitten yhdysvaltalainen entinen salausstandardi DES joutui toistuvasti raa'alla voimalla hakkerointiin - ensin globaalin Internetin pohjalta järjestynyt tietokoneverkko ja sitten erikoistunut, ts. erityisesti tähän tarkoitukseen suunniteltu tietokone. Oletetaan, että GOST:n standardiversio, kun se on toteutettu ohjelmistossa nykyaikaisissa prosessoreissa, toimii neljä kertaa nopeammin kuin DES. Sitten 8-kierroksen "alennettu GOST" toimii 16 kertaa nopeammin kuin DES. Oletetaan myös, että DES-hakkeroinnin jälkeen laskentatekniikan suorituskyky on Mooren lain mukaan nelinkertaistunut. Tuloksena saamme, että nyt yhden 64-bittisen avaimen varmennus "pienennetylle GOST:lle" kahdeksalla jaksolla on 64 kertaa nopeampi kuin yhden DES-avaimen varmennus suoritettiin kerran. Siten tämän GOST-version etu DES:iin verrattuna raa'an voiman hyökkäyksen monimutkaisuuden suhteen pienenee arvosta 2 64–56 = 2 8 = 256 arvoon 256 / 64 = 4 kertaa. Samaa mieltä, tämä on hyvin harhaanjohtava ero, melkein ei mitään.

On paljon vaikeampaa arvioida GOST:n heikenneiden muutosten kestävyyttä "intensiivisille" kryptausanalyysimenetelmille. Yleinen kuvio voidaan kuitenkin jäljittää tässäkin. Tosiasia on, että monien tällä hetkellä vahvimpien kryptausanalyysityyppien "profiili"-ominaisuudet riippuvat eksponentiaalisesti salauskierrosten lukumäärästä. Joten lineaarisessa krypta-analyysissä (LCA) tämä on lineaarisuusominaisuus L :

missä C ja ovat vakioita, R on kierrosten lukumäärä. Samanlainen suhde on olemassa differentiaalisella kryptoanalyysillä. "Fyysisen merkityksensä" mukaan kaikki tämänkaltaiset ominaisuudet ovat todennäköisyyksiä. Yleensä kryptausanalyysiin tarvittavan alkutiedon määrä ja sen monimutkaisuus ovat kääntäen verrannollisia tällaisiin ominaisuuksiin. Tästä seuraa, että nämä työvoimaintensiteetin indikaattorit kasvavat eksponentiaalisesti perussalausvaiheiden määrän kasvaessa. Siksi, jos kierrosten määrää vähennetään useita kertoja, tunnetuimpien analyysityyppien monimutkaisuus muuttuu hyvin likimääräisesti ja karkeasti tämän tehon juureksi alkuperäisestä määrästä. Tämä on erittäin suuri pudotus kestävyydessä.

Toisaalta GOST on suunniteltu suurella turvamarginaalilla ja se kestää nykyään kaikkia tunnettuja kryptoanalyysityyppejä, mukaan lukien differentiaali- ja lineaarianalyysi. Mitä tulee LCA:han, tämä tarkoittaa, että sen onnistuneeseen toteuttamiseen tarvitaan enemmän "avoin lohko – salattu lohko" -pareja kuin "luonnossa on", eli enemmän kuin 2 64 . Edellä esitetyn perusteella tämä tarkoittaa, että 16 kierroksen GOST:n onnistunut LCA vaatii vähintään lohkoja tai 2 35 tavua tai 32 Gt tietoa ja 8 kierroksen GOST:n osalta vähintään lohkoja tai 2 19 tavua tai 0,5 megatavua.

Päätelmät kaikesta edellä mainitusta on esitetty seuraavassa taulukossa, jossa on yhteenveto GOST:n supistettujen versioiden ominaisuuksista.

Kaksi viimeistä vaihtoehtoa, 12 ja 8 kierrosta, pystyvät tarjoamaan erittäin, hyvin rajoitetun suojan ajallisesti. Niiden käyttö on perusteltua vain tehtävissä, joissa suljetuista tiedoista vaaditaan vain lyhytaikaista, useiden tuntien luokkaa olevaa salassapitoa. Yksi mahdollinen sovellusalue näille heikkoille salakirjoille on sähköisten pörssikauppajärjestelmien UDP-liikenteen sulkeminen. Tässä tapauksessa jokainen datapaketti (datagrammi, keskimmäinen "D" UDP-lyhenteestä) salataan erillisellä 64-bittisellä avaimella ja itse avain on salattu istuntoavaimella (avain, jonka laajuus on yksi viestintäistunto kahden tietokoneen välillä ) ja lähetetään tietojen mukana.

Ennen kuin lopetan GOSTin supistettujen versioiden kanssa, sanon, että kaikki yllä olevat näkökohdat ovat erittäin spekulatiivisia. Standardi tarjoaa kestävyyden vain yhdelle, 32-kierroksiselle vaihtoehdolle. Ja kukaan ei voi antaa sinulle takuita siitä, että salauksen supistettujen muunnelmien murtumiskestävyys muuttuu yllä kuvatulla tavalla. Jos kuitenkin päätät käyttää niitä kehitystyössäsi, muista, että olet astunut hyvin horjuvalle maalle, joka voi pudota jalkojen alta minä hetkenä hyvänsä. Koska salausnopeus on sinulle kriittinen, sinun pitäisi ehkä harkita nopeamman salauksen tai tehokkaamman tietokoneen käyttöä? Toinen seikka, jonka vuoksi tämä kannattaa tehdä, on se, että heikennetyt GOST-versiot ovat mahdollisimman herkkiä käytettyjen korvaavien yksiköiden laadulle.

Käsillä olevalla ongelmalla on myös varjopuolensa. Entä jos salausnopeus ei ole kriittinen ja vahvuusvaatimukset ovat erittäin tiukat? GOSTin vastustuskyvyn lisäämiseksi on kaksi tapaa - kutsumme niitä ehdollisesti "laajaksi" ja "intensiiviseksi". Ensimmäinen näistä ei ole muuta kuin pelkkä salauskierrosten määrän lisääminen. Minulle ei ole täysin selvää, miksi tätä saattaisi todella tarvita, koska kotimainen standardi antaa jo ilman sitä tarvittavan vakauden. Jos kuitenkin kärsit vainoharhaisuudesta enemmän kuin vaadittu taso (ja kaikki "tiedonsuojelijat" ovat yksinkertaisesti velvollisia kärsimään siitä, tämä on ammattisoveltuvuuden ehto, ainoa kysymys on tapauksen vakavuus :), tämä auttaa sinua hieman rauhoittumaan. Jos olet epävarma tästä KGB-salauksesta tai käyttämästäsi korvaustaulukosta, tupla, nelinkertaista jne. kierrosten määrä - valitse moninkertaisuus tapauksesi vakavuuden perusteella. Tämän lähestymistavan avulla voit todella lisätä salauksen vahvuutta - jos aiemmin kryptausanalyysi oli yksinkertaisesti mahdotonta, nyt se on mahdotonta neliössä!

Hankalempi ja mielenkiintoisempi on kysymys siitä, onko mahdollista lisätä salauksen vahvuutta muuttamatta pääsalausvaiheiden määrää ja rakennetta. Yllättäen vastaus tähän kysymykseen on kyllä, vaikka poljemme jälleen spekulaation horjuvalla pohjalla. Tosiasia on, että GOST:ssa sen on tarkoitus korvata päämuunnosvaiheessa 4 bitillä 4, mutta käytännössä (puhumme tästä myöhemmin) kaikki ohjelmistototeutukset suorittavat korvaamisen tavu kerrallaan, ts. 8 x 8 bittiä - tämä tehdään tehokkuussyistä. Jos suunnittelemme sellaisen korvaavan välittömästi 8-bittiseksi, parannamme merkittävästi yhden kierroksen ominaisuuksia. Ensinnäkin "diffuusio"-ominaisuus tai "lumivyöry" -indikaattori kasvaa - yksi bitti lähdedataa ja/tai avain vaikuttaa useampaan tulokseen. Toiseksi suuremmille substituutiosolmuille voidaan saada alhaisemmat differentiaaliset ja lineaariset ominaisuudet, mikä vähentää salauksen herkkyyttä samantyyppisille kryptausanalyysille. Tämä pätee erityisesti alennetuille GOST-sykleille ja 8- ja 12-kierrosvaihtoehdoille tällainen vaihe on yksinkertaisesti välttämätön. Tämä kompensoi jonkin verran kestävyyden menetystä, joka johtuu kierrosten määrän vähenemisestä. Tämän tekniikan käyttöä vaikeuttaa se, että sinun on suunniteltava tällaiset "lisätyt" korvaavat solmut itse. Ja myös se, että suurempia solmuja on yleensä huomattavasti vaikeampi suunnitella kuin pienempiä.

Epätyypillinen standardin käyttö.

Tietenkin GOST-salausalgoritmien päätarkoitus on tietojen salaus ja jäljitelmäsuojaus. Niitä löytyy kuitenkin muista sovelluksista, jotka liittyvät luonnollisesti tiedon suojaan. Puhutaanpa niistä lyhyesti:

1. Gamma-tilassa tapahtuvaa salausta varten GOST mahdollistaa kryptografisen gamman luomisen - bittisarjan, jolla on hyvät tilastolliset ominaisuudet ja korkea kryptografinen vahvuus. Lisäksi tätä gammaa käytetään avoimen tiedon muokkaamiseen, mikä johtaa salattuihin tietoihin. Tämä ei kuitenkaan ole ainoa mahdollinen kryptografisen gamman sovellus. Tosiasia on, että sen kehittämisen algoritmi on pseudosa(PRNG), jolla on erinomaiset ominaisuudet. Tietenkään ei ole kovin järkevää käyttää sellaista PRNG:tä, jossa vaaditaan vain generoidun sekvenssin tilastollisten ominaisuuksien saamista, eikä kryptografista vahvuutta tarvita, se ei ole kovin järkevää - näihin tapauksiin on olemassa paljon tehokkaampia generaattoreita. Mutta erilaisille tietoturvaan liittyville sovelluksille tällainen lähde on erittäin hyödyllinen:

• Kuten edellä mainittiin, gammaa voidaan käyttää "raaka-aineena" avainten luomiseen. Tätä varten sinun tarvitsee vain saada halutun pituinen gammasegmentti - 32 tavua. Tällä tavalla avaimia voidaan tehdä tarpeen mukaan, eikä niitä tarvitse tallentaa - jos tällaista avainta tarvitaan uudelleen, se on tarpeeksi helppoa luoda uudelleen. Tarvitsee vain muistaa, millä avaimella se alun perin luotiin, mitä synkronointiviestiä käytettiin ja mistä generoidun gamman tavusta avain alkoi. Kaikki tiedot käytettyä avainta lukuun ottamatta eivät ole salaisia. Tällä lähestymistavalla on helppo hallita melko monimutkaista ja haarautunutta avainjärjestelmää käyttämällä vain yhtä "pääavainta".
• Samoin kuin edellisessä, gammaa voidaan käyttää salasanojen luomisen "raaka-aineena". Tässä voi herää kysymys, miksi niitä ylipäätään pitää generoida, eikö ole helpompaa keksiä niitä tarpeen mukaan. Tämän lähestymistavan epäonnistumisen osoittivat selvästi useita tietoverkoissa tapahtuneita tapauksia, joista suurin oli "Morris-madon" aiheuttama Internetin vuorokausillinen halvaantuminen marraskuussa 1988. Yksi tapa, jolla haittaohjelma tunkeutui tietokoneeseen, oli salasanan arvaus: ohjelma yritti päästä järjestelmään lajittelemalla peräkkäin useita satoja salasanoja sisäisestä luettelostaan, ja merkittävässä osassa tapauksia se onnistui. Ihmisen fantasia salasanojen keksimisessä osoittautui erittäin huonoksi. Siksi niissä organisaatioissa, joissa turvallisuuteen kiinnitetään asianmukaista huomiota, salasanat generoi ja jakaa käyttäjille turvajärjestelmän ylläpitäjä. Salasanan luominen on hieman monimutkaisempaa kuin avainten luominen, koska tässä tapauksessa "raaka" binäärigamma on muutettava merkkimuotoon, eikä vain "leikattava" paloiksi. Lisäksi yksittäiset arvot on ehkä hylättävä, jotta varmistetaan, että kaikki aakkosten merkit näkyvät yhtä todennäköisesti salasanassa.
• Toinen tapa käyttää kryptografista kirjoa on taattu tietojen poistaminen magneettisilta tietovälineiltä. Tosiasia on, että vaikka tiedot kirjoitetaan päälle magneettiselle tietovälineelle, aiemmista tiedoista jää jälkiä, jotka voidaan palauttaa asianmukaisella tutkimuksella. Näiden jälkien tuhoamiseksi tällainen päällekirjoitus on suoritettava useita kertoja. Kävi ilmi, että tiedot joutuisivat kirjoittamaan uudelleen mediaan harvemmin, jos tällaisessa menettelyssä käytetään satunnaisia ​​tai näennäissatunnaisia ​​tietoja, jotka jäävät tuntemattomiksi asiantuntijoille, jotka yrittävät palauttaa päällekirjoitetun tiedon. Gammasalauksesta on hyötyä tässä.

2. Salausgamman lisäksi myös itse kryptografista muunnosa voidaan käyttää tarpeisiin, jotka eivät liity suoraan salaukseen:

• Tiedämme, että yksi tällaisista GOST-käyttömahdollisuuksista on simuloidun lisäyksen kehittäminen tietotaulukoille. Minkä tahansa lohkosalauksen, mukaan lukien GOST, perusteella on kuitenkin melko helppoa rakentaa kaavio yksisuuntaisen hash-funktion laskemiseksi, jota kirjallisuudessa kutsutaan myös MDC:ksi, joka eri lähteissä tarkoittaa muuta tunnistuskoodia / manipulointi (M muutos/ M anipulaatio D etection C ode) tai viestin tiivistelmä (M essee D igest C oodi). Ensimmäinen transkriptio ilmestyi kirjallisuudessa paljon aikaisemmin, toisen, lyhyemmän, mielestäni ne keksivät, jotka eivät muistaneet ensimmäistä :) - se oli vitsi. MDC:tä voidaan käyttää suoraan jäljitelmäsuojausjärjestelmissä jäljitelmän lisäyksen analogina, joka ei kuitenkaan riipu salaisesta avaimesta. Lisäksi MDC:tä käytetään laajalti sähköisen digitaalisen allekirjoituksen (EDS) järjestelmissä, koska useimmat näistä menetelmistä on suunniteltu siten, että kiinteän kokoinen tietolohko on kätevä allekirjoittaa. Kuten tiedät, käsitellyn standardin GOST 28147-89 perusteella rakennetaan Venäjän federaation standardi yksisuuntaisen hash-funktion laskemiseksi GOST R34.11-94.
• Vähemmän tiedetään, että minkä tahansa lohkosalauksen, mukaan lukien GOST, perusteella voidaan rakentaa täysin toimiva EDS-järjestelmä, jossa on salainen allekirjoitusavain ja avoin varmennusyhdistelmä. Monista syistä tämä järjestelmä ei ole saanut laajaa käytännön leviämistä, mutta joissain tapauksissa sitä voidaan silti pitää erittäin houkuttelevana vaihtoehdona "matemaattisille" EDS-järjestelmille, jotka ovat tällä hetkellä hallitsevia maailmassa.

Kirjallisuus

Tietojenkäsittelyjärjestelmät. Kryptografinen suojaus. Kryptografinen muunnosalgoritmi GOST 28147-89. Osavaltio. Com. Neuvostoliitto standardien mukaan, M., 1989. ftp://ftp.wtc-ural.ru/pub/ru.crypt/GOST-28147
Shannon Claude. Salaisten järjestelmien matemaattinen teoria. Kokoelmassa "Työteoksia informaatioteoriasta ja kybernetiikasta", M., IL, 1963, s. 333-369. http://www.enlight.ru/crypto/articles/shannon/shann__i.htm
Federal Information Processing Standard (FIPS) 197, Advanced Encryption Standard (AES), Federal Register Voi. 66, nro. 235 / torstai 6. joulukuuta 2001 / Ilmoitukset, s. 63369–63371. http://csrc.nist.gov/encryption/aes/
Feistel Horst. Salaus ja tietoturva. A. Vinokurovin käännös, julkaisija Horst Feistel. Cryptography and Computer Privacy, Scientific American, toukokuu 1973, voi. 228, nro 5, s. 15-23. http://www.enlight.ru/crypto/articles/feistel/feist_i.htm
Schneier Bruce. Sovellettu kryptografia. 2. painos Protokollat, algoritmit ja lähdetekstit C-kielellä., M., "Triumph", 2002 http://www.ssl.stu.neva.ru/psw/crypto/appl_rus/appl_cryp.htm
Menezes Alfred, van Oorschot Paul, Vanstone Scott. Sovellettavan kryptografian käsikirja. http://www.cacr.math.uwaterloo.ca/hac/
Vinokurov Andrey. Miten lohkosalaus on rakennettu? Käsikirjoitus. http://www.enlight.ru/crypto/articles/vinokurov/blcyph_i.htm
Vinokurov Andrey. Salausongelmia sähköisessä iNFUSED BYTES -lehdessä verkossa. http://www.enlight.ru/crypto/articles/ib/ib.htm
Vinokurov Andrey, Primenko Eduard. Raportin teksti "Venäjän federaation ja Yhdysvaltojen salausstandardien ohjelmistojen käyttöönotosta", informatisointikonferenssi, Moskova, MEPhI, 28.-29.1.2001. Julkaistu konferenssijulkaisussa.
Tietotekniikka. Tietojen kryptografinen suojaus. Hash-funktio GOST R34.11-94, Gosstandart RF, M., 1994.

Tunnettu tutkija, algebrallisen krypta-analyysin perustaja Nicolas Courtois väittää, että lähitulevaisuudessa kansainväliseksi standardiksi piti GOST-lohkosalaus on todellakin murrettu ja odottaa tulevaisuudessa monia julkaisuja, joiden pitäisi kehittyä. hänen ajatuksensa tämän algoritmin epävakaudesta.

Seuraavassa on lyhyitä otteita tästä työstä, jota voidaan pitää hälyttävänä hyökkäyksenä kansainvälisen standardoinnin huipulla (kirjailija tunnettiin samanlaisista liioituksista AES:n suhteen, mutta hänen työllään oli silloin suuri teoreettinen vaikutus kryptausanalyysiin, mutta ei vielä johtanut käytännön hyökkäyksiin itse AES:tä vastaan). Mutta ehkä tämä on myös todellinen varoitus "sukellus tailspin" -vaiheen alkamisesta, joka voi päättyä kansallisen salausstandardin romahtamiseen, kuten tapahtui SHA-1-hajautusalgoritmin ja "de facto" -algoritmin tapauksessa. MD5 hajautusalgoritmi.

GOST 28147-89 standardoitiin vuonna 1989, ja siitä tuli ensimmäistä kertaa virallinen standardi luottamuksellisten tietojen suojaamiseen, mutta salausspesifikaatio pysyi suljettuna. Vuonna 1994 standardin luokitus poistettiin, se julkaistiin ja käännettiin englanniksi. Analogisesti AES:n (ja toisin kuin DES:n) kanssa, GOST saa suojata turvaluokiteltuja tietoja ilman rajoituksia Venäjän standardissa määritetyllä tavalla. Että. GOST ei ole DES:n analogi, vaan kilpailija 3-DES:lle kolmella itsenäisellä avaimella tai AES-256:lla. Ilmeisesti GOST on melko vakava salaus, joka täyttää sotilaalliset kriteerit ja joka on luotu vakavimpien sovellusten odotuksella. Ainakin kaksi GOST S-laatikkosarjaa on tunnistettu venäläisten pankkien sovellusten perusteella. Näiden pankkien on käytävä salaista viestintää satojen sivukonttoreiden kanssa ja suojattava miljardeja dollareita petollisilta varkauksilta.

GOST on lohkosalaus, jolla on yksinkertainen Feistel-rakenne, lohkokoko 64 bittiä, 256-bittinen avain ja 32 kierrosta. Jokainen kierros sisältää modulo 2^32 avaimen lisäyksen, kahdeksan 4-bittisen S-laatikon joukon ja yksinkertaisen 11-bittisen kierron. GOST:n ominaisuus on kyky tallentaa S-laatikoita salassa, mikä voidaan esittää toisena avaimena, joka kasvattaa tehokkaan avainmateriaalin 610 bittiin. Yksi S-laatikoiden sarja julkaistiin vuonna 1994 osana GOST-R 34.11-94 hash-funktiospesifikaatiota, ja Schneierin mukaan sitä käytti Venäjän keskuspankki. Se tuli myös RFC4357-standardiin osassa "id-GostR3411-94-CryptoProParamSet". Schneierin kirjan lopussa oli virhe lähdekoodeissa (S-box-järjestyksessä). Tarkin alkuperäisen venäläisen alkuperän viitetoteutus löytyy nyt OpenSSL-kirjastosta. Jos salaisia ​​S-laatikoita käytetään jossain, niin ne voidaan poimia ohjelmistototeutuksista ja mikropiireistä, itse asiassa vastaavia teoksia on julkaistu.

GOST on vakava kilpailija

Erittäin suuren avainkoon lisäksi GOST:lla on huomattavasti alhaisemmat suorituskustannukset kuin AES:llä ja muilla vastaavilla salausjärjestelmillä. Itse asiassa se maksaa paljon vähemmän kuin AES, joka vaatii neljä kertaa enemmän laitteistologiikkaportteja paljon pienemmän suojausvaatimuksen saavuttamiseksi.

Ei ole yllättävää, että GOST:sta on tullut Internet-standardi, erityisesti se sisältyy moniin kryptokirjastoihin, kuten OpenSSL ja Crypto++, ja siitä on tulossa yhä suositumpi alkuperämaansa ulkopuolella. Vuonna 2010 GOST jätettiin ISO-standardointiin maailmanlaajuiseksi salausstandardiksi. Erittäin pieni määrä algoritmeja on onnistunut nousemaan kansainvälisiksi standardeiksi. ISO/IEC 18033-3:2010 kuvaa seuraavat algoritmit: neljä 64-bittistä salausta - TDEA, MISTY1, CAST-128, HIGHT - ja kolme 128-bittistä salausta - AES, Camellia, SEED. GOST ehdotetaan lisättäväksi samaan ISO/IEC 18033-3 -standardiin.

Ensimmäistä kertaa teollisen standardoinnin historiassa olemme tekemisissä niin kilpailukykyisen algoritmin kanssa kustannus- ja turvallisuustason optimaalisuuden kannalta. GOST:lla on takanaan 20 vuoden kryptoanalyysiyrityksiä, ja viime aikoihin asti sen sotilastason turvallisuus oli kiistaton.

Kuten kirjoittaja äskettäin sai tietää yksityisestä kirjeenvaihdosta, useimmat maat äänestivät GOST:ia vastaan ​​ISO-äänestyksessä Singaporessa, mutta tämän äänestyksen tuloksia käsitellään edelleen ISO SC27:n täysistunnossa, joten GOST on edelleen standardointiprosessissa. tämän teoksen julkaisuaika.

Asiantuntijoiden mielipiteet GOST: sta

Mikään saatavilla olevasta tiedosta ja GOST-kirjallisuudesta ei anna syytä uskoa, että salaus voi olla epävarma. Päinvastoin, suuri avaimen koko ja suuri määrä kierroksia tekevät GOSTista ensi silmäyksellä sopivan vuosikymmenien käyttöön.

Jokainen Mooren lain tunteva ymmärtää, että teoriassa 256-bittiset avaimet pysyvät turvassa vähintään 200 vuotta. GOST:ia ovat tutkineet laajasti johtavat kryptografian asiantuntijat, jotka ovat kuuluisia lohkosalausanalyysin alalla, kuten Schneier, Biryukov, Dankelman, Wagner, monet australialaiset, japanilaiset ja venäläiset tutkijat, salausasiantuntijat ISO:sta ja kaikki tutkijat ovat ilmaisseet, että kaikki näyttää tältä, että hän voi olla tai hänen pitäisi olla turvassa. Vaikka yleisesti tiedetään, että itse GOST-rakenne on äärimmäisen heikko esimerkiksi verrattuna DES:ään, diffuusio ei ole niin hyvä, mutta tämä on aina johtunut siitä, että tämä on kompensoitava suurella määrällä kierrosta (32) sekä lisäepälineaarisuutta ja diffuusiota modulo-lisäyksen avulla.

Biryukov ja Wagner kirjoittivat: "Suuri määrä kierroksia (32) ja hyvin tutkittu Feistel-rakenne yhdistettynä peräkkäisiin Shannon-korvauksiin-permutaatioihin tarjoavat vankan perustan GOST-turvallisuudelle." Samassa teoksessa luemme: "huomattavan ajan ja vaivan investoinnin jälkeen standardin kryptausanalyysissä ei ole edistytty avoimessa kirjallisuudessa." Näin ollen ei ollut merkittäviä hyökkäyksiä, jotka mahdollistaisivat salauksen purkamisen tai avainten palautuksen realistisessa skenaariossa, jossa GOST:ia käytetään salauksessa useilla eri satunnaisilla avaimilla. Sitä vastoin GOST:ssa on paljon töitä hyökkäyksille heikkoja avaimia vastaan, hyökkäyksiä niihin liittyvillä avaimilla, hyökkäyksiä salaisten S-laatikoiden palauttamiseen. Crypto-2008:ssa esiteltiin tähän salaukseen perustuva hash-funktion hakkerointi. Kaikissa hyökkäyksissä hyökkääjällä on paljon suurempi vapaus kuin hänelle yleensä sallitaan. Perinteisissä satunnaisesti valittuja avaimia käyttävissä salaussovelluksissa ei ole toistaiseksi löydetty vakavia kryptografisia hyökkäyksiä GOST:iin, mikä ilmaistiin vuonna 2010 viimeisellä lauseella: "huolimatta kryptanalyytikkojen merkittävistä ponnisteluista viimeisten 20 vuoden aikana, GOST ei ole vieläkään rikki" ( Axel Poschmann, San Ling ja Huaxiong Wang: 256-bittinen standardisoitu salaus 650 GE:n GOSTille uudelleen, julkaisussa CHES 2010, LNCS 6225, s. 219–233, 2010).

Lineaarinen ja differentiaalianalyysi GOST

Schneierin tunnetusta kirjasta luemme: "Differentiaalista ja lineaarista kryptausanalyysiä vastaan ​​GOST on luultavasti vankempi kuin DES." Pääarvioinnin GOST:n turvallisuudesta antoivat Gabidulin ym. Heidän tulokset ovat erittäin vaikuttavia: suojaustasolla 2^256 viisi kierrosta riittää suojaamaan GOST:ia lineaariselta kryptausanalyysiltä. Lisäksi, vaikka S-laatikot korvataan identtisillä ja salauksen ainoa epälineaarinen toiminta - additio modulo 2 ^ 32 - salaus kestää lineaarista kryptausanalyysiä 6 kierroksen jälkeen 32:sta. GOST-differentiaalinen kryptausanalyysi näyttää suhteellisen helpommalta ja herättää enemmän huomiota. Tason 2^128 tietoturvatutkijat (Vitaly V. Shorin, Vadim V. Jelezniakov ja Ernst M. Gabidulin: Linear and Differential Cryptanalysis of Russian GOST, Preprint toimitettu Elsevier Preprintille 4. huhtikuuta 2001) olettivat riittävän pysyvyyden 7 kierroksen tasolla. Heidän mukaansa GOSTin hakkerointi yli viidellä kierroksella on "erittäin vaikeaa". Lisäksi kaksi japanilaista tutkijaa ovat osoittaneet, että klassisella suoralla differentiaalihyökkäyksellä, jolla on yksi erotusominaisuus, on erittäin pieni todennäköisyys läpäistä suuri määrä kierroksia. Perustuen siihen tosiasiaan, että tutkitaan riittävän "hyvää" iteratiivista differentiaalista ominaisuutta rajoitetulle määrälle kierroksia (jolla itsessään on läpäisyn todennäköisyys enintään 2-11,4 kierrosta kohti), yhteensopivien avainten joukon arvot ovat pienempiä. kuin puolet. Täysikierroksisella GOST:lla tällainen yhdellä ominaisuudella varustettu hyökkäys toimii vain merkityksettömän pienellä osalla avaimista luokkaa 2-62 (ja jopa tässä pienessä osassa sen todennäköisyys ohittaa enintään 2 -360).

Kehittyneemmät hyökkäykset sisältävät useita differentiaaleja tiettyjen mallien mukaan, kuten käyttämällä erillisiä S-laatikoita, joissa on nolla eroa, kun taas muilla biteillä on nollasta poikkeava ero. Puhumme syrjintähyökkäyksistä, jotka perustuvat GOSTin huonoihin diffuusioominaisuuksiin. Paras näistä hyökkäyksistä toimii 17 GOST-kierrosta vastaan, riippuu avaimesta, ja sillä on itsessään erittäin heikko erottaja satunnaisista tiedoista, jotta sitä voidaan jotenkin käyttää avaimen tiedon saamiseksi.

Liuku- ja heijastushyökkäykset

Biryukovin ja Wagnerin mukaan GOSTin rakenne, mukaan lukien käänteinen aliavaimien järjestys viimeisillä kierroksilla, tekee siitä kestävän liukastumishyökkäyksiä (ns. "slide hyökkäyksiä") vastaan. Kuitenkin, koska salauksessa on paljon samankaltaisuutta, tämä sallii avainten käänteishyökkäykset kiinteiden pisteiden ja "heijastusominaisuuksien" yhdistelmille (niin sanotut "heijastavat hyökkäykset") tietyille heikkoille avaimille. . Tämän hyökkäyksen monimutkaisuus on 2^192 ja 2^32 täsmääviä selkokielisiä tekstejä.

Uusimmat tulokset

Uudet hyökkäykset käyttävät myös reflektiota ja itse asiassa murtavat GOST:n, joka esiteltiin FSE 2011 -konferenssissa.Nämä hyökkäykset löysivät myös itsenäisesti tämän työn tekijän toimesta. Hyökkäys vaatii 2^132 tavua muistia, mikä on itse asiassa huonompaa kuin hitaammat hyökkäykset pienemmillä muistivaatimuksilla.

Monet uudet samankaltaisuushyökkäykset toimivat kaikkia GOST-avaimia vastaan ​​ja mahdollistavat täyden GOST:n murtamisen 256-bittisellä avaimella, ei vain heikkoille avaimille, kuten aiemmin. Kaikki nämä hyökkäykset vaativat huomattavasti vähemmän muistia ja ovat huomattavasti nopeampia.

Näitä uusia hyökkäyksiä voidaan pitää esimerkkeinä uudesta yleisestä lohkosalauksen salausanalyysin paradigmasta, jota kutsutaan "algebrallisen monimutkaisuuden vähentämiseksi", ja nämä hyökkäykset yleistetään moniin erikoistapauksiin hyökkäyksissä, joissa on tunnetut kiinteät pisteet, lipsahdus, involuutio ja jakso. On tärkeää, että kaikkien näiden hyökkäysten perheessä on sellaisia, jotka mahdollistavat GOST-kryptausanalyysin ilman heijastuksia ja ilman symmetrisiä pisteitä, jotka ilmestyvät laskelmien aikana. Yksi esimerkki on yksinkertainen GOST-hakkerointihyökkäys ilman heijastuksia tässä artikkelissa.

Algebrallinen kryptausanalyysi ja alhaisen datan monimutkaisuuden hyökkäykset pienemmillä pyöreälukuisilla salakirjoilla

Algebralliset hyökkäykset lohko- ja virtasalauksiin voidaan esittää ongelmana ratkaista suuri Boolen algebrallinen yhtälöjärjestelmä, joka seuraa tietyn kryptografisen järjestelmän geometriaa ja rakennetta. Ajatus juontaa juurensa Shannonille. Käytännössä se otettiin käyttöön DES:lle (tämän työn kirjoittaja esitteli ensimmäisen kerran) muodollisena koodausmenetelmänä ja se voi murtaa 6 kierrosta vain yhdelle tunnetulle selväkieliselle tekstille. Manipulointi yhtälöillä perustuu XL-algoritmeihin, Gröbner-kantoihin, ElimLin-menetelmään, SAT-ratkaisimiin.

Käytännössä algebrallisia hyökkäyksiä on toteutettu hyvin pientä määrää lohkosalauksen kierroksia vastaan, mutta ne ovat jo johtaneet virtasalausten katkeamiseen, ja myös mikrolaitteistojen ultrakevyiden salausten rikkomisessa on onnistuttu. Muistin kokojen ja laskennallisten kustannusarvioiden vaikeuksien vuoksi ne yhdistetään muihin hyökkäyksiin.

Kuinka hakkeroida GOST?

Algebrallinen hyökkäys täyden kierroksen GOST:iin on esitetty yksityiskohtaisemmin käsiteltävänä olevassa julkaisussa. Aiemmassa työssään kirjoittaja on jo hahmotellut 20 algebrallista hyökkäystä GOST:iin ja odottaa niitä suuren määrän lähitulevaisuudessa. Tässä artikkelissa ehdotettu hyökkäys ei ole niistä paras, mutta se avaa yksinkertaisen (ainakin kryptografien ymmärtämään) tavan myöhemmälle kehitykselle luoda erityinen menetelmä GOST:n rikkomiseksi.

Käytännön tulos on toistaiseksi vaatimaton: 2^64 tunnettua selkeää tekstiä ja 2^64 muistia selväteksti/salausteksti-parien tallentamiseen mahdollistavat GOST:n murtamisen 2^8 nopeammin kuin pelkkä raaka voima. Mutta kryptoanalyysin kannalta tämä tekee väitteestä, että "GOST on hakkeroitu" täysin oikeudenmukaiseksi.

johtopäätöksiä

GOST on suunniteltu tarjoamaan sotilaallinen turvallisuustaso 200 vuodeksi eteenpäin. Suurin osa johtavista asiantuntijoista, jotka ovat tutkineet GOST:a, ovat päässeet yksimielisyyteen, että "huolimatta huomattavista kryptanalyyttisistä ponnisteluista yli 20 vuoden ajan, GOST ei ole vielä rikki". Vuonna 2010 GOST nostettiin ISO 18033:ksi maailman salausstandardiksi.

Algebrallista kryptausanalyysiä koskevien käsitysten perusta syntyi yli 60 vuotta sitten. Mutta vasta viimeisen 10 vuoden aikana on kehitetty tehokkaita ohjelmistotyökaluja (osittain) ratkaisemaan monia NP-täydellisiä ongelmia. Useita tietovirran salauksia on rikottu. Tällä menetelmällä on rikottu vain yksi lohkosalaus, itse heikko KeeLoq. Tässä työssä kirjoittaja murtaa tärkeän, tosiasiallisesti käytetyn GOST-salauksen. Hän huomauttaa, että tämä on ensimmäinen kerta historiassa, kun standardoitu tilasalaus on rikki algebrallisen kryptausanalyysin avulla.

Yksinkertainen "MITM with reflection" -hyökkäys GOSTia vastaan ​​on jo esitelty FSE 2011 -konferenssissa. Tässä artikkelissa tarkasteltavassa työssä esitetään toinen hyökkäys vain havainnollistamaan sitä tosiasiaa, kuinka monta hyökkäystä GOSTia vastaan ​​on jo esiintynyt nyt, monet jotka ovat nopeampia, ja itse algebrallinen hyökkäys vaatii paljon vähemmän muistia ja avaa vastustajalle lähes ehtymättömän mahdollisuudet hyökätä salaukseen monin eri tavoin. Myös tässä työssä on osoitettu, ettei hakkerointiin tarvitse käyttää heijastusominaisuutta.

Kirjoittaja väittää, että on ilmeistä, että GOST:ssa on vakavia puutteita, eikä se nyt tarjoa ISO:n vaatimaa vastustasoa. Joukko hyökkäyksiä GOST:ia vastaan ​​esitetään osana algebrallisen kompleksisuuden vähentämisen paradigman vahvistusta.

Lopuksi tutkija panee erityisesti merkille joitain seikkoja, jotka eivät vielä ole lukijan saatavilla, mutta jotka ovat tutkijan tiedossa ja jotka ovat tärkeitä ISO-standardointiprosessin aikana. Tämä hyökkäys ei ole vain "sertifiointi" -hyökkäys GOST:ia vastaan, joka on nopeampaa kuin raakaa voimaa. Itse asiassa GOSTin standardointi nyt olisi erittäin vaarallista ja vastuutonta. Tämä johtuu siitä, että osa hyökkäyksistä on käytännössä toteutettavissa. Jotkut GOST-avaimet voidaan jopa purkaa käytännössä, olivatpa ne sitten heikkoja avaimia tai avaimia tietyistä todellisista GOST-sovelluksista. Aiemmassa työssään kirjoittaja on tarkastellut yksityiskohtaisesti käytännön hyökkäysten mahdollisuutta. Merkittävää on, että "tämä on ensimmäinen kerta historiassa, kun vakava, standardoitu lohkosalaus, joka on suunniteltu suojelemaan sotilastason salaisuuksia ja suunniteltu suojaamaan valtioiden, suurten pankkien ja muiden organisaatioiden valtionsalaisuutta, on murtunut matemaattisen hyökkäyksen seurauksena. "

GOST 28147-89:n määrittelemän algoritmin salausavaimen pituus on 256 bittiä. Se salaa tiedot 64-bittisiksi lohkoiksi (tällaisia ​​algoritmeja kutsutaan lohkoalgoritmeiksi), jotka sitten jaetaan kahteen 32-bittiseen alilohkoon (N1 ja N2) (kuva 1). Alilohko N1 käsitellään tietyllä tavalla, minkä jälkeen sen arvo lisätään alilohkon N2 arvoon (lisäys suoritetaan modulo 2, eli käytetään loogista XOR-toimintoa - "exclusive or"), ja sitten alilohkot vaihdetaan. Tämä muunnos suoritetaan tietyn määrän kertoja ("kierroksia"): 16 tai 32 riippuen algoritmin moodista. Jokaisella kierroksella suoritetaan kaksi operaatiota.

Kuva 1. Algoritmin GOST 28147-89 kaavio.

Ensimmäinen on näppäily. Osalohkon N1 sisältö lisätään modulo 2 avaimen Kx 32-bittiseen osaan. Täysi salausavain esitetään 32-bittisten aliavaimien ketjuna: K0, K1, K2, K3, K4, K5, K6, K7. Yhtä näistä aliavaimista käytetään salausprosessissa pyöreän luvun ja algoritmin toimintatilan mukaan.

Toinen toimenpide on pöydän vaihto. Avaimen päällekkäisyyden jälkeen alilohko N1 jaetaan 8 osaan 4 bittiä, joista kunkin arvo korvataan tämän alilohkon osan korvaustaulukon mukaisesti. Alilohkoa jätetään sitten kierrettynä bittikohtaisesti 11 bittiä.

Taulukkokorvauksia (Substitution box - S-box) käytetään usein nykyaikaisissa salausalgoritmeissa, joten kannattaa selittää, miten tällainen toiminta järjestetään. Lohkojen lähtöarvot kirjoitetaan taulukkoon. Tietyn ulottuvuuden tietolohkolla (tapauksessamme 4-bittisellä) on oma numeerinen esitys, joka määrittää lähtöarvon numeron. Jos S-laatikko näyttää esimerkiksi 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1 ja 4-bittinen lohko "0100" tuli syötteeseen (arvo 4), silloin taulukon mukaan lähtöarvo on 15, eli "1111" (0 a 4, 1 a 11, 2 a 2 ...).

GOST 28147-89:n määrittelemä algoritmi tarjoaa neljä toimintatapaa: yksinkertainen korvaaminen, skaalaus, skaalaus palautteen avulla ja jäljitelmien etuliitteiden luominen. Niissä käytetään samaa yllä kuvattua salausmuunnosta, mutta koska moodien tarkoitus on erilainen, tämä muunnos suoritetaan jokaisessa niistä eri tavalla.

Yksinkertaisessa korvaustilassa suoritetaan edellä kuvatut 32 kierrosta jokaisen 64-bittisen tietolohkon salaamiseksi. Tässä tapauksessa 32-bittisiä aliavaimia käytetään seuraavassa järjestyksessä:

K0, K1, K2, K3, K4, K5, K6, K7, K0, K1 jne. - kierroksilla 1-24;

K7, K6, K5, K4, K3, K2, K1, K0 - kierroksilla 25-32.

Salauksen purku tässä tilassa suoritetaan täsmälleen samalla tavalla, mutta hieman erilaisella aliavaimien käyttöjärjestyksellä:

K0, K1, K2, K3, K4, K5, K6, K7 - kierroksilla 1-8;

K7, K6, K5, K4, K3, K2, K1, K0, K7, K6 jne. - kierroksilla 9-32.

Kaikki lohkot salataan toisistaan ​​riippumatta, eli kunkin lohkon salauksen tulos riippuu vain sen sisällöstä (vastaava lähdelohko). Jos alkuperäistä (pelkkää) tekstiä on useita identtisiä lohkoja, vastaavat salatekstilohkot ovat myös samat, mikä tarjoaa hyödyllistä lisätietoa salauksen avaamista yrittävälle kryptaanalyytikolle. Siksi tätä tilaa käytetään pääasiassa itse salausavaimien salaamiseen (usein käytetään moniavaimen järjestelmiä, joissa avaimet salataan useista syistä päällekkäin). Itse tiedon salaamiseen on tarkoitettu kaksi muuta toimintatapaa - gamma ja gamma palautetta käyttäen.

Gammatilassa jokainen selkeä tekstilohko lisätään bittikohtaisesti modulo 2 64-bittiseen salauksen gammalohkoon. Salausgamma on erityinen sekvenssi, joka saadaan tiettyjen N1- ja N2-rekisterien operaatioiden tuloksena.

• 1. Rekistereihin N1 ja N2 kirjoitetaan niiden alkutäyttö - 64-bittinen arvo, jota kutsutaan synkronointiviestiksi.
• 2. Rekistereiden N1 ja N2 sisällön (tässä tapauksessa synkronointiviestien) salaus suoritetaan yksinkertaisessa korvaustilassa.
• 3. Rekisterin N1 sisältö lisätään modulo (232 - 1) vakiolla C1 = 224 + 216 + 28 + 24 ja summauksen tulos kirjoitetaan rekisteriin N1.
• 4. Rekisterin N2 sisältö lisätään modulo 232 vakiolla C2 = 224 + 216 + 28 + 1, ja summauksen tulos kirjoitetaan rekisteriin N2.
• 5. Rekistereiden N1 ja N2 sisältö tulostetaan 64-bittisenä salausgammalohkona (tässä tapauksessa N1 ja N2 muodostavat ensimmäisen gammalohkon).

Jos tarvitaan seuraava gammalohko (eli salausta tai salauksen purkamista on jatkettava), palaa vaiheeseen 2.

Salauksen purkamista varten gamma generoidaan samalla tavalla, ja sitten salateksti ja gammabitit XOR-koodataan jälleen. Koska tämä toiminto on palautuva, oikein generoidun gamman tapauksessa saadaan alkuperäinen teksti (taulukko 1).

Pöytä 1. Salaus ja salauksen purku gammatilassa

Salauksen purkamiseen tarvittavan salausalueen kehittämiseksi kryptogrammin salausta purkavalla käyttäjällä on oltava sama avain ja sama synkronointiviestin arvo, joita käytettiin tiedon salauksessa. Muuten et voi saada alkuperäistä tekstiä salatusta tekstistä.

Useimmissa GOST 28147-89 -algoritmin toteutuksissa synkronointiviesti ei ole salainen, mutta on järjestelmiä, joissa synkronointiviesti on sama salainen elementti kuin salausavain. Tällaisissa järjestelmissä algoritmiavaimen tehollista pituutta (256 bittiä) kasvatetaan vielä 64 bitillä salaista synkronointiviestiä, jota voidaan myös pitää avainelementtinä.

Palautteen gammamoodissa rekisterien N1 ja N2 täyttämiseen 2. lohkosta alkaen ei käytetä edellistä gammalohkoa, vaan edellisen selväkielilohkon salauksen tulosta (kuva 2). Ensimmäinen lohko tässä tilassa luodaan täsmälleen samalla tavalla kuin edellinen.

Kuva 2. Salauksen gamman luominen palautegammatilassa.

Ottaen huomioon etuliitejäljitelmien generointitavan, on tarpeen määritellä sukupolven subjektin käsite. Huijaus on salauksen tarkistussumma, joka lasketaan salausavaimella ja on suunniteltu tarkistamaan viestien eheys. Etuliitettä muodostettaessa suoritetaan seuraavat toiminnot: tietotaulukon ensimmäinen 64-bittinen lohko, jolle etuliite lasketaan, kirjoitetaan rekistereihin N1 ja N2 ja salataan pelkistetyssä yksinkertaisessa korvaustilassa (16 ensimmäistä kierrosta 32:sta suoritetaan). Saatu tulos summataan modulo 2 seuraavaan tietolohkoon, jolloin tulos tallennetaan N1:een ja N2:een.

Jakso toistuu viimeiseen tietolohkoon asti. Näistä muunnoksista syntyvää rekistereiden N1 ja N2 64-bittistä sisältöä tai osaa siitä kutsutaan imitaatioetuliitteeksi. Etuliitteen koko valitaan viestien vaaditun luotettavuuden perusteella: etuliitteen pituudella r bittiä todennäköisyys, että viestin muutos jää huomaamatta, on 2-r. Useimmiten 32-bittinen etuliite on käytetään eli puolet rekisterien sisällöstä Tämä riittää, koska, kuten mikä tahansa tarkistussumma, jäljitelmäetuliite on ensisijaisesti tarkoitettu suojaamaan vahingossa tapahtuvalta tietojen vääristymiseltä. Tietojen tahallisen muuttamisen estämiseksi käytetään muita salausmenetelmiä - ensisijaisesti sähköistä digitaalista allekirjoitusta.

Tietoja vaihdettaessa jäljitelmäetuliite toimii eräänlaisena lisäohjauskeinona. Se lasketaan selkeälle tekstille, kun osa tiedoista on salattu, ja lähetetään salatekstin mukana. Salauksen purkamisen jälkeen lasketaan jäljitelmäetuliitteelle uusi arvo, jota verrataan lähetettyyn arvoon. Jos arvot eivät täsmää, se tarkoittaa, että salateksti on vääristynyt lähetyksen aikana tai salauksen purkamisen aikana käytettiin vääriä avaimia. Jäljitelmäetuliite on erityisen hyödyllinen avaintietojen oikean salauksen tarkistamiseen käytettäessä moniavaimen järjestelmiä.

GOST 28147-89 -algoritmia pidetään erittäin vahvana algoritmina - tällä hetkellä sen paljastamiseen ei ole ehdotettu tehokkaampia menetelmiä kuin edellä mainittu "raaka voima" -menetelmä. Sen korkea turvallisuus saavutetaan ensisijaisesti suuren avaimen pituuden ansiosta - 256 bittiä. Salaista synkronointiviestiä käytettäessä tehollinen avaimen pituus kasvaa 320 bittiin ja korvaustaulukon salaisuus lisää bittejä. Lisäksi kryptografinen vahvuus riippuu muunnoskierrosten lukumäärästä, jonka GOST 28147-89:n mukaan pitäisi olla 32 (syöttötietojen hajonnan täysi vaikutus saavutetaan 8 kierroksen jälkeen).

GOST 28147-89:n etuja ovat suojaus väärien tietojen määräämistä vastaan ​​(jäljitelmän lisäyksen kehittäminen) ja sama salausjakso kaikissa neljässä GOST-algoritmissa.

Tämä algoritmi on pakollinen käytettäväksi salausalgoritmina Venäjän federaation valtion organisaatioissa ja useissa kaupallisissa organisaatioissa.

Algoritmin kuvaus

Algoritmin kaavio on esitetty kuvassa. 3.1. Kuten näet, tämän algoritmin järjestelmä on melko yksinkertainen, mikä yksinkertaistaa yksiselitteisesti sen ohjelmisto- tai laitteistototeutusta.

GOST 28147-89 -algoritmi salaa tiedot 64-bittisiksi lohkoiksi, jotka on jaettu kahteen 32-bittiseen alilohkoon (N1 ja N2). Alilohko N1 käsitellään tietyllä tavalla, minkä jälkeen sen arvo lisätään

alilohkoarvolla N2 (lisäys suoritetaan modulo 2), sitten alilohkot vaihdetaan. Tällainen muunnos suoritetaan tietylle määrälle kierroksia: 16 tai 32, riippuen algoritmin toimintatavasta (kuvattu alla). Jokaisella kierroksella suoritetaan seuraavat toiminnot:

1. Näppäinpeitto. /VI-alilohkon sisältö lisätään modulo 2 32 avaimen Kx-osaan.

GOST 28147-89 -algoritmin salausavaimen mitta on 256 bittiä, ja Kx on sen 32-bittinen osa, eli 256-bittinen salausavain esitetään 32-bittisten aliavaimien ketjuna (kuva 3.2):

SH ATI, AG2, Yu, AG4, K5, Kb, K7.

Salausprosessin aikana käytetään yhtä näistä aliavaimista riippuen pyöreästä numerosta ja algoritmin toimintatavasta.

Riisi. 3.1. Algoritmin kaavio GOST 28147-

Riisi. 3.2. GOST 28147-89 -algoritmin salausavain

2. Taulukko vaihto. Avaimen päällekkäisyyden jälkeen /VI-alilohko jaetaan 8 osaan, joissa on 4 bittiä, joiden kunkin arvo korvataan yksitellen tämän alilohkon osan korvaustaulukon mukaisesti. Taulukkokorvauksia (Substitution box, S-box) käytetään usein nykyaikaisissa salausalgoritmeissa, joten niitä kannattaa harkita tarkemmin.

Taulukon korvaamista käytetään näin: tuloon syötetään tietyn mittainen (tässä tapauksessa 4-bittinen) tietolohko, jonka numeerinen esitys määrää lähtöarvon numeron. Meillä on esimerkiksi seuraavan muotoinen S-laatikko:

4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1.

Tulkoon 4-bittinen lohko "0100" eli arvo on 4. Taulukon mukaan lähdön arvoksi tulee 15, ts. "1111" (0 korvataan 4:llä, 1 korvataan 11:llä, 2:n arvo ei muutu jne.).

Kuten näette, algoritmin kaavio on hyvin yksinkertainen, mikä tarkoittaa, että suurin tiedon salauksen taakka lankeaa korvaaville taulukoille. Valitettavasti algoritmilla on se ominaisuus, että on olemassa "heikkoja" korvaustaulukoita, joiden avulla algoritmi voidaan paljastaa kryptausanalyyttisillä menetelmillä. Heikkoja ovat esimerkiksi taulukko, jossa tulos on yhtä suuri kuin syöte:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.

3. Bitittainen syklinen siirto vasemmalle 11 bittiä.

Algoritmitilat

GOST 28147-89 -algoritmilla on 4 toimintatilaa:

□ yksinkertainen vaihtotila;

□ gammatila;

P-pelitila, jossa palaute;

□ jäljitelmien liitteiden valmistustapa.

Nämä tilat poikkeavat jonkin verran yleisesti hyväksytyistä (kuvattu luvussa 1.4), joten niitä kannattaa pohtia tarkemmin.

Näillä tiloilla on erilaiset tarkoitukset, mutta ne käyttävät samaa salausmuunnosta, joka on kuvattu yllä.

Helppo vaihtotila

Yksinkertaisessa korvaustilassa yllä kuvatut 32 kierrosta suoritetaan yksinkertaisesti jokaisen 64-bittisen tietolohkon salaamiseksi. 32-bittisiä aliavaimia käytetään seuraavassa järjestyksessä:

□ KO, Kl, K2, K3, K4, K5, Kb, AG7, KO, ATI jne. - kierroksilla 1-24;

□ K1, Kb, K5, K4, K3, K2, K\, KO - kierroksilla 25-32.

Salauksen purku yksinkertaisessa korvaustilassa tehdään täsmälleen samalla tavalla, mutta hieman erilaisella aliavaimien käyttöjärjestyksellä:

□ KO, K\, K2, KZ, K4, K5, Kb, KP - kierroksilla 1-8;

□ KP, Kb, K5, K4, K3, K2, K\, KO, K1, Kb jne. - kierroksilla 9-32.

Kuten tavallinen ECB-tila, lohkojen erillisestä salauksesta johtuen yksinkertaista korvaustilaa ei suositella todellisten tietojen salaamiseen; sitä tulisi käyttää vain muiden salausavaimien salaamiseen moniavaimen malleissa.

Gamma-tila

Gammamoodissa (kuva 3.3) jokainen selkeän tekstin lohko lisätään bitti bitiltä modulo 2 salauksen gammalohkoon, jonka koko on 64 bittiä. Salausgamma on erityinen sekvenssi, joka luodaan käyttämällä yllä kuvattuja muunnoksia seuraavasti:

1. Rekistereihin N1 ja N2 kirjoitetaan niiden alkutäyttö - 64-bittinen arvo, jota kutsutaan "synkronointiviestiksi" (synkronointisanoma on itse asiassa alustusvektorin analogi CBC-, CFB- ja OFB-tiloissa ).

2. /VI- ja N2-rekisterien sisältö (tässä tapauksessa synkronointiviestit) salataan yksinkertaisessa korvaustilassa.

3. N1:n sisältö lisätään modulo (2 32 - 1) vakiolla CI = 2 24 + 2 16 + 2 8 + 4, summauksen tulos kirjoitetaan /VI-rekisteriin.

4. N2:n sisältö lisätään modulo 2 vakiolla C2 = 2 24 + 2 16 + 2 8 +1, summauksen tulos kirjoitetaan rekisteriin N2.

5. /VI- ja N2-rekisterien sisältö tulostetaan 64-bittisenä salauksen gammalohkona (eli tässä tapauksessa /VI ja N2 muodostavat ensimmäisen gammalohkon).

6. Jos tarvitaan seuraava gammalohko (eli salausta tai salauksen purkamista on jatkettava), palaa vaiheeseen 2.

Salauksen purkamista varten generoidaan gamma samalla tavalla, minkä jälkeen XOR-toimintoa sovelletaan jälleen salatekstiin ja gammabitteihin.

Jotta voidaan luoda sama salausgamma, kryptogrammin salausta purkavalla käyttäjällä on oltava sama avain ja sama synkronointiviestin arvo, joita käytettiin tietojen salaamiseen. Muuten et voi saada alkuperäistä tekstiä salatusta tekstistä.

Useimmissa GOST 28147-89 -algoritmin toteutuksissa synkronointiviesti ei ole salainen elementti, mutta synkronointiviesti voi olla yhtä salainen kuin salausavain. Tässä tapauksessa voidaan katsoa, ​​että algoritmiavaimen tehollinen pituus (256 bittiä) kasvaa synkronointiviestin vielä 64 bitillä, jota voidaan pitää lisäavainelementtinä.

Palaute gamma -tila

Palautteen gammatilassa 2. lohkosta alkaen /VI- ja L/2-rekisterit täytetään ei edellisellä gammalohkolla, vaan edellisen selvätekstilohkon salauksen tuloksella (kuva 3.4). Ensimmäinen lohko tässä tilassa luodaan täsmälleen samalla tavalla kuin edellinen.

Riisi. 3.4. Salausgamman luominen gammatilassa palautteen avulla

Imitaattorin generointitila

Huijaus on salauksen tarkistussumma, joka lasketaan salausavaimella ja on suunniteltu tarkistamaan viestien eheys. Sen laskemiseksi on GOST 28147-89 -algoritmin erityinen tila.

Jäljitelmäetuliite luodaan seuraavasti:

1. Ensimmäinen 64-bittinen tietolohko, jolle imitaattori lasketaan, kirjoitetaan rekistereihin N1 ja N2 ja salataan pelkistetyssä yksinkertaisessa korvaustilassa, jossa suoritetaan ensimmäiset 16 kierrosta 32:sta.

2. Saatu tulos summataan modulo 2 seuraavaan tietolohkoon, jolloin tulos tallennetaan N1:een ja N2:een.

3. M ja N2 salataan jälleen pelkistetyssä vaihtomuodossa ja niin edelleen viimeiseen tietolohkoon asti.

Etuliitteen katsotaan olevan rekisterien N1 ja N2 tuloksena oleva 64-bittinen sisältö tai osa siitä. Useimmiten käytetään 32-bittistä etuliitettä, eli puolet rekisterien sisällöstä. Tämä riittää, koska, kuten mikä tahansa tarkistussumma, jäljitelmäetuliite on tarkoitettu ensisijaisesti suojaamaan vahingossa tapahtuvalta tietojen vääristymiseltä. Tietojen tahallisen muuttamisen estämiseksi käytetään muita salausmenetelmiä - ensisijaisesti sähköistä digitaalista allekirjoitusta (katso kohta 1.1).

Jäljitelmäetuliitettä käytetään seuraavasti:

1. Kun mitä tahansa tietoa salataan, selvätekstiimitaattori lasketaan ja lähetetään salatekstin mukana.

2. Dekoodauksen jälkeen jäljitelmäetuliite lasketaan uudelleen ja sitä verrataan lähetettyyn.

3. Jos lasketut ja lähetetyt jäljitelmäetuliitteet eivät täsmää, salateksti on vääristynyt lähetyksen aikana tai salauksen purkamisen aikana on käytetty vääriä avaimia.

Jäljitelmäetuliite on erityisen hyödyllinen avaintietojen oikean salauksen tarkistamiseen käytettäessä moniavainjärjestelmiä.

Jäljitelmäetuliite on jonkin verran analogia MAC-sanoman todennuskoodille, joka on laskettu CBC-tilassa; ero on siinä, että etuliitelaskenta ei käytä synkronointiviestiä, kun taas MAC-laskennassa käytetään alustusvektoria.

Algoritmin kryptografinen vahvuus

Vuonna 1994 GOST 28147-89 -algoritmin kuvaus käännettiin englanniksi ja julkaistiin; tämän jälkeen ulkomaisten asiantuntijoiden suorittaman analyysin tulokset alkoivat ilmestyä; Käytännöllisiä hyökkäyksiä ei kuitenkaan löydetty merkittävään aikaan.

□ suuri avaimen pituus - 256 bittiä; yhdessä salaisen synkronointiviestin kanssa tehollinen avaimen pituus kasvaa 320 bittiin;

□ 32 muunnoskierrosta; jo 8 kierroksen jälkeen saavutetaan syöttödatan sirontavaikutus kokonaisuudessaan: selvätekstilohkon yhden bitin muuttaminen vaikuttaa kaikkiin salatekstilohkon bitteihin ja päinvastoin, eli on olemassa moninkertainen turvamarginaali.

Harkitse GOST 28147-89 -algoritmin kryptausanalyysin tuloksia.

Korvaustaulukoiden analyysi

Koska standardissa ei anneta korvaustaulukoita, useat teokset (esimerkiksi in) viittaavat siihen, että "pätevä organisaatio" voi laatia sekä "hyviä" että "huonoja" korvaustaulukoita. Kuuluisa asiantuntija Bruce Schneier kuitenkin kutsuu tällaisia ​​oletuksia "huhuiksi". On selvää, että algoritmin kryptografinen vahvuus riippuu pitkälti käytettyjen korvaustaulukoiden ominaisuuksista, vastaavasti on heikkoja korvaustaulukoita (katso esimerkki yllä), joiden käyttö voi yksinkertaistaa algoritmin hyökkäystä. Mahdollisuus käyttää erilaisia ​​korvaustaulukoita näyttää kuitenkin olevan erittäin kannatettava idea, jota tukevat seuraavat kaksi tosiasiaa DES-salausstandardin historiasta (katso lisätietoja osiosta 3.15):

□ DES-algoritmin lineaarista ja differentiaalista kryptausanalyysiä käyttävät hyökkäykset käyttävät korvaustaulukoiden erityispiirteitä; käytettäessä muita taulukoita kryptausanalyysi on aloitettava alusta;

□ DES:ää on yritetty vahvistaa lineaarista ja differentiaalista kryptausanalyysiä vastaan ​​käyttämällä vahvempia korvaustaulukoita; sellaisia ​​taulukoita, jotka ovat todellakin vakaampia, on ehdotettu esimerkiksi s 5 DES -algoritmissa; mutta valitettavasti DES:n korvaaminen s 5 DES:llä oli mahdotonta, koska korvaavat taulukot on määritelty tiukasti standardissa, joten algoritmin toteutukset eivät todennäköisesti tue mahdollisuutta vaihtaa taulukoita muihin.

Useissa teoksissa (esimerkiksi , ja ) päätellään virheellisesti, että GOST 28147-89 -algoritmin salaiset korvaustaulukot voivat olla osa avainta ja lisätä sen tehollista pituutta (millä ei ole merkitystä, koska algoritmilla on erittäin suuri 256-bittinen avain). Työ kuitenkin osoittaa, että salaiset korvaustaulukot voidaan laskea seuraavalla käytännössä sovellettavalla hyökkäyksellä:

1. Aseta nolla-avain ja etsi "nollavektori", eli arvo z = /(0), missä /() on algoritmin pyöreä funktio. Tämä vaihe kestää noin 2 salausoperaatiota.

2. Nollavektorin avulla lasketaan korvaustaulukoiden arvot, mikä kestää enintään 2 11 operaatiota.

Algoritmien modifikaatiot ja niiden analysointi

Työssä suoritettiin GOST 28147-89 -algoritmin muutosten kryptausanalyysi:

□ GOST-H-algoritmi, jossa aliavaimien käyttöjärjestystä muutetaan alkuperäiseen algoritmiin verrattuna, eli kierroksittain 25:stä 32:een aliavaimia käytetään suorassa järjestyksessä eli samalla tavalla kuin edellisessä. algoritmin kierrokset ;

□ 20 kierroksen GOST®-algoritmi, joka käyttää XOR:ta modulo 2 32:n sijaan avaimen päällekkäisyyteen.

Analyysin tulosten perusteella pääteltiin, että GOST-H ja GOST© ovat heikompia kuin alkuperäinen GOST 28147-89 -algoritmi, koska molemmissa on heikkojen avainten luokat. On syytä huomata, että GOST©-kryptausanalyysin kannalta teos toistaa sanasta sanaan GOST 28147-89 -algoritmin kryptausanalyysiä käsittelevän osan, joka julkaistiin vuonna 2000 tunnetussa teoksessa (ilman viittausta alkuperäiseen). Tämä asettaa kyseenalaiseksi teoksen tekijöiden ammattitaidon ja sen muut tulokset.

Työssä ehdotetaan erittäin mielenkiintoinen algoritmin muunnos: taulukoiden S \ ... Ss on välttämättä oltava erilaisia; jokaisella algoritmin kierroksella ne on muutettava tietyn lain mukaan. Tämä permutaatio voi olla riippuvainen salausavaimesta tai se voi olla salainen (eli olla osa suurempaa salausavainta kuin alkuperäinen 256-bittinen avain). Molemmat vaihtoehdot lisäävät kirjoittajiensa mukaan merkittävästi algoritmin vastustuskykyä lineaarista ja differentiaalista kryptausanalyysiä vastaan.

Ja työssä annetaan vielä yksi korvaustaulukoihin liittyvä muunnos, jossa analysoidaan yhtä mahdollisista menetelmistä substituutiotaulukoiden laskentaan salausavaimen perusteella. Työn kirjoittajat päättelivät, että tällainen riippuvuus heikentää algoritmia, koska se johtaa heikkojen avainten esiintymiseen ja joihinkin algoritmin mahdollisiin haavoittuvuuksiin.

Koko kierroksen algoritmianalyysi

Hyökkäyksiä on myös koko kierroksen GOST 28147-89:ää vastaan ​​ilman muutoksia. Yksi ensimmäisistä avoimista töistä, jossa algoritmin analyysi suoritettiin, hyvin tunnettu työ, on omistettu hyökkäyksille, jotka hyödyntävät useiden tunnettujen salausalgoritmien avainten laajennusprosessin heikkouksia. Erityisesti täyden kierroksen algoritmi GOST 28147-89 voidaan rikkoa käyttämällä differentiaalista kryptausanalyysiä linkitetyissä avaimissa, mutta vain jos käytetään heikkoja korvaustaulukoita. Algoritmin 24 kierroksen versio (josta puuttuu ensimmäiset 8 kierrosta) avataan samalla tavalla kaikille korvaustaulukoille, mutta vahvat korvaustaulukot (esimerkiksi kohdassa ) tekevät tällaisesta hyökkäyksestä ehdottoman epäkäytännöllisen.

Kotimaiset tutkijat A. G. Rostovtsev ja E. B. Makhovenko ehdottivat vuonna 2001 pohjimmiltaan uutta kryptausanalyysimenetelmää (tekijöiden mukaan se on huomattavasti tehokkaampi kuin lineaarinen ja differentiaalinen kryptausanalyysi) muodostamalla tavoitefunktion tunnetusta selkeästä tekstistä, joka vastaa sitä salatekstiä ja haluttua arvoa. avaimesta ja löytää sen ääriarvo, joka vastaa avaimen todellista arvoa. He löysivät myös suuren luokan GOST 28147-89 -algoritmin heikkoja avaimia, joiden avulla voit avata algoritmin käyttämällä vain neljää valittua selkeää tekstiä ja niitä vastaavia salatekstejä, joiden monimutkaisuus on melko alhainen. Algoritmin kryptausanalyysiä jatketaan työssä.

Vuonna 2004 korealainen asiantuntijaryhmä ehdotti hyökkäystä, jolla käyttämällä toisiinsa liittyvien avainten differentiaalista kryptausanalyysiä on mahdollista saada 91,7 %:n todennäköisyydellä 12 bittiä salaista avainta. Hyökkäys vaatii 235 valittua selkeää tekstiä ja 236 salaustoimintoa. Kuten näette, tämä hyökkäys on käytännössä hyödytön algoritmin todelliselle avaamiselle.

Maassamme yhtenäinen algoritmi tietojen salauskuvaukselle tietojenkäsittelyjärjestelmille tietokoneverkoissa, yksittäisissä tietokonejärjestelmissä ja tietokoneissa, jonka määrää GOST 28147-89.

Tämä salaustietojen muunnosalgoritmi on 64-bittinen lohkoalgoritmi 256-bittisellä avaimella, suunniteltu laitteisto- ja ohjelmistototeutukseen, täyttää kryptografiset vaatimukset eikä rajoita suojattujen tietojen salassapitoastetta.

Algoritmia kuvattaessa käytetään seuraavaa merkintää:

L ja R ovat bittisarjoja;
LR on sekvenssien L ja R ketju, jossa sekvenssin R bitit seuraavat sekvenssin L bittejä;
(+) - bittikohtainen lisäys modulo 2 ("yksinomainen TAI"-toiminto);
[+] - 32-bittisten lukujen yhteenlasku modulo 2 32 ;
(+) - 32-bittisten lukujen yhteenlasku modulo 2 32 -1.

Luvut lasketaan yhteen seuraavan säännön mukaan:

A[+]B=A+B, jos A+B< 2 32 ,
A [+] B = A + B - 2 32, jos A + B > = 2 32 . A (+) B = A + B, jos A + B< 2^32 - 1, A {+} B = A + B - (2^32 - 1), если A + B >= 2^32 - 1.

Algoritmi tarjoaa neljä toimintatilaa:

Joka tapauksessa datan salaamiseen käytetään 256-bittistä avainta K, joka esitetään kahdeksana 32-bittisenä aliavaimena K i:

K = K 7 K 6 K 5 K 4 K 3 K 2 K 1 K 0 .

Salauksen purku suoritetaan samalla avaimella kuin salaus, mutta tämä prosessi on käänteinen tietojen salausprosessille.

Helppo vaihtotila

Ensimmäinen ja helpoin tila - korvaus. Salattava tieto on jaettu 64-bittisiin lohkoihin. Avoimen datalohkon T0 salausproseduuri sisältää 32 jaksoa (j=1...32).

Lohko T0 on jaettu kahteen 32-bitin sekvenssiin: B(0)A(0), jossa B(0) ovat vasen tai eniten merkitsevä bitti, A(0) ovat oikeat tai vähiten merkitsevät bitit.

Nämä sekvenssit syötetään asemiin N 1 ja N 2 ennen ensimmäisen salausjakson alkua.

64-bittisen datalohkon salausmenettelyn ensimmäinen jakso (j=1) kuvataan seuraavilla kaavoilla:

Tässä i tarkoittaa iteraationumeroa (i = 1, 2,..., 32).

Funktiota f kutsutaan salausfunktioksi. Sen argumentti on edellisessä iteraatiovaiheessa saadun luvun A(i) ja avaimen luvun X(j) summa modulo 2 32 (kunkin näistä numeroista on 32 numeroa).

Salaustoiminto sisältää kaksi operaatiota tuloksena olevalle 32-bittiselle summalle. Ensimmäistä operaatiota kutsutaan substituutioksi K. Korvauslohko K ​​koostuu kahdeksasta korvaussolmusta K(1) ... K(8), joissa kussakin on 64 bitin muisti. Korvauslohkoon saapuva 32-bittinen vektori jaetaan kahdeksaan peräkkäiseen 4-bittiseen vektoriin, joista jokainen muunnetaan 4-bittisiksi vektoriksi vastaavalla korvaussolmulla, joka on taulukko, jossa on 16 kokonaislukua välillä 0. .15.

Tulovektori määrittää sen taulukon rivin osoitteen, jonka numero on lähtövektori. 4-bittiset lähtövektorit yhdistetään sitten peräkkäin 32-bittiseksi vektoriksi. Korvauslohkotaulukko K sisältää tietoverkolle yhteisiä ja harvoin muuttuvia avainelementtejä.

Toinen operaatio on 32-bittisen vektorin syklinen siirto vasemmalle, joka saadaan korvaamalla K. 64-bittinen salattu datalohko Tw esitetään muodossa Tw =A(32)B(32).

Loput avoimet datalohkot yksinkertaisessa korvaustilassa salataan samalla tavalla.

Muista, että yksinkertaista vaihtotilaa voidaan käyttää tietojen salaukseen vain rajoitetuissa tapauksissa. Näihin tapauksiin kuuluu avaimen luominen ja sen salaus jäljitelmäsuojauksella (suojaus väärien tietojen määräämistä vastaan) tiedonsiirtokanavien kautta tapahtuvaa siirtoa tai tietokoneen muistiin tallentamista varten.

Gamma-tila

Avoin data, joka on jaettu 64-bittisiin lohkoihin T(i) (i=1, 2,..., m, missä m määräytyy salatun tiedon määrän mukaan), salataan gammatilassa bittikohtaisella lisäyksellä modulo 2 salausgamma Гw, joka tuotetaan 64-bittisinä lohkoina, eli Гw = (Г(1),Г(2),...,Г(i),...,Г(m)).

Datan salausyhtälö gammatilassa voidaan esittää seuraavasti:

W(i) = A (Y(i-1) [+] C2, Z(i-1) (+) C1) (+) T(i) = G(i) (+) T(i) .
Tässä W(i) on 64-bittinen salatekstilohko,
A - salaustoiminto yksinkertaisessa korvaustilassa (tämän funktion argumentit ovat kaksi 32-bittistä numeroa),
C1 ja C2 - GOST 28147-89:ssä määritellyt vakiot,
Y(i) ja Z(i) ovat suureita, jotka määritetään iteratiivisesti, kun gamma muodostuu seuraavasti:
(Y(0), Z(0)) = A(S), jossa S on 64-bittinen binaarisekvenssi (synkronointiviesti);
(Y(i), Z(i)) = (Y(i-1) [+] C2, Z(i-1) (+) C1) arvolle i = 1, 2,...,m.

Tietojen salauksen purku on mahdollista vain, jos on olemassa synkronointiviesti, joka ei ole salauksen salainen elementti ja joka voidaan tallentaa tietokoneen muistiin tai lähettää viestintäkanavia pitkin salatun tiedon mukana.

Palaute gamma -tila

tila skaalaus palaute on hyvin samanlainen kuin gammatila. Kuten gammatilassa, avoin data, joka on jaettu 64-bittisiin lohkoihin T(i) (i=1, 2,..., m , missä m määräytyy salatun datan määrällä), salataan bittikohtaisella lisäyksellä modulo 2 gamma G sh -salauksella, joka tuotetaan 64-bittisinä lohkoina:

Гw = (Г(1),Г(2),...,Г(i),...,Г(m)).

Lohkon T(m) bittien määrä voi olla pienempi kuin 64, kun taas se osa lohkon G(m) salauksen gammasta, jota ei käytetä salaukseen, hylätään.

Datan salausyhtälö gammatilassa palautetta käyttäen voidaan esittää seuraavasti:

Kehitysprosessi jäljitelmäpinot on yhtenäinen mille tahansa tiedon salausmoodille.

Jäljitelmälisäys on p-bitin lohko (imitation insertion Ip), joka generoidaan joko ennen koko viestin salausta tai rinnakkain lohkokohtaisen salauksen kanssa. Ensimmäiset avoimen datan lohkot, jotka ovat mukana lisäyssimulaation kehittämisessä, voivat sisältää palveluinformaatiota (esimerkiksi osoiteosan, ajan, synkronointiviestin) eivätkä olla salattuja. Parametrin p arvo (binäärinumeroiden lukumäärä simuloidussa lisäyksessä) määräytyy salausvaatimusten mukaan ottaen huomioon, että väärien häiriöiden aiheuttamisen todennäköisyys on 1/2^p.

Lisäysjäljitelmän saamiseksi avoin data esitetään 64-bittisinä lohkoina T(i) (i = 1, 2,..., m, missä m määräytyy salatun datan määrän mukaan). Ensimmäiselle avoimen datan lohkolle T(1) suoritetaan muunnos, joka vastaa salausalgoritmin 16 ensimmäistä jaksoa yksinkertaisessa korvausmoodissa. Lisäksi tietojen salaamiseen käytettyä avainta käytetään avaimena jäljitellyn lisäyksen luomiseen.

16 toimintajakson jälkeen saatu 64-bittinen luku summataan modulo 2 toisen avoimen datalohkon T(2) kanssa. Summatulokseen kohdistetaan jälleen muunnos, joka vastaa salausalgoritmin 16 ensimmäistä jaksoa yksinkertaisessa korvaustilassa. Tuloksena oleva 64-bittinen luku lisätään modulo 2 kolmanteen avoimeen datalohkoon T(3) ja niin edelleen. Viimeinen lohko T(m), joka on tarvittaessa pehmustettu täydelliseksi 64-bittiseksi lohkoksi nollien kanssa, summataan modulo 2 työn tuloksella vaiheessa m-1, jonka jälkeen se salataan yksinkertaisessa korvaustilassa ensimmäisen päälle. Algoritmin 16 sykliä. Vastaanotetusta 64-bittisestä luvusta valitaan segmentti Ip, jonka pituus on p bittiä.

Jäljitelmäliite Ip välitetään tietoliikennekanavaa pitkin tai tietokoneen muistiin salatun tiedon jälkeen. Saapuvan salatun tiedon salaus puretaan ja vastaanotetuista avoimen datan T(i) lohkoista muodostetaan jäljitelmälisäys Ip, jota sitten verrataan viestintäkanavalta tai tietokoneen muistista saatuun jäljitelmälisäkkeeseen IR. eivät täsmää, kaikki salatut tiedot katsotaan vääriksi.