Multiplicative Differentials
Nikita Borisov,Monica Chew,Rob Johnson,and David Wagner
University of California at Berkeley
Abstract.We prent a new type of differential that is particularly suited to an-
alyzing ciphers that u modular multiplication as a primitive operation.The
differentials are partially inspired by the differential ud to break Nimbus,and
we generalize that result.We u the differentials to break the MultiSwap ci-
pher that is part of the Microsoft Digital Rights Management subsystem,to derive
a complementation property in the xmx cipher using the recommended modulus,
and to mount a weak key attack on the xmx cipher for many other moduli.We also
prent weak key attacks on veral variants of IDEA.We conclude that cipher
designers may have placed too much faith in multiplication as a mixing operator,恃
and that it should be combined with at least two other incompatible group opera-
tions.
1Introduction
Modular multiplication is a popular primitive for ciphers targeted at software becau
many CPUs have built-in multiply instructions.In memory-constrained environments, multiplication is an attractive alternative to S-boxes,which are often implemented us-ing large tables.Multiplication has also been quite successful at foiling traditional dif-
ferential cryptanalysis,which considers pairs of messages of the form or .The differentials behave well in ciphers that u xors,additions,or bit permutations,but they fall apart in the face of modular multiplication.Thus,we con-
sider differential pairs of the form,which clearly commute with multiplication. The task of the cryptanalyst applying multiplicative differentials is tofind values for that allow the differential to pass through the other operations in a cipher.
It is well-known that differential cryptanalysis can be applied with respect to any Abelian group,with the group operation defining the notion of difference between texts. However,rearchers have mostly ignored multiplicative ,differentials over the multiplicative group,perhaps becau it was not clear how to com-bine them with basic operations like xor.In this paper,we develop new techniques that make multiplicative differentials a more rious threat than previously recognized.
A key obrvation is that in certain cas,multiplicative differentials can be ud
to approximate bitwi operations,like xor,with high probability.As we will e in Section4,for many choices of there exists a such that
with non-negligible probability.Similarly,is simply a left-shift operation. It is therefore possible to analyze how the differentials interact with other operations that are normally thought incompatible with multiplication,such as xor and bitwi permutations.
Cipher Complexity Comments
[Data][Time][Keys]澳洲龙虾
Nimbus CP all e[4](previously known)
xmx(standard version)plementation property(new) xmx(challenge version)CP multiplicative differentials(new)
MultiSwap CP all multiplicative differentials(new)
MultiSwap KP all multiplicative differentials(new)
IDEA-X CP multiplicative differentials(new)
Table1.A summary of some cryptanalytic results using multiplicative differentials.The attacks
on xmx are distinguishing attacks with advantages clo to one;the remaining attacks are key-
recovery attacks.All attacks are on the full ciphers;we do not need to consider reduced-round
variants.“CP”denotes chon plaintexts,and“KP”denotes known plaintexts.
After reviewing previous work in Section2,we give two examples using the ciphers xmx[11]and Nimbus[8]to convey theflavor of the attacks in Section3.In Section4,
we generalize the ideas and catalogue veral common cipher primitives that prerve
助睡眠的音乐multiplicative differentials.We then focus on specific ciphers.Section5prents many moduli,including the xmx challenge modulus,that admit large numbers of weak keys
in xmx.In Section6,we examine the MultiSwap cipher[12],which is ud in Mi-crosoft’s Digital Rights Management system,and show that it is extremely vulnerable
to multiplicative differential cryptanalysis.In Section7,we study veral IDEA[7]风平浪静是什么意思
variants obtained by replacing additions with xors and show that the variants are vul-nerable to weak key attacks using multiplicative differentials.As an example,we show
that IDEA-X,a version of IDEA derived by replacing all the additions with xors,is in-
cure.This suggests that multiplicative differentials may yield new attacks on IDEA. Table1summarizes the attacks developed in this paper.
2Related Work
In this paper,we analyze the xmx cipher,originally propod by M’Raihi,Naccache, Stern and Vaudenay[11].We also look at Nimbus,which was propod by Machado
[8]and broken by Furman[4].IDEA wasfirst propod by Lai,Masy and Murphy [7].Meier obrved that part of the IDEA cipher often reduces to an affine transfor-
mation,and ud this to break2rounds using differential cryptanalysis[10].Daemen,
Govaerts,and Vandewalle obrved that whenever ,the cond least signicant bit of,is[2].They showed that if certain IDEA sub-
keys are,the algorithm can be broken with differential cryptanalysis.We u the
same obrvation tofind weak keys for a variant of IDEA in Section7.The class of weak keys wefind is much larger(keys versus keys),but they are otherwi unrelated.The newest cipher we look at,MultiSwap,was designed by Microsoft and subquently rever-engineered and published on the Internet under the pudonym Beale Screamer[12].
Differential cryptanalysis was invented by Biham and Shamir[1].In the prent paper,we apply the ideas of differential cryptanalysis using a non-standard group op-
eration:multiplication modulo.Daemen,van Linden,Govaerts,and Vandewalle have performed a very thorough analysis of multiplication mod,how it relates to elementary bit-operations,and its potential for foiling differential cryptanalysis[3].
In Section6we u the multiplicative homomorphism
搞笑诗句
to recover MultiSwap keys efficiently.This technique is the multiplicative equivalent of Matsui’s linear cryptanalysis[9].In a similar vein,Harpes,Kramer and Masy ap-plied the quadratic residue multiplicative homomorphism QR,for ,to attack IDEA[5].Kely,Schneier and Wagner ud the reduction map(a ring homomorphism),for and dividing,in cryptanalysis[6].
3Two Examples
To illustrate some of the ideas behind our attacks,we give two examples of using mul-tiplicative differentials to cryptanalyze simple ciphers.Throughout the paper,will reprent the th bit of,and will denote the least significant bit of.1 Cryptanalysis of xmx.As afirst example,we demonstrate a complementation property for the“standard”version of the xmx cipher[11],which operates on-bit blocks using two basic operations:multiplication modulo and xor.The th round of the cipher is
where the binary operator“”is defined by
if
otherwi.
The cipher has an output termination pha that may be viewed as an extra half-round, so the entire algorithm is
xmx
where counts the number of rounds.
In the paper introducing xmx[11],the designers recommend lecting.2 The curious thing about this choice of is that for all,
什么是胆囊炎This is a conquence of the following simple obrvation:if,then if and only if.As a result,this differential will be prerved with probability1through the entire cipher,giving a complementation property
xmx xmx
After describing the basic cipher,the xmx designers suggest veral possible extensions, including rotations and other bit permutations.None of the enhancements would de-stroy this complementation property.
We analyze other versions of xmx later;e Section5.
肠梗阻Cryptanalysis of Nimbus.As a cond example,we explain how the framework of multiplicative differentials can be ud to better understand a previously known attack on Nimbus.Nimbus accepts64-bit blocks,and its th round is
rev
where rev revers the bits in a64-bit word.The subkeys must be odd for the cipher to be invertible.
At FSE2001,Furman ud the xor differential,which pass through one round of Nimbus whenever rev is odd,to launch a devastating attack on this cipher[4].
Furman’s xor differential may appear mysterious atfirst,but can be readily ex-plained using the language of multiplicative differentials.Whenever is odd,
(This is a standard fact from two’s complement arithmetic,and follows from the earlier obrvation that.)So Furman’s differential pairs are in fact pairs where but, a property that obviously survives multiplication by whenever is odd.In other words,Furman’s xor differential is equivalent to the multiplicative differential
(with probability),
taken,with explicit analysis of the high bit to ea propagation through the rev operation.
Discussion.The complementation property of standard xmx has not been previously described,despite xmx’s relative maturity.The attack on Nimbus was previously de-scribed using xor differentials,but is neatly summarized in our new framework for multiplicative differentials.We believe the two examples motivate further study of multiplicative differentials,and the remainder of this paper is dedicated to this task.
4New Differentials
Most of the conclusions in this ction are summarized in Table2.
The xmx example in Section3ud the multiplicative difference,becau
.Thus the multiplicative differential pair is equivalent to the xor differential pair.In the Nimbus example,the modulus is of the form instead of,so the identity between the multiplicative and xor differentials does not hold.However,there is an approximate identity
,which holds whenever is odd,or equivalently,when.
Operation Modulus
1111
multiply by0
multiply by
101–
multiply by
reduction mod
111111
111111
111111
电脑截屏快捷键是哪个
Fig.1.The modulus,the bit-constraints on values of for which, and.See Proposition1for a preci definition of.
To generalize the multiplicative/xor correspondence exploited in the two exam-ples,first obrve that every-bit modulus,,can be divided into strings of the form and strings of the form.As an example,the15-bit modulus
is divided into such substrings in Figure1.
For each gment of the modulus of the form,we u the xor differential .For the gments of the modulus of the form,we u the xor differ-ential.Suppo is one of the gments of of the form. Then we also require that and.The constraint that rves the same purpo as the constraint that be odd in the Nimbus differential:it ensures that when and are added together,a chain of carries is started at bit.The require-ment that assures that no carry bits propagate past bit when and are added together.In the example,bit of is constrained if and only if bit of is0. This is always true becau of the symmetry between and.
The above scheme works by controlling the carry bits when and are added together.It ensures that,for each substring of the modulus of the form,a carry chain is started at the low bit and terminated at the high bit.Starting and stopping carry chains necessitates imposing constraints on,and if two substrings of the form
are adjacent,it is more efficient to simply ensure that the carry chain from thefirst substring propagates to the cond.Analogously,if the modulus contains a substring of the form,then the above method will start a carry chain,only to terminate it at the next bit.A more efficient approach would ensure that no carry ever started.Algorithm1,which computes an optimal value of for a given,incorporates the improvements.The algorithm also outputs and,which reprent the bits of constrained to0and1,respectively.
Algorithm1Compute the optimal.
best-differential
,
for length-2
switch
ca//Begin a carry chain by requiring.
,
ca//Force carry propagation by requiring.
ca//Force no carry by requiring.
ca//End carry chain by requiring.
,
default//No change to carry bit.No constraint on.
if then
output
To determine the probability that a randomly lected satisfies the bit-constraints described above,let
be the number of bits ,the number of bits of that are constrained).Then will satisfy the constraints with probability at least.To e why this is only a lower bound,consider the modulus
(ba2).The constraints derived from this modulus are and.However, only one value of fails to satisfy,so this constraint is nearly vacuous. The following proposition formalizes this discussion:
Proposition1.Let be an-bit modulus.Let the-bit words,be the result of Algorithm1,and let.Take any.Define:
if and
otherwi.
Then if and only if.By symmetry, .Further,define to be the number of0bits in.Then,for a uniformly distributed,with probability at least.Finally,for any ,.
The Nimbus attack us the slight tweak of considering pairs such that
but not mod.Generalizing this gives a truncated multiplica-tive differential.
Proposition2.Suppo
where each stands for any single bit,and suppo moreover that is odd.If is odd, then
