XXTEA

XXTEA
Dues rondes Feistel (un cicle) de TEA
Detall
EstructuraXarxa del tipus Feistel desbalancejada

En criptografia, Corrected Block TEA (sovint referit com a XXTEA) és un xifratge de blocs dissenyat per corregir les debilitats del Block TEA original.[1][2]

XXTEA és vulnerable a un atac de text pla escollit que requereix 259 consultes i un treball insignificant. Vegeu la criptoanàlisi a continuació.

Els dissenyadors del xifrat van ser Roger Needham i David Wheeler del Cambridge Computer Laboratory, i l'algoritme es va presentar en un document inèdit d'informe tècnic, l'octubre de 1998 (Wheeler i Needham, 1998). No està subjecte a cap patent.[3]

Parlant formalment, XXTEA és un xifratge de blocs heterogeni UFN (xarxa Feistel desequilibrada) heterogeni i incomplet i consistent. XXTEA opera en blocs de longitud variable que són uns múltiples arbitraris de 32 bits de mida (mínim 64 bits). El nombre de cicles complets depèn de la mida del bloc, però n'hi ha almenys sis (pugen a 32 per a blocs petits). El Block TEA original aplica la funció de rodona XTEA a cada paraula del bloc i la combina de manera additiva amb la seva veïna més a l'esquerra. La velocitat de difusió lenta del procés de desxifrat es va aprofitar immediatament per trencar el xifrat. El bloc corregit TEA utilitza una funció rodona més implicada que fa ús dels dos veïns immediats per processar cada paraula del bloc.

És probable que XXTEA sigui més eficient que XTEA per a missatges més llargs.

Needham & Wheeler fan els següents comentaris sobre l'ús de Block TEA: Per facilitar l'ús i la seguretat general, s'ha de preferir la versió de bloc gran quan sigui aplicable pels motius següents.

  • Un sol canvi de bit canviarà aproximadament la meitat dels bits de tot el bloc, sense deixar cap lloc on comencen els canvis.
  • No hi ha cap opció de modalitat implicada.
  • Fins i tot si s'utilitza l'ús correcte de canviar sempre les dades enviades (possiblement per un número de missatge), només missatges idèntics donen el mateix resultat i la fuga d'informació és mínima.
  • El número de missatge sempre s'ha de comprovar, ja que aquesta redundància és la comprovació d'un missatge aleatori acceptat.
  • Els atacs tallar i unir no semblen ser possibles.
  • Si no és acceptable tenir missatges molt llargs, es poden dividir en trossos, per exemple, de 60 paraules i encadenar-los de manera anàloga als mètodes utilitzats per DES.

Tanmateix, a causa de la naturalesa incompleta de la funció rodona, es poden trobar dos grans textos xifrats de 53 o més paraules de 32 bits idèntiques en totes menys 12 paraules mitjançant una simple cerca de col·lisió de força bruta que requereix 2 96 − N memòria, 2 N temps. i 2 N +2 96 − N textos senzills escollits, és a dir, amb una complexitat total de temps*memòria de 2 96, que en realitat és de 2 paraules*cicles complets/2 per a qualsevol xifrat d'aquest tipus. Actualment es desconeix si aquestes col·lisions parcials representen alguna amenaça per a la seguretat del xifrat. Vuit cicles complets elevarien el llistó per a aquesta recerca de col·lisions per sobre de la complexitat dels atacs paral·lels de força bruta.

La mida inusualment petita de l'algorisme XXTEA el convertiria en una opció viable en situacions en què hi ha limitacions extremes, com ara sistemes de maquinari heretats (potser integrats) on la quantitat de RAM disponible és mínima, o, alternativament, ordinadors d'una sola placa com el Raspberry Pi, Banana Pi o Arduino.

Cripanàlisi

[modifica]

Un atac publicat l'any 2010 per E. Yarrkov presenta un atac de text pla escollit contra XXTEA de ronda completa amb bloc ample, que requereix 259 consultes per a una mida de bloc de 212 bytes o més i un treball insignificant. Es basa en la criptoanàlisi diferencial.[4]

Per xifrar "212 bytes o més" l'algorisme realitza només 6 rondes, i els patrons de bits escollits amb cura permeten detectar i analitzar l'efecte d'allau.

Codi de referència

[modifica]

La formulació original de l'algoritme Corrected Block TEA, publicat per David Wheeler i Roger Needham, és la següent: [5][6]

 #define DELTA 0x9e3779b9
 #define MX ((z>>5^y<<2) + (y>>3^z<<4) ^ (sum^y) + (k[p&3^e]^z))

 long btea(long* v, long n, long* k) {
 unsigned long z=v[n-1], y=v[0], sum=0, e, DELTA=0x9e3779b9;
 long p, q ;
 if (n > 1) { /* Coding Part */
 q = 6 + 52/n;
 while (q-- > 0) {
 sum += DELTA;
 e = (sum >> 2) & 3;
 for (p=0; p<n-1; p++) y = v[p+1], z = v[p] += MX;
 y = v[0];
 z = v[n-1] += MX;
 }
 return 0 ; 
 } else if (n < -1) { /* Decoding Part */
 n = -n;
 q = 6 + 52/n;
 sum = q*DELTA ;
 while (sum != 0) {
 e = (sum >> 2) & 3;
 for (p=n-1; p>0; p--) z = v[p-1], y = v[p] -= MX;
 z = v[n-1];
 y = v[0] -= MX;
 sum -= DELTA;
 }
 return 0;
 }
 return 1;
 }

Referències

[modifica]
  1. ↑ Matthew D. Russell. «Tinyness: An Overview of TEA and Related Ciphers» (en anglès), 27-02-2004. Arxivat de l'original el 2007-08-12.
  2. ↑ Roger M. Needham and David J. Wheeler. «Tea extensions» (en anglès). Computer Laboratory, Cambridge University, England, 01-10-1997. [Consulta: 4 juliol 2008].
  3. ↑ «Cryptanalysis of XXTEA» (en anglès). [Consulta: 1r octubre 2024].
  4. ↑ Elias Yarrkov Cryptology ePrint Archive, 04-05-2010.
  5. ↑ David J. Wheeler and Roger M. Needham. «Correction to XTEA». Computer Laboratory, Cambridge University, England, 01-10-1998. [Consulta: 4 juliol 2008].
  6. ↑ «xxtea: xxtea is a simple block cipher» (en anglès). [Consulta: 1r octubre 2024].