See discussions, stats, and author profiles for this publication at: [Link]

net/publication/344465037

Different Types of Attacks on Block Ciphers

Article in International Journal of Recent Technology and Engineering (IJRTE) · September 2020
DOI: 10.35940/ijrte.C4214.099320

CITATIONS READS

16 4,444

2 authors:

Wageda Ibrahim Alsobky Hala Saeed

Benha University Benha University
36 PUBLICATIONS 195 CITATIONS 4 PUBLICATIONS 24 CITATIONS

SEE PROFILE SEE PROFILE

All content following this page was uploaded by Wageda Ibrahim Alsobky on 04 October 2020.

The user has requested enhancement of the downloaded file.

 International Journal of Recent Technology and Engineering (IJRTE)
ISSN: 2277-3878, Volume-9 Issue-3, September 2020

Different Types of Attacks on Block Ciphers

Wageda Alsobky, Hala Saeed, Ali [Link]

 component of block ciphers, they have an important effect on

Abstract: Cryptanalysis is a very important challenge that faces cryptographic strength [5]. The design of S-boxes represents
cryptographers. It has several types that should be well studied by an important problem for security because they are the only
cryptographers to be able to design cryptosystem more secure and nonlinear part in an encryption process and each successful
able to resist any type of attacks. This paper introduces six types of linearization approximation can help break a few bits of the
attacks: Linear, Differential , Linear-Differential, Truncated key [5].S-box operates independently on each byte of the state
differential Impossible differential attack and Algebraic attacks. using a substitution table [6]. The main limitation of S-box is
In this paper, algebraic attack is used to formulate the substitution that it is fixed through the encryption algorithm. This main
box(S-box) of a block cipher to system of nonlinear equations and point of weakness attracts the cryptanalyst to exploit it for
solve this system by using a classical method called Grobner  certain attacks [7]. There are four evaluation criteria for
Bases . By Solving these equations, we made algebraic attack on S-Boxes : bijectivity, nonlinearity, strict avalanche, and
S-box. independence of output bits [7]. The nonlinearity of S-box
Keywords: Linear attack; Differential attack; Algebraic attack; reflects the algebraic degree that should be highly enough to

S-box; Grobner Bases resist the algebraic attacks [7] . In this paper, we have used
algebraic attack to penetrate the S-box of a block cipher.
I. INTRODUCTION In our study, we will explain the different types of attacks on
block ciphers and use one type of them called algebraic attack
Cryptography is an essential process to transmit data in a to penetrate the S-box.
secure way. It protects data against passive and active attacks In section 2, we introduce the definition of the attack. Then in
[1]. More generally, cryptography is almost constructing section 3, different types of attacks are introduced. In section
protocols that prevent public from reading private data[1]. 4, the principle of light weight AES S-box is explained. In
Cryptographers face a huge number of difficults to design the section 5, the resistance of algebraic attacks (  ) explained to
cryptosystem. One of these challenges is the attack that tries measure the strength of the S-box. In section 6, we apply
to penetrate the cryptosystem [2]. There are two types of 
Grobner Bases as a method for solving multivariate system
attacks based on the method of treating data transmitted: of nonlinear equations included in the mathematical model of
active attack and passive attack[1,2]. In active attack, the the S-box to penetrate it.
hacker attempts to modify and change the data transmitted
between sender and receiver[2]. This type of attack is divided II. DEFINITION OF ATTACK
into five types: Masquerade, Modification of messages,
Repudiation, Replay and Denial of service[1,2]. On the other Attack of cryptosystem (also called cryptanalysis) means
hand, hacker in the passive attack uses the data being understanding how the cryptosystem works with the aim of
transmitted but doesn't affect it[2]. This type includes another finding and improving techniques in order to defeat or weak
two types: The release of message content and Traffic this system [8]. Results of cryptanalysts' research are used by
analysis[1,2]. Based on what type of information the hacker cryptographers to improve the strength of the encryption
has available, there are two types: Statistical and Algebraic algorithm to be able to resist any attack [8]. Abroad range of
attacks. Statistical attacks are divided into linear and organizations (such as government and companies) practiced
differential attacks[3]. Statistical attacks are considered easier cryptanalysis to decrypt other nations' confidential
than algebraic attacks since they avoid the complexity of the communications.[8]
algebraic attacks[3]. Algebraic attacks depend on formulating A. Different types of attacks
the cipher into system of equations and then solve it[4]. The
There are different types of attacks based on what type of
block ciphers depend on the substitution boxes( S-boxes).
information the hacker has available. These types are
These S-boxes are static and have no relation with the secret
explained as follows:[3]
key, so the secret key is the only volatile parameter [4] .The
design of S-boxes was published by Don Coppersmith in 1) Statistical attacks
1994. Until this date, the use of S-boxes in the standard wasn't In these attacks statistical weaknesses are exploited in a
perfectly understood [5]. Since S-boxes are the only nonlinear targeted algorithm. They includes six types: Differential ,
Linear, Differential-linear , Truncated differential and
Revised Manuscript Received on August 05, 2020. Impossible differential attack.[3]
* Correspondence Author
Wageda Hafez*, Department of Basic Engineering Sciences, Benha
 Differential attack [9]
Faculty of Engineering, Benha University, Egypt. E-mail: This type of attack try to find the difference between
[Link]@[Link] related plaintexts that are encrypted . The plaintexts may
Hala Saeed, *, Department of Basic Engineering Sciences, Benha differ by a few bits.
Faculty Of Engineering, Benha University, Egypt. E-mail:
[Link]@[Link].
Ali [Link], Department of Basic Engineering Sciences, Benha
Faculty Of Engineering, Benha University, Egypt.

Published By:
Retrieval Number: 100.1/ijrte.C4214099320 Blue Eyes Intelligence Engineering
DOI:10.35940/ijrte.C4214.099320 28 and Sciences Publication
 Different Types of Attacks on Block Ciphers

The plaintext to be encrypted are chosen by the attacker (but The S-box is constructed by the composition of two
attacker doesn't know the key) and then encrypts related transformations:[16]
1) Taking multiplicative inverse (x ) in GF (2 ) . (x ) is
plaintexts . Then statistical analysis is used by the 1 4 1

cryptanalyst to search for signs of non-randomness in cipher

defined by the inverse function I ( x ) as follows:
texts, zeroing in on areas where the plaintexts differ . Every
bit of the related cipher texts should have a 50/50 chance of
flipping; the cryptanalyst searches for areas where this is not ( x )14 , x   0
true. Any such underlying order is a clue to recover the key. I ( x )  
 Linear attack [10] 0, x   0
It is one of the two most widely used attacks on block 2) Applying an affine transformation function y ( x ) over
ciphers; the other being differential attack. It seeks to find GF (2) defined by:
affine approximations to the action of a cipher. There are two
1 0 1 1   x 3   0 
parts to linear attack. The first one is about constructing linear
    
0 1 1 1   x 2   0 
y (x )  Ma  x  ' 2 '  
equations relating plaintext, cipher text and key bits that have
   (1)
a high bias , whose probabilities of holding (over the space of 1 1 1 0   x 1  1 
all possible values of their variables) are as close as possible     
to 0 or 1. The second is about using these linear equations in 1 1 0 1   x 0   0 
conjunction with known plaintext-cipher text pairs to derive
key bits.
Where x i (i  0,1, 2, 3) are the bits of the byte x  and x 3 is
 Differential- Linear attack [11]
In this type a differential characteristic is used over part of the most significant bit.
the cipher with a probability of 1 (this probability would be
much lower for the whole cipher for a few rounds). The Case Study :
1
rounds immediately following the differential characteristic Let the design equation of the S-box be 13x  2 of
have a linear approximation defined, and we expect that the GF (24 / x 4  x  1) , then the S-box can be as shown in
probability of the linear approximation that holding for one
Table 1:
chosen plaintext but not the other will be lower for the correct 1
key for each chosen plaintext pair. Table I: S-box of equation 13x  2 of
 Truncated differential attack [12] GF (2 / x  x  1)
4 4

This type of attack is a generalization of differential Input F E D C B A 9 8 7 6 5 4 3 2 1 0

cryptanalysis. In this type, the full difference between two
Output 9 1 5 7 8 E C D B 6 A 3 0 4 F 2
texts is analyzed by ordinary differential cryptanalysis and
the truncated variant considers differences that are only Step 1: The mathematical model of S-box formed as
partially determined. It makes predictions of only some of the follows:[17]
bits instead of the full block.
 Impossible differential attack [13]
This attack is a form of differential attack for block x 3 z 3  x 3  x 0  x 3 z 2  x 1z 0  x 2 z 1  0 , (2)
ciphers. differences ,that propagate through the cipher , that
are impossible (having probability 0) are exploited at some
intermediate state of the cipher algorithm. x 3 z 3  x 3  x 2 z 3  x 2  x 3 z 0  x 0 z 0  x 2 z 2  x 1z 1  0 , (3)
2) Algebraic attack [14]
This type uses polynomials with several variables over finite x 2 z 3  x 2  x 3z 0  x 2 z 0  x 3z 1  x 1z 3  x 1  x 0 z 1  x 1z 2  0 , (4)
field. It depends on converting the encryption system into a
simultaneous multivariate equations system then solve it by
one of algebraic tools such as grobner bases. This type x 3 z 3  x 3  x 3 z 2  x 2 z 1  x 1z 0  x 0 z 3  x 0  z 3  1  0 , (5)
requires very small number of known plaintexts.

III. PRINCIPLE OF LIGHT WEIGHT AES S-BOX x 3 z 3  x 3  x 3 z 0  x 2 z 3  x 2  x 2 z 2  x 1z 1  x 0 z 0  z 0  0 , (6)

Definition 1 (mathematical definition of S-box) [15]

A substitution operation or a m  m S-box (or S-box of x 3 z 0  x 3 z 1  x 2 z 3  x 2  x 2 z 0  x 1z 3  x 1  x 1z 2  x 0 z 1  z 1  0 , (7)
the size m  m ) is a mapping V : F  F ,where m  2
m m
2 2
is a fixed positive integer. A m -argument Boolean function x 3 z 1  x 2 z 0  x 1z 3  x 1  x 0 z 2  z 2  0 , (8)
if a mapping g : F2  F2 . An S-box V : F2  F2 can be
m m m

decomposed into the sequence, V   f 1 , f 2 ,......, f m  of x 3 z 3  x 3 z 2  x 2 z 1  x 1z 0  x 0 z 3  x 0  0 , (9)

Boolean functions such that
V  f 1 , f 2 ,....., f m   (f 1 (x 1 , x 2 ,....., x m ), f 2 (x 1 , x 2 ,....., x m ),....., f m (x 1 , x 2 ,....., x m ))
. We say that the functions f 1 , f 2 ,....., f m are the
components functions of S-box.

Published By:
Retrieval Number: 100.1/ijrte.C4214099320 Blue Eyes Intelligence Engineering
DOI:10.35940/ijrte.C4214.099320 29 and Sciences Publication
 International Journal of Recent Technology and Engineering (IJRTE)
ISSN: 2277-3878, Volume-9 Issue-3, September 2020

x 3 z 3  x 3  x 3 z 0  x 2 z 3  x 2 z 2  x 1z 1  x 0 z 0  0 , (10) The graded reverse lexicographic order: is the order >

such that y
x1
 y x 2 if deg y x 1 > deg y x 2 or
x 3 z 0  x 3 z 1  x 2 z 3  x 2  x 2 z 0  x 1z 3  x 1z 2  x 0 z 1  0 , (11) deg y
x1
= deg y
x2
, and the last non-zero entry of x 1  x 2
is negative.
x 3 z 1  x 2 z 0  x 1z 3  x 1  x 0 z 2  x 0  0 . (12) We have defined each of these so that in every case,
y 1  y 2    y n for R  k  y 1 , y 2 , y 3  , the graded
After making the mathematical model, we should
determine the difficulty of solving these equations by reverse lexicographic order satisfies
using the resistance of algebraic attacks (Γ) which will be y 12  y 1 y 2  y 2 2  y 1 y 3  y 2 y 3  y 32 ,
explained in the next section. While the graded lexicographic order has
y 12  y 1 y 2  y 1 y 3  y 2 2  y 2 y 3  y 32
IV. THE RESISTANCE OF ALGEBRAIC ATTACKS
(RAA) Definition 4 [19]

One S-box with good cryptographic properties can ensure 

Given a monomial order, a Grobner Bases G of a nonzero
the cipher to resist against a variety of cryptanalysis methods, ideal I is a generating set {g 1 , g 2 ,  , g k }  I such that
so any shortcomings of S-box will weaken the security of the for all f  R , f leaves a remainder 0 when divided by G if
cipher. [18] and only if f  I .

Definition 2 [18] Definition 5 [20]

4
Given r equations of t terms in GF (2 ) , the resistance Let
of algebraic attacks (RAA) is denoted by Γ and is defined to lcm (LM (f ), LM ( g )) lcm (LM (f ), LM (g ))
be S (f , g )  f  g (15)
LT (f ) LT (f )
  ((t  r ) / n ) (t  r ) / n (13) Where lcm is the least common multiple, LT is the
leading term, and LM is the leading monomial. This is the
This resistance reflects the difficulty of solving S-polynomial of f and g , where’s’ stands for “Subtraction
multivariate equations system. Thus, in this paper we will use
or Syzygy”.
this quantity ' Γ’ to measure the resistance of the light weight
S-box against algebraic attacks. [18]
Theorem 1 (Buchberger’s Criterion) [20]
Let G  {g 1 , g 2 ,  , g k }  I for some ideal I . If
Step 2:In our case study, n  4 , r  11 and t  24 , so
S ( g i , g j ) gives a remainder 0 when divided by G for all
the resistance will be
pairs g i , g j G , then G is a Grobner
 Bases of I .

  ( 24  11) / 4 
( 24 11)/ 4
 45.09888 (14) Buchberger’s Algorithm
 A monomial ordering is chosen.

Step 3:After estimating 'ᴦ' we will apply Grobner Bases  Starting with any generating set
to this system to be solved. G  {g 1 , g 2 ,  , g k } of I .
 Selecting a pair of generators g i , g j from G .
V. GR o BNER BASES AS A METHOD TO ATTACK  The remainder r when S ( g i , g j ) is divided by
G

Grobner is a classical method used to solve multivariate  If r  0 then continue, otherwise add r to the
nonlinear system of equations. "Buchberger” developed the generating set G .

basic algorithm for computing Grobner Bases in 1965 [19].  Repeating from step 2 until processing all possible
The discovery of this algorithm solved many problems that pairs from G .
needed a computational treatment in commutative algebra, Note that adding generators to G at any time, suddenly
such as deciding whether a polynomial belongs to the ideal many more pairs have to be considered.
generated by some sequence of polynomials [20]. For more 
In our case study, after applying Grobner Bases method to

understanding Grobner Bases, there are some definitions the mathematical model, then the Result will be as follows:
described as follows: (equations16-23)
Definition 3 [19]
The lexicographic order: is the order > such that
y x 1  y x 2 exactly when the first non-zero entry of the
vector x 1  x 2 is positive.
The graded lexicographic order: is the order > such that
y x 1  y x 2 , if deg y x 1 > deg y x 2 or
, and the first non-zero entry of x 1  x 2
x1 x2
deg y =deg y
is positive.

Published By:
Retrieval Number: 100.1/ijrte.C4214099320 Blue Eyes Intelligence Engineering
DOI:10.35940/ijrte.C4214.099320 30 and Sciences Publication
 Different Types of Attacks on Block Ciphers

Table II: Results of the Case Study 10. Matsui, M. (1993, May). Linear cryptanalysis method for DES cipher.
In Workshop on the Theory and Application of Cryptographic
1 z 3  0 , (16)
Techniques (pp. 386-397). Springer, Berlin, Heidelberg.
11. Langford, S. K., & Hellman, M. E. (1994, August). Differential-linear
cryptanalysis. In Annual International Cryptology Conference (pp.
17-25). Springer, Berlin, Heidelberg.
z 2  z 22  0 (17) 12. Lee, S., Hong, S., Lee, S., Lim, J., & Yoon, S. (2001, December).
Truncated differential cryptanalysis of Camellia. In International
Conference on Information Security and Cryptology (pp. 32-38).
z1  0 (18)
Springer, Berlin, Heidelberg.
13. Kim, J., Hong, S., Sung, J., Lee, S., Lim, J., & Sung, S. (2003,
December). Impossible differential cryptanalysis for block cipher
structures. In International Conference on Cryptology in India (pp.
z0 0 (19) 82-96). Springer, Berlin, Heidelberg.
14. Bard, G. (2009). Algebraic cryptanalysis. Springer Science &
Business Media.
15. Improved rijndael-like S-box and its transform domain
x3  0 (20) analysis2006Lecture Notes in Computer Science including subseries
Lecture Notes in Artificial Intelligence and Lecture Notes in
Bioinformatics)153-167
x2 0 (21) 16. Evaluating algebraic attacks on the AES2003Diplom thesis,
Technische
17. Generating S-Box Multivariate Quadratic Equation Systems And
Estimating Algebraic Attack Resistance Aided By SageMath20151-21
x1  0 (22) 18. Resistance of S-boxes against algebraic attacks2004Lecture Notes in
Computer Science (including subseries Lecture Notes in Artificial
Intelligence and Lecture Notes in Bioinformatics)83-93
x0 z2  0 (23) 19. Gröbner bases, Gaussian elimination and resolution of systems of
algebraic equations1983Lecture Notes in Computer Science (including
subseries Lecture Notes in Artificial Intelligence and Lecture Notes in
Bioinformatics)146-156
Then the resistance will be 20. An introduction to Gröbner bases1994American Mathematical Soc.
21. “Algebraic Construction of Powerful Substitution” International
  ( 3  2) / 4 
(3  2)/ 4
 0.707106 (24) Journal of Recent Technology and Engineering (IJRTE) ISSN: 2277
3878, Volume-8 Issue-6, March 2020.
22. -“Performance Analysis of Advanced Encryption Standard (AES)
Hence the ratio of penetrating this S-box is S-boxes “International Journal of Recent Technology and Engineering
98.43209854%. This ratio means that this S-box has (IJRTE) ISSN: 2277-3878, Volume-9 Issue-1, May 2020.
23. ”A Review of Advanced Encryption Standard (AES) Performance”
weak algebraic structure. Benha Journal of Engineering Science and Technology (BJEST) ISSN:
2357-0105, Volume-1 Issue-1, July 2018
VI. CONCLUSION
In this paper, we have introduced different types of AUTHORS PROFILE
attacks on block ciphers .Also, we have used the algebraic Wageda Ibrahim Al Sobky was born in Egypt in
cryptanalysis type to convert the S-box into a system of 1981. She received the [Link]. degree in
communications and computers from benha
multivariate nonlinear equations . After that, we have solved faculty of engineering in 2003. She received the

it by a classical method called Grobner bases . Finally, we [Link]. degree in science from benha faculty of
have made an algebraic attack on the S-box by exploiting its science in 2008. She received the [Link]. in applied
weak algebraic construction. mathematics from Benha University, Cairo,
Egypt, in 2012 and the Ph.D. degree in
cryptography from Ain Shams University, Cairo, Egypt, in 2017. She is
REFERENCES currently a doctor in basic engineering sciences, at Benha Faculty of
Engineering, Benha University, Egypt. Her current research interests include
1. Christof Paar · Jan Pelzl2009Understanding Cryptography: A
data security, and cryptography.
Textbook for Students and PractitionersSpringer Heidelberg Dordrecht
London New York.
Hala Saeed Omar was born in Benha, Egypt in
2. William Stallings2011Cryptography and network security : principles
1993. She received the [Link]. degree in electrical
and practiceFifth edition. Boston Prentice Hall.
power engineering computers from benha faculty of
3. Blondeau, C., & Gérard, B. (2009, May). On the data complexity of
engineering in 2016. She is currently a demonstrator
statistical attacks against block ciphers. In Workshop on coding and
at Benha Faculty of Engineering, Benha University,
cryptography-wcc (Vol. 2009, pp. 469-488).
Egypt.
4. Weinmann, R. P. (2009). Algebraic methods in block cipher
cryptanalysis (Doctoral dissertation, Technische Universität).
5. The Laws of Cryptography with Java Code2003Available online at
Neal Wagner's home page1-334
6. Analysis of Development of Dynamic S-Box
Generation2017Computer Science and Information
Technology154-163
7. Cryptographic analysis of all 4 × 4-bit S-boxes2012Lecture Notes in
Computer Science (including subseries Lecture Notes in Artificial
Intelligence and Lecture Notes in Bioinformatics)118-133
8. Abomhara, M. (2015). Cyber security and the internet of things:
vulnerabilities, threats, intruders and attacks. Journal of Cyber Security
and Mobility, 4(1), 65-88.
9. Lai, X., Massey, J. L., & Murphy, S. (1991, April). Markov ciphers and
differential cryptanalysis. In Workshop on the Theory and Application
of of Cryptographic Techniques (pp. 17-38). Springer, Berlin,
Heidelberg.

Published By:
Retrieval Number: 100.1/ijrte.C4214099320 Blue Eyes Intelligence Engineering
DOI:10.35940/ijrte.C4214.099320 31 and Sciences Publication
View publication stats