An Effective and Secure Cipher Based on SDDO

Published Online October 2012 in MECS DOI: 10.5815/ijcnis.2012.11.01

Nowadays, the standard encryption AES [2] and other encryption algorithms are widely used in information security of Communication Networks. However, in the fast telecommunication systems requiring the optimization on hardware implementation or the specialized applications, it is very difficult to ensure when using those algorithms. To solve this requirement, [8-10, 13] have proposed the block cipher on the basis of the controlled substitution permutation network (CSPN). Besides, a very important element that the advanced encryption algorithms need to achieve is to ensure high speed in case of frequent change of secret keys. This was also studied and solved in [8-10, 12, 13] regards to synthetic methods of algorithms which don’t used the complexity transformation generating subkeys but use very simple key schedules. This solution ensures both the fast encryption in the case of frequent change of keys and the cheap hardware implementation.

However, [10] also point out the weakness of non-use of that key change process. That is the existence of weak key layers, which mean that it will reduce security of the ciphering algorithm. The existence of this weak key layer is because of the lack of procedure to generate the complex key, which leads to the fad that the attacker could use attacking method based on related-key [1] as in the algorithm IDA, GOST 28147, TEA, [3, 5-7]. Some solutions to prevent related-key:

• a)    Precomputation of key scheduling, algorithms in reality often use this method. Howerer, the resources to perform this algorithm will increase while changing speed will derease.

• b)    Developing algorithm with round function is changed.

• c)  Generating round keys “on the fly” with this

method, the resource to perform the algorithm will increase significautly while changing speed won’t change.

With the second solution, against the weak key lagers is solved in [11-13] by proposing the building block cipher 64 bits based on SDDOs.

Moreover, block ciphers which are being used have block size of 64 bits, but it also needs to have larger size cipher in order to ensure high flexibility due to its requirement and different applications. Concurrently, the higher the block cipher is, the higher security is, before the attacks.

With the problems denoted, a new cipher BMD-128 is proposed. It is developed based on SDDO with the block size of 128 bit, not ues procedure to generate the complex key. Thus, it is evaluated to be more suitable in fast telecommunication network.

This article is organired as follows: part 1, general instruction; part 2, the structure of switchable data-dependent operations data used in developing algorithms; part 3, representing developing algorithms; part 4, the results of evaluation and comparision the statical characteristics of the algorithms developed based on NESSIE’s criterias; part 5, differential analysis; part 6, evaluation and comparision performance when implementing developing algorithms on FPGA comparing with the famous algorithms and finally, conclusion.

II.   The structure of SDDO

The in [12], Moldovyan N.A described SDDO using Hawk 64 cipher based on minimum controlled element F 2/1 . Next, on the basic of symmetry topology of CSPN, it is very easy for us to build SDDO, which is the combination of active layers L i and the fixed permutation П [10]. The general structure of SDDO is presented in figure 1. The structure of SDDO is also the structure of CSPN, but it has the switchable controlling bit e which is used to control the distribution of the controlling vectors of lagers in CSPN. If e = 0 then the controlling vectors is distributed as follows: V 1 , V 2 … V s and if e = 1 then the controlling vectors is presented as V s , V s-i , …, V 1 . Therefore, the building SDDO on symmetry CSPNs is very simple. The structure of SDDOs which user BMD– 128 and minimum controlled element F 2/2 is given below.

symmetry topology. CSPNs are designed to enlarge directly and indirectly via the minimum controlled element F 2/2 . F 2/2 is shown in figure 2. F 2/2 is represented as a pair of BFs in four variables or as four 2×2 substitutions. If it is described in logic function y 1 , y 2 and y 3 = y 1 + y 2 , they will have higher number of 3. Consequently, non-linear (NL) value NL =4. The algebraic normal form of logic function of y 1 , y 2 and y 3 is shown below:

yt = vzxv Ф vx Ф zxv Ф zx2 Ф v Ф Xj Ф1;NL(y,) = 4;

y ₂ = vzx ₂ Ф vz Ф vx Ф zx_t Ф zx ₂ Ф v Ф z Ф x ₂ Ф 1; NL ( y ₂) = 4; y ₃ = vzx, Ф vzx ₂ Ф vx j Ф X j Ф v Ф X j Ф x ₂; NL ( y ₃) = 4;

NL(.) non-linearity of logic function for function affine based on the numbers of available variates. The differential characteristics of F 2/2 are described in table I.

x ₁           x ₂

v               ( v , z )

z       F 2/2

y 1          y 2

a)

A ' ^A y / А\ Pr ( A ' / A- , A ", )

S 1                  S 2                  S 3                  S 4

x 1        x 2        x 1        x 2        x 1        x 2        x 1        x 2

F 2/2

(01) 2/2

F 2/2

(11) 2/2

y ₁(1)          _{y 2}(1)          _{y 1}(2)          _{y 2}(2)          _{y 1}(3)          _{y 2}(3)          _{y 1}(4)          _{y 2}(4)

i, j,k = 0,1,2

c)

d)

Fig 2.The representation of the F2/2. a. General; b. represented as a pair of BFs in four variables; c. four 2×2 substitutions. d. Differential representation.

F ( V , e )

/ m . a. in case of even layer; b. in case of odd layer

The switchable data-dependent controlled operations which on in BMD-128 are built via CSPNs with

TABLE I. P robabilities P r ( ijk )=P r ( A ^y , / A X , A ^V k ) of any differential characteristics of F 2/2 element .

i, j k	001	002	011	101	110	120	002	102	102	202
F 2/2	0,25	0,125	0,1875	0,375	0,75	0,5	0,125	0,5	0,375	0,375

From F2/2, we synthesize and construct the structure of expanded operator with symmetry. In particular, F8/32 is built from 16 elements F2/2 which is divided into 4 layers in which each layer consists of 4 elements (see figure 3). Alternating between layers is the fixed permutations described in diagram. Then, 4 blocks F8/32 are combined parallel, so F32/128 is generated as a part in figure 5. In figure 5, the blocks F32/128 and the blocks of substitution S4x4 in SPN with fixed permutation I1 and I2 are combined as seen in the figure. The fixed permutation network SPN (see Figure 5) is constructed on the basic of permutational table used the Cipher DES. Where I1 and I2 are described as follows:

I 1 = (1)(2,9)(3,17)(4,25)(5)(6,13)(7,21)(8,29)(9,2)(10) (11,18)(12,26)(13,6)(14)(15,22)(16,30)(17,3)(18,11)(19) (20,27)(21,7)(22,15)(23)(24,31)(25,4)(26,12)(27,20)(28) (29,8) (30,16) (31,24) (32)

I 2 = (1)(2,5)(3,9)(4,13)(5,2)(6)(7,10)(8,14)(9,3)(10,7)

(11)(12,15)(13,4)(14,8)(15,12)(16)(17)(18,21)(19,25)

(20,29)(21,18)(22)(23,26)(24,30)(25,19)(26,23)(27)

(28,31) (29,20) (30,24) (31,28) (32).

V 2

V 3

V 4

a)

V 1

Z 3

Z 2

Z 1

b)

Z 4

Fig 3.The structure of F 8/32 (a), F^-1 8/32 (b)

of the controlled element of parallel combination P_2/1 and 2 expanded operators E and E ′ . The detail structure of SDDO F 3⁽2 ^L /^,1 ^{e )}28 and

F 6⁽4 ^L /^,3 ^e 8⁾4 is shown in figure 7.

а)

V 1 Z 1

V 2 Z 2

V 3 Z 3

a) V 1, Z1 V 2, Z2 V 3, Z3 V 4, Z4 V 5, Z5 V 6, Z6		x1       . . .        x8      x9       . . .        x16				x49    . . .       x64 ЛИЛЛ
	1	1        F 8/24	2       F 8/24		...	8       F 8/24
		... 8 2 ...		... 1		... 8 2 ...
		1        F 8/24	2       F 8/24		...	8       F 8/24
		y1       . . .         y8      y9       . . .        y16				лллл y49 . . . y64

V3, Z3

V2, Z2

V1, Z1

Fig 6.The structure of F64/384 (a) and F-164/384 (b)

b)

Fig 4.The structure of F8/24 (a) and F-18/24

With the block F 8/32 as figure 4, they are synthesized from 12 elements F 2/2 which are divided into 3 layers in which each layer includes 4 parallel elements. There are symmetric fixed permutations between layers shown in figure. Figure 6 describes detail the controlled block F 64/384 ; where F 64/384 is built indirectly via 16 blocks F 8/24 which is divided into 2 layers in which each layer includes 8 parallel blocks. Between 2 layers, it is the fixed permutation I described as follows:

I = (1)(2,9)(3,17)(4,25)(5,33)(6,41)(7,49)(8,57)(9,2)(10) (11,18)(12,26)(13,4)(14,8)(15,12)(16)(17,3)(18,11)(19) (20,27)(21,35)(22,43)(24,51)(25,4)(26,12)(27,20)(28) (29,36)(30,44)(31,52)(32,60)(33,5)(34,13)(35,21)(36,29) (37)(38,45)(39,53)(40,61)(41,6)(42,14)(43,22)(44,30) (45,38)(46)(47,54)(48,62)(49,7)(50,15)(51,23) (52,31)(53,39)(54,47)(55)(56,)(57,8)(58,16) (59,24)(60,32)(61,40)(62,48)(63,56)(64)

In figure 7, to control the distribution of the controlling ( L , e ) ( L , e )

vector in ^F 32/128 and ^F 64/384 , we use 16 permutations P 2/1 which are connected parallel. The expandion of bits in E and E ′ is performed as follows:

Box E : 32 bits which is seen as the right sub branch of figure 7 it is an input of the extension box E is L =( L 1 , L 2 ) with L 1 , L 2 ∈ {0, 1} ¹⁶ , while the controlling vector V =( V 1 , Z 1 , V 2 , Z 2 , V 3 , Z 3 , V 4 , Z 4 , V 5 , Z 5 , V 6 , Z 6 ) uses the switchable controlled operator F ^{( L , e )} gerenerated as follows:

F 32/128

V 1 = L 1 || L 2^<<<2 , V 2 = L 1^<<<4 || L 2^<<<6 , V 3 = L 1^<<<8 || L 2^<<<10 , V 4 = L 2^<<<8 || L 1^<<<10 , V 5 = L 2^<<<4 || L 1^<<<6 , V 6 = L 2 || L 1^<<<2 ; Z 1 = L 1^<<<6 || L 2^<<4 , Z 2 = L 1^<<<12 || L 2^<<8 , Z 3 = L 1 || L 2^<<<12 , Z 4 = L 2 || L 1^<<<12 , Z 5 = L 2^<<12 || L 1^<<<8 , Z 6 = L 2^<<<6 || L 1^<<<4;

( L , e )        ( L , e )

Fig 7.The structure of SDDO 32/ 128 ,    64/384

I      F 8/32     II F 8/32      | |      F 8/32      | [ F 8/32

I 1

I S0 ]| S1 ]| S2 :i S3:i S4:i S5 ]| S6 :i S7

S-0 ] S1-]1 S-2]1 S3-

S ^- 4 ]  S - 5Л S ^- 6]1 S7 -

SPN

I 2

Box E ′ : Similary, 32 bits is seen as the left sub branch of figure 3 (it is an output of the extention block E ′ ) then the controlling vector V =( V 1 , Z 1 , V 2 , Z 2 , V 3 , Z 3 , V 4 , Z 4 ) uses the switchable controlled block F ^{( L , e )} created as follows: 32/128

V 1 = L 1 , V 2 = L 1^<<<8 , V 3 = L 2^<<<8 , V 4 = L 2 ; Z 1 = L 1^<<<6 , Z 2 = L 1^<<<12 , Z 3 = L 2^<<<12 , Z 4 = L 2^<<<6 .

Fig 5.The structure of F32/128, I1 and SPN

On the basic of F32/128 and F64/384, we embed the switchable controlled operator (SCO) to generate SDDO. SCO is created via the combination

Above is the whole structure of SDDOs used in the algorithm BMD-128. With this structure, it is more interesting to build from F2/2 which will provide a huge support in generating the high performace Cipher.

• III. The Cipher BMD-128

The Cipher BMD-128 is the block cipher with the block size of 128 bits. Its includes eight – round change as seen in figure 8, without the complex used secret key procedure and constructed on the basic of SDDO in combining with the fixed permutation network. The prominent characteristics that BMD-128 oriented to:

• a)    Using the nontinear transformation with the differential characteristics in correspondence with the minimum controlled element.

• b)    Orienting to implementation on hardware which has ability or cheap reconfiguration with high speed encryption.

• c)    The process in encrypted cirle is parellel so it help to create high speed encryption.

• d)    The process of the extention of keys is simple. Therefore, it ensures a high speed encryption in the case of frequent change of keys.

• e)    The encryption and decryption procedure are used the same diagram.

• f)    The security and efficiency are improved.

According to the diagram algorithm, each basic round unit of BMD-128 uses 2 elements SDDO which are F ^{( L , e )} and F ^{( L , e )} (as describled detail in part 2). The 32/128        64/ 384

elements used in this algorithm are basically synthesized from the minnimum controlled element F 2/2 , so it helps to improve mainly the sandard cipher of algoriths. Using SDDOs contructed as above allows to decrease the encrytion loops of the algorithm, but it also ensures the high durability of the Cipher. Concurently , italso ensures to decrease the complex in device when implementing on FPGA with the pipelining architecture and improves speed encryption when implementing on FPGA with the Iterative Looping.

Fig 8.The diagram of the algorithm BMD-128.

General diagram (a); A basic round Cipher unit (b).

The subkeys Ki∈ {0,1}64 are constructed from the sceret key K including 256 bits K = (K1, K2, K3, K4). The round key Uj, Qj are selected from the subkeys Ki and listed in table II. Here, we don’t used the complext transformation generating subkeys, aiming to minimise device and speed up when implementing on hardware, but it also ensures the security (see VI for more detail) of the cipher owing to special point of the switchable controlled operators which are used the algorithm to generate the data dependent controlling with F(L,e) andF(L,e) . The switchable bits e1, e2, e3 and e4 depend on bit e (e∈{0,1}). Defining encryption  (e=0)  and decryption (e=1) mode and ei is determined as follows:

e 1 = e ⊕ e ′ 1 , e 2 = e ⊕ e ′ 2 , e 3 = e ⊕ e ′ 3 , e 4 = e ⊕ e ′ 4 , where e ′ 1 , e ′ 2 , e ′ 3 and e ′ 4 are described in table II.

The whole Cipher BMD-128 is briefted as follows:

• 1.    For j = 1 to 7 do: {( L , R ) ← Crypt ^{( e )} ( L , R , U j ,Q j ); ( L , R ) ← ( L , R )}.

• 2.    ( L , R ) ← Crypt ^{( e )} ( L , R , U 8 , Q 10 ).

• 3.    ( L , R ) ← ( L ⊕ U 9 , R ⊕ Q 9 ).

The final transformation (FT) is perpormed by implementing the operation XOR on left or right halfes data block with the round key corresponding to its selection. This algorithm enables the encryption and decryption processes to be used the same algorithm. Besides, it is shown that the encryption and decryption processes use the same key scheduling and transformation encryption and decryption mode only needing transformation of the controlling bit. This helps to reduce significantly the lost of hardware implementation.

TABLE II.      T he key scheduling and lists the switch bits in

BMD-128

j =	1	2	3	4	5	6	7	8	FT
Q =	K 1	K 3	K 1	K 2	K 3	K 4	K 3	K 4	K 1
U j =	K 2	K 4	K 3	K 4	K 3	K 2	K 1	K 3	K 2
e ′ 1 =	1	0	1	1	0	1	0	0	-
e ′ 2 =	0	0	1	0	1	1	0	1	-
e ′ 3 =	0	0	0	1	0	1	1	0	-
e ′ 4 =	0	1	1	0	1	0	0	0	-

• IV.    SECURITY ESTIMATIONS of the algorithm BMD-128 according to criteria NESSIE.

According to criteria of NESSIE [7], we have carried out to evaluate the statistical characteristics of the Cipher BMD-128, which also denotes that it is suitable with the criterias that NESSIE has given. We evaluated with the number of samples being 40.000 and carried out in 2 directions:

• a)    keeping keys and only changing data (#K=1;#X=40000);

• b)    keeping data and changing key (#K=40000;#X=1).

The evaluated testing results in to 2 directions above are represented in table IV (see part appendix). Based on the standard of NESSIE, the algorithm can meet a demand of this standard when d 1 ≈ 64, d c =1, d a ≈ 1, d sa ≈ 1.

From the testing results, the paper shows that the algorithm BMD-128 can satisfy the 4 criterias of NESSIE about the influence of the original data bits clear text, as the same as the influence of key bits. The research results of the statistical charateristics about the influence of key bits for this algorithm are very important because it used very simple key schedules, but it ensured the statistical properties in term of the standard of NESSIE.

• V.    Differential characteristics of BMD–128

To evaluate the reliability of cipher before the different attacks of the cryptanalysis is one of the important and necessary requirement. With block cipher, most effective cryptanalysis solution is the differential cryptanalysis method. It means that the probability p through the transformations of the ciphering diagram.

As you know, the differential characteristics of expanded controlling operations will depend on the building architecture, the distribution of controlling bit and the differential characteristics of the minimum controlled element used in that structure.

Firstly we should consider the mechanism creating avalanche effect or the differential characteristics of operations used in algorithm. For SPN, figure 6 shows that when changing any bit input of SPN blocks, it can transform the output less than 4 bits. For F 2/2 element, the differential characteristics is described in table I. Then the differential characteristics of expanded element from F 2/2 used in this algorithm will be studied.

Assume, input block X with one active bit, then the probability happening in case of output which has one active bit passing through F ^(e3)64/384 (or F ^(e4)64/384 and F ^(e1)32/128 (or F ^(e2)32/128 )) with zero active bit of the controlling vector as follows:

Pr( A X 1 — F ⁶⁴ / ³⁸⁴ >  A Y 1 ) = (Pr(yk )) ⁶ = 0.75 ⁶ « 2 -2.5 ,

Pr( A X i — F ³ — >  A Y i ) = (Pr(ijk )) ⁴ = 0.75 ⁴ « 2 -1.5 .

Where Pr( ijk )=Pr(110)=0.75 (see table I). Besides, because of data block X when passing through the extention block E (in Figure 8), which is repeated 12 times, when passing through the extention block E ’ which is repeated 4 times, active bit in data block X will generate the output of the extention block E being 12 active bit, and the output of the extion block E ’ being 4 active bits. Therefore, the input data block X has zero active bit, where the probability happening in case of the output without the active bits when passing through F ^(e3)64/384 (or F ^(e4)64/384 ) and F ^(e1)32/128 (or F ^(e2)32/128 ) when having an active bit in the controlling vector equals to:

Pr(AXо —F6— >A Yo) = (Pr(ijk))12 = 2-24, Pr(AXо F32/128 >AYo) = (Pr(ijk))4 = 2-8, where, Pr(ijk)=Pr(001)=1/4 (see table I). When having k, k<5, the active bits belonging to random type of the data block X for have F(e3)64/384 / (or F(e4)64/384) and F(e1)32/128 (or F(e2)32/128) the probabilities as follows:

Pr( A X ₀ — F ⁶⁴ / ³⁸⁴ >  A Y ₀ ) « (Pr( ijk )) ^{12 k} = 2 ^{-24 k} .

Pr( A X о — F ³² / ¹²⁸ > A Y o ) « (Pr( ijk )) ^{4 k} = 2 ^{-8 k} .

The study shows that when having 2 active bits at input of the controlling vector F 2/2 , the probability of Pr( ijk )=Pr(002)=1/8 (see table I). The output of the extention block E has 12 active bits and the output of the extention block E ’ is 4 active bits. The maximum value of the probability Pr( A X ₀ >A Y 0 ) is used to compare in the case of small probability when tk active bits of the controlling vector falling down the controlling t/2k of the Elements F 2/2 , t=2k or t=4k . In case of this, we have the probability:

Pr( A X 0 — F ⁶⁴ / ³⁸⁴ > A Y ₀ ) = (Pr(002)) ^{-6 k} « 2 ^{-18 k} .

Pr( A X 0 — F ³² / ¹²⁸ > A Y ₀ ) = (Pr(002)) ^{-2 k} « 2 ^{-6 k} .

Thus, the controlling elements appeared above are the main part to create avalanche effect in this cryptographic algorithm. Concurrently, on the basic of the differential analysis above, the paper studies and calatates the two – round differential trace of BMD-128 in 2 cases (see figure 9, 10 part appendix) and collects the probability results of the existence of differential trace through two– round transformation being p = 2 ^-45.5 (figure 9) and p =2 ^-51.5 (figure 10 - see part appendix).

Combining with the analysic and the calculation above, the differential traces of the algorithm are carried out to evaluate via testing program on software. In this program, to reduce the numbers of calculation and exist the generality 2 cases are considered:

• a)    The samples given encryption only appear 2 active bits which go into the primarity at the left data halres L and appear at the output of the left halres L .

• b)    The samples given to encryption only appear 2 active bits which go into the primarily at the right data halres R and appear at the output of the right halres L .

With weight w =2, at the output of the algorithm after two-rounds of encryption has been calculated and the results were nearly equivalent p ≈2 ^-54

Therefore, with both two methods given above, the following conclusions can show that after 4–round transformation, the cipher BMD–128 has excess capacity against differential cryptanalysic. However, the authors also has 4–round is order to increase the reliability of avoid the other cryptanalysis.

table iii.   The best differential characteristics of BMD-128

Cipher	Rmax	Differential charactenstics		P(r)
		min	P(2)
COBRA-H64	8	(0, Δ R )	P(2) ≈ 1.13.2-19	≈ 2-75
COBRA-H128	10	(0, Δ R 1 )	P(2) ≈ 1.25.2-29	≈ 2-144
SG-128	10	(0, Δ R 1 )	P(2) ≈ 2-32	≈ 2 -160
SS-128	10	(0, Δ R 1 )	P(2) ≈ 2-34	≈ 2-170
DDO-64	6	(0, Δ R )	P(2) ≈ 2-29	≈ 2-87
Eagle-128	10	(0, Δ R )	P(2) ≈ 2-35	≈ 2-175
BMD-128	8	(0, Δ R )	P(2) ≈ 2- 51.5	≈ 2- 206

(R max: the maximum number of rounds)

In order to have more information for conclusion about the ability against differential cryptanalysis of the cipher BMD–128, the compared table about the differential cryptanalysis of some cipher (see table III). Through the compared table, the study show that the cipher BMD–128 has the ability against differential cryptanalysis best which is homogenised with BMD-128 which has a better security.

• VI.   FPGA SYNTHESIS RESULT AND

COMPARISIONS

The study is carried out to do test which simulates the cipher BMD–128 on FPGA and compare and evaluate its performance with the other famous algorithms such as CIKS-128H, Rijndael, Serpent, RC6, Twofish, Cobra-H128, IDEA, AES. To ensure the objectivity, the study is also concurrently performed on chips FPGA Xilinx Virtex Device v200pq240. The results in detail are described in table V.

The results above shows that the algorithm BMD–128 has higher speed, but has smaller hardware requirement than the modern famous algorithms. Comparing the performance: speed/cost or speed/(cost * frequence) shows that BMD–128 has higher and higher performance than the famous algorithms.

table iv.   Comparing the implementation results of algorithms on Chips FPGA Xilinx Virtex Device v200pq240

Cipher	Block size	Rmax	N	Area (CLBs)	F (MH z)	Throughput (Mbps)	Performance
							Mbps/#CLBs	Mbps/(#CLBs*GHz)
BMD-128	128	8	1	1006	89	1424	1.42	15.9
CIKS-128H [9]	128	8	1	1,511	65	992	0.66	10.2
Rijndael [10]	128	10	1	2,358	22	259	0.11	5.0
Serpent [11]	128	32	8	7,964	13.9	444	0.056	4.0
RC6 [11]	128	20	1	2,638	13.8	88.5	0.034	2.4
Twofish [11]	128	16	1	2,666	13	104	0.039	3.0
Cobra-H128 [3]	128	12	1	2364	86	917	0.39	4.51
IDEA [3]	128		1	2878	150	600	0.21	1.39
AES [3]	128	8	1	2358	22	259	0.11	4.99

• VII.    CONCLUSION

This paper proves the efficiency of using SDDOs which is constructed on the basic of CSPNs in constructing the block cipher BMD–128, aim at implementing on the platform of FPGA technology. The evaluation of performance, statistical analysis and differential analysis show the high applicability of our algorithm in fast and highly efficient telecommumcation system.