Hello, Habr! Here is the translation of the original article “PRESENT: An Ultra-Lightweight Block Cipher” by ~~Robert B. Weide~~ Bogdanov, Lender, Paar, Poshman, Robshav, Seurin and Wikkelsoy.

annotation

With the introduction of AES, the need for new block cipher algorithms has plummeted, since in most cases AES is a great solution. However, despite its ease of implementation, AES is not suitable for extremely limited environments such as RFID tags and readers . This article will describe the ultra-lightweight block encryption algorithm PRESENT. During the development of this algorithm, both the efficiency of implementation in iron and the reliability of encryption were taken into account. As a result, the result of system requirements is comparable to today's leading compact stream ciphers.

1. Introduction

The main course in IT of the current century is the development of small computing devices, which are used not only in consumer products, but also form an integral - and invisible - part of the environment - communication infrastructure. It has already been revealed that such implementations create a whole range of very specific security threats. At the same time, available cryptographic solutions, even rather primitive ones, are often not suitable for use in highly resource-limited environments.

In this article, we offer a new, hardware-optimized block cipher algorithm, developed with the maximum possible size and power limitations. At the same time, we tried to avoid compromising data. To achieve this, we took advantage of DES experience and supplemented the propertiesSerpent as having shown amazing performance in hardware.

Perhaps it’s worth explaining why we decided to develop a new block cipher, because the generally accepted fact is that stream ciphers are potentially more compact. Indeed, in the beginning we made efforts to understand the design of compact stream ciphers in the process of working on the eSTREAM project, as well as several other promising assumptions that seem to be quick-acting. But we noticed several reasons why we nevertheless chose a block cipher. Firstly, block encryption is universal and primitive, and when used in encryption mode, i.e. using the already encrypted blocks to encrypt the following, we get streaming encryption. Secondly, and, perhaps, mainly, the intricacies of the principles of operation of block ciphers seem to be better studied than the principles of operation of stream encryption algorithms. For example, while there is an extensive theory based on the use of shift registers with linear feedback , it is not so easy to combine these blocks in such a way as to get a safe offer. We assume that a neatly designed block cipher may be more secure than a freshly created stream cipher. Thus, we find that a block cipher that requires as much iron resources as a compact stream cipher can be very interesting.

It is important to note that when creating a new block cipher algorithm, especially with eye-catching performance, we do not just pursue innovation. On the contrary, the development and implementation of the cipher goes hand in hand, revealing some fundamental limits and inherent limitations. For example, a given level of security imposes restrictions on the minimum key and block lengths. Even processing a 64-bit state with an 80-bit key limits the minimum device size. You can also notice that the embodiment in hardware - especially the compactness of the hardware implementation - contributes to repeatability. Even small changes can adversely affect the volume of the device. However, cryptanalysts also value repeatability and look for mathematical structures that easily multiply in many rounds.So how many simple repeating structures can be used without compromising system security?

So, this article will describe the compact block cipher PRESENT. After a short review of the existing literature, we designed the rest of the article in a standard form. The code is described in section 3, in section 4 design decisions are described. In section 5 we will consider security, while section 6 will contain a detailed analysis of performance. This work ends with our conclusions.

2. Existing works

While the volume of work devoted to cheap cryptography is constantly growing, the number of articles devoted to super-light ciphers is surprisingly small. Moving focus to the protocol device, we will no longer refer to works on cheap communication and identification protocols. One of the most extensive work on compact implementation is currently associated with the eSTREAM project. As part of one part of this project, new stream ciphers adapted for effective implementation in hardware were proposed. In the course of this work, promising candidates are outlined. So far, the ratios are approximate, but it follows from the implementation brochures that compact ciphers of the eSTREAM project will require about 1300-2600 GE (Gate equivalents) .

Among the block ciphers, one of the widely known, namely DES, was created taking into account the efficiency of the equipment. Bearing in mind the very limited state of semiconductors in the early 1970s, it is not surprising that DES has very competitive implementation properties. During development, 3000GE was spent on DES, and after serialization, this number dropped to 2300GE. However, the DES key length limits its usefulness in many applications and leads to the fact that specialized modifications are developed on its basis, for example, with increased cryptographic strength or an extended key.

Regarding modern block ciphers, this article provides a thorough analysis of low-cost AES. However, its implementation requires about 3,600 GE, which is an indirect consequence of the design of fines for 8- and 32-bit processors. The system requirements <a href = " TEA are not known, but according to estimates they require about 2100 GE. There are 4 more solutions that are designed for low-cost equipment: mCRYPTON (has an exact execution of 2949 GE), HIGHT (about 3000 GE), SEA (about 2280 GE) and CGEN (also about 2280 GE), despite the fact that the latter was not conceived as a block cipher.

3. Block cipher PRESENT

PRESENT is a special case of the SP network and consists of 31 rounds. The block length is 64 bits, and the keys are supported in 2 versions, 80- and 128-bit. This level of protection should be enough for low-security applications that are usually used for deployment based on tags, and in addition, more importantly, PRESENT largely coincides in its design features with stream ciphers of the eSTREAM project, sharpened for effective implementation in hardware, which allows us to adequately compare their.
Security requirements and operational properties of 128-bit versions are provided in the appendix to the original article.

Each of the 31 rounds consists of an XOR operation to enter the key K _i for 1 ≤ i ≤ 32, where K _{32 is} used for“Bleaching” the key , linear bitwise permutation and non-linear substitution layer (or, more simply, increasing the strength of encryption). The non-linear layer uses separate 4-bit S-blocks , which are applied in parallel 16 times in each round. The cipher described by the pseudo-code is shown in the figure:

Now each stage is determined in turn. The design justifications are given in Section 4, and bits are numbered everywhere from scratch, starting with the right one in a block or word.

Adding a round key (addRoundKey). The round key K _i = k ⁱ₆₃ ... k ⁱ₀ , where 1 ≤ i ≤ 32, as well as the current state b ₆₃ ... b ₀. Adding a round key to the current state occurs modulo 2 (b _j = b _j ⊕ k ⁱ_j , where 0 ≤ j ≤ 63).

S-Box Layer (sBoxlayer). The S-blocks used in PRESENT map 4-bit blocks to 4-bit blocks. The action of this block in the hexadecimal number system is shown in the following table:

For the S-block layer, the current state b ₆₃ ... b ₀ is 16 4-bit words w ₁₅ ... w ₀ , where w _i = b _{4 * i + 3} || b _{4 * i + 2} || b _{4 * i + 1} || b _{4 * i} for 0 ≤ i ≤ 15. Frame output S [w _i] returns updated state values in an obvious way.

Permutation layer (pLayer). Bitwise permutation used PRESENT defined in the following table (the state of bit i is shifted to the position P (i)):

Key Conversion ( The key schedule ). PRESENT can use 80- and 128-bit keys, however, we will focus on the 80-bit version. The key provided by the user is stored in the key register K, represented as k ₇₉ k ₇₈ ... k ₀ . On the i-th round, a 64-bit round key K _i = k ₆₃ k ₆₂ ... k ₀, consisting of 64 left bits of the current contents of register K. Thus, in the i-th round we have:
K _i = k ₆₃ k ₆₂ ... k ₀ = k ₇₉ k ₇₈ ... k ₁₆ .

After unpacking the round key K _{i, the} key register K = k ₇₉ k ₇₈ ... k _{0 is} updated as follows:
1. [k ₇₉ k ₇₈ ... k ₁ k ₀ ] = [k ₁₈ k ₁₇ ... k ₂₀ k ₁₉ ]
2. [k ₇₉ k₇₈ k ₇₇ k ₇₆ ] = S [k ₇₉ k ₇₈ k ₇₇ k ₇₆ ]
3. [k ₁₉ k ₁₈ k ₁₇ k ₁₆ k ₁₅ ] = [k ₁₉ k ₁₈ k ₁₇ k ₁₆ k ₁₅ ] ⊕ round_counter

Therefore, register the key is shifted 61 positions to the left, the 4 leftmost bits passed through the S-block and round_counter the value of i is added modulo 2 with bits k ₁₉ k ₁₈ k ₁₇ k ₁₆ k ₁₅from K with the least significant bit from round_counter to the right.

A key conversion for a 128-bit algorithm can be found in the appendix to the original article.

4. Design features of PRESENT

In addition to security and efficient implementation, the main achievement of PRESENT is its simplicity. therefore, it is not surprising that similar projects were adopted in other circumstances, and were even used as a textbook for students. In this section, we will justify the decisions we made when designing PRESENT. However, first of all, we describe the expected application requirements.

4.1. Purpose and application environment

When designing a block cipher that is applicable in tightly constrained environments, it is important to understand that we are not creating a block cipher that will certainly be applicable in many situations - there is AES for this. On the contrary, we are aimed at a very specific application for which AES is not suitable. The foregoing determines the following characteristics.

The cipher will be implemented "in hardware"
Applications will only be required to adjust the security level. Therefore, an 80-bit key would be a robust solution. Note that the developers of stream ciphers of the eSTREAM project adhere to the same position.
Applications do not require encryption of large amounts of data. Thus, an implementation can be optimized for performance or space without making too much change.
, . , ( ).
, , , , , .
, , (encryption-only mode). , - (challenge-response) , , , , .

Based on such considerations, we decided to create PRESENT as a 64-bit block cipher with an 80-bit key. Encryption and decryption, in this case, have approximately the same physical requirements. With the ability to support both encryption and decryption, PRESENT will be more compact than supporting only AES encryption. And in the case of encryption-only execution, our cipher will be completely super-easy. Encryption sub-keys will be computed on the go.

There are many examples in the literature of attacks of compromise between time, date and memory , or attacks using the birthday paradoxwhen encrypting large amounts of data. However, these attacks depend only on the parameters of the cipher and do not use the internal structure. Our goal is to make these attacks the best they can use against us. Third-party channel attacks and direct chip-breaking attacks threaten PRESENT as much as other cryptographic primitives . However, for probable applications, moderate security requirements make the benefits to an attacker in practice very limited. In risk assessment, such threats are not perceived as a significant factor.

4.2. Permutation layer

When choosing a key mixing layer, our attention to hardware efficiency requires a linear layer, which can be implemented with a minimum number of control elements (for example, transistors). this leads to a bitwise permutation. Paying attention to simplicity, we chose regular bitwise permutation, which helps to conduct a transparent security analysis (see section 5).

4.3. S-blocks.

At PRESENT, we use separate S-blocks that translate 4 bits to 4 bits (F ⁴₂ → F ⁴₂ ). This is a direct consequence of our desire for hardware efficiency, and the implementation of such an S-block is usually much more compact than that of an 8-bit S-block. Since we use bitmap permutation for a linear diffusion layer, AES-like diffusion technologies are not an option for our cipher. Therefore, we place some additional conditions on S-blocks in order to reduce the so-called “avalanche effect” . More precisely, the S-blocks for PRESENT satisfy the following conditions, where we denote the Fourier coefficient S by

S ^W_b (a) = ∑ (-1) ^{<b, S (x)> + <a, x>} , x∈F ⁴₂

1. For any fixed nonzero input bias ∆ _I ∈ F ⁴₂ and any fixed nonzero input bias ∆ _O ∈ F ⁴₂ inside the S-block, we require
# {x ∈ F ⁴₂ | S (x) + S (x + ∆ _I ) = ∆ _O } ≤ 4.

2. For any fixed nonzero input difference ∆ _I ∈ F ⁴₂ and any fixed nonzero output difference ∆ _O ∈ F ⁴₂ such that wt (∆ _I ) = wt (∆ _O ) = 1 , we have
{x ∈ F ⁴₂| S (x) + S (x + ∆ _I ) = ∆ _O } = ∅

3. For all nonzero a ∈ F ⁴₂ and all nonzero b ∈ F _{4 it} holds that | S ^W_b (a) | ≤ 8
4. For all nonzero a ∈ F ⁴₂ and all nonzero b ∈ F ₄ such that wt (a) = wt (b) = 1, S ^W_b (a) = ± 4 holds.

As will be clear from section 5, these conditions ensure that PRESENT is resistant to differential and linear attacks. Using the classification of all 4-bit S-blocks satisfying the above conditions, we have chosen the S-block, which is especially suitable for efficient hardware implementation.

5. Security Analysis

Now we will present the results of the PRESENT security analysis.

Differential and linear cryptanalysis

Differential and linear cryptanalysis are some of the most powerful methods available to cryptanalysts. To measure the PRESENT resistance to differential and linear cryptanalysis, we set the lower bound on the number of so-called active S-blocks participating in the differential (or linear) characteristic.

Differential cryptanalysis

The case of differential cryptanalysis is covered by the following theorem.

Theorem 1. Any five-circuit differential characteristic of PRESENT has at least 10 active S-blocks.

Theorem 1 is proved in Appendix 3 of the original article, and we continue the observations. We divide 16 S-blocks into 4 groups:

_{The numbers at the input (above) indicate the number of the S-block at the previous step, and at the output (at the bottom) - at the next}

Note that:

The input bits to the S-block come from 4 different S-blocks of the same group.
Input bits for groups of four s-blocks come from 16 different s-blocks.
Four output bits from a particular S-block are included in four different S-blocks, each of which belongs to a separate group of S-blocks in the next round.
The output bits of s-blocks in different groups go to different s-blocks.

According to Theorem 1, any differential characteristic for more than 25 rounds of PRESENT must have at least 5 × 10 = 50 active S-blocks. The maximum differential probability of the PRESENT S-block is 2 ^-2 , and therefore the probability of a single 25-round differential characteristic is limited to 2 ^-100. Advanced methods allow the cryptanalyst to remove external rounds from the cipher in order to use a shorter characteristic; however, even if we allow an attacker to remove six rounds from the cipher, which is an unprecedented situation, the data required to use the remaining 25-round differential characteristic will exceed the available amount. Thus, security boundaries are more than reliable. However, we have practically confirmed that the boundary of the number of active S-blocks in Theorem 1 is tight.

Practical confirmation

We can define characteristics that include ten S-blocks over five rounds. The next two-round iterative characteristic includes two S-blocks per round and holds with a probability of ^2–25 for five rounds.

More complex characteristics are held with a probability of 2 ^-21 for 5 rounds.

Although the probability of this second characteristic is very close to the boundary of 2 ^-20It is not iterative and has little practical value. Instead, we experimentally confirmed the likelihood of a two-round iterative differential. In experiments with more than 100 independent sub-keys using 223 selected plaintext pairs, the observed probability was predicted. This seems to suggest that for this particular characteristic there is no concomitant significant differential. However, determining the extent of any differential effect is a complex and time-consuming task, even though our preliminary analysis was encouraging.

Linear cryptanalysis

The case of linear PRESENT cryptanalysis is considered in the following theorem, in which we analyze the best linear approximation to the four rounds of PRESENT.

Theorem 2. Let E _4R be the maximum linear displacement of the four-round approximation using PRESENT. Then E _4R ≤ 2 ^-7 .
The proof of the theorem is contained in Appendix 4 of the original article. Then for 28 rounds the maximum displacement will be
2 ⁶ × E _4R⁷ = 2 ⁶ × (2 ^-7 ) ⁷ = 2 ^-43

Therefore, assuming that a cryptanalyst only needs about 28 of the 31 rounds in PRESENT to initiate a key recovery attack, a linear cryptanalysis of a cipher will require about 2 ⁸⁴ known plaintexts / ciphertexts. Such data requirements exceed the available text.

Some advanced differential / linear attacks

The PRESENT structure allows us to consider some of the distinguished forms of attacks. However, none of them led to an attack requiring less text than the lower bound of the text requirements for linear cryptanalysis. Among the distinguished attacks, we considered one that uses palindromic differences, since symmetric differences persist with a probability of one (i.e. always) over the diffusion layer, and some advanced versions of differential-linear attacks. Although the attacks seemed promising for several rounds, they quickly lost their practical value and are unlikely to be useful in PRESENT cryptanalysis. We also found that truncated differential cryptanalysis is likely to be of limited value, although the next two rounds.

Truncated expansion is performed with a probability of one.

Even when used to reduce the length of the already identified differential characteristics, the data requirements remain excessive. Ranked expansion is performed with a probability of one.

5.2. Structural attacks

Structural attacks, such as integrated cryptanalysis and bottleneck analysis, are well suited for analyzing AES-like ciphers. Such ciphers have strong word-like structures, where the words are usually bytes. However, the representation construction is almost exclusively bitwise, and although the permutation operation is somewhat regular, the development and distribution of word structures are disrupted by the bitwise operations used in the cipher.

5.3. Algebraic attacks

Algebraic attacks were used to lshy success when applied to stream ciphers, than to block. However, the simple structure of PRESENT means that they deserve serious study. The PRESENT S-block is described by 21 quadratic equations for eight input / output bit variables over field G (2). This is not surprising, since it is well known that any four-bit S-block can be described by at least 21 such equations. Then the entire cipher can be described by quadratic equations e = n × 21 in the variables v = n × 8, where n is the number of S-blocks in the encryption and key transformation algorithm.

For PRESENT, we have n = (31 × 16) + 31 so the whole system consists of 11,067 quadratic equations in 4,216 variables. The general problem of solving a system of multidimensional quadratic equations is NP-hard. However, the systems obtained for block ciphers are very rare, since they consist of n small systems connected by simple linear layers. However, it is not clear whether this fact can be used in the so-called algebraic attack. Some specialized methods have been proposed, such as XL and XSL, although shortcomings have been discovered in both methods. Instead, the only practical results on algebraic cryptanalysis of block ciphers were obtained by applying the Buchberger and F4 algorithms.as part of Magma. Modeling on small-scale versions of AES showed that for all but the smallest SP-networks , difficulties quickly arise in both time and memory complexity. The same goes for PRESENT.

Practical confirmation.We conducted simulations on small-scale versions using the F4 algorithm in Magma. When there is one S-block, that is, a very small block with a size of four bits, Magma can solve the resulting system of equations in many rounds. However, as the block size increases and S-blocks are added, along with the corresponding variant of the linear diffusion layer, the system of equations soon becomes too large. Even when considering a system consisting of seven S-blocks, that is, having a block size of 28 bits, we were not able within a reasonable time to get a solution for the abbreviated cipher variant that passed two rounds. Our analysis shows that algebraic attacks are unlikely to pose a threat to PRESENT.

5.4. Key conversion attacks

Since there are no established guidelines for the development of key transformations, there is both a wide variety of projects and a wide variety of attacks based on the characteristics of the project. The most effective attacks fall under the general heading of attack on related keys and shear attack , and both are based on the construction of identifiable relationships between different sets of sub-keys. To counter this threat, we use a round-dependent counter, so that sub-key sets cannot be easily “shifted”, and we use a non-linear operation to mix the contents of key register K. In particular:

all bits in the key register are a non-linear function of the 80-bit key supplied by the user to round 21,
that each bit in the key register after round 21 depends on at least four of the user-provided key bits, and
by the time we get K ₃₂ , six bits are expressions of degree two out of 80 user-provided key bits, 24 bits are degree three, while the remaining bits are a function of degree six or degree nine user-provided key bits.

We believe that these properties are enough to withstand key attacks based on key conversion.

6. Productivity of "iron"

We implemented PRESENT-80 in VHDL and adapted it for the standard Virtual Silicon Cell Library (VST) based on the UMC L180 0.18 μ 1P6M Logic. We used the Mentor Graphics Modelsim SE PLUS 5.8 c for simulation and Synopsys Design Compilerversion Y-2006.06 for the synthesis and modeling of power consumption. Typical values for foundry were used (1.8 Volts for core voltage and 25 ° C for temperature), and the proposed model of wire loading was used to model power. Please note that such a simulation is intended for structures around 10,000 GE, so power results will be pessimistic for much smaller structures. On the image

The data path shown is space-optimized PRESENT-80 without the possibility of decryption (encryption-only), which performs one round per cycle, that is, a data path of 64-bit width. Please note that at the PRESENT design stage, we use the same S-block 16 times instead of having 16 different S-blocks, and this facilitates the further serialization of the project, i.e. with a 4-bit data channel. Our implementation requires 32 clock cycles for encrypting 64-bit plaintext with an 80-bit key, takes 1570 GE and has a 5 micW power consumption in modulation.

^{Spatial requirements PRESENT}

Most of the area is occupied by triggers for storing the key and data state, followed by the S-layer and the XOR keying department. Simple permutation bit permutations will increase the area only when the implementation reaches the place & route stage. Note that the main goal of our implementation was a small amount of hardware, however, we also synthesized a process optimized for power. For an additional 53 GE, we achieve energy consumption of only 3.3 μW, and the current 128 will occupy an estimated area of 1886 GE. In addition to its very small size, PRESENT has a fairly high throughput, giving good energy per bit. Comparison with other ciphers is given in the table:

7. Conclusion

In this article, we described the new PRESENT block cipher. Our goal was an ultralight cipher, which provides a level of security commensurate with the size of a 64-bit block and an 80-bit key. As a result, PRESENT has implementation requirements similar to many compact stream ciphers. Therefore, we believe that it is of both theoretical and practical interest. Like all new proposals, we do not encourage the immediate deployment of PRESENT, but urge its analysis.

Confession

The work presented in this document was partially supported by the European Commission as part of the STREP UbiSec & Sens of the EU Framework Program 6for Research and Development (www.ist-ubisecsens.org). The opinions and conclusions contained in this document are those of the authors and should not be interpreted as constituting an official policy or endorsement expressed or endorsed by the UbiSec & Sens project or the European Commission.

PRESENT - Ultra-Lightweight Block Encryption (translation of the original PRESENT: An Ultra-Lightweight Block Cipher)