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.
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
.
Le S-Box utilizzate del DES sono state per anni oggetto di studi dato che si riteneva possibile che il Governo statunitense 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.
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.