Chiave debole

In crittografia, una chiave debole (weak key in inglese) è una chiave crittografica che, utilizzata con uno specifico cifrario, porta l'algoritmo crittografico ad operare in modo improprio. Le chiavi deboli normalmente sono solo una piccolissima frazione di tutte le chiavi possibili, ossia, se si utilizza un algoritmo casuale per la generazione delle chiavi per la crittazione di un messaggio, difficilmente si incorre in un problema di sicurezza. In ogni modo è considerato un pregio per un cifrario non avere chiavi deboli. Un cifrario senza chiavi deboli è detto avere uno spazio delle chiavi lineare o piatto.

Chiavi deboli nel DES

Il cifrario a blocchi DES ha alcune chiavi particolari denominate rispettivamente "chiavi deboli" e "chiavi semi-deboli". Queste chiavi, se utilizzate, fanno sì che la modalità di cifratura del DES operi nello stesso modo della modalità di decifratura (potenzialmente anche con una chiave differente).

Durante il funzionamento, il gestore della chiave del DES divide i 56 bit della chiave segreta in 16 sotto-chiavi: ogni sotto-chiave è poi usata per ognuno dei 16 passaggi del DES. Le chiavi deboli del DES sono quelle che producono 16 sotto-chiavi identiche. Ciò accade quando i bit della chiave sono (in esadecimale):^[1]

una sequenza alternata di "0" ed "1": 0x0101010101010101
una sequenza alternata di "F" ed "E": 0xFEFEFEFEFEFEFEFE
0xE0E0E0E0F1F1F1F1
0x1F1F1F1F0E0E0E0E

Se un'implementazione dell'algoritmo non considera i bit di parità, allora le chiavi corrispondenti con i bit di parità invertiti possono operare come chiavi deboli:

una sequenza composta da tutti "0": 0x0000000000000000
una sequenza composta da tutti "1": 0xFFFFFFFFFFFFFFFF
0xE1E1E1E1F0F0F0F0
0x1E1E1E1E0F0F0F0F

Usano le chiavi deboli la funzione PC1 (Permuted Choice 1) del gestore della chiave del DES genera sotto-chiavi composte tutte da "0", tutte da "1" oppure sequenze alternate di "0" ed "1". Dato che tutte le sotto-chiavi risultano identiche e dato che il DES è una rete di Feistel, la funzione di cifratura è auto-invertibile, vale a dire che eseguendo due cifrature si ottiene il testo in chiaro originale.

Il DES ha anche delle chiavi semi-deboli, che fanno genereare 2 sole differenti sotto-chiavi, ognuna usata in 8 passaggi dell'algoritmo. Ciò significa che compaiono in coppie K₁ e K₂ ed hanno la seguente proprietà:

E_{K_{1}}(E_{K_{2}}(M))=M

dove E_K(M) è l'algoritmo di cifratura che cifra il messaggio M con la chiave K. Ci sono 6 coppie di chiavi semi-deboli:

0x011F011F010E010E e 0x1F011F010E010E01
0x01E001E001F101F1 e 0xE001E001F101F101
0x01FE01FE01FE01FE e 0xFE01FE01FE01FE01
0x1FE01FE00EF10EF1 e 0xE01FE01FF10EF10E
0x1FFE1FFE0EFE0EFE e 0xFE1FFE1FFE0EFE0E
0xE0FEE0FEF1FEF1FE e 0xFEE0FEE0FEF1FEF1

Ci sono anche 48 possibili chiavi deboli che fanno generare solo 8 sotto-chiavi distinte (invece di 16)^[2].

Le chiavi deboli e semi-deboli non sono considerati "difetti fatali" del DES. Ci sono 2⁵⁶ (7,21 × 10¹⁶, circa 72 milioni di miliardi) possibili combinazioni di chiavi per il DES, di cui 4 sono chiavi deboli e 12 sono semi-deboli. È nel complesso una piccolissima frazione di tutto lo spazio delle chiavi di cui si può non tenere conto. Se proprio si vuole, è sempre possibile eseguire un controllo per identificare le chiavi deboli e sotto-deboli durante la loro creazione: sono molto poche e facilmente riconoscibili. Resta il fatto che tutte le chiavi del DES possono essere recuperate tramite forza bruta con hardware il cui costo è alla portata di tutti (vedi il progetto COPACOBANA).

Elenco degli algoritmi con chiavi deboli

RC4. I deboli vettori di inizializzazione dell'RC4 permettono ad un attaccante di eseguire un attacco con testo in chiaro noto: questo tipo di attacco è stato ampiamente usato per compromettere la sicurezza del WEP^[3].

IDEA. Le chiavi deboli dell'IDEA sono identificabili con un attacco con testo in chiaro scelto. Esse rendono prevedibili le relazioni fra le somme XOR dei bit del testo in chiaro ed i bit del testo cifrato. Non c'è una lista di queste chiavi ma esse possono essere identificate dalla loro struttura.

DES

Blowfish. Le chiavi deboli del Blowfish producono S-box errate dato che le S-box di questo algoritmo dipendono dalla chiave. Esiste un attacco con testo in chiaro scelto contro una variante del Blowfish con un ridotto numero di passaggi che trae benefici dall'uso delle chiavi deboli. La versione con 16 passaggi non è però coinvolta.

L'assenza di chiavi deboli è uno scopo progettuale

Lo scopo di avere uno spazio delle chiavi "piatto" (cioè con tutte chiavi forti) è da sempre uno degli obiettivi della progettazione dei cifrari. Come nel caso del DES, alle volte un piccolo numero di chiavi deboli può essere tollerato, fatto salvo che siano tutte identificate o identificabili: un algoritmo che ha delle chiavi deboli che non sono note non ispirerebbe molta fiducia.

Ecco le due principali contromisure contro l'utilizzo inavvertito di una chiave debole:

controllare le chiavi generate tramite una lista di chiavi deboli note, oppure strutturare il gestore della chiave in modo che rifiuti l'uso di queste chiavi;
quando il numero di chiavi deboli è noto essere molto piccolo (in paragone alla dimensione dello spazio delle chiavi), generare una chiave in maniera del tutto casuale assicura che le probabilità che essa sia una chiave debole siano molto basse.

Un numero di chiavi deboli elevato è sintomo di un grave difetto nella struttura di qualunque cifrario dato che ci saranno molte probabilità (forse troppe) che una chiave generata casualmente sia una chiave debole, compromettendo la sicurezza dei messaggi cifrati con l'algoritmo. Questo problema richiederà anche un tempo elevato per controllare la debolezza di tutte le chiavi generate casualmente, cosa che potrebbe portare alla tentazione di ridurre detto tempo di controllo aumentando la non sicurezza dell'algoritmo.

Le chiavi deboli sono molto spesso un problema su cui un attaccante può avere del controllo rispetto ad esempio a quali chiavi sono usate. Questa situazione si presenta ad esempio quando un cifrario a blocchi è utilizzato in una modalità di funzionamento atta a creare una funzione crittografica di hash sicura (come la funzione di compressione a senso unico Davies-Meyer).

Note

^ FIPS: Guidelines for implementing and using the NBS Data Encryption Standard Archiviato il 3 gennaio 2014 in Internet Archive. - FIPS-PUB 74
^ NIST: Recommendation for the Triple Data Encryption Algorithm (TDEA) Block Cipher, Special Publication 800-67, pag. 14
^ Fluhrer, Mantin, Shamir: Weaknesses in the key scheduling algorithm of RC4 - Eighth Annual Workshop on Selected Areas in Cryptography (2001)

Voci correlate

Portale Crittografia

Portale Sicurezza informatica

[1] FIPS: Guidelines for implementing and using the NBS Data Encryption Standard Archiviato il 3 gennaio 2014 in Internet Archive. - FIPS-PUB 74

[2] NIST: Recommendation for the Triple Data Encryption Algorithm (TDEA) Block Cipher, Special Publication 800-67, pag. 14

[3] Fluhrer, Mantin, Shamir: Weaknesses in the key scheduling algorithm of RC4 - Eighth Annual Workshop on Selected Areas in Cryptography (2001)

[1]

[2]

[3]