575 Project - Winter 2000
Comparison with other AES Candidates
Module by IBM
The current Digital Encryption Standard (DES) does
no longer satisfy the need for data security because of its short 56-bit
key. Such short keys can today be broken by brute force attacks (trying
of all keys). That's why the NIST is looking for a newer and more flexible
algorithm to replace DES. One of the candidates for the Advanced Encryption
Standard (AES) is MARS encryption algorithm developed by IBM. It is a symmetric
key block cipher uses 128 bit blocks and supports variable key sizes (from
128 to 1248 bits). MARS is unique in that it combines virtually every design
technique known to cryptographers in one algorithm. It uses addition and
subtractions, S-boxes, fixed and data dependent rotations, and multiplications.
The goal of this project is the analyzes of MARS
encryption algorithm and point out some advantages of this algorithms compared
to the other candidates for AES. Further a demo program based on the c-code
that was published by NIST on February, 18th 2000 shows how the algorithm
MARS is a shared-key block cipher that works with a block size of 128 bit
and a variable key size. The algorithm is a type-3 Feistel network which
is word (32 bit) oriented. The word orientation should bring a performance
for software implementations on most computer architectures available today.
A fully optimized implementation is expected to run at 100Mbit/second and
hardware can achieve an additional 10x speedup factor.
Following you'll find the most important facts how the MARS algorithm
works. If you want more detailed information go to IBM's
MARS page or NIST's
AES finalist page.
MARS algorithm uses a big variety of different operations:
Additions, subtractions and xors: These simple operations are used to mix
data and key values together. Because xors are interleaved with additions
and subtractions these operations do not commute with each other.
Table look-up: Similar to the S-boxes in DES has also MARS cipher a table
look-up. It uses a single table of 512 32-bit words, simple called S-box.
A problem of the table look-up is the slow software implementation (at
least 3 instructions per look-up). That's why S-box look-up is only used
sparely in MARS where fast avalanche of the key bits is needed.
Data-dependent rotations: Data dependent rotations may lead to differential
weaknesses. This problem is solved in MARS by combining these rotations
Multiplications: All multiplications in MARS are modulo 232
which suits most modern computer architectures. Multiplications used to
be a problem in cryptographic algorithms because they were slow. Today
is this no longer the case. Most architectures can complete a multiplication
in 2 clock cycles. MARS algorithms uses 16 multiplications per block. This
should not be a big deal. For hardware realizations we have the the problem
that a multiplicator needs much more chip-space than adders or logical
MARS algorithm takes the 128 bit input block as four 32 bit words. Figure
1 shows the high level structure of the cipher. The input is first proceeded
through a forward mixing stage, which contains a key addition and eight
rounds of unkeyed forward mixing. Then it goes to the cryptographic core
(a type-3 Feistel network) where eight rounds of keyed forward transformation
and eight rounds of keyed backwards transformation are performed and at
the end is another backward mixing stage, which contains eight rounds of
unkeyed backwards mixing and a key subtraction.
Figure 1: High-level structure of the cipher [MarsIBM99]
The structure of the forward mixing stage is showed in figure 2. First
the data words are added with 4 key words. Then 8 rounds of unkeyed type-3
Feistel mixing are performed. Type-3 Feistel mixing means there is always
one word that is used to modify the three other words. The modification
is done without key information by using S-boxes.
The output of the S-boxes is added or xored with the other words. Additional
to the S-box mixing several shifts are performed.
Figure 2: Structure of the forward mixing phase [MarsIBM99]
Also the cryptographic core (figure 3) is a type-3 Feistel network. But
here the algorithm use a keyed E-function (figure 4) instead of the unkeyed
S-boxes as in the forward mixing stage. The output of the E-function is
also added or xored with the other words. There are total 16 rounds in
the core. Eight forward plus eight backward rounds.
Figure 3: Type-3 Feistel network of the main keyed transformation
The E-function (Figure 4) is a combination of different operations that
mix two key word with the input word. This is also the place where the
multiplication comes into play. It also contains an S-box lookup.
The k' (odd) means that this are special made-up key words with special
properties (see Key Expansion ). The E-function
is one of the best designed parts of the MARS algorithm. The different
functions are combined in a way that maximizes the advantage of each.
When you multiply the lower bits of the input have larger effect on the
than the higher bits. Bits that are not fed into the S-box are therefore
the lower bits in the multiplication.
The amount of rotation (13 bit) was set to maximize the resistance to differential
The higher bits of the multiplication output are affected by more input
bits than the lower ones. That's why the higher bits are used to determine
the amount of the data-dependent rotation.
The three lines of the function are as independent of each other as possible
to avoid cancellation and make it harder to obtain a linear approximation.
Since M is the weakest output of the function it is put as the middle output,
so that it is never used to modify the word that is the source for the
modification in the next round.
Figure 4: The E-function of the main keyed transformation [MarsIBM99]
The structure of the backward mixing showed in figure 5 is very similar
to the one of the forward mixing. It consists also of 8 rounds of a unkeyed
type-3 Feistel network, followed by a key subtraction step.
Figure 2: Structure of the forward mixing phase [MarsIBM99]
The S-boxes are designed in a pseudorandom fashion and tested that the
resulting S-box has good differential and linear properties. Values of
the S-boxes see here.
MARS algorithm has a variable key length. The interval of the key length
is either from 128 to 448 bit or 128 to 1248 bit with some restrictions.
Internal the algorithm works with 40 key words, which is equal to 1280
bit. But 32 of these bits are constant 1 (the two least significant bits
of the key words 5,7,9,..,35) therefore the actual internal key is just
1248 bit. There are some further restrictions to that key. The same key
words with the two bits constant 1 should not contain 10 consecutive 0's
or 1's. The reasons for this criteria are that this key words are used
for the multiplication in the E-function and key words without these properties
would lead to weak keys for differential attacks. In the submission for
AES IBM suggests to use just 128 to 448 bit keys that are expanded to a
1280 bit key with the mentioned properties.
The key expansion routine uses the same operations (xor, shift and
table look-up) as the encryption / decryption. The pseudo code for the
key expansion routine that takes from 4 to 14 key words and produces a
valid 1280 bit MARS key can be found here.
Comparison with other AES Candidates
There are 4 other candidates for AES in the last round. All of them satisfy
the minimal requirements from NIST. So they are all 128 bit block ciphers
with variable key length from 128 bit to at least 192 bit. All designs
claim to be secure against all known attacks like differential, linear,
known plaintext or ciphertext and other attacks.
RC6 is the submission of MIT (Massachusetts Institute of Technology) and
the RSA-Laboratories [RC6-MIT-RSA] .
Similar to MARS it splits the 128 bit blocks into four words in the algorithm,
but the algorithm is designed in a way that you can easily change to two
64 bit words in newer architectures. RC6 is also a Feistel network. It
uses the same type of operations except from look-up tables and fixed rotations.
The algorithm is more flexible than MARS about blocksize and number of
rounds. The AES submission is optimized for 128 bit blocks and 20 rounds.
Several performance test showed that RC6 is slower than MARS for encryption
and for the key setup. But it uses less memory because there are no look-up
Rijndael is the submission of the Belgium Proton World Int. and the Katholieke
Universiteit Leuven, Belgium. This algorithm is quite different from MARS.
It works with Galois Field GF(128) arithmetic and handles the input blocks
as matrices of bytes. They define several operations to these matrices
as ByteSub, ShiftRow, MixColumn and AddRoundKey. For detailed information
about these operations consult [Rijndael99].
Several combinations of these operations define a round. Depending on the
key length which is in the range from 128 to 256 bits a fixed number of
rounds has to be executed. This cipher is not a Feistel network. Several
performance tests showed that Rijndael is about the same speed in encryption
and decryption as MARS. But the key expansion for keys of the same length
is significant slower.
Serpent is a submission from three universities (Cambridge University,
England; Technion, Haifa, Israel; University of Bergen, Norway) [Serpent]
. Therefore it's the only algorithm where no company stands behind. The
algorithm is pretty similar to DES, it uses permutations, xors, fixed rotations
and shifts and constant table look-up's. The first version of the algorithm
even used the same S-boxes as DES. The key can vary from 128 to 256 bit.
The algorithm works internally also with 4 words as RC6 and MARS. Performance
tests that the encryption of Serpent is about 25% faster than the MARS
encryption. But the key expansion is significant slower. An implementation
of Serpent also uses a lot of memory because of the look-up tables.
Twofish is the submission from a company called Counterpane. It is a 16
round Feistel cipher that works with key dependent 8x8 bit look-up
tables, 4 by 4 matrices over the Galois field GF(128), a pseudo-Hadamard
transform, permutations and rotations. The detailed description of these
functions can be found in [Twofish]. The
key length varies also from 128 bit to 256 bit as in most other AES candidates.
Performance tests showed that the encryption speed of Twofish is about
the same as for MARS, but the Twofish key setup is significant faster.
In February 2000 NIST published c and java code for all AES candidate ciphers.
All codes use a similar header defined by NIST. The c code is written in
a fashion that it is compileable with most c compilers on most platforms.
It could be optimized for each platform. This code is freeware and can
The fact that the code is free does not mean that also the algorithm is
free. Check the copyright statements on NIST's
MARS Module by IBM
The c code I used for my demoprogram consists of two files:
from this code I use the functions:
I don't use the so called highlevel functions to encrypt and decrypt byte
streams. I first wanted to use them to encrypt and decrypt text in my demo
program, but I run into some problems with this function and decided to
write my own chain encrypt and decrypt functions for my program.
mars_setup (Key expansion)
mars_encrypt (Encryption of a single block)
mars_decrypt (Decryption of a single block)
CGI Web Interface
The actual CGI program is installed on my COE account at OSU. To move it
to another location you have to follow these steps:
The demoprogram has the following functionality:
Change the CGIpath in the file 'Mars-cgi.c'.
Compile the cgi-file for the actual target machine. When you use GNU's
gcc compiler you can use the makefile I provided. For successful compilation
the files: Mars-cgi.c, Mars-ref.c and aes.h are used.
The program should never be called without a parameter. In a link to the
program provide at least the parameter Init=Init. Later the code provided
by the cgi-program will always call itself and makes sure that the parameters
The CGI program is mainly concerned with interpreting the user input and
providing the HTML output. There are three procedures that may be interesting
for cryptographic reasons. The functions doChainEncrypt and doChainDecrypt
replace the highlevel functions from IBM with which I had problems to make
them work. These functions provide the encryption of long bytestreams using
the ECB or CBC mode. The routines work with Big Endian byte ordering. The
other function is the one that creates a key when the user don't want to
provide one. This function initializes the random generator of the computer
with the actual system time and then combines each key word from 6 pseudo
random numbers from this generator.
You can provide or generate a key from 128 to 448 bit.
You can encrypt or decrypt a single datablock provided in HEX.
You can encrypt an ASCII text using ECB or CBC chaining mode. For CBC you
can provide or generate an IV. The result will be a bytestream in HEX.
You can decrypt a bytestream in HEX using ECB or CBC and reconstruct the
ASCII text from the encoded stream.
It won't be an easy decision to choose one of the finalists as AES. There
is no known weakness in all these algorithms, so other factors as performance,
needed hardware or flexibility must be used for the decision. MARS cipher
is for sure a good candidate. It has the largest available key length of
all of them and it is expandable to larger block sizes than 128 bit. Another
advantage of MARS is that it comes from a well known company that is in
this business for a long time which means they have a lot of experience
and have proven their trustworthiness.
||C.Burwick, D.Coppersmith, E.D'Avignon, R.Gennaro, S.Halevi, C.Jutla,
S.Matyas, L.O'Connor, M.Peyravian, D.Safford, N.Zunic, "MARS - a candidate
cipher for AES", IBM Corporation, September 1999. http://www.research.ibm.com/security/mars.pdf
||Shai Halevi, "Detailed discussion of the MARS "tweak" for Round 2",
IBM Corporation, Mai 1999. http://csrc.nist.gov/encryption/aes/round2/AESAlgs/MARS/mars-twk.txt
||Ronald L. Rivest, M.J.B. Robshaw, R. Sidney, Y.L. Yin, "The RC6 Block
Cipher", M.I.T. Laboratory for Computer Science,RSA Laboratories, http://csrc.nist.gov/encryption/aes/round2/AESAlgs/RC6/cipher.pdf
||Joan Daemen, Vincent Rijmen, "AES Proposal: Rijndael", Proton World
Int.l, Belgium, Katholieke Universiteit Leuven, Belgium, September
||Ross Anderson, Eli Biham, Lars Knudsen, "Serpent: A Proposal for the
Advanced Encryption Standard", Cambridge University, England; Technion,
Haifa, Israel; University of Bergen, Norway; http://csrc.nist.gov/encryption/aes/round2/AESAlgs/Serpent/Serpent.pdf
||Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall,
Niels Ferguson, "Two sh: A 128-Bit Block Cipher", Counterpane Systems,
University of California Berkeley, http://csrc.nist.gov/encryption/aes/round2/AESAlgs/Twofish/Twofish.pdf