# Attacco XSL

In crittografia, l'attacco eXtended Sparse Linearization (XSL) è un metodo teorico di crittoanalisi per i cifrari a blocchi, pubblicato 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 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, ed è già ampiamente utilizzato in ambito commerciale e governativo 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

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 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 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. 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

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.
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, sebbene questi possano risultare complessi nell'implementazione pratica. 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:
   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, sebbene altri credano non sia possibile risalire alla chiave di cifratura di AES attraverso metodi algebrici standard, ma solamente sfruttando altre vulnerabilità.