MARS (ECB)

create

create("mars")

family

Feistel

options

--key

self-inverse

no

keyspace

2^128 to 2^448 keys

try it

ciphers mars "ATTACK AT DAWN" --key 0123456789abcdeffedcba9876543210

MARS is what IBM sent to the AES competition in 1998. Don Coppersmith was on the team, the same Coppersmith who had worked on DES more than twenty years before. It made the final five, got a tweak to its key schedule in August 1999, and lost to Rijndael in 2000 like everybody else.

The block is 16 bytes, read as four 32-bit words. Where Rijndael does everything with bytes, MARS mixes all the operations a 1998 CPU was good at: addition, subtraction, XOR, table lookups, multiplication and rotations by an amount that depends on the data. Thirty-two rounds in three layers:

• the key gets added to the four words, then eight forward mixing rounds run S-box lookups with no key at all,
• sixteen core rounds do the real work, each one with two key words, a multiplication and those data-dependent rotations,
• eight backwards mixing rounds mirror the first eight, and the last key words get subtracted.

In every round one word changes the other three and then all four rotate one place. The paper calls it a type-3 Feistel network, so it's filed under feistel here. The unkeyed layers on both ends are there so an attack has to peel them off first before it even sees the core.

The key is 32 to 112 hex digits in steps of 8, so 4 to 14 words, 128 to 448 bits. Words are little-endian, in the key and in the block, as in IBM's test vectors. Case doesn't matter and spaces are ignored. Text goes in as UTF-8 with PKCS#7 padding, ciphertext comes out as lowercase hex, and decode wants hex back. The mode is ECB, over 16-byte blocks like AES.

const mars = create("mars");
const key = "0123456789abcdeffedcba9876543210";
mars.encode("ATTACK AT DAWN", { key }).text; // "de839bee915b8cd4fc0243d93c4cae4b"
mars.decode("de839bee915b8cd4fc0243d93c4cae4b", { key }).text; // "ATTACK AT DAWN"

Where the S-box comes from

The S-box has 512 words, and nobody typed them in. Entry 5i + j is word j of SHA-1 over four words: 5i, then 0xb7e15162 and 0x243f6a88, which are the fraction digits of e and pi, then 0x02917d59. That last one is the only picked constant. IBM ran through about 2^26 candidates for a week and kept the one that gave the best S-box.

One more step, though. Any two entries in the same half that XOR to two or more zero bytes are too alike. So the first one of the pair gets multiplied by 3. It happens to nine entries.

That's how this package builds the table too, once, with its own small SHA-1, instead of shipping 4096 hex digits. The tests run IBM's table chains, 40 encryptions per key size fed into each other, and between them they touch every entry.

Checked against

IBM's known answers for the tweaked key schedule, the ones Crypto++ ships, cover 128, 192 and 256-bit keys. Crypto++ also takes 320, 384 and 448 bits. For 160 and 416, which Crypto++ refuses, the vectors come from CycloneCRYPTO, and the two agree everywhere else. Whole texts with padding are checked against Crypto++'s ECB_Mode<MARS>.

How strong is it

Nobody broke the full thing. The best attack in print is Kelsey and Schneier's "MARS Attacks!" from 2000. It keeps the mixing layers whole and cuts the core down to five rounds, 21 out of 32, and even that takes around 2^232 work. Sixteen core rounds are a long way off.

The block is 128 bits, so the Sweet32 collisions that hit Blowfish and Triple DES aren't a problem here.

Why ECB leaks

Same as every ECB here. Thirty-two As are two equal blocks, and they come out as two equal blocks:

mars.encode("A".repeat(32), { key }).text;
// 5ad31428f5ee9d935898dfa24bc60047 5ad31428f5ee9d935898dfa24bc60047 8d521a3c918480273dd03bf203d294d4

Spaces added to show the blocks. The last one is only padding.

A key that isn't 4 to 14 words of hex is an InvalidOptionError, a missing one a MissingOptionError. On decode, ciphertext that isn't whole 16-byte blocks of hex is a CipherError. A wrong key almost always breaks the padding, and that's a CipherError too. So are decrypted bytes that aren't UTF-8. It's a teaching implementation, not constant time. Puzzles and learning, not secrets.