From: (Michael Roe)
Newsgroups: sci.crypt.research

Subject: Re: SAFER K-64
Date: 1 Dec 1994 10:03:18 GMT
Organization: U of Cambridge Computer Lab, UK
Lines: 54
Sender: (sci.crypt.research co-moderator)
Message-ID: <3bk716$>
References: <3bi2jh$>
Reply-To: (Michael Roe)
X-Newsreader: NN version 6.5.0 #7 (NOV)

Anrew Haley writes:
> In _Fast Software Encryption_, James Massey proposes a block cipher
> which uses FFT-like permutations combined with 8 -> 8-bit S-boxes derived
> from the function n -> (45^n mod 257).
[text deleted]
> Is there any really strong reason for the chice of this function?
When I first looked at SAFER K-64, I was also worried about the relationships
between the function n -> (45^n mod 257) and modular addition.
In particular, I was worried that that this would cause the round functions
of SAFER K-64 to generate a group significantly smaller than S(2^64).
The experiments I have done so far seem to indicate that this fear was
unfounded; I have a cut-down version of SAFER that works on 4 bit nibbles
rather than 8-bit bytes, and I can prove that its round functions generate
the full symmetric group. (The full SAFER K-64 was too tough to analyse).
  [As has often been discussed on sci.crypt, the fact that an algorithm
   generates the symmetric group does NOT prove that it is
   cryptographically strong! However, this result is still interesting.]
In fact, I have an intuitive argument as to why the discrete log/exponential
function should be 'good' when combined in the right way with modular
  Consider stepping through the elements of GF(p) by adding one each time.
  At each step, if the step number is a quadratic residue, output a 0, else
  output a 1. I assert (without proof :-) ) that this sequence has 'good'
  statistical properties for most p.
  Now consider what the discrete log function is doing in SAFER K-64. If the
  input to the discrete log function is a quadratic residue, then the least
  significant bit of the output will be a 0, otherwise it will be a one.
  Thus, if my (unsubstantiated) claim about the quadratic residues of GF(p)
  is true, then least significant bit of the discrete log output will have
  'good' non-linearity with respect to the key mixing operation (modular
  A similar argumenr holds for all the bits of the discrete log output.
PS. There is a paper to presented at this year's K.U.Leuven Workshop on
Cryptographic Algorithms that may be relevant: ``On the need for
multipermutaions/Cryptanalysis of MD4 and SAFER'' by Serge Vaudenay.
In this paper, he breaks a variant of SAFER that uses a different function
in place of n -> (45^n mod 257). Thus, the exponential is not the worst
possible function that could have been used!