Cryptography Reference
In-Depth Information
We will then collect many plaintext-ciphertext pairs, and attempt to brute-force keys as was done previously:
by taking each potential key and calculating the left-hand side of the equation's value.
Our first instinct in using multiple linear approximations might tell us to just perform this whole process
again, with an entirely new linear approximation for the cipher. However, it is better to try to obtain a linear
approximation that has the same right-hand side as the other approximation, that is, intersects exactly the same
key bits. If both linear expressions are affected by the exact same key bits, then the two linear approximations
will match up better and can be “combined.”
When combining two linear approximations, we use a weighted sum to add together the counts acquired
from the plaintext-ciphertext pairs. If the two linear expressions have different right-hand sides, then we might
inadvertently have our overall biases reversed (since one's right-hand side might evaluate to be 0 and the other
to be 1), which would make them not line up properly.
The weights multiplied against each count are simply the ratio of the bias of the expression to the sum of the
biases for all of the expressions being measured, that is,
This gives the total count ( T ) for each individual count ( T i ) multiplied by its weight.
Multiple linear approximations make a lot of sense in one way: The bulk of our work is in looping through
every single key and every single plaintext-ciphertext pair. We only have one line that actually computes the
linear expression's value, and it is not the most computationally intensive portion. It would be very easy to tack
on another computation right there, and not even come close to doubling the time requirement of running the
algorithm.
Overall, multiple linear expressionsdon'tsaveusmuchtime. Theydo,however,increase theeffectiveness of
using the same number of plaintext-ciphertext pairs by increasing the success rate of using them, and lowering
the false-positive rate. The primary difficulty in using this method is, of course, coming up with several good
linear expressions involving the same key bits.
6.9 Finding Linear Expressions
Throughout this chapter, I have glossed over finding good linear expressions. It should come as no surprise that
finding good linear expressions with high biases is a fairly difficult task, even more so to find the “best” such
expression.
Matsui developed an algorithm to perform these searches [3].
Matsui Linear Expression Search
Here, we are looking for the best linear expression, B , using induction, building from one good guess and work-
ing our way up to the best expression for a given cipher. We must assume that we already have a pretty good
expression (perhaps developed by hand), which I write as . The “closer” to B that is, the more efficient the
search. The search is split into rounds, with each one giving a linear expression for one more round of the cipher
(until all n rounds).
Round 1:
Search WWH ::




Custom Search