Path: illuminati.io.com!uunet!news.mathworks.com!hookup!ames!waikato!auckland. + ac.nz!news From: Serge.Vaudenay@ens.fr (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: crypt-submission@cs.aukuni.ac.nz (sci.crypt.research co-moderator) Approved: crypt-submission@cs.aukuni.ac.nz Message-ID: <3bk9v9$bs@net.auckland.ac.nz> References: <3bi2jh$drk@lyra.csx.cam.ac.uk> <3bk716$t0a@net.auckland.ac.nz> Reply-To: Serge.Vaudenay@ens.fr (Serge Vaudenay) NNTP-Posting-Host: cs13.cs.aukuni.ac.nz X-Newsreader: NN version 6.5.0 #7 (NOV) In article <3bk716$t0a@net.auckland.ac.nz>, mrr@cl.cam.ac.uk (Michael Roe) write s: |> 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: http://www.ens.fr/users/grecc/vaudenay/pub.html ftp://ftp.ens.fr/pub/reports/liens/liens-94-23.A4.dvi.Z --Serge