Cryptography Reference
In-Depth Information
Taking into account that typically the key requirements for a stream cipher are
high speed and reduced area footprint, such a countermeasure does not look very
appealing. In the case of adding redundancy-based techniques, the update operation
of the modified LFSR is not a feedback anymore but must be replaced with some
more general linear transformation. While this idea may lead to interesting research
and generate a number of papers in CHES and FDTC workshops, its practicality is
inherently limited by the detection capability of the underlying linear code. Consid-
ering that the attack models on most of the stream ciphers tolerate multi-bit faults,
implementation of error detection methods based on redundancy is likely to be almost
as costly as simple duplication of computations.
Does the absence of countermeasures mean that fault attacks on stream ciphers
are more dangerous in practice as they are more difficult to prevent than attacks on
block ciphers? We think so. Stream ciphers tend to be vulnerable to fault attacks
because the nonlinear mixing effect of the stream cipher is usually obtained in a sort
of “incremental fashion”, while block ciphers can rely on more effective mixing of
the plaintext and key material. It is thus more difficult to disturb the computations of
a block cipher “politely”, so that the output differences or any kind of relationship
between the correct and the faulty outputs make sense for further analysis. This
usually involves targeting with a rather high time precision a particular round or a
particular bit. One approach to designing a stream cipher that can be more robust
against fault attacks is to use a nonlinear function with a high degree as a feedback
and never employ linear or almost-linear feedbacks. These technique tend to involve
a larger part of the state and create a highly nonlinear bound between the state and the
output, which in turn transforms usable differential information into unexploitable
relations. This is a direct consequence of the fact that multivariate equation solving
over
F
2
is NP-complete as soon as the degree of the equation is greater than 2.
A construction akin to “tweakable” ciphers [256] may be helpful since this would
quickly raise the degree of the relations binding inputs and outputs. This cipher
design proposal suggests using a third input to the cipher, called tweak, which is
used to alter the structure of the cipher. The tweak may also be public, but must be
changed often, leading to the impossibility of collecting faults with the same cipher
structure.
Another idea could be inserting a nonlinear layer which depends on the key (like
the S-Boxes in Blowfish [362]), which would also hinder cryptanalysis, since the
attacker one would need to consider the differential relations among a family of
output functions. The only drawback of this technique is that the function family
employed to generate the nonlinear layer should be carefully chosen to avoid having
weak members, which in turn would constitute a backdoor. What about the stream
ciphers constructed by “leak extraction” from block ciphers, such as LEX [50]?
Does protecting them against fault attacks amount to protecting an underlying block
cipher? The answer is not that simple since one has to take into account the rounds
at which the extraction takes place. The protection will have to be extended to these
rounds, instead of being applied only to the last ones, which eventually most likely
will result in a full computation duplication as well.
