2 Catalog and Illustrative Examples of Lightweight Cryptographic Primitives
45
2.3.2.1 Generic Approach
Certain stream ciphers can be attacked by employing the following approach: (1)
Assuming the availability of a sufficiently long sample for recovering an internal
state, we develop a dedicated TMD-TO attack which allows recovery of the internal
state for a certain segment of the available sample. (2) The dedicated TMD-TO
attack is developed over a subset of the internal states in which certain parts of
the internal state are preset or algebraically recovered based on the considered
keystream segment. Assume that the state size is ν and that certain bits (say β) of the
internal state are fixed according to a specific pattern. Then, with this information,
for the corresponding keystream segment, we try to obtain some more bits (say γ )
of the internal state. The final goal is to recover the unknown bits of the internal
state δ = ν − β − γ by employing a suitable TMD-TO attack. Accordingly, the
cryptanalysis is based on the following framework:
• preset certain bits of the internal state to a suitable pattern (the all-zeros pattern,
for example);
• for a given m-bit prefix (usually an m-zeros prefix) of the keystream segment,
algebraically recover up to m bits of the internal state assuming that the remaining
internal state bits are known;
• recover the assumed bits of the internal state by employing the dedicated TMDTO attack.
2.3.2.2 Summary of Cryptanalysis of Grain-v1 Employing
Guess-and-Determine and Dedicated TMD-TO Approaches
The internal state of Grain-v1 consists of 160 bits corresponding to the employed
nonlinear and linear feedback shift registers NFSR and LFSR, respectively. For
a given parameter m, let Ω (m) be a subset of all internal states where three
m-length segments of all zeros exist which implies that the state generates m
consecutive zero outputs. Let the vectors b (i) and s (i) be the states of the NFSR
and LFSR, respectively, at the instant i, s (i) = [s i , s i+1 , . . . , s i+79 ] and b (i) =
[b i , b i+1 , . . . , b i+79 ]. Let u (i) be the internal state of Grain-v1, and accordingly,
u (i) = [s (i) ||b (i) ] = [s i , s i+1 , . . . , s i+79 , b i , b i+1 , . . . , b i+79 ]. For a given parameter
m, the set Ω (m) is the set of internal state vectors defined as follows Ω (m) =
{u (i) |s i+25−j = 0, s i+64−j = 0, b i+63−j = 0 ,
j = 0, 1, . . . , m − 1}.
Consequently, the number of internal states belonging to Ω (m) is upper-bounded
by 2 160−3m .
The internal state recovery is based on the following: Whenever we observe an
m-zeros prefix of a keystream segment, we suppose that the segment is generated
by an internal state belonging to Ω (m) and we employ a dedicated TMD-TO attack
to check the hypothesis. The complexities of this cryptanalysis and a related one are
illustrated in Table 2.12.
45
2.3.2.1 Generic Approach
Certain stream ciphers can be attacked by employing the following approach: (1)
Assuming the availability of a sufficiently long sample for recovering an internal
state, we develop a dedicated TMD-TO attack which allows recovery of the internal
state for a certain segment of the available sample. (2) The dedicated TMD-TO
attack is developed over a subset of the internal states in which certain parts of
the internal state are preset or algebraically recovered based on the considered
keystream segment. Assume that the state size is ν and that certain bits (say β) of the
internal state are fixed according to a specific pattern. Then, with this information,
for the corresponding keystream segment, we try to obtain some more bits (say γ )
of the internal state. The final goal is to recover the unknown bits of the internal
state δ = ν − β − γ by employing a suitable TMD-TO attack. Accordingly, the
cryptanalysis is based on the following framework:
• preset certain bits of the internal state to a suitable pattern (the all-zeros pattern,
for example);
• for a given m-bit prefix (usually an m-zeros prefix) of the keystream segment,
algebraically recover up to m bits of the internal state assuming that the remaining
internal state bits are known;
• recover the assumed bits of the internal state by employing the dedicated TMDTO attack.
2.3.2.2 Summary of Cryptanalysis of Grain-v1 Employing
Guess-and-Determine and Dedicated TMD-TO Approaches
The internal state of Grain-v1 consists of 160 bits corresponding to the employed
nonlinear and linear feedback shift registers NFSR and LFSR, respectively. For
a given parameter m, let Ω (m) be a subset of all internal states where three
m-length segments of all zeros exist which implies that the state generates m
consecutive zero outputs. Let the vectors b (i) and s (i) be the states of the NFSR
and LFSR, respectively, at the instant i, s (i) = [s i , s i+1 , . . . , s i+79 ] and b (i) =
[b i , b i+1 , . . . , b i+79 ]. Let u (i) be the internal state of Grain-v1, and accordingly,
u (i) = [s (i) ||b (i) ] = [s i , s i+1 , . . . , s i+79 , b i , b i+1 , . . . , b i+79 ]. For a given parameter
m, the set Ω (m) is the set of internal state vectors defined as follows Ω (m) =
{u (i) |s i+25−j = 0, s i+64−j = 0, b i+63−j = 0 ,
j = 0, 1, . . . , m − 1}.
Consequently, the number of internal states belonging to Ω (m) is upper-bounded
by 2 160−3m .
The internal state recovery is based on the following: Whenever we observe an
m-zeros prefix of a keystream segment, we suppose that the segment is generated
by an internal state belonging to Ω (m) and we employ a dedicated TMD-TO attack
to check the hypothesis. The complexities of this cryptanalysis and a related one are
illustrated in Table 2.12.