Path: illuminati.io.com!uunet!news.mathworks.com!hookup!ames!waikato!auckland.
+     ac.nz!news
From: mrr@cl.cam.ac.uk (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: crypt-submission@cs.aukuni.ac.nz (sci.crypt.research co-moderator)
Approved: crypt-submission@cs.aukuni.ac.nz
Message-ID: <3bk716$t0a@net.auckland.ac.nz>
References: <3bi2jh$drk@lyra.csx.cam.ac.uk>
Reply-To: mrr@cl.cam.ac.uk (Michael Roe)
NNTP-Posting-Host: cs13.cs.aukuni.ac.nz
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
addition:
 
  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
  addition).
 
  A similar argumenr holds for all the bits of the discrete log output.
 
Mike
 
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!