XTEA

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 29. huhtikuuta 2016 tarkistetusta versiosta . tarkastukset vaativat 8 muokkausta .
XTEA
Luoja David Wheeler ja Roger Needham
Luotu 1997_ _
julkaistu 1997_ _
Avaimen koko 128 bittinen
Lohkon koko 64-bittinen
Kierrosten lukumäärä 64
Tyyppi Feistelin verkko

Salaustekniikassa XTEA (eXtended TEA )  on lohkosalausalgoritmi, joka on suunniteltu poistamaan kriittiset virheet TEA -algoritmissa . Salauksen kehittäjät ovat David Wheeler ja Roger Needham (tietotekniikan laitos , Cambridgen yliopisto ). Algoritmi esiteltiin julkaisemattomassa teknisessä raportissa vuonna 1997 [1] . Salaus ei ole patentoitu, sitä käytetään laajalti useissa salaussovelluksissa ja monissa laitteistoissa sen erittäin alhaisten muistivaatimusten ja helppokäyttöisyyden vuoksi.

Salausominaisuudet

Kuten TEA , salaus perustuu 64-bittisiin lohkotoimintoihin, siinä on 32 täyttä jaksoa, jokaisessa täydessä jaksossa on kaksi Feistel Network -kierrosta , mikä tarkoittaa 64 Feistel Network -kierrosta. Kierrosten lukumäärää paremman diffuusion saavuttamiseksi voidaan kuitenkin lisätä suorituskyvyn kustannuksella. Lisäksi XTEA, kuten TEA, käyttää 128-bittistä avainta, joka koostuu neljästä 32-bittisestä sanasta K[0], K[1], K[2] ja K[3]. XTEA:lla ei ole avainaikataulutusalgoritmia tavallisessa mielessä. Määrittääkseen, mitä neljästä avainsanasta käytetään kullakin kierroksella, algoritmi käyttää vakiota δ = 9E3779B9 16 . TEA:ssa tällaista jakelua ei ole. Toinen ero TEA:sta on salauksessa käytettyjen bittitoimintojen permutaatio . Näiden parannusten ansiosta XTEA ei ole kokenut suuria komplikaatioita TEA:han verrattuna, mutta samalla eliminoi kaksi TEA-algoritmin päähaittaa [1] :

Algoritmin kuvaus

XTEA käyttää seuraavia loogisia operaatioita: XOR , bittisiirto ja looginen AND . Lisäksi XTEA käyttää kokonaislukujen yhteenlaskutoimintoa modulo 2 32 , joita merkitään x y (x ja y Z 2 32 ). Yksinomainen "OR" Boolen logiikassa merkitään x y:llä ja C -kielellä x ^ y. Looginen "AND" Boolen logiikassa on x y C-kielellä - x & y. Looginen x:n siirtymä y bitillä vasemmalle on merkitty x y:llä ja x:n looginen siirtymä y bitillä oikealle on merkitty x y:llä. Olkoon algoritmin n:nnen (1 ≤ n ≤ 64) kierroksen syöte (L n ,R n ), ja tulos on (L n+1 ,R n+1 ), jossa L n+1 = R n . Rn +1 lasketaan seuraavasti:

jos n = 2 * i - 1, jos 1 ≤ i ≤ 32, niin R n+1 = L n + ({ (R n 4 R n 5) R n } ({ i - 1 } * δ K [ ({ i ) — 1 } * δ) 3 ]),

jos n = 2 * i, jos 1 ≤ i ≤ 32, niin R n+1 = L n + ({ (R n 4 R n 5) R n } (i * δ K [ (i * δ 11) 3 ]) .

Koska tämä on lohkosalaus, jossa lohkon pituus on 64 bittiä ja datan pituus ei välttämättä ole 64 bitin kerrannainen, kaikkien lohkon 64-bitin kerrannaiseksi täydentävien tavujen arvoksi asetetaan 0x01 .

Kryptanalysis algoritmi

Uskotaan, että XTEA on turvallisempi kuin TEA, mutta on mahdollista poimia hyökkäystyyppi, jolle XTEA on haavoittuvampi [3] . Ensimmäinen lähestymistapa on differentiaaliset hyökkäykset . Koska TEA käyttää modulo 2 -lisäystä 32 kierroksen näppäimestä ja syöttää selkeää tekstiä, ja XTEA käyttää XOR:ta, on helpompi hyökätä XTEA:han kuin TEA:han. 14 XTEA-kierroksen jälkeen voidaan rakentaa differentiaalinen ominaisuus todennäköisyydellä 2 −57,79 ja käyttää sitä rikkomaan XTEA, joka sisältää 16 kierrosta (tämä hyökkäys vaatii 2 61 valittua selkeää tekstiä). Samaan aikaan TEA:n on vaikea rakentaa hyvää eroa. Toinen lähestymistapa on katkaistu differentiaalinen hyökkäys. Kahdeksan TEA- ja XTEA-kierroksen jälkeen voidaan muodostaa katkaistu erokäyrä todennäköisyydellä 1. Tällä hyökkäyksellä on mahdollista rikkoa XTEA enintään 23 kierrosten lukumäärällä ja TEA enintään 17 kierrosten määrällä. havaitaan kunkin algoritmin tärkeimpien suunnitteluominaisuuksien vuoksi.

Menestynein julkaistu hyökkäys XTEA:ta vastaan ​​on linkitetyn avaimen differentiaalihyökkäys, joka pystyy murtamaan 37 algoritmin 64 kierroksesta käyttämällä 263 valittua selkeää tekstiä, joiden aikamonimutkaisuus on 2125 . Jos tarkastellaan heikkojen avainten osajoukkoa, joka sisältää 2 107,5 avainta 2 128 :sta , niin tämä hyökkäys pystyy murtamaan 51 algoritmin 64 kierroksesta aikakompleksisuudella 2 123 [4] .

Esimerkki algoritmin toteutuksesta

C - kielen toteutus (muokattu David Wheelerin ja Roger Needhamin [1] artikkelissa esitetystä koodista ) salauksesta ja salauksen purkamisesta XTEA-algoritmilla:

#include <stdint.h> void xtea_encipher ( unsigned int num_rounds , uint32_t * v , uint32_t const * k ) { allekirjoittamaton int i ; uint32_t v0 = v [ 0 ], v1 = v [ 1 ], summa = 0 , delta = 0x9E3779B9 ; for ( i = 0 ; i < kierrosten_määrä ; i ++ ) { v0 += ((( v1 << 4 ) ^ ( v1 >> 5 )) + v1 ) ^ ( summa + k [ summa & 3 ]); summa += delta ; v1 += ((( v0 << 4 ) ^ ( v0 >> 5 )) + v0 ) ^ ( summa + k [( summa >> 11 ) & 3 ]); } v [ 0 ] = v0 ; v [ 1 ] = v1 ; } void xtea_decipher ( unsigned int num_rounds , uint32_t * v , uint32_t const * k ) { allekirjoittamaton int i ; uint32_t v0 = v [ 0 ], v1 = v [ 1 ], delta = 0x9E3779B9 , summa = delta * kierrosten_määrä ; for ( i = 0 ; i < kierrosten_määrä ; i ++ ) { v1 -= ((( v0 << 4 ) ^ ( v0 >> 5 )) + v0 ) ^ ( summa + k [( summa >> 11 ) & 3 ]); summa -= delta ; v0 -= ((( v1 << 4 ) ^ ( v1 >> 5 )) + v1 ) ^ ( summa + k [ summa & 3 ]); } v [ 0 ] = v0 ; v [ 1 ] = v1 ; }

Kommentit:

  • v - lähdeteksti, joka koostuu kahdesta 32 bitin sanasta
  • k - avain, joka koostuu neljästä 32-bittisestä sanasta
  • num_rounds — algoritmijaksojen määrä (suositus 32)
  • kierrosten lukumäärän on oltava sama salaukselle ja salauksen purkamiselle, jos num_rounds==0, salausta tai salauksen purkamista ei tapahdu

Muutokset alkuperäiseen koodiin:

  • uint32_t-tyyppiä käytetään, koska se on aina 32 bitin kokoinen, toisin kuin pitkä (joka on alkuperäisessä koodissa), joka voi sisältää 64 bittiä (esimerkiksi joissakin 64-bittisissä järjestelmissä)
  • lähdekoodi ei käytä const-tyyppiä
  • redundantit hakasulkeet lausekkeissa v0 ja v1 jätetään pois lähdekoodista, tässä muutoksessa ne jätetään selkeyden vuoksi

Algoritmin versiot

Avainaikataulussa löydetyt haavoittuvuudet ja onnistuneet hyökkäykset TEA- , XTEA- ja XXTEA- algoritmeja vastaan ​​johtivat useiden kryptaanalyytikoiden vaihtoehtoisten salausten luomiseen. Erityisesti tällä hetkellä on olemassa TEA -perheen salakirjoihin perustuvia algoritmeja RTEA (Sean O'Neill), Raiden (Julio Castro), XTEA-1, XTEA-2 ja XTEA-3 [5] (Tom St. Denis) . Näitä modifikaatioita ei kuitenkaan ole tutkittu niin laajasti, eivätkä ne ole saaneet riittävää käytännön sovellusta.

Algoritmi XTEA-1

Yksi XTEA:n haavoittuvuuksista on, että avaimen bitit vaikuttavat samoihin bitteihin algoritmin jokaisella kierroksella. Tämä ongelma voidaan poistaa käyttämällä salausta, joka sisältää avaimen ajoitusalgoritmin. Avainten ajoitus on dynaamista eikä vaadi muistin varaamista. Näppäinajoitus tehdään syklisellä avaimen bittisiirrolla selkotekstistä riippuvalla arvolla. XTEA-1-algoritmi toteuttaa tämän idean XTEA-salauksen vahvistamisesta muuttamalla hieman salauksen rakennetta muuttamatta algoritmin perusperiaatteita.

Salaus käyttää whitewashing-tekniikkaa ja tiedoista riippuvaa aliavainmuunnoksia, mikä vaikeuttaa kryptausanalyysiä , koska alkuperäinen algoritmi sisälsi haavoittuvuuden - tiettyjen avainbittien modifikaatio heijastui vastaaviin salatekstin bitteihin.

XTEA-1:n toteutus C -kielellä :

#include <stdint.h> uint32_t rol ( uint32_t base , uint32_t shift ) { uint32_t res ; /* vain 5 bittiä muutos on merkitsevää*/ vaihto &= 0x1F ; res = ( kanta << siirto ) | ( pohja >> ( 32 - vuoro )); return res ; } void xtea1_encipher ( unsigned int num_rounds , uint32_t * v , uint32_t const * k ) { allekirjoittamaton int i ; uint32_t y , z , summa = 0 , delta = 0x9E3779B9 ; /* lataa ja esivalko rekisterit */ y = v [ 0 ] + k [ 0 ]; z = v [ 1 ] + k [ 1 ]; /* Pyöreät funktiot */ for ( i = 0 ; i < kierrosten_määrä ; i ++ ) { y += (( z << 4 ) ^ ( z >> 5 )) + ( z ^ summa ) + rol ( k [ summa & 3 ], z ); summa += delta ; z += (( y << 4 ) ^ ( y >> 5 )) + ( y ^ summa ) + rol ( k [( summa >> 11 ) & 3 ], y ); } /* postittaa valkoinen ja kaupparekisterit */ v [ 0 ] = y ^ k [ 2 ]; v [ 1 ] = z ^ k [ 3 ]; } void xtea1_decipher ( unsigned int num_rounds , uint32_t * v , uint32_t const * k ) { allekirjoittamaton int i ; uint32_t y , z , delta = 0x9E3779B9 , summa = delta * kierrosten_määrä ; z = v [ 1 ] ^ k [ 3 ]; y = v [ 0 ] ^ k [ 2 ]; for ( i = 0 ; i < kierrosten_määrä ; i ++ ) { z -= (( y << 4 ) ^ ( y >> 5 )) + ( y ^ summa ) + rol ( k [( summa >> 11 ) & 3 ], y ); summa -= delta ; y -= (( z << 4 ) ^ ( z >> 5 )) + ( z ^ summa ) + rol ( k [ summa & 3 ], z ); } v [ 1 ] = z - k [ 1 ]; v [ 0 ] = y - k [ 0 ]; }

"Roll"-toiminto suorittaa näppäimen syklisen bittisiirron käyttämällä vähiten merkitsevää 5 bittiä. Tämä algoritmi käyttää vain yhtä vuoroa kierrosta kohti, mikä on varsin tehokasta ja nopeaa useimmissa nykyaikaisissa prosessoreissa .

Algoritmi XTEA-2

On mahdollista vaihtaa XTEA-1 käyttämällä 128-bittistä lohkoa. Tuloksena oleva algoritmi vaatii enemmän kierroksia, mutta sen salausnopeus on suurempi kuin XTEA:n.

XTEA-2:n käyttöönotto C :ssä :

#include <stdint.h> void xtea2_encipher ( unsigned int num_rounds , uint32_t * v , uint32_t const * k ){ allekirjoittamaton int i ; uint32_t a , b , c , d , summa = 0 , t , delta = 0x9E3779B9 ; a = v [ 0 ]; b = v [ 1 ] + k [ 0 ]; c = v [ 2 ]; d = v [ 3 ] + k [ 1 ]; for ( i = 0 ; i < kierrosten_määrä ; i ++ ) { a += (( b << 4 ) ^ ( b >> 5 )) + ( d ^ summa ) + rol ( k [ summa & 3 ], b ); summa += delta ; c += (( d << 4 ) ^ ( d >> 5 )) + ( b ^ summa ) + rol ( k [( summa >> 11 ) & 3 ], d ); t = a ; a = b _ b = c ; c = d ; d = t ; } v [ 0 ] = a ^ k [ 2 ]; v [ 1 ] = b ; v [ 2 ] = c ^ k [ 3 ]; v [ 3 ] = d ; } void xtea2_decipher ( unsigned int num_rounds , uint32_t * v , uint32_t const * k ){ allekirjoittamaton int i ; uint32_t a , b , c , d , t , delta = 0x9E3779B9 , summa = delta * kierrosten_määrä ; d = v [ 3 ]; c = v [ 2 ] ^ k [ 3 ]; b = v [ 1 ]; a = v [ 0 ] ^ k [ 2 ]; for ( i = 0 ; i < kierrosten_määrä ; i ++ ) { t = d_ _ d = c ; c = b _ b = a ; a = t_ _ c -= (( d << 4 ) ^ ( d >> 5 )) + ( b ^ summa ) + rol ( k [( summa >> 11 ) & 3 ], d ); summa -= delta ; a -= (( b << 4 ) ^ ( b >> 5 )) + ( d ^ summa ) + rol ( k [ summa & 3 ], b ); } v [ 0 ] = a ; v [ 1 ] = b - k [ 0 ]; v [ 2 ] = c ; v [ 3 ] = d - k [ 1 ]; }

Tämän algoritmin tärkein etu on kyky salata suuria lohkoja. Tämä algoritmi käyttää samoja perustoimintoja kuin XTEA-1, mutta vaatii enemmän iteraatioita. Se vaatii itse asiassa kaksi kertaa enemmän iteraatioita 32-64 (64-128 kierrosta). 48 iteraatio on kompromissi salauksen nopeuden ja luotettavuuden välillä.

Algoritmi XTEA-3

Toinen XTEA-1:n luonnollinen laajennus on 256-bittisen avaimen ja käytännöllisemmän 128-bittisen lohkon käyttö. Tämä algoritmi vaatii 32-64 iteraatiota, mutta tarjoaa samalla luotettavan suojan hyökkäyksiä vastaan ​​kattavalla haulla. Salaus käyttää whitewashing-tekniikkaa ja toteuttaa avaimesta riippuvaisia ​​operaatioita, mikä tekee kryptan analysoinnista vaikeaa.

XTEA-3:n käyttöönotto C :ssä :

#include <stdint.h> void xtea3_encipher ( unsigned int num_rounds , uint32_t * v , uint32_t const * k ) { allekirjoittamaton int i ; uint32_t a , b , c , d , summa = 0 , t , delta = 0x9E3779B9 ; summa = 0 ; a = v [ 0 ] + k [ 0 ]; b = v [ 1 ] + k [ 1 ]; c = v [ 2 ] + k [ 2 ]; d = v [ 3 ] + k [ 3 ]; for ( i = 0 ; i < kierrosten_määrä ; i ++ ){ a += ((( b << 4 ) + rol ( k [( summa % 4 ) + 4 ], b )) ^ ( d + summa ) ^ (( b >> 5 ) + rol ( k [ summa % 4 ], b >> 27 ))); summa += delta ; c += ((( d << 4 ) + rol ( k [(( summa >> 11 ) % 4 ) + 4 ], d )) ^ ( b + summa ) ^ (( d >> 5 ) + rol ( k [( summa >> 11 ) % 4 ], d >> 27 ))); t = a ; a = b _ b = c ; c = d ; d = t ; } v [ 0 ] = a ^ k [ 4 ]; v [ 1 ] = b ^ k [ 5 ]; v [ 2 ] = c ^ k [ 6 ]; v [ 3 ] = d ^ k [ 7 ]; } void xtea3_decipher ( unsigned int num_rounds , uint32_t * v , uint32_t const * k ) { allekirjoittamaton int i ; uint32_t a , b , c , d , t , delta = 0x9E3779B9 , summa = delta * kierrosten_määrä ; d = v [ 3 ] ^ k [ 7 ]; c = v [ 2 ] ^ k [ 6 ]; b = v [ 1 ] ^ k [ 5 ]; a = v [ 0 ] ^ k [ 4 ]; for ( i = 0 ; i < kierrosten_määrä ; i ++ ){ t = d_ _ d = c ; c = b _ b = a ; a = t_ _ c -= ((( d << 4 ) + rol ( k [(( summa >> 11 ) % 4 ) + 4 ], d )) ^ ( b + summa ) ^ (( d >> 5 ) + rol ( k [( summa >> 11 ) % 4 ], d >> 27 ))); summa -= delta ; a -= ((( b << 4 ) + rol ( k [( summa % 4 ) + 4 ], b )) ^ ( d + summa ) ^ (( b >> 5 ) + rol ( k [ summa % 4 ], b >> 27 ))); } v [ 3 ] = d - k [ 3 ]; v [ 2 ] = c - k [ 2 ]; v [ 1 ] = b - k [ 1 ]; v [ 0 ] = a - k [ 0 ]; }

XTEA-3 käyttää 5 MSB:tä ja 5 LSB:tä selväkielirekisteristä avaimen kiertämiseen, koska tilastot osoittavat, että nämä bitit ovat alttiimpia muutoksille. Tämä algoritmi vaatii myös vähintään 32 iteraatiota, mutta 48 iteraatiota on kompromissi tiedon salauksen nopeuden ja luotettavuuden välillä.

XTEA-laajennuksen eri versioiden vertailu

Nämä kolme algoritmia ovat TEA : n ja XTEA:n luonnollisia laajennuksia. Niiden erottuvia piirteitä alkuperäisiin salausalgoritmeihin verrattuna ovat parempi avainaikataulu ja suurempi lohko- ja/tai avaimen koko. Selkeästä tekstistä dynaamisesti riippuvien avainten käyttö tarkoittaa, että näppäinten käytölle ei ole ennalta määrättyä järjestystä eikä muistin varaamista tarvita. Tämä on varsin hyödyllinen ominaisuus, koska useimmin käytettyjen avainten löytäminen vaikeutuu. Salaukset ovat turvallisempia differentiaalista kryptausanalyysiä vastaan , koska avaimen bitit voivat vaikuttaa muihin salatekstin bitteihin. Epälineaarisen algebran käyttö (lisäys modulo 2 32 pois lukien "OR") on tehokas lineaarista kryptausanalyysiä vastaan . Lisäksi näiden toimintojen käyttö ei tuo haavoittuvuuksia algoritmeihin.

Ensimmäisellä algoritmilla (XTEA-1) on suurin nopeus ja riittävällä kierrosmäärällä (32-64) hyvä luotettavuus. XTEA-2 on suurempi lohkolaajennus, eikä se ole turvallisempi kuin XTEA-1. XTEA-3 on algoritmin laajennus käyttämällä suurempaa lohkokokoa ja avainta. Kolmas vaihtoehto on hieman hitaampi, mutta turvallisempi. Koska nämä algoritmit perustuvat alkuperäiseen TEA :han ja poistavat kaikki tunnetut puutteet, niitä voidaan pitää varsin luotettavina.

Vertaileva algoritmitaulukko:

Algoritmin nimi Kierrosten vähimmäismäärä Kierrosten enimmäismäärä Lohkon koko Avaimen koko
XTEA-1 32 64 64 bittiä 128 bittinen
XTEA-2 64 128 128 bittinen 128 bittinen
XTEA-3 64 128 128 bittinen 256 bittiä

Nämä algoritmit vaativat kuitenkin vielä tarkennusta. Ensimmäinen ongelma on, että vain vähiten merkitseviä selkeän tekstin bittejä käytetään avaimen sykliseen bittisiirtoon (kuten XTEA-1:ssä ja XTEA-2:ssa). Toinen ongelma on, että avain on jaettu kahteen 4 elementin alaryhmään, ja jokainen lausekkeen osa käyttää vain yhtä alaryhmää (kuten XTEA-3:ssa). XTEA-3:a voidaan laajentaa käyttämällä kaikkia kahdeksaa elementtiä lausekkeen molemmissa osissa. Jos nämä parannukset tehdään, algoritmista tulee käytännöllisempi, mutta silloin se on liian erilainen kuin alkuperäinen TEA.

Katso myös

Muistiinpanot

  1. ↑ 1 2 3 A. Roger M. Needham ja David J. Wheeler. Tea extensions Arkistoitu 20. syyskuuta 2017 Wayback Machinessa
  2. ↑ John Kelsey, Bruce Schneier, David Wagner. Aiheeseen liittyvä 3-WAY, Biham-DES, CAST, DES-X, NewDES, RC2, TEA  (linkki ei käytettävissä)
  3. ↑ Seokhie Hong, Deukjo Hong, Youngdai Ko, Donghoon Chang, Wonil Lee, Sangjin Lee. TEA:n ja XTEA:n differentiaalinen kryptaanalyysi  (linkki ei saatavilla)
  4. ↑ Charles Bouillaguet, Orr Dunkelman, Gaetan Leurent ja Pierre-Alain Fouque. Toinen katsaus täydennysominaisuuksiin Arkistoitu 6. heinäkuuta 2017 Wayback Machinessa
  5. ↑ Tom St Denis. Laajennetut TEA-algoritmit arkistoitu 27. elokuuta 2018 Wayback Machinessa

Linkit

  • David J. Wheeler ja Roger M. Needham. Korjaus xteaan. Tekninen raportti, Computer Laboratory, University of Cambridge, lokakuu 1998 (PDF) .
  • Dukjae Moon, Kyungdeok Hwang, Wonil Lee, Sangjin Lee ja Jongin Lim. "Mahdoton differentiaalinen kryptaanalyysi vähennetyn kierroksen XTEA:sta ja TEA:sta." Center for Information and Security Technologies (CIST), 2004 (PDF)  (linkki ei saatavilla) .
Toteutukset
 Symmetriset salausjärjestelmät
Suoratoista salauksia
Feistelin verkko
SP verkko
Muut