Encyclopedia  |   World Factbook  |   World Flags  |   Reference Tables  |   List of Lists     
   Academic Disciplines  |   Historical Timeline  |   Themed Timelines  |   Biographies  |   How-Tos     
Sponsor by The Tattoo Collection
Mod n cryptanalysis
Main Page | See live article | Alphabetical index

Mod n cryptanalysis

In cryptography, mod n cryptanalysis is an attack applicable to block and stream ciphers. It is a form of partitioning cryptanalysis which exploits unevenness in how the cipher operates over equivalence classes (congruence classes) modulo n. The method was first suggested in 1999 by John Kelsey, Bruce Schneier and David Wagner and applied to RC5P (a variant of RC5) and M6 (a family of block ciphers used in the FireWire standard).

Mod 3 analysis of RC5P

For RC5P, analysis was conducted modulo 3. It was observed that for the operations in the cipher (rotation and addition, both on 32-bit words) were somewhat biased over congruence classes mod 3. To illustrate the approach, consider left rotation by a single bit:

Then, because

,

we can deduce that

.

Thus left rotation by a single bit has a simple description modulo 3. Analysis of other operations (data dependent rotation and modular addition) reveals similar, notable biases. Although there are some theoretical problems analysing the operations in combination, the bias can be detected experimentally for the entire cipher. In (Kelsey et. al, 1999), experiments were conducted up to seven rounds, and based on this they conjecture that as many as nineteen or twenty rounds of RC5P can be distinguished from random using this attack. There is also a corresponding method for recovering the secret key.

References


Block ciphers
Algorithms: 3-Way | AES | Blowfish | Camellia | CAST-128 | CAST-256 | CMEA | DEAL | DES | DES-X | FEAL | G-DES | GOST | IDEA | Iraqi | KASUMI | KHAZAD | Khufu and Khafre; | LOKI89/91 | LOKI97 | Lucifer | MacGuffin | Madryga | MAGENTA | MARS | MISTY1 | MMB | NewDES | RC2 | RC5 | RC6 | Red Pike; | S-1 | SAFER | Serpent | SHARK | Skipjack | Square | TEA | Triple DES; | Twofish | XTEA
Design: Feistel network; | Key schedule; | Product cipher; | S-box | SPN   Attacks: Brute force; | Linear / Differential cryptanalysis | Mod n; | XSL   Standardisation: AES process; | CRYPTREC | NESSIE   Misc: Avalanche effect | Block size; | IV | Key size; | Modes of operation; | Piling-up lemma; | Weak key;