Piccolo: An Ultra-Lightweight Blockcipher
Kyoji Shibutani, Takanori Isobe, Harunaga Hiwatari, Atsushi Mitsuda,
Toru Akishita, and Taizo ShiraiSony Corporation
1-7-1 Konan, Minato-ku, Tokyo 108-0075, Japan{Kyoji.Shibutani,Takanori.Isobe,Harunaga.Hiwatari,Atsushi.Mitsuda,Toru.Akishita,Taizo.Shirai}@jp.sony.com

Abstract. We propose a new 64-bit blockcipher Piccolo supporting 80
and 128-bit keys. Adopting several novel design and implementation
techniques, Piccolo achieves both high security and notably compact implementation in hardware. We show that Piccolo offers a sufficient security level against known analyses including recent related-key differential
attacks and meet-in-the-middle attacks. In our smallest implementation,
the hardware requirements for the 80 and the 128-bit key mode are only
683 and 758 gate equivalents, respectively. Moreover, Piccolo requires
only 60 additional gate equivalents to support the decryption function
due to its involution structure. Furthermore, its efficiency on the energy
consumption which is evaluated by energy per bit is also remarkable.
Thus, Piccolo is one of the competitive ultra-lightweight blockcipherswhich are suitable for extremely constrained environments such as RFID
tags and sensor nodes.
Keywords: blockcipher, generalized Feistel networks, related-key differential attacks, meet-in-the-middle attacks, ultra-lightweight1

Introduction

Background and Motivation. Blockciphers are essential primitives for cryptographic applications such as data integrity, confidentiality, and protection ofprivacy. At the same time, with the large deployment of low resource devices
such as RFID tags and sensor nodes and increasing need to provide security
among such devices, lightweight cryptography has become a hot topic. Hence,
recently, research on designing and analyzing lightweight blockciphers has received a lot of attention. In fact, there have been several blockciphers designed
for a lightweight hardware implementation such as mCrypton [28], HIGHT [20],DESL/DESXL [27], PRESENT [11], KATAN/KTANTAN [13] and PRINTcipher [25]. The structures of these ciphers are generally categorized into two
structures: Substitution Permutation Networks (SPNs) and Feistel-type structures1 .
SPNs are known as the basic structure of the current U.S. encryption standard AES [16]. Also, several lightweight blockciphers based on an SPN have
1

KATAN/KTANTAN is exceptional, which is based on a stream cipher.

been published. PRESENT consisting of an SPN is supposed to be competitive ciphers among them, since its required gate is comparable with compact
stream ciphers such as Grain and Trivium2 [19, 15]. Recently, PRINTcipher was
designed for IC-printing, which is also an instantiation of an SPN. It achieves
remarkably compact implementation, though it has uncommon block size, i.e.,
48 or 96 bits. mCrypton, which is a miniature of Crypton [29], also adopts an
SPN.
On the other hand, Feistel-type structures including Feistel networks and generalized Feistel networks (GFNs) are the other most widely used structure andknown as the basic structure of the former U.S. encryption standard DES [17].
Though a lot of lightweight blockciphers instantiated by the Feistel-type structure have also been published, most of them have security problems in contrast to
the SPN based designs. HIGHT was designed for low resource devices, which is avariant of GFN. While it is relatively light, it has been theoretically broken by arelated-key differential attack [26]. GOST is known as the former Soviet encryption standard, and has Feistel network [32]. Since the compact implementation
result on GOST requiring 651 GE has been published [35], it is considered as
one of the ultra-lightweight blockciphers. However it has also been theoreticallybroken by an improved three-subset meet-in-the-middle (MITM) attack [21].
These attacks basically rely on the slow diffusion of the Feistel-type structures and high controllability of round keys caused by a simple key schedule.
Thus, to avoid those attacks, the Feistel-type structures generally require a larger
number of rounds than an SPN based construction. Since this reduces the efficiency on the energy consumption, the Feistel-type structure does not seem tobe suitable for lightweight blockciphers. However, it has a lot of distinct featuresfrom those of SPNs. For instance, the Feistel-type structure has a smaller round
function than SPNs, since only half of the data are updated per one round.
Moreover the Feistel-type structure can support a decryption function without
much implementation cost. As discussed in [11], by using the counter-mode, any
encryption-only ciphers can support decryption function. Yet, if the cipher itself supports decryption function, it can be used for more applications, e.g., an
application requiring CBC-mode. Also, a diversity of designs is considered to beimportant. Thus, it is meaningful to think about design possibilities of a Feisteltype structure based lightweight blockcipher that is not only efficient but also
secure against known attacks including the above explained powerful attacks.
Efficiency Metrics. While hardware efficiency can be measured in many different ways, both the energy consumption and the power consumption are important measure for lightweight applications. The energy consumption is considered as a metric for active devices which have an own power supply, and thepower consumption for passive devices which do not have an own power supply.
Though the power consumption heavily depends on the used technology and the
EDA tool, it is well known that it is proportional to the area requirement at
2Note that the expected security of them against distinguish attacks is substantiallyhigher than that of 64-bit lightweight blockciphers.

2

Table 1. Comparative results in hardware implementations
block keyserialized arch.
size size type area cycles/[bit] [bit][GE] block
DESXL [27]
64 184 Feistel 2,168
144†⋆
64 128 GFNHIGHT [20]mCrypton-96 [28]6496 SPN
mCrypton-128 [28]
64 128 SPN
PRESENT-80 [36, 11] 64
80 SPN 1,000
547
KATAN64 [13]64
80 stream 1,054
254‡
64
80 stream 688
254
KTANTAN64 [13]‡64 256 Feistel 651
264
GOST-PS [35]‡GOST-FB [35]
64 256 Feistel 800
264
Piccolo-80
64
80 GFN 683
432
Piccolo-128
64 128 GFN 758
528⋆
Piccolo-80
64
80 GFN 743
432⋆
Piccolo-128
64 128 GFN 818
528
Algorithm

area
[GE]
3,048
2,681
2,949
1,570
1,017
1,000
1,136
1,197
1,274
1,362

round-based arch.
cycles/ energy/∗1 FOM∗2
block
bit
34
1,620
202
13
545
684
13
600
566
32
785
811
32
509
1,933
32
500
2,000
27
480
1,836
33
618
1,353
27
538
1,460
33
703
1,045

AES-128 [31],[38]⋆128 128 SPN 2,400
226
12, 454∗3
11
1,071
75
CLEFIA-128 [1],[40]⋆ 128 128 GFN 2,488
328
5,979
18
841
202
PRINTcipher-48 [25]48
80 SPN 402
768
503
48
503
3,952
PRINTcipher-96 [25]
96 160 SPN 726
3,072
967
96
967
1,069
†
: Theoretically broken under related-key setting [26].
‡: Theoretically broken under single-key setting [12, 21].
⋆: Including decryption function. The others support encryption-mode only.
∗1: energy / bit = (area [GE] × required cycles for one block process [cycle]) / block size [bit].
∗2: FOM = (nanobit per cycles) / area squared [GE2 ].
∗3: This implementation is not intended to be high efficiency but high throughput.

low frequencies, e.g., 100 kHz [25]. Thus, we adopt the area requirement, i.e.,
gate equivalents (GE) as the measure to evaluate the efficiency with respect tothe power consumption in this work. The energy consumption is the power consumption over a certain time period, and for one block process, it is evaluated bymultiplying the area requirements with the required cycles for one block. Then,by dividing the power estimation for one block process by the block size, we
obtain energy per bit as the fair measure for the energy consumption. FOM (innano bits per clock cycle per GE squared) proposed by [4] is known as anothermetric for energy consumption. In this work, we mainly adopt the above mentioned measures area requirement, energy per bit and FOM for the efficiency
comparison.
Contributions and Outline. In this paper, we propose a new lightweightblockcipher Piccolo which is optimized for extremely constrained devices. Piccolo supports 64-bit block with 80 or 128-bit keys, and has an iterative structure
which is a variant of a generalized Feistel network. We demonstrate that Piccolo
offers a sufficient security level against known analyses including recent relatedkey differential and MITM attacks. Moreover, we present that Piccolo achieves
remarkably compact implementation in hardware. In our smallest implementation, the area requirements for the 80 and the 128-bit key mode are only 683 and758 GE with 432 and 528 cycles per block, respectively. The efficiency on theenergy consumption evaluated by energy per bit is 480 for the 80-bit key mode,
which is the smallest class among current lightweight blockciphers in literature.
Furthermore, Piccolo requires only 60 additional GE to support decryption func3

X(64)
64
16

wk0

16

16

F

wk1
rk0

F

RP
rk2

16

F

X(64)
rk1

F

rk3

F

rk2r−3

64

x0

x1

x2 x3

x4

x5

x6

x7

8

8

8

8

8

8

8

x2

x7

x4 x1

x6

x3

x0

x5

8

RP

wk2

F

rk2r−4FRP
rk2r−2
wk3

F

64

rk2r−1

Y(64)

64

Y(64)
Fig. 2. Round permutation RP

Fig. 1. Encryption function Gr

tion. Therefore, Piccolo supporting both encryption and decryption functions isstill comparable to other encryption-only lightweight blockciphers. These comparative results regarding the hardware efficiency for lightweight blockciphers
whose key size is more than 80 bits are summarized in Table 1. Note that, in
our implementations, a key input is assumed to hold its value during the block
process. Thus, Piccolo achieves both high security and extremely compact implementation unlike the other Feistel-type structure based lightweight blockciphers.
This paper is organized as follows. The specification of Piccolo is given in Section 2. Section 3 describes the design rationale. Sections 4 and 5 provide results
on security and hardware implementation, respectively. Finally, we conclude in
Section 6.

2

Specification

This section provides the specification of Piccolo. Piccolo is a 64-bit blockcipher
supporting 80 and 128-bit keys. The 80 and the 128-bit key mode are referred
as Piccolo-80 and Piccolo-128, respectively. Both ciphers consist of a data processing part and a key scheduling part. The differences between two key modes
lie in the number of rounds for the data processing part and the key schedulingpart. We first give notations used throughout this paper, then define each part.
2.1

Notationsa(b): b denotes the bit length of a.
a|b or (a|b) : Concatenation.
a ← b : Updating a value of a by a value of b.
ta: Transposition of a vector or a matrix a.
{a}b: Representation in base b.
4

4

S

4

S

16
4

S

4

S

S
M

S

LSB
4

S
S

MSB

Fig. 4. S-box

Fig. 3. F-function

2.2

4

16

Data Processing Part

The data processing part of Piccolo consisting of r rounds, Gr , takes a 64-bit
data X ∈ {0, 1}64 , four 16-bit whitening keys wki ∈ {0, 1}16 (0 ≤ i < 4) and 2r
16-bit round keys rki ∈ {0, 1}16 (0 ≤ i < 2r) as the inputs, and outputs a 64-bit
data Y ∈ {0, 1}64 . Gr is defined as follows:{0, 1}64 × {{0, 1}16 }4 × {{0, 1}16 }2r → {0, 1}64
Gr :(X(64) , wk0(16) , ..., wk3(16) , rk0(16) , ..., rk2r−1(16) ) 7→ Y(64)Algorithm Gr (X(64) , wk0 , ..., wk3 , rk0 , ..., rk2r−1 ) :X0(16) |X1(16) |X2(16) |X3(16) ← X(64)
X0 ← X0 ⊕ wk0 , X2 ← X2 ⊕ wk1
for i ← 0 to r − 2 do
X1 ← X1 ⊕ F (X0 ) ⊕ rk2i , X3 ← X3 ⊕ F (X2 ) ⊕ rk2i+1
X0 |X1 |X2 |X3 ← RP (X0 |X1 |X2 |X3 )X1 ← X1 ⊕ F (X0 ) ⊕ rk2r−2 , X3 ← X3 ⊕ F (X2 ) ⊕ rk2r−1
X0 ← X0 ⊕ wk2 , X2 ← X2 ⊕ wk3
Y(64) ← X0 |X1 |X2 |X3

where F is a 16-bit F-function and RP is a 64-bit permutation defined in thefollowing sections. The decryption function G−1
r is obtained from Gr by simply
changing the order of whitening and round keys as follows:{0, 1}64 × {{0, 1}16 }4 × {{0, 1}16 }2r → {0, 1}64
−1Gr :(Y(64) , wk0(16) , ..., wk3(16) , rk0(16) , ..., rk2r−1(16) ) 7→ X(64)Algorithm G−1
r (Y(64) , wk0 , ..., wk3 , rk0 , ..., rk2r−1 ) :wk0′ ← wk2 , wk1′ ← wk3 , wk2′ ← wk0 , wk3′ ← wk1
for i ← 0 to r − 1do
rk2r−2i−2 |rk2r−2i−1 (if i mod 2 = 0)′′
rk2i
|rk2i+1←
rk2r−2i−1 |rk2r−2i−2 (if i mod 2 = 1)′
X(64) ← Gr (Y, wk0′ , ..., wk3′ , rk0′ , ..., rk2r−1)

The number of rounds, r, is 25 and 31 for Piccolo-80 and -128, i.e., G25 andG31 for Piccolo-80 and -128, respectively (See Fig. 1).
F-Function. F-function F : {0, 1}16 → {0, 1}16 consists of two S-box layers
separated by a diffusion matrix (See Fig. 3). The S-box layer consists of four5Table 2. 4-bit bijective S-box S in hexadecimal form
x
S[x]

0
e

1
4

2
b

3
2

4
3

5
8

6
0

7
9

8
1

9
a

a
7

b
f

c
6

d
c

e
5

f
d

4-bit bijective S-boxes S given by Table 2, and updates a 16-bit data X(16) as
follows:(x0(4) , x1(4) , x2(4) , x3(4) ) ← (S(x0(4) ), S(x1(4) ), S(x2(4) ), S(x3(4) )),where X(16) = x0(4) |x1(4) |x2(4) |x3(4) . The diffusion matrix M is defined as

2311
1 2 3 1

M =1 1 2 3.
3112


Then the diffusion function updates a 16-bit data X(16) as follows:t(x0(4) , x1(4) , x2(4) , x3(4) ) ← M · t (x0(4) , x1(4) , x2(4) , x3(4) ),where the multiplications between matrices and vectors are performed overGF(24 ) defined by an irreducible polynomial x4 + x + 1.
Round Permutation. The round permutation RP : {0, 1}64 → {0, 1}64 divides a 64-bit input X(64) into eight 8-bit data as X(64) = x0(8) |x1(8) |...|x7(8) ,then permutes them by the following manner:
RP : (x0(8) , x1(8) , ..., x7(8) ) ← (x2(8) , x7(8) , x4(8) , x1(8) , x6(8) , x3(8) , x0(8) , x5(8) ).

Finally, the round permutation concatenates (x0(8) , x1(8) , ..., x7(8) ) into X(64)(See Fig. 2).
2.3

Key Scheduling PartThe key scheduling part of Piccolo supports 80 and 128-bit keys, and outputs
16-bit whitening keys wki(16) (0 ≤ i < 4) and round keys rkj(16) (0 ≤ j < 2r) for
the data processing part. The key scheduling functions for Piccolo-80 and -128
are referred as KSr80 and KSr128 , respectively. We first define 16-bit constants
128
con80
i and coni , then describe each key schedule.
128
Constant Values. The constants con80
used in KSr80 and KSr128 ,i and coni
respectively, are generated as follows:80(con802i |con2i+1 ) ← (ci+1 |c0 |ci+1 |{00}2 |ci+1 |c0 |ci+1 ) ⊕ {0f1e2d3c}16 ,128(con2i |con128
2i+1 ) ← (ci+1 |c0 |ci+1 |{00}2 |ci+1 |c0 |ci+1 ) ⊕ {6547a98b}16 ,where ci is a 5-bit representation of i, e.g., c11 = {01011}2 .
6Key Schedule for 80-Bit Key Mode (KSr80 ). The key scheduling function
for the 80-bit key mode, KSr80 , divides an 80-bit key K(80) into five 16-bit subkeys ki(16) (0 ≤ i < 5) and provides wki(16) (0 ≤ i < 4) and rkj(16) (0 ≤ j < 2r)
as follows:
Algorithm KSr80 (K(80) ) :wk0 ← k0L |k1R , wk1 ← k1L |k0R , wk2 ← k4L |k3R , wk3 ← k3L |k4R
for i ← 0 to (r − 1) do (k2 , k3 ) (if i mod 5 = 0 or 2)80(k0 , k1 ) (if i mod 5 = 1 or 4)(rk2i , rk2i+1 ) ← (con80
2i , con2i+1 ) ⊕(k4 , k4 ) (if i mod 5 = 3),

where kiL and kiR are left and right half 8 bits of ki , respectively, i.e., ki(16) =
L
R
R
ki(8)
|ki(8)and ki(8)contains the least significant bit of ki(16) .
Key Schedule for 128-Bit Key Mode (KSr128 ). The key scheduling function for the 128-bit key mode, KSr128 , divides a 128-bit key K(128) into eight 16bit sub-keys ki(16) (0 ≤ i < 8) and provides wki(16) (0 ≤ i < 4) and rkj(16) (0 ≤j < 2r) as follows:
Algorithm KSr128 (K(128) ) :wk0 ← k0L |k1R , wk1 ← k1L |k0R , wk2 ← k4L |k7R , wk3 ← k7L |k4R
for i ← 0 to (2r − 1) do
if (i + 2) mod 8 = 0 then(k0 , k1 , k2 , k3 , k4 , k5 , k6 , k7 ) ← (k2 , k1 , k6 , k7 , k0 , k3 , k4 , k5 )rki ← k(i+2) mod 8 ⊕ con128
i

3

Design Rationale

In this section, we briefly describe design rationale of Piccolo.
Structure. Piccolo supports 64-bit block to fit standard applications, and 80
and 128-bit keys to achieve moderate security levels. The underlying structure
is a variant of GFN that can easily support decryption function without much
implementation cost and has light round functions.
Key Schedule. We adopt a permutation based key schedule which can significantly reduce the required number of gates. For instance, the registers for storingkeys are not required and it leads the almost same gate requirement for eachkey size, in contrast to a key schedule requiring key state. While the drawback
is security concern, by carefully choosing the permutation, it has enough immunity against attacks exploiting weakness of the key schedule such as related-key
differential and MITM attacks. Note that, in our evaluation, key inputs are notrequired to be hard-wired, but are assumed to hold its values during the block
operation.
7

Round Permutation. In order to improve diffusion property, Piccolo utilizes
an 8-bit word based permutation between rounds instead of a 16-bit word based
cyclic shift used in the standard GFN. Moreover, it demolishes the 16-bit word
structure and thus improves the security against cryptanalysis exploiting strong
word-based structure such as saturation attacks. We choose the specific one
among several possibilities not to destroy the involution property in which theencryption process is identical to the decryption process when whitening andround keys are not introduced.
F-Function. The F-function consists of two S-box layers separated by a diffusion matrix without key additions before the second S-box layer. The S-box in
the F-function has a 4-round iterative structure like GFN, and is extremely light.
As shown in Fig. 4, each S-box consists of only four NOR gates, three XOR gatesand one XNOR gate. Both the maximum differential probability (MDP) and the
maximum linear probability (MLP) of the S-box are 2−2 which are optimal, andit has no fixed point. Moreover, it is suitable for efficient threshold implementation as discussed in Section 5. Furthermore, by using a standard PC, we obtain
2−9.3 and 2−8.0 as MDP and MLP of the F-function, respectively. While those
figures are not optimal for a 16-bit bijective function, it is sufficient for our design, since Piccolo has enough differentially and linearly active F-functions overa certain number of rounds.

4

Security Analysis

In this section, we provide results on security analysis for Piccolo.
Differential Attack / Linear Attack [7, 30]. We first show the minimum
numbers of differentially and linearly active F-functions of Gr up to 30 rounds inTable 3. The figures in the table are obtained by an exhaustive search based on
the algorithm given by [39]. Note that the minimum numbers for differentiallyand linearly active F-functions are the same due to the duality of differential andlinear attacks and the similarity of Gr and G−1
r . As explained in Section 3, MDP
and MLP of the F-function are 2−9.3 and 2−8.0 , respectively. Combining thoseresults, Piccolo consisting of at least 7 or 8 rounds provide at least 7 or 8 active
F-functions, and have no differential or linear trails whose probabilities are morethan 2−64 , respectively. Thus, we expect that the full-round of Piccolo (25 and
31 rounds for Piccolo-80 and -128) has enough immunity against differential andlinear attacks, since it has large security margin.
Boomerang-Type Attacks [42, 23, 6]. The boomerang-type attacks (including the boomerang, amplified boomerang and rectangle attacks) first divide thecipher into two sub-ciphers, then find a boomerang quartet with high probability.
The probabilityof constructing a boomerang quartet is denoted as p̂2 q̂ 2 , where
qP
2
p̂ =
β Pr [α → β], and α and β are input and output differences for the
first sub-cipher, and q̂ for the second sub-cipher. p̂2 is bounded by the maximum
8

Table 3. Min. # differentially and linearly active F-functions (single-key setting)rounds
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
min. # active F-functions 0 1 2 3 4 6 7 8 9 10 11 12 13 14 15
rounds16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
min. # active F-functions 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

differential trail probability, i.e., p̂2 ≤ maxβ Pr[α → β], and q̂ 2 as well. Let p, q
be the maximum differential trail probability for the first and the second subciphers. Then, p, q are bounded by multiplying the minimum number of active
F-functions in each sub-cipher with MDP of the F-function. From Table 3, any
combination of two sub-ciphers for Piccolo consisting of at least 9 rounds has
at least 7 active F-functions in total. Hence, we conclude that the full-round of
Piccolo is sufficiently secure against boomerang-type attacks.
Impossible Differential Attack [5]. An impossible differential attack is likely
to be applied to a variant of GFN due to its slow diffusion. However, Piccolo
utilizes the round permutation RP to achieve faster diffusion compared to a
standard type-II GFN. Then, for both encryption and decryption sides, Piccolo
requires only four rounds to be full diffusion, which is a property that all outputs
are affected by all inputs. This implies that there exists at most 9-round impossible differential using a 16-bit truncated differential from the observation in [41].
We also search the longest impossible differential by modified U -method [24] algorithm and found a 7-round impossible differential exploiting a 4-bit truncateddifferential. Therefore, we conclude that the full-round of Piccolo is expected to
be secure against the impossible differential attack.
Related-Key Differential Attacks [9, 8]. In the related-key setting, a distinguisher is allowed to use related-keys and usually uses key differentials tocancel out differentials in a data processing part. While the practical impactof related-key differential attacks is still controversial, we care about it from a
pessimistic (designers’) point of view. To evaluate the resistance to it, we follow
an approach presented in [10]. In other words, we evaluate the immunity against
related-key differential attacks by counting the minimum number of differentially
active F-functions in the related-key setting. Table 4 shows the minimum numbers of differentially active F-functions for the 80 and the 128-bit key modes up
to 20 rounds. Unlike the attacks under the single-key setting, the total numberof active F-functions for the related-key differential attacks may vary according to the starting round. However, in our evaluations, those differences are at
most 2 active F-functions, even if the starting round is changed. Consequently,
we obtain that over 14 and 16 rounds for Piccolo-80 and -128 have at least 7
differentially active F-functions in the related-key setting, respectively.
Moreover, we consider related-key boomerang/rectangle attacks [8]. Similarly to non related-key boomerang-type attacks, we evaluate the security in theworst case that an attacker can use pq instead of p̂2 q̂ 2 for the probability of a9

Table 4. Min. # differentially active F-functions (related-key setting)hhhhhh rounds 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
starting round i hhhhfor Piccolo-80 encryption
i mod 5 = 0
0 0 0 0 0 2 3 4 4 5 5 6 7 7 7 8 9 10 11 11i mod 5 = 1
0 0 0 0 1 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11i mod 5 = 2
0 0 0 0 1 2 3 3 4 6 6 6 7 7 9 9 9 10 10 12i mod 5 = 3
0 0 0 0 1 2 2 3 4 5 5 6 6 7 8 8 9 9 10 11i mod 5 = 4
0 0 0 0 0 0 2 3 4 5 6 6 7 7 7 7 9 10 11 11
for Piccolo-80 decryption
i mod 5 = 0
0 0 0 0 1 2 2 3 4 5 5 6 6 7 8 8 9 9 10 11i mod 5 = 1
0 0 0 0 1 2 3 3 4 6 6 6 7 7 9 9 9 10 10 12i mod 5 = 2
0 0 0 0 1 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11i mod 5 = 3
0 0 0 0 0 2 3 4 4 5 5 6 7 7 7 8 9 10 11 11i mod 5 = 4
0 0 0 0 0 0 2 3 4 5 6 6 7 7 7 7 9 10 11 11
for Piccolo-128 encryption
i mod 4 = 0
0 0 0 0 0 0 0 1 3 3 4 5 5 6 7 7 8 9 10 10i mod 4 = 1
0 0 0 0 0 0 1 2 3 3 4 5 5 6 7 7 8 9 10 11i mod 4 = 2
0 0 0 0 0 0 1 2 2 3 4 4 5 6 6 7 7 9 9 9i mod 4 = 3
0 0 0 0 0 1 1 1 2 3 4 5 5 6 7 7 8 9 9 10
for Piccolo-128 decryption
i mod 4 = 0
0 0 0 0 0 1 1 2 3 3 4 5 5 6 6 7 8 9 9 11i mod 4 = 1
0 0 0 0 0 0 1 2 3 3 4 4 5 6 7 7 8 9 9 9i mod 4 = 2
0 0 0 0 0 0 0 1 2 3 4 5 5 6 7 7 7 9 10 10i mod 4 = 3
0 0 0 0 0 0 1 1 2 3 4 5 5 6 7 7 8 9 10 10boomerang quartet. As a result, we confirmed that over 17 and 21 rounds of
Piccolo-80 and -128 provide enough (seven) differentially active F-functions inthis setting.
Furthermore, we take related-key impossible differential attacks [22] into account. Consequently, by using modified U -method, we found an 11 and a 17round impossible differential distinguisher using an 8-bit truncated differential
for Piccolo-80 and -128 in the related-key setting, respectively, and they are thelongest in our evaluation. Therefore, we conclude that the full-round Piccolo is
expected to be resistant to those attacks.
Meet-in-the-Middle Attack [12]. Three-subset meet-in-the-middle (MITM)
cryptanalysis [12] is a recent attack on blockciphers. This attack works well forblockciphers having a simple key schedule and slow diffusion. Indeed, KTANTAN and GOST have been theoretically broken by this attack [12, 21]. Since
Piccolo consists of the permutation based key scheduling and a variant of GFN,
evaluating the resistance against this attack is important.
Similarly to data difference, Piccolo requires 4 rounds to non-linearly diffuse
any round-key difference to all output data in the data processing part, i.e., anyround-key bits of the i-th round non-linearly affect all input of the (i − 3)-thround and all output of the (i + 3)-th round. Thus, we assume that an attacker
might construct an 8-round indirect-partial matching [3] and a 4-round initialstructure [37] in the worst case. Besides, we even allow the attacker to use code10

book and splice and cut techniques [2]. In this worst setting, Piccolo-80 and -128
without whitening keys have neutral words up to 19 and 23 consecutive rounds,
respectively. We expect that the attacked rounds obtained by this observation
are upper bounds on the security against the three-subset MITM attack, since
the given assumptions are sufficiently strong. Moreover, we attempt to constructactual attacks to obtain the lower bounds on the security. As a result, the Piccolo-80 and -128 without whitening keys reduced to 14 and 21 rounds can be
attacked by the three-subset MITM attacks, respectively. Since Piccolo actually
has whitening keys, it is obviously stronger than the variants evaluated above.
Thus, we conclude that Piccolo has enough immunity against the three-subset
MITM attack.
Other Attacks. We also consider other attacks including a slide, a saturation,
an interpolation, a higher order differential, a truncated differential, and an
algebraic attack. Though the details of the evaluations for those attacks areomitted due to the page limitation, consequently, we expect that none of themwork better than the previously explained attacks.

5

Implementation Aspects

This section provides results on compact hardware implementation of Piccolo
with novel implementation techniques, showing two types of implementations: around-based implementation and a serialized implementation. While one round
function is processed within one clock cycle in a round-based implementation,
only a fraction of one round is treated in a clock cycle in a serialized implementation to realize the low-power and low-area implementation.
5.1

Optimization in Key Scheduling PartThe key scheduling part of Piccolo can be implemented by using multiplexers
without flip-flops which have high area requirement, in a way similar to theimplementation of GOST and KTANTAN [35, 13]. Actually, our round-based
implementation of Piccolo-80 needs only 32-bit wide 3-to-1 MUX to select theappropriate round key. For a serialized implementation, we require a 4-bit wide
20-to-1 MUX to select the right chunk of the round key.
In our evaluation, key inputs are assumed to hold those values during theblock process, but are not required to be hard-wired. Therefore, our results do
not contain registers for storing keys. If such registers are needed, around 360 and
576 extra GE are required for Piccolo-80 and -128, respectively. Moreover, if we
use hard-wired key, we can reduce around 85 and 114 GE from the round-based
implementations, also about 67 and 104 GE from the serialized implementations
for Piccolo-80 and -128, respectively.
5.2

Optimization in Data Processing Part

A round-based implementation of Piccolo can be done straightforwardly. Notethat we use scan flip-flops for the data state, which take both an input and an
output of a round function as inputs.
11

4

con

4
4:1

data in

4

16

5:1

4

2:1

16

k0

16

k1

16

k2

16

k3
k4

16
3:1
2:1

DQ

DQ

DQ

DQ

DQ

DQ

DQ

DQ

DQ

DQ

DQ

DQ

2:1

data out

S −1

R0
QD
×{2}

R1

R2

QD

QD

R3
QD

2:1

S

2:1

×{3}

path A
Fig. 5. Data path of our serialized implementation

On the other hand, a serialized implementation has many variety. Our serialized implementation is based on 4-bit shift registers in the similar way as [18].
The 4-bit data path for Piccolo-80 is described in Fig. 5.
In our serialized implementation, firstly outputs of the first S-box are set to
the registers (R0 , R1 , R2 , R3 ) described in Fig. 5. In the next four clock cycles,
each row of the diffusion matrix is updated in order by rotating the registers(R0 , R1 , R2 , R3 ). Simultaneously, the outputs of the matrix are input to S-box
S through path A, then the outputs of the F-function are obtained. In the next
four clock cycles, the inputs of the F-function are recovered in order throughS −1 which is the inversion of S. At the same time, the outputs of the first S-box
layer of the next F-function are set to the registers (R0 , R1 , R2 , R3 ). Therefore,
this implementation requires 8 clock cycles per F-function, and thus 16 clock
cycles per round. We emphasize that our serialized implementation does not
require additional registers for storing intermediate values of the F-functions byappending S −1 which costs only 12 GE.
5.3

Hardware Performance

Table 5 shows the detailed implementation figures of the round-based and theserialized implementations of Piccolo-80 and -128.
We designed hardware implementations of Piccolo in Verilog-HDL and synthesized the designs to a 0.13 µm standard cell library. We used VCS version
2006.06 for simulation and Design Compiler version 2007.03-SP3 for synthesis.
One GE is equivalent to the area of a 2-way NAND.
In a recent trend, the implementation of lightweight blockciphers uses a scan
flip-flop instead of a combination of a D flip-flop and a 2-to-1 MUX [13, 35, 36]
to reduce the gate requirement. In our evaluation environment, a D flip-flop anda 2-to-1 MUX cost 4.5 and 2.0 GE, respectively, while a scan flip-flop costs 6.25
GE. Thus, we can save 0.25 GE per bit of storage by using this implementation
12

Table 5. Implementation figures for Piccolo
Piccolo-80
Piccolo-128
serial round serial roundcycles per block
432
27
528
33
throughput @ 100 kHz (kbps.) 14.81 237.04 12.12 193.94
Area [GE]sum 683.00 1,135.25 757.75 1,196.50
Key scheduling 95
72
135
120
Data state 309
344
309
344
S-box/S-box−1 24
192
24
192
Matrix 34
208
34
208
Key XOR 8∗64
8∗64
Constants XOR -∗40-∗
40
F-func. output XOR 864
864
MUX 2472
24
72
Others/Control 181.00 79.25 215.75 92.50∗: XOR for round keys and constants is sharedtechnique. Moreover, the library we used has the 4-input AND-NOR and 4-input
OR-NAND gates with two inputs inverted as described in Fig. 6. The outputsof these cells are corresponding to those of XOR or XNOR when the inputs
X, Y are set as shown in Fig. 6. Thus, we can use these cells instead of XOR or
XNOR cells. Since both cells cost 2 GE instead of 2.25 GE required for XOR
or XNOR, we can save 0.25 GE per an XOR or XNOR gate. We employed theabove mentioned implementation techniques in our evaluation.

X
Y

X
Y

X
Y

X
Y
4-input AND-NOR gatewith 2 inputs inverted

4-input OR-NAND gatewith 2 inputs inverted

Fig. 6. 4-input AND-NOR and 4-input OR-NAND gates with 2 inputs inverted, whichcorrespond to XOR and XNOR gate

5.4

Security against Side Channel Attacks

A provably secure countermeasure against first order side-channel attacks called
threshold implementations [33, 34] can be applied to Piccolo. In threshold implementations, at least three shares are necessary for any nonlinear function. The
S-box of Piccolo defined in Section 2 is chosen to belong to the alternating group
A16 , where a 4 × 4 bijection can be decomposed using quadratic bijections [14].
13

Therefore, for the S-box of Piccolo, the masking method can be applied using
only three shares, which leads efficient threshold implementations of Piccolo.

6

Conclusion

In this paper, we have presented a lightweight blockcipher consisting of a variantof generalized Feistel network with a permutation based key schedule. Despite
several desirable implementation properties for a combination of Feistel-type
structure with a permutation based key schedule, the ciphers having such structures are likely to be vulnerable to attacks. The proposed cipher Piccolo employs
several new design approaches including the half-word based round permutationand the effective permutation for key expanding to avoid known attacks withoutloosing efficiency on both power and energy consumptions. Consequently, Piccolo
achieves not only notably compact implementation but also high security.
Acknowledgments The authors would like to thank the anonymous reviewers
for their helpful comments.

References
1. T. Akishita and H. Hiwatari, “Very compact hardware implementationsof the blockcipher CLEFIA.” Sony corporation, June 2011.
Available at
http://www.sony.co.jp/Products/cryptography/clefia/download/data/clefia-hwcompact-20110615.pdf.
2. K. Aoki and Y. Sasaki, “Preimage attacks on one-block MD4, 63-step MD5 andmore.” SAC , LNCS 5381, pp. 103–119, Springer-Verlag, 2008.
3. K. Aoki and Y. Sasaki, “Meet-in-the-middle preimage attacks against reduced
SHA-0 and SHA-1.” CRYPTO, LNCS 5677, pp. 70–89, Springer-Verlag, 2009.
4. S. Badel, N. Dagtekin, J. Nakahara, K. Ouafi, N. Reffé, P. Sepehrdad, P. Susil,
and S. Vaudenay, “Armadillo: A multi-purpose cryptographic primitive dedicatedto hardware.” CHES 2010, LNCS 6225, pp. 398–412, Springer-Verlag, 2010.
5. E. Biham, A. Biryukov, and A. Shamir, “Cryptanalysis of Skipjack reduced to
31 rounds using impossible differentials.” in Eurocrypt’99 , LNCS 1952, pp. 12–23,
Springer-Verlag, 1999.
6. E. Biham, O. Dunkelman, and N. Keller, “The rectangle attack - rectangling theSerpent.” Eurocrypt’01 , LNCS 2045, pp. 340–357, Springer-Verlag, 2001.
7. E. Biham and A. Shamir, Differential Cryptanalysis of the Data Encryption Standard . Springer, 1993.
8. E. Biham, O. Dunkelman, and N. Keller, “Related-key boomerang and rectangle
attacks.” EUROCRYPT , LNCS 3494, pp. 507–525, Springer-Verlag, 2005.
9. E. Biham, O. Dunkelman, and N. Keller, “A unified approach to related-key attacks.” FSE , LNCS 5086, pp. 73–96, Springer, 2008.
10. A. Biryukov and I. Nikolić, “Automatic search for related-key differential characteristics in byte-oriented block ciphers: Application to AES, Camellia, Khazad andothers.” Eurocrypt’10 , LNCS 6110, pp. 322–344, Springer-Verlag, 2010.
11. A. Bogdanov, L. Knudsen, G. Leander, C. Paar, A. Poschmann, M. J. B. Robshaw, Y. Seurin, and C. Vikkelsoe, “PRESENT: An ultra-lightweight block cipher.”
CHES’07 , LNCS 4727, pp. 450–466, Springer-Verlag, 2007.

1412. A. Bogdanov and C. Rechberger, “A 3-subset meet-in-the-middle attack: Cryptanalysis of the lightweight block cipher KTANTAN.” SAC , LNCS 6544, pp. 229–
240, Springer, 2010.
13. C. D. Cannière, O. Dunkelman, and M. Knezevic, “KATAN and KTANTAN - afamily of small and efficient hardware-oriented block ciphers.” CHES , LNCS 5747,
pp. 272–288, Springer, 2009.
14. C. D. Cannière, V. Nikov, S. Nikova, and V. Rijmen, “S-box decompositions for
SCA-resisting implementations.” Poster session of CHES’10, 2010.
15. C. D. Cannière and B. Preneel, “Trivium.” New Stream Cipher Designs - The
eSTREAM Finalists, LNCS 4986, pp. 244–266, Springer, 2008.
16. FIPS, “Advanced Encryption Standard (AES).” Federal Information Processing
Standards Publication 197.
17. FIPS, “Data Encryption Standard.” Federal Information Processing Standards
Publication 46.
18. P. Hämäläinen, T. Alho, M. Hännikäinen, and T. D. Hämäläinen, “Design andimplementation of low-area and low-power AES encryption hardware core.” DSD,
pp. 577–583, IEEE Computer Society, 2006.
19. M. Hell, T. Johansson, A. Maximov, and W. Meier, “The Grain family of stream
ciphers.” New Stream Cipher Designs - The eSTREAM Finalists, LNCS 4986,
pp. 179–190, Springer, 2008.
20. D. Hong, J. Sung, S. Hong, J. Lim, S. Lee, B. Koo, C. Lee, D. Chang, J. Lee,
K. Jeong, H. Kim, J. Kim, and S. Chee, “HIGHT: A new block cipher suitable forlow-resource device.” CHES’06 , LNCS 4249, pp. 46–59, Springer-Verlag, 2006.
21. T. Isobe, “A single-key attack on the full GOST block cipher.” FSE’11 , LNCS 6733,
pp. 290–305, 2011.
22. G. Jakimoski and Y. Desmedt, “Related-key differential cryptanalysis of 192-bit
key AES variants.” SAC’03 , LMCS 3006, pp. 208–221, Springer-Verlag, 2004.
23. J. Kelsey, T. Kohno, and B. Schneier, “Amplified boomerang attacks against
reduced-round MARS and Serpent.” FSE’00 , LNCS 1978, pp. 75–93, SpringerVerlag, 2001.
24. J. Kim, S. Hong, J. Sung, C. Lee, and S. Lee, “Impossible differential cryptanalysis
for block cipher structure.” INDOCRYPT’03 , LNCS 2904, pp. 82–96, SpringerVerlag, 2003.
25. L. Knudsen, G. Leander, A. Poschmann, and M.J.B.Robshaw, “PRINTcipher: A
block cipher for IC-printing.” CHES’10 , LNCS 6225, pp. 16–32, Springer-Verlag,
2010.
26. B. Koo, D. Hong, and D. Kwon, “Related-key attack on the full HIGHT.” PreProceedings of ICISC’10 , Springer-Verlag, 2010.
27. G. Leander, C. Paar, A. Poschmann, and K. Schramm, “New lightweight DES
variants.” FSE’07 , LNCS 4953, pp. 196–210, Springer-Verlag, 2007.
28. C. H. Lim and T. Korkishko, “mCRYPTON - a lightweight block cipher for securityof low-cost RFID tags and sensors.” WISA’05 , LNCS 3786, pp. 243–258, SpringerVerlag, 2005.
29. C. H. Lim, “A revised version of Crypton - Crypton V1.0.” FSE , LNCS 1636,
pp. 31–45, Springer, 1999.
30. M. Matsui, “Linear cryptanalysis of Data Encryption Standard.” Eurocrypt’93 ,LNCS 765, pp. 386–397, Springer-Verlag, 1994.
31. A. Moradi, A. Poschmann, S. Ling, C. Paar, and H. Wang, “Pushing the limits: A
very compact and a threshold implementation of AES.” Eurocrypt’11 , LNCS 6632,
pp. 69–88, Springer-Verlag, 2011.

15

32. National Soviet Bureau of Standards, “Information Processing System - Cryptographic Protection - Cryptographic Algorithm GOST 28147-89.”.
33. S. Nikova, C. Rechberger, and V. Rijmen, “Threshold implementations against
side-channel attacks and glitches.” ICICS , LNCS 4307, pp. 529–545, Springer,
2006.
34. S. Nikova, V. Rijmen, and M. Schläffer, “Secure hardware implementation of nonlinear functions in the presence of glitches.” ICISC , LNCS 5461, pp. 218–234,
Springer, 2008.
35. A. Poschmann, S. Ling, and H. Wang, “256 bit standardized crypto for 650 GE GOST revisited.” CHES’10 , LNCS 6225, pp. 219–233, Springer, 2010.
36. C. Rolfes, A. Poschmann, G. Leander, and C. Paar, “Ultra-lightweight implementations for smart devices - security for 1000 gate equivalents.” CARDIS , LNCS 5189,
pp. 89–103, Springer, 2008.
37. Y. Sasaki and K. Aoki, “Finding preimages in full MD5 faster than exhaustive
search.” EUROCRYPT , LNCS 5479, pp. 134–152, Springer, 2009.
38. A. Satoh and S. Morioka, “Hardware-focused performance comparison for the standard block ciphers AES, Camellia, and Triple-DES.” ISC , LNCS 2851, pp. 252–266,
Springer, 2003.
39. T. Shirai and K. Araki, “On generalized Feistel structures using the diffusion
switching mechanism.” IEICE Trans. Fundamentals, vol.E91-A, No.8 , pp. 2120–
2129, Aug. 2008.
40. T. Shirai, K. Shibutani, T. Akishita, S. Moriai and T. Iwata, “The 128-bit Blockcipher CLEFIA.” FSE , LNCS 4953, pp. 181–195, Springer, 2007.
41. T. Suzaki and K. Minematsu, “Improving the generalized Feistel.” FSE’10 ,LNCS 6147, pp. 19–39, Springer-Verlag, 2010.
42. D. Wagner, “The boomerang attack.” FSE’99 , LNCS 1636, pp. 156–170, SpringerVerlag, 1999.

A

Test Vectors

We give test vectors of Piccolo for each key length. The data are represented inhexadecimal form.
80-bit key:
key
00112233 44556677 8899
plaintext
01234567 89abcdef
ciphertext
8d2bff99 35f84056
128-bit key:
key
00112233 44556677 8899aabb ccddeeff
plaintext
01234567 89abcdef
ciphertext
5ec42cea 657b89ff

16