Crittoanalisi Commutativa: Decifrare i Segreti dei Cifrari Oltre il Solito Differenziale!

Ciao a tutti, appassionati di crittografia e segreti digitali! Oggi voglio portarvi con me in un viaggio affascinante nel mondo della crittoanalisi, quella branca della crittografia che si occupa di “rompere” i codici. Non per scopi loschi, sia chiaro, ma per capire meglio come funzionano e, di conseguenza, come costruirne di più robusti. Parleremo di un approccio che sta guadagnando attenzione: la crittoanalisi commutativa. Sembra un nome altisonante, ma cercherò di spiegarvelo in modo semplice e, spero, avvincente!

Forse avete già sentito parlare della crittoanalisi differenziale. È una delle tecniche più potenti e studiate per attaccare i cifrari simmetrici (quelli che usano la stessa chiave per cifrare e decifrare, come il celebre AES). In parole povere, si basa sull’analizzare come le differenze tra due input si propagano attraverso il cifrario per influenzare le differenze negli output. Se si trova una coppia di differenze (input-output) che appare con una probabilità più alta del previsto, bingo! Si potrebbe avere una pista per scoprire la chiave.

Un Passo Avanti Rispetto alla Crittoanalisi Differenziale

Ecco, la crittoanalisi commutativa è un po’ come la sorella maggiore e più versatile della crittoanalisi differenziale. Immaginate un cifrario come una serie di trasformazioni matematiche, che indichiamo con E_k (dove k è la chiave segreta). La crittoanalisi commutativa cerca di sfruttare l’esistenza di due “scorciatoie”, due permutazioni (funzioni che rimescolano gli elementi) A e B, tali che applicare A prima di cifrare un messaggio x dia lo stesso risultato (o quasi) che applicare B dopo aver cifrato x. Matematicamente, si cerca questa relazione: E_k(A(x)) = B(E_k(x)).

Questa relazione non deve valere sempre, ma con una probabilità “sospettosamente” alta, e magari solo per un certo insieme di chiavi, dette chiavi deboli. La cosa interessante è che la crittoanalisi differenziale classica può essere vista come un caso particolare di quella commutativa. Se prendiamo A(x) = x + α (una traslazione, cioè una somma) e B(y) = y + β, la formula diventa E_k(x + α) = E_k(x) + β, che è proprio il cuore della crittoanalisi differenziale!

Ma la crittoanalisi commutativa non si ferma qui. Può inglobare anche altri tipi di attacchi, come quelli rotazionali (dove si sfruttano rotazioni di bit) o quelli rotazionali-differenziali. Persino i cosiddetti c-differenziali, una generalizzazione dei differenziali classici, rientrano in questo schema più ampio. Insomma, è un framework che ci permette di guardare agli attacchi crittografici da una prospettiva più unificata.

Il Cuore della Questione: Distinguisher Commutativi e Chiavi Deboli

Per capire se un cifrario è vulnerabile a un attacco commutativo, si usa un “distinguisher”. Immaginate di avere una scatola nera: potrebbe contenere il vero cifrario con una chiave casuale, oppure una permutazione scelta a caso tra tutte quelle possibili. Un distinguisher è un algoritmo che cerca di indovinare quale delle due opzioni è vera, facendo delle “domande” (query) alla scatola nera.

Un distinguisher commutativo, date le nostre funzioni A e B, sceglie un input x a caso, calcola A(x), e chiede alla scatola nera di cifrare sia x che A(x). Poi verifica se l’output di A(x) è uguale a B applicato all’output di x. Se questa uguaglianza si verifica più spesso con il cifrario reale che con una permutazione casuale, allora il distinguisher ha “vinto” e ha trovato una debolezza.

Un punto cruciale, come accennavo, è il concetto di chiavi deboli. Spesso, queste proprietà commutative non valgono per tutte le chiavi, ma solo per un sottoinsieme significativo. Se un cifrario è sicuro per la maggior parte delle chiavi ma vulnerabile per un gruppo specifico, quelle sono chiavi deboli. La ricerca ha mostrato che gli attacchi commutativi che vanno oltre la semplice crittoanalisi differenziale (cioè, quando A e B non sono semplici traslazioni) tendono a funzionare proprio in questo scenario di chiavi deboli. Questo è particolarmente vero se il cifrario usa delle “whitening keys” indipendenti all’inizio e alla fine (chiavi aggiunte direttamente al testo in chiaro e al testo cifrato), una pratica comune per rafforzare i cifrari.

In particolare, si è visto che i c-differenziali con c diverso da 1 (dove c è una costante moltiplicativa usata nella definizione della differenza) hanno il potenziale d’attacco più basso in questo framework generale, soprattutto in presenza di chiavi di “whitening” indipendenti. Sembra quasi che, per distinguere un cifrario da una permutazione casuale usando questi strumenti, l’attacco debba necessariamente concentrarsi su chiavi specifiche.

Pensate a un cifrario iterato, costruito ripetendo più volte una stessa funzione di round. La crittoanalisi commutativa permette di estendere le formule che descrivono come le probabilità si accumulano lungo questi “trail” (percorsi) di round. Se le chiavi di round sono indipendenti, si scopre che la sicurezza contro attacchi commutativi generici (in media su tutte le chiavi) è sostanzialmente la stessa della sicurezza contro attacchi differenziali. Questo ci dice che, per trovare un vantaggio reale con un attacco commutativo più generale, dobbiamo per forza guardare al modello a chiave fissa o a chiave debole.

S-Box Sotto la Lente: Quando la Commutatività Diventa un Problema

Le S-box (Substitution boxes) sono componenti fondamentali di molti cifrari moderni, inclusi AES. Sono piccole tabelle di sostituzione non lineari che introducono confusione nel processo di cifratura, rendendo difficile risalire alla chiave. La loro robustezza alla crittoanalisi differenziale è misurata dalla loro “uniformità differenziale” (Δ_S): più basso è questo valore, meglio è (per le S-box su campi binari, il valore ottimale è 2, e si parla di funzioni APN – Almost Perfect Nonlinear).

La crittoanalisi commutativa getta nuova luce anche sulle S-box. Se una S-box S possiede una proprietà commutativa “non banale” con permutazioni affini A e B (cioè S(A(x)) = B(S(x)) per tutti gli x), e questa proprietà permette l’esistenza di molte chiavi deboli in un attacco basato su trail, allora l’uniformità differenziale Δ_S di quella S-box tende ad essere alta. In altre parole, una S-box “troppo” commutativa in questo senso specifico potrebbe non essere molto resistente agli attacchi differenziali classici!

Questo è un risultato importante perché lega la struttura algebrica interna della S-box (la sua commutatività con certe funzioni) alla sua principale misura di sicurezza crittografica. Ad esempio, se una S-box ha una auto-equivalenza affine non banale (un caso particolare della nostra relazione commutativa), e vogliamo che ci siano molte chiavi deboli sfruttabili, allora la sua uniformità differenziale non può essere troppo bassa. Ci sono stati studi che hanno mostrato come, per S-box APN (quindi con ottima uniformità differenziale), le possibili auto-equivalenze lineari siano molto limitate. I nostri risultati qui aiutano a restringere ulteriormente queste possibilità.

Un esempio interessante si ha con le costruzioni di Feistel a 2 round. Si può dimostrare che, scegliendo opportunamente le funzioni interne f1 e f2, si può costruire una permutazione S che ha una proprietà commutativa perfetta (cioè con probabilità 1) con una A che è una semplice traslazione e una B affine, pur mantenendo un’uniformità differenziale Δ_S inferiore al massimo possibile. Questo mostra che i legami sono sottili e che esistono S-box che soddisfano queste condizioni.

Creare il Caos Controllato: Generare Permutazioni Affini A e B

Una domanda sorge spontanea: come troviamo queste permutazioni A e B “giuste”? Se vogliamo che la relazione S(A(x)) = B(S(x)) valga per una S-box S, e vogliamo che A e B siano permutazioni affini, una strategia è cercare A e B che abbiano lo stesso “tipo di ciclo”. Cosa significa? Ogni permutazione scompone l’insieme su cui agisce in cicli disgiunti. Il “tipo di ciclo” è una descrizione di quanti cicli ci sono di ogni lunghezza. Se A e B hanno lo stesso tipo di ciclo, c’è una speranza di poter costruire una S che le “colleghi”.

Questo problema di generare permutazioni (lineari o affini) con lo stesso tipo di ciclo è un classico, studiato fin dagli anni ’50 e ’60. La teoria si basa sull’analisi dei polinomi caratteristici e minimi delle parti lineari di A e B, e sulla loro scomposizione in forma normale di Weierstraß. Non voglio annoiarvi con i dettagli matematici, ma l’idea è che se i “mattoni” irriducibili di questi polinomi hanno lo stesso ordine (un concetto legato alla lunghezza dei cicli che generano), allora si possono costruire A e B con la stessa struttura ciclica. Una volta trovate A e B adatte, si può, in linea di principio, calcolare tutte le S-box S che soddisfano la relazione.

Si analizza anche cosa succede se l’ordine di A (e quindi di B, se S è biiettiva) non è una potenza del primo p che definisce il campo finito su cui lavoriamo (spesso p=2 per la crittografia). In questi casi, si può dimostrare che la S-box è equivalente (tramite trasformazioni affini) a una S-box che ha una auto-equivalenza lineare, dove le matrici lineari coinvolte hanno una particolare forma a blocchi diagonali. Questo aiuta a classificare e comprendere meglio queste strutture.

Oltre l’Addizione: Crittoanalisi con Operazioni di Gruppo Alternative

L’ultima parte del nostro viaggio ci porta in territori ancora più astratti, ma con implicazioni pratiche. La crittoanalisi differenziale classica usa l’addizione (o lo XOR nel caso binario) per definire le differenze. Ma cosa succede se usiamo un’operazione di gruppo diversa, che chiameremo ♢ (diamond)? Si parla allora di ♢-differenziali.

Sorprendentemente, questo approccio è strettamente legato alla crittoanalisi commutativa e alla crittoanalisi differenziale dei cosiddetti cifrari coniugati. Se abbiamo una funzione F e una biiezione H, il cifrario coniugato è F^H = H ○ F ○ H^-1. Studiare le proprietà differenziali di F^H (usando l’addizione standard) è equivalente a studiare proprietà commutative di F originale, dove le funzioni A e B appartengono a un gruppo specifico derivato da H e dal gruppo delle traslazioni.

Inoltre, si può dimostrare che studiare i ♢-differenziali di F è equivalente a studiare i differenziali standard del suo coniugato F^H (per una H opportuna che lega l’operazione ♢ all’addizione standard). Quindi, queste tre prospettive – commutativa, differenziale di coniugati, e ♢-differenziale – sono facce della stessa medaglia! Questo è potente perché ci permette di usare gli strumenti e le intuizioni di un approccio per fare progressi negli altri.

Ad esempio, il concetto di “spazio di chiavi deboli” W^♢ introdotto per i ♢-differenziali (chiavi k per cui l’aggiunta della chiave T_k si “comporta bene” rispetto all’operazione ♢) può essere reinterpretato come l’insieme delle “strutture lineari” della funzione H che fa da ponte. Le strutture lineari sono un concetto ben noto in crittografia e questo ci dà nuovi strumenti per analizzare W^♢.

Per illustrare questi legami, sono stati analizzati alcuni cifrari, inclusa una versione “coniugata” del cifrario Midori e alcuni cifrari giocattolo proposti in letteratura per dimostrare l’efficacia dei ♢-differenziali. In ogni caso, si vede come una traccia ♢-differenziale possa essere vista come una traccia commutativa o una traccia differenziale standard su un cifrario coniugato. Ad esempio, per Midori coniugato, una certa transizione differenziale con probabilità 1 nel dominio coniugato corrisponde a una relazione commutativa con probabilità 1 nel dominio originale, o a una transizione ♢-differenziale con probabilità 1 per un’opportuna operazione ♢.

In conclusione, la crittoanalisi commutativa ci offre una lente più ampia e potente per esaminare le debolezze dei cifrari simmetrici. Generalizzando la crittoanalisi differenziale e collegandosi ad altri approcci apparentemente distinti, apre nuove strade per la ricerca e, speriamo, per la progettazione di sistemi crittografici sempre più sicuri. È un campo in continua evoluzione, pieno di matematica elegante e sfide stimolanti. Spero di avervi incuriosito almeno un po’!

Fonte: Springer