密码学超轻量级密码——present.pdf

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：0.24M 资料格式：pdf 举报版权申诉

woshiliuxuan-4181273-4744300845238211146.pdf-第1页.png

第1页 / 共18页

woshiliuxuan-4181273-4744300845238211146.pdf-第2页.png

第2页 / 共18页

woshiliuxuan-4181273-4744300845238211146.pdf-第3页.png

第3页 / 共18页

woshiliuxuan-4181273-4744300845238211146.pdf-第4页.png

第4页 / 共18页

woshiliuxuan-4181273-4744300845238211146.pdf-第5页.png

第5页 / 共18页

woshiliuxuan-4181273-4744300845238211146.pdf-第6页.png

第6页 / 共18页

woshiliuxuan-4181273-4744300845238211146.pdf-第7页.png

第7页 / 共18页

woshiliuxuan-4181273-4744300845238211146.pdf-第8页.png

第8页 / 共18页

文本预览

PRESENT: An Ultra-Lightweight Block Cipher A. Bogdanov1, L.R. Knudsen2, G. Leander1, C. Paar1, A. Poschmann1, M.J.B. Robshaw3, Y. Seurin3, and C. Vikkelsoe2 1 Horst-G¨ortz-Institute for IT-Security, Ruhr-University Bochum, Germany 2 Technical University Denmark, DK-2800 Kgs. Lyngby, Denmark 3 France Telecom R&D, Issy les Moulineaux, France leander@rub.de, {abogdanov,cpaar,poschmann}@crypto.rub.de lars@ramkilde.com, chv@mat.dtu.dk {matt.robshaw,yannick.seurin}@orange-ftgroup.com Abstract. With the establishment of the AES the need for new block ciphers has been greatly diminished; for almost all block cipher appli- cations the AES is an excellent and preferred choice. However, despite recent implementation advances, the AES is not suitable for extremely constrained environments such as RFID tags and sensor networks. In this paper we describe an ultra-lightweight block cipher, present. Both security and hardware eﬃciency have been equally important during the design of the cipher and at 1570 GE, the hardware requirements for present are competitive with today’s leading compact stream ciphers. 1 Introduction One deﬁning trend of this century’s IT landscape will be the extensive deploy- ment of tiny computing devices. Not only will these devices feature routinely in consumer items, but they will form an integral part of a pervasive — and unseen — communication infrastructure. It is already recognized that such deployments bring a range of very particular security risks. Yet at the same time the cryp- tographic solutions, and particularly the cryptographic primitives, we have at hand are unsatisfactory for extremely resource-constrained environments. In this paper we propose a new hardware-optimized block cipher that has been carefully designed with area and power constraints uppermost in our mind. Yet, at the same time, we have tried to avoid a compromise in security. In achieving this we have looked back at the pioneering work embodied in the DES [34] and complemented this with features from the AES ﬁnalist candidate Serpent [4] which demonstrated excellent performance in hardware. At this point it would be reasonable to ask why we might want to design a new block cipher. After all, it has become an “accepted” fact that stream ciphers are, potentially, more compact. Indeed, renewed eﬀorts to understand the design of compact stream ciphers are underway with the eSTREAM [15] project and several promising proposals oﬀer appealing performance proﬁles. But we note a couple of reasons why we might want to consider a compact block cipher. First, a block cipher is a versatile primitive and by running a block cipher in counter

mode (say) we get a stream cipher. But second, and perhaps more importantly, the art of block cipher design seems to be a little better understood than that of stream ciphers. For instance, while there is a rich theory under-pinning the use of linear feedback shift registers [29] it is not easy to combine these building blocks to give a secure proposal. We suspect that a carefully designed block cipher could be a less risky undertaking than a newly designed stream cipher. Thus, we feel that a block cipher that requires similar hardware resources as a compact stream cipher could be of considerable interest. It is important to realise that in developing a new block cipher, particularly one with aggressive performance characteristics, we are not just looking for inno- vative implementation. Rather, the design and implementation of the cipher go hand-in-hand and this has revealed several fundamental limits and inherent con- tradictions. For instance, a given security level places lower bounds on the block length and key length. Just processing a 64-bit state with an 80-bit key places fundamental lower limits on the amount of space we require. We also observe that hardware implementation — particularly compact hardware implementa- tion — favours repetition. Even minor variations can have an unfortunate eﬀect on the space required for an implementation. Yet, at the same time, the cryptan- alyst also favours repetition and seeks mathematical structures that propagate easily across many rounds. How much simple, repetitive structure can we include without compromising its security? In this paper we describe the compact block cipher1 present. After a brief survey of the existing literature, the rest of the paper is organised in a stan- dard way. present is described in Section 3 with the design decisions described in Section 4. The security analysis follows in Section 5 along with a detailed performance analysis in Section 6. We close the paper with our conclusions. 2 Existing Work While there is a growing body of work on low-cost cryptography, the number of papers dealing with ultra-lightweight ciphers is surprisingly limited. Since our focus is on algorithm design we won’t refer to work on low-cost communication and authentication protocols. Some of the most extensive work on compact im- plementation is currently taking place within the eSTREAM project. As part of that initiative, new stream ciphers suitable for eﬃcient hardware implementation have been proposed. While this work is ongoing, some promising candidates are emerging [7, 19]. While the trade-oﬀs are complex, implementation papers [18] suggest that around 1300-2600 gate equivalents (GE) would be required for the more compact ciphers within the eSTREAM project. With regards to block ciphers it is well-known that DES was designed with hardware eﬃciency in mind. Given the very limited state of semiconductor cir- cuits in the early 1970s, it is not surprising that DES possesses very competitive implementation properties. Work on DES reveals an implementaton of around 1 The name reﬂects its similarity to Serpent and the goal of ﬁtting everywhere; the very nature of ubiquitous computing.

generateRoundKeys() for i = 1 to 31 do addRoundKey(state,Ki) sBoxLayer(state) pLayer(state) end for addRoundKey(state,K32) plaintext key register addRoundKey addRoundKey ? update ? ... ? update ? ? sBoxLayer pLayer ?... ? sBoxLayer pLayer ? ? ciphertext Fig. 1. A top-level algorithmic description of present. 3000 GE [42] while a serialized implementation can be realized with around 2300 GE [37]. The key length of DES limits its usefulness in many applications and makes proposals such as DESXL (2168 GE) of some considerable interest [37]. For modern block ciphers, the landmark paper of [16] gives a very thorough analysis of a low-cost implementation of the AES [35]. However, the resources required for this cipher are around 3600 GE, which is an indirect consequence of the fact that Rijndael was designed for software eﬃciency on 8- and 32- bit processors. Implementation requirements for the Tiny Encryption Algorithm tea [43, 44] are not known, but a crude estimate is that tea needs at least 2100 GE and xtea needs2 at least 2000 GE. Four dedicated proposals for low-cost implementation are mCrypton [30], hight [22], sea [41], and cgen [40], though the latter is not primarily intended as a block cipher. mCrypton has a precise hardware assessment and requires 2949 GE, hight requires around 3000 GE while sea with parameters comparable to present requires around 2280 GE. 3 The Block Cipher present present is an example of an SP-network [33] and consists of 31 rounds. The block length is 64 bits and two key lengths of 80 and 128 bits are supported. Given the applications we have in mind, we recommend the version with 80-bit keys. This is more than adequate security for the low-security applications typically required in tag-based deployments, but just as importantly, this matches the design goals of hardware-oriented stream ciphers in the eSTREAM project and allows us to make a fairer comparison. The security claims and performance attributes of the 128-bit version are provided in an appendix. 2 These ﬁgures and others in Section 2 are “back-of-an-envelope” where we assume the following requirements: 32-bit XOR = 80 GE, 32-bit arithmetic ADD = 148 GE, 192-bit FF = 1344 GE, SHIFT = 0 GE. All estimated ﬁgures lack any control logic which might signiﬁcantly increase the required area.

Each of the 31 rounds consists of an xor operation to introduce a round key Ki for 1 ≤ i ≤ 32, where K32 is used for post-whitening, a linear bitwise permutation and a non-linear substitution layer. The non-linear layer uses a single 4-bit S-box S which is applied 16 times in parallel in each round. The cipher is described in pseudo-code in Figure 1, and each stage is now speciﬁed in turn. The design rationale are given in Section 4 and throughout we number bits from zero with bit zero on the right of a block or word. addRoundKey. Given round key Ki = κi state b63 . . . b0, addRoundKey consists of the operation for 0 ≤ j ≤ 63, 0 for 1 ≤ i ≤ 32 and current 63 . . . κi bj → bj ⊕ κi j. sBoxlayer. The S-box used in present is a 4-bit to 4-bit S-box S : F4 2 → F4 2. The action of this box in hexadecimal notation is given by the following table. x 0 1 2 3 4 5 6 7 8 9 A B C D E F S[x] C 5 6 B 9 0 A D 3 E F 8 4 7 1 2 For sBoxLayer the current state b63 . . . b0 is considered as sixteen 4-bit words w15 . . . w0 where wi = b4∗i+3||b4∗i+2||b4∗i+1||b4∗i for 0 ≤ i ≤ 15 and the output nibble S[wi] provides the updated state values in the obvious way. pLayer. The bit permutation used in present is given by the following table. Bit i of state is moved to bit position P (i). 2 3 4 5 6 7 8 i i i i 1 P (i) P (i) 0 9 10 11 12 13 14 15 0 16 32 48 1 17 33 49 2 18 34 50 3 19 35 51 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 4 20 36 52 5 21 37 53 6 22 38 54 7 23 39 55 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 8 24 40 56 9 25 41 57 10 26 42 58 11 27 43 59 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 P (i) 12 28 44 60 13 29 45 61 14 30 46 62 15 31 47 63 P (i) The key schedule. present can take keys of either 80 or 128 bits. However we focus on the version with 80-bit keys. The user-supplied key is stored in a key register K and represented as k79k78 . . . k0. At round i the 64-bit round key Ki = κ63κ62 . . . κ0 consists of the 64 leftmost bits of the current contents of register K. Thus at round i we have that: Ki = κ63κ62 . . . κ0 = k79k78 . . . k16. After extracting the round key Ki, the key register K = k79k78 . . . k0 is updated as follows.

ki ki+1 S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S S Fig. 2. . The S/P network for present. 1. [k79k78 . . . k1k0] = [k18k17 . . . k20k19] 2. [k79k78k77k76] = S[k79k78k77k76] 3. [k19k18k17k16k15] = [k19k18k17k16k15] ⊕ round_counter Thus, the key register is rotated by 61 bit positions to the left, the left-most four bits are passed through the present S-box, and the round_counter value i is exclusive-ored with bits k19k18k17k16k15 of K with the least signiﬁcant bit of round_counter on the right. The key schedule for 128-bit keys is presented in an appendix. 4 Design Issues for present Besides security and eﬃcient implementation, the main goal when designing present was simplicity. It is therefore not surprising that similar designs have been considered in other contexts [21] and can even be used as a tutorial for students [20]. In this section we justify the decisions we took during the design of present. First, however, we describe the anticipated application requirements. 4.1 Goals and environment of use In designing a block cipher suitable for extremely constrained environments, it is important to recognise that we are not building a block cipher that is necessarily suitable for wide-spread use; we already have the AES [35] for this. Instead, we are targeting some very speciﬁc applications for which the AES is unsuitable. These will generally conform to the following characteristics. – The cipher is to be implemented in hardware.

– Applications will only require moderate security levels. Consequently, 80- bit security will be adequate. Note that this is also the position taken for hardware proﬁle stream ciphers submitted to eSTREAM [15]. – Applications are unlikely to require the encryption of large amounts of data. Implementations might therefore be optimised for performance or for space without too much practical impact. – In some applications it is possible that the key will be ﬁxed at the time of device manufacture. In such cases there would be no need to re-key a device (which would incidentally rule out a range of key manipulation attacks). – After security, the physical space required for an implementation will be the primary consideration. This is closely followed by peak and average power consumption, with the timing requirements being a third important metric. – In applications that demand the most eﬃcient use of space, the block cipher will often only be implemented as encryption-only. In this way it can be used within challenge-response authentication protocols and, with some careful state management, it could be used for both encryption and decryption of communications to and from the device by using the counter mode [36]. Taking such considerations into account we decided to make present a 64- bit block cipher with an 80-bit key3. Encryption and decryption with present have roughly the same physical requirements. Opting to support both encryption and decryption will result in a lightweight block cipher implementation that is still smaller than an encryption-only AES. Opting to implement an encryption- only present will give an ultra-lightweight solution. The encryption subkeys can be computed on-the-ﬂy. The literature contains a range of attacks that manipulate time-memory-data trade-oﬀs [6] or the birthday paradox when encrypting large amounts of data. However such attacks depend solely on the parameters of the block cipher and exploit no inner structure. Our goal is that these attacks be the best available to an adversary. Side-channel and invasive hardware attacks are likely to be a threat to present, as they are to all cryptographic primitives. For the likely ap- plications, however, the moderate security requirements reﬂect the very limited gain any attacker would make in practice. In a risk assessment, such attacks are unlikely to be a signiﬁcant factor. 4.2 The permutation layer When choosing the mixing layer, our focus on hardware eﬃciency demands a linear layer that can be implemented with a minimum number of processing elements, i.e. transistors. This leads us directly to bit permutations. Given our focus on simplicity, we have chosen a regular bit-permutation and this helps to make a clear security analysis (see Section 5). 3 Appendix II gives an option for 128-bit keys but we do not expect it to be used.

4.3 The S-box. 2 → F4 We use a single 4-bit to 4-bit S-box S : F4 2 in present. This is a direct consequence of our pursuit of hardware eﬃciency, with the implementation of such an S-box typically being much more compact than that of an 8-bit S-box. Since we use a bit permutation for the linear diﬀusion layer, AES-like diﬀusion techniques [12] are not an option for present. Therefore we place some addi- tional conditions on the S-boxes to improve the so-called avalanche of change. More precisely, the S-box for present fullﬁls the following conditions, where we denote the Fourier coeﬃcient of S by b (a) = X SW x∈F4 2 (−1)hb,S(x)i+ha,xi. 1. For any ﬁxed non-zero input diﬀerence ∆I ∈ F4 2 and any ﬁxed non-zero output diﬀerence ∆O ∈ F4 2 we require #{x ∈ F4 2 |S(x) + S(x + ∆I ) = ∆O} ≤ 4. 2. For any ﬁxed non-zero input diﬀerence ∆I ∈ F4 ence ∆O ∈ F4 2 such that wt(∆I ) = wt(∆O) = 1 we have 2 and any ﬁxed output diﬀer- {x ∈ F4 2 |S(x) + S(x + ∆I ) = ∆O} = ∅. 3. For all non-zero a ∈ F4 4. For all a ∈ F4 that SW b (a) = ±4. 2 and all non-zero b ∈ F4 it holds that |SW b (a)| ≤ 8. 2 and all non-zero b ∈ F4 such that wt(a) = wt(b) = 1 it holds As will become clear in Section 5, these conditions will ensure that present is resistant to diﬀerential and linear attacks. Using a classiﬁcation of all 4-bit S-boxes that fulﬁll the above conditions [27] we chose an S-box that is particular well-suited to eﬃcient hardware implementation. 5 Security Analysis We now present the results of a security analysis of present. 5.1 Diﬀerential and linear cryptanalysis Diﬀerential [3] and linear [32] cryptanalysis are among the most powerful tech- niques available to the cryptanalyst. In order to gauge the resistance of present to diﬀerential and linear cryptanalysis we provide a lower bound to the number of so-called active S-boxes involved in a diﬀerential (or linear) characteristic.

Fig. 3. The grouping of S-boxes in present for the purposes of cryptanalysis. The input numbers indicate the S-box origin from the preceeding round and the output numbers indicate the destination S-box in the following round. Diﬀerential cryptanalysis. The case of diﬀerential cryptanalysis is captured by the following theorem. Theorem 1. Any ﬁve-round diﬀerential characteristic of present has a mini- mum of 10 active S-boxes. While Theorem 1 will be formally proved in Appendix III, we make the following observations. We divide the 16 S-boxes into four groups (see Figure 3) and by examining the permutation layer one can then establish the following. 1. The input bits to an S-box come from 4 distinct S-boxes of the same group. 2. The input bits to a group of four S-boxes come from 16 diﬀerent S-boxes. 3. The four output bits from a particular S-box enter four distinct S-boxes, each of which belongs to a distinct group of S-boxes in the subsequent round. 4. The output bits of S-boxes in distinct groups go to distinct S-boxes. The proof of Theorem 1 in Appendix III follows from these observations. By using Theorem 1 any diﬀerential characteristic over 25 rounds of present must have at least 5 × 10 = 50 active S-boxes. The maximum diﬀerential probability of a present S-box is 2−2 and so the probability of a single 25-round diﬀerential characteristic is bounded by 2−100. Advanced techniques allow the cryptanalyst to remove the outer rounds from a cipher to exploit a shorter characteristic. However even if we allow an attacker to remove six rounds from the cipher, a situation without precedent, then the data required to exploit the remaining 25- round diﬀerential characteristic exceeds the amount available. Thus, the security bounds are more than we require. However, we have practically conﬁrmed that the bound on the number of active S-boxes in Theorem 1 is tight. Practical conﬁrmation. We can identify characteristics that involve ten S- boxes over ﬁve rounds. The following two-round iterative characteristic involves two S-boxes per round and holds with probability 2−25 over ﬁve rounds. ∆ = 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 → 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 3 → 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 = ∆.

分享到：

赞收藏

资料库

密码学超轻量级密码——present.pdf

相关推荐

课程资源

热门标签

最新资料