RC5

In crittografia l'RC5 è un algoritmo di cifratura a blocchi progettato da Ronald Rivest nel 1994. È degno di nota per la sua semplicità e perché una sua evoluzione (l'RC6) è stato fra i candidati per l'Advanced Encryption Standard.

RC5
Schema del cifrario RC5
Generale
Progettisti	Ronald Rivest
Prima pubblicazione	1994
Successori	RC6, Akelarre
Dettagli
Dimensione chiave	da 0 a 2048 bit (suggeriti 128)
Dimensione blocco	32, 64 o 128 bit
Struttura	rete di Feistel
Numero di passaggi	da 1 a 255 (inizialmente suggeriti 12)
Migliore crittanalisi
L'implementazione dell'RC5 con 12 cicli e blocchi di 64 bit è sensibile ad un attacco differenziale con l'uso di 244 testi in chiaro scelti

Descrizione

Al contrario della maggior parte degli algoritmi di cifratura a blocchi, nei quali è parametrizzabile al più una delle costanti dell'elaborazione, solitamente la dimensione della chiave, nell'RC5 tutti i parametri di base sono variabili: è possibile infatti scegliere fra diverse dimensioni del blocco (32, 64 o 128 bit), della chiave (da 0 a 2048 bit) e del numero di passaggi o rounds (da 0 a 255). Non tutti i valori ammessi portano ad un risultato utilizzabile; ad esempio, se la dimensione della chiave o il numero di passaggi è 0, praticamente non avviene nessuna elaborazione. La combinazione suggerita dall'autore è di 12 passaggi con una chiave da 128 bit e con blocchi da 64 bit.

Una delle operazioni centrali dell'RC5 consiste in una rotazione dei bit dei dati di un valore dipendente dal dato di ingresso; si può anche affermare che il cifrario stesso nacque proprio per studiare le proprietà crittografiche di questa operazione. In ogni ciclo si effettuano anche operazioni di OR esclusivo e addizioni modulari, organizzate in una rete di Feistel esprimibili con poche righe di codice.

Il gestore della chiave è, invece, più complesso: esso espande la chiave utilizzando una funzione monodirezionale che utilizza le espansioni binarie di e e della sezione aurea come sorgenti di "numeri dalle proprietà non nascoste" (o nothing up my sleeve numbers" in inglese).

La semplicità dell'algoritmo unità alla novità delle rotazioni dipendenti dai dati hanno fatto dell'RC5 un interessante oggetto di studi per i crittanalisti.

RC5 orientato alla word

La caratteristica principale dell'RC5 è quella di essere un algoritmo orientato all'architettura del computer sul quale è in esecuzione. In particolare, tutte le elaborazioni sono effettuate su stringhe di lunghezza pari a quella della word della macchina, ossia dipendono dall'architettura del computer su cui sta girando il cifrario, con ovvi vantaggi in termini di prestazioni: le operazioni su stringhe di lunghezza pari a quella della word del computer richiedono meno cicli macchina). Un'altra caratteristica è quella di usare istruzioni "base", comuni alla maggior parte dei processori, in quanto opera su dati la cui lunghezza è identica a quella word, anche se la stessa può essere di lunghezza diversa (come già detto, la lunghezza di una word può variare in funzione dell'architettura del computer), ed anche rotazioni dipendenti dai dati.

L'RC5 è un algoritmo che usa poca memoria, quindi risulta adatto per dispositivi quali le smart card, ed è semplice da analizzare ed implementare; infatti l'RC5 è stato utilizzato in diversi prodotti, ad esempio le librerie crittografiche BSAFE e JSAFE di RSA Security. Dobbiamo anche ricordare che RC5 si basa su una macchina con un'architettura little-endian (il bit meno significativo è posto a destra; tipicamente processori Intel); in realtà può funzionare anche su una macchina con architettura big endian (ovvero, tipicamente processori Motorola), ma il procedimento d'espansione della chiave ha bisogno di alcune modifiche.

Si può affermare che l'RC5 è una famiglia di cifrari dove ogni membro è indicato come RC5-w/r/b, con le lettere w/r/b che indicano i seguenti parametri:

• w, word, denota la lunghezza della word del computer (32, 64 o 128 bit). La dimensione del blocco è pari al doppio della lunghezza della word, o 2w, mentre tutte le funzioni interne dell'RC5 ricevono in ingresso e forniscono in uscita dati lunghi esattamente w bit.
• r, round, indica il numero di passaggi che varia da 0 a 255 (anche se, come è stato specificato, utilizzare 0 passaggi equivale a non eseguire il processo di cifratura per cui il numero minimo di passaggi è 1). L'RC5 utilizza un passaggio iniziale differente da tutti gli altri utilizzati durante il processo di cifratura; ogni passaggio utilizza 2 sottochiavi. Dalla chiave iniziale sono generate 2 sottochiavi per ogni passaggio comune, quindi 2r, e 2 sottochiavi per la fase iniziale, per un totale di 2r+2.
• b, byte, è la lunghezza della chiave espressa in byte, che varia da 0 a 255 (anche qui, utilizzare una chiave di 0 byte equivale a non effettuare nessuna operazione di cifratura). Il gestore della chiave genera 2r+2 sottochiavi ognuna lunga w bit.

Perciò quando si scrive RC5 w/r/b significa che si sta indicando il RC5 che lavora su 2 word di w bit con un numero di passaggi pari ad r e con una chiave lunga b byte.

Le operazioni dell'RC5

Come detto, le operazioni eseguite dall'RC5 sono tutte operazioni di w bit, e sono le seguenti:

• la somma a+b modulo 2w;
• la sottrazione a-b modulo 2w;
• a XOR b bit a bit
• a << b, ossia rotazione a sinistra di b bit applicato alla word a
• a >> b, ossia rotazione a destra di b bit applicato alla word a

La prima operazione da vedere è la schedulazione della chiave. Partendo da una chiave di b byte, dove b è un parametro di RC5, immaginiamo che questi byte siano memorizzati in un array K:

K[0,….,b-1]

A partire da questa chiave l'algoritmo produce un altro array denominato S, l'array delle sottochiavi, perché in totale occorrono 2r+2 sottochiavi:

S[0,….,2r+1]

In effetti, per produrre S, che verrà poi usato nella fase di cifratura, occorre effettuare una conversione dai byte per ottenere delle word, dopo di che su queste ultime saranno eseguite delle operazioni per andare ad aggiornare il contenuto di S(funzione di mescolamento, o Mixing Function). Questo array intermedio è denominato L e si ottiene dall'array K. Su un computer ad architettura little-endian viene semplicemente copiato il contenuto dell'array K nell'array L; in totale, L avrà c locazioni, dove c=(8*b)/w. Nel caso in cui 8*b non dovesse essere un multiplo di w, saranno aggiunti degli "zero" per completare il valore (operazione di padding).

Algoritmo di schedulazione

L'algoritmo di schedulazione della chiave è diviso in 2 fasi:

1. la prima fase inizializza l'array S (quello finale) con dei valori che dipendono da alcune costanti definite Pw e Qw, di w bit. Pw è l'espansione binaria a w bit del numero di Nepero (e=2,71828182459045... in decimale): in particolare Pw = Odd[(e-2)2w] dove Odd(x) indica l'intero dispari più vicino ad x. Qw è l'espansione binaria a w bit del rapporto aureo (φ=1,6180339887... in decimale): in particolare, Qw = Odd[(φ-1)2w]. Questi valori sono già stati calcolati e memorizzati in una tabella, ed il loro valore dipende da w. In seguito l'array S viene modificato usando l'array L, che contiene la chiave. In particolare, nella prima locazione di S viene posto Pw, e poi, dalla locazione 1 fino a 2r+1, viene aggiornata la locazione S[i] andando a sommare la costante Qw alla locazione immediatamente precedente. La chiave non è stata ancora usata.
2. La seconda fase, chiamata Mixing Function, sfrutta l'array L, nel quale è stata copiata in precedenza la chiave: viene eseguito un ciclo che è eseguito 3 volte il numero massimo di elementi contenuto tra c e 2r+2. Ad ogni ciclo S e L vengono aggiornati. Vengono usati due puntatori i e j: S è aggiornato in base al valore attuale di S[i] e a 2 word a w bit denominate X e Y, inizialmente poste a 0, e poi con una rotazione a sinistra di 3 locazioni; L viene aggiornato in base al valore attuale di L[j] e a 2 word a w bit denominate X e Y e poi una rotazione che dipende dai dati, cioè la rotazione dipende dal valore di X+Y. Dopo di che, ogni volta, gli indici i e j vengono incrementati.

In pratica l'array S che era stato inizializzato con le costanti Pw e Qw subisce degli aggiornamenti che dipendono dall'array L, array di c word ottenuto dalla chiave iniziale. Il risultato finale equivale ad un array S aggiornato, array di 2r+2 locazioni, ognuna di w bit. Quindi, la fase di schedulazione della chiave prende in input una chiave di b byte e produce 2r+2 sottochiavi, ognuna di w bit.

Fase di cifratura

La fase di cifratura parte da un blocco di 2 word di w bit e produce un altro blocco di 2 word di w bit, tramite r passaggi. Vi è un passaggio iniziale che usa 2 sottochiavi e poi ogni passaggio successivo utilizza altre 2 chiavi sottochiavi, per un totale di 2r+2. Nell'algoritmo, in pratica, sono svolte operazioni di addizione su word di w bit, operazioni di XOR e rotazioni dei bit. Il testo in chiaro è memorizzato in 2 word denominate A e B, ognuna di w bit, in cui viene restituito anche l'output dell'algoritmo.

Si aggiorna A con la prima sottochiave e B con la seconda sottochiave (le prime 2 sottochiavi utilizzate), dopo di che vengono eseguiti r passaggi in cui vengono usate 2 diverse sottochiavi S[2i] e S[2i+1] (altre 2r sottochiavi). Durante un singolo passaggio viene eseguita prima l'operazione di XOR bit a bit tra A e B, poi una rotazione di B, ed infine una addizione con la sottochiave S[2i] col il risultato finale che aggiorna A. Inoltre, nel passaggio viene eseguito anche uno XOR bit a bit tra B ed A, poi viene eseguita una rotazione a sinistra che dipende dal valore di A, ed infine una somma con la sottochiave S[2i+1], aggiornando il valore di B.

A differenza del DES e dei cifrari di Feistel, nell'RC5 entrambe le metà del blocco dati sono aggiornate nel passaggio, sia la parte A sia la parte B. Nei cifrari di Feistel invece una parte è ricopiata e si aggiorna l'altra metà del blocco. La decifratura è l'operazione inversa della cifratura: infatti sono svolti prima gli r passaggi a partire dall'ultimo al primo e poi gli ultimi 2 aggiornamenti. L'unica differenza tra la fase di cifratura e quella di decifratura è che in quest'ultima le operazioni sono di sottrazione invece che di somma; restano invariate le operazioni di XOR e di rotazione.

Le caratteristiche dell'RC5

Le caratteristiche salienti di RC5 sono:

1. le rotazioni sono dipendenti dai dati e non sono fisse; questo fatto complica gli attacchi di crittanalisi differenziale e lineare, proprio perché l'ammontare dello shift dipende dal dato;
2. in ogni passaggio le operazioni coinvolgono tutto il blocco, a differenza di quello che accadeva nel DES;
3. l'RC5 è una famiglia che dipende dai parametri w/r/b, quindi per specificare un particolare cifrario dobbiamo indicare tali valori.

Voci correlate

• Crittografia asimmetrica

Collegamenti esterni

• Il documento con cui Rivest presenta l'RC5 (PDF), su people.csail.mit.edu.
• Corso RC5 , su dia.unisa.it.
• Cosa sono RC5 ed RC6?, su rsasecurity.com (archiviato dall'url originale il 29 dicembre 2006).
• Algoritmo di cifratura RC5, su islab.oregonstate.edu. URL consultato il 6 dicembre 2006 (archiviato dall'url originale il 1º settembre 2006).
• RC5-CTS cipher (TXT), su ietf.org.