💻 computer science

Analyzing Linear Layers in Related-Differential Cryptanalysis

Questo articolo indaga sistematicamente l'esistenza di strutture differenziali correlate nei livelli lineari di cifrari simili ad AES, dimostrando che tali vulnerabilità sono inevitabili per tutte le matrici non-MDS, per tutte le matrici MDS simmetriche di ordine dispari e per la maggior parte delle matrici circolanti, fornendo al contempo una caratterizzazione completa per le matrici MDS $3 \times 3$ su $\mathbb{F}_{2^m}$ .

Autori originali: Yogesh Kumar, Akshay Ankush Yadav, Susanta Samanta

Pubblicato 2026-05-28

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Yogesh Kumar, Akshay Ankush Yadav, Susanta Samanta

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di costruire una cassaforte ad alta sicurezza (un blocco digitale) per proteggere i tuoi segreti. Per assicurarti che nessuno possa violarla, utilizzi una speciale macchina di miscelazione chiamata Livello Lineare. Questa macchina prende i tuoi dati, li mescola e li distribuisce in modo che un minuscolo cambiamento nell'input generi un enorme e caotico cambiamento nell'output. Questo fenomeno è chiamato "diffusione".

Per decenni, i crittografi hanno utilizzato un tipo specifico di macchina di miscelazione chiamata Matrice MDS perché rappresenta lo "standard aureo" per una diffusione perfetta. Pensavano: "Se usiamo una matrice MDS, siamo al sicuro".

Tuttavia, questo articolo rivela un difetto nascosto in questo ragionamento. Si scopre che anche se la tua macchina di miscelazione è lo "standard aureo" (MDS), potrebbe comunque possedere una debolezza segreta chiamata Differenziali Correlati.

Ecco la spiegazione di ciò che gli autori hanno scoperto, utilizzando semplici analogie:

1. Lo "Standard Aureo" non è sufficiente

Considera la proprietà MDS come una garanzia che la tua macchina di miscelazione distribuisca una goccia d'inchiostro su un'intera pagina di carta.

La Vecchia Credenza: Se la macchina distribuisce l'inchiostro perfettamente (MDS), è sicura.
La Nuova Scoperta: Gli autori hanno dimostrato che se una macchina non distribuisce l'inchiostro perfettamente (Non-MDS), è garantito che abbia una debolezza segreta.
L'Analogia: Immagina di cercare di nascondere un messaggio segreto in una stanza. Se la stanza è piccola e ingombra (Non-MDS), un ladro può facilmente trovare un modello per infiltrarsi. Gli autori hanno dimostrato che solo una stanza perfettamente spaziosa e ordinata (MDS) ha una possibilità di essere sicura. Ma avere semplicemente la stanza spaziosa non garantisce la sicurezza; conta anche la forma della stanza.

2. La "Trappola della Simmetria"

Molte macchine di miscelazione sono costruite per essere Simmetriche, il che significa che appaiono identiche se le capovolgi (come una farfalla). Questo è popolare perché è facile da realizzare.

La Scoperta: Gli autori hanno scoperto che se una macchina simmetrica ha un numero dispari di parti (come 3x3 o 5x5), è sempre vulnerabile.
L'Analogia: Immagina una pista da ballo con un numero dispari di ballerini. Non importa come tentino di accoppiarsi, un ballerino rimane sempre in piedi al centro, creando un modello prevedibile. Gli autori hanno dimostrato che per qualsiasi macchina simmetrica di dimensioni dispari, esiste sempre un modello "avanzo" che un hacker può sfruttare. Non importa quanto bene sia costruita; il numero dispari la rende intrinsecamente debole contro questo specifico tipo di attacco.

3. Il Problema del "Modello Circolare"

Un altro design popolare è la Matrice Circolante. Immagina un nastro trasportatore in cui il modello degli ingranaggi si ripete in cerchio. Questo è efficiente e veloce.

La Scoperta: Gli autori hanno esaminato queste macchine circolari e hanno trovato una regola basata sulle loro dimensioni (chiamata $n$ $n$ ).
- Se la dimensione del cerchio è un multiplo di 3 (come 3, 6, 9) o un multiplo di 4 (come 4, 8, 12), è vulnerabile.
- In effetti, hanno dimostrato che a meno che la dimensione non sia un numero molto specifico (nello specifico, numeri che non sono 2 o 10 lontani da un multiplo di 12), la macchina è vulnerabile.
L'Analogia: Pensa a un quadrante di orologio. Se cerchi di camminare intorno all'orologio a passi di 3 o 4, alla fine colpirai gli stessi punti ripetutamente in modo prevedibile. Gli autori hanno mostrato che per la maggior parte dei design circolari, un hacker può trovare una "scorciatoia" attraverso gli ingranaggi che bypassa la sicurezza.

4. La "Ricetta Perfetta" per le Macchine 3x3

Infine, gli autori si sono concentrati sulla dimensione più piccola e comune: le Matrici 3x3.

Il Problema: I tentativi precedenti di trovare una macchina 3x3 "sicura" erano incompleti. Fornivano una ricetta che lasciava fuori alcuni ingredienti.
La Soluzione: Gli autori hanno scritto una ricetta completa composta da 15 regole specifiche (equazioni matematiche).
L'Analogia: Immagina di cuocere una torta. I precedenti chef dicevano: "Non usare il sale". Gli autori hanno detto: "In realtà, devi evitare sale, zucchero, farina, uova, latte e altri 11 ingredienti specifici in combinazioni esatte". Hanno fornito un elenco di controllo di 15 cose da evitare. Se la tua macchina 3x3 segue tutte le 15 regole, è sicura. Se ne viola anche solo una, è vulnerabile.
Il Risultato: Hanno contato quante macchine 3x3 esistono e quante sono effettivamente sicure. Hanno scoperto che quelle "sicure" sono molto più rare di quanto pensassimo.

Riepilogo del Messaggio Chiave

Questo articolo è come un ispettore di sicurezza per i blocchi digitali. Ci hanno detto:

Le macchine Non-MDS sono decisamente insicure. (Devi usare MDS).
Le macchine Simmetriche di dimensioni dispari sono decisamente insicure. (Non usare numeri dispari se vuoi la simmetria).
La maggior parte delle macchine Circolari è insicura. (A meno che la dimensione non sia molto specifica).
Per le macchine 3x3, ecco l'esatto elenco di controllo per assicurarti di non costruire un blocco debole.

Gli autori non hanno inventato un nuovo blocco; ci hanno semplicemente fornito un modo migliore per verificare se i blocchi che stiamo già costruendo hanno crepe nascoste.

Riepilogo Tecnico: Analisi dei Livelli Lineari nella Crittanalisi Differenziale Correlata

Enunciato del Problema
Nei cifrari a blocchi basati su SPN (ad esempio AES), il livello di diffusione lineare è tipicamente implementato utilizzando matrici MDS (Maximum Distance Separable) per garantire numeri di ramo ottimali e resistenza contro la crittanalisi differenziale e lineare classica. Tuttavia, recenti lavori di Daemen e Rijmen (2009) e di Bardeh e Rijmen (2022) hanno rivelato che le matrici MDS possono ancora esibire strutture "differenziali correlate". Queste strutture permettono la costruzione di caratteristiche differenziali correlate che possono essere sfruttate negli attacchi, come l'attacco di recupero della chiave su 7 round su AES-128. Sebbene studi precedenti abbiano identificato differenze correlate in istanze specifiche (ad esempio, matrici circolanti 4×4, matrici involutorie 3×3), una comprensione sistematica di quali strutture di livello lineare evitino o ammettano intrinsecamente queste differenze rimane incompleta. Questo articolo investiga le condizioni in cui i livelli lineari su campi finiti evitano le differenze correlate, mirando a identificare classi di matrici intrinsecamente resistenti a questo specifico vettore crittanalitico.

Metodologia
Gli autori adottano un approccio algebrico teorico su campi finiti di caratteristica 2 ( $\mathbb{F}_{2^m}$ ). La metodologia comprende:

Definizione delle Differenze Correlate: Utilizzando le definizioni di Daemen e Rijmen, due differenze $(u, Mu) $e$ (v, Mv)$ sono "correlate" se la coppia di input $(u, v)$ e la coppia di output $(Mu, Mv)$ soddisfano la condizione $x_i \cdot y_i \cdot (x_i \oplus y_i) = 0$ per tutte le coordinate.
Analisi Strutturale: Investigazione della relazione tra le proprietà della matrice (stato MDS, simmetria, struttura circolante) e l'esistenza di coppie di differenze correlate non banali.
Decomposizione Polinomiale: Per le matrici circolanti, gli autori mappano le operazioni della matrice sulla moltiplicazione polinomiale nell'anello quoziente $\mathbb{F}_{2^m}[X]/\langle X^n - 1 \rangle$ . Decompongono il polinomio di trasformazione basandosi sull'aritmetica modulare degli esponenti (modulo 2, 3 e 4) per costruire coppie specifiche di differenze di input che producono differenze di output correlate.
Enumerazione Caso per Caso: Per il caso $3 \times 3$ , gli autori utilizzano la decomposizione di qualsiasi matrice MDS in una forma rappresentativa $M = D_1 M_1 D_2$ (dove $D_i$ sono diagonali e $M_1$ è un rappresentante specifico). Analizzano sistematicamente tutti i possibili pattern di peso di Hamming delle triple di differenze di input $(u, v, u \oplus v)$ per derivare condizioni algebriche necessarie e sufficienti per l'assenza di differenze correlate.

Contributi e Risultati Chiave

Necessità della Proprietà MDS:
L'articolo dimostra che la proprietà MDS è una condizione necessaria per evitare le differenze correlate. Nello specifico, il Teorema 2 dimostra che ogni matrice non-MDS ammette almeno una coppia non banale di differenze correlate. Questo restringe lo spazio di ricerca per i livelli lineari resistenti strettamente alla classe delle matrici MDS.
Vulnerabilità delle Matrici Simmetriche:
Gli autori stabiliscono che la simmetria in dimensioni dispari è una vulnerabilità intrinseca. Il Teorema 4 dimostra che ogni matrice MDS simmetrica di ordine dispari ammette differenze correlate. Questo risultato esclude ampie famiglie di costruzioni, incluse le matrici MDS basate su Cauchy di Tipo 2 e le matrici circolanti a sinistra di ordine dispari (Corollari 2 e 3), poiché sono intrinsecamente simmetriche e quindi vulnerabili.
Vulnerabilità delle Matrici Circolanti:
L'articolo fornisce una caratterizzazione completa per le matrici circolanti. Analizzando le proprietà modulari dell'ordine della matrice $n$ , gli autori dimostrano nel Teorema 5 che una matrice MDS circolante di ordine $n$ ammette differenze correlate ogniqualvolta $n \not\equiv \pm 2 \pmod{12}$ . Questo generalizza i risultati precedenti per i casi $3 \times 3$ e $4 \times 4$ , identificando una vasta classe di ordini vulnerabili.
Caratterizzazione Completa delle Matrici $3 \times 3$ :
Riprendendo il caso $3 \times 3$ , gli autori derivano una caratterizzazione algebrica completa. Il Teorema 7 fornisce un insieme esplicito di 15 vincoli polinomiali necessari e sufficienti sui parametri di una matrice MDS rappresentativa $3 \times 3$ . Se una qualsiasi di queste 15 condizioni è soddisfatta, la matrice ammette differenze correlate; se nessuna è soddisfatta, la matrice è resistente.
- L'articolo nota che le caratterizzazioni precedenti (ad esempio, di Otal et al.) erano incomplete.
- Utilizzando questa caratterizzazione, gli autori calcolano il numero esatto di matrici MDS $3 \times 3$ su vari campi finiti ( $\mathbb{F}_{2^m}$ ) che non possiedono differenze correlate, dimostrando che l'insieme delle matrici resistenti è un sottoinsieme stretto di tutte le matrici MDS (Tabella I).

Significato e Affermazioni
L'articolo afferma di fornire un'indagine sistematica sui prerequisiti strutturali per resistere alla crittanalisi differenziale correlata. Il suo significato primario risiede in:

Stabilire i Limiti: Dimostrare che la proprietà MDS da sola è insufficiente per la resistenza e che specifiche proprietà strutturali (simmetria di ordine dispari, specifici ordini circolanti) garantiscono la vulnerabilità.
Raffinare i Criteri di Progettazione: Offrire un insieme concreto e verificabile di 15 vincoli algebrici per le matrici $3 \times 3$ , consentendo ai progettisti di verificare esaustivamente o costruire matrici resistenti in questa dimensione.
Guidare la Costruzione Futura: Identificando che le matrici non-MDS sono intrinsecamente vulnerabili e che molte comuni costruzioni simmetriche falliscono, il lavoro indirizza la ricerca futura verso la costruzione di matrici MDS che siano sia asimmetriche (o simmetriche di ordine pari) e soddisfino i vincoli algebrici specifici derivati per la resistenza.

Gli autori concludono che, sebbene il caso $3 \times 3$ sia completamente caratterizzato, estendere questi risultati alle matrici $4 \times 4$ e costruire matrici MDS leggere ed efficienti senza differenze correlate rimangono sfide aperte. Notano inoltre che i casi irrisolti per le matrici circolanti (dove $n \equiv \pm 2 \pmod{12}$ ) presentano una congettura per una futura dimostrazione.