analiza criptografica asupra versiunilor serpent

8/2/2019 Analiza Criptografica Asupra Versiunilor Serpent

1/68

CRYPTOGRAPHIC ANALYSIS

OF

THE VERSIONS OF THE SERPENT CIPHER

CIGDEM ACAR

SEPTEMBER 2008


2/68


OF


A MASTERS GRADUATE PROJECT

SUBMITTED TO

THE DEPARTMENT OF CRYPTOGRAPHY

OF

THE MIDDLE EAST TECHNICAL UNIVERSITY

BY

CIGDEM ACAR

IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE

OF

MASTER SCIENCE

IN

THE DEPARTMENT OF CRYPTOGRAPHY

AUGUST 2008


3/68

Abstract


OF


Cigdem AcarM.Sc., Department of Cryptography

Supervisor: Assoc. Prof. Dr. Melek Diker YUCEL

September 2008, 60 pages

In this project, s-boxes of Serpent are evaluated according to its Linear Approx-

imation Tables (LAT) and Difference Distribution Tables (XOR). Then, All of the

outputs of Serpent Ciphers Versions are examined by NIST Statistical Test Suite forrandomness testing.

Finally, the randomness characteristics of Serpent Ciphers Versions are compared

with respect to each other for full and partial rounds. The overall performance of

the versions of the Serpent Cipher is found to be same, although there is a significant

difference in their s-boxes and linear transformation parts.

Keywords: Serpent-0, Serpent, Serpent-p, Serpent-p-ns, Linear Approximation

Table, Difference Distribution Table, randomness testing.

i


4/68

Contents

Page

Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i

Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii

List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv

Chapter

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.2 Boolean Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.3 Cryptographic Properties of Boolean Functions . . . . . . . . . . . . . 5

2.4 Linear Approximation Table (LAT) . . . . . . . . . . . . . . . . . . . . 6

2.5 Difference Distribution Table (Exclusive or-XOR) . . . . . . . . . . . . 8

3 Analysis of Serpents S-boxes . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3.2 Serpent Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3.2.1 Serpent-0 Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3.2.2 Serpent-1 (Serpent) Cipher . . . . . . . . . . . . . . . . . . . . . 10

3.2.3 Serpent-p and Serpent-p-ns Cipher . . . . . . . . . . . . . . . . 12

3.2.3.1 Description of Serpent-p . . . . . . . . . . . . . . . . . 12

3.2.3.2 Description of Serpent-p-ns . . . . . . . . . . . . . . . 13

3.3 S-boxes of Serpent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.4 Analysis of Serpents S-boxes . . . . . . . . . . . . . . . . . . . . . . . 14

3.4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.4.2 Results of LAT Tables of Serpents S-boxes . . . . . . . . . . . . 16

3.4.2.1 Properties of Serpents Linear Approximation Tables . 17

3.4.2.2 Observations on Serpents Linear Approximation Tables 18

3.4.3 Results of XOR Tables of Serpents S-boxes . . . . . . . . . . . 21

ii


5/68

3.4.3.1 Properties of Serpents Difference Distribution Tables . 21

3.4.3.2 Observations on Serpents Difference Distribution Tables 233.4.3.3 Observations for cryptanalysis . . . . . . . . . . . . . . 23

4 Randomness Testing of Serpent Ciphers Versions . . . . . . . . . . . . . . . 25

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.2 Randomness Testing Experimental Preparation . . . . . . . . . . . . . 25

4.3 Randomness Testing of the Perturbed Random Plaintext . . . . . . . . 28

4.4 Full Round Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.4.1 Full Round Testing For Serpent-0 . . . . . . . . . . . . . . . . . 29

4.4.2 Full Round Testing For Serpent-1 (Serpent) . . . . . . . . . . . 314.4.3 Full Round Testing For Serpent-p . . . . . . . . . . . . . . . . . 32

4.4.4 Full Round Testing For Serpent-p-ns . . . . . . . . . . . . . . . 33

4.5 Partial Round Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.5.1 Partial Round Testing For Serpent-0 . . . . . . . . . . . . . . . 34

4.5.2 Partial Round Testing For Serpent-1 (Serpent) . . . . . . . . . . 36

4.5.3 Partial Round Testing For Serpent-p . . . . . . . . . . . . . . . 38

4.5.4 Partial Round Testing For Serpent-p-ns . . . . . . . . . . . . . . 39

4.6 Comparison of Test Results . . . . . . . . . . . . . . . . . . . . . . . . 405 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

A Appendix A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

A.1 Linear Approximation Tables (LAT) of Serpents S-boxes . . . . . . . . 47

A.2 Difference Distribution Tables (XOR) of Serpents S-boxes . . . . . . . 52

B Appendix B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

B.1 Description of the Statistical Tests . . . . . . . . . . . . . . . . . . . . 57

iii


6/68

List of Tables

3.1 Serpent-1 and Serpent-p-ns S-box definitions . . . . . . . . . . . . . . 14

3.2 Serpent-0 and Serpent-ps S-box definitions . . . . . . . . . . . . . . . . 15

3.3 Parts of LAT Tables of the S-boxes with input/output sum weight of 1 17

3.4 Parts of LAT Tables of the S-boxes . . . . . . . . . . . . . . . . . . . . 19

3.5 A part of XOR Table of the S-boxes with input/output differences weight

of 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.6 Parts of XOR Tables of the S-boxes . . . . . . . . . . . . . . . . . . . . 22

3.7 A part of XOR Table of the S-box 0 . . . . . . . . . . . . . . . . . . . . 24

4.1 List of Statistical Tests Applied During Test Application . . . . . . . . 26

4.2 Parameter Adjustments for some of the Statistical Tests . . . . . . . . 27

4.3 Test Results of Perturbed Random Plaintext . . . . . . . . . . . . . . . 29

4.4 Test Results of Full Round Serpent-0s Output . . . . . . . . . . . . . . 30

4.5 Test Results of Full Round Serpent-1s Output . . . . . . . . . . . . . . 31

4.6 Test Results of Full Round Serpent-ps Output . . . . . . . . . . . . . . 32

4.7 Test Results of Full Round Serpent-p-nss Output . . . . . . . . . . . . 33

4.8 Test Results of Partial Round Serpent-0s Output . . . . . . . . . . . . 35

4.9 Test Results of Partial Round Serpent-1s Output . . . . . . . . . . . . 37

4.10 Test Results of Partial Round Serpent-ps Output . . . . . . . . . . . . 39

4.11 Test Results of Partial Round Serpent-p-ns Output . . . . . . . . . . . 40

4.12 Comparison of Test Results of Serpent Cipher Versions Full Round Out-

puts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.13 Comparison of Test Results of Serpent Cipher Versions Round 1 Outputs 414.14 Comparison of Test Results of Serpent Cipher Versions Round 2 Outputs 42

4.15 Comparison of Test Results of Serpent Cipher Versions Round 3 Outputs 43

A.1 LAT Table of the S-box 0 . . . . . . . . . . . . . . . . . . . . . . . . . 48

iv


7/68


A.3 LAT Table of the S-box 2 . . . . . . . . . . . . . . . . . . . . . . . . . 49A.4 LAT Table of the S-box 3 . . . . . . . . . . . . . . . . . . . . . . . . . 49





A.9 XOR Table of the S-box 0 . . . . . . . . . . . . . . . . . . . . . . . . . 52


A.11 XOR Table of the S-box 2 . . . . . . . . . . . . . . . . . . . . . . . . . 53A.12 XOR Table of the S-box 3 . . . . . . . . . . . . . . . . . . . . . . . . . 54





v


8/68

List of Abbreviations

AES . . . . . . . . . . . . . Advanced Encryption Standard

ASCII . . . . . . . . . . . American Standard Code for Information Interchange

DES . . . . . . . . . . . . . Data Encryption Standard

LAT . . . . . . . . . . . . . Linear Approximation Table

MOSAC . . . . . . . . . Maximum Order Strict Avalanche Criterion

NIST . . . . . . . . . . . . National Institute of Standards and Technology

SAC . . . . . . . . . . . . . Strict Avalanche Criterion

XOR ............. Exclusive or

XOR Table . . . . . . Distribution Difference Distribution Table

vi


9/68

Chapter 1

Introduction

For many applications, the Data Encryption Standard (DES) algorithm is not

suitable because of its too small key and inefficiency of its implementation. In order

to overcome this issue, the US National Institute of Standards and Technology has

issued a call for a successor algorithm which would be called the Advanced Encryption

Standard (AES). As a result, this intention culminated in five algorithms. One of those

algorithms was the Serpent Algorithm. This algorithm was better than DES algorithm

when compared with respect to their performance, key length and strength of s-boxes.

In this project, the cryptographic properties of the Serpents S-boxes are examined

by a program which has written in Java programming language. The cryptographic

properties of the Serpents S-boxes, its cryptographic strengths against the Differential

and Linear cryptanalysis attacks and randomness testing of the Serpent cipher versions

are given.

In the first chapter, a brief information about Boolean functions and their crypto-

graphic properties and also, an information about vector Boolean functions (S-boxes)

and their cryptographic properties such as Linear Approximation (LAT) and Difference

Distribution (Exclusive or-XOR) tables are given.

In the second chapter, a brief information about the Serpent Cipher, the Serpents

S-boxes is defined. Then, the results and observations of the cryptographic properties

of the Linear Approximation and Difference Distribution of the Serpents S-boxes are

explained.

The last chapter contains the observations of randomness testing of the outputs

of the versions of the Serpent Cipher by using NIST Statistical Test Suite [3]. The

tests are done using a code written in C programming language. In addition, normal

distribution statistical test results and graphics of Serpents outputs are also given in

1


10/68

this chapter. As a result, an intuition about randomness of the outputs are acquired.

2


11/68

Chapter 2

Preliminaries

2.1 Introduction

In this chapter, some basic concepts about Boolean functions and some crypto-

graphic properties of Boolean functions such as balance, nonlinearity, correlation immu-

nity, Linear Approximation Table (LAT) and Difference Distribution Table (Exclusive

or-XOR) are presented.

2.2 Boolean Functions

Let F2 denote the finite field with binary values and let Fn2 denote the vector space

of binary n-tuples over F2 with respect to addition and scalar multiplication .Definition 2.2.1. A Boolean Function f, is an F2-valued function defined on F

n2 ,

f : Fn2 F2.

Definition 2.2.2. A vector Boolean function, S(x) : Fn2 Fm2 , which maps n bits to

m bits, each entry of S(x) = (f1(x),...,fm()x)1xm is a Boolean function.

Definition 2.2.3. A Boolean function, which is in the form f(x) =n

i=1 wi xi c

where w = (w1,...,wn) Fn2 and c F2, is called an affine function. If c = 0, f(x) is

called a linear, denoted by lw(x) = w x.

Definition 2.2.4. The Hamming distance between two functions f(x) and g(x) is the

function

dH(f(x), g(x)) = #{x Fn2 |f(x) = g(x)}.

3


12/68

Definition 2.2.5. A Boolean function f(x) : Fn2 F2 is balanced if its truth table

consists of equal number of 0s and 1s.

Definition 2.2.6. The cross-correlation between f(x) and g(x) is the function

cf,g(d) =xFn

2

(1)f(x)(1)g(xd)

for all d Fn2 .

Definition 2.2.7. The autocorrelation function of f(x) is

rf(d) =xFn

2

(1)f(x)(1)f(xd)

for all d Fn2 .

Definition 2.2.8. The Walsh-Hadamard transform of the Boolean function f(x)

is

Wf(w) =xFn

2

(1)f(x)(1)wx

for all a Fn2 , the correlation between f(x) and lw(x) = w x . Furthermore, inverse

of this transform is,

(1)f(x) =1

2n

wFn

2

Wf(w)(1)wx

Then, we have (Wf(w0),...,Wf(w2n1))t = Hn ((1)

f(w0), ..., (1)f(w2n1))t where Hn

is the Sylvester-Hadamard matrix of order n defined by

H1 = 1 11 1

and H n = H1 Hn1 for n > 1.Using the definition of the Hamming distance and Walsh-Hadamard transform, we

4


13/68

get

xFn

2

(1)f(x)(1)g(x) =

2n dH(f(x), g(x))

+ dH(f(x), g(x))(1)

= 2n 2dH(f(x), g(x))

By replacing g(x) with lw(x), we can obtain

Wf(w) =xFn

2

(1)f(x)(1)lw(x) = 2n 2dH(f(x), lw(x)),

therefore

dH(f(x), lw(x)) = 2n1

Wf(w)

2.

2.3 Cryptographic Properties of Boolean Functions

Definition 2.3.1. (Nonlinearity) The nonlinearity of a Boolean function f(x) is

defined to be the distance of f(x) to the set of affine functions,

Nf = minw,cdH(f(x), (w x c))

= minw{dH(f(x), lw(x)), dH(f(x), lw(x))}

where lw(x) is a linear function and lw(x) = lw(x) 1.

Using the definition of nonlinearity and the Hamming distance,

Nf = mina{dH(f(x), lw), dH(f(x), lw)}

= mina{2n1

1

2xFn

2

(1)f(x)

(1)lw(x)

, 2n1

1

2xFn

2

(1)f(x)

(1)lw(x)

}

= 2n1 1

2maxwFn

2|Wf(w)|,

where Wf(w) is the Walsh-Hadamard transform of the Boolean function f(x).

5


14/68

Definition 2.3.2. (Correlation Immunity of a Boolean Function) A function is said

to be correlation immune of order t, denoted by CI(t), if for the Walsh-Hadamardtransform, it holds that Wf(w) = 0, for 1 wH(w) t, where wH(w) denote the

Hamming weight of w.

Definition 2.3.3. (Resiliency) The correlation immunity of order t and the property

balancedness together give the property resiliency of order t

Definition 2.3.4. (Propogation Characteristics of a Boolean function) A function is

said to satisfy the propagation criterion P C(k) of degree k, if the functions f(x)

f(x d) are balanced for all {d Fn2 |1 wH(d) k}.

Definition 2.3.5. (SAC) For a Boolean function f(x), if the autocorrelation function

rf(w) =

xFn2

(1)f(x)(1)f(x)w = 0 for all w Fn2 such that wH(w) = 1 satisfies

the SAC. Namely, Strict Avalanche Criterion, SAC corresponds propagation criterion

of order 1, P C(1) and maximum order strict avalanche criterion MOSAC is the same

thing as P C(n).

If a vector Boolean function S(x) : Fn2 Fn2 satisfy the Strict Avalanche Criterion,

the change of the i th input bit results in the change of the j th output exactly forhalf of the input vectors, so the probability that the j th output bit is complemented

is 12 .

2.4 Linear Approximation Table (LAT)

Linear cryptanalysis is a known plaintext attack that take the advantage of high

probability occurrences of linear expressions involving plaintext bits, ciphertext bits

and subkey bits. A complete enumeration of all linear approximations of a cipher givesLinear Approximation Table (LAT). Each element in the table represents the number

of matches between the linear equation represented in hexadecimal as Input Sum

and the sum of the output bits represented in hexadecimal as Output Sum minus

2n1. More formally, the definition for the elements of the LAT table follows.

6


15/68

Definition 2.4.1. Let x, y Fn2 and S(x) : Fn2 F

n2 is the vector Boolean function.

Each element of the Linear Approximation Table is defined as

LAT,Fn2

(, ) = #{x| S(x) = x} 2n1

= #{x| S(x) = l(x)} 2n1

= 2n dH( S(x), l(x)) 2n1

= 2n1 dH( S(x), l(x))

where is the row indices and is the column indices.

Using the distance between S(x) and l(x), we get

dH( S(x), l(x)) = 2n1

1

2WS(x)()

= 2n1 LAT,Fn2

and

LAT,Fn2{0} =

WS(x)()

2.

By combining nonlinearity and the linear approximation table (LAT), we obtain

Nf = 2n1 max,Fn

2{0}|LAT(, )|.

In addition,

LAT,Fn2{0} = |x| x = S(x)| 2

n1

Multiplying both sides with 12n

,

2nLAT,Fn2

= 2n|x| x = S(x)| 1

2

= P r{ x = S(x)} 1

2(2.1)

If x f(x) Bn(Booleanfunction) then,

7


16/68

2nLAT,Fn

2 = P r{ x = f(x)} 1

2

Wf() =xFn

2

(1)f(x)(1)x = |x|f(x) = x| |x|f(x) = x|

= 2|x|f(x) = x| 2n

|x|f(x) = x| = 2n1 +Wf()

2

2n|x|f(x) = x| =1

2+

2nWf()

2

P r{f(x) = x} =1

2+

2nWf()

2=

1

2+

LAT,Fn2

2n

where P r is the probability.

2.5 Difference Distribution Table (Exclusive or-XOR)

Differential cryptanalysis is a chosen plaintext attack, which uses the high prob-

ability occurrences of plaintext differences and differences into the last round of the

cipher. The attacker examine the differential characteristics, where differential charac-

teristic is a sequence of input and output differences to the rounds so that the output

difference from one round corresponds to the input difference for the next round. For

finding differential characteristic, the difference distribution table (XOR) is generated.

Definition 2.5.1. Let S(x) : Fn2 Fn2 is a vector Boolean function with x, y F

n2 .

Let two inputs be X and X with the corresponding outputs Y and Y, respectively.

The input difference is X = XX and the output difference Y = YY. Then

an element of the XOR table defined by

XOR(X, Y) = #{X|S(X) S(XX) = Y}.

Each element of the table represents the number of occurrences of the corresponding

8


17/68

output difference Y value given the input difference X.

Remark 2.5.2. (Properties of XOR table)

1. XOR(X = 0, Y = 0) = 2n

2.

Fn2

XOR(, ) = 2n

3. For an n n and one to one s-box mapping XOR(, 0) = 0, = 0

Definition 2.5.3. The differential uniformity parameter, , is

maxX,Y=0XOR(X, Y)

If the differential uniformity is large, then the security of the cipher against differ-

ential cryptanalysis is low.

9


18/68

Chapter 3

Analysis of Serpents S-boxes

3.1 Introduction

In this chapter, the cryptographical results of Serpents S-boxes are evaluated ac-

cording to the Difference Distribution (XOR) and Linear Approximation tables (LAT)

.

In the first section, brief descriptions of the versions of the Serpent Cipher are

given. In the second section, the summary of the generation of Serpents S-boxes will

be given. The last section presents the analysis of Serpents S-boxes.

3.2 Serpent Cipher

3.2.1 Serpent-0 Cipher

The Serpent-0 is the first version of the Serpent Cipher. Serpent-0 use the S-boxes

from DES. Algorithm was fast as DES and yet more secure than three-key triple-DES,

provided a 192 or 256 bit key was selected. After strengthening the algorithm and

improving its performance, a candidate for AES, the Serpent-1, more briefly, Serpent

was introduced.

3.2.2 Serpent-1 (Serpent) Cipher

Serpent is a 32-round substitution permutation network (SPN) operating on four

32-bit words, thus with block size of 128 bits.

10


19/68

The indices of the bits are counted from 0 to bit 31 for one 32-bit word, 0 to 127

for 128-bit blocks and 0 to 255 for 256-bit keys.Serpent encrypts a 128-bit plaintext P to a 128-bit ciphertext C in 32 rounds with

33 subkeys K0,...,K32.

The cipher consist of:

- an initial permutation IP (no cryptographic significance)

- 32 rounds

- a key mixing operation

- a pass through S-boxes

- a linear transformation

In the last round, this linear transformation is replaced by an additional key

mixing operation

- a final permutation FP (no cryptographic significance)

The following equations describes the operations of the cipher formally:

B0 : = IP(P)

Bi+1 : = Ri(Bi)

C : = F P(B32)

where P is the plaintext, C is the ciphertext and

Ri(X) = L(Si(X Ki)) i = 0, ..., 30

Ri(X) = Si(X Ki) K32 i = 32

11


20/68

3.2.3 Serpent-p and Serpent-p-ns Cipher

The two variants of Serpent:

1. Serpent with the rotation linear transformation and the S-boxes of Serpent-0

(derived from the S-boxes of DES). This variant is called Serpent-p.

2. Serpent with the rotation linear transformation and the new S-boxes of Serpent-1.

This variant is called Serpent-p-ns.

3.2.3.1 Description of Serpent-p

Serpent-p encrypts 128-bit blocks under keys of 128, 192 and 256 bits. Given a

plaintext - P:

B0 = IP(P)

Bi+1 = Ri(Bi)

C = IP1(B64)

Ri = Roti(Si(X Ki)) i = 0, ..., 62

Ri(X) = Si(X Ki) K64 i = 63

After each of the 64 rounds , we use Roti, which is a set of rotations defined as

(0, 1, 3, 7) for even is and (0, 5, 13, 22) for odd is. This means that for even is the first

bit in each nibble is rotated to the left by 0 nibbles, the second by 1 (eg., from nibble

3 to nibble 4), etc.

In each round the same s-box is used 32 times, while different s-boxes are used in

the various rounds. The s-boxes are derived from the S-boxes of DES, giving 32 s-boxesin total.

Serpent-p uses the key schedule of Serpent (Serpent-1).

12


21/68

3.2.3.2 Description of Serpent-p-ns

Serpent-p-ns is defined as a variant of Serpent-p with the following modifications:

1. Serpent-p-ns uses the same s-boxes as Serpent-1.

2. Serpent-p-ns has 32 rounds. Therefore in the encryption process i is between 0 to

31, and in the key schedule algorithm i is between 0 to 32. Also for Serpent-p-ns

n(i) = (3 i) mod 8.

Therefore, Serpent-p-ns differs from Serpent-1 only in the linear transformation.

3.3 S-boxes of Serpent

For many applications, the Data Encryption Standard (DES) algorithm is not

much secure with its too small 56-bit key. Although triple-DES can solve the key

length problem, DES is inefficient for hardware encryption.

Serpent cipher is an efficient algorithm and uses the s-boxes which are generated

from the S-boxes of DES, but much more secure than the S-boxes of DES.

The Serpent cipher has 8 s-boxes with dimension 4 4 for each.The S-boxes of Serpent were generated in the following algorithm:

index :=0

repeat

currentsbox := index modulo 32

for i:=0 to 15 do

j := sbox[(currentsbox+1) modulo 32][serpent[i]];

swapentries(sbox[currentsbox][i],sbox[currentsbox][j]);

if sbox[currentsbox][.] has the desired properties, save it;index := index + 1;

until 8 S-boxes have been generated

In the algorithm, a matrix with 32 arrays each with 16 entries was used. The

array sbox[.][.] contains 32 rows of the DES S-boxes. The array serpent[.] contains

13


22/68

the least significant four bits of each of the 16 ASCII characters in the expression

sboxesforserpent. The function swapentries swaps the elements of the array sbox.

Table 3.1: Serpent-1 and Serpent-p-ns S-box definitionsOutput

Input S0 S1 S2 S3 S4 S5 S6 S70 3 15 8 0 1 15 7 11 8 12 6 15 15 5 2 132 15 2 7 11 8 2 12 153 1 7 9 8 3 11 5 04 10 9 3 12 12 4 8 14

5 6 0 12 9 0 10 4 86 5 5 10 6 11 9 6 27 11 10 15 3 6 12 11 118 14 1 13 13 2 0 14 79 13 11 1 1 5 3 9 4

10 4 14 14 2 4 14 1 1211 2 8 4 4 10 8 15 1012 7 6 0 10 9 13 13 913 0 13 11 7 14 6 3 314 9 3 5 5 7 7 10 515 12 4 2 14 13 1 0 6

3.4 Analysis of Serpents S-boxes

3.4.1 Introduction

The resistance of the block ciphers to attacks depend on their diffusion and confu-

sion properties. Diffusion is the property that each of plaintext equally has to appear

in the ciphertext. Confusion is the property that the relation between plaintexts and

ciphertexts has to be complex enough. It means that confusion comes with nonlinearity

property. The overall nonlinearity of the cipher is ensured by the s-boxes of the cipher.

In this chapter, we examine the resistance to Linear cryptanalysis and Differential

cryptanalysis attacks of Serpent cipher. We constitute the Linear Approximation (LAT

14


23/68

Table 3.2: Serpent-0 and Serpent-ps S-box definitionsS0 14 , 4 , 13 , 1 , 2 , 15 , 11 , 8 , 3 , 10 , 6 , 12 , 5 , 9 , 0 , 7S1 0 , 15 , 7 , 4 , 14 , 2 , 13 , 1 , 10 , 6 , 12 , 11 , 9 , 5 , 3 , 8S2 4 , 1 , 14 , 8 , 13 , 6 , 2 , 11 , 15 , 12 , 9 , 7 , 3 , 10 , 5 , 0S3 15 , 12 , 8 , 2 , 4 , 9 , 1 , 7 , 5 , 11 , 3 , 14 , 10 , 0 , 6 , 13S4 15 , 1 , 8 , 14 , 6 , 11 , 3 , 4 , 9 , 7 , 2 , 13 , 12 , 0 , 5 , 10S5 3 , 13 , 4 , 7 , 15 , 2 , 8 , 14 , 12 , 0 , 1 , 10 , 6 , 9 , 11 , 5S6 0 , 14 , 7 , 11 , 10 , 4 , 13 , 1 , 5 , 8 , 12 , 6 , 9 , 3 , 2 , 15S7 13 , 8 , 10 , 1 , 3 , 15 , 4 , 2 , 11 , 6 , 7 , 12 , 0 , 5 , 14 , 9S8 10 , 0 , 9 , 14 , 6 , 3 , 15 , 5 , 1 , 13 , 12 , 7 , 11 , 4 , 2 , 8S9 13 , 7 , 0 , 9 , 3 , 4 , 6 , 10 , 2 , 8 , 5 , 14 , 12 , 11 , 15 , 1S10 13 , 6 , 4 , 9 , 8 , 15 , 3 , 0 , 11 , 1 , 2 , 12 , 5 , 10 , 14 , 7S11 1 , 10 , 13 , 0 , 6 , 9 , 8 , 7 , 4 , 15 , 14 , 3 , 11 , 5 , 2 , 12S12 7 , 13 , 14 , 3 , 0 , 6 , 9 , 10 , 1 , 2 , 8 , 5 , 11 , 12 , 4 , 15S13 13 , 8 , 11 , 5 , 6 , 15 , 0 , 3 , 4 , 7 , 2 , 12 , 1 , 10 , 14 , 9S14 10 , 6 , 9 , 0 , 12 , 11 , 7 , 13 , 15 , 1 , 3 , 14 , 5 , 2 , 8 , 4S15 3 , 15 , 0 , 6 , 10 , 1 , 13 , 8 , 9 , 4 , 5 , 11 , 12 , 7 , 2 , 14S16 2 , 12 , 4 , 1 , 7 , 10 , 11 , 6 , 8 , 5 , 3 , 15 , 13 , 0 , 14 , 9S17 14 , 11 , 2 , 12 , 4 , 7 , 13 , 1 , 5 , 0 , 15 , 10 , 3 , 9 , 8 , 6

S18 4 , 2 , 1 , 11 , 10 , 13 , 7 , 8 , 15 , 9 , 12 , 5 , 6 , 3 , 0 , 14S19 11 , 8 , 12 , 7 , 1 , 14 , 2 , 13 , 6 , 15 , 0 , 9 , 10 , 4 , 5 , 3S20 12 , 1 , 10 , 15 , 9 , 2 , 6 , 8 , 0 , 13 , 3 , 4 , 14 , 7 , 5 , 11S21 10 , 15 , 4 , 2 , 7 , 12 , 9 , 5 , 6 , 1 , 13 , 14 , 0 , 11 , 3 , 8S22 9 , 14 , 15 , 5 , 2 , 8 , 12 , 3 , 7 , 0 , 4 , 10 , 1 , 13 , 11 , 6S23 4 , 3 , 2 , 12 , 9 , 5 , 15 , 10 , 11 , 14 , 1 , 7 , 6 , 0 , 8 , 13S24 4 , 11 , 2 , 14 , 15 , 0 , 8 , 13 , 3 , 12 , 9 , 7 , 5 , 10 , 6 , 1S25 13 , 0 , 11 , 7 , 4 , 9 , 1 , 10 , 14 , 3 , 5 , 12 , 2 , 15 , 8 , 6S26 1 , 4 , 11 , 13 , 12 , 3 , 7 , 14 , 10 , 15 , 6 , 8 , 0 , 5 , 9 , 2S27 6 , 11 , 13 , 8 , 1 , 4 , 10 , 7 , 9 , 5 , 0 , 15 , 14 , 2 , 3 , 12S28 13 , 2 , 8 , 4 , 6 , 15 , 11 , 1 , 10 , 9 , 3 , 14 , 5 , 0 , 12 , 7

S29 1 , 15 , 13 , 8 , 10 , 3 , 7 , 4 , 12 , 5 , 6 , 11 , 0 , 14 , 9 , 2S30 7 , 11 , 4 , 1 , 9 , 12 , 14 , 2 , 0 , 6 , 10 , 13 , 15 , 3 , 5 , 8S31 2 , 1 , 14 , 7 , 4 , 10 , 8 , 13 , 15 , 12 , 9 , 0 , 3 , 5 , 6 , 11

15


24/68

) and Difference Distribution (XOR) tables of the S-boxes of Serpent and give the

results about the nonlinearity and resistance of Serpents S-boxes.

3.4.2 Results of LAT Tables of Serpents S-boxes

For each of the S-boxes of Serpent, the Linear Approximation table (LAT) is a

matrix of size 16 16. It means that each s-box Si(x) : Fn2 F

n2 where n = 4. The

elements of the LAT table are calculated by

LAT,Fn2

(, ) = #{x| x = S(x)} 2n1 (sec 2.4)

The full Linear Approximation tables (LAT) of the S-boxes of Serpent will be given

in the first part of Appendix A in the document.

Nonlinearity property of each of s-box can be computed by the equation,

Nf = 2n1 max,Fn

2{0}|LAT(, )|.

According to the results, each of LAT tables of s-boxes of Serpent have maximum

value is equal to 4 except the element at the intersection of the first row and first

column (LAT(0, 0)). Hence the nonlinearity of each s-box can be computed likely,

Nf = 2n1 max,Fn

2{0}|LAT(, )|.

for n = 4 and max,Fn2{0}|LAT(, )| = 4,

Nf = 241 4 = 4.

It can be seen from the LAT tables of s-boxes that each linear characteristic has aprobability in the range 1

2 1

4.

16


25/68

Table 3.3: Parts of LAT Tables of the S-boxes with input/output sum weight of 1

S-box 0 S-box 11x 2x 4x 8x 1x 2x 4x 8x

1x -2 -2 -2 0 1x -2 -2 0 +22x +2 -2 0 0 2x -2 +2 0 -24x 0 0 0 0 4x 0 -2 0 -28x -2 -2 +2 0 8x 0 0 0 0


1x 0 0 0 0 1x +2 0 0 02x 0 +2 +2 0 2x -2 +2 0 -2

4x 0 +2 -2 0 4x 0 +2 +2 08x 0 -2 0 -2 8x 0 0 +2 -2


1x 0 +2 +2 0 1x 0 0 -2 02x 0 +2 0 0 2x 0 0 -2 +24x 0 0 +2 +2 4x 0 -2 +2 08x 0 0 +2 0 8x 0 0 0 -2


1x +2 0 -2 -2 1x -2 0 -2 02x 0 0 0 0 2x -2 +2 0 04x -2 0 -2 0 4x 0 +2 -2 08x +2 0 -2 +2 8x 0 0 +2 -2

3.4.2.1 Properties of Serpents Linear Approximation Tables

The LAT distributions of subsets with weight 1 can be observed from Table 3.3

(full LAT distributions of S-boxes is in Appendix LAT Tables).

It can be seen from the tables with weight 1 input and output sums, there are only

three values (2, 0, +2), so a linear relation between one single bit in the input and

one single bit in the output has a probability in the range 12 1

8. These probabilities

are low for Linear cryptanalysis.

On the other hand, there are some weakness of the LAT tables. For example, for

17


26/68

some input sum values give a value only for 4 output sum values with probability bias

14 . Then, other output sum values are 0.

3.4.2.2 Observations on Serpents Linear Approximation Tables

These observations of LAT tables can be used for linear cryptanalysis of Serpent.

1. For the LAT Table of S-Box 0, input sum 4x = (0100)2 give values only for

output sums Cx = (1100)2, Dx = (1101)2, Ex = (1110)2, Fx = (1111)2 and input

sum 9x = (1001)2 give values only for output sums5x = (0101)2, 6x = (0110)2, Cx = (1100)2, Fx = (1111)2.


output sums 6x = (0110)2, 7x = (0111)2, Cx = (1100)2, Dx = (1101)2 and input

sum Bx = (1011)2 give values only for output sums

1x = (0001)2, 2x = (0010)2, 8x = (1000)2, Bx = (1011)2.


output sums 3x

= (0011)2

, 5x

= (0101)2

, Bx

= (1011)2

, Dx

= (1101)2

and input

sum 7x = (0111)2 give values only for output sums

2x = (0010)2, 6x = (0110)2, 8x = (1000)2, Cx = (1100)2.

4. For the LAT Table of S-Box 3, input sum Fx = (1111)2 give values only for

output sums 1x = (0001)2, 3x = (0011)2, 4x = (0100)2, 6x = (0110)2.

5. For the LAT Table of S-Box 4, input sum Bx = (1011)2 give values only for

output sums 4x = (0100)2, 5x = (0101)2, 8x = (1000)2, 9x = (1001)2.

6. For the LAT Table of S-Box 5, input sum Bx = (1011)2 give values only foroutput sums 2x = (0010)2, 3x = (0011)2, 4x = (0100)2, 5x = (0101)2.


output sums 3x = (0011)2, 6x = (0110)2, Ax = (1010)2, Fx = (1111)2 and input

18


27/68

Table 3.4: Parts of LAT Tables of the S-boxesA part of LAT Table of the S-box 0

0x 1x 2x 3x 4x 5x 6x 7x 8x 9x Ax Bx Cx Dx Ex Fx4x 0 0 0 0 0 0 0 0 0 0 0 0 +4 -4 -4 -49x 0 0 0 0 0 +4 -4 0 0 0 0 0 +4 0 0 +4

A part of LAT Table of the S-box 10x 1x 2x 3x 4x 5x 6x 7x 8x 9x Ax Bx Cx Dx Ex Fx

3x 0 0 0 0 0 0 +4 -4 0 0 0 0 -4 -4 0 0Bx 0 -4 -4 0 0 0 0 0 -4 0 0 +4 0 0 0 0


6x 0 0 0 -4 0 +4 0 0 0 0 0 -4 0 -4 0 07x 0 0 +4 0 0 0 -4 0 -4 0 0 0 -4 0 0 0


Fx 0 +4 0 -4 +4 0 +4 0 0 0 0 0 0 0 0 0

A part of LAT Table of the S-box 4

0x 1x 2x 3x 4x 5x 6x 7x 8x 9x Ax Bx Cx Dx Ex FxBx 0 0 0 0 -4 -4 0 0 +4 -4 0 0 0 0 0 0


Bx 0 0 -4 +4 -4 -4 0 0 0 0 0 0 0 0 0 0


9x 0 0 0 +4 0 0 +4 0 0 0 -4 0 0 0 0 +4Bx 0 -4 0 0 +4 0 0 0 0 -4 0 0 -4 0 0 0

A part of LAT Table of the S-box 7

0x 1x 2x 3x 4x 5x 6x 7x 8x 9x Ax Bx Cx Dx Ex Fx7x 0 0 0 0 +4 +4 0 0 +4 -4 0 0 0 0 0 0

19


28/68

sum Bx = (1011)2 give values only for output sums

1x = (0001)2, 4x = (0100)2, 9x = (1001)2, Cx = (1100)2.


output sums 4x = (0100)2, 5x = (0101)2, 8x = (1000)2, 9x = (1001)2.

20


29/68

3.4.3 Results of XOR Tables of Serpents S-boxes

For each of the S-boxes of Serpent, the Difference Distribution table (XOR) is a

matrix of size 16 16. It means that each s-box Si(x) : Fn2 F

n2 where n = 4. The

elements of the XOR table are calculated by

XOR(X, Y) = #{X|S(X) S(XX) = Y}.(Section2.5)

The full Difference Distribution tables (XOR) of the S-boxes of Serpent will be

given in the second part of Appendix A in the document.

The differential uniformity parameter, , is

maxX,Y=0XOR(X, Y)(Definition2.5.3)

All Difference Distribution (XOR) tables have maximum value is 4 except the ele-

ment at the intersection of the first row and first column (XOR(X = 0, Y = 0)),

then the differential uniformity, of each s-boxes of Serpent is

maxX,Y=0XOR(X, Y) = 4.

It can be seen from the XOR tables of s-boxes that each differential characteristic

has a probability of at most 14

.

3.4.3.1 Properties of Serpents Difference Distribution Tables

Table 3.5 shows the XOR distributions of input and output differences with weight

1 for each s-boxes of Serpent, (the full XOR tables of S-box in Appendix A.2).

As a result, for each s-boxes of Serpent, a one-bit input difference will never lead

to a one-bit output difference.

21


30/68

Table 3.5: A part of XOR Table of the S-boxes with input/output differencesweight of 1

1x 2x 4x 8x1x 0 0 0 02x 0 0 0 04x 0 0 0 08x 0 0 0 0

Table 3.6: Parts of XOR Tables of the S-boxesA part of XOR Table of the S-box 0

0x 1x 2x 3x 4x 5x 6x 7x 8x 9x Ax Bx Cx Dx Ex Fx4x 0 0 0 0 0 0 0 0 0 4 4 0 0 4 4 0Dx 0 0 0 4 0 0 0 4 4 0 0 0 0 0 0 4

A part of XOR Table of the S-box 10x 1x 2x 3x 4x 5x 6x 7x 8x 9x Ax Bx Cx Dx Ex Fx

4x 0 0 0 0 0 0 4 4 0 0 0 0 4 4 0 0Fx 0 4 0 0 0 0 0 0 0 0 0 4 0 0 4 4


4x 0 0 0 0 0 0 4 0 0 0 4 4 0 4 0 0


Fx 0 0 0 0 0 4 0 4 4 0 0 0 0 0 0 4

22


31/68

3.4.3.2 Observations on Serpents Difference Distribution Tables

These observations are the result of XOR tables of Serpent.

1. For the XOR Table of S-Box 0, input difference 4x = (0100)2 give values only

for output differences 9x = (1001)2, Ax = (1010)2, Dx = (1101)2, Ex = (1110)2

and input difference Dx = (1101)2 give values only for output differences

3x = (0011)2, 7x = (0111)2, 8x = (1000)2, Fx = (1111)2.

2. For the LAT Table of S-Box 1, input difference 4x = (0100)2 give values only for

output differences 6x = (0110)2, 7x = (0111)2, Cx = (1100)2, Dx = (1101)2and

input difference Fx = (1111)2 give values only for output differences

1x = (0001)2, Bx = (1011)2, Ex = (1110)2, Fx = (1111)2.

3. For the LAT Table of S-Box 2, input difference 4x = (0100)2 give values only for

output differences 6x = (0110)2, Ax = (1010)2, Bx = (1011)2, Dx = (1101)2.

4. For the LAT Table of S-Box 6, input difference Fx = (1111)2 give values only

for output differences 5x = (0101)2, 7x = (0111)2, 8x = (1000)2, Fx = (1111)2.

3.4.3.3 Observations for cryptanalysis

These observations of XOR tables can be used for Differential cryptanalysis of

Serpent.

1. In three out of 8 of Serpents S-boxes, S0, S1, S2 the input difference

4x = (0100)2 can become the output difference with probability14

.

2. In two out of 8 of Serpents S-boxes, S1, S6 the input difference Fx = (1111)2

can become the output difference with probability 14 .

3. In one out of 8 of Serpents S-boxes, S0 the input difference Dx = (1101)2 can

become the output difference with probability 14 .

4. There are many places where given an active bit, and an arbitrary bit, the

output is the same under the same probability, such in S2 where 4x = (0100)2

23


32/68

0x 1x 2x 3x 4x 5x 6x 7x 8x 9x Ax Bx Cx Dx Ex Fx

2x 0 0 0 0 0 0 0 0 0 2 2 0 4 2 2 44x 0 0 0 0 0 0 0 0 0 4 4 0 0 4 4 06x 0 2 2 4 0 2 2 4 0 0 0 0 0 0 0 0

Table 3.7: A part of XOR Table of the S-box 0

and Cx = (1100)2 give Dx = (1101)2 with probability of14

. Also, in S3,

2x = (0010)2 and 3x = (0011)2 give Fx = (1111)2 with probability of14

.

5. In S0, the input difference 6x = (0110)2 has probability 0 to become (1???)2.

This means that the first bit is always zero. The cipher can be attacked byfinding differential and keeping some bit at zero difference. This reduces the

number of unknown bits in the next rounds.1

6. Also, in S0, the input difference 2x = (0010)2 has probability 0 to become

(0???)2 and input difference 4x = (0100)2 has probability 0 to become (0???)2.

Hence, these input differences give an output difference of the form (1???)2.

7. There are some connections of some output differences such as in S0, the input

difference 4x = (0100)2 give output difference in the form (1?x3

x4)2, where

x3 x4 = 1.

In the observations item (1), item (2), item (3) can be examined by Table 3.6. Also,

the observation explained in the items, item (5) and item (6) can be examined by Table

3.7.

1? denotes unknown values of bits.

24


33/68

Chapter 4

Randomness Testing of Serpent

Ciphers Versions

4.1 IntroductionA random process is one whose consequences are unknown. This is why randomness

is crucial in cryptographic applications. It provides a way to create information that

third part can not predict or learn. Thus, the experiments which tests randomness

of the outputs of ciphers, are done. There are some ways for randomness testing.

Especially, today NIST Statistical Test Suite [3] is used for randomness testing.

This chapter consists of the results of the randomness testing of Serpent Ciphers

versions and the tests were done according to the NIST Statistical Test Suite [3].

In the first section, Randomness Testing Experimental Preparation, that is; which

statistical tests were used, chosen sample data and test parameters are described.

In the second section, the results of randomness testing of full round output of

Serpent Ciphers versions and perturbed plaintext are given and in the last section,

the results of randomness testing of partial round output of Serpent Ciphers versions

are given. Partial round output means the outputs of round 1, round 2 and round 3.

4.2 Randomness Testing Experimental PreparationThis section defines some preparations of randomness testing. These preparations

consists of list of statistical tests, test parameters and sample data used in randomness

testing.

25


34/68

Table 4.1: List of Statistical Tests Applied During Test Application

Statistical Test No. of P-values Test IDMonobit 1 1

Block Frequency 1 2Cusum 2 3-4

Runs 1 5Long Runs of Ones 1 6

Rank 1 7Spectral DFT 1 8

Aperiodic Templates 148 9-156Periodic Template 1 157

Universal Statistical 1 158Approximate Entropy 1 159

Random Excursions 8 160-167Random Excursions Variant 18 168-185

Serial 2 186-187Lempel-Ziv Compression 1 188

Linear Complexity 1 189

Randomness testing of the outputs of Serpent Ciphers versions is divided into two

parts. First part is the testing of the full round outputs of the cipher. Second part is

the testing of the partial round outputs of the cipher.

All tests were done according to the application of the NIST Statistical Test Suite.

This suite consists of 16 core statistical tests, under different parameter inputs they

becomes 189 statistical tests.

26


35/68

Table 4.2: Parameter Adjustments for some of the Statistical Tests

Statistical Test Parameter ValueBlock Frequency Test Block Length(M) 128 bit

Non-Overlapping Template Test Block Length(m) 9 bitOverlapping Template Test Block Length(m) 9 bitApproximate Entropy Test Block Length(m) 10 bit

Serial Test Block Length(m) 16Linear Complexity Test Block Length(M) 500 bit

Universal Test Block Length(m) 1280 bit

Randomness Testing was performed with these specifications:

1. For each output of the Serpent Ciphers versions, the input parameters such as

the sequence-length, sample-size, and significance-level 1 were fixed for each

output data. The sequence-length is 65536 bits, the sample-size is 300 binary

sequences and the significance-level is 0.01.

2. For each P-value, a success/failure assessment was made based on whether or

not it exceeded or fell below the pre-selected significance level.

3. For each statistical test and each output, the proportion of binary sequences ina sample that passed the statistical test was calculated. If the P-values fell

below 0.01, the output was flagged as suspect2.

Data Description:

Data set was selected based on the belief that they would be useful in evaluating

the randomness of cryptographic algorithms. Plaintext Avalanche data type was

used for testing.

To examine the sensitivity of algorithms to changes in the plaintext, 300 binary

sequences were analyzed. The 300 sequences were parsed from a string constructed as

1The significance-level was fixed at 0.01 in each experiment. Thus, the expected number of rejec-

tions is 1 out of every 100 binary sequences.2Based on the size of the number of sequences and tests that were performed, 1 in 10.000 will not

give an excessive number of rejections when a generator is good.

27


36/68

follows: given 1200 random 128 bit plaintext blocks, and a 192-bit (or 256-bit) key of

all zeros, 153,600 derived blocks were concatenated. Each derived block was based onthe XOR of the ciphertext formed using the fixed 192-bit (or 256-bit) key and the

random plaintext and the ciphertext formed using the fixed 192-bit (or 256-bit) key

and the perturbed random plaintext with the ith bit changed for 1 i 128. A total

of 128 sets of derived blocks were formed for each random plaintext. All derived blocks

were concatenated, and a total of 153,600 derived blocks resulted. The 300 sequences

of 65,536 bits (512 blocks) were parsed from the concatenated derived blocks.

4.3 Randomness Testing of the Perturbed Random

Plaintext

In this section, the analysis of perturbed random plaintext is showed.

This data was chosen from 1200 random text where ith bit changed for 1 i 128.

One bit changed then concatenated, other bit changed and then concatenated. This

data was prepared in non-random way. Thus, non-randomness is expected from the

testing of this perturbed plaintext. The randomness testing results of the perturbed

plaintext are given in this section by NIST Statistical Test Suite.

Test Results of perturbed random plaintext is given in Table 4.3.

According to the test results, for only Longest Run test, the perturbed plaintext

gives 100% success rate. It gives success rate because it depends on the selected test

parameters. Also, for Block Frequency test, perturbed plaintext gives 0.7467 success

proportion, again it depends on the selected test parameters, since Block Frequency

block length is chosen 128 bit.

On the other hand, for 6 of these 16 statistical test, perturbed plaintext give 0.0000

success proportion. And all other tests give low success rate.

As a result, perturbed plaintext can be observed non-random as it is expected.

28


37/68

Table 4.3: Test Results of Perturbed Random Plaintext

Test Success ProportionApproximate Entropy 0.0000

Block Frequency 0.7467Cusum 0.2017

FFT 0.0000Frequency 0.2017

Longest Run 1.0000Linear Complexity 0.9433

Non-overlapping Template 0.0008Overlapping Template 0.0558

Runs 0.0542Serial 0.0000

Universal 0.0000Rank 0.0000

Random Excursion 0.3478Random Excursion Variant 0.0570

Lempel-Ziv 0.0000

4.4 Full Round Testing

In this section, the analysis of full round Serpent Ciphers versions outputs is

showed. Each experiment is done by sample data which is plaintext avalanche data

type generating from full round output of each Serpent Ciphers versions. And this

data is 300 number of binary string with 65536 sequence length for each.

In experiments, 148 templates for each binary sequences are used for Non-overlapping

Template Test.

4.4.1 Full Round Testing For Serpent-0

In this section, the experimental results of analysis of full round Serpent-0s outputsare given. Serpent-0 is a 32-round SPN. Thus, the 32-round outputs of the cipher are

used.

In 300 sample data, for one sequence, the maximum number of 0s is equal to 33085

and the maximum number of 1s is equal to 33099, the minimum number of 0s is equal

29


38/68

to 32437 and the minimum number of 1s is equal to 32451.

Test Results of full round Serpent-0s output is given in Table 4.4.

Table 4.4: Test Results of Full Round Serpent-0s OutputTest Success Proportion

Approximate Entropy 0.9867Block Frequency 0.9900

Cusum 0.9933FFT 1.0000

Frequency 0.9967Longest Run 0.9867

Linear Complexity 0.9667Non-overlapping Template 0.9833

Overlapping Template 0.9867Runs 0.9867Serial 0.9900Rank 0.9867

Random Excursions 0.9165Random Excursions Variant 0.9165

Lempel-Ziv 1.0000

Universal test is not applicable for the chosen sample data since the selected testparameters are not appropriate for this test.

According to Table 4.4, the minimum success proportion is 0.9165 and the maximum

success proportion is 1.0000 . And the number of test that gives 100% success rate is

2. This means that the P-values of all the test results of these sequences does not fell

below 0.01.

As a conclusion, Serpent-0s outputs gives good results for randomness. Thus, the

full round output of Serpent-0 can be decided as random.

30


39/68

4.4.2 Full Round Testing For Serpent-1 (Serpent)

This section describes the analysis result of full round output of Serpent-1 (Ser-

pent).

According to the experiments, for 100 sample binary sequences, the maximum num-

ber of 0s is equal to 33160 and the minimum of 0s is equal to 32387; therefore, the

maximum number of 1s is equal to 33149 and the minimum number of 1s is equal to

32451.

Again in the experiment, for Non-overlapping Template Test, 148 templates are

used for each binary string.

Test Results of full round Serpent-1s output is given in Table 4.5.

Table 4.5: Test Results of Full Round Serpent-1s OutputTest Success Proportion


Cusum 0.9900FFT 1.0000





Lempel-Ziv 1.0000

Universal test is not applicable for the chosen sample data since the selected testparameters are not appropriate for this test.


success proportion is 1.0000 . And the number of test that gives 100% success rate is

3. This means that the P-values of all the test results of these sequences does not fell

31


40/68

below 0.01.

Thus, Serpent-1s outputs give better results than the results of Serpent-0. However,they give nearest results.

As a conclusion, Serpent-1s outputs give good results for randomness. Thus, the

full round output of Serpent-1 can be decided as random.

4.4.3 Full Round Testing For Serpent-p

The new version Serpent-p of Serpent Cipher is tested by NISTs Statistical Test

Suite and the following results are occurred.

For 300 sample binary sequences, the maximum number of 0s is equal to 33203, so

then the minimum number of 1s is equal to 32451; and the maximum number of 1s is

equal to 33109, so then the minimum number of 0s is equal to 32427.

Test Results of full round Serpent-ps output is given in Table 4.6.

Table 4.6: Test Results of Full Round Serpent-ps OutputTest Success Proportion


Cusum 0.9867FFT 1.0000




Random Excursion 1.0000Random Excursion Variant 0.9333Lempel-Ziv 1.0000

Universal test is not applicable for the chosen sample data since the selected test

parameters are not appropriate for this test.

32


41/68


success proportion is 1.0000 . And the number of test that gives 100% success rate is3. This means that the P-values of all the test results of these sequences does not fell

below 0.01.

Thus, Serpent-ps outputs give nearest results to Serpent-1.

As a conclusion, Serpent-ps outputs give good results for randomness. Thus, for

the full round output of Serpent-p, randomness is evident.

4.4.4 Full Round Testing For Serpent-p-ns

In this section, another new version Serpent-p-ns of Serpent cipher is examined by

Nist Statistical Test Suite.

By examining each binary sequences the maximum numbers of 0s and 1s are equal

to 33136 and 33096, respectively. And the minimum numbers of 0s and 1s are equal

to 32440 and 32400, respectively.

Test Results of full round Serpent-p-nss output is given in Table 4.7.

Table 4.7: Test Results of Full Round Serpent-p-nss Output

Test Success ProportionApproximate Entropy 0.9933

Block Frequency 0.9833Cusum 0.9933

FFT 0.9967Frequency 0.9900

Longest Run 0.9867Linear Complexity 0.9733

Non-overlapping Template 0.9767Overlapping Template 0.9967

Runs 0.9967

Serial 0.9800Rank 0.9933


Lempel-Ziv 1.0000

33


42/68


parameters are not appropriate for this test.According to Table 4.7, the minimum success proportion is 0.9444 and the maximum

success proportion is 1.0000 . And one test that gives 100% success rate, which is

Lempel-Ziv. This means that the P-values of all the test results of these sequences

does not fell below 0.01.

This results are near to test results of previous Serpent Ciphers versions.

As a conclusion, Serpent-p-ns outputs give good results for randomness. Thus, for

the full round output of Serpent-p-ns, randomness is evident.

4.5 Partial Round Testing

In this section, partial round testing of Serpent ciphers versions are done. Partial

Round means that round 1s, round 2s and round 3s outputs of Serpent ciphers

versions are used in the statistical test experiments. Each experiment is done by

sample data which is 300 number of binary string of partial round output of each

Serpent ciphers versions.

For Non-overlapping Template Test, 148 templates for each binary sequences areused in the experiment.

The following subsections describes the experiment results.

4.5.1 Partial Round Testing For Serpent-0

The results of partial round testing of Serpent-0 is given below.

For outputs of round 1:

For 300 sample binary sequences, the maximum number of 0s is equal to 59697, so

then the minimum number of 1s is equal to 5839; and the maximum number of 1s is

equal to 6195, so then the minimum number of 0s is equal to 59341.


The maximum number of 0s is equal to 36021, so then the minimum number of

34


43/68

1s is equal to 29515; and the maximum number of 1s is equal to 30633, so then the

minimum number of 0s is equal to 34903.For outputs of round 3:



minimum number of 0s is equal to 32451.

Test Results of partial rounds of Serpent-0s output are given in Table 4.8.

Table 4.8: Test Results of Partial Round Serpent-0s OutputTest Success Proportion

Round 1 Round 2 Round 3Approximate Entropy 0.0000 0.0000 0.9800

Block Frequency 0.0000 0.0000 0.9900Cusum 0.0000 0.0000 0.9867

FFT 0.0000 0.1867 0.9967Frequency 0.0000 0.0000 0.9933

Longest Run 0.0000 0.9433 0.9900Linear Complexity 0.6900 0.9867 0.9867

Non-overlapping Template 0.0000 0.6500 0.9695Overlapping Template 0.0000 0.6500 0.9695

Runs 0.0000 0.0000 0.9933Serial 0.0000 0.0000 0.9800Rank 0.0000 0.9900 0.9867

Random Excursions 0.0000 0.0000 0.9286Random Excursions Variant 0.0000 0.0000 0.9286

Lempel-Ziv 0.0000 0.0000 0.0000

In the experiment, for Non-overlapping Template Test, 148 templates are used for

each binary string.



According to the results in Table 4.8, for 14 tests, Serpent-0s round 1 give all failure.

And only for 1 test, which is Linear Complexity test, Serpent-0s round 1 outputs give

0.6900 success proportion. It can be caused by chosen test parameter. Thus, it can be

concluded that Serpent-0s round 1 outputs are decided to be non-random.

35


44/68

For 9 tests, Serpent-0s round 2 outputs give all failure. The outputs pass the

Discrete Fourier Transform test with low success proportion. But for Longest Run,Linear Complexity and Rank tests, the outputs give success proportion above 0.9000 .

Again, Serpent-0s round 2 outputs can be said non-random.

On the other hand, Serpent-0s round 3 outputs give success proportion between

0.9200 and 0.9900 for all tests except Universal and Lempel-ziv Tests. From this

observation, it can be decided that Serpent-0s round 3 outputs are random according

to the results of NIST Statistical Test Suite.

4.5.2 Partial Round Testing For Serpent-1 (Serpent)

The results of partial round testing of Serpent-1 is given below.


The maximum number of 0s is equal to 59523, so then the minimum number of 1s is

equal to 6013; and the maximum number of 1s is equal to 6389, so then the minimum

number of 0s is equal to 59147.

It can be observed from above result, 0s and 1s are not distributed equally on the

outputs. This can be evidence for non-randomness.









Test results of partial rounds of Serpent-1s output are given in Table 4.9.



According to the results in Table 4.9, for 14 tests, Serpent-1s round 1 outputs give

all failure. And only for 1 test, which is Linear Complexity test, Serpent-1s round

36


45/68

Table 4.9: Test Results of Partial Round Serpent-1s Output

Test Success ProportionRound 1 Round 2 Round 3

Approximate Entropy 0.0000 0.0000 0.9867Block Frequency 0.0000 0.0000 0.9933

Cusum 0.0000 0.0000 0.9967FFT 0.0000 0.1867 1.0000

Frequency 0.0000 0.0000 0.9967Longest Run 0.0000 0.9300 0.9867

Linear Complexity 0.7866 0.9900 0.9867Non-overlapping Template 0.0000 0.6600 0.9933

Overlapping Template 0.0000 0.6600 0.9933Runs 0.0000 0.0000 0.9933Serial 0.0000 0.6567 0.9867Rank 0.0000 0.9867 0.9867


Lempel-Ziv 0.0000 0.0000 0.0000

1 outputs give 0.7866 success proportion. Again, it can be caused by chosen test

parameter. Thus, it can be concluded that Serpent-1s round 1 outputs are decided to

be non-random.

For 9 tests, Serpent-1s round 2 outputs give all failure. The outputs pass the

Longest Run, Linear Complexity, Non-overlapping Template, Overlapping Template,

Serial and Rank tests. The outputs give success proportion above 0.6000. Again,

Serpent-1s round 2 outputs can be flagged as suspect.

On the other hand, Serpent-1s round 3 outputs give success proportion between

0.9091 and 1.0000 for all tests except Universal and Lempel-ziv Tests. Also, for 2

tests, Discrete Fourier Transform and Random Excursions Variant, the outputs give

100% success rate. From these observations, it can be decided that Serpent-1s round3 outputs are random according to the results of NIST Statistical Test Suite.

37


46/68

4.5.3 Partial Round Testing For Serpent-p

The results of partial round testing of Serpent-p is given below.





It can be observed from above result, 0s and 1s are not distributed equally on the

outputs. This can be evidence for non-randomness.





Again, 0s and 1s are not distributed equally on the outputs.





Test results of partial rounds of Serpent-ps output are given in Table 4.10.



According to the results in Table 4.10, for 14 tests, Serpent-ps round 1 outputs

give all failure. And only for 1 test, which is Linear Complexity test, Serpent-ps round

1 outputs give 0.0033 success proportion. But this success proportion is low. Hence,

Serpent-ps round 1 outputs can be flagged as suspect.

As in the Serpent-ps round 1 outputs, except Linear Complexity test, all other

tests give all failure for Serpent-ps round 2 outputs. Linear Complexity test give0.9233 success proportion. Thus, Serpent-ps round 2 can be flagged as suspect, too.

In addition, as in the Serpent-ps round 1 and round 2 outputs, round 3 outputs

give 0.9900 success proportion for only Linear Complexity test. Other tests give failure.

It can be decided that Serpent-ps round 3 outputs are non-random.

38


47/68

Table 4.10: Test Results of Partial Round Serpent-ps Output



Cusum 0.0000 0.0000 0.0000FFT 0.0000 0.0000 0.0000





Lempel-Ziv 0.0000 0.0000 0.0000

4.5.4 Partial Round Testing For Serpent-p-ns

The results of partial round testing of Serpent-p-ns is given.


The maximum number of 0s and 1s are equal to 64 and 77, respectively. And the

minimum numbers of 0s and 1s are equal to 51 and 64, respectively.







Test results of partial rounds of Serpent-p-nss output are given in Table 4.11.



39


48/68

Table 4.11: Test Results of Partial Round Serpent-p-ns Output



Cusum 0.0000 0.0000 0.0000FFT 0.0000 0.0000 0.0000





Lempel-Ziv 0.0000 0.0000 0.0000

According to the results in Table 4.11, for 14 tests, Serpent-p-ns round 1 outputs

give all failure. And only for 1 test, which is Linear Complexity test, Serpent-p-ns

round 1 outputs give 0.0033 success proportion. But this success proportion is low.

Hence, Serpent-p-ns round 1 outputs can be flagged as suspect.

As in the Serpent-p-ns round 1 outputs, except Linear Complexity test, all other

tests give all failure for Serpent-p-ns round 2 outputs. Linear Complexity test give

0.9133 success proportion. Thus, Serpent-p-ns round 2 can be flagged as suspect, too.

In addition, as in the Serpent-p-ns round 1 and round 2 outputs, round 3 outputs

give 0.9933 success proportion for only Linear Complexity test. Other tests give failure.

It can be decided that Serpent-p-ns round 3 outputs are non-random.

4.6 Comparison of Test Results

By comparing the randomness test results, all Serpent Cipher versions full round

outputs pass all of the statistical tests except Universal test. Universal test can not be

40


49/68

applied since given test parameters are not appropriate for this test.

Comparison Table of full round outputs of Serpent Cipher versions, is given in Table4.12

Table 4.12: Comparison of Test Results of Serpent Cipher Versions Full RoundOutputs

Serpent-0 Serpent-1 Serpent-p Serpent-p-nsNo failure No failure No failure No failure

Failureproportion proportion proportion proportion

All sequences All sequences All sequences All sequencesSuccess

give success give success give success give success

proportion proportion proportion proportion

above 0.9000 above 0.9000 above 0.9000 above 0.9000

Comparison Table of round 1 outputs of Serpent Cipher versions, is given in Table

4.13

Table 4.13: Comparison of Test Results of Serpent Cipher Versions Round 1 Out-puts

Serpent-0 Serpent-1 Serpent-p Serpent-p-nsAll sequences All sequences All sequences All sequences

Failure give failure give failure give failure give failure

for all tests. for all tests. for all tests. for all tests.

Only Linear Only Linear Only Linear Only Linear

Success Complexity Complexity Complexity Complexity

test gives test gives test gives test gives

0.6999 0.7866 0.0033 0.0033

success proportion. success proportion. success proportion. success proportion.


41


50/68

4.14


Serpent-0 Serpent-1 Serpent-p Serpent-p-nsFrequency, Frequency, All sequences All sequences

Failure Block Frequency Block Frequency give failure give failure

Cusum Cusum for all tests. for all tests.

Runs Runs

App. Entropy App. Entropy

Serial FFT

give failure. give failure.

Longest Run 0.9433 Longest Run 0.9300 Only Linear Only Linear

Success Rank 0.9900 Rank 0.9867 Complexity Complexity

FFT 0.1867 Serial 0.6567 test gives test gives

Linear Complexity Linear Complexity 0.9233 0.9133

0.9867 0.9900 success proportion. success proportion.


4.15

According to the randomness testing experiments;

1. Perturbed random plaintext can be observed non-random.

2. Full round outputs of Serpent Ciphers Versions is where randomness is evident.

3. Round 1 outputs of all Serpent Ciphers Versions are flagged as suspect.

4. Round 2 outputs of all Serpent Ciphers Versions are flagged as suspect.

5. It can be observed randomness from Serpent-0 and Serpent-1s round 3 outputs.

However, Serpent-p and Serpent-p-ns round 3 outputs are flagged as suspect.

42


51/68


Serpent-0 Serpent-1 Serpent-p Serpent-p-nsLempel-Ziv, Lempel-Ziv, All sequences All sequences

Failure give failure. give failure. give failure give failure

for all tests. for all tests.

All tests All tests Only Linear Only Linear

Success give success give success Complexity Complexity

proportion proportion test gives test gives

between between 0.9900 0.9933

0.9286 and 0.9091 and success proportion. success proportion.

0.9967 value. 0.9967 value.

43


52/68

Chapter 5

Conclusion

Serpent was a candidate for the Advanced Encryption Standard. It has known its

cryptographic strengths against the known attacks such as; Differential cryptanalysis

and Linear cryptanalysis.

This project contains results and observations of the cryptographic properties of the

Serpents s-boxes and also randomness testing of the cipher outputs. As a conclusion,

according to the observations Serpents s-boxes have good cryptographic properties.

First of all, each linear characteristic of Serpents s-boxes has a probability in the

range 12 1

4. This means that the probability bias is 1

4for each s-boxes and for finding

a linear characteristic, too much known plaintexts are required. Also, a linear relation

between one single bit in the input and one single bit in the output has a probability

in the range 12 1

8.

In addition, each differential characteristic of Serpents s-boxes has a probability at

most 14

, and one-bit input difference never lead to one-bit output difference.

According to these results although there are some weakness of the Serpents s-

boxes, these s-boxes have good cryptographic properties against the known attacks.

At the same time, for all of the outputs of Serpent Ciphers versions, randomness

tests are done using NIST Statistical Test Suite. According to the randomness test

results, Serpent-0 and Serpent (Serpent-1) can be observed random first at the third

round. Although, Serpent-p and Serpent-p-ns is the upgrade versions of Serpent, their

round 1, round 2 and round3 outputs are flagged as suspect. However, full round

outputs of Serpent-p and Serpent-p-ns can be observed random.

44


53/68

Bibliography

[1] R. Anderson, E. Biham, and L.Knudsen, Serpent: A proposal for the

Advanced Encryption Standard, NIST AES Proposal, 1998.

[2] E. Biham, R. Anderson, L. Knudsen, Serpent: A New Block Cipher

Proposal, in Fast Software Encryption - FSE 98, Springer LNCS vol 1372 pp

222-238.

[3] A. Ruhkin, et. al., A Statistical Test Suite for the Validation of Random

and Pseudo Random Number Generators for Cryptographic Applica-

tions , NIST Special Publication, Spring 2000.

[4] M. Matsui, Linear cryptanalysis Method for DES Cipher, in Advances

in Cryptology - Eurocrypt 93, Springer LNCS v 765 pp 386-397.

[5] E. Biham, A. Shamir, Differential Cryptanalysis of DES-like cryptosys-

tems, in Advances in Cryptology: Proceedings of CRYPTO 90, pages 1-21.

Springer-Verlag, 1991.

[6] E. Biham, On Matsuis linear cryptanalysis, in Advances in Cryptology:

Proceedings of EUROCRYPT 94, pages 341-355, Springer-Verlag, 1995.

[7] O. Dunkelman, An Analysis of Serpent-p and Serpent-p-ns, presented in the second AES Conference, available at:

http://csrc.nist.gov/encryption/aes/round1/conf2/aes2conf.htm

[8] L. Knudsen, M. Robshaw, D. Wagner, Truncated Differentials and Skip-

jack.

45


54/68

[9] Howard M. Heys, A tutorial on Linear and Differential Cryptanalysis,

Memorial University of Newfoundland, St. Johns, NF, Canada.

[10] L. Knudsen, Block Ciphers: A Survey, State of the Art in Applied Cryp-

tography: Course on Computer Security and Industrial Cryptography (Lecture

Notes in Computer Science no. 1528), Springer-Verlag, pages 18-48, 1998.

[11] M. Hellman, S. Langford, Differential-Linear Cryptanalysis, Advances in

Cryptology - CRYPTO 94 (Lecture Notes in Computer Science no. 839), Springer-Verlag, pages 26-39, 1994.

[12] L. Knudsen, Truncated and Higher Order Differentials, Fast Software

Encryption (Lecture Notes in Computer Science no. 1008), Springer-Verlag, pages

196-211, 1995.

[13] J. Soto, L. Bassham, Randomness Testing of the Advanced Encryption

Standard Finalist Candidates,NIST, Spring 2000.

46


55/68

Appendix A

Appendix A

A.1 Linear Approximation Tables (LAT) of Ser-

pents S-boxes

Maximum values of LAT Tables of Serpents S-boxes

The maximum value of LAT Table of S-box 0 = 4.






The maximum value of LAT Table of S-box 6 = 4.The maximum value of LAT Table of S-box 7 = 4.

47


56/68

Table A.1: LAT Table of the S-box 00 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

0 +8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 0 -2 -2 0 -2 0 0 -2 0 -2 +2 +4 -2 0 -4 +22 0 +2 -2 0 0 +2 +2 +4 0 -2 -2 +4 0 -2 +2 03 0 0 -4 0 +2 -2 -2 -2 0 -4 0 0 +2 +2 +2 -24 0 0 0 0 0 0 0 0 0 0 0 0 +4 -4 -4 -45 0 +2 -2 +4 -2 -4 0 +2 0 +2 +2 0 +2 0 0 +26 0 -2 +2 0 0 -2 -2 +4 -4 -2 -2 0 0 +2 -2 07 0 0 0 -4 +2 -2 +2 +2 +4 0 0 0 +2 +2 -2 +28 0 -2 -2 0 +2 0 0 +2 0 -2 +2 -4 -2 -4 0 +29 0 0 0 0 0 +4 -4 0 0 0 0 0 +4 0 0 +4

10 0 +4 0 0 +2 -2 -2 -2 0 0 -4 0 -2 -2 -2 +211 0 -2 +2 0 +4 -2 -2 0 0 +2 +2 +4 0 -2 +2 012 0 -2 +2 +4 +2 0 +4 -2 0 -2 -2 0 +2 0 0 +213 0 -4 -4 0 0 0 0 0 0 +4 -4 0 0 0 0 014 0 0 0 +4 +2 +2 -2 +2 +4 0 0 0 -2 +2 -2 -215 0 -2 +2 0 -4 -2 -2 0 +4 -2 -2 0 0 -2 +2 0

Table A.2: LAT Table of the S-box 10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 150 +8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 0 -2 -2 -4 0 -2 +2 0 +2 0 0 -2 +2 0 -4 +22 0 -2 -2 0 0 +2 +2 +4 0 -2 -2 +4 0 -2 +2 03 0 0 0 0 0 0 +4 -4 0 0 0 0 -4 -4 0 04 0 0 -2 +2 0 0 +2 -2 -2 -2 0 -4 +2 +2 0 -45 0 +2 0 -2 0 +2 0 -2 0 +2 +4 +2 +4 -2 0 -26 0 -2 0 +2 0 -2 -4 -2 0 -2 +4 -2 0 -2 0 +27 0 -4 +2 +2 0 +4 +2 +2 +2 -2 0 0 +2 -2 0 08 0 0 0 0 0 +4 0 -4 0 0 0 0 0 +4 0 +49 0 -2 +2 0 0 +2 -2 0 -2 +4 0 -2 -2 0 -4 -2

10 0 +2 +2 +4 0 -2 +2 0 -2 0 0 +2 +2 0 -4 +2

11 0 -4 -4 0 0 0 0 0 -4 0 0 +4 0 0 0 012 0 0 -2 +2 +4 0 -2 -2 +2 +2 -4 0 +2 -2 0 013 0 +2 -4 +2 +4 +2 0 +2 0 +2 0 -2 0 -2 0 +214 0 +2 0 -2 -4 +2 0 +2 -4 -2 0 -2 0 -2 0 +215 0 0 -2 +2 -4 0 +2 +2 +2 +2 +4 0 -2 +2 0 0

48


57/68


0 +8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 0 0 0 0 0 +4 0 +4 0 -4 0 +4 0 0 0 02 0 0 +2 +2 +2 -2 0 +4 0 0 -2 -2 +2 -2 +4 03 0 0 +2 +2 +2 +2 0 0 0 +4 -2 +2 +2 -2 -4 04 0 0 +2 -2 -2 -2 +4 0 0 0 -2 +2 -2 -2 0 -45 0 0 -2 +2 -2 +2 0 0 -4 0 -2 -2 +2 +2 0 -46 0 0 0 -4 0 +4 0 0 0 0 0 -4 0 -4 0 07 0 0 +4 0 0 0 -4 0 -4 0 0 0 -4 0 0 08 0 0 -2 +2 0 0 +2 -2 -2 -2 -4 0 -2 -2 0 +49 0 0 -2 +2 +4 0 -2 -2 +2 -2 0 0 -2 -2 0 -4

10 0 +4 0 0 -2 -2 -2 +2 +2 -2 -2 -2 0 0 -4 011 0 -4 0 0 +2 -2 +2 +2 -2 -2 +2 -2 0 0 -4 012 0 0 0 0 +2 +2 +2 +2 +2 +2 -2 -2 -4 +4 0 013 0 0 +4 +4 -2 +2 +2 -2 +2 -2 +2 -2 0 0 0 014 0 +4 -2 +2 0 0 +2 +2 -2 +2 +4 0 -2 -2 0 015 0 +4 +2 -2 +4 0 +2 -2 -2 -2 0 0 +2 +2 0 0

Table A.4: LAT Table of the S-box 30 1 2 3 4 5 6 7 8 9 10 11 12 13 14 150 +8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 0 +2 0 -2 0 +2 -4 +2 0 +2 0 -2 0 +2 +4 +22 0 -2 +2 0 0 +2 +2 -4 -2 0 0 +2 +2 0 +4 +23 0 +4 +2 +2 0 0 -2 +2 -2 -2 0 +4 +2 -2 0 04 0 0 +2 +2 +2 +2 0 0 0 +4 +2 -2 +2 -2 0 -45 0 -2 -2 0 +2 0 0 +2 0 +2 -2 +4 +2 +4 0 -26 0 -2 0 -2 -2 0 +2 +4 +2 0 +2 0 +4 -2 0 +27 0 0 +4 0 -2 +2 +2 +2 +2 +2 -2 +2 -4 0 0 08 0 0 0 +4 +2 -2 +2 +2 -2 +2 -2 -2 0 0 0 +49 0 +2 0 +2 -2 -4 +2 0 +2 0 +2 0 0 +2 +4 -2

10 0 +2 +2 0 -2 0 0 -2 0 +2 +2 0 +2 +4 -4 +2

11 0 0 +2 +2 +2 +2 0 0 +4 -4 -2 -2 +2 + 0 012 0 0 -2 +2 0 +4 +2 +2 -2 -2 +4 0 -2 +2 0 013 0 -2 +2 0 +4 -2 -2 0 +2 0 +4 +2 -2 0 0 +214 0 +2 -4 +2 0 +2 0 -2 +4 +2 0 +2 0 -2 0 +215 0 +4 0 -4 +4 0 +4 0 0 0 0 0 0 0 0 0

49


58/68


0 +8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 0 0 +2 +2 +2 -2 0 -4 0 0 -2 -2 -2 +2 0 -42 0 0 +2 -2 0 0 +2 -2 0 0 +2 -2 +4 +4 -2 +23 0 0 0 -4 +2 -2 -2 -2 0 0 -4 0 +2 -2 +2 +24 0 0 0 0 +2 +2 -2 -2 +2 -2 +2 -2 0 -4 -4 05 0 +4 +2 -2 0 0 +2 +2 +2 +2 0 0 +2 -2 0 -46 0 -4 -2 -2 -2 +2 0 0 +2 +2 0 -4 0 0 +2 -27 0 0 -4 0 +4 0 0 0 +2 -2 +2 +2 +2 +2 +2 -28 0 0 0 +4 +2 -2 +2 +2 0 0 0 -4 +2 -2 +2 +29 0 0 +2 -2 0 0 -2 +2 -4 -4 +2 -2 0 0 +2 -2

10 0 0 +2 +2 -2 +2 0 -4 0 0 +2 +2 +2 -2 +4 011 0 0 0 0 -4 -4 0 0 +4 -4 0 0 0 0 0 012 0 -4 0 0 0 0 +4 0 -2 -2 -2 +2 +2 -2 -2 -213 0 0 +2 -2 +2 +2 +4 0 +2 -2 0 0 -4 0 +2 +214 0 0 -2 -2 0 -4 +2 -2 -2 +2 +4 0 -2 -2 0 015 0 -4 +4 0 +2 -2 -2 +2 +2 +2 +2 +2 0 0 0 0

Table A.6: LAT Table of the S-box 50 1 2 3 4 5 6 7 8 9 10 11 12 13 14 150 +8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 0 0 0 0 -2 +2 +2 -2 0 +4 0 +4 +2 +2 -2 -22 0 0 0 0 -2 +2 -2 +2 +2 +2 +2 +2 0 -4 0 +43 0 0 +4 +4 0 0 0 0 -2 +2 +2 -2 +2 -2 +2 -24 0 0 -2 +2 +2 +2 0 +4 0 0 +2 -2 +2 +2 -4 05 0 +4 -2 -2 0 0 +2 -2 0 0 +2 -2 +4 0 +2 +26 0 -4 +2 +2 0 0 +2 -2 +2 -2 0 0 +2 +2 0 +47 0 0 -2 +2 +2 +2 +4 0 -2 +2 0 0 -4 0 +2 +28 0 0 0 0 0 0 -4 -4 -2 +2 +2 -2 -2 +2 -2 +29 0 0 0 0 +2 -2 +2 -2 +2 +2 -2 -2 0 -4 -4 0

10 0 0 0 0 -2 +2 +2 -2 0 -4 +4 0 -2 -2 -2 -2

11 0 0 -4 +4 -4 -4 0 0 0 0 0 0 0 0 0 012 0 -4 -2 -2 -2 +2 0 0 +2 +2 0 -4 0 0 +2 -213 0 0 -2 +2 0 +4 -2 -2 -2 -2 -4 0 +2 -2 0 014 0 0 +2 -2 -4 0 +2 +2 -4 0 -2 -2 0 0 -2 +215 0 -4 -2 -2 +2 -2 0 0 -4 0 +2 +2 +2 -2 0 0

50


59/68


0 +8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 0 +2 0 -2 -2 0 +2 0 -2 -4 -2 0 0 -2 +4 -22 0 0 0 0 0 0 0 0 0 0 -4 +4 0 0 -4 -43 0 -2 0 +2 -2 +4 +2 +4 -2 0 +2 0 0 +2 0 -24 0 -2 0 -2 -2 0 +2 -4 0 -2 0 -2 +2 +4 -2 05 0 0 0 +4 0 -4 0 0 +2 -2 +2 +2 +2 +2 +2 -26 0 +2 -4 -2 +2 0 +2 0 0 +2 0 +2 -2 +4 +2 07 0 0 -4 0 -4 0 0 0 +2 -2 +2 +2 -2 -2 -2 +28 0 +2 0 +2 -2 0 -2 0 +2 0 -2 -4 -4 +2 0 -29 0 0 0 +4 0 0 +4 0 0 0 -4 0 0 0 0 +4

10 0 +2 0 +2 +2 +4 +2 -4 +2 0 +2 0 0 -2 0 -211 0 -4 0 0 +4 0 0 0 0 -4 0 0 -4 0 0 012 0 0 0 0 0 +4 -4 0 +2 -2 -2 +2 +2 +2 +2 +213 0 -2 0 +2 -2 0 -2 -4 -4 +2 0 +2 -2 0 +2 014 0 -4 -4 0 0 0 0 0 +2 +2 -2 -2 +2 -2 +2 -215 0 -2 +4 -2 -2 0 +2 0 +4 +2 0 +2 -2 0 +2 0

Table A.8: LAT Table of the S-box 70 1 2 3 4 5 6 7 8 9 10 11 12 13 14 150 +8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 0 -2 0 -2 -2 0 +2 -4 0 -2 0 -2 +2 +4 -2 02 0 -2 +2 0 0 -2 +2 0 0 -2 -2 +4 0 -2 -2 -43 0 0 -2 -2 +2 -2 +4 0 0 0 +2 +2 -2 +2 +4 04 0 0 +2 +2 -2 +2 0 -4 0 0 +2 +2 +2 -2 +4 05 0 -2 -2 +4 0 -2 +2 0 0 -2 -2 -4 0 -2 +2 06 0 -2 0 -2 -2 0 -2 0 +4 +2 0 -2 -2 0 +2 -47 0 0 0 0 +4 +4 0 0 +4 -4 0 0 0 0 0 08 0 0 0 0 +2 +2 +2 +2 -2 +2 +2 -2 +4 0 0 -49 0 +2 -4 -2 0 -2 0 -2 +2 0 +2 0 +2 -4 -2 0

10 0 +2 +2 -4 -2 0 0 +2 -2 -4 0 -2 0 -2 +2 0

11 0 0 +2 +2 0 -4 -2 +2 +2 -2 +4 0 +2 +2 0 012 0 -4 +2 -2 0 0 +2 +2 +2 +2 0 0 +2 -2 0 +413 0 -2 +2 0 +2 0 0 -2 -2 0 +4 -2 -4 -2 -2 014 0 -2 0 -2 +4 -2 -4 -2 -2 0 -2 0 +2 0 +2 015 0 +4 +4 0 +2 -2 +2 -2 +2 +2 -2 -2 0 0 0 0

51


60/68

A.2 Difference Distribution Tables (XOR) of Ser-

pents S-boxes

Maximum values of XOR Tables of S

analiza criptografica asupra versiunilor serpent

Documents