On some attacks on block ciphers

Attacks on block ciphers can be classified according to the goal of the attacker.

For example, in akey recovery attackthe objective is to get the secret key. In a distinguishing attack, the goal is to distinguish whether the output is a random sequence or the result of the encryption process.

Attacks can also be classified based on the amount of information that the adversary has access to. In this case, three different models are defined.

• Theblack-box attacker model. In this scenario we assume that the attacker has complete knowledge of the algorithm used for encrypting (and de-crypting) but it has no knowledge of the key used. We assume that the attacker can observe some pairs of inputs and/or corresponding outputs but he has no further knowledge beyond it. In some scenarios we assume furthermore that the attacker can choose the value of some inputs or out-puts. Until recently, this model was the only one considered by cryptog-raphers.

• The gray-box attacker model. An attack belonging to this model is also called a side-channel attack. In this scenario, the adversary has physical access to the device which performs the cryptographic operations. There-fore all the side channel information leaked during the execution of the algorithm can be collected and analysed. The leakages can correspond to power consumption, temperature change, running-time, electromagnetic emanation, etc. Usually, the attacker tries to perform an attack on the first or the last round of the block cipher.

• Thewhite-box attacker model. In this scenario the attacker has knowledge of every information except the secret key. This includes all the intermediate values of the algorithms. The set of the intermediate values of a block cipher consists of the outputs of each function involved in every round of the block cipher.

Different techniques are required to make a block cipher robust against attacks from different models. In general, the security of a block cipher strongly de-pends on the S-boxes implemented in the algorithms. Many scientists and re-searchers have focused their work on these functions with particular interest on good cryptographic properties. They defined mathematical properties of the S-box that measure its resistance, and therefore that of the entire cipher, to some of these attacks. In the following we give a brief idea of two attacks from the black-box model, which have a connection with the work presented in the next chapters.

2.1 Cryptography and cryptographic primitives 15 The differential attack, introduced by Biham and Shamir [12] in 1990, is among the most efficient attacks on block ciphers. The attack is based on the study of how differences between two inputs can affect the resulting differ-ences at the output. To be effective, it assumes that there exists an ordered pair(a,b),a6=0, of sequences of bits satisfying the following property: form a random block of the plaintext, c=E_k(m) andc⁰=E_k(m⊕a), the sequence c⊕c⁰ has a larger probability to equal bthan ifc andc⁰ are sequences of bits randomly chosen. In [92] Nyberg introduced the notion of differential unifor-mity, which measures the resistance of an S-box to this attack. The smaller the differential uniformity, the better resistance the S-box has. Such property is obtained by studying the behaviour of the S-box Sin the situation described in Figure2.4. Boolean functions that achieve the best resistance are called

al-Figure 2.4: The differential attack at the S-box level

most perfect nonlinear, shortly APN. The role of APN functions is not restricted only to cryptography. For example, in coding theory such optimal functions define optimal, in a certain sense, binary error correcting codes [44]. In pro-jective geometry, quadratic APN functions define dual hyperovals [104] and they also have connections with the theory of commutative semifields [49]. For functions defined over fields of odd characteristic, optimal differential unifor-mity is achieved byperfect nonlinear(PN) functions, also calledplanarfunctions.

In 1999 Wagner [101] introduced the boomerang attack, an important crypt-analysis technique against block ciphers. This attack can be seen as an exten-sion of the differential attack. In fact, it combines two differentials for the upper part and the lower part of the cipher. More precisely, the cipherEis considered as the composition of two sub-ciphersE1andE2. ForE1the attacker considers

a differential(a,d)with probabilityp, forE2a differential(c,b)with probabil-ity q, see Figure2.5. Then the attack is based on the following estimation of probability:

Pr[E⁻¹(E(x)⊕b)⊕E⁻¹(E(x⊕a)⊕b)) =a]≈p²q². (2.1) Since Wagner’s seminal paper, many improvements and variations of boomerang attacks have been proposed (see for instance [11,13,78]). One of them is the sandwich attack, proposed in [63]. In this attack the cipher is further decom-posed asE=E2◦Em◦E₁, whereEmis typically one round (or one S-box layer) of the cipher, see Figure2.6. Then the sandwich attack is based on the

estima-Figure 2.5: The boomerang attack Figure 2.6: The sandwich attack

tion of probability in (2.1) multiplied by

Pr[E⁻_m¹(Em(x)⊕c)⊕E⁻_m¹(Em(x⊕d)⊕c) =d]. (2.2) In order to evaluate the feasibility of boomerang-style attacks, Cid et al. in-troduced in EUROCRYPT 2018 [46] a new cryptanalysis tool: the Boomerang Connectivity Table (BCT). Later in 2018, Boura and Canteaut [16] introduced a parameter for cryptographic S-boxes calledboomerang uniformity. It is defined as the maximum value in the BCT and it measures the resistance of the S-box against the boomerang attack. Figure2.7shows how the BCT at entry (a,b) is obtained for an invertible S-boxS. Notice that it corresponds to the