Twofish — AES konkurso finalistas: simetrinis 128/256 bitų blokinis šifras

Kriptografijoje "Twofish" yra simetrinio rakto blokinis šifras, kurio bloko dydis yra 128 bitai, o rakto ilgis - iki 256 bitų. Twofish buvo sukurtas su tikslu suteikti saugų, lankstų ir efektyvų blokinį šifrą tiek programinei, tiek aparatinei įgyvendinimui.

Konkursas ir istorija

1997 m. NIST paskelbė konkursą DES įpėdiniui, kuris bus vadinamas AES, išrinkti. Twofish buvo vienas iš penkių Advanced Encryption Standard konkurso finalininkų, tačiau nebuvo pasirinktas kaip standartas. Nors Twofish nelaimėjo AES konkurso, jis išliko vertinamas dėl savo dizaino kūrybiškumo ir stiprios saugumo analizės.

Struktūra ir pagrindinės savybės

"Twofish" yra glaudžiai susijęs su ankstesniu blokiniu šifru Blowfish", tačiau turi reikšmingų skirtumų ir patobulinimų. Pagrindinės Twofish ypatybės:

Raktų dydžiai: palaikomi iki 256 bitų (dažniausiai 128, 192 ir 256 bitų variantai).
Bloko dydis: 128 bitų.
Feistelio struktūra: naudojama 16 raundų Feistelio tinklo architektūra kartu su įėjimo ir išėjimo whitening (raktų maskavimu) mechanizmu.
S-dėžutės: iš anksto apskaičiuotos, nuo rakto priklausomos S-dėžučių naudojimas — tai leidžia, kad dalis S-laukų formavimo priklauso nuo rakto ir taip padidinamas šifro atsparumas tam tikroms atakoms.
Sudėtingas raktų tvarkaraštis: Twofish naudoja gana sudėtingą raktų tvarkaraštį, kurio metu raktas dalijamas į dalis, iš kurių viena naudojama tiesioginiam šifravimui, o kita — šifro vidiniams parametrams (pvz., S-laukams).
MDS matrica ir q-laukai: h funkcija naudoja fiksuotas q-pakeitimo lenteles ir MDS (Maximum Distance Separable) matricą, kad užtikrintų gerą išsklaidymą.
PHT transformacija: taikoma pseudo-Hadamardo transformacija (PHT), kilusi iš SAFER šeimos šifrų.

Dizainas trumpai (techniniai aspektai)

Twofish raktų tvarkaraštis ir S-laukų generavimo mechanizmas naudoja klavišų padalijimą: pusė n bitų rakto naudojama kaip tikrasis šifravimo raktas, o kita pusė n bitų rakto — kaip parametrai S-dėžutėms (nuo rakto priklausantys S-laukai). S-dėžučių konstrukcija remiasi fiksuotomis q-permutacijomis ir MDS transformacijomis, todėl jos yra greitos programiniame ir aparatūriniame įgyvendinime, bet kartu raktui jautrios. Twofish taip pat naudoja įėjimo ir išėjimo raktų maskavimą (whitening), kas padidina atsparumą tiesioginėms raktų atakoms.

Veikimas ir našumas

Daugumoje programinės įrangos platformų "Twofish" yra šiek tiek lėtesnis nei "Rijndael" (pasirinktas "Advanced Encryption Standard" algoritmas) 128 bitų raktams, bet šiek tiek greitesnis 256 bitų raktams. Realiuose diegimuose našumas labai priklauso nuo optimizacijų: asamblėjos lygio optimizacijos ar specialios dėžutės (table) metodikos gali ženkliai pagerinti greitį. Aparatinė implementacija taip pat dažnai išlygina skirtumus tarp algoritmų.

Saugumas ir kriptoanalizė

Twofish buvo intensyviai analizuotas AES konkurso metu ir vėliau. Nėra žinomų praktiškai pritaikomų atakų, kurios prieštarautų pilno 16 raundų Twofish saugumui bei leistų efektyviau nei bruteforce atskleisti pilną raktą. Vis dėlto egzistuoja teorinės ar sumažintų raundų versijų atakos (pvz., susijusios su related-key modeliu), kurios nepažeidžia pilnos implementacijos praktinio saugumo, bet yra svarbios akademinei kriptoanalizei.

Autoriai ir analizės komanda

"Twofish" sukūrė Bruce'as Schneieras, Johnas Kelsey, Dougas Whitingas, Davidas Wagneris, Chrisas Hallas ir Nielsas Fergusonas; išplėstinę "Twofish" komandą", kuri susitiko atlikti tolesnę "Twofish" ir kitų AES konkurentų kriptoanalizę, sudarė Stefanas Lucksas, Tadayoshi Kohno ir Mike'as Stay. Dėl šios plačios atviros analizės Twofish dizainas yra gerai ištirtas ir dokumentuotas.

Licencijavimas ir prieinamumas

"Twofish" algoritmu gali naudotis visi norintys be jokių apribojimų. "Twofish" šifras nėra patentuotas, o jo specifikacijos programinės įrangos pavyzdys yra viešai prieinamas. Dėl atviro statuso yra prieinami referenciniai įgyvendinimai ir šaltinio kodas, todėl jį laisvai gali integruoti tiek atviro kodo, tiek komercinės programos.

Praktinis naudojimas

Nors "Twofish" nėra taip plačiai paplitęs kaip kai kurie senesni ar populiaresni algoritmai (pvz., Blowfish, kuris buvo prieinamas ilgesnį laiką), jis vis dar naudojamas kai kuriuose projektuose ir siūlomas kaip saugi alternatyva AES kai kuriose programose. Dėl geros saugumo ir našumo pusiausvyros jis yra tinkamas pasirinkimas tiek saugiai duomenų šifravimui diske, tiek kitoms simetrinio šifravimo užduotims.

Apibendrinant: Twofish yra techniškai subalansuotas, gerai ištirtas ir laisvai prieinamas blokinis šifras, skirtas 128 bitų blokams ir iki 256 bitų raktams — vertingas įrankis kriptografiniame arsenale, nors ir netapęs AES standarto dalimi.

Kriptoanalizė

Nuo 2008 m. geriausia paskelbta blokinio šifro "Twofish" kriptoanalizė yra sutrumpinta diferencinė visos 16 raundų versijos kriptoanalizė. Straipsnyje teigiama, kad sutrumpintų diferencialų atakų tikimybė yra 2-57^,3 kiekvienam blokui ir kad prireiks maždaug ²⁵¹ pasirinkto atvirojo teksto (32 PiB vertės duomenų), norint rasti gerą sutrumpintų diferencialų porą.

2005 m. tinklaraščio įraše Bruce'as Schneieras atsako, kad šiame straipsnyje nepateikiama visa kriptoanalitinė ataka, o tik kai kurios hipotetinės diferencinės savybės: Tačiau net ir teoriniu požiūriu "Twofish" nėra nė iš tolo nulaužta. Nuo 2000 m., kai šie rezultatai buvo paskelbti, nebuvo jokių jų išplėtimų".

Susiję puslapiai

Klausimai ir atsakymai

Klausimas: Kas yra "Twofish"?

A: Twofish yra simetrinis blokinis šifras, kurio bloko dydis yra 128 bitai, o rakto ilgis - iki 256 bitų.

K: Kaip Twofish susijęs su ankstesniu blokiniu šifru Blowfish?

A: Pagrindinės Twofish savybės yra iš anksto apskaičiuotų, nuo rakto priklausomų S-dėžučių naudojimas ir gana sudėtingas rakto tvarkaraštis. Pusė n bitų rakto naudojama kaip tikrasis šifravimo raktas, o kita pusė n bitų rakto naudojama šifravimo algoritmui modifikuoti (nuo rakto priklausomi S-laukai).

Klausimas: Ar "Twofish" buvo pasirinktas kaip pažangusis šifravimo standartas?

A: Ne, 1997 m. NIST paskelbė konkursą DES įpėdiniui, kuris būtų vadinamas AES, tačiau Twofish nebuvo pasirinktas kaip standartas.

K: Kokius elementus Twofish naudoja iš kitų projektų?

A.: Twofish naudoja kai kuriuos kitų konstrukcijų elementus, pavyzdžiui, pseudo-Hadamardo transformaciją (PHT) iš SAFER šeimos šifrų.

K: Ar jis naudoja Feistelio struktūrą kaip DES?

A: Taip, jame naudojama Feistelio struktūra, kaip ir DES.

K: Ar jis greitesnis už Rijndael 128 bitų raktams?

A.: Daugumoje programinės įrangos platformų "Twofish" yra šiek tiek lėtesnis už "Rijndael" 128 bitų raktams.

K: Ar 256 bitų raktams jis greitesnis už "Rijndael"?

A.: 256 bitų raktams jis šiek tiek greitesnis už "Rijndael".