3 RC6
RC6
è un cifrario a blocchi a chiave simmetrica, semplice, compatto e sicuro, con dimensione dei blocchi
di 128 bit e lunghezza della chiave variabile, in un range tra 0 e 32
byte.
RC6 è un’evoluzione dell’RC5 ([3],
[9]), in particolare l’RC5 è
stato modificato in modo da andare incontro alle richieste del NIST riguardo le
specifiche tecniche dell'AES. RC5 raggiunge prestazioni ottimali quando la taglia del blocco in input
è doppia rispetto alla grandezza della parola macchina. Segue che per blocchi
di 128 bit, è necessaria un’architettura a 64 bit, il che non
soddisfa la richiesta del NIST.
Un'altra
modifica apportata all'RC5 è l'aggiunta, all'insieme delle operazioni
primitive, della moltiplicazione di interi; quest'ultima è adoperata per
computare le rotazioni, in modo da renderle dipendenti da tutti i bit di un
registro, piuttosto che da un porzione di tali bit, incrementandone la sicurezza.
3.2
Dettagli dell'algoritmo
RC6
appartiene alla famiglia degli algoritmi di cifratura parametrizzati [3].
L'algoritmo cifra parole di w bit, eseguendo r iterazioni (o
round), utilizzando una chiave di cifratura lunga b bytes, come illustrato
nella Figura
3.1. L'algoritmo considera 3 parametri fondamentali per il
suo funzionamento: w, r e b.
Per soddisfare le richieste dello standard AES, la versione che i progettisti
hanno presentato è RC6-32/20/b con b = 16, 24 o 32 bytes.
RC6-w/r/b
opera su unità di 4 parole di w-bit utilizzando le seguenti 6
operazioni di base:
·
a + b: addizione di interi modulo 2w;
·
a - b: sottrazione di interi modulo 2w;
·
a Å b: XOR bit a bit di parole di w bit;
a •
b:
moltiplicazione di interi modulo 2w;
·
a «
b: shift ciclico a sinistra di a di un
numero di bit dato dai lg w bit meno significativi di b;
·
a » b: shift ciclico a destra di a di un numero di bit dato dai
lg w bit meno significativi di b.
3.2.1 Algoritmi di cifratura e decifratura
L'algoritmo
di cifratura prende in input
·
il
testo in chiaro, memorizzato nei 4 registri A, B, C,
D ognuno di w bit;
·
il
numero r di iterazioni da eseguire;
·
la
chiave, memorizzata in S[0, .., 2r + 3] (si veda il paragrafo 3.2.2)
e
restituisce il testo cifrato nei registri A, B, C, D.
L'algoritmo
é il seguente:
|
Algoritmo di cifratura |
|
B = B+S[0] D = D+S[1]
t = (B • (2B+1)) « lg w u = (D • (2D+1)) «
lg w A = ((AÅ t) « u)+S[2i] C =
((C Å u) «
t)+S[2i+1]
(A,B,C,D) = (B,C,D,A) A = A+S[2r+2] C =
C+S[2r+3] |
In modo del tutto analogo, l'algoritmo di decifratura prende in input il testo
cifrato, memorizzato nei 4 registri, e restituisce il testo in chiaro
nei registri A, B, C, D.
L'algoritmo
è il seguente:
|
Algoritmo di decifratura |
|
C = C-S[2r+3]
|
3.2.2 Schedulazione della chiave
La
schedulazione della chiave dell' RC6-w/r/b é sostanzialmente identica a quella
dell'RC5, cambia, soltanto, il numero di parole chiave dedotte da quella
fornita dall’utente: 2r + 1 per
l’RC5 e 2r + 4 per l’RC6.
L'utente
fornisce una chiave di b bytes, con 0 £ b £ 32, che viene caricata in
modalità little-endian in un vettore L di c parole (ognuna di w
bit), dove 
; così il primo byte della chiave è memorizzato come byte di
ordine inferiore di L[0], ecc., e L[c-1] è riempito con degli
zeri nelle posizioni più significative, se necessario, per completare
l’inizializzazione di L. L'algoritmo di schedulazione genera 2r+4
parole di w bit, che memorizza nel vettore S[0, .., 2r + 3].
L'algoritmo é il seguente:
|
Algoritmo di schedulazione
della chiave |
|
L [0,…,c-1] = chiave con padding di 0
se necessario
|
La procedura di
schedulazione, utilizza, due “costanti magiche” Pw e Qw,
che sono così definite per un w arbitrario:
Pw = Odd((e - 2)2w)
Qw = Odd((F - 1)2w)
dove
·
e è il numero di Nepero: e= 2.71828182459045…
·
F è il rapporto aureo: F =
(1+51/2)/2=1.61803398874989…
e Odd(x)
è l’intero dispari più vicino ad x.
In
particolare nella Tabella 3.1 vengono riportati i valori di Pw e Qw per w = 16, 32,
64.
|
|
3.3 Performance dello schema RC6
Uno
dei criteri di valutazione dell’AES, riguarda le performance raggiunte da
implementazioni dell'algoritmo in diversi linguaggi di sviluppo, quali l'ANSI C
ed il Java e da implementazioni che permettano l'utilizzo dell'algoritmo su
architetture con processori a capacità computazionali limitate, ad esempio le
smart-card. Nei successivi paragrafi, è analizzato il comportamento
computazionale delle implementazioni dell'algoritmo in ANSI C e Java, ed è
mostrato come sia possibile adattarlo ad architetture con processore ad 8
bit senza che le proprietà di sicurezza ed efficienza vengano penalizzate.
3.3.1 Performance dello schema RC6 in ANSI C, Java e
Assembly
Nella
Tabella
3.2 vengono riportati dei valori che evidenziano le caratteristiche
computazionali dell'RC6 nei diversi linguaggi di sviluppo richiesti dal NIST
(queste misurazioni sono state effettuate dalla RSA). I valori riportati
rappresentano una media dei risultati dei test effettuati su ogni
implementazione dell'algoritmo (in particolare ogni test è stato eseguito 10
volte).
I
valori di riferimento per le implementazioni ANSI C ed Assembly sono
stati ottenuti utilizzando un elaboratore con processore Pentium II 266MHz
(misure scalate a 200 MHz) con 32MB di RAM e Windows 95 (durante l'esecuzione
dei test, gli interrupt mascherabili sono stati disabilitati in modo da
aumentare l'accuratezza dei risultati).
I risultati riportati per l'implementazione
Java sono stati ottenuti utilizzando un elaboratore con processore PENTIUM
PRO 180MHz con 64 MB di RAM e Windows NT 4.0., e l’interprete
Javasoft JDK 1.1.6 (compilazione JIT disabilitata) Symantec Java! JustInTime
Compiler versione 210.054.
I dati riportati nella
Tabella
3.2, non comprendono i valori relativi alla schedulazione della
chiave (mostrati nella Tabella 3.3) i quali sono indipendenti dalla
lughezza della chiave fornita dall'utente. I dati riferiti all'implementazione
ANSI C e JAVA sono stati ottenuti, utilizzando blocchi di 3.000 e di 100.000
caratteri, in modalità ECB.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
3.3.2 Performance di RC6 su piattaforma ad 8
bit
L'algoritmo
RC6 é adattabile ad architetture con processore ad 8 bit; é infatti
possibile definire le operazioni di base di RC6-32/20/b adoperando operazioni
implementabili sulla maggior parte dei processori. Verrà mostrato come sia
possibile implementare RC6-32/20/b sul processore ad 8 bit Intel MCS 51.
·
Cifratura/Decifratura. Analizzando gli algoritmi descritti nel paragrafo
precedente, e considerando che l'espressione
B x (2B +1) = 2B2+ B
può essere valutata con 1 quadrato e 2 addizioni ad 8
bit. Segue che in ogni round dell'algoritmo di cifratura/decifratura
vengono eseguite:
6 addizioni,
2 OR esclusivi (XOR),
2 quadrati,
2 rotazioni a sinistra di 5
bit (log w = log 32 = 5)
2 rotazioni a sinistra di una
quantità r variabile.
come mostrato nella Figura 3.2.
Queste operazioni possono essere implementate su un processore ad 8
bit come segue:
1.
un'addizione
a 32 bit può essere computata mediante 4 addizioni a 8
bit con riporto (ADDC);
2.
un
OR esclusivo (XOR) a 32 bit può essere computato
con 4 XOR a 8 bit (XRL);
3.
un
quadrato a 32 bit può essere computato mediante 6
moltiplicazioni di stringhe di 8 bit (MUL) ed 11 addizioni con
riporto (ADDC). In questo caso le 6 moltiplicazioni sono sufficienti
dato che si è interessati solo ai 32 bit meno significativi di tale
prodotto.
4.
una
rotazione ciclica a sinistra di 5 bit su una stringa di 32 bit
può essere computata attraverso una rotazione a destra di 1 bit su una
stringa di 32 bit, eseguita 3 volte, e permutando i 4 byte
risultanti (vedi Figura 3.3). La
rotazione a destra di 1 bit su stringhe a 32
bit può essere implementata mediante 4 rotazioni ad 8 bit (RRC).
|
Figura 3.3: rotazione a sinistra di 5 bit mediante l’esecuzione di 3
rotazioni a destra di 1 bit su stringhe a 32 bit seguita da una
opportuna permutazione p. |
|
|
5.
una
rotazione ciclica a sinistra di z bit su una stringa di 32 bit può
essere computata con una rotazione a sinistra o a destra di 1 bit,
eseguita z’ volte (con z’£ 4 ottenuto dai 5 bit
meno significativi di z), seguita da una permutazione dei 4
bytes. Ogni permutazione può essere controllata mediante i salti (JB).
Motivazione:
Se z è multiplo di 8 è possibile effettuare una rotazione
ciclica a sinistra di z bit con la sola permutazione dei 4 bytes
(si noti che effettuare una rotazione ciclica
a sinistra di 8 bit corrisponde ad una rotazione ciclica a
sinistra dei 4 byte), segue che, non occorrono operazioni di “«”.
Se z non è multiplo di 8, allora z=8k+ z’ con k³0 e
1£ z’£ 7,
il valore di z’ è l’equivalente decimale dei 3 bit meno
significativi di z. Segue che permutando i 4 byte in modo
opportuno, lo stesso risultato si può ottenere effettuando k rotazioni
cicliche a sinistra dei 4 byte, si otteniene la sequenza di 4
byte su cui effettuare una rotazione ciclica a sinistra di z’ bit, per
concludere l’operazione.
Se z’ >4 è possibile effettuare 8-z’ shift ciclici a destra
e poi permutare i 4 byte come in Figura 3.3 per ottenere lo stesso
risultato che si otterrebbe con una rotazione ciclica a sinistra di z’ bit. In particolare se z’=5 vengono
effettuate le stesse operazioni descritte nel passo 4.
Dato che la permutazione dei 4 byte corrisponde a
shift ciclici a sinistra dei 4 byte, allora non è significativo
applicare prima la permutazione o gli shift ciclici su bit dei quattro byte.
Si può ora definire lo pseudo algoritmo per effettuare una rotazione ciclica a
sinistra di z bit:
·
se 1£ z’£ 4 allora
effettuare l’operazione « z’ sulla sequenza di quattro byte.
·
se 5£ z’£ 7 allora
effettuare l’operazione « 8-z’ sulla sequenza di quattro byte.
·
“permutazione dei byte” in modo opportuno mediante i salti
Tutte le istruzioni, sopra elencate, sono eseguite in 1
ciclo, eccetto MUL e JB che richiedono, rispettivamente, 4 e 2
cicli. Il numero totale di cicli necessari all'esecuzione di un round di RC6 é
stimato nella Tabella 3.4. Tabella 3.4: rotazione a sinistra di 5 bit mediante l’esecuzione di 3
rotazioni a destra di 1 bit su stringhe a 32 bit seguita da una
opportuna permutazione p. Istruzioni cicli per operazione Cicli + 4 ADDC 4 4 x 6 = 24 Å 4 XRL 4 4 x 2 = 8 Quadrato 6 MUL, 11 ADDC 35 35 x 2 = 70 « 5 12 RRC 12 12 x 2 = 24 « z (media 2) 8 RRC/RLC, 8JB 24 24 x 2 = 48 Totale 174 Il numero di cicli per eseguire
cifratura/decifratura sono circa (174 x 20) x 4 =
13920, dove 20 rappresenta il
numero di iterazioni e 4 è un fattore utilizzato per incorporare nella
stima i cicli che occorrono per l’indirizzamento, l’azzeramento e l’overhead.
Dato che sul processore MCS 51 ogni ciclo impiega 1 microsecondo, allora la
velocità dell'algoritmo é circa (1000000/13920) x 128 =
9,2 Kbit/sec. Recentemente è stata
sviluppata un'implementazione di RC6 per processori Intel 8051che necessita di 13535
cicli per cifrare un blocco di dati. ·
Schedulazione della chiave. La parte
fondamentale della schedulazione della chiave é rappresentata dall'ultimo for
nel codice dell'algoritmo (vedi paragrafo 3.2.2). Per b=16, 24, 32,
il numero di iterazioni di questo ciclo é v = 3 x max(20x2+4, b/4) = 132, che non dipende
da b. In ogni iterazione vengono effettuate 4 addizioni a 32
bit, 1 rotazione a sinistra di 3 bit ed una rotazione a sinistra
di t=(A+B) bit. Inoltre, ci sono alcune operazioni ad 8 bit che
vengono incluse come overhead. Seguendo un'analisi del tutto simile a quella
fatta per la cifratura/decifratura si ottiene, per ogni iterazione, un numero
di cicli pari a 52. Pertanto, sono necessari (52 x 132) x 4 = 27456 cicli per
schedulare chiavi di 128, 192, 256 bit, impiegando, sul
processore MCS 51, circa 27 millisecondi. La forza crittografica dell’RC6 dipende
pesantemente dall'utilizzo delle rotazioni dipendenti dai dati, le quali non permettono
di collezionare statistiche ed evitano attacchi di crittoanalisi sia
differenziale che crittoanalisi lineare. Gli attacchi più avanzati di
crittoanalisi differenziale [11] e lineare [12], ammissibili
su versioni dell'algoritmo con un basso numero di iterazioni, non sono adatti
ad attaccare versioni dell'RC6 con 20 iterazioni; la principale
difficoltà nasce dal fatto che é difficile trovare caratteristiche iterative o
buone approssimazioni lineari su cui basare l'attacco. Il miglior attacco (in riferimento ad RC6-32/20/b) che un
crittoanalista può apportare ad RC6 consiste in una ricerca esaustiva della
chiave di cifratura di b byte (o sul vettore S[0, …, 43] espanso,
quando la chiave fornita dall'utente é particolarmente lunga). Per riuscire in
questo intento sono richieste un numero di operazioni determinato dal min(28b,
21408). In conclusione, sulla sicurezza dell'RC6 si può affermare quanto
segue: 1.
il miglior attacco sul cifrario è la ricerca esaustiva su tutti i
possibili valori della chiave di cifratura fornita dall'utente; 2.
la quantità di dati necessaria ad attacchi sofisticati, quale la
crittoanalisi differenziale e lineare, supera di gran lunga la quantità di dati
a disposizione; 3.
non esistono esempi conosciuti che abbiano sfruttato le proprietà
della weak-key. 3.5 Alcuni esempi di cifratura In questo paragrafo mostriamo alcuni
esempi dell'applicazione dell'RC6 a particolari testi da cifrare ed il
corrispondente testo cifrato:
Testo
in chiaro
00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00
Chiave
usata
00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00
Testo
cifrato
8f c3 a5 36 56 b1 f7 78 c1 29 df 4e 98 48
a4 1e
Testo
in chiaro
02 13 24 35 46 57 68 79 8a 9b ac bd ce df e0 f1
Chiave
usata
01 23 45
67 89 ab cd ef 01 12 23 34 45 56 67 78
Testo
cifrato
52 4e 19
2f 47 15 c6 23 1f 51 f6 36 7e a4 3f 18
Testo
in chiaro
00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00
Chiave
usata
00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00
00 00 00 00 00
Testo
cifrato
6c d6 1b
cb 19 0b 30 38 4e 8a 3f 16 86 90 ae 82
Testo in chiaro
02 13 24 35 46 57 68 79 8a 9b ac bd ce df e0 f1
Chiave usata
01 23 45
67 89 ab cd ef 01 12 23 34 45 56 67 78
89 9a ab bc cd de ef f0
Testo cifrato
68 83 29
d0 19 e5 05 04 1e 52 e9 2a f9 52 91 d4
Testo in chiaro
00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00
Chiave usata
00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00
Testo cifrato
8f 5f bd
05 10 d1 5f a8 93 fa 3f da 6e 85 7e c2
Testo in chiaro
02 13 24 35 46 57 68 79 8a 9b ac bd ce df e0 f1
Chiave usata
01 23 45
67 89 ab cd ef 01 12 23 34 45 56 67 78 89 9a ab bc cd de ef f0 10 32 54 76 98
ba dc fe
Testo cifrato
c8 24 18
16 f0 d7 e4 89 20 ad 16 a1 67 4e 5d 48