Cryptography Reference
In-Depth Information
However, the output differential (of
F
, which could be a round function, or one or more rounds) is normally
referred to as the second-order differential. For the first-order output differentials, we would then have
And for the second-order output differential:
This would give us the second-order characteristic:
I use the symbol ''
⇒
2
'' to represent that this is not an ordinary characteristic.
This process can be extended further to create higher-order differentials.Formally, for these, we can use a
slightly different notation from Reference [9], as the above notation can quickly become a bit cumbersome. Fur-
thermore,the above notation applies only to standard binary ciphers. For ones that take place, for example, in
finite fields, we need a slightly different notation, since the operation to take the difference might be different
from the one to add a difference.
Let a first-order differential of the output of a round function
F
of an input point
X
be denoted
where
A
1
is the differential of the input. For a second-order differential, we have
We'll expand this so it is a little clearer:
This technique of higher-order differentials can be very useful. In Reference [9], Knudsen shows that the
round function
f
(
x
+
k
)
2
mod
p
, where
p
is prime (and has a block size of twice the number of bits in
p
), has no
useful first-order differentials. However, if we use second-order differentials, we can break the round function
very easily.
7.12 Truncated Differentials
In standard differential cryptanalysis, we take a fixed difference in the input and rely on this difference produ-
cing a chain reaction of a step-by-step series of differences, which eventually trickle down to a point that we
can measure. When we measure at this point, we are looking for an exact difference between two ciphertexts:
We count these exact differences, and ignore any plaintext-ciphertexts pairs that do not have this difference in
the ciphertext.
Tobemorespecific,intheabovestandarddifferentialattacks,wewouldchecktoseeiftherewasadifference
by XORing the two values and checking the value of the output. If it matched what we expected, then it's a hit.
Otherwise, it's not, even if all of the bits we expected to be flipped were, but some extra bits were also flipped.
The concept of
truncated differentials
relaxes the constraint that we need to look for the entire difference
to be exactly what we use (in the input difference) or what we predict (in the output difference). If we have a
normal characteristic, with two differentials:
then we have a truncated differential:
Search WWH ::
Custom Search