Svelare i Segreti della Cifratura: Nuovi Limiti per la Diffusione dei Dati nelle Permutazioni n-bit!

Ciao a tutti, appassionati di enigmi digitali e fortezze informatiche! Oggi voglio portarvi con me in un viaggio affascinante nel cuore della crittografia, un mondo dove numeri e logica danzano per proteggere le nostre informazioni più preziose. Parleremo di un concetto che forse suona un po’ tecnico, il “numero di diramazione differenziale” (o *differential branch number* per gli amici anglofoni), ma che è assolutamente cruciale per capire quanto sia “brava” una permutazione a mescolare le carte in tavola, o meglio, i bit!

Ma cos’è esattamente questo “Numero di Diramazione Differenziale”?

Immaginate un cifrario a blocchi, uno di quegli algoritmi che trasformano i vostri messaggi in un guazzabuglio incomprensibile per occhi indiscreti. Uno dei principi fondamentali per un buon cifrario, come ci ha insegnato il grande Claude Shannon, è la diffusione. Vogliamo che una piccola modifica nell’input si sparpagli come un’onda d’urto, modificando tantissimi bit nell’output. Ecco, il numero di diramazione differenziale è una misura di questa capacità di diffusione, specificamente per le permutazioni, che sono funzioni che riordinano gli elementi.

Più alto è questo numero, più la permutazione è abile a spargere le differenze, e quindi più resistente diventa il nostro cifrario contro un tipo di attacco molto insidioso chiamato criptoanalisi differenziale. Pensatelo come il minimo numero di “S-box attive” (le S-box sono piccole tabelle di sostituzione, componenti fondamentali dei cifrari) quando introduciamo una differenza nell’input di un round di permutazione e osserviamo l’output. Un numero di diramazione alto significa che anche una singola differenza in input scatena una valanga di cambiamenti. Per questo, studiare i suoi limiti superiori è importantissimo: ci aiuta a capire fin dove possiamo spingerci nel progettare componenti di cifratura robusti, come le S-box o i livelli lineari, senza chiedere l’impossibile.

Il Legame con la Teoria dei Codici e i Limiti Precedenti

Una cosa super interessante è che, grazie alla teoria dei codici, possiamo tradurre il problema del numero di diramazione differenziale di una permutazione in un problema sulla distanza minima di un codice binario corrispondente. Questo ci apre un mondo di strumenti matematici! Esistono limiti famosi nella teoria dei codici, come il limite di Singleton o quello di Griesmer, che però sono pensati principalmente per i codici lineari. E qui casca l’asino, perché nel design dei cifrari moderni, specialmente quelli leggeri (pensati per dispositivi con poche risorse, come nell’IoT), si usano sempre più spesso permutazioni non lineari.

Un esempio celebre è il cifrario leggero PRESENT, che usa S-box piccole (4×4 bit) con un numero di diramazione differenziale di 3, e per lo strato lineare usa una semplice permutazione di bit. Questa accoppiata furba garantisce una buona diffusione con un basso costo implementativo. Quindi, la ricerca su permutazioni non lineari con un alto numero di diramazione è in pieno fermento!

Negli anni passati, sono stati proposti alcuni limiti superiori per il numero di diramazione differenziale di qualsiasi permutazione su ({mathbb{G}mathbb{F}(2)}^n) (cioè permutazioni di n-bit). Nel 2018, Sarkar e Syed hanno proposto un limite di circa (frac{2}{3}n) per (n ge 5). Poi, nel 2020, You e colleghi hanno fatto ancora meglio, portandolo a circa (frac{1}{2}n), che fino a poco fa era la stima più precisa. Ma la domanda sorge spontanea: possiamo fare di più? Possiamo “stringere la cinghia” ancora un po’ a questo limite? Beh, la risposta, come vedremo, è un sonoro sì!

La Nostra Caccia a Limiti Più Stretti

Nel nostro studio, abbiamo affrontato il problema analizzando l’esistenza di codici binari con una certa dimensione e distanza minima, usando delle disuguaglianze combinatorie. Questo ci ha permesso di stimare il numero di diramazione differenziale delle permutazioni associate a questi codici. E il risultato? Abbiamo trovato due nuovi limiti superiori, uno dei quali è, al momento, il più stretto conosciuto!

Per darvi un’idea, per una permutazione (phi) su ({mathbb{G}mathbb{F}(2)}^n), il suo numero di diramazione (mathcal{B}(phi)) è definito come:
[ mathcal{B}(phi) = min_{x ne 0} { textbf{wt}(x) + textbf{wt}(phi(x) oplus phi(0)) } ]
dove (textbf{wt}(y)) è il peso di Hamming di (y), cioè il numero di ‘1’ nella sua rappresentazione binaria. Se una permutazione ha un numero di diramazione (mathcal{B}), allora definisce un codice ((2n, 2^n, mathcal{B})), cioè un codice di lunghezza (2n), con (2^n) parole di codice e distanza minima (mathcal{B}).

Sfruttando il limite di Hamming per i codici (che non si limita ai codici lineari) e alcune proprietà della funzione entropia binaria (H(lambda)), siamo riusciti a derivare condizioni più precise. In pratica, se una certa condizione che coinvolge (n) e un parametro (lambda) (legato alla frazione di errori che un codice può correggere) è soddisfatta, allora possiamo stabilire un nuovo limite superiore.

I Nuovi Campioni: Due Limiti Freschi Freschi

Senza entrare troppo nei dettagli matematici della derivazione (che coinvolge la funzione (U(lambda, m) = frac{2^{mH(lambda )}}{sqrt{8mlambda (1-lambda )}}) e l’analisi di come cresce rispetto a (n)), vi presento i nostri risultati principali:

• Teorema 1: Se (n ge 35), allora per qualsiasi permutazione (phi) su ({mathbb{G}mathbb{F}(2)}^n), abbiamo (mathcal{B}(phi) < frac{n}{2} + 1). Questo si ottiene ponendo (lambda = frac{1}{8}).
• Teorema 2: Se (n ge 57), allora per qualsiasi permutazione (phi) su ({mathbb{G}mathbb{F}(2)}^n), abbiamo (mathcal{B}(phi) < frac{12n}{25} + 1) (che è (0.48n + 1)). Questo si ottiene con (lambda = frac{3}{25}).

Confrontando questi risultati, vediamo che il limite di Sarkar era a livello (frac{2}{3}n approx 0.667n). Il limite di You e il nostro Teorema 1 sono entrambi a livello (frac{1}{2}n = 0.5n), ma il nostro Teorema 1 mantiene un leggero vantaggio in certe condizioni. Il vero campione, però, è il Teorema 2, che porta il coefficiente lineare a (frac{12}{25} = 0.48). Un bel passo avanti! Certo, c’è un piccolo “costo”: questo limite più stretto richiede che (n) sia almeno 57, quindi ha un campo di applicazione un po’ più ristretto rispetto agli altri.

È importante notare che per valori piccoli di (n) (come quelli di una singola S-box), il nostro schema non è direttamente applicabile. Tuttavia, se consideriamo uno strato non lineare composto da molte S-box come un’unica grande permutazione non lineare, allora i nostri limiti più stretti possono dare una valutazione più accurata delle sue performance diffusive. Per esempio, per un cifrario tipo PRESENT con blocchi da 64 bit, il Teorema 2 ci dice che il numero di diramazione differenziale di una permutazione a 64 bit è al massimo 31 ((0.48 times 64 + 1 approx 31.72), quindi intero 31). Questo ha implicazioni dirette sulla stima della sicurezza contro la crittoanalisi differenziale.

Verso l’Infinito e Oltre: Il Limite Asintotico

Ma non ci siamo fermati qui! Ci siamo chiesti: cosa succede quando (n) diventa enormemente grande? Esiste un limite “definitivo” che possiamo raggiungere con questo approccio? Ebbene sì, abbiamo studiato il comportamento asintotico del limite superiore.

Abbiamo dimostrato che per ogni (lambda) in un certo intervallo (specificamente, (lambda in (H^{-1}(frac{1}{2}), frac{1}{2}]), dove (H^{-1}) è l’inversa della funzione entropia binaria), quando (n) è sufficientemente grande (cioè (n ge N_{lambda}), dove (N_{lambda}) è un valore che dipende da (lambda)), allora (4lambda n) è un limite superiore per il numero di diramazione differenziale.

Questo ci porta a una conclusione davvero affascinante: il numero di diramazione differenziale di qualsiasi permutazione su ({mathbb{G}mathbb{F}(2)}^n) ha un limite superiore asintotico di (4H^{-1}(frac{1}{2})n). Calcolando il valore di (H^{-1}(frac{1}{2})) (che è circa 0.11003), otteniamo un limite asintotico di circa 0.44012n. Questa è la ciliegina sulla torta: è il limite superiore più accurato che possiamo dimostrare con lo schema presentato nel nostro lavoro.

Cosa Significa Tutto Questo?

In sintesi, abbiamo fatto un bel passo avanti nella comprensione dei limiti teorici della capacità di diffusione delle permutazioni n-bit, siano esse lineari o non lineari. I nostri due nuovi limiti concreti sono più stringenti di quelli esistenti, e il limite asintotico ci dà una prospettiva a lungo raggio.
Questo tipo di ricerca è fondamentale perché fornisce ai progettisti di cifrari stime più precise. Sapere qual è il massimo numero di diramazione differenziale teoricamente ottenibile per una data dimensione (n) aiuta a:

• Valutare quanto “buona” sia una particolare costruzione.
• Evitare di cercare l’impossibile, cioè permutazioni con proprietà diffusive che superano i limiti teorici.
• Guidare la progettazione di nuovi componenti crittografici più efficienti e sicuri.

Certo, il nostro schema si basa su condizioni sufficienti perché un valore sia un limite superiore. Una sfida aperta e interessante per il futuro sarebbe quella di migliorare ulteriormente questi limiti analizzando condizioni necessarie e sufficienti. Ma per ora, siamo molto contenti di aver aggiunto un altro tassello a questo complesso e cruciale puzzle della crittografia!

Spero che questo piccolo tuffo nel mondo dei limiti crittografici vi sia piaciuto. È un campo in continua evoluzione, dove la matematica elegante si sposa con la necessità pratica di sicurezza. Alla prossima avventura nel mondo dei segreti digitali!

Fonte: Springer