The S-box in MARS
=================
It was recently brought to our attention that the S-box in MARS does 
not satisfy the "differential property number 4" from the submission 
document: 

"(4) S has {512 choose 2} distinct xor-differences and 2*{512 choose 2}
     distinct subtraction-differences."

In fact, there are a handful of xor- and subtraction-differences that 
appear twice in the S-box (see below). We identified a programming error 
in the code that was used to generate the S-box for MARS, in the part 
that checks for that specific property.  (The error is in the function 
fail() in the file sbox.c, where the order of parameters to the qsort() 
function is incorrect.) 

These repeated differences do not seem to have any effect on the security 
of MARS.  Indeed, our rationale for disallowing them was a feeling that 
not having repeated differences "ought to be a good thing", rather than 
a concrete security concern.  In particular, we note that: 

* The analysis of the strength of MARS in the submission paper never 
  uses the fact that there are no repeated differences in the S-box. 

* None of the known cryptanalysis attempts of MARS seems to benefit 
  from such repeated differences. 

* The repeated differences that actually appear in the S-box (see below), 
  do not seem to interact in any useful way with the rest of the cipher. 

We verified that the S-box satisfies all the other differential and 
linear requirements that are listed in the MARS submission document, 
including low linear correlations and no "useful differences" (e.g., 
differences with two zero bytes). 

We thank L. Burnett, G. Carter, E. Dawson and W. Millan for pointing 
out this discrepancy to us.  (We refer the reader to their paper 
"Efficient Methods for Generating MARS-like S-boxes", which will be 
presented at FSE 2000.) 


The repeated differences in the S-box are: 

xor-differences: 
----------------
   S[27]^S[101] = S[292]^S[360] = 0x117f1a43

and as a result also

   S[27]^S[292] = S[101]^S[360] = 0x2b05b22a
   S[27]^S[360] = S[101]^S[292] = 0x3a7aa869



subtraction differences:
------------------------
   S[13]-S[138] = S[364]-S[297] = 0x75082c89
   S[19]-S[168] = S[509]-S[335] = 0x0b7fc4bd
   S[49]-S[97]  = S[142]-S[392] = 0x725ca4be
   S[131]-S[333] = S[348]-S[211]= 0xc73689fe

and as a result also 

   S[13]-S[364] = S[138]-S[297] = 0x86dedc7c
   S[131]-S[348] = S[333]-S[211]= 0x22492124
   S[19]-S[509] = S[168]-S[335] = 0x9ce0ed93
   S[49]-S[142] = S[97]-S[392]  = 0x5d91f03a