S-box

Da Wikipedia, l'enciclopedia libera.

In Crittografia, le S-box (o Substitution-box) sono dei componenti base degli algoritmi a chiave simmetrica. Nei blocchi di cifratura le S-box vengono utilizzate per oscurare relazioni tra il testo in chiaro e il testo cifrate seguendo il principio della confusione enunciato da Shannon. Spesso le S-box vengono appositamente progettate per resistere alla crittanalisi.

In generale le S-box ricevono m bit di ingresso e li trasformano in n bit di uscita. Una S-box n x m è formata da una matrice. Queste matrici sono statiche e vengono utilizzate nel Data Encryption Standard (DES), ma in molti altri algoritmi di cifratura queste matrici sono generate dinamicamente a partire dalla chiave. Questa strategia viene utilizzata per esempio dal Blowfish e dal Twofish.

Questa è un esempio di matrice S-box 6×4-bit di DES (S₅):

S₅		4 bit centrali in ingresso
S₅		0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1100	1011	1100	1101	1110	1111
Altri bit	00	0010	1100	0100	0001	0111	1100	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 dal DES sono state per anni oggetto di studi dato che, si riteneva possibile che il governo 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 riscoperta della crittanalisi differenziale, Don Coppersmith nel 1994 pubblico degli studi riservati sulle S-box che dimostravano che queste erano state accuratamente progettate per resistere a quel tipo di analisi dato che l'NSA era 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.

Recenti ricerche [1] 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.

[modifica] Voci correlate

Algebra booleana

[modifica] Bibliografia

Coppersmith, Don. (1994). The data encryption standard (DES) and its strength against attacks. The IBM Journal of Research and Development, 38(3), pp243–250.
S. Mister and C. Adams, "Practical S-Box Design," Workshop on Selected Areas in Cryptography (SAC '96) Workshop Record, Queens University, 1996, pp. 61–76