Lightweight block ciphers

From CryptoWiki
Jump to: navigation, search

Block cipher - a kind of a symmetric cipher, which through constant mapping (usually) processes information blocks (often 64 or 128 bits). "Lightweight" block cipher is different from the block so that it uses the algorithms that require less computing power.

Below is a list of the most popular to date block of lightweight cryptographic algorithms.

This article is one the divided articles of the entry called "Lightweight" ciphers; so reading it has a recommendation character for the deeper understanding of the criteria of this kind of algorithms, the spheres of its' implementations as well as their pros and cons.

Return to the table of contents

Contents

Present

The block length of PRESENT is 64 bits and the key sizes are 80 or 128 bits. There are 32 rounds in PRESENT. 31 rounds consists of XOR operation to form a round key and the 32nd round is used for post whitening. Each of the 31 rounds consists of a non linear substitution layer and a linear permutation layer. The main module of the cipher is given below.

Mrd lightweight7 en.png
Picture 1 — Main module of PRESENT [J12].

addRoundKey performs the following operation Mrd lightweight1.png where j varies from 0 to 63 and I varies from 1 to 32. sBoxlayer performs a conversion from 4 bit to 4 bit. This is more compact than an 8-bit S Box which gives more hardware efficiency. pLayer performs the movement of bit i to a bit position P( i ). The key given by the user is stored in key register K. Mrd lightweight2.png contains left most 64 bits of K. Thus at round i, Mrd lightweight3.png. Then the key register is updated as follows. Mrd lightweight4.png Mrd lightweight5.png The key is rotated by 61 bit positions to the left , left most 4 bits are passed through the S Box and the round counter value i is XORed with bits Mrd lightweight6.png of K with the least significant bit of round counter on the right.

This algorithm is well protected from attacks based on the associated keys, slide attacks and other common methods of attacks on cryptosystems.

GOST 28147-89

Russian block encryption standard GOST 28147-89 [GOST 28147-89] has been known for more than twenty years and considered resistant algorithm an appropriate choice of replacement units. Simple design and low hardware requirements allowed using quite effectively on platforms with limited resources.

Mrd lightweight gost1.png
Picture 2 — GOST 28147-89 round (left) S-block detailed sheme [P10]

GOST has a block size of 64 bits and a key size of 256 bits. Its overall structure - two Feistel network with 32 rounds and internal function roundfunction F, consisting of the addition, the non-linear replacement and 11-bit cyclic shift to the left. Let 64-bit data state of GOST set as a Mrd lightweight gost2.png - denotes the union, then Mrd lightweight gost3.png is a plain text and Mrd lightweight gost4.png - ciphertext. The right half of the sum Ri modulo 32 with roundKey Mrd lightweight8.png, the result is divided by eight 4-bit subsequences, each of which is input to the other unit replace table (in ascending order of precedence bits), referred to below as S- unit and finally cyclically shifted by 11 bits to the left. The result of round function F (Mrd lightweight8.png, Mrd lightweight gost5.png) is added to the left half of Mrd li.png, and is stored in the right side as a result of Mrd lightweight gost6.png, while Mrd lightweight gost7.png retained without any changes. Obtained

Mrd lightweight gost8.png,

where denotes the bitwise XOR and << a - a cyclic shift to the left as well. In the final round, the halves do not change: Mrd lightweight gost9.png. This makes it possible to use the reverse algorithm to decrypt. In [D14] described the implementation of this cipher with lightweight implementation. Here is a brief excerpt from the description. The cryptographic algorithm GOST 28147-89 used mapping Mrd lightweight gost10.png, where P - plaintext, K - key, Mrd lightweight gost11.png, C - ciphertext. With fixed key 'K' maping 'F' provides a bijective transformation of the set Mrd lightweight gost17.png and become the product of 32 mappings: Mrd lightweight gost12.png.Hereinafter in throughout the product transformations are applied to the argument in sequence from left to right, that is,

Mrd lightweight gost13.png.

Mapping Mrd lightweight gost14.png, (i iteration) iteration iteration is dependent on key Mi and is defined as follows: Let the mapping

Mrd lightweight gost15.png,

defined by the following formulas: Mrd lightweight gost16.png, Mrd lightweight gost18.png, L - linear transformation of Mrd lightweight gost19.png, which is a cyclic shift to the left (senior co-ordinates) by 11 positions P - non-linear transformation of the space Mrd lightweight gost19.png, is implemented using eight parallel operating permutations of binary vectors of length 4: Mrd lightweight gost20.png. [] - Modulo Mrd 232.png. Suppose also that the mapping Mrd lightweight gost22.png given by Mrd lightweight gost23.png. Then Mrd lightweight gost24.png. Thus, the mapping F can be written as follows: Mrd lightweight gost25.png. Iterative keys Mrd lightweight gost26.png, equal Mrd lightweight gost27.png to Mrd lightweight gost28.png.

Isobe method and Dinur-Dunkelman-Shamir method.

Isobe method uses the fact that the iterative algorithm keys GOST iterations 1-8, 9-16, 17-24 are used in the order Mrd lightweight gost29.png, and in iteration 25-32 in reverse - Mrd lightweight gost30.png. Given the permutation final 32-bit half-blocks T, and its transformation commutes with F ^ *, and the fact that the GOST 28147-89, as in any other scheme Feistel decryption represents Encoding, but with iterative key taken in reverse, we find that the encoding of plaintext P for any fixed key Mrd lightweight gost31.png has the following form Mrd lightweight gost32.png, where the G = G (K) is a substitution implemented the first eight iterations of the algorithm GOST for fixed K . Substitution Mrd lightweight gost33.png like (for any value of the key Mrd lightweight gost29.png) the substitution T, and therefore has the same cyclic structure. At exactly substituting T Mrd 232.png fixed points of the form Mrd lightweight gost34.png. Thus, the conversion of Mrd lightweight gost33.png and Mrd 232.png fixed points. Let Mrd lightweight gost36.png - fixed point of Mrd lightweight gost33.png, then if for some Mrd lightweight gost35.png, it means that Mrd lightweight gost37.png, that is, in this case, the encryption algorithm GOST 32 iterations 16 iterations equivalent encryption algorithm. In [I11] This property is called the algorithm of GOST 28147-89 property reflection (reflection-property). At random equiprobable choice of plaintext P likely to get into a fixed point Mrd lightweight gost40.png is Mrd 232.png. If Mrd lightweight gost40.png - fixed point, then further to the conversion of Mrd lightweight gost41.png used the so-called R-MITM attack (reflection-meet-in-the-middle-attack) with complexity [ [File: mrd_lightweight_gost42.png]] encoding operations. Total labor Isobe method of Mrd lightweight gost43.png encoding operations with the necessary material Mrd 232.png famous pair of open-ciphertext with a success rate of 0.63. In [D11] Dinur, Dunkelman and Shamir were offered two methods of determining the key algorithm GOST, which essentially are a further development of the method Isobe. They are based on the use of the method in the middle of the meeting for a couple of open-ciphertext than 16 iterations in the method Isobe, and two pairs of open-ciphertext 8 iterations. The first method uses the following fact. Let the encryption algorithm GOST plaintext P after the first 8 iterations goes to itself (P fixed point for the first eight iterations), then exit after 24 iterations will continue to P, and the yield after 32 iterations - some ciphertext C. Then, taking into account a key scan algorithm GOST obtain two input-output pair 8 iterations' '(P, P)' 'and' '(∈, P)' '(' '∈' 'and' 'P' 'derived from' C and P rearrangement of 32-bit half-blocks). At random equiprobable choice of the key probability that the P - fixed point iterations for 8 Standard is Mrd lightweight gost44.png. Consequently, the likelihood that all available material in the Mrd lightweight gost47.png meet fixed point iterations for 8 Mrd lightweight gost45.png. The total complexity of the method is Mrd lightweight gost46.png encoding operations with the necessary material Mrd lightweight gost47.png famous pair of open-ciphertext with probability. Success 0.63 . The second method uses the material in the Mrd 232.png, to the probability 0.63 to get a fixed point for the transformation Mrd lightweight gost33.png. Suppose we have a fixed point Mrd lightweight gost40.png to show Mrd lightweight gost33.png. Then we have the matching Mrd lightweight gost48.png between input and output for 16 iterations of the algorithm of GOST 28147-89. The amount of Mrd lightweight gost47.png options we can sort out Z - yield after 8 iterations GOST, therefore, we will have available 2 matching Mrd lightweight gost49.png and Mrd lightweight gost50.png between input and output of the algorithm GOST 8 iterations. After that, the method of meeting in the middle for 8 iterations GOST. The complexity of the method Mrd lightweight gost51.png encoding operations, the material Mrd 232.png famous pair of open-ciphertext, the success rate of 0.63. The memory required for the performance of the method is reduced from Mrd lightweight gost47.png to address Mrd236.png by the so-called technology "guess and is determined» (guessanddetermine), which is to build the tree of possible keys Partial enumeration values.

GOST 28147-89 modification

Isobe method and both of Dinur, Dunkelman and Shamir methods use GOST 28147-89 key scan simplicity, therefore, the proposed modification of the algorithm should first of all have a different key scan. New scan should not substantially impair the performance characteristics of the algorithm (including the possibility of an effective lightweight implementation). It was therefore decided to maintain the principle with the number of iterations Mrd lightweight gost53.png, iterative key Mrd lightweight gost54.png for some Mrd lightweight gost55.png. Table 2 shows the scan of key to modified algorithm GOST 28147-89. In the table at the intersection of the line with the number of Mrd lightweight gost56.png, and the column number Mrd lightweight gost57.png is an iterative key.

Table 1 - GOST 28147-89 modified algorithm scan of key [P10]

i/j 1 2 3 4 5 6 7 8
0
Mrd lightweight k0.png
Mrd lightweight k1.png
Mrd lightweight k2.png
Mrd lightweight k3.png
Mrd lightweight k4.png
Mrd lightweight k5.png
Mrd lightweight k6.png
Mrd lightweight k7.png
1
Mrd lightweight k3.png
Mrd lightweight k4.png
Mrd lightweight k5.png
Mrd lightweight k6.png
Mrd lightweight k7.png
Mrd lightweight k0.png
Mrd lightweight k1.png
Mrd lightweight k2.png
2
Mrd lightweight k5.png
Mrd lightweight k6.png
Mrd lightweight k7.png
Mrd lightweight k0.png
Mrd lightweight k1.png
Mrd lightweight k2.png
Mrd lightweight k3.png
Mrd lightweight k4.png
3
Mrd lightweight k5.png
Mrd lightweight k6.png
Mrd lightweight k7.png
Mrd lightweight k0.png
Mrd lightweight k1.png
Mrd lightweight k2.png
Mrd lightweight k3.png
Mrd lightweight k4.png
4
Mrd lightweight k6.png
Mrd lightweight k5.png
Mrd lightweight k4.png
Mrd lightweight k3.png
Mrd lightweight k2.png
Mrd lightweight k1.png
Mrd lightweight k0.png
Mrd lightweight k7.png

Set of replacement units is a key element and a long-term by the standard is not defined. At the same time, usually in the cryptographic analysis algorithm GOST 28147-89 replacement of a set of units is considered known. Therefore it is possible to select as a set consisting of all the various permutations and those in which all substitutions are the same. It was therefore decided in the modified algorithm GOST 28147-89 to use two different substitution Mrd lightweight gost59.png, Mrd lightweight gost60.png, where Mrd lightweight gost61.png, and Mrd lightweight gost62.png. Substitutions Mrd lightweight gost63.png and Mrd lightweight gost64.png taken from sets previously submitted by ISO in the international standardization.

Clefia

CLEFIA - encryption algorithm, developed by Sony as a safe alternative to AES for the scope of copyright protection and DRM-systems (Digital rights management - software or firmware that are intended to limit or impede a variety of actions with the data in electronic form, such as the protection of works copy and other actions prohibited by the authors or other copyright holders on the basis of copyright or related rights after the sale to the end user). The algorithm consists of two component parts: a key part of the schedule and data processing portion. Algorithm complies with the cipher AES: Block Size - 128 bits (16 bytes) supported key lengths - 128, 192 and 256 bits. The number of rounds dependent on the key length and is respectively 18, 22 or 26 rounds and 36, 44 and 52 of round keys used. Driving encryption algorithm Clefiapokazana ricunkah at 5-6, settings, and the attack on the algorithm shown in Tables 2-3.

Mrd clefia.png
Picture 3 — Clefia encryption algorithm scheme [QB]
Mrd clefia1.png
Picture 4 — Clefia encryption algorithm scheme [QB]
Table 2 — Clefia algorithm key length 128, 192, 256 parameters [J12]
Key Cycles on the block Throughput

(at 100KHz)[Kbps]

Count Efficiency Current
128 36 355,6 4950 71,83 N/A
128 18 711,11 5979 118,93 N/A
192 22 581,8 8536 68,16 N/A
256 26 492,3 8482 58,04 N/A
Table 3 — The attacks on the algorithm Clefia [J12]
number of rounds
Complexity
Stuff[ciphertexts] Time [cycles] Memory [blocks]
10(18)
Mrd clefia11.png
Mrd clefia12.png
Mrd clefia13.png
11(22)
Mrd clefia21.png
Mrd clefia22.png
Mrd clefia23.png
12(26)
Mrd clefia31.png
Mrd clefia32.png
Mrd clefia33.png
12(18)
Mrd clefia41.png
Mrd clefia42.png
Mrd clefia43.png
12(18)
Mrd clefia51.png
Mrd clefia52.png
Mrd clefia53.png
13(22)
Mrd clefia61.png
Mrd clefia62.png
Mrd clefia63.png
13(22)
Mrd clefia71.png
Mrd clefia72.png
Mrd clefia73.png
14(26)
Mrd clefia81.png
Mrd clefia82.png
Mrd clefia83.png
14(26)
Mrd clefia91.png
Mrd clefia92.png
Mrd clefia93.png

The algorithm uses a key whitening is further coupled to the data processing and after it. The stated requirements for the algorithm are:

- Security;

- Execution speed;

- Easy to implement on cheap equipment.

The algorithm is the first cipher applied technologies DSM (Diffusion Switching Mechanism) to increase security against linear and differential cryptanalysis. The developers also took into account the existence of a new type of attack - algebraic and declare resistance to them the cipher CLEFIA. To protect against a number of attacks are also used two types of lookup tables.

Katan

The KATAN ciphers compose of three variants: KATAN32, KATAN48 and KATAN64. All the ciphers in the KATAN family share the key schedule which accepts an 80-bit key. Any of the algorithms KATAN loads the encrypted data block in the two shift register constituting the internal state of the algorithm (an intermediate value, depending on the block data and an encryption key, and it is processed in the encryption algorithm). Encryption consists of 254 rounds, each of which uses nonlinear functions, which form the feedback registers:

Mrd katan1.png

The main feature of this algorithm is that it can be implemented using 802 GE's case KATAN32, allowing its use in systems with limited computing resources. The structure of one round is shown in Figure 5, where Mrd katan2.png and Mrd katan3.png - shift registers.

Mrd katan7.png
Picture 5 — The Outline of a round of the KATAN/KTANTAN ciphers [C9].

After 254 rounds of encryption registers become a cipher text. And the last bit of the register Mrd katan3.png is the last bit of the ciphertext. When deciphering the ciphertext is placed into the shift register, the last bit of the plaintext is placed in the last bit of the register Mrd katan3.png. Since symmetric cipher, the algorithm is identical to the decryption algorithm encryption in the same way. Key schedule loads 80-bit key in the shift register. Each round 0 and 1 of register positions are formed and used as a subkey Mrd katan4.png and Mrd katan6.png. Thus, the round plug i are:

Mrd katan5 en.png

Glossary

Bibliography

Go to references of the article "Lightweight block ciphers".

Return to the table of contents

Makhmutov R. D., 2015