TEE

TEE
Luoja David Wheeler ja Roger Needham
Luotu 1994_ _
julkaistu 1994_ _
Avaimen koko 128 bittinen
Lohkon koko 64-bittinen
Kierrosten lukumäärä 64 (32 sykliä)
Tyyppi Feistelin verkko

Salaustekniikassa Tiny Encryption Algorithm (TEA) [ 1]  on Feistel Network -tyyppinen lohkosalausalgoritmi . Algoritmin kehittivät Cambridgen yliopiston tietojenkäsittelytieteen laitoksella David Wheeler ( David Wheeler ) ja Roger Needham ( Roger Needham ), ja se esiteltiin ensimmäisen kerran vuonna 1994 [2] nopeita salausalgoritmeja käsittelevässä symposiumissa Leuvenissa ( Belgia ).

Salaus ei ole patentoitu , ja sitä käytetään laajalti useissa salaussovelluksissa ja monenlaisissa laitteistoissa sen erittäin alhaisten muistivaatimusten ja helppokäyttöisyyden vuoksi. Algoritmissa on sekä ohjelmistototeutus eri ohjelmointikielillä että laitteistototeutus FPGA - tyyppisille integroiduille piireille .

Ominaisuudet

TEA - salausalgoritmi [1] perustuu bittitoimintoihin 64-bittisellä lohkolla, ja siinä on 128-bittinen salausavain . Feistelin verkon kierrosten vakiomäärä on 64 (32 kierrosta), mutta parhaan suorituskyvyn tai salauksen saavuttamiseksi kierrosten lukumäärää voidaan vaihdella 8:sta (16 kierrosta) 64:ään (128 kierrosta). Feistelin verkko on epäsymmetrinen johtuen modulo 2 32 additio -toiminnon käytöstä overlay-toimintona .

Salauksen etuja ovat sen helppokäyttöisyys, pieni koodin koko ja melko suuri suoritusnopeus sekä mahdollisuus optimoida suoritus tavallisilla 32-bittisillä prosessoreilla, koska päätoiminnot ovat yksinomainen "OR" (XOR) , bittikohtainen siirto . ja lisääminen moduulilla 2 32 . Koska algoritmi ei käytä hakutaulukoita ja kierrosfunktio on melko yksinkertainen, algoritmi tarvitsee vähintään 16 sykliä (32 kierrosta) tehokkaan diffuusion saavuttamiseksi, vaikka täysi diffuusio saavutetaan 6 syklissä (12 kierrosta). [yksi]

Algoritmilla on erinomainen vastustuskyky lineaariselle kryptausanalyysille ja melko hyvä vastustuskyky differentiaalista kryptausanalyysiä vastaan . Tämän salausalgoritmin suurin haittapuoli on sen haavoittuvuus siihen liittyville -avainhyökkäyksille .  Yksinkertaisen näppäinajoituksen ansiosta jokaisessa avaimessa on 3 vastaavaa avainta. Tämä tarkoittaa, että avaimen tehollinen pituus on vain 126 bittiä [3] [4] , joten tätä algoritmia ei tule käyttää hash-funktiona .

Algoritmin kuvaus

Lähdeteksti on jaettu 64 bitin lohkoihin. 128-bittinen avain K on jaettu neljään 32-bittiseen aliavaimeen K[0], K[1], K[2] ja K[3]. Tämä päättää valmisteluprosessin, jonka jälkeen jokainen 64-bittinen lohko salataan 32 jaksoksi (64 kierrosta) alla olevan algoritmin mukaisesti. [5]

Oletetaan, että n:nnen kierroksen syöte (1 ≤ n ≤ 64) on oikea ja vasen osa (L n , R n ), niin n:nnen kierroksen tulos on vasen ja oikea osa (L n+1 , R n +1 ), jotka lasketaan seuraavien sääntöjen mukaisesti:

Ln +1 = Rn .

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

Jos n = 2 * i, kun 1 ≤ i ≤ 32 (parilliset kierrokset), niin R n+1 = L n ({ [ R n 4 ] K[2] } { R n i * δ } { [ R n 5 ] K[3] })

Missä

On myös ilmeistä, että TEA-salausalgoritmissa ei ole sellaisenaan avaimen ajoitusalgoritmia. Sen sijaan aliavaimia K[0] ja K[1] käytetään parittomilla kierroksilla ja K[2] ja K[3] parittomilla kierroksilla.

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

Toteutus

TEA-algoritmia käyttävien salaus- ja salauksenpurkutoimintojen toteutus C-ohjelmointikielellä (muokattu versio David Wheelerin ja Roger Needhamin [2] artikkelissa esittämästä koodista ):

#include <stdint.h> void encrypt ( uint32_t * v , const uint32_t * k ) { /* perustaa */ uint32_tv0 = v [ 0 ] ; uint32_tv1 = v [ 1 ] ; uint32_t summa = 0 ; uint32_t i ; /* avainaikataulu vakio */ uint32_t delta = 0x9e3779b9 ; /* välimuistiavain */ uint32_tk0 = k [ 0 ] ; uint32_tk1 = k [ 1 ] ; uint32_t k2 = k [ 2 ]; uint32_t k3 = k [ 3 ]; /* perussyklin aloitus */ for ( i = 0 ; i < 32 ; ++ i ) { summa += delta ; v0 += ( ( v1 << 4 ) + k0 ) ^ ( v1 + summa ) ^ ( ( v1 >> 5 ) + k1 ); v1 += ( ( v0 << 4 ) + k2 ) ^ ( v0 + summa ) ^ ( ( v0 >> 5 ) + k3 ); } /* loppujakso */ v [ 0 ] = v0 ; v [ 1 ] = v1 ; } void decrypt ( uint32_t * v , const uint32_t * k ) { /* perustaa */ uint32_tv0 = v [ 0 ] ; uint32_tv1 = v [ 1 ] ; uint32_tsum = 0xC6EF3720 ; _ uint32_t i ; /* avainaikataulu vakio */ uint32_t delta = 0x9e3779b9 ; /* välimuistiavain */ uint32_tk0 = k [ 0 ] ; uint32_tk1 = k [ 1 ] ; uint32_t k2 = k [ 2 ]; uint32_t k3 = k [ 3 ]; /* perussyklin aloitus */ for ( i = 0 ; i < 32 ; ++ i ) { v1 -= ( ( v0 << 4 ) + k2 ) ^ ( v0 + summa ) ^ ( ( v0 >> 5 ) + k3 ); v0 -= ( ( v1 << 4 ) + k0 ) ^ ( v1 + summa ) ^ ( ( v1 >> 5 ) + k1 ); summa -= delta ; } /* loppujakso */ v [ 0 ] = v0 ; v [ 1 ] = v1 ; }

Kommentit:

  • v - lähdeteksti, joka koostuu kahdesta 32 bitin osasta
  • k on avain, joka koostuu neljästä 32-bittisestä osasta

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

Cryptanalysis

Tämän algoritmin oletetaan tarjoavan IDEA -salausalgoritmiin verrattavaa turvallisuutta , koska se käyttää samaa ajatusta ortogonaalisten algebrallisten ryhmien operaatioista . [1] Tämä lähestymistapa tarjoaa erinomaisen suojan lineaarisia kryptausanalyysitekniikoita vastaan .

Aiheeseen liittyvät avainhyökkäykset

Algoritmi on haavoittuvimmin liittyville -avainhyökkäyksille yksinkertaisen näppäinajoituksen vuoksi ( mukaan lukien avaimen ajoitusalgoritmin puuttuminen sellaisenaan). Tämän tyyppisiä hyökkäyksiä tunnetaan ainakin kolme, ne esiteltiin John Kelseyn ( John Kelsea ), Bruce Schneierin ( Bruce Schneier ) ja David Wagnerin ( David Wagner ) teoksissa vuonna 1997 [6] . Yksinkertaisimmat niistä antavat differentiaalivasteen todennäköisyydellä 2 −32 algoritmin 32 syklin jälkeen, joten vähintään 2 34 valittua selkeää tekstiä tarvitaan differentiaalivasteen löytämiseksi todennäköisyydellä 1 ja avaimen kaikkien bittien määrittämiseen. Monimutkaisempi hyökkäys, jossa yhdistyvät Eli Bihamin " linkitetyn avainhyökkäyksen " [7] ja differentiaalihyökkäyksen ideat , antaa differentiaalisen vastauksen todennäköisyydellä 2 −11 , vaatii vain 2 23 valittua selkeää tekstiä ja aikaa noin 2 32 salausaikaa (eli se vaatii bittioperaatioiden määrän luokkaa 2 32 ).  

Differentiaalinen kryptausanalyysi

TEA:n on havaittu olevan varsin kestävä differentiaalista kryptausanalyysiä vastaan . 10 kierroksen TEA-hyökkäys vaatii 2 52,5 valittua selkeää tekstiä ja sen aikamonimutkaisuus on 2 84 [8] . Paras tulos on 17 TEA-kierroksen kryptausanalyysi [9] . Tämä hyökkäys vaatii vain 1920 valittua selkeää tekstiä, mutta sen aikamonimutkaisuus on 2123,37 .

Vastaavat avaimet

Toinen TEA-algoritmin ongelma on vastaavien avainten olemassaolo. On osoitettu, että jokaisella avaimella on kolme vastinetta [4] . Tämä tarkoittaa, että tehokas avaimen pituus on vain 126 bittiä kehittäjien suunnitteleman 128 bitin sijaan, joten TEA:ta ei ole toivottavaa käyttää hash-funktiona , mikä heijastui Andrew Huangin kirjassa " Hacking the Xbox: an introduction to reverse engineering" ( "Xboxin hakkerointi: Johdatus käänteiseen suunnitteluun") esimerkkinä Microsoft Xbox -pelikonsolin hakkerointi .

Taulukko vastaavista avaimista:

K[0] K[1] K[2] K[3]
K[0] K[1] K[2] 80000000 h K[3] 80000000 h
K[0 ] 80000000h K[1] 80000000 h K[2] K[3]
K[0 ] 80000000h K[1] 80000000 h K[2] 80000000 h K[3] 80000000 h

Algoritmin laajennukset

Useiden vakavien haavoittuvuuksien ja heikkouksien löytäminen alkuperäisestä TEA-algoritmista johti sen laajennusten nopeaan luomiseen. Kaikkien näiden algoritmien tärkeimmät erot ovat parannettu näppäinaikataulu, avaimen dynaaminen riippuvuus tekstistä sekä erilainen avaimen koko, syöttölohko ja/tai Feistel-verkon kierrosten lukumäärä.

XTEA

XTEA :n lohkokoko on 64 bittiä, avaimen koko on 128 bittiä ja Feistelin verkkokierrosluku on 64. Algoritmin ovat kehittäneet David Wheeler ja Roger Needham, ja se julkaistiin vuonna 1997 . Suurin ero alkuperäiseen TEA-algoritmiin on avainten ajoitusalgoritmin olemassaolo, joka mahdollisti kriittisen haavoittuvuuden eliminoimisen "liittyviin avaimiin kohdistuville hyökkäyksille", mutta johti differentiaalisen krypta -analyysin vastustuskyvyn heikkenemiseen [9] . Tom Denisin [10] kehittämään algoritmiin on kolme muunnelmaa : XTEA-1 (lohkokoko - 64 bittiä, avaimen koko - 128 bittiä, Feistelin verkkokierrosten määrä - 32), XTEA-2 (lohkokoko - 128 bittiä, avaimen koko 128 bittiä, Feistel-verkkokierrosten määrä 64) ja XTEA-3 (lohkokoko 128 bittiä, avaimen koko 256 bittiä, Feistel-verkkokierrosten määrä 64).

XXTEA

Vuonna 1998 julkaistiin algoritmin seuraava laajennus, nimeltään XXTEA . Avaimen koko on 128 bittiä. Erottuva piirre on kyky salata kaikki lohkot, jotka ovat 64 bitin kerrannaisia, kierrosten lukumäärä on 52 + 6 * (32-bittisten sanojen määrä lohkossa) tai 52 + 12 * M lohkon pituudella 64 * M bittiä. Nimettömästi julkaistun differentiaalihyökkäyksen käytännön tehokkuutta ei ole todistettu [11] .

RTEA

TEA-algoritmista on myös vaihtoehtoinen muunnos nimeltä RTEA , jonka Marcos el Ruptor kehitti vuonna 2007 . Lohkon koko - 64 bittiä; 128-bittiselle avaimelle Feistel-verkon kierrosten määrä on 48, 256-bittisellä avaimella 64. Kehittäjien mukaan tämä algoritmi on kuitenkin XTEA:ta tuottavampi ja kestävämpi salausanalyysille [12] . , tällä algoritmilla on jo "hyökkäys toisiinsa liittyviin avaimiin" [13] .

Raiden

Geneettisten ohjelmointimekanismien avulla vuonna 2006 Julio Castron ( eng.  Julio César Hernández Castro ) johtama kehittäjäryhmä loi Raiden - algoritmin , joka on suunniteltu poistamaan TEA-salauksen haavoittuvuudet. Se toistaa lähes täsmälleen TEA-algoritmin rakenteen, paitsi että Raiden -algoritmissa on laajennettu avainaikataulutusalgoritmi. Feistel-verkoston kierrosten vakiomäärä on 32 (16 kierrosta). Raiden käyttää PRNG:n kaltaista näppäinaikataulua, muuntaa avaimen ja luo aliavaimia jokaiselle kierrokselle. Salaus läpäisee Diehard- , Sexton- ja ENT -testit [14] .

TEA-algoritmilaajennuksen eri versioiden vertailu

Tässä on vertaileva taulukko TEA-algoritmien pääominaisuuksista:

Algoritmin nimi Vakiomäärä Feistelin verkkokierroksia Lohkon koko Avaimen koko
TEE 64 64 bittiä 128 bittinen
XTEA 64 64 bittiä 128 bittinen
XTEA-1 32 64 bittiä 128 bittinen
XTEA-2 64 128 bittinen 128 bittinen
XTEA-3 64 128 bittinen 256 bittiä
XXTEA 52+12*M 64*M bittiä 128 bittinen
RTEA 48 tai 64 64 bittiä 128 tai 256 bittiä
Raiden 32 64 bittiä 128 bittinen

Samalla TEA-algoritmin kirjoittajat virallisella sivullaan [1] kiinnittävät huomiota siihen, että todellisissa käytännön käyttöolosuhteissa TEA-algoritmi on edelleen melko luotettava ja kaikki löydetyt haavoittuvuudet eivät pääsääntöisesti ole kriittinen esimerkiksi siirrettäessä dataa reaaliajassa.

Katso myös

Muistiinpanot

  1. ↑ 1 2 3 4 5 TEA-salaussivu (linkki ei ole käytettävissä) . Haettu 25. helmikuuta 2009. Arkistoitu alkuperäisestä 12. kesäkuuta 2017. 
  2. ↑ 1 2 3 Roger M. Needham ja David J. Wheeler. TEA, a Tiny Encryption Algorithm Arkistoitu 13. lokakuuta 2017 Wayback Machinessa
  3. ↑ Kelsey, John; Schneier, Bruce; Wagner, David. IDEA, G-DES, GOST, SAFER ja Triple-DES  (englanniksi)  avainaikataulun kryptausanalyysi // Tietojenkäsittelytieteen luentomuistiinpanot: päiväkirja. - 1996. - Voi. 1109 . - s. 237-251 . - doi : 10.1007/3-540-68697-5_19 .
  4. ↑ 1 2 Andem, Vikram Reddy (2003). Pienen salausalgoritmin kryptoanalyysi Arkistoitu alkuperäisestä 20. huhtikuuta 2009.
  5. ↑ Seokhie Hong, Deukjo Hong, Youngdai Ko, Donghoon Chang, Wonil Lee, Sangjin Lee, (2003). TEA:n ja XTEA:n differentiaalinen kryptaanalyysi  (linkki ei saatavilla)
  6. ↑ Kelsey, John; Schneier, Bruce; Wagner, David. 3-WAY:n, Biham-DES:n, CAST:n, DES-X NewDES:n, RC2:n ja TEA :n vastaavan avaimen kryptausanalyysi  //  Tietojenkäsittelytieteen luentomuistiinpanot: päiväkirja. - 1997. - Voi. 1334 . - s. 233-246 . - doi : 10.1007/BFb0028479 .
  7. ↑ Eli Biham, Tietojenkäsittelytieteen osasto, Technion - Israel Institute of Technology, Haifa 32000, Israel, (1992). "Uusia kryptaanalyyttisiä hyökkäyksiä käyttämällä vastaavia avaimia"  (linkki ei saatavilla)
  8. ↑ Kuu, Dukjae; Hwang, Kyungdeok; Lee, Wonil; Lee, Sangjin; Lim, Jongin. Pyöreän XTEA:n ja TEA:n mahdoton differentiaalinen kryptausanalyysi  //  Tietojenkäsittelytieteen luentomuistiinpanot: lehti. - 2002. - Voi. 2365 . - s. 49-60 . - doi : 10.1007/3-540-45661-9_4 .
  9. ↑ 1 2 Hong, Seokhie; Hong, Deukjo; Ko, Youngdai; Chang, Donghoon; Lee, Wonil; Lee, Sangjin. TEA:n ja XTEA:n differentiaalinen kryptausanalyysi  (määrittämätön)  // Proceedings of ICISC 2003. - 2003.  (pääsemätön linkki)
  10. ↑ Tom St Denis. Laajennetut TEA-algoritmit arkistoitu 27. elokuuta 2018 Wayback Machinessa
  11. ↑ Alkuperäinen artikkeli XXTEA-hyökkäyksen toteuttamisesta ja esimerkkikoodista (downlink) . Haettu 6. marraskuuta 2009. Arkistoitu alkuperäisestä 23. syyskuuta 2009. 
  12. ↑ Symmetristen kryptalgoritmien stabiiliuden vertailutulokset Arkistoitu 25. heinäkuuta 2008.  (Englanti)
  13. ↑ Asiaan liittyvä avainhyökkäys RTEA:lle.  (linkki ei saatavilla)
  14. ↑ [ Raiden: Vaihtoehto TEA Block Cipherille  ] . Haettu 6. marraskuuta 2009. Arkistoitu alkuperäisestä 5. maaliskuuta 2016. Raiden: Vaihtoehto TEA Block Cipherille 

Linkit

 Symmetriset salausjärjestelmät
Suoratoista salauksia
Feistelin verkko
SP verkko
Muut