XTEA

Extended TEA (XTEA)
Due passaggi della funzione Feistel (1 ciclo) nell'XTEA
Generale
Progettisti	Roger Needham, David Wheeler
Prima pubblicazione	1997
Derivato da	TEA
Successori	XXTEA
Dettagli
Dimensione chiave	128 bits
Dimensione blocco	64 bits
Struttura	Rete di Feistel
Numero di passaggi	variabili: raccomandati 64 passaggi della funzione Feistel (32 cicli)
Migliore crittanalisi
Nel 2004 è stato dimostrato che un attacco di crittanalisi differenziale correlato alla chiave può violare 26 dei 64 passaggi dell'XTEA con ${\displaystyle 2^{20,5}}$ testi in chiaro scelti ed un tempo di ${\displaystyle 2^{115,15}}$.

In crittografia l'XTEA (eXtended TEA) è un cifrario a blocchi che fu presentato nel 1997 da David Wheeler e Roger Needham, del dipartimento informatico dell'Università di Cambridge,^[1] per correggere le vulnerabilità scoperte nel loro algoritmo TEA. L'XTEA non è soggetto ad alcun brevetto.

La semplicità della sua struttura e la compattezza del codice rendono l'XTEA un'interessante scelta in molte situazioni dove si hanno vincoli estremi legati alle risorse, ad esempio nei vecchi sistemi hardware dove la quantità di memoria è spesso minima.

Struttura

Anche l'XTEA, come il TEA, è strutturato sulla funzione nota come rete di Feistel e opera su blocchi di dati di 64 bit, chiavi di cifratura di 128 bit e un numero consigliato di 64 passaggi. Le differenze più appariscenti rispetto al TEA sono un algoritmo di gestione della chiave più complesso e un diverso ordine delle operazioni di XOR, addizione e spostamento dei bit.

Block TEA

Insieme all'XTEA, gli autori presentarono anche un'ulteriore variante dell'algoritmo originale denominata Block TEA, che utilizzava la stessa funzione interna dell'XTEA ma applicata ciclicamente sull'intero messaggio per diverse iterazioni. Dato che opera sull'intero messaggio, il Block TEA ha la proprietà di non richiedere una modalità di funzionamento.

Nel 1998 Saarinen mostrò un attacco portato al Block TEA nella sua interezza, attacco che scovò anche una vulnerabilità nel successore del Block TEA, l'XXTEA.

Sicurezza

Il miglior attacco all'XTEA è stato descritto da Youngdai Ko e altri autori che nel 2004 hanno mostrato come utilizzare la crittanalisi differenziale correlata alla chiave per violare 26 dei 64 passaggi dell'XTEA, attacco che richiede ${\displaystyle 2^{20,5}}$ testi in chiaro scelti e un tempo di ${\displaystyle 2^{115,15}}$.

Implementazioni

Quelle che seguono sono le funzioni di cifratura e decifratura dell'XTEA, pubblicate nel pubblico dominio dagli autori, scritte in linguaggio C:

#include <stdint.h>

/* riceve 64 bit di dati in v[0] e v[1] e una chiave a 128 bit in key[0]..key[3] */

void encipher(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) {
    unsigned int i;
    uint32_t v0=v[0], v1=v[1], sum=0, delta=0x9E3779B9;
    for (i=0; i < num_rounds; i++) {
        v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
        sum += delta;
        v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
    }
    v[0]=v0; v[1]=v1;
}

void decipher(unsigned int num_rounds, uint32_t v[2], uint32_t const key[4]) {
    unsigned int i;
    uint32_t v0=v[0], v1=v[1], delta=0x9E3779B9, sum=delta*num_rounds;
    for (i=0; i < num_rounds; i++) {
        v1 -= (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
        sum -= delta;
        v0 -= (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
    }
    v[0]=v0; v[1]=v1;
}

Il codice è stato leggermente modificato per aggiornarlo all'evoluzione hardware e ora funziona sui sistemi a 64 bit grazie all'uso del tipo uint32_t, fornito dalla libreria stdint.h. Sono state anche aggiunte nelle formule le parentesi tonde che nel sorgente originale erano state tolte per sfruttare le regole di precedenza del linguaggio. In Java va usato il tipo di dato int e l'operatore >>> al posto di >>.

Il valore raccomandato per il parametro num_rounds è 32 e non 64, dato che per ogni iterazione il ciclo esegue 2 passaggi della rete di Feistel. Per incrementare la velocità si possono precalcolare i valori di sum+k[].

Note

1. Sito ufficiale del Computer Laboratory of Cambridge University

Bibliografia

• Youngdai Ko, Seokhie Hong, Wonil Lee, Sangjin Lee e Jongin Lim. "Related-key attack|Related key differential attacks on 26 rounds of XTEA and full rounds of GOST." In Proceedings of FSE '04 - Lecture Notes in Computer Science, 2004 (Springer Science+Business Media|Springer-Verlag)
• Seokhie Hong, Deukjo Hong, Youngdai Ko, Donghoon Chang, Wonil Lee e Sangjin Lee. "Differential cryptanalysis of TEA and XTEA." - Proceedings of ICISC 2003 (2003b)
• Dukjae Moon, Kyungdeok Hwang, Wonil Lee, Sangjin Lee e Jongin Lim. "Impossible differential cryptanalysis of reduced round XTEA and TEA." - Lecture Notes in Computer Science, 2365: 49-60, 2002. ISSN 0302-9743.
• Roger M. Needham and David J. Wheeler. "Tea extensions." Technical report, Computer Laboratory, University of Cambridge (1997) (PDF).

Voci correlate

• RC4 - Un cifrario a flusso che, come l'XTEA, è disegnato per essere molto semplice da implementare
• XXTEA - Corrected Block TEA, il successore dell'XTEA
• Tiny Encryption Algorithm, l'algoritmo precursore dell'XTEA

Collegamenti esterni

• Diagramma di flusso dell'XTEA (JPG), su commons.wikimedia.org.
• Implementazione in Java dell'XTEA (TXT), su 143.53.36.235:8080. URL consultato il 15 ottobre 2008 (archiviato dall'url originale l'8 dicembre 2008).
• Vettori di test per il TEA e l'XTEA, su cix.co.uk.
• Implementazione in PHP dell'XTEA, su php-einfach.de.
• Implementazione in Pascal/Delphi dell'XTEA, su irnis.net. URL consultato il 15 ottobre 2008 (archiviato dall'url originale il 22 ottobre 2008).
• Implementazione in Python dell'XTEA, su aspn.activestate.com.