From: (Serge Vaudenay)
Newsgroups: sci.crypt.research

Subject: Re: SAFER K-64
Date: 1 Dec 1994 10:53:29 GMT
Organization: Ecole Normale Superieure, Paris, France
Lines: 42
Sender: (sci.crypt.research co-moderator)
Message-ID: <3bk9v9$>
References: <3bi2jh$> <3bk716$>
Reply-To: (Serge Vaudenay)
X-Newsreader: NN version 6.5.0 #7 (NOV)

In article <3bk716$>, (Michael Roe) write
|> 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.
|> [...]
|> 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!
In this paper, it is shown that a necessary condition for the strength of the
substitution S is that the least significant bit is unbiased: is x is uniformly
distributed, we are ougth to have Expected( x xor S(x) mod 2 ) = 0.
It is precisely a property of all exponentiation which are permutation: we have
S(128)=-1 and S(x+y)=S(x)s(y) so S(x+128)=257-S(x), therefore, the bit
x xor S(x) mod 2 is perfectly unbiased.
From this point of view, it is amazing to notice that the regular property
S(x+y)=S(x)s(y) plays an important role in the good distribution of the substi-
tution function instead of weakening it.
It is now possible to retreive my technical report via WWW/ftp: