In crittografia, le S-Box (o Substitution-box, lett. "scatole di sostituzione") sono dei componenti base degli algoritmi a chiave simmetrica. Nella crittografia a blocchi le S-Box vengono utilizzate per oscurare relazioni tra il testo in chiaro e il testo cifrato seguendo il principio della confusione enunciato da Shannon. Spesso le S-Box vengono appositamente progettate per resistere alla crittanalisi, come nel caso del DES[1].
In generale le S-Box ricevono bit di ingresso e li trasformano in bit di uscita. Una S-Box può essere implementata come una lookup table di word di bit l'una, che di norma sono tabelle fisse, come nel caso del DES, anche se in alcuni cifrari sono generate dinamicamente a partire dalla chiave crittografica, come nel caso del Blowfish e del Twofish. Bruce Schneier descrive la moltiplicazione lineare dell'IDEA come una S-Box dipendente dalla chiave.
Esempio di S-Box
Questa è un esempio di matrice S-Box del DES ():
4 bit centrali in ingresso
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
bit esterni
00
0010
1100
0100
0001
0111
1010
1011
0110
1000
0101
0011
1111
1101
0000
1110
1001
01
1110
1011
0010
1100
0100
0111
1101
0001
0101
0000
1111
1100
0011
1001
1000
0110
10
0100
0010
0001
1011
1100
1101
0111
1000
1111
1001
1100
0101
0110
0011
0000
1110
11
1011
1000
1100
0111
0001
1110
0010
1101
0110
1111
0000
1001
1100
0100
0101
0011
Questa S-Box ha 6 bit di ingresso e 4 in uscita. Il primo e l'ultimo bit vengono utilizzati per individuare la riga mentre i bit centrali vengono utilizzati per individuare la colonna. Per esempio il numero in ingresso 011011 ha agli estremi i bit 01 e centralmente i bit 1101 che producono come uscita il valore 1001.
Utilizzo nel Data Encryption Standard
Le S-Box utilizzate del DES sono state per anni oggetto di studi dato che si riteneva possibile che il Governostatunitense avesse accuratamente scelto i valori delle S-Box per poter decifrare qualsiasi messaggio tramite una particolare parola chiave che avrebbe funzionato come una chiave universale. Dopo la scoperta pubblica della crittanalisi differenziale, Don Coppersmith nel 1994 pubblicò degli studi riservati sulle S-Box che dimostravano che queste erano state accuratamente progettate per resistere a quel tipo di attacco dato che gli ingegneri IBM (che progettarono il DES) erano già a conoscenza di quella tecnica di analisi decenni prima della sua "scoperta" da parte degli esperti esterni. Un altro studio dimostrò che anche una piccola modifica dei valori nelle S-Box avrebbe esposto il DES alla crittoanalisi differenziale.
Sicurezza e crittanalisi
Molte ricerche sono state svolte sulle S-Box e si è scoperto molto sulle loro proprietà e sulle tecniche per sviluppare delle buone S-Box.
Talune ricerche[2] di Daniel J. Bernstein hanno dimostrato come la classica implementazione software delle S-Box, ovvero l'uso di array pre-calcolato di valori, sia in realtà vulnerabile ad attacchi basati sul tempo: difatti per vari motivi (in primis la dimensione limitata delle cache delle CPU) difficilmente l'intero array avrà tempi di accesso omogenei. Utilizzando questa tecnica ha sviluppato un programma dimostrativo che recupera una chiave AES da un'altra macchina in rete locale in poche ore e senza utilizzare alcuna informazione sui dati cifrati stessi. Bisogna ancora capire quanto questo si ripercuoterà sull'utilità stessa di utilizzo delle S-Box, spesso usate proprio perché l'accesso ad un array pre-calcolato è sempre stato considerato sia efficiente che tempo-costante.
Note
^
(EN) Bruce Schneier, Applied Cryptography, 2ª ed., John Wiley & Sons, 1996, p. 280, ISBN0-471-12845-7.