Mod n cryptanalysis: Difference between revisions

Revision as of 14:49, 8 June 2004

Latest revision as of 17:18, 19 December 2024

(43 intermediate revisions by 27 users not shown)

Line 1:

{{DISPLAYTITLE:Mod {{Mvar|n}} cryptanalysis}}

In [[cryptography]], '''mod ''n'' cryptanalysis''' is an [[cryptanalysis|attack]] applicable to [[block cipher|block]] and [[stream cipher]]s. It is a form of [[partitioning cryptanalysis]] which exploits unevenness in how the [[cipher]] operates over [[equivalence class]]es (congruence classes) [[modular arithmetic|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).

{{Short description|Attack applicable to block and stream ciphers}}

{{no footnotes|date=August 2017}}

In [[cryptography]], '''mod ''{{Mvar|n''}} cryptanalysis''' is an [[cryptanalysis|attack]] applicable to [[block cipher|block]] and [[stream cipher]]s. It is a form of [[partitioning cryptanalysis]] whichthat exploits unevenness in how the [[cipher]] operates over [[equivalence class]]es (congruence classes) [[modular arithmetic|modulo ''{{Mvar|n''}}]]. The method was first suggested in [[1999]] by [[John Kelsey (cryptanalyst)|John Kelsey]], [[Bruce Schneier]], and [[David A. Wagner|David Wagner]] and applied to RC5P (a variant of [[RC5]]) and [[M6 (cipher)|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 for the operations in the cipher (rotation and addition, both on 32-bit words) were somewhat biased over congruence classes mod 3. AsTo anillustrate examplethe approach, consider left rotation by a single bit. :

<math>X <<< 1=\left\{\begin{matrix} 2X, & \mbox{if } X < 2^{23} \\ 2X + 1 - 2^{32}, & \mbox{if } X \geq 2^{32}\end{matrix}\right.</math> <!-- would prefer "\lll" or "\ll" to "<<<", but gives error (June 8, 2004) -->

: <math>X <<<\lll 1=\left\{\begin{matrix} 2X, & \mbox{if } X < 2^{2331} \\ 2X + 1 - 2^{32}, & \mbox{if } X \geq 2^{3231}\end{matrix}\right.</math> <!-- would prefer "\lll" or "\ll" to "<<<", but gives error (June 8, 2004) -->

Because

Then, because

<math>2^{32} \equiv 1\pmod 3</math>,

: <math>2^{32} \equiv 1\pmod 3,\,</math>,

we can deduce that

it follows that

<math>X <<< 1 \equiv 2X\pmod 3</math>

: <math>X <<<\lll 1 \equiv 2X\pmod 3.</math>

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 (cryptography)|key]].

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 nineteen19 or twenty20 rounds of RC5P can be [[distinguishing attack|distinguished from random]] using this attack. There is also a corresponding method for recovering the secret [[key (cryptography)|key]].

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

==References==

* {{cite conference

* [[John Kelsey]], [[Bruce Schneier]], [[David Wagner]]: Mod n Cryptanalysis, with Applications Against RC5P and M6. Fast Software Encryption 1999: pp139&ndash;155

| author = [[John Kelsey (cryptanalyst)|John Kelsey]], [[Bruce Schneier]], [[David A. Wagner|David Wagner]]

* [[Vincent Rijmen]], "mod n" Cryptanalysis of Rabbit, Whitepaper, Cryptico, December 1, 2003. [http://www.cryptico.com/Files/filer/wp_modn_analysis.pdf (PDF)]

* [[John Kelsey]], [[Bruce Schneier]],| [[Davidtitle Wagner]]:= Mod n Cryptanalysis, with Applications Against RC5P and M6. Fast Software Encryption 1999: pp139&ndash;155

* Toshio Tokita&#12289;Tsutomu Matsumoto, On Applicability of Differential Cryptanalysis, Linear Cryptanalysis and Mod n Cryptanalysis to an Encryption Algorithm M8 (ISO9979-20), IPSJ JOURNAL Vol.42 No.08.

| conference = [[Fast Software Encryption]], Sixth International Workshop Proceedings

| pages = 139&ndash;155

| publisher = [[Springer-Verlag]]

| date = March 1999

| ___location = [[Rome]]

| url = http://www.schneier.com/paper-mod3.html

| format = [[PDF]]/[[PostScript]]

| access-date = 2007-02-12 }}

* {{cite journal

| author = [[Vincent Rijmen]]

| title = "mod n" Cryptanalysis of Rabbit

| version = [[White paper]], Version 1.0

| publisher = [[Cryptico]]

| date = 2003-12-01

| url = http://www.cryptico.com/Files/filer/wp_modn_analysis.pdf

| access-date = 2007-02-12 }}

* {{cite journal

* |author1=Toshio Tokita&#12289; |author2=Tsutomu Matsumoto, | title = On Applicability of Differential Cryptanalysis, Linear Cryptanalysis and Mod n Cryptanalysis to an Encryption Algorithm [[M8 (cipher)|M8]] (ISO9979-20), IPSJ JOURNAL Vol.42 No.08.

| journal = Ipsj Journal

| volume = 42

| issue = 8 }}

{{Cryptography navbox | block}}

[[Category:Cryptographic attacks]]

{{Block_ciphers}}

[[Category:Modular arithmetic]]