Attacco XSL

In crittografia, l'attacco eXtended Sparse Linearization (XSL) è un metodo teorico di crittoanalisi per i cifrari a blocchi, pubblicato[1] per la prima volta nel 2002 dai ricercatori Nicolas Courtois e Josef Pieprzyk.

Questo nuovo approccio ha suscitato qualche polemica tra gli esperti di crittoanalisi[2] perché si sosteneva che fosse in grado di rompere il cifrario Advanced Encryption Standard (AES), noto anche come Rijndael, più velocemente di una ricerca esaustiva (brute force). Poiché l'AES è uno standard di cifratura accreditato dal NIST[3], ed è già ampiamente utilizzato in ambito commerciale e governativo[4] per la trasmissione di informazioni riservate e segrete, trovare una tecnica in grado di ridurre il tempo necessario per recuperare il messaggio segreto senza disporre della chiave potrebbe avere implicazioni considerevoli.

Risoluzione delle equazioni polinomiali quadratiche

[modifica | modifica wikitesto]

Nel caso generale, la risoluzione di equazioni polinomiali quadratiche su un insieme finito di numeri è un problema NP-difficile con diverse applicazioni in crittografia. L'attacco XSL richiede de facto un algoritmo efficiente per affrontare le equazioni polinomiali quadratiche.

Nel 1999, Kipnis e Shamir hanno dimostrato[5] che un particolare algoritmo a chiave pubblica, noto come schema Hidden Field Equations (HFE), poteva essere ridotto a un sistema con più equazioni quadratiche che incognite. Una tecnica per risolvere tali sistemi è la linearizzazione, che prevede la sostituzione di ogni termine quadratico con una variabile indipendente e la risoluzione del sistema lineare risultante mediante un algoritmo come l'eliminazione gaussiana. Per avere successo, la linearizzazione richiede un numero sufficiente di equazioni linearmente indipendenti (approssimativamente pari al numero di termini). Tuttavia, per la crittoanalisi di HFE le equazioni erano troppo poche, quindi Kipnis e Shamir proposero la ri-linearizzazione, una tecnica in cui dopo la linearizzazione vengono aggiunte altre equazioni non lineari e il sistema risultante viene risolto con una seconda applicazione della linearizzazione. La ri-linearizzazione si è dimostrata abbastanza generale da poter essere applicata ad altri schemi.

Nel 2000, un gruppo di ricerca guidato da Courtois ha proposto[6] un algoritmo migliorato per la risoluzione di equazioni polinomiali quadratiche noto come XL (eXtended Linearization), che aumenta il numero di equazioni moltiplicandole con tutti i monomi di un certo grado. Le stime di complessità hanno mostrato che l'attacco XL non avrebbe funzionato contro le equazioni derivate da cifrari a blocchi come AES[7]. Tuttavia, i sistemi di equazioni prodotti avevano una struttura particolare e l'algoritmo XSL è stato sviluppato come un perfezionamento di XL in grado di sfruttare questa struttura. In XSL, le equazioni sono moltiplicate solo per monomi accuratamente selezionati.

Complessità algebrica di XSL

[modifica | modifica wikitesto]

L'algoritmo scelto per sfruttare l'attacco XSL non influisce sulla sicurezza reale dei cifrari a blocchi, dato che il metodo ha un fattore di lavoro elevato per via dell'enorme tempo macchina richiesto per l'esecuzione. Ciò significa che questo attacco non riduce effettivamente lo sforzo di violare AES attraverso ricerca esaustiva. Ciononostante, l'attacco ha fatto sì che alcuni esperti esprimessero un maggiore disagio nei confronti della semplicità algebrica dell'attuale AES[8].

In sintesi, l'attacco XSL si basa sull'analisi degli interni di un cifrario e sulla derivazione di un sistema di equazioni quadratiche simultanee. Questi sistemi di equazioni sono tipicamente molto grandi nell'utilizzo dello standard AES, sfruttando ad esempio 8000 equazioni con 1600 variabili per l'AES a 128 bit. Sono noti diversi metodi per risolvere tali sistemi[9], sebbene questi possano risultare complessi nell'implementazione pratica[10]. Nell'attacco XSL l'applicazione di questi metodi risolutivi risulta tediosa con l'aumentare della lunghezza in bit della chiave di cifratura scelta, come riportato anche nell'Abstract della pubblicazione di Courtois e Pieprzyk[1]:

L'attacco XSL è molto potente, ma euristico ed è molto difficile valutarne la complessità. L'attacco XSL ha un parametro P, e in teoria dimostriamo che P dovrebbe essere una costante. L'attacco XSL sarebbe quindi polinomiale in Nr, con un'enorme costante che è doppiamente esponenziale rispetto alla dimensione della S-box.

La ricerca sull'efficienza di XL e dei suoi algoritmi derivati è tuttora in corso[11], sebbene altri credano non sia possibile risalire alla chiave di cifratura di AES attraverso metodi algebrici standard, ma solamente sfruttando altre vulnerabilità[12].

Note

[modifica | modifica wikitesto]
  1. ^ a b (EN) Nicolas Courtois e Josef Pieprzyk, Cryptanalysis of Block Ciphers with Overdefined Systems of Equations, in Cryptology ePrint Archive, 2002.
  2. ^ (EN) NESSIE Discussion Forum, su cosic.esat.kuleuven.ac.be (archiviato dall'url originale il 3 agosto 2004).
  3. ^ Advanced encryption standard (AES), National Institute of Standards and Technology, 2001-11, DOI:10.6028/nist.fips.197.
  4. ^ (EN) Commerce Secretary Announces New Standard for Global Information Security, in NIST, 4 dicembre 2001.
  5. ^ (EN) Aviad Kipnis e Adi Shamir, Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization, in Michael Wiener (a cura di), Advances in Cryptology — CRYPTO’ 99, Springer, 1999, pp. 19–30, DOI:10.1007/3-540-48405-1_2.
  6. ^ (EN) Nicolas Courtois, Alexander Klimov e Jacques Patarin, Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations, in Bart Preneel (a cura di), Advances in Cryptology — EUROCRYPT 2000, Springer, 2000, pp. 392–407, DOI:10.1007/3-540-45539-6_27.
  7. ^ (EN) Gregory V. Bard, 12.4, in Algebraic Cryptanalysis, Springer Science & Business Media, DOI:10.1007/978-0-387-88757-9.
  8. ^ (EN) Claus Diem, The XL-Algorithm and a Conjecture from Commutative Algebra, in Pil Joong Lee (a cura di), Advances in Cryptology - ASIACRYPT 2004, Springer, 2004, pp. 323–337, DOI:10.1007/978-3-540-30539-2_23.
  9. ^ (EN) Goce Jakimoski e Ljupčo Kocarev, Analysis of some recently proposed chaos-based encryption algorithms, in Physics Letters A, vol. 291, n. 6, 17 dicembre 2001, pp. 381–384, DOI:10.1016/S0375-9601(01)00771-X.
  10. ^ B. E. Mitchell, A Method for the Solution of Simultaneous Quadratic Equations of the Symmetric Type, in The American Mathematical Monthly, vol. 19, n. 5, 1º maggio 1912, pp. 94–96, DOI:10.1080/00029890.1912.11997679.
  11. ^ (EN) Bo-Yin Yang e Jiun-Ming Chen, Theoretical Analysis of XL over Small Fields, in Huaxiong Wang, Josef Pieprzyk, Vijay Varadharajan (a cura di), Information Security and Privacy, Springer, 2004, pp. 277–288, DOI:10.1007/978-3-540-27800-9_24.
  12. ^ Luminita Scripcariu, Felix Diaconu e Petre Daniel Mătăsaru, AES Vulnerabilities Study, in 2018 10th International Conference on Electronics, Computers and Artificial Intelligence (ECAI), 2018-06, pp. 1–4, DOI:10.1109/ECAI.2018.8678930.
  Portale Crittografia
  Portale Sicurezza informatica