From Surf Wiki (app.surf) — the open knowledge base

Mod n cryptanalysis

Attack applicable to block and stream ciphers

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

Then, because

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

it follows 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 19 or 20 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.

References

{{cite conference | access-date = 2007-02-12 }}
{{cite journal | access-date = 2007-02-12 }}
{{cite journal

Info: Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

cryptographic-attacks modular-arithmetic

Want to explore this topic further?

Ask Mako anything about Mod n cryptanalysis — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report