S-box del Rijndael

L'S-box è utilizzata nell'algoritmo crittografico Rijndael (alias AES).

L'S-box

Dopo che la moltiplicazione di matrici è stata completata, viene eseguito un OR esclusivo fra il numero decimale "99" (0x63 in notazione esadecimale, "1100011" in notazione binaria, "11000110" come stringa di bit con il bit meno significativo in prima posizione). Questa operazione genera la seguente S-Box, che è rappresentata in notazione esadecimale:

	00	01	02	03	04	05	06	07	08	09	0a	0b	0c	0d	0e	0f
00	63	7c	77	7b	f2	6b	6f	c5	30	01	67	2b	fe	d7	ab	76
10	ca	82	c9	7d	fa	59	47	f0	ad	d4	a2	af	9c	a4	72	c0
20	b7	fd	93	26	36	3f	f7	cc	34	a5	e5	f1	71	d8	31	15
30	04	c7	23	c3	18	96	05	9a	07	12	80	e2	eb	27	b2	75
40	09	83	2c	1a	1b	6e	5a	a0	52	3b	d6	b3	29	e3	2f	84
50	53	d1	00	ed	20	fc	b1	5b	6a	cb	be	39	4a	4c	58	cf
60	d0	ef	aa	fb	43	4d	33	85	45	f9	02	7f	50	3c	9f	a8
70	51	a3	40	8f	92	9d	38	f5	bc	b6	da	21	10	ff	f3	d2
80	cd	0c	13	ec	5f	97	44	17	c4	a7	7e	3d	64	5d	19	73
90	60	81	4f	dc	22	2a	90	88	46	ee	b8	14	de	5e	0b	db
a0	e0	32	3a	0a	49	06	24	5c	c2	d3	ac	62	91	95	e4	79
b0	e7	c8	37	6d	8d	d5	4e	a9	6c	56	f4	ea	65	7a	ae	08
c0	ba	78	25	2e	1c	a6	b4	c6	e8	dd	74	1f	4b	bd	8b	8a
d0	70	3e	b5	66	48	03	f6	0e	61	35	57	b9	86	c1	1d	9e
e0	e1	f8	98	11	69	d9	8e	94	9b	1e	87	e9	ce	55	28	df
f0	8c	a1	89	0d	bf	e6	42	68	41	99	2d	0f	b0	54	bb	16

L'S-box è generata determinando l'inverso moltiplicativo di un numero appartenente al campo finito del Rijndael (lo zero, che non ha inversi, è impostato a zero). L'inverso moltiplicativo è poi trasformato usando la seguente trasformazione affine:

${\displaystyle {\begin{bmatrix}1&0&0&0&1&1&1&1\\1&1&0&0&0&1&1&1\\1&1&1&0&0&0&1&1\\1&1&1&1&0&0&0&1\\1&1&1&1&1&0&0&0\\0&1&1&1&1&1&0&0\\0&0&1&1&1&1&1&0\\0&0&0&1&1&1&1&1\end{bmatrix}}{\begin{bmatrix}x_{0}\\x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\\x_{6}\\x_{7}\end{bmatrix}}+{\begin{bmatrix}1\\1\\0\\0\\0\\1\\1\\0\end{bmatrix}}}$

dove [x₀, ..., x₇] è l'inverso moltiplicativo espresso come vettore.

La moltiplicazione di matrici può essere calcolata con il seguente algoritmo:

1. immagazzinare l'inverso moltiplicativo del numero di ingresso in 2 variabili temporanee ad 8 bit senza segno s e x;
2. ruotare s di 1 bit a sinistra; se il valore di s aveva il bit più alto (l'ottavo da destra) impostato a "1", impostare il bit più basso di s ad "1", altrimenti a "0";
3. OR esclusivo fra x ed s, immagazzinando il risultato in x;
4. per 3 iterazioni: ripetere i punti 2. e 3. (i punti 2. e 3. saranno eseguiti 4 volte in totale);
5. x conterrà adesso il risultato della moltiplicazione

Le colonne sono determinate dal nibble meno significativo, le righe sono determinate dal nibble più significativo. Ad esempio, il valore 0x9a è convertito in 0xb8. Da notare che l'inverso moltiplicativo di 0x00 è definito come sé stesso.

S-box invertita

La tabella seguente rappresenta l'S-box invertita del Rijndael:

	00	01	02	03	04	05	06	07	08	09	0a	0b	0c	0d	0e	0f
00	52	09	6a	d5	30	36	a5	38	bf	40	a3	9e	81	f3	d7	fb
10	7c	e3	39	82	9b	2f	ff	87	34	8e	43	44	c4	de	e9	cb
20	54	7b	94	32	a6	c2	23	3d	ee	4c	95	0b	42	fa	c3	4e
30	08	2e	a1	66	28	d9	24	b2	76	5b	a2	49	6d	8b	d1	25
40	72	f8	f6	64	86	68	98	16	d4	a4	5c	cc	5d	65	b6	92
50	6c	70	48	50	fd	ed	b9	da	5e	15	46	57	a7	8d	9d	84
60	90	d8	ab	00	8c	bc	d3	0a	f7	e4	58	05	b8	b3	45	06
70	d0	2c	1e	8f	ca	3f	0f	02	c1	af	bd	03	01	13	8a	6b
80	3a	91	11	41	4f	67	dc	ea	97	f2	cf	ce	f0	b4	e6	73
90	96	ac	74	22	e7	ad	35	85	e2	f9	37	e8	1c	75	df	6e
a0	47	f1	1a	71	1d	29	c5	89	6f	b7	62	0e	aa	18	be	1b
b0	fc	56	3e	4b	c6	d2	79	20	9a	db	c0	fe	78	cd	5a	f4
c0	1f	dd	a8	33	88	07	c7	31	b1	12	10	59	27	80	ec	5f
d0	60	51	7f	a9	19	b5	4a	0d	2d	e5	7a	9f	93	c9	9c	ef
e0	a0	e0	3b	4d	ae	2a	f5	b0	c8	eb	bb	3c	83	53	99	61
f0	17	2b	04	7e	ba	77	d6	26	e1	69	14	63	55	21	0c	7d

L'S-box invertita è semplicemente l'S-box eseguita alla rovescia: ad esempio, l'S-box invertita di 0xdb è 0x9f. Viene calcolata computando prima la trasformazione affine inversa del valore di ingresso e poi l'inverso moltiplicativo. La trasformata affine inversa è definita come segue:

${\displaystyle {\begin{bmatrix}0&0&1&0&0&1&0&1\\1&0&0&1&0&0&1&0\\0&1&0&0&1&0&0&1\\1&0&1&0&0&1&0&0\\0&1&0&1&0&0&1&0\\0&0&1&0&1&0&0&1\\1&0&0&1&0&1&0&0\\0&1&0&0&1&0&1&0\end{bmatrix}}{\begin{bmatrix}x_{0}\\x_{1}\\x_{2}\\x_{3}\\x_{4}\\x_{5}\\x_{6}\\x_{7}\end{bmatrix}}+{\begin{bmatrix}1\\0\\1\\0\\0\\0\\0\\0\end{bmatrix}}}$

Specifiche progettuali

L'S-box del Rijndael è stata progettata specificatamente per risultare resistente alla crittoanalisi differenziale e lineare: ciò si è ottenuto minimizzando la correlazione tra le trasposizioni lineari di bit di input/output ed al tempo stesso minimizzando la probabilità di far propagare una differenza. Inoltre, per irrobustire dell'S-box contro gli attacchi algebrici è stata aggiunta la trasformazione affine.

Nel caso si sospetti la presenza di una trap door all'interno del cifrario, l'S-box corrente può essere sostituita da un'altra. Gli autori affermano che la struttura del cifrario Rijndael dovrebbe offrire abbastanza resistenza alla crittoanalisi lineare e differenziale da resistere a questi tipi di attacco anche se venisse utilizzata una S-box che presentasse o una correlazione "media" o la propagazione di differenze.

Una equazione alternativa per la Trasformazione Affine

Una equazione alternativa per la trasformazione affine è:

${\displaystyle b'_{i}=b_{i}\oplus b_{(i+4)mod8}\oplus b_{(i+5)mod8}\oplus b_{(i+6)mod8}\oplus b_{(i+7)mod8}\oplus c_{i}}$

dove b', b e c sono matrici ad 8 bit e c è "01100011"^[1].

Implementazioni

Quella che segue è un'implementazione in Java del precedente algoritmo:

public  static boolean[]  affineX (boolean[]  bprime, boolean[]  b, boolean[]  c) {	
	for (int  j=0; j<8; j++) {
		bprime[ j ]   =   b[ j ] ^ b[ (j+4)%8 ];
		bprime[ j ]  ^=   b[  (j+5)%8 ];
		bprime[ j ]  ^=   b[  (j+6)%8 ];
		bprime[ j ]  ^=   b[  (j+7)%8 ];
		bprime[ j ]  ^=   c [ j ];
	}
	return  bprime;
}