Crittoanalisi Lineare
- Introdotto da
- Mitsuru Matsui
- Anno
- 1993
- Tipo
- linear approximation attack
- Famiglia
- Cryptanalytic technique
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
La crittoanalisi lineare è un attacco a testo in chiaro noto (known-plaintext attack) che sfrutta approssimazioni lineari delle trasformazioni non lineari di un cifrario per recuperare bit della chiave segreta.
Introdotta da Mitsuru Matsui nel 1993, la crittoanalisi lineare fornisce attacchi pratici contro cifrari come DES con una complessità computazionale inferiore alla forza bruta. La tecnica analizza i bias statistici nel modo in cui le combinazioni lineari di bit di testo in chiaro e di testo cifrato si relazionano ai bit della chiave, consentendo il recupero della chiave con requisiti di dati ridotti.
L’intuizione alla base del metodo
La crittoanalisi lineare individua equazioni lineari che mettono in relazione bit di testo in chiaro, bit di testo cifrato e bit di chiave. A causa del mescolamento non perfetto nei round del cifrario, queste equazioni lineari sono valide con una probabilità leggermente superiore al caso casuale. Raccogliendo molte coppie testo in chiaro-testo cifrato e osservando quali valori di chiave fanno sì che queste equazioni siano più spesso valide, l'attaccante può restringere il campo della chiave corretta.
Storia
La crittoanalisi lineare è stata introdotta da Matsui nel 1993 come attacco a testo in chiaro noto contro DES. Nel 1994, Matsui ha dimostrato la prima crittoanalisi sperimentale dello standard DES utilizzando la crittoanalisi lineare, recuperando una chiave con 2^43 testi in chiaro noti. Questa scoperta ha dimostrato attacchi pratici contro uno standard distribuito e ha influenzato lo sviluppo di AES con limiti di resistenza dimostrati.
Quando usarlo
La crittoanalisi lineare è utilizzata nella ricerca sulla crittoanalisi e nella valutazione della progettazione dei cifrari. Guida i progettisti di cifrari nella selezione di S-box e trasformazioni che resistono alle approssimazioni lineari. I cifrari moderni sono progettati con limiti dimostrati sulla forza delle approssimazioni lineari.
Limiti e considerazioni
- I cifrari moderni (AES) sono progettati con cura per resistere alla crittoanalisi lineare con limiti dimostrabili
- Richiede coppie di testo in chiaro-testo cifrato note, che potrebbero non essere disponibili in tutti gli scenari
- I requisiti computazionali e di dati possono superare la fattibilità pratica per cifrari ben progettati
- Scoprire forti approssimazioni lineari per cifrari moderni è estremamente difficile
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Attacco pratico su DES che richiede 2^43 coppie testo in chiaro-testo cifrato e 2^39 operazioni
- Quadro matematico ben formalizzato (lemma di piling-up) per l'analisi dei bias delle approssimazioni
- Completa la crittoanalisi differenziale, trovando debolezze che l'analisi differenziale potrebbe trascurare
- Modella i requisiti di progettazione dei cifrari per la selezione di S-box e la trasformazione dei round
Applicazioni
- Crittoanalisi di cifrari a blocchi (block ciphers) che valuta le proprietà di sicurezza nella ricerca e nella standardizzazione
- Progettazione di cifrari e selezione di S-box per garantire limiti adeguati alle approssimazioni lineari
- Validazione di standard crittografici (NIST, ETSI) che richiede analisi della resistenza lineare
- Valutazione di cifrari legacy per decisioni di ritiro e sostituzione
Come funziona
Come funziona
Trovare approssimazioni lineari: relazioni lineari tra bit di testo in chiaro, bit di testo cifrato e bit di chiave che sono valide con una probabilità significativamente diversa da 0.5.
Stimare il bias (deviazione da 0.5) di ciascuna approssimazione lineare utilizzando l'analisi statistica delle trasformazioni dei round.
Per i valori candidati della chiave, contare quante volte l'approssimazione lineare è valida nelle coppie di testo in chiaro note. La chiave corretta fa sì che l'approssimazione sia valida più frequentemente.
Verificare i bit della chiave recuperati decifrando il testo cifrato e controllandone la correttezza.
Errori comuni
- Presuppone che tutte le approssimazioni lineari siano sfruttabili; approssimazioni deboli forniscono un vantaggio minimo
- Sottovalutazione della difficoltà pratica dell'attacco quando i requisiti teorici di dati sembrano ragionevoli
- Trascurare l'interazione tra proprietà lineari e differenziali nell'analisi dei cifrari
Domande frequenti
Cos'è il lemma di piling-up?
Il lemma di piling-up fornisce un metodo per calcolare il bias delle approssimazioni lineari attraverso più round combinando i bias delle approssimazioni dei singoli round. È fondamentale per la crittoanalisi lineare.
Come resiste AES alla crittoanalisi lineare?
AES utilizza S-box scelti per minimizzare la probabilità massima di approssimazione lineare e uno strato di diffusione che assicura una rapida diffusione dei bias lineari attraverso i round. Limiti dimostrati garantiscono l'assenza di approssimazioni lineari pratiche.
Qual è la differenza tra crittoanalisi lineare e differenziale?
L'analisi differenziale studia le differenze di input-output, mentre l'analisi lineare studia le approssimazioni lineari (XOR di bit di testo in chiaro e testo cifrato). Entrambe sfruttano debolezze strutturali nei cifrari.
La crittoanalisi lineare può rompere cifrari moderni?
Non praticamente. Cifrari moderni come AES hanno limiti dimostrabili sulle approssimazioni lineari che rendono gli attacchi computazionalmente infattibili.
Come valuto la resistenza lineare nella progettazione del mio cifrario?
Analizzare le tabelle di approssimazione lineare delle S-box e calcolare il bias massimo attraverso i round utilizzando il lemma di piling-up. Assicurarsi che il bias massimo sia trascurabile per tutte le possibili approssimazioni lineari.
Metodi correlati
Fonti
Matsui, M. (1993). Linear cryptanalysis method for DES cipher. In Advances in Cryptology - EUROCRYPT 1993, LNCS 765, pp. 386-397.
Apri il riferimento DOICopiato.Matsui, M. (1994). The first experimental cryptanalysis of the Data Encryption Standard. In Advances in Cryptology - CRYPTO 1994, LNCS 839, pp. 1-11.
Apri il riferimento DOICopiato.