Grain-128AEAD v2 Specification
Grain-128AEADv2 - A lightweight AEAD
stream ciphe
Cover sheet
Martin Hell, Lund University, Sweden
Thomas Johansson, Lund University, Sweden
Alexander Maximov, Ericsson AB, Sweden
Willi Meier, FHNW, Switzerland
Jonathan Sönnerup, Lund University, Sweden
Hirotaka Yoshida, AIST, Japan
Co
esponding submitter:
Hirotaka Yoshida
Cyber Physical Security Research Center (CPSEC),
National Institute of Advanced Industrial Science and Technology (AIST),
2-3-26 Aomi, Koto-ku, Tokyo, XXXXXXXXXX, Japan
XXXXXXXXXX
phone: XXXXXXXXXX
Backup point of contact:
Martin Hell
Dept. of Electrical and Information Technology
Box 118, Lund University, Sweden
XXXXXXXXXX
phone: XXXXXXXXXX
1
Grain-128AEADv2
Contents
1 Introduction 3
1.1 NIST requirements . . . . . . . . . . . . . . . . XXXXXXXXXX3
1.2 Acknowledgments . . . . . . . . . . . . . . . . . XXXXXXXXXX5
2 Algorithm Specification 6
2.1 Building Blocks and Functions . . . . . . . . . . XXXXXXXXXX6
2.2 Key and Nonce Initialization . . . . . . . . . . . XXXXXXXXXX8
2.3 Operating Mode . . . . . . . . . . . . . . . . . . XXXXXXXXXX9
2.4 Keystream Limitation . . . . . . . . . . . . . . XXXXXXXXXX10
2.5 Authenticated Encryption with Associated Data XXXXXXXXXX10
2.6 Using Grain-128AEADv2 with NIST API . . . . XXXXXXXXXX11
3 Design Rationale 14
3.1 Short History of the Grain Family of Stream Ciphers XXXXXXXXXX
3.2 Update to Grain-128AEADv2 . . . . . . . . . . XXXXXXXXXX15
3.3 Differences Between Grain-128AEADv2 and Grain-128a XXXXXXXXXX
3.4 Design Choices for Individual Building Blocks . XXXXXXXXXX17
4 Security Analysis and Cryptanalytic Attacks 21
4.1 General Security Analysis . . . . . . . . . . . . XXXXXXXXXX21
4.2 Linear Approximations . . . . . . . . . . . . . . XXXXXXXXXX23
4.3 Co
elation Attacks . . . . . . . . . . . . . . . . XXXXXXXXXX23
4.4 Chosen IV Attacks . . . . . . . . . . . . . . . . XXXXXXXXXX24
4.5 Fault Attacks . . . . . . . . . . . . . . . . . . . XXXXXXXXXX25
4.6 Security of the Authentication . . . . . . . . . . XXXXXXXXXX26
5 Hardware Implementation 26
6 Advantages and Limitations 28
6.1 Suitability of Grain-128AEADv2 in IoT/Embedded Systems XXXXXXXXXX
6.2 Other Aspects . . . . . . . . . . . . . . . . . . . XXXXXXXXXX29
7 Test Vectors 30
2
Grain-128AEADv2
1 Introduction
This is the second version of the Grain-128AEAD documentation, detailing the
Grain-128AEADv2 design. This is the specification for round 3 in the NIST LWC
standardization process. The main difference with the first version is a tweak
added in the initialization. This document is intended to be self-contained, and
therefore it largely overlaps with the specification for the first version.
Grain-128AEADv2 is an authenticated encryption algorithm with support fo
associated data. The specification is closely based on Grain-128a, introduced in
2011, which has, already for several years, been analyzed in the literature. To
enefit from the maturity of the Grain family, our strategy in the design of Grain-
128AEADv2 is to have the changes made to Grain-128a as small as possible.
This allows us to argue for the security of the cipher, based on previous results
on Grain-128a. One notable change is added security against key reconstruction
from a known internal state. Increased understanding of this feature is also the
motivation for the update from Grain-128AEAD to Grain-128AEADv2.
Grain-128a is in turn based on Grain v1 and Grain-128, which have both
een extensively analyzed, providing much insight into the security of the design
approach. All Grain stream ciphers also allow the throughput to be increased by
adding additional copies of the Boolean functions involved.
1.1 NIST requirements
This section provides a mapping of the requirements given by NIST [45] to the
espective sections in this document and supporting files.
1.1.1 Cover Sheet
The cover sheet with the name of the submission, name of the submitters, in-
cluding contact information for the co
esponding submitter and a backup point
of contact is provided as the first page of this document.
1.1.2 Algorithm Specification and Supporting Documentation
The documentation requirements are provided in [45, Section 2.2].
• The complete written specification of the algorithm is given in Section 2.
3
Grain-128AEADv2
• The design rationale and an explanation for the different design decisions
are given in Section 3. This also includes specific constants that are used
in the algorithm.
• The submission describes a single AEAD algorithm, denoted Grain-128AEADv2
that takes a 128-bit key and a 96-bit nonce. It does not implement hashing
functionality.
• Grain-128AEADv2 has been designed with 128-bit security in mind. Thus,
efe
ing to the NIST requirements [45, Section 3.1], we expect that crypt-
analytic attacks require at least 2112 computations on a classical compute
in a single key setting.
• Known cryptanalytic attacks, using attacks on Grain-128a as a reference
point, on the algorithm are specified in Section 4.
• Advantages and limitations of Grain-128AEADv2 are given in Section 6.
• References given in Section 4 provide a list of published materials that
analyze the security of the very similar Grain-128a.
1.1.3 Source Code and Test Vectors
These requirements are provided in [45, Section 2.3]. Source code of a reference
implementation is provided separately from this document. Test vectors from the
eference implementation are provided in Section 7.
1.1.4 AEAD Requirements
The AEAD requirements are provided in [45, Section 3.1].
• Grain-128AEADv2 takes a variable-length plaintext, variable-length asso-
ciated data, a fixed-length nonce (IV) of size 96 bits, and a fixed-length key
of size 128 bits. The output is a variable length ciphertext. The plaintext
is recovered from a valid ciphertext. An invalid ciphertext does not return
a plaintext.
• For a single key, the nonce must be unique. If the nonce is not unique, i.e.,
it is repeated for the same key, the algorithm leaks information about the
two plaintext, and the MAC can be forged.
4
Grain-128AEADv2
• The Grain-128AEADv2 is one algorithm with the only supported parame-
ters are 128-bit key and 96-bit nonce.
• Grain-128AEADv2 is a bit oriented stream cipher and it thus also allows
yte string inputs. The message padding of one ’1’ bit, can in an environ-
ment that only operates with bytes, be replaced by a ’1’ followed by seven
’0’s. This will not affect the MAC result.
• Grain-128AEADv2 has a keystream limitation of 280 bits, i.e., a pre-output
stream limitation of 281 bits.
1.2 Acknowledgments
We wish to thank Martin AÌŠgren, who has been involved in designing a previous
variant in the Grain family of stream ciphers. His work has been valuable to the
understanding of the cipher and design choices made to Grain-128AEADv2 have
used inspiration from his work.
5
Grain-128AEADv2
2 Algorithm Specification
Grain-128AEADv2 consists of two main building blocks. The first is a pre-output
generator, which is constructed using a Linear Feedback Shift Register (LFSR),
a Non-linear Feedback Shift Register (NFSR) and a pre-output function, while
the second is an authenticator generator consisting of a shift register and an
accumulator. The design is very similar to Grain-128a, but has been modified to
allow for larger authenticators and to support AEAD. Moreover, the modes of
usage have been updated.
2.1 Building Blocks and Functions
The pre-output generator generates a stream of pseudo-random bits, which are
used for encryption and the authentication tag. It is depicted in Fig. 1. The
LFSR
Accumulato
Registe
NFSR
g f
h
7 2 7
6524
mi
z'i zi
y512+t
...
/
Figure 1: An overview of the building blocks in Grain-128AEADv2.
content of the 128-bit LFSR is denoted St = [s
t
0, s
t
1, . . . , s
t
127] and the content
of the 128-bit NFSR is similarly denoted Bt = [
t
0,
t
1, . . . ,
t
127]. These two shift
egisters represent the 256-bit state of the pre-output generator.
The primitive feedback polynomial of the LFSR, defined over GF(2) and de-
noted f(x), is defined as
f(x) = 1 + x32 + x47 + x58 + x90 + x121 + x128.
6
Grain-128AEADv2
The co
esponding update function of the LFSR is given by
st+1127 = s
t
0 + s
t
7 + s
t
38 + s
t
70 + s
t
81 + s
t
96
= L(St).
The nonlinear feedback polynomial of the NFSR, denoted g(x) and also defined
over GF(2), is defined as
g(x) = 1 + x32 + x37 + x72 + x102 + x128 + x44x60 + x61x125
+ x63x67 + x69x101 + x80x88 + x110x111 + x115x117
+ x46x50x58 + x103x104x106 + x33x35x36x40
and the co
esponding update function is given by
t+1127 = s
t
0 +
t
0 +
t
26 +
t
56 +
t
91 +
t
96 +
t
3
t
67 +
t
11
t
13
+ bt17
t
18 +
t
27
t
59 +
t
40
t
48 +
t
61
t
65 +
t
68
t
84
+ bt22
t
24
t
25 +
t
70
t
78
t
82 +
t
88
t
92
t
93
t
95
= st0 + F(Bt).
Nine state variables are taken as input to a Boolean function h(x). Two of
these bits are taken from the NFSR and seven are taken from the LFSR. The
function is defined as
h(x) = x0x1 + x2x3 + x4x5 + x6x7 + x0x4x8,
where the variables x0, . . . , x8 co
espond to, respectively, the state variables
t12, s
t
8, s
t
13, s
t
20,
t
95, s
t
42, s
t
60, s
t
79 and s
t
94.
The output of the pre-output generator, is then given by the pre-output func-
tion
yt = h(x) + s
t
93 +
∑
j∈A
tj,
where A = {2, 15, 36, 45, 64, 73, 89}.
The authenticator generator consists of a