World Library  
Flag as Inappropriate
Email this Article

Mod n cryptanalysis

Article Id: WHEBN0000709367
Reproduction Date:

Title: Mod n cryptanalysis  
Author: World Heritage Encyclopedia
Language: English
Subject: M6 (cipher), WikiProject Cryptography, Mod, Modular arithmetic, Cryptographic attacks
Collection: Cryptographic Attacks, Modular Arithmetic
Publisher: World Heritage Encyclopedia

Mod n cryptanalysis

In cryptography, mod n cryptanalysis is an attack applicable to block and stream ciphers. It is a form of partitioning cryptanalysis that 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). These attacks used the properties of binary addition and bit rotation modulo a Fermat prime.

Mod 3 analysis of RC5P

For RC5P, analysis was conducted modulo 3. It was observed that 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:

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.

Then, because

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

we can deduce that

X \lll 1 \equiv 2X\pmod 3.

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.

Against M6 there are attacks mod 5 and mod 257 that are even more effective.


  • Toshio Tokita, Tsutomu Matsumoto. "On Applicability of Differential Cryptanalysis, Linear Cryptanalysis and Mod n Cryptanalysis to an Encryption Algorithm  
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.