Visualizza wikitesto di S-Box

In [[crittografia]], le '''S-Box''' (o '''''Substitution-box''''', {{Lett|scatole di sostituzione}}) sono dei componenti base degli [[Crittografia simmetrica|algoritmi a chiave simmetrica]]. Nella [[cifrario a blocchi|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 e diffusione|confusione]] enunciato da ''[[Claude Shannon|Shannon]]''. Spesso le S-Box vengono appositamente progettate per resistere alla [[crittanalisi]], come nel caso del [[Data Encryption Standard|DES]]<ref>
{{en}}{{cita libro
|nome=Bruce
|cognome=Schneier
|titolo=Applied Cryptography
|edizione=2
|editore=John Wiley & Sons
|anno=1996
|isbn=0-471-12845-7
|pagine=280
}}</ref>.

== Caratteristiche ==
In generale le S-Box ricevono <math>m</math> bit di ingresso e li trasformano in <math>n</math> bit di uscita. Una S-Box <math>n \times m</math> può essere implementata come una [[lookup table]] di <math>2^m</math> [[word]] di <math>n</math> 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'[[International Data Encryption Algorithm|IDEA]] come una S-Box dipendente dalla chiave.

=== Esempio di S-Box ===
Questa è un esempio di matrice S-Box <math>4 \times 16</math> del DES (<math>S_5</math>):

<div style="font-size: smaller">
{| class="wikitable" align="center" border="1" cellpadding="2"
|-----
! rowspan="2" colspan="2" | <math>S_5</math>
! colspan="16" |  4 bit centrali in ingresso
|-----
! 0000
! 0001
! 0010
! 0011
! 0100
! 0101
! 0110
! 0111
! 1000
! 1001
! 1010
! 1011
! 1100
! style="background:#ffdead;" | 1101
! 1110
! 1111
|-----
! rowspan="4" | bit esterni
! 00
| 0010 || 1100 || 0100 || 0001 || 0111
| 1010 || 1011 || 0110 || 1000 || 0101 || 0011 || 1111
| 1101 || style="background:#ffdead;" | 0000
| 1110 || 1001
|-----
! style="background:#deffad;" | 01
| style="background:#deffad;" | 1110 || style="background:#deffad;" | 1011
| style="background:#deffad;" | 0010
| style="background:#deffad;" | 1100 || style="background:#deffad;" | 0100
| style="background:#deffad;" | 0111
| style="background:#deffad;" | 1101 || style="background:#deffad;" | 0001
| style="background:#deffad;" | 0101
| style="background:#deffad;" | 0000 || style="background:#deffad;" | 1111
| style="background:#deffad;" | 1100
| style="background:#deffad;" | 0011 || style="background:#fefe2d;" | 1001
| style="background:#deffad;" | 1000 || style="background:#deffad;" | 0110
|-----
! 10
| 0100 || 0010 || 0001 || 1011 || 1100
| 1101 || 0111 || 1000 || 1111 || 1001 || 1100 || 0101
| 0110 || style="background:#ffdead;" | 0011
| 0000 || 1110
|-----
! 11
| 1011 || 1000 || 1100 || 0111 || 0001
| 1110 || 0010 || 1101 || 0110 || 1111 || 0000 || 1001
| 1100 || style="background:#ffdead;" | 0100
| 0101 || 0011
|}
</div>

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 {{Codice|codice=011011}} ha agli estremi i bit {{Codice|codice=01}} e centralmente i bit {{Codice|codice=1101}} che producono come uscita il valore {{Codice|codice=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 [[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 [[Data Encryption Standard#Coinvolgimento dell.27NSA|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<ref>{{en}}{{pdf}} [https://cr.yp.to/antiforgery/cachetiming-20050414.pdf Cache-timing attacks on AES] - Daniel J. Bernstein</ref> 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 [[Advanced Encryption Standard|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==
<references/>

==Bibliografia==
* {{cita conferenza
 |autore       = [[Kaisa Nyberg]]
 |titolo       = Perfect nonlinear S-boxes
 |conferenza   = Advances in Cryptology - [[EUROCRYPT]] '91
 |pagine       = 378-386
 |data         = 1991
 |città       = [[Brighton]]
 |url          = http://dsns.csie.nctu.edu.tw/research/crypto/HTML/PDF/E91/378.PDF
 |formato      = PDF
 |accesso      = 20 febbraio 2007
 |urlmorto     = sì
 |urlarchivio  = https://web.archive.org/web/20070926205507/http://dsns.csie.nctu.edu.tw/research/crypto/HTML/PDF/E91/378.PDF
 |dataarchivio = 26 settembre 2007
}}
* {{cita pubblicazione
    | autore = [[Don Coppersmith]]
    | titolo = The Data Encryption Standard (DES) and its strength against attacks
    | giornale = IBM Journal of Research and Development
    | volume = 38
    | numero = 3
    | pp = 243-250
    | data = 1994
    | url = http://ieeexplore.ieee.org/search/freesrchabstract.jsp?tp=&arnumber=5389567&queryText%3DThe+Data+Encryption+Standard+.LB.DES.RB.+and+its+strength+against+attacks%26openedRefinements%3D*%26searchField%3DSearch+All
    }}
* {{cita conferenza
 |autore       = S. Mister and [[Carlisle Adams|C. Adams]]
 |titolo       = Practical S-Box Design
 |conferenza   = Workshop on [[Selected Areas in Cryptography]] (SAC '96) Workshop Record
 |pp           = 61-76
 |data         = 1996
 |città       = [[Queens University]]
 |url          = http://adonis.ee.queensu.ca/sac/sac96/papers/paper7.ps
 |formato      = ps
 |accesso      = 20 febbraio 2007
 |urlmorto     = sì
 |urlarchivio  = https://web.archive.org/web/20060831001412/http://adonis.ee.queensu.ca/sac/sac96/papers/paper7.ps
 |dataarchivio = 31 agosto 2006
}}
* {{cita libro
    | cognome = Schneier
    | nome = Bruce
    | coautori = Bruce Schneier
    | titolo = Applied Cryptography, Second Edition
    | editore = [[John Wiley & Sons]]
    | data = 1996
    | pagine = 296-298, 349
    | isbn = 0-471-11709-9
    }}

==Voci correlate==
* [[Crittografia simmetrica]]
* [[Cifratura a blocchi]]
* [[Cifrario a trasposizione]]
* [[Cifrario a sostituzione]]
* [[Funzione booleana]]
* [[P-box]]
* [[S-box del Rijndael]]

== Altri progetti ==
{{Interprogetto|preposizione=sulle}}

== Collegamenti esterni ==
* {{cita web|http://www.ciphersbyritter.com/RES/SBOXDESN.HTM|A literature survey on S-Box design - Research Comments from Ciphers By Ritter|lingua=en}}
* {{cita web|http://www.quadibloc.com/crypto/co4513.htm|John Savard's "Questions of S-Box Design"|lingua=en}}
* {{cita web|1=http://www.securitydocs.com/library/1319|2=Gargiulo's "S-Box Modifications and Their Effect in DES-like Encryption Systems"|lingua=en|accesso=14 dicembre 2008|urlarchivio=https://web.archive.org/web/20080513024854/http://www.securitydocs.com/library/1319|dataarchivio=13 maggio 2008|urlmorto=sì}}

{{Cifratura a blocchi}}
{{Cifratura a flusso}}
{{Portale|crittografia|Sicurezza informatica}}

[[Categoria:Cifrari a blocchi]]