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

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

modifica

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

modifica

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

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.

  1. ^ (EN) Bruce Schneier, Applied Cryptography, 2ª ed., John Wiley & Sons, 1996, p. 280, ISBN 0-471-12845-7.
  2. ^ (EN) (PDF) Cache-timing attacks on AES - Daniel J. Bernstein

Bibliografia

modifica

Voci correlate

modifica

Altri progetti

modifica

Collegamenti esterni

modifica