In
cryptography
Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), ...
, xmx is a
block cipher
In cryptography, a block cipher is a deterministic algorithm that operates on fixed-length groups of bits, called ''blocks''. Block ciphers are the elementary building blocks of many cryptographic protocols. They are ubiquitous in the storage a ...
designed in 1997 by David
M'Raïhi,
David Naccache
David Naccache is a cryptographer, currently a professor at the École normale supérieure and a member of its Computer Laboratory. He was previously a professor at Panthéon-Assas University.
Biography
He received his Ph.D. in 1995 from the ...
,
Jacques Stern
Jacques Stern (born 21 August 1949) is a cryptographer, currently a professor at the École Normale Supérieure. He received the 2006 CNRS Gold medal. His notable work includes the cryptanalysis of numerous encryption and signature schemes, the ...
, and
Serge Vaudenay
Serge Vaudenay (born 5 April 1968) is a French cryptographer and professor, director of the Communications Systems Section at the École Polytechnique Fédérale de Lausanne
Serge Vaudenay entered the École Normale Supérieure in Paris as a ''n ...
. According to the
designers it "uses
public-key
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic alg ...
-like operations as
confusion and diffusion
In cryptography, confusion and diffusion are two properties of a secure cipher identified by Claude Elwood Shannon, Claude Shannon in his 1945 classified report ''A Mathematical Theory of Cryptography''. These properties, when present, work toge ...
means." The
cipher was designed for efficiency, and the only operations it uses are
XOR
Exclusive or, exclusive disjunction, exclusive alternation, logical non-equivalence, or logical inequality is a logical operator whose negation is the logical biconditional. With two inputs, XOR is true if and only if the inputs differ (one ...
s
and
modular multiplications.
The main parameters of xmx are variable, including the
block size and
key size
In cryptography, key size or key length refers to the number of bits in a key used by a cryptographic algorithm (such as a cipher).
Key length defines the upper-bound on an algorithm's security (i.e. a logarithmic measure of the fastest known a ...
, which are equal, as well
as the number of rounds. In addition to the
key, it also makes
use of an odd modulus ''n'' which is small enough to fit in a single block.
The round function is f(m)=(m
oa)·b mod n, where a and b are
subkeys and b is
coprime
In number theory, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equiv ...
to n. Here m
oa represents an operation that
equals m XOR a, if that is less than n, and otherwise equals m. This is a simple
invertible operation: m
oa
oa = m. The xmx cipher consists
of an even number of iterations of the round function, followed by a final
o
with an additional subkey.
The
key schedule
In cryptography, the so-called product ciphers are a certain kind of cipher, where the (de-)ciphering of data is typically done as an iteration of '' rounds''. The setup for each round is generally the same, except for round-specific fixed va ...
is very simple, using the same key for all the multipliers, and
three different subkeys for the others: the key itself for the first half of the
cipher, its
multiplicative inverse
In mathematics, a multiplicative inverse or reciprocal for a number ''x'', denoted by 1/''x'' or ''x''−1, is a number which when Multiplication, multiplied by ''x'' yields the multiplicative identity, 1. The multiplicative inverse of a ra ...
mod n for the last half, and the XOR of these two
for the middle subkey.
The designers defined four specific variants of xmx:
* ''Standard'': 512-bit block size, 8 rounds, n=2
512-1
* ''High security'': 768-bit block size, 12 rounds, n=2
768-1
* ''Very-high security'': 1024-bit block size, 16 rounds, n=2
1024-1
* ''Challenge'': 256-bit block size, 8 rounds, n=(2
80-1)·2
176+157
Borisov, et al., using a multiplicative form of
differential cryptanalysis
Differential cryptanalysis is a general form of cryptanalysis applicable primarily to block ciphers, but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in information input can a ...
, found a
complementation property for any variant of xmx, like the first three above, such that
n=2
k-1, where k is the block size. They also found large
weak key In cryptography, a weak key is a key, which, used with a specific cipher, makes the cipher behave in some undesirable way. Weak keys usually represent a very small fraction of the overall keyspace, which usually means that, a cipher key made by ran ...
classes
for the Challenge variant, and for many other moduli.
References
*
*
{{Cryptography navbox , block
Block ciphers