## K-64.pdf

**PERFORMANCE EVALUATION OF SAFER K-64 **
**AND S-BOXES OF SAFER FAMILY **
**Ekrem Aras and Melek D. Yücel **
**Electrical Engineering Department of Middle East Technical University, 06531 Ankara, Türkiye. **
**e-mail: **[email protected]**, phone: 312 210 23 47, fax: 312 210 12 61 **
**Abstract − **If the characteristics of s-boxes of SAFER family of ciphers are examined for the
*criteria of strict avalanche, bit independence, and XOR table distribution, experiments show *
*that the “exponentiating” s-box has a weakness for the input difference of 128 (=10000000 2) *
*and the “logarithm-taking” s-box has a weakness for the input difference of 253 *
*(=111111012). However, since these experiments are performed by isolating the s-boxes from *
*the general structure, they do not necessarily indicate a weakness of the overall algorithm. We *
*propose a quick and rough test method, called the avalanche weight distribution criterion, to *
*evaluate the overall performance of block ciphers. We then apply this novel criterion and the *
*conventional strict avalanche criterion to SAFER K-64; and show that the algorithm passes *
*both tests successfully despite the specific weaknesses of its isolated s-boxes. *
**I. INTRODUCTION **
**S**ecure

**A**nd

**F**ast

**E**ncryption

**R**outine with a

**K**ey of length

**64** bits [1] (SAFER K-64) is a

symmetric (one-key) block cipher, which was designed by James L.Massey. SAFER K-64 is
the first designed cipher of the SAFER family of ciphers, which differ only in their key
schedules and in the number of rounds used.
The encryption and decryption blocks of SAFER family of ciphers contain two nonlinear
operations, called the “exponentiating box” and “logarithm-taking box”, which may have
significant effects on the strength of the entire system. If the “exponentiating” and “logarithm-
taking” boxes of SAFER family of ciphers are examined with respect to the criteria of
completeness, avalanche, strict avalanche (

*SAC*) and bit independence (

*BIC*), by considering
them isolated from the general structure of the cipher [2,3,4], experiments show that the
“exponentiating” s-box has a weakness for the input difference of 128 (=100000002 ) and the
“logarithm-taking” s-box has a weakness for the input difference of 253 (corresponding to
111111012 ). However, since these experiments are performed by isolating the boxes from the
general structure, these results do not indicate an overall weakness of the SAFER algorithms.
We propose a quick and rough test method, called the Avalanche Weight Distribution (

*AWD*)
criterion, to evaluate the overall performance of block ciphers [4,5,6]. We then apply this
novel criterion and the conventional strict avalanche criterion to SAFER K-64; and show that
the cryptographic algorithm passes both tests successfully.
In Sec.II, we introduce

**A**valanche

**W**eight

**D**istribution (

*AWD*) criterion after briefly

discussing the conventional criteria of completeness, avalanche, strict avalanche, bit
independence and

*X-OR* distribution. SAFER K-64 is described and corresponding s-box
results are summarized in Sec.III. The overall round by round performance of SAFER K-64 is
presented in terms of

*AWD* curves in Sec.IV, and with reference to the conventional strict
avalanche criterion in Sec.V. Conclusions are discussed in Sec.VI.

**II. CRYPTOGRAPHIC TEST CRITERIA **
Ideally, a block cipher should be hard to break, easy to implement, and fast to encrypt. In
1949, Shannon gave the fundamental theory of symmetric (secret-key) cryptosystems [7],
where he presented the principles of

*diffusion* and

*confusion*. Since then, these principles have
become the essential properties that block ciphers must have and methods of achieving good
diffusion and confusion have lied at the heart of block cipher design. Actually both principles
are defined in quite similar forms and try to achieve the same goal:

*hiding the statistical *
To design a cipher according to the principle of diffusion means that one designs it to ensure
that “

*the statistical structure of plaintext which leads to its redundancy is dissipated into long *
*term statistics*” [7]. Lai [8] states the principle of diffusion as follows: “

*for virtually every key, *
*the encryption function should be such that there is no statistical dependence between simple *
*structures in the plaintext and simple structures in the ciphertext and that there is no simple *
*relation between different encryption functions*”. In other words, every bit of the ciphertext
should depend on every bit of the plaintext and every bit of the key, i.e., the effect of changing
one bit in the plaintext or in the key should be sensed on all ciphertext bits. This ensures that
the statistics of the plaintext are dissipated within the ciphertext so that an attacker cannot
predict the plaintext that corresponds to a particular ciphertext, even after observing a number
of similar plaintexts and their corresponding ciphertexts.
To design a cipher according to the principle of confusion means that one designs it so as “

*to *
*make the relation between the simple statistics of ciphertext and the simple description of key *
*a very complex and involved one*” [7]. The principle of confusion is also stated [8] as follows:

*the dependence of the key on the plaintext and ciphertext should be so complex that *
We first describe the conventional test criteria which can be applied either to the overall
transformation describing a block cipher or to the isolated s-boxes of substitution permutation
networks. We then define our novel criterion of

** A**valanche

**W**eight

**D**istribution (

*AWD*) which

measures the overall performance roughly but quickly.

**II.1. Conventional Test Methods **
** 1) Completeness: **
The idea of completeness was introduced by Kam and Davida [9]. If a cryptographic
transformation is complete, then each ciphertext bit must depend on all of the plaintext bits.
Thus, if it were possible to find the simplest Boolean expression for each ciphertext bit in
terms of the plaintext bits, each of those expressions would have to contain all of the plaintext

**2) Avalanche Criterion: **
The idea of avalanche was introduced by Feistel [10]. For a given transformation to exhibit
the avalanche effect, an average of one half of the output bits should change whenever a single
input bit is complemented. In order to determine whether a given function

*f *:

*n*
the

*n* dimensional binary vector space into itself) satisfies this requirement, 2 plaintext pairs,

**P** and

** P***i*, such that

** P** and

** P***i* differ only in bit

*i *(

**P***i* =

** P** ⊕

**e***i*, and

**e***i * is the

*n*-bit unit vector with

a one in position

*i*) are used to calculate the 2 exclusive-or sums,

**C***d* =

*f* (

**P**) ⊕

*f* (

**P***i*). These

output difference vectors

** C***d* are referred to as avalanche vectors, whose elements are called

avalanche variables. If one half of the avalanche variables are equal to 1 for each

*i *in 1≤

*i *≤

*n*,
then the function

*f * has good avalanche effect.

**3) Strict Avalanche Criterion: **
The concepts of the completeness and the avalanche effect were combined by Webster and
Tavares [11] to define the

**S**trict

**A**valanche

**C**riterion (

*SAC*). If a cryptographic function is to

satisfy the strict avalanche criterion, then each output bit should change with a probability of
one half whenever a single input bit is complemented. Consider two input vectors which
differ only in bit

*i, *with the corresponding avalanche vector

**C***d* .

*f * meets the strict avalanche

criterion, if the probability that each bit in the avalanche vector

**C***d* is equal to 1 is one half

over the set of all possible input vectors

**P** and

**P***i* , for all values of

*i*. Therefore; completeness

and avalanche effect are necessary conditions if the strict avalanche criterion is to be met.
In addition,

*f *is said to satisfy

**M**aximum

**O**rder

**S**trict

**A**valanche

**C**riterion (

*MOSAC*) if for all

*j* such that 1≤

*j *≤

*n*, flipping any combination of one or more input bits changes output bit

*j*
Distance to

*SAC* and distance to

*MOSAC* are the measures of the closeness of the cipher
function

*f , * to

*SAC *and

*MOSAC* respectively. We define normalized distance to

*SAC* for the

*j*th avalanche variable as follows:
{

*D j ***P e**
*all*(

**P**,

**P **)

where

**e***i* is the n-bit unit vector with a 1 in position

*i*,

**P***d* is the input difference,

**C***d* [

*j*] is the

*j*th avalanche variable of the avalanche vector

**C**
*d*. If

*SAC* is satisfied perfectly, then

*DSAC *[
is 0 for all output bits; and in the worst case normalized distance
Similarly we define normalized distance to

*MOSAC* for the

*j*th avalanche variable as:

**P***d *=

**ä **}= 1

*all *(

**P **,

**P**⊕

**ä**)

where

**δ** is the

*n*-bit binary representation of any integer in [1, 2 −1], and the avalanche vector

*d* =

*f *(

**P**) ⊕

*f *(

**P** ⊕

**δ **). If

*MOSAC* is satisfied, then

*D*
In the worst case, the normalized distance

**4) Bit Independence Criterion: **
The idea of

**B**it

**I**ndependence

**C**riterion (

*BIC*) was introduced by Webster and Tavares [11].

For a given set of avalanche vectors generated by complementing a single plaintext bit, all
avalanche variables should be pairwise independent. Alternatively, consider two n-bit input
vectors which differ only in bit

*i*, with the corresponding avalanche vector

**C***d*. If

*f* meets the

bit independence criterion, the bits

*j* and

*k* in

**C***d* change independently for all

*i*,

*j*,

*k* (1≤

*j*,

*k *≤

*n*
with

*j *≠

*k*). In order to measure the degree of independence between a pair of avalanche
variables, their correlation coefficient

*ρ* (

**C***d* [

*j*],

* ***C***d* [

*k*]) is calculated. The cryptographic

function

*f *is said to satisfy

**M**aximum

**O**rder

**B**it

**I**ndependence

**C**riterion (

*MOBIC*) if the same

output bit independence holds whenever any combination of one or more input bits are
The correlation matrix

**B***BIC* and the maximum correlation matrix

using the correlation coefficient

*ρ* (

**C***d* [

*j*],

* ***C***d* [

*k*]) :

**P **=

**e **=

*ρ ***C**
Similarly, for the criteria of

*MOBIC*, the correlation coefficient is calculated for every pair of
avalanche variables, and correlation and maximum correlation matrices of size

*n*x

*n* are defined
=

**ä **=

*ρ ***C**
) (

*d*[

*j*] ,

*d *[

*k*]
) = max {

**B***MOBIC*( ,

where

**δ** is the

*n*-bit binary representation of any integer in the interval [1, 2 −1], and

**C***d* [

*j*] is

the

*j*th avalanche variable of the avalanche vector

**C***d* =

*f *(

**P**) ⊕

*f *(

**P** ⊕

**δ**).

**5) X-OR Table Distribution **
Differential cryptanalysis [13], which is a powerful cryptanalytic attack, requires knowledge
tables of substitution boxes (s-boxes). For an

*n*x

*n* s-box, the

*X-OR* table
has a size of 2 x 2 with its rows and columns indexed by 0, 1, 2, …, 2 −1. Position [

*i*,

*j*] in
the

*X-OR* table contains the number of input vectors:
{

**P** ∈{ ,0 }

*n*
:

*f *(

**P**) ⊕

*f *(

**P **⊕

**ç**
=

**ç**
such that 0 ≤

*i*,

*j *≤ 2 −1, and

**η**i and

**η**j are

*n*-bit binary representations of indices

*i* and

*j*.

** P** is the

input vector,

*f *(.) corresponds to the cryptographic function of the s-box, and the pair (

*i*,

*j*) is
called an input/output

*X-OR* pair. Differential cryptanalysis exploits such

*X-OR* pairs with
large

*X-OR* table entries. A cipher can be secured against differential cryptanalysis by
selecting s-boxes with low

*X-OR* table entries, ideally 0 or 2 (the only exception is the entry
(0, 0) which has the value of 2 ). The sum of the

*X-OR* table entries on each row is equal to 2 ,
which is the total number of input vector pairs (

**P**,

** P** ⊕

**η**i).

**II.2. Avalanche Weight Distribution Criterion **
We define the

*“Avalanche Weight Distribution (AWD) curve” *as the

*“histogram of the *
*Hamming weight of the ciphertext difference vector” *[4,5,6]. We then propose

*AWD* as a
simple criterion for fast and rough analysis of the diffusion and confusion properties
If the Avalanche Weight Distribution (

*AWD*) criterion measures the diffusion properties of
block ciphers [4] then we state the criterion as follows: Even for quite similar plaintext pairs
(

**P**1,

**P**2), histograms of the Hamming weight of the avalanche vectors should be completely

random. Hence,

*AWD* curves corresponding to all possible pairs of similar inputs should be
binomially distributed around

*n/*2 for a well diffused block cipher of blocklength

*n*.
If the

*AWD* criterion reveals the confusion properties of block ciphers [4] then we state the
criterion as follows: For all pairs of similar secret keys (

**K**1,

**K**2), histograms of the Hamming

weight of the differences of corresponding ciphertext pairs (

**C**1,

**C**2) should be binomially

distributed around

* n/2* for a well confused block cipher of blocklength

*n*.

**III. TEST RESULTS FOR SAFER S-BOXES **
**S**ecure

**A**nd

**F**ast

**E**ncryption

**R**outine with a

**K**ey of length 64 bits [1] (SAFER K-64)

is a symmetric (one-key) block cipher, which was designed by J. L. Massey. SAFER K-64 is a
byte-oriented block-enciphering algorithm. The block length is 8 bytes (64 bits) for plaintext
and ciphertext; the user-selected key is also 8 bytes (64 bits) in length. SAFER K-64 is the
first designed cipher of the SAFER family of ciphers consisting of SAFER K-64, SAFER K-
128, SAFER SK-64, SAFER SK-128, and SAFER SK-40. The block size of all the ciphers in
the SAFER family is 64 bits, while the key length is 40 or 64 or 128 bits as indicated in the
name of the cipher. The other ciphers in the SAFER family differ from SAFER K-64 only in
their key schedules and in the number of rounds used. The encryption round structure of
SAFER K-64 is shown in Figure 1. The operations labeled “45(.)” and “log45” in Figure 1 are
the “only nonlinear layers” of the cipher and they apply two different “highly nonlinear”
transformations to their inputs. These two operations are called the “exponentiating box” and
-taking box”, which can be considered as the s-boxes of SAFER family of ciphers.
They are used both in the encryption and decryption, but in different locations of the round
structures, since the encryption and decryption are slightly different. The s-boxes of SAFER
family of ciphers use the two operations defined by:
• the operation labeled “45(.)” in Figure1, which maps the byte input

* j *to the byte output
45j modulo 257 (except that this output is taken to be 0 if the modular result is 256,
• the operation labeled “log45” in Figure 1, which maps the byte input

* j *to the byte output
is log45(j) (except that this output is taken to be 128 if the input bit is

* j *= 0).

**Figure 1**: Encryption Round Structure of SAFER K-64

The encryption algorithm consists of

*r* rounds of identical transformations that are applied in
sequence to the plaintext, followed by an output transformation, to produce the final
ciphertext.

*r *= 6 is recommended but larger values of

*r* can be used if desired for even greater
security. Each round is controlled by two 8-byte subkeys and the output transformation is
We apply the conventional criteria discussed in Sec.II to SAFER s-boxes and summarize the

**III.1. Exponentiating S-Box **
**1) SAC and MOSAC: **
*j ***P **=

**e ** curves, given by (1), are depicted in Figure 2.

In the figure there are eight curves corresponding to input differences,

**e **, …,

**e **. If those

curves are merged into a single one by (2), the maximum of normalized distance to

*SAC* for
[

*j *, is found almost the same as the curve

*SAC *[ ] |

**P***d *=

**e **(= 128 )}

**Normalized Distance to SAC**
**Bit Position ***j *** of the Avalanche Vector**
**Figure 2:** {

*D*
*j ***P **=

**e ** versus

*j* Curves for the Exponentiating S-box

The normalized distance to

*MOSAC* values for all possible 255 input differences are calculated
by (3). Instead of drawing all these curves in the same figure, only the

*D *max
by (4), is depicted in Figure 3. Actually, this curve is also nearly the same as the curve
in Figure 2. The only difference is at the 6th avalanche variable and occurs
for the input difference of 137 (=100010012).

**Normalized Distance to MOSAC .**
**Bit Position ***j *** of the Avalanche Vector**
**Figure 3:** *D *max

versus

*j* Curve for the Exponentiating S–box
At all other avalanche variables, the maxima occur for the input difference of 128
(=100000002). It is observed that normalized distance to

*MOSAC* for all avalanche variables
other than the 6th are considerably high and

*SAC* completely fails at the 7th and 8th avalanche

*D*(

*MO*)

*SAC * is equal to 1.

** 2) BIC and MOBIC: **
matrices are calculated by (6) and (8) respectively as follows;
As seen from the matrices, the correlation coefficient between the 7th and any other avalanche
variable, and between the 8th and any other avalanche variable is ∞ (actually “undefined”
since the variance of the avalanche variable is 0 for the 7th and 8th bit positions of the
avalanche vector). A search over all correlation matrices defined by (7) shows that these
undefined rows correspond to an input difference of 128. Other values in the
are also quite close to 1, which means that the avalanche variables are highly correlated.

**3) X-OR Table Distribution: **
The

*X-OR* table is a matrix of size 256x256, whose entries are calculated by (9). If it is
divided into 8 pieces, so that each piece is 32x256, the maximum entry for each piece is as
1st piece: max. entry = 12 for (i, j) = (21, 184)
The maximum entry is 128 for the whole

*X-OR* table and occurs for the position [128, 253],
which means that when

**P***d* =12810, the avalanche vector

**C***d* =25310 occurs for 50% of the

overall input pairs since the highest possible value is 28=256. The

*X-OR* table distribution test
also verifies the previous tests in that the maximum table entry occurs for the input difference

**III.2. Logarithm-Taking S -Box **
**1) SAC and MOSAC: **
*j ***P **=

**e**
curves, given by (1), are depicted in Figure 4.
In the figure there are eight curves each obtained for one of the eight 8-bit unit vector input
differences,

**e **, …,

**e **. It is seen from Figure 4 that normalized distances to

*SAC* for all

avalanche variables are below 0.25, which is quite good. Those curves are merged into a
curve by (2), which takes the maximum of normalized distance to

*SAC* values
for each avalanche variable. However,

*D*max
curve is not depicted since (1) gives more
valuable information than (2) will give.
Bit Position

*j * of the Avalanche Vector

**Figure 4:** {

*D*
*j ***P **=

**e**
versus

* j *Curves for the Logarithm-Taking S-box
The normalized distance to

*MOSAC* values for all possible 255 input differences are calculated
by (3). Because of the difficulty in drawing all these curves, only

*D *max
(4) is depicted in Figure 5. In this figure, the maxima, which are about 0.5, all occur for the
input difference of 253 (=111111012) at all avalanche variables; hence, we obtain the same
Bit Position

* j * of the Avalanche Vector

**Figure 5:** *D *max

versus

* j* Curve for the Logarithm-Taking S-box

**2) BIC and MOBIC: **
matrices are calculated by (6) and (8) respectively as follows;

**3) X-OR Table Distribution: **
The

*X-OR* table is a matrix of 256 x 256, whose entries are calculated by (9). If it is
divided into 8 pieces, so that each piece is 32 x 256, the maximum entry for each piece is as
The maximum entry is 128 for the whole

*X-OR* table and occurs for the position [253, 128],
which means that when

**P***d* = 25310, the avalanche vector

**C***d* =12810 occurs for 50% of the

overall input pairs since the highest possible value is 28=256. The

*X-OR* table distribution test
also verifies the

*SAC* test in that the maximum table entry occurs for the input difference of
253, where

*SAC* test has its maxima.

**III.3. Comparison of Exponentiating and **
**Logarithm-Taking Boxes **
The exponentiating s-box has a weakness for the input difference of 128 (=100000002). In
order to compare the exponentiating s-box and the logarithm-taking s-box better in terms of
curves, given by Figure 3 and Figure 5 are sketched together in Figure 6.
Bit Position

* j * of the Avalanche Vector

**Figure 6:**
Curves for the Exponentiating and Logarithm-Taking S-boxes
As seen from the solid curve in Figure 6, none of the avalanche variables obey the

*SAC*; moreover, it is observed by comparing Figure 6 with Figure 2 that:
for all

*j*, except

* j *= 6. For the input difference of 128,
many of the avalanche variables have large distances to

*SAC*, and

*D*
one for

*j *= 7 and

*j *= 8; since the outputs of the exponentiating box always have the same bit
values in their 7th, and the complement bit values in their 8th bit positions.
For the same reason, the last two rows of
are also quite close to 1, which means that the avalanche variables are highly
correlated, and many of them are the same as the elements of

**B**
given by (5). The

*X-OR* table distribution test also verifies

*SAC* and

*BIC* tests in that the
maximum table entry occurs for the input difference of 128.
The logarithm-taking s-box has a weakness for the input difference of 253 (=111111012). The
dashed curve in Figure 6 corresponds to

*D*max
[

*j ***P**
for all j. However, normalized distance to

*MOSAC* for all

* j *is about 0.5, which is better than
the case of exponentiating s-box. Many elements of
entry of the

*X-OR* table also occurs for the input difference of 253, where the

*SAC* test has its
So, the logarithm-taking s-box seems to be have a weakness for the input difference of 253
and the exponentiating s-box has a weakness for the input difference of 128.
Finally, we should mention that since the results presented in this section are obtained by
isolating the substitution boxes from the general structure, they don’t indicate an overall
weakness of the SAFER algorithm. The overall performance of a specific algorithm from
SAFER family is investigated by two different criteria in the following two sections.

**IV. AWD CURVES OF SAFER K-64 **
We use the following test procedure [4] to examine the overall round by round diffusion
properties of SAFER K-64 by the criterion of avalanche weight distribution (

*AWD*):
§ A plaintext

**P** is chosen at random and the plaintext

**P***i* is calculated so that the difference

between

**P** and

**P***i* is

**e***i*, i.e.,

**P***i* =

**P** ⊕

**e***i* and

**P** and

**P***i* differ only in bit

*i*, where

**e***i* is a 64-bit

unit vector with a 1 in position

*i*, and

*i*∈ {1, 2, …, 64},
§

**P** and

**P***i* are submitted to

*r*-rounds of SAFER K-64 for encryption under a random key,

§ From the resultant ciphertexts

**C** and

**C***i*, the Hamming weight of the avalanche vector:

*wt*(

**C***d*) =

*wt*(

**C** ⊕

**C***i*) =

*j * is calculated, where

*j *∈ {0, 1, 2, …, 64},

§ The value of the

*j*th element of an avalanche weight distribution array of size 65 is

*AWD*_array [

*j*] =

*AWD*_array [

*j*] + 1,
§ The steps above are repeated 10000 times and the values in the avalanche weight
distribution array are sketched versus its index.
With the help of the test procedure explained above, 64 figures, each corresponding to a
different input difference

**P***d* =

**e***i* where i=1,., 64, are obtained for 1-round encryption of

SAFER K-64. Some of these curves seem to obey the binomial distribution around a mean
value of 32 and this is what we expect due to the

*AWD* criterion. However, some curves seem
to be far from being binomially distributed. These histograms are unacceptable since after a
single round of encryption the avalanche vectors may have very small Hamming weights such
as 1, 2, 4, 5 and 6. Hence, we concentrate on the worst diffusion curves of the first round and
increase the encryption round number to 2. The resultant curves after 2 rounds of encryption
are depicted in figures 7, 8 and 9 together with the former curves obtained after a single round
S A F E R K - 6 4 w i t h 1 - r o u n d e n c r y p t i o n
S A F E R K - 6 4 w i t h 2 - r o u n d e n c r y p t i o n

**Number of occurences of wt(Cd)**
**Figure 7:** *AWD* Curves of SAFER K-64 for

**e**57

**Number of occurences of wt(Cd)**
**Figure 8:** *AWD* Curves of SAFER K-64 for

**e**41

S A F E R K - 6 4 w i t h 1 - r o u n d o f e n c r y p t i o n
S A F E R K - 6 4 w i t h 2 - r o u n d o f e n c r y p t i o n

**Number of occurences of wt(Cd)**
**Figure 9: ***AWD* Curves of SAFER K-64 for

**e**49

It is observed from figures 7, 8, and 9 that when the number of encryption rounds is increased
to 2, the desired diffusion is achieved even for the worst

*AWD* curves of the first round.
Moreover, for more than 2 rounds of encryption we did not observe any distortion in the
binomial shape of the

*AWD* curves .
Hence, we conclude that the SAFER K-64 achieves the desired diffusion after at most the

**V. AVALANCHE CURVES OF SAFER K-64 **
We now use the following test procedure to examine the overall round by round
diffusion properties of SAFER K-64, by the conventional criterion of strict avalanche;
§ A plaintext

** P** is chosen at random and the plaintext

** P***i* is calculated so that the difference

between

** P** and

** P***i* is

**e***i*, i.e.,

** P***i* =

** P** ⊕

**e***i* and

** P** and

** P***i* differ only in bit

*i*, where

**e***i* is a 64-bit

unit vector with a 1 in position

*i*, and

*i*∈ {1, 2, …, 64},
§

**P** and

** P***i* are submitted to

*r*-rounds of SAFER K-64 for encryption under a random key,

§ From the resultant ciphertexts

**C** and

**C***i*, the avalanche vector

**C***d* = (

**C** ⊕

**C***i*) is calculated,

§ The 64 bit avalanche vector is summed up to an avalanche sum array, i.e.,
avalanche_sum_array = avalanche_sum_array +

**C***d*,

§ The steps above are repeated 10000 times and the values in the avalanche sum array are
With the help of the test procedure explained above, 64 avalanche curves each corresponding
to an input difference e

*i* where

* i *∈ {1,2,., 64} are obtained for

*r*-round encryption of SAFER
K-64. In figures 10 and 11 we give the worst case examples each showing 3 curves
corresponding to 1-round, 2-round and 6-round encryptions of SAFER K-64.
S A F E R K - 6 4 w i t h 1 - r o u n d e n c r y p t i o n
S A F E R K - 6 4 w i t h 2 - r o u n d e n c r y p t i o n
S A F E R K - 6 4 w i t h 8 - r o u n d e n c r y p t i o n

**Number of changes of avalanche variables**
**A v a l a n c h e v a r i a b l e**
**Figure 10:** Avalanche Curves of SAFER K-64 for

**e**2

S A F E R K - 6 4 w i t h 1 - r o u n d e n c r y p t i o n
S A F E R K - 6 4 w i t h 2 - r o u n d e n c r y p t i o n
S A F E R K - 6 4 w i t h 8 - r o u n d e n c r y p t i o n

**Number of changes of avalanche variable**
**A v a l a n c h e v a r i a b l e**
**Figure 11:** Avalanche Curves of SAFER K-64 for

**e**32

It is expected due to the strict avalanche criterion that an average of one half of the output bits
should change whenever a single input bit is complemented, i.e., avalanche_sum_array [

*i*] ≈
5000 for all

*i* since the number of trials is 10000.
However, it is observed from figures 10 and 11 that the number of changes is much different
from 5000 for most of the avalanche variables and the strict avalanche criterion completely
fails at some avalanche variables for 1-round encryption of SAFER K-64. It is also observed
that when the number of encryptions is increased to 2, the desired diffusion is achieved even
for the worst avalanche variables. Moreover, for 6-rounds of encryption the resultant
avalanche curves are very similar to the curves obtained for 2-rounds of encryption.
Hence, we conclude that the SAFER K-64 achieves the desired diffusion after at most the
second of its six rounds and note that this result is also verified by the tests applied for the

**VI. CONCLUSIONS **
Characteristics of s-boxes of SAFER family of ciphers in terms of

*SAC*,

*MOSAC*,

*BIC*,

*MOBIC* and

*X-OR* distributions, and overall diffusion properties of SAFER K-64 in terms of

*AWD* and

*SAC* are examined. Experiments show that although the logarithm-taking s-box
seems to be more resistive to the attacks than the exponentiating s-box, yet it has a weakness
for the input difference of 253 (=111111012) and the exponentiating s-box has a weakness for
the input difference of 128 (=100000002).
However, as far as two different criteria such as the quick and rough test method of

*AWD*, and
a more sensitive measure of strict avalanche curves indicate, the overall performance of
SAFER K-64 does not suffer from the weaknesses of its s-boxes and achieves the desired
diffusion after at most the second step of its six rounds. It is still challenging to direct further
work on this subject towards cryptanalysis of SAFER K-64 by making use of the sensitive
inputs of its exponentiating and logarithm-taking boxes.

**REFERENCES **
1. J. L. Massey, “SAFER K-64: A Byte-Oriented Block-Ciphering Algorithm

*”, Fast *
*Software Encryption – Proceedings of Cambridge Security Workshop*, Cambridge, U.K.,
LNCS 809, pp.1-17, Springer Verlag, 1994.
2. E. Aras and M. D. Yücel, “Examination of Substitution Boxes of SAFER”,

*Proc. *
*ELECO’99 Int. Conf. on Electrical & Electronics Engineering*, Bursa, Türkiye, pp.418-
3. E. Aras and M. D. Yücel, “Some Cryptographic Properties of Exponentiating and
Logarithm-Taking Boxes”,

*Proc.* *20’th Biennial Symp. on Communications, *
Univ., Kingston, Ontario, Canada, pp.69-73, May 2000.
4. E. Aras, “Analysis of Security Criteria for Block Ciphers”,

*M.Sc.Thesis, *Electrical &
Electronics Eng. Dept. of Middle East Technical University, Ankara, Türkiye, September
5. R. C. Acar, “Cryptographic Test Methods for Block Ciphers”,

*M.Sc.Thesis, *Electrical &
Electronics Eng. Dept. of Middle East Technical University, Ankara, Türkiye, December
6. M. D. Yücel and R. C. Acar, “Comparison of the Block Ciphers DES and IDEA”,

* Proc. *
*ELECO’99 Int. Conf. on Electrical & Electronics Engineering*, Bursa, Türkiye, pp.281-
7. C. E. Shannon, “Communication Theory of Secrecy Systems”,

*Bell Systems Technical *
*Journal, * Vol.28, pp.656-715, 1949.
8. X. Lai, “On the Design and Security of Block Ciphers”,

*ETH Series in Information *
*Processing,* Vol.1, Hartung-Gorre Verlag Konstanz, 1992.
9. J. B. Kam and G. I. Davida, “Structured Design of Substitution-Permutation Encryption
Networks”,

*IEEE Transactions on Computers*, Vol. C-28, No. 10, pp. 747-753, October
10. H. Feistel, “Cryptography and Computer

*Scientific American*, Vol. 228, No. 5,
11. A. F. Webster and S. E. Tavares, “On the Design of S-

*Proc. of CRYPTO’85*, Springer Verlag, New York, pp. 523-534, 1986.
12. S. Mister and C. M. Adams, “Practical S-Box Design”,

*SAC’96 – Third Annual Workshop *
*on Selected Areas in Cryptography*, Queen’s Univ., Kingston, Ontario, Canada, pp. 61-76,
13. E. Biham and A. Shamir

*, “*Differential Cryptanalysis of DES-like Cryptosystems”

*, *
*Journal of Cryptology, *Vol.4, No.1, pp.3-72, 1991.

**LIST OF FIGURES **
**Figure 1**: Encryption Round Structure of SAFER K-64

**Figure 2:** {

*D*
**P **=

**e ** versus

*j* Curves for the Exponentiating S-box

**Figure 3:** *D *max

versus

*j* Curve for the Exponentiating S–box

**Figure 4:** {

*D*
[

*j ***P **=

**e ** versus

* j *Curves for the Logarithm-Taking S-box

**Figure 5:** *D *max

versus

* j* Curve for the Logarithm-Taking S-box

**Figure 6:**
Curves for the Exponentiating and Logarithm-Taking S-boxes

**Figure 7:** *AWD* Curves of SAFER K-64 for

**e**57

**Figure 8:** *AWD* Curves of SAFER K-64 for

**e**41

**Figure 9: ***AWD* Curves of SAFER K-64 for

**e**49

**Figure 10:** Avalanche Curves of SAFER K-64 for

**e**2

**Figure 11:** Avalanche Curves of SAFER K-64 for

**e**32

Source: http://www.eee.metu.edu.tr/~yucel/PerformanceEvaluationSaferK64.pdf

REQUEST # 30680-S1-01 Pharmaceutical Prior Art Challenge – Montelukast Sodium Requesting Organization: SUBMIT PRIOR ART BY : February 20, 2009 MANAGER: Kevin C. Stark, Ph.D. SOLUTION PROVIDER HELP DESK EMAIL Opportunity $50,000 Reward for legitimizing the validity of patents based on technical literature research. If one or more references show a paten

Otto-von-Guericke - University of MagdeburgComputer Graphics and Interactive Systems Laboratory at the Department of Simulation and Graphics (ISG) Faculty of Computer Science Otto-von-Guericke-University of Magdeburg Universitätsplatz 2 D-39106 Magdeburg, Germany ℡ +49-391-67 18772 " +49-391-67 Rooms and Locations The lab occupies adequate lab space in its new Core Competence