MARS encryption algorithm

Reto Galli

ECE 575 Project - Winter 2000

Introduction
Mars Algorithm
         Operations
         Structure
         S-box design
         Key Expansion
Comparison with other AES Candidates
         RC6
         Rijndael
         Serpent
         Twofish
Software
         MARS Module by IBM
         CGI Web Interface
Conclusion
References

Introduction

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 works.

top

Mars 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.

Operations

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.
Fixed rotations
Data-dependent rotations: Data dependent rotations may lead to differential weaknesses. This problem is solved in MARS by combining these rotations with multiplications.
Multiplications: All multiplications in MARS are modulo 2³² 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 units.

Structure

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]

Forward mixing

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]

Cryptographic core

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 [MarsIBM99]

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 product 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 attacks.
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]

Backward mixing

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]

S-Box design

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.

top

Key Expansion

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.

top

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

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 tables.

Rijndael

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

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

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.

top

Software

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 be downloaded. The fact that the code is free does not mean that also the algorithm is free. Check the copyright statements on NIST's page.

MARS Module by IBM

The c code I used for my demoprogram consists of two files:

Mars-ref.c
aes.h

from this code I use the functions:

mars_setup (Key expansion)
mars_encrypt (Encryption of a single block)
mars_decrypt (Decryption of a single block)

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.

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:

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 are correct.

The demoprogram has the following functionality:

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.

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.

top

Conclusion

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.

top

References

[MarsIBM99]	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 or http://csrc.nist.gov/encryption/aes/round2/AESAlgs/MARS/mars.pdf
[TweakIBM99]	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
[RC6-MIT-RSA]	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
[Rijndael99]	Joan Daemen, Vincent Rijmen, "AES Proposal: Rijndael", Proton World Int.l, Belgium, Katholieke Universiteit Leuven, Belgium, September 1999, http://csrc.nist.gov/encryption/aes/round2/AESAlgs/Rijndael/Rijndael.pdf
[Serpent]	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
[Twofish]	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

Contents