S-Box
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].
Caratteristiche[modifica | modifica wikitesto]
In generale le S-Box ricevono m bit di ingresso e li trasformano in n bit di uscita. Una S-Box n × m può essere implementata come una lookup table di 2m word di n 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[modifica | modifica wikitesto]
Questa è un esempio di matrice S-Box 4×16 del DES (S5):
| S5 | 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[modifica | modifica wikitesto]
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.
Sicurezza e crittanalisi[modifica | modifica wikitesto]
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[modifica | modifica wikitesto]
- ^ (EN) Bruce Schneier, Applied Cryptography, 2ª ed., John Wiley & Sons, 1996, p. 280, ISBN 0-471-12845-7.
- ^ (EN) (PDF) Cache-timing attacks on AES - Daniel J. Bernstein
Bibliografia[modifica | modifica wikitesto]
- Kaisa Nyberg, Perfect nonlinear S-boxes (PDF), Advances in Cryptology - EUROCRYPT '91, Brighton, 1991, pp. 378-386. URL consultato il 20 febbraio 2007 (archiviato dall'url originale il 26 settembre 2007).
- Don Coppersmith, The Data Encryption Standard (DES) and its strength against attacks, in IBM Journal of Research and Development, vol. 38, n. 3, 1994, pp. 243-250.
- S. Mister and C. Adams, Practical S-Box Design (ps), Workshop on Selected Areas in Cryptography (SAC '96) Workshop Record, Queens University, 1996, pp. 61-76. URL consultato il 20 febbraio 2007 (archiviato dall'url originale il 31 agosto 2006).
- Bruce Schneier, Bruce Schneier, Applied Cryptography, Second Edition, John Wiley & Sons, 1996, pp. 296-298, 349, ISBN 0-471-11709-9.
Voci correlate[modifica | modifica wikitesto]
- Crittografia simmetrica
- Cifratura a blocchi
- Cifrario a trasposizione
- Cifrario a sostituzione
- Funzione booleana
- P-box
- S-box del Rijndael
Altri progetti[modifica | modifica wikitesto]
Collegamenti esterni[modifica | modifica wikitesto]
- (EN) A literature survey on S-Box design - Research Comments from Ciphers By Ritter, su ciphersbyritter.com.
- (EN) John Savard's "Questions of S-Box Design", su quadibloc.com.
- (EN) Gargiulo's "S-Box Modifications and Their Effect in DES-like Encryption Systems", su securitydocs.com. URL consultato il 14 dicembre 2008 (archiviato dall'url originale il 13 maggio 2008).
