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!