Crittanalisi mod n

In crittografia, la crittanalisi mod n è un attacco crittanalitico che si può applicare ai cifrari a blocchi e ai cifrari a flusso. È una specifica forma di crittanalisi a partizioni che sfrutta le incongruenze presenti durante la cifratura di classi di equivalenza modulo n. Il metodo fu esposto per la prima volta nel 1999 da John Kelsey, Bruce Schneier e David Wagner quando venne applicato all'algoritmo RC5P (una variante dell'RC5) e a M6 (famiglia di cifrari a blocchi usati nello standard FireWire). Questi attacchi sfruttano le proprietà delle addizioni binarie e di rotazione di bit modulo a dove a è un numero primo di Fermat. Sono stati proposti attacchi anche agli algoritmi di cifratura M8^[1] e a Rabbit^[2].

Analisi Mod 3 di RC5P

Per l'algoritmo RC5P, è stata condotta l'analisi di tipo mod 3^[3]. È stato osservato che le operazioni di cifratura (rotazione e addizione, entrambe su parole di 32 bit) sono in qualche modo legate alla classe di congruenza mod 3. Per illustrare l'approccio si consideri la rotazione a sinistra di un singolo bit:

${\displaystyle X\lll 1=\left\{{\begin{matrix}2X,&{\mbox{if }}X<2^{31}\\2X+1-2^{32},&{\mbox{if }}X\geq 2^{31}\end{matrix}}\right.}$

Quindi, siccome

${\displaystyle 2^{32}\equiv 1{\pmod {3}},\,}$

si può dedurre che

${\displaystyle X\lll 1\equiv 2X{\pmod {3}}.}$

Quindi la rotazione a sinistra di un singolo bit ha la forma mod 3. L'analisi di altre operazioni (rotazioni dipendenti dai dati e addizioni modulari) rivelano tendenze simili. Nonostante ci siano alcuni problemi teorici nell'analisi della combinazione di operazioni, la tendenza può essere individuata sperimentalmente per l'intero cifrario. Nella descrizione fatta da Kelsey, Sheier e Wagner, sono stati fatti esperimenti fino a sette cicli di cifratura e, basandosi su queste evidenze, hanno ipotizzato che, usando questo attacco, sia possibile decifrare RC5P anche dopo diciannove o venti cicli. È stato anche individuato un metodo per recuperare la chiave segreta.

Sono stati provati attacchi ancora più efficaci contro l'algoritmo M6 che usano le modalità mod 5 e mod 257.

Note

1. (EN) Toshio Tokita, Tsutomu Matsumoto, On Applicability of Differential Cryptanalysis, Linear Cryptanalysis and Mod n Cryptanalysis to an Encryption Algorithm M8 (ISO9979-20), in Ipsj Journal, vol. 42, n. 8.
2. (EN) Vincent Rijmen, "mod n" Cryptanalysis of Rabbit (PDF), Cryptico, 1º dicembre 2003.
3. (EN) John Kelsey, Bruce Schneier, David Wagner, Mod n Cryptanalysis, with Applications Against RC5P and M6 (PDF), su schneier.com, Rome, Springer-Verlag, 1999-03, pp. 139–155.

Portale Crittografia

Portale Sicurezza informatica