New Symmetric Cipher Fast Algorithm of Revertible Operations' Queen (FAROQ) Cipher

Published Online April 2017 in MECS

The modern techniques for the design of symmetric cipher basically rely on the mathematical and practical aspects and encourage on flexible style and intractable manner with robust structure by selection effective factors of cryptographic primitives for the algorithm built [1]. The National Institute of Standards and Technology (NIST) invited the cryptographers, cryptanalysts academic researchers and data security specialists all over the world to apply their own algorithms in order to select one to be a good alternative for the Data Encryption Standard (DES) and triple-DES, because the DES cipher suffered from many problems, represented by short key that not withstand the advance technology through nonresistance against brute force attacks, and the Triple-DES suffered from slowness with three ciphering key [2]. Many ciphers were originally submitted by designers from several countries. Fifteen algorithms were selected as initial selection, then after deep study and hard analysis processes reduced to the best five algorithms as a finalist candidate in the second selection [3]. The five algorithms were MARS, RC6, RIJNDAEL, SERPENT and TWOFISH which are considered non-superior at all. On October 2nd 2000, NIST announced that the Rijndael algorithm is the best one that has got the higher voting scores. The Rijndael cipher appears to be a very good in both hardware and software implementation through a wide range of platforms [4]. Our proposed model called FAROQ cipher similar in its work to the Rijndael cipher from several aspects and can be pictured as a byte-oriented structure that iterated for a number of stable rounds. So the first stage is a Subbyte operation that designed by applying another irreducible equation and a new affine transformation that was chosen from the best selection of what we have gotten. They have been given acceptable results in randomness and non-linearity. The second stage is a ReversibleShiftRow that is based on the same rotate operations in forward and backward operations. The third stage is a ReversibleMixcolumn operation is also based on adoption new linear equation with Maximum Distance Separable (MDS) notation that has self-inverse, which uses a single 4*4 MDS matrix over GF(28)[5]. The ReversibleMixcolumns considers a prominent change in polynomial matrices’ nature and one of the two main diffusion resource in the algorithm. This means the same linear equation used in a forward and backward operation that has self-reversible inverse with involution characteristics. The fourth stage represents the Round key addition or what is known by the key addition operation that is based on some sophisticated operations and it uses an extra bit-wise shift and rotates operations. The purpose behind the idea of reversible operation is to design a fast algorithm of involution structure in most of its stages that can be implemented in restricted space environments and to be work with small amount of RAM and an accepted amount of ROM as well as support fast key setup. The proposed cipher designed with some flexibility in terms of block and key sizes which accommodates alterations in the number of rounds and balanced of round structure with instruction parallelism. Our submitted paper is organized as follows: Section II. Describes the main characteristics and the types of algorithms’ structures for the modern block cipher. Section III. Explains the whitening and tweaking comprehensions. Section IV. Explicates the general structure diagram of the proposed algorithm and the main security layers. Section V. Attempts to show the rational design for the proposed cipher with basic criteria of construction steps. Section VI. Provides an overview of the important applications of the proposed algorithm. Section VII. Highlight the essential points of the analysis and the experimental results that have acquired, and we conclude in Section VIII.

• II. Block Cipher Design

The design scheme for any symmetric cipher based mainly on the type of structure design that different from one algorithm to another, so there are several of compact structure which adopted in numerous famous ciphers. These structures determine the general form of the work of the algorithm and can be reviewing here rapidly.

• A.    Substitution-Permutation Network (SPN) Structure

Substitution-Permutation Network, represent a series of mathematical operations that use substitutions clue also called (S-Box) and permutations which are called (P-Boxes) and it represents a special type of an iterated ciphers that have a more uniform round transformation [6]. The combining of these two primitives represents a special form of product ciphers where S-boxes provide confusion of input bits and P-boxes provides diffusion across P-box inputs. SPN acts as an iterated structure designed for modern product cipher. The key scheduling in this structure expanded normally into round keys that will be XOR’ed at the beginning of each round. The Rijndael and Serpent ciphers represent a good example of the SPN structure [7].

• B.    Feistel Cipher Structure

The Feistel structure is the most popular constructions and the oldest structure that was used in the Lucifer cipher and designed by Horst Feistel of IBM Company and later it was used in DES cipher. Feistel structure uses F-Function that accept half a block and subkeys as an input then depends on the block size which process as a two halves of data [8]. The same algorithm of Feistel structure used for encryption and decryption, so it is a suitable structure for the implementation with low cost of hardware. The SubKey algorithm implemented with reversed order for decryption this mean K1 is the last round and Kn in the first round and Kn-1 in the second round and so on. A typical number of Feistel round is 16 rounds for each round uses the SubKey generation algorithm that makes the algorithm more resistance to cryptanalysis. DES, RC6, MARS, Twofish are good ciphers for the Feistel structure [9].

• C.    Unbalanced Feistel Network

This type of structure similar to the traditional Feistel networks but it consists of a series of rounds in which one part of the block operates on the rest of the block. The UFN has two parts which no need to be of equal size. The main difference between traditional or conventional Feistel and the Unbalanced Feistel cipher is the last uses modified structure where L0 and R0 are not of equal lengths. The Skipjack encryption algorithm is a good example of such structure [10].

• D.    Generalized Unbalanced Feistel Network

Schneier and Kelsey generalized the concept of UFN by dispense with the two blocks to be combined by XOR operation. For a Generalized Unbalanced Feistel Network (GUFN) it is enough that one part of the input block controls another part of the input block, in which all bits of the internal state of the round are used in the round transformation, therefore the cipher is called complete, from another perspective if the bits are left invariant by the round transformation, the cipher is called incomplete. The advantages of this structure is allow a parallel computations of n-bits for encryption and it can provide provable security against the traditional differential and linear cryptanalysis [11].

• E.    Involution Structure

An involution block cipher is a block cipher with operations of involutional properties which has the forward process is the same as the backward process that means the same algorithm used for encryption and decryption. The involution structure characterized by reduced cost of hardware and good software implementation, in addition, to providing the same level of security since it uses the same digital circuit in ciphering and deciphering.

The only difference between the encryption and decryption processes in these ciphers is the reverse keyscheduling that performed in reverse order. The Feistel and SPN structure sometimes in certain ciphers considered as an involution ciphers. Anubis, KHAZAD and BSPN ciphers designed with involution structure [12].

• III.    Whitening and Tweaking

Whitening it is the technique of bit-wise XORing between the cipher key and the text before the first round and after the last round. It is proven that whitening routine substantially increases the difficulty of key search and increases the difficulty of attacking the cipher, by obscuring from an attacker specific inputs to the first and last rounds. The same whitening key is used for each block makes the brute-force search for the key much more time-consuming [13]. In recent years a new comprehension has emerged about the block cipher design which is known by a Tweakable Block Cipher (TBC) that was first introduced by Liskov, Rivest, and Wagner [14]. The TBC concept on opposite to the traditional block cipher that consists of just two inputs of cleartext and cipher key. The CBT contains an additional input called the tweak that controls the main operations of the round transformation along the key. The tweak purpose is to apply variability which provides flexibility in applications but not security [15].

• IV.    FAROQ Structural Features and Characteristics

The proposed cipher interests with the coherent internal structure which provides a new method to integrate the forward and backward operations into a full systematic crypto-cipher. This method assists the structure with reduced hardware resources and removes the vulnerability threat against the timing attack. The proposed architecture imposed to be suitable for critical applications, such as smartcard, personal digital assistant (PDA), and mobile phone, etc., among those difficult challenges the urgent need for lightweight block cipher become a demand and plays a vital role as a cornerstone for contemporary security applications. FAROQ cipher consists of three elementary layers: confusion layer, diffusion layer, and key addition layer. The confusion layer: A substitution of the bytes by means of a nonlinear transformation. The diffusion layer: Every byte is replaced by a linear combination of the bytes within the same column. The round key addition layer: The bytes are XORed with an n-bit round key.

FAROQ cipher supports the input plaintext block of 128-bit that represents as a state array of a square matrix 4*4 dimensions while it uses three variable secret keys of 128-bit, 192-bit, and 256-bit and with three limited rounds 10, 12, and 14 respectively. The main structure of the proposed cipher with ten rounds can be shown in Fig 1. One of the main points of the algorithm strength is the key length. Whenever the cipher key is big the resistance against the effective attacks will be difficult to exploit the byte-oriented structure and it will be extremely high, such as a square attack that deduces the key information with small size or with reduced number of rounds. So the proposed cipher followed the policy of utilizing the same key length of the AES cipher with three options according to the work sensitivity.

Fig.1. FAROQ Structure

• V.    The Design Framework

Our new design seeks to explain the positive aspects from the construction of a graceful algorithm that involves combining some operations in the main stages to provide a good structure. The new structure has to support a high speed and low cost hardware as well as applied a trusted cipher. The block size in any algorithm should be acceptable so as neither to be very big nor too small size. The designer should avoided the small block size because ciphertext will be subject to the dictionary attacks, since the large block has more resistant against the attacks. From other prospective with very big block size the algorithm will not work well and it will need to some padding operations. The suitable choice for the reasonable block size is multiple of a byte (8-bits) that can be implemented on most processors and devices easily. The proposed cipher expected to be capable of safeguarding against all known attacks, In the design of this cipher, we have taken into account the fact that the cipher must be feasible to implement perfectly in such a way that it provides conservativeness design. This cipher designed according to several important criteria:

• •    High margin of security

• •    Design simplicity and ease of implementation

• •    Resistance against all known attacks

• •    Transparent and conservative structure

• •    Suitability for secure implementations

• •    Symmetry in the round transformation

B. InvSubyte Transformations

The inverse of the proposed S-box is constructed by applying the inverse of the affine transformation followed by applying the multiplicative inverse in GF(28) and the result XORed with constant vector (3C). As shown in the equation (2).

b '

A. SubBytes Transformations

SubBytes: This is the first stage in the algorithm for data substitution process in the FAROQ cipher where each small block is replaced by its substitution in S-Box table with other block of output. The S-box is a table-driven non-linear substitution operation that used in most block ciphers and can be created either randomly or mathematically, so it can be defined as a square matrix 16*16, which contains permutation of all possible 256 values. The proposed S-Box is a mapping of one to one relationship with 8-bit values that constructed by selected another irreducible polynomial x8 + x5 + x3 + x + 1 and other affine equation as shown below matrix. The construction of the forward S-Box essentially depends on three steps, the first step is by taking the multiplicative inverse of all tables' values then applying the affine transform and the result XORred with the constant vector

represented by the value (87)

as it shown in the equation

b '₁ b '₂ b '₃ b '₄ b '₅ b '₆ b '₇

b ' 0 b ' 1 b ' 2 b ' 3 b ' 4 b ' 5 b ' 6 b ' 7

b0

b1

b2 b3

b4

b5

b6

b7

Ф

Table 2. Backward S-Box

Table 1. Forward S-Box

C. RevisibleShiftRows Transformations

The main purpose of the step RevisibleShiftRows is to spread the bytes of each input column to different output columns. This phase is a linear diffusion process that works on a singular row and each row of the array is rotated by a certain number of byte positions. The first row (row 0) is not shifted, and the remaining rows proceed as follows 2nd, 3rd and 4th rows 2-bytecircular left shift is performed, see Fig 2. For decryption, the corresponding steps of shifting process repeated again, the same replacement rows is exactly implemented with the same direction without any change. This is a good method to obtain an optimal diffusion and high fast implementation in addition to gain resistance against truncated differential attacks and saturation attacks. This stage inspired from the Tigris cipher with the same shifting steps, see ref [16].

Su	Soj	Si;	Su
Sic	Sil	Sy	Sy
Sm	821	Si;	Sy
S3|l	Sy	Sy	Sy

Fig.2. RevisibleShiftRows

Об

Об

D. RevisibleMixColumns Transformations

This stage includes shifting left and xoring of bits operation with themselves. These operations provide both confusion and diffusion particularity and mixing operations from various algebra. The mixcolumn transformation is based on multiplication of the state array with a certain matrix of Maximum Distance Separable (MDS). The MDS matrices are useful building blocks for ciphers because they guarantee a certain degree of diffusion and they are derived from the property that multiplication of a polynomial with a fixed polynomial over GF(28) results in a constant matrix multiplication. If one of the input elements is changed, all the output elements must change, as it defined in equation (3).

a(x) = {05} x3 + {06} x2 + {05} x + {07} (3)

This equation written as a matrix multiplication where the matrix is a circular matrix with the first row equal to a0; a3; a2; a1, each subsequent row is obtained by a circular shift of the previous one by 1 position to the left. This polynomial is coprime to (x4 + 1). Therefore, the transformation is invertible. This formula can be addressed under the shape of a matrix multiplication that is for all the 4 columns in the state matrix. The results of this multiplication are 4 bytes in the column, the matrix multiplication of s'(x) as follows.

a;		"07 05 06 05		A"		"07 05 06 05"		А/
A	®	05 07 05 06		Su	®	05 07 05 06	_	Su
Sic		06 05 07 05		A		06 05 07 05		Sic
Ar.		,05 06 05 07_		Su		05 06 05 07		Ar.

for 0 ≤ c < Nb where Nb = 4 no of bytes

As a result of this multiplication, the four bytes in a column are multiplied by the same matrix, in forward and backward, since the multiplying this matrix by itself give the identity matrix, this proved with a reducible polynomial of   (x4 + 1) over GF(28), as stated below.

a( x ) = b( x ) mod ( x4 + 1 )

• E.    FAROQ Add Round Key Transformation

The key addition is denoted by AddRoundKey. In this transformation the 128-bits of state matrix are bitwise XORed with 128-bit of the round key. The process is saw as a column by column between the 4 bytes of a state column and 4-bytes of round key column. The AddRoundKey transformation being as simple as possible and affects every bit of the state. There is no need to explain the inverse of AddRoundKey transformation because the forward of ciphering key transformation is identical to the inverse operation since the XOR operation has its own inverse.

• F.    FAROQ Key Expansion

Ciphering key represents the heart of encryption and decryption operations that must be kept secret which effects to the whole algorithm. The Rijndael cipher receive the initial cipher key K and executes a key expansion routine to generate a key schedule. The key expansion process determines in which method the expanded key is generated from the cipher key because the cipher model requires one round key for the initial key (primary key) to be XORed with the state array and one for each round which is known by subkeys and the operation called the key scheduling. The key expansion technique has been modified to be possible to execute the key schedule using a small amount of working memory and with high key agility feature. The expansion technique is the same that one adopted in Euphrates cipher, as shown in Fig 3. See ref [17] that achieved with two constants vectors represented by base natural logarithm and golden ratio, in order to eliminate any symmetries, prevent any weak keys through the progressive generation process of subkeys and to give an efficient diffusion for cipher key layer through the expansion process. The first use of these two constant vectors in the RC6 cipher’s key expansion [18] and then adopted in the proposing of developed new variant AES paper [19] that published by us.

Note

Pw = base natural logarithm (b7e15163), Qw = golden ratio (9e377969)

• >>8 bit =right rotate over the vector

Fig.3. FAROQ Key Expansion

G. FAROQ (F) Function

The function (F) forms the backbone for the SubKey generator. It is a complex function that is responsible for the key expansion, the terms F1 and F2 are work with the same manner and with the same three steps but the main difference between them, the (F1) manipulate the state matrix row by row and uses the base natural logarithm as a constant vector whether (F2) manipulate the state matrix column by column and uses the golden ratio as a constant vector. So the third step is performed as XORed vector with the previous vector. So, we will define the function (F) in more detail, it consists of three subfunctions through which each byte is run with its own key-dependent S-box. Each S-box is an 8-bit permutation: it takes eight bits of input and produces eight bits of output. The second sub function applied 8-bit right rotate over the vector and the third sub-function includes two constant vectors (base natural logarithm and golden ratio) that XORed with the previous result of the second subfunction. The key generator of our cipher can work efficiently in environments that need fast key change and can be built in a few gates of hardware that supported complex round function. The usage of two constant vectors are to derive the key information and through which eliminate weak keys and add a substantial resistance against related-key attacks as well as increase the computational complexity.

• VI.    Applications of The Proposed Model

The proposed cipher can be utilized in several areas, so the entire algorithm can be implemented completely using byte operation routine and the submitted cipher can be applied efficiently for the following applications:

• •    FAROQ cipher considers a good choice for the securing in E-commerce.

• •    It can be used in smart phone applications and handheld devices.

• •    It is sufficient cipher to apply in secured E-mails system Pretty Good Privacy (PGP).

• •    It provides secure financial transactions among banks Automata Teller Machine (ATM).

• •    The proposed model is inexpensive in software/hardware implementation so, it may be built with a few amount of resources.

• •    The proposed algorithm can be implemented to online ciphering of high speed-networking protocols like Fiber Distributed Data Interface (FDDI).

• •    Flexible design: e.g., accept additional key lengths; can be implemented on a wide variety of platforms and applications, it is suitable for a stream cipher, hash function, and MAC.

• •    Can be used to protect the E-Voting and online examinations from malicious activities.

• •    The elegant structure for the algorithm make it a multi-use model for several of light and heavy applications.

• •    FAROQ cipher acts a good solution for the sensor network applications.

• •    It’s a convenient choice for the trusted of network access control.

• •    FAROQ algorithm is applicable on Wi-Fi and WiMAX techniques.

• VII.    Analysis and Experimental Results

FAROQ cipher is a new cipher design which supports key expansion unit with simple design and high complexity that performed efficiently in applications with low covered area resources that has the ability to change keys quickly and with a minimum of resources (high key agility). This cipher uses an innovative paradigm, in the form of key-dependent S-boxes that creates an unusual dependency between the security of the algorithm and the structure of the key schedule that makes the known attacks very hard. We have proposed a more efficient combination      of     ReversibleShiftrows      and

ReversibleMixColumn operations that uses in the same manner in forward and backward, in order to use less resource than separated block implementations. This cipher ensures high performance with applications that require frequent change of the key relatively with high parallelism of computations to ensure fast encryption speed. The proposed cipher is tested using several statistical tests; the results of these tests do not indicate any deviation from random behavior. These tests are so important and necessary but not adequate for security needs. Simple comparison in encryption speed in Ms between the proposed cipher and the standard AES cipher can be shown in Table 1.

Table 1. Comparison Speed between FAROQ Cipher and the Original AES

Algorithms	No. of Rounds	Block Size	Number of Byte	Time of Encryption
Rijndael Cipher	10-Rounds	128-bit	1000	0.68
			10000	0.76
			100000	1.19
FAROQ Cipher	10-Rounds	128-bit	100	0.49
			10000	0.69
			100000	1.10

We have tested the algorithm’s implementation several times and select the best results with taken in to consideration the uncontrollable parameters and the deviation of statistical analysis with 16 bytes per block, see Table 2. The algorithm measured under Windows 10 Pro 32-bit, Intel (R) Core i7 Tm, with HD graphics 5500 NVIDIA GEFORCE 820m.

Table 2. FAROQ Performance of Different Key Implementations

Key Length	Language	Processor	Code Size	Clocks to Key	Clock to Encrypts
128-Bit	Assembly	Intel-Core i7	8950	10800	12850
192-Bit	Assembly	Intel-Core i7	8950	12250	14730
256-Bit	Assembly	Intel-Core i7	8950	13500	15690

FAROQ cipher provides both cipher execution and key setup/key change very fast with flexible design, timing and power analysis attacks have been taken into account. Our cipher mainly designed to be convenient with nonsacrifice of hardware resources and to be work with sufficient throughput. The S-Box is designed with restricting linear correlations between the plaintext and ciphertext bits so as to thwart linear cryptanalysis; this design is reasonable and provides an acceptable degree of confusion. FAROQ cipher interest with the high degree of balancing that makes the power analysis attack impossible for exploiting the difference in internal implementation of instructions.

• VIII.    Conclusions

We are introduced a new cipher design that can be implemented efficiently on smartcard processors and applications that require a small amount of RAM and ROM and gate count, especially in embedded systems. Number of modern design considerations have been done through designing of this cipher. This cipher focuses on the most important issues that have adopted in the design of most standard ciphers which include computational complexity and the hardware implementation in addition to the performance that effects on the cost and power consumption. FAROQ cipher can be considered as a lightweight cipher with a high margin security and highly processing rate to fully utilizing the affordable network bandwidth. The developed model designed to defeat the real security threats and to satisfy the current and the perspective of future requirements.

Acknowledgment

The authors would like to apply special thanks and grateful to those kind people in Computer Science Department-University of Technology for their support and help. The authors also would like to extend special thanks to Dr. Rafi Hussen for his great contribution in editing and proof reading this paper from a linguistic point of view.