Come può la cirpanalisi lineare rompere un crittosistema DES?

/ / Pubblicato in Cybersecurity, Fondamenti di crittografia classica EITC/IS/CCF, Crittografia con cifratura a blocchi DES, Data Encryption Standard (DES) - Pianificazione e decrittografia delle chiavi

La crittoanalisi lineare è un potente metodo di attacco crittoanalitico che applica approssimazioni lineari all'azione di un algoritmo crittografico. È particolarmente efficace contro i codici a blocchi come il Data Encryption Standard (DES). Per comprendere come la crittoanalisi lineare possa rompere un crittosistema DES, è essenziale considerare sia i meccanismi del DES che i principi della crittoanalisi lineare.

1. Panoramica del DES:

Il Data Encryption Standard (DES) è un algoritmo a chiave simmetrica per la crittografia dei dati digitali. Funziona su blocchi di dati a 64 bit e utilizza una chiave a 56 bit. Il DES si basa su una struttura Feistel, che divide il blocco di input in due metà e le elabora attraverso più cicli di permutazione e sostituzione. Ogni round prevede i seguenti passaggi:
– Espansione: la metà destra del blocco viene espansa da 32 bit a 48 bit.
– Key Mixing: la metà destra espansa viene sottoposta a XOR con una chiave rotonda derivata dalla chiave principale.
– Sostituzione: il risultato viene diviso in otto segmenti da 6 bit, ciascuno dei quali viene fatto passare attraverso una S-box corrispondente, producendo un output da 4 bit.
– Permutazione: l'uscita a 32 bit delle S-box viene permutata secondo una tabella predefinita.

Le metà sinistra e destra vengono quindi scambiate e il processo si ripete per 16 round. La permutazione finale produce l'output crittografato.

2. Principi di crittoanalisi lineare:

La crittoanalisi lineare, sviluppata da Mitsuru Matsui all'inizio degli anni '1990, cerca di sfruttare le relazioni lineari tra testo in chiaro, testo cifrato e bit chiave. L'idea centrale è trovare approssimazioni lineari che valgano con una certa probabilità per i componenti non lineari del codice, come le S-box in DES. I passaggi coinvolti nella crittoanalisi lineare sono i seguenti:
– Identificare approssimazioni lineari: determinare equazioni lineari che approssimano il comportamento delle S-box. Queste approssimazioni sono della forma P[i] \opiù C[j] \opiù K[k] = 0Durante la serata, P è la parte del testo in chiaro, C è il bit del testo cifrato e K è la chiave.
– Calcola bias: misura la probabilità che valga l’approssimazione lineare. Il bias è la deviazione da 0.5 (la probabilità che un'ipotesi casuale sia corretta).
– Raccogli dati: crittografa un gran numero di testi in chiaro per raccogliere dati sufficienti per l'analisi statistica.
– Analizzare i dati: utilizzare i dati raccolti per identificare gli aspetti chiave più probabili in base ai bias osservati.

3. Applicazione della crittoanalisi lineare al DES:

L'applicazione della crittoanalisi lineare al DES prevede diverse fasi. Analizziamo il processo:

3.1. Identificazione delle approssimazioni lineari:

Il primo passo è identificare le approssimazioni lineari per le S-box utilizzate nel DES. Ciascuna S-box nel DES ha 6 bit di ingresso e 4 bit di uscita. L'obiettivo è trovare equazioni lineari che approssimino i risultati della S-box con una certa distorsione. Ad esempio, considera una S-box con bit di input x_1, x_2, x_3, x_4, x_5, x_6 e bit di uscita y_1, y_2, y_3, y_4. Un'approssimazione lineare potrebbe essere della forma:

    \[ x_1 \opiù x_2 \opiù y_3 = 0 \]

Questa equazione indica lo XOR dei bit di ingresso x_1 and x_2 e il bit di uscita y_3 è uguale a 0 con una certa probabilità.

3.2. Calcolo della distorsione:

Una volta identificate le approssimazioni lineari, il passaggio successivo consiste nel calcolare la distorsione per ciascuna approssimazione. Il bias è la differenza tra la probabilità che l'approssimazione sia valida e 0.5. Ad esempio, se l'approssimazione x_1 \opiù x_2 \opiù y_3 = 0 vale con una probabilità di 0.75, il bias è:

    \[ \epsilon = 0.75 - 0.5 = 0.25 \]

3.3. Raccolta dei dati:

Per eseguire la crittoanalisi lineare su DES, sono necessarie un gran numero di coppie di testo in chiaro-testo cifrato. Il numero di coppie necessarie dipende dalla distorsione dell'approssimazione lineare. Generalmente, maggiore è il numero di coppie raccolte, maggiore è la precisione dell'analisi. Per DES potrebbero essere necessarie diverse migliaia o addirittura milioni di coppie.

3.4. Analisi dei dati:

Con i dati raccolti, il passo successivo è analizzare le coppie testo in chiaro-testo cifrato per determinare i bit chiave più probabili. Ciò comporta i seguenti passaggi secondari:
– Per ciascuna coppia testo in chiaro-testo cifrato, calcola i valori delle approssimazioni lineari.
– Contare il numero di volte in cui vale ciascuna approssimazione.
– Utilizzare i conteggi per stimare le probabilità e confrontarle con le probabilità attese in base ai bias.

4. Esempio di Crittoanalisi Lineare su DES:

Consideriamo un esempio semplificato in cui abbiamo identificato un'approssimazione lineare per la prima S-box in DES. Supponiamo che l'approssimazione sia:

    \[ P[1] \oplus C[3] \oplus K[5] = 0 \]

Qui, P[1] è la prima parte del testo in chiaro, C[3] è il terzo bit del testo cifrato e K[5] è il quinto bit della chiave. I passaggi per rompere DES utilizzando questa approssimazione sono i seguenti:

4.1. Raccolta dati:

Crittografa un gran numero di testi in chiaro utilizzando DES e raccogli i corrispondenti testi cifrati. Per semplicità, supponiamo di aver raccolto 1,000,000 di coppie di testo in chiaro-testo cifrato.

4.2. Analisi dei dati:

Per ogni coppia testo in chiaro-testo cifrato, calcola il valore di P[1] \opiù C[3]. Se il risultato è 0, incrementa un contatore; altrimenti decrementa il contatore. Il valore del contatore indicherà la distorsione dell'approssimazione.

4.3. Stima dei bit chiave:

In base al controvalore, stimare la probabilità che l'approssimazione sia valida. Confronta questa probabilità con la probabilità attesa in base al bias. Se la probabilità osservata è significativamente superiore o inferiore a 0.5, ciò suggerisce che il bit chiave K[5] è probabile che sia 0 o 1, rispettivamente.

5. Considerazioni pratiche:

Mentre l'esempio sopra è semplificato, la pratica crittoanalisi lineare su DES implica approssimazioni più complesse e molteplici S-box. Inoltre, l’attacco richiede notevoli risorse computazionali per raccogliere e analizzare i dati. Tuttavia, con dati e potenza di calcolo sufficienti, la crittoanalisi lineare può ridurre efficacemente lo spazio della chiave e rendere possibile il recupero della chiave.

6. Contromisure:

Per mitigare il rischio della crittoanalisi lineare, i moderni algoritmi crittografici sono progettati pensando alla resistenza a tali attacchi. Tecniche come l'aumento del numero di cicli, l'utilizzo di chiavi di dimensioni maggiori e l'incorporazione di S-box più complesse possono migliorare la sicurezza dei codici a blocchi. Per DES, l'introduzione del Triple DES (3DES) fornisce un livello di sicurezza più elevato applicando l'algoritmo DES tre volte con chiavi diverse.

Altre domande e risposte recenti riguardanti Data Encryption Standard (DES) - Pianificazione e decrittografia delle chiavi:

Visualizza altre domande e risposte in Data Encryption Standard (DES) - Pianificazione e decrittografia delle chiavi

Altre domande e risposte:

Etichettato sotto: , , , , ,