Kaksi kalaa

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 21. toukokuuta 2022 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Kaksi kalaa

Luoja	Bruce Schneierin johtama asiantuntijaryhmä
Luotu	1998
Avaimen koko	128/192/256 bittiä
Lohkon koko	128 bittinen
Kierrosten lukumäärä	16
Tyyppi	Feistelin verkko

Twofish on symmetrinen lohkosalaus, jonka lohkokoko on 128 bittiä ja avaimen pituus jopa 256 bittiä. Kierrosten lukumäärä 16. Bruce Schneierin johtaman asiantuntijaryhmän kehittämä . Hän oli yksi viidestä AES - kilpailun toisen vaiheen finalistista . Algoritmi perustuu Blowfish- , SAFER- ja SQUARE -algoritmeihin .

Algoritmin tunnusomaisia piirteitä ovat ennalta laskettujen ja avaimesta riippuvaisten korvaussolmujen käyttö ja monimutkainen menetelmä salauksen aliavaimien purkamiseksi. Puolet n - bittisestä salausavaimesta käytetään varsinaisena salausavaimena, toista puolta käytetään algoritmin muokkaamiseen (korvaussolmut riippuvat siitä).

Yleistä tietoa

Twofish kehitettiin erityisesti täyttämään NIST : n vaatimukset ja suositukset AES :lle [1] :

128-bittinen lohkosymmetrinen salaus,
avaimen pituus 128, 192 ja 256 bittiä,
ei heikkoja avaimia
tehokas ohjelmisto (pääasiassa 32-bittisille prosessoreille) ja laitteistototeutus,
joustavuus (mahdollisuus käyttää ylimääräisiä avainten pituuksia, käyttö suoratoiston salauksessa, hash-toiminnot jne.),
algoritmin yksinkertaisuus - sen tehokkaan analyysin mahdollisuudesta.

Kuitenkin algoritmin rakenteen monimutkaisuus ja vastaavasti sen heikkojen avainten tai piilolinkkien analyysin monimutkaisuus sekä melko hidas suoritusaika verrattuna Rijndaeliin useimmilla alustoilla eivät olleet sen eduksi [2 ] .

Twofish-algoritmi sai alkunsa yrityksestä muokata Blowfish-algoritmia 128-bittiselle syöttölohkolle. Uuden algoritmin piti olla helposti toteutettavissa laitteistoon (mukaan lukien pienempien taulukoiden käyttö), siinä on oltava kehittyneempi avainten laajennusjärjestelmä ( eng. key schedule ) ja yksiarvoinen funktio F.

Tuloksena algoritmi toteutettiin sekoitettuna Feistel-verkona, jossa oli neljä haaraa, jotka muokkaavat toisiaan Hadamar-salausmuunnolla ( eng. pseudo-Hadamar transform, PHT ).

Mahdollisuus tehokkaaseen toteutukseen nykyaikaisilla (silloinkin) 32-bittisillä prosessoreilla (sekä älykorteilla ja vastaavilla laitteilla) on yksi Twofishin kehittäjiä ohjanneista avainperiaatteista.

Esimerkiksi F-funktio, kun lasketaan PHT:ta ja lisätään avainosaan K, käyttää tarkoituksella yhteenlaskua perinteisen xor :n sijaan . Tämä mahdollistaa Pentium-prosessoriperheen LEA-käskyn käytön, jonka avulla Hadamard-muunnos voidaan laskea yhdessä kellojaksossa . (Tässä tapauksessa koodi on kuitenkin käännettävä tietylle avainarvolle). $(T_{0}+2T_{1}+K_{2r+9}){\bmod {2}}^{32}$

Twofishin algoritmia ei ole patentoitu, ja kuka tahansa voi käyttää sitä ilman maksuja tai rojalteja. Sitä käytetään monissa salausohjelmissa, vaikka se on vähemmän yleinen kuin Blowfish .

Algoritmin kuvaus

Twofish jakaa syötetyn 128-bittisen datalohkon neljään 32-bittiseen alilohkoon, joille tulovalkaisutoimenpiteen jälkeen suoritetaan 16 muunnoskierrosta. Viimeisen kierroksen jälkeen suoritetaan ulostulovalkaisu.

Valkaisu

Valkaisu on menettely datan siirtämiseksi aliavaimilla ennen ensimmäistä kierrosta ja viimeisen kierroksen jälkeen. Tätä tekniikkaa käytti ensin Khufu / Khare-salauksessa ja itsenäisesti Ron Rivest DESX - salausalgoritmissa . Joe Killian (NEC) ja Phillip Rogaway (University of California) ovat osoittaneet, että valkaisu vaikeuttaa perusteellista avainten hakua DESX:ssä [3] . Twofishin kehittäjät väittävät [4] , että Twofishin valkaisu vaikeuttaa merkittävästi myös avaimen arvaamista, koska kryptanalyytikko ei voi saada selville, mitä dataa tulee ensimmäisen kierroksen funktion F syötteeseen.

Siinä oli kuitenkin myös negatiivisia puolia. IBM Research Centerin asiantuntijat suorittivat mielenkiintoisen tutkimuksen. [5] He toteuttivat Twofishin algoritmin tyypilliselle CMOS-älykortille ja analysoivat hyökkäyksen mahdollisuutta käyttämällä differentiaalitehoanalyysiä (DPA). Juuri syötteen valkaisumenettelyä vastaan hyökättiin, koska se käyttää suoraan aliavaimien xor:ta syötetietojen kanssa. Tuloksena tutkijat osoittivat, että on mahdollista laskea 128-bittinen avain kokonaan analysoimalla vain 100 satunnaista lohkosalausoperaatiota.

Funktio g

G-funktio on Twofishin algoritmin perusta. Funktiosyöttö on 32-bittinen luku X, joka jaetaan sitten neljään tavuun x0, x1, x2, x3. Jokainen tuloksena oleva tavu kulkee sen S-laatikon läpi. (On huomattava, että algoritmin S-laatikot eivät ole kiinteitä, vaan ne riippuvat avaimesta). Tuloksena saadut 4 tavua S-laatikoiden lähdöissä tulkitaan vektoriksi, jossa on neljä komponenttia. Tämä vektori kerrotaan kiinteällä 4x4 MDS-matriisilla (maximum distance separable) ja laskelmat suoritetaan Galois'n kentässä moduloi redusoitumaton polynomi $GF(2^{8})$ $x^{8}+x^{6}+x^{5}+x^{3}+1$

MDS-matriisi on sellainen matriisi äärellisen kentän K yli, että jos otamme sen lineaarisen muunnoksen matriisina avaruudesta avaruuteen , niin mitkä tahansa kaksi vektoria muodon (x, f(x)) avaruudesta on vähintään m + 1 eroja komponenteissa . Toisin sanoen joukko vektoreita muotoa (x, f(x)) muodostaa koodin, jolla on maksimietäisyyden erotettavissa oleva koodiominaisuus. Tällainen koodi on esimerkiksi Reed-Solomon-koodi . $f(x)=(MDS)x$ $K^n$ $K^{m}$ $K^{{n+m}}$

Twofishissa MDS-matriisin maksimidiversiteettiominaisuus tarkoittaa, että vektorin a ja vektorin vaihtuvien tavujen kokonaismäärä on vähintään viisi. Toisin sanoen mikä tahansa muutos vain yhteen tavuun a:ssa muuttaa kaikki neljä tavua b:ssä. $b=(MDS)a$

Hadamarin kryptomuunnos (Pseudo-Hadamar Transform, PHT)

Crypto Hadamard -muunnos on käännettävä muunnos bittijonosta, jonka pituus on 2n. Merkkijono jaetaan kahteen osaan a ja b, jotka ovat samanpituisia n bitissä. Muunnos lasketaan seuraavasti:

{\displaystyle a'=a+b\,{\pmod {2^{n))))

{\displaystyle b'=a+2b\,{\pmod {2^{n))))

Tätä toimintoa käytetään usein koodin "hajottamiseen" (esimerkiksi SAFER -salauksessa ).

Twofishissa tätä muunnosa käytetään sekattaessa kahden g-funktion tuloksia (n = 32).

Kierrä 1 bitti

Jokaisella kierroksella kahta oikeaa 32-bittistä lohkoa, jotka on xored F-funktion tuloksilla, kierretään lisäksi yhden bitin verran. Kolmas lohko siirretään ennen xor-operaatiota, neljäs lohko sen jälkeen. Nämä siirtymät on lisätty tarkoituksella katkaisemaan tavujen kohdistus, joka on luontainen S-laatikoille ja MDS-matriisikertouksille. Salaus kuitenkin lakkaa olemasta täysin symmetrinen, koska salauksen ja salauksen purkamisen aikana siirrot tulisi suorittaa vastakkaisiin suuntiin.

Avaimen luominen

Twofish on suunniteltu toimimaan 128-, 192- ja 256-bittisten avainten kanssa. Alkuavaimesta generoidaan 40 32-bittistä aliavainta, joista kahdeksan ensimmäistä käytetään vain syötteen ja lähdön valkaisuoperaatioissa ja loput 32 käytetään salauskierroksilla, kaksi aliavainta kierrosta kohti. Twofishin ominaisuus on, että alkuperäistä avainta käytetään myös itse salausalgoritmin vaihtamiseen, koska g-funktiossa käytetyt S-laatikot eivät ole kiinteitä, vaan riippuvat avaimesta.

Pyöreiden aliavaimien muodostamiseksi alkuperäinen avain M jaetaan tavujen permutaatiolla kahdeksi identtiseksi lohkoksi ja . Sitten lohkolla ja funktiolla h salataan arvo 2*i ja lohkolla 2*i+1, jossa i on nykyisen kierroksen numero (0 - 15). Tuloksena saadut salatut lohkot sekoitetaan Hadamardin salausmuunnoksen avulla ja käytetään sitten pyöreinä aliavaimina. $M_{o}$ $Minä}$ $M_{o}$ $Minä}$

Tekniset tiedot

Tarkastellaanpa tarkemmin algoritmia pyöreiden aliavaimien generoimiseksi sekä avaimesta riippuvaa funktiota g. Sekä aliavaimien luominen että g-funktion muodostus Twofishin ohjelmassa käyttävät yhtä pääfunktiota: h(X, L 0 , L 1 , … , L k ). Tässä X, L 0 , L 1 , … , L k ovat 32-bittisiä sanoja ja k = N / 64, missä N on alkuperäisen avaimen pituus bitteinä. Toiminnon tulos on yksi 32-bittinen sana.

Funktio h

Toiminto suoritetaan k vaiheessa. Eli 256 bitin avaimella on 4 vaihetta, 192 bitin avaimella - 3 vaihetta, 128 bitin avaimella - 2 vaihetta.

Jokaisessa vaiheessa syötetty 32-bittinen sana jaetaan 4 tavuksi ja jokaiselle tavulle tehdään kiinteä bittipermutaatio q 0 tai q 1

Tulos esitetään 4 tavun vektorina ja kerrotaan MDS-matriisilla. Laskutoimitukset suoritetaan Galois'n kentässä GF(2 8 ) modulo redusoitumaton polynomi . $x^{8}+x^{6}+x^{5}+x^{3}+1$

MDS-matriisilla on muoto:

${\mbox{MDS}}={\begin{pmatrix}01&EF&5B&5B\\5B&EF&EF&01\\EF&5B&01&EF\\EF&01&EF&5B\end{pmatrix}}$

Permutaatiot q 0 ja q 1

q 0 ja q 1 ovat tulotavun x kiinteitä permutaatioita 8 bitille.

Tavu x jaetaan kahdeksi 4-bittiseksi puolikkaaksi a 0 ja b 0 , joiden yli suoritetaan seuraavat muunnokset:

a_{0}=x/16

b_{0}=x{\bmod {16}}

a_{1}=a_{0}\oplus b_{0}

b_{1}=a_{0}\oplus {\mbox{ROR}}_{4}(b_{0},1)\oplus 8a_{0}{\bmod {16}}

a_{2}=t_{0}[a_{1}]

b_{2}=t_{1}[b_{1}]

a_{3}=a_{2}\oplus b_{2}

b_{3}=a_{2}\oplus {\mbox{ROR}}_{4}(b_{2},1)\oplus 8a_{2}{\bmod {16}}

a_{4}=t_{2}[a_{3}]

b_{4}=t_{3}[b_{3}]

{\displaystyle y=16b_{4}+a_{4))

Tässä on 4-bittinen syklinen siirto oikealle, ja t 0 , t 1 , t 2 , t 3 ovat 4-bittisten lukujen taulukkokorvauksia. ${\mbox{ROR}}_{4}$

Arvolla q 0 taulukot näyttävät tältä:

t 0 = [ 8 1 7 D 6 F 3 2 0 B 5 9 ECA 4 ] t 1 = [ EKP 8 1 2 3 5 F 4 A 6 7 0 9 D ] t 2 = [ BA 5 E 6 D 9 0 C 8 F 3 2 4 7 1 ] t 3 = [ D 7 F 4 1 2 6 E 9 B 3 0 8 5 CA ]

Q1 : lle taulukot näyttävät tältä:

t 0 = [ 2 8 BDF 7 6 E 3 1 9 4 0 AC 5 ] t 1 = [ 1 E 2 B 4 C 3 7 6 DA 5 F 9 0 8 ] t 2 = [ 4 C 7 5 1 6 9 A 0 ED 8 2 B 3 F ] t 3 = [ B 9 5 1 C 3 DE 6 4 7 F 2 0 8 A ]

Avaimen luominen

Olkoon M alkuperäinen avain, N sen pituus bitteinä. Ala-avaimet luodaan seuraavasti:

Alkuperäinen avain on jaettu 8*k tavuksi , missä k = N / 64. $m_{0},...,m_{{8k-1}}$
Nämä 8*k tavua on jaettu neljän tavun sanoiksi, ja jokaisessa sanassa tavut käännetään. Tuloksena on 2*k 32-bittistä sanaa $Mi}$

M_{i}=\sum _{j=0}^{3}m_{(4i+j)}\cdot 2^{8j}~~~~~~i=0,...,2k- yksi

Tuloksena saadut 2*k 32-bittistä sanaa jaetaan kahdeksi vektoriksi , joiden koko on k 32-bittistä sanaa. $Minä}$ $M_{o}$

M_{e}=(M_{0},M_{2},...,M_{2k-2})

M_{o}=(M_{1},M_{3},...,M_{2k-1})

I:nnen kierroksen aliavaimet lasketaan kaavoilla:

{\displaystyle \rho =2^{24}+2^{16}+2^{8}+2^{0))

A_{i}=h(2i\rho ,M_{e})

B_{i}={\mbox{ROL}}(h((2i+1)\rho ,M_{0}),8)

{\displaystyle K_{2i}=(A_{i}+B_{i}){\bmod {2^{32))))

K_{2i+1}={\mbox{ROL}}((A_{i}+2B_{i}){\bmod {2^{32}}},9)

Funktio g ja S -laatikot

Funktio g määritellään funktiolla h : . $g(X)=h(X,S)$

Vektori S , kuten vektorit M e ja M o , muodostuu myös alkuperäisestä avaimesta ja koostuu k 32-bittisestä sanasta. Alkuperäiset avaintavut on jaettu k kahdeksan tavun ryhmään. Jokaista tällaista ryhmää käsitellään vektorina, jossa on 8 komponenttia ja kerrotaan kiinteällä 4 × 8 tavun RS-matriisilla. Kertomisen tuloksena saadaan neljästä tavusta koostuva vektori. Laskutoimitukset suoritetaan Galois'n kentässä modulo redusoitumaton polynomi . RS-matriisilla on muoto $GF(2^{8})$ $x^{8}+x^{6}+x^{3}+x^{2}+1$

.

Cryptanalysis

Twofishin tutkimus pienemmällä määrällä kierroksia osoitti, että algoritmilla on suuri turvallisuusmarginaali, ja verrattuna muihin AES-kilpailun finalisteihin se osoittautui kestävimmäksi. Sen epätavallinen rakenne ja suhteellinen monimutkaisuus ovat kuitenkin herättäneet epäilyksiä tämän lujuuden laadusta.

Alkuperäisen avaimen jakaminen kahteen puolikkaaseen pyöreiden aliavaimien muodostuksen aikana aiheutti kritiikkiä. Kryptografit Fauzan Mirza ja Sean Murphy ehdottivat, että tällainen jako mahdollistaa hyökkäyksen järjestämisen "hajaa ja hallitse" -periaatteen mukaisesti, eli tehtävän jakamisen kahteen samanlaiseen, mutta yksinkertaisempaan [6] . Tällaista hyökkäystä ei kuitenkaan todellisuudessa toteutettu.

Vuodelle 2008 Twofishin kryptoanalyysin paras variantti on typistetyn differentiaalisen kryptaanalyysin muunnos, jonka Shiho Moriai ja Yiqun Lisa Yin julkaisivat Japanissa vuonna 2000 [7] . Ne osoittivat, että tarvittavien erojen löytämiseen tarvitaan 251 täsmäävää selkeää tekstiä . Siitä huolimatta tutkimukset olivat luonteeltaan teoreettisia, varsinaista hyökkäystä ei tehty. Twofishin luoja Bruce Schneier väittää blogissaan, että tällainen hyökkäys on todellisuudessa mahdoton [8] .

Muistiinpanot

↑ "Announcing Request for Candidate Algorithm Nominations for the Advanced Encryption Standard (AES)" Arkistoitu 5. kesäkuuta 2011 Wayback Machinessa . Kauppaministeriö – National Institute of Standards and Technology – Federal Register: 12. syyskuuta 1997.
↑ Nechvatal J., Barker E., Bassham L., Burr W., Dworkin M., Foti J., Roback E. "Report on the Development of the Advanced Encryption Standard (AES)" Arkistoitu 30. joulukuuta 2010 Wayback Machinessa (englanniksi) . — National Institute of Standards and Technology.
↑ J. Kilian ja P. Rogaway "Kuinka suojata DES: tä tyhjentävältä avainhakulta" Arkistoitu 11. kesäkuuta 2010 Wayback Machinessa 2. helmikuuta 2000
↑ N. Ferguson, J. Kelsey, B. Schneier, D. Whiting "A Twofish Retreat: Related-Key Attacks Against Reduced-Round Twofish" Arkistoitu 19. heinäkuuta 2008, Wayback Machine Twofishin tekninen raportti #6, 14. helmikuuta 2000
↑ Suresh Chari, Charanjit Jutla, Josyula R. Rao, Pankaj Rohatgi "A Cautionary Note Regarding Evaluation of AES Candidates on Smart-Cards" Arkistoitu 13. lokakuuta 2012 Wayback Machinessa , 1999
↑ Fauzan Mirza, Sean Murphy "Havainto Twofishin avainaikataulusta" Arkistoitu 21. joulukuuta 2016 Wayback Machine -tietoturvaryhmässä , Royal Holloway, Lontoon yliopisto - 26. tammikuuta 1999
↑ Shiho Moriai, Yiqun Lisa Yin "Cryptanalysis of Twofish (II)" Arkistoitu 1. kesäkuuta 2012 Wayback Machinessa - Taloustieteen, tieto- ja viestintäinsinöörien instituutissa
↑ Bruce Schneier "Twofish Cryptanalysis Rumors" Arkistoitu 9. kesäkuuta 2012 Wayback Machine -blogissa

Linkit

Twofishin verkkosivu .
Twofishin lähdekoodit .
Twofish: A 128-Bit Block Cipher Arkistoitu 29. elokuuta 2008 Wayback Machinessa .
Salausalgoritmit - AES-kilpailun finalistit .
Luettelo Twofishia käyttävistä tuotteista .

Symmetriset salausjärjestelmät
Suoratoista salauksia	A3 A5 A8 Desim F-FCSR Vilja HC-256 KCipher-2 MIKKI MUGI HAUKI Phelix RC4 Kani TIIVISTE LUMI SOSEMANUK Salsa 20 STRUMOK Trivium VMPC
Feistelin verkko	GOST 28147-89 (Magma) blowfish Camellia CAST-128 CAST-256 CIPHERUNICORN-A CIPHERUNICORN-E CLEFIA Kobra SOPIMUS DES DESX DFC E2 enRUPT FEAL HPC IDEA KASUMI Khafre Khufu LOKI97 MacGuffin MARS MESH MISTY1 UusiDES NDS RC5 RC6 SIEMEN Simon Sinopoli jätkä SM4 Speck TEE XTEA XXTEA Raiden RTEA Kolminkertainen DES Kaksi kalaa
SP verkko	Heinäsirkka 3 tapaa ABC AARIA AES (Rijndael) Akelarre Anubis BaseKing Basso Omatic Vyö CRYPTON Timantti 2 grand cru Hierocrypt-3 Hierocrypt-L1 KHAZAD Kalyna Lucifer esittää Sateenkaari TURVALLISTA HAI NELIÖ Käärme kolme kalaa
muu	SAMMAKKO NUSH REDOC SC2000 SHACAL CS-Cipher