Cryptography Reference
In-Depth Information
1. For each possible set of output bits in the first round, which Matsui calls a
mask
, set
O
1
to be the mask,
and do the following:
(a) Set
p′
1
to be the maximum probability for any linear expression that outputs
O
1
.
(b) If the best expression starting with
p′
1
is less than the probability of , then we skip back to Step
1 (and try the next value of
O
1
). This is because there is no way, using
p′
1
,
to obtain an expression
better than .
(c) Go to Round 2.
2. If no key was found, return .
Round 2:
1. For each possible value of the input bit mask
(I
2
)
and output bit mask (
O
2
):
(a) Let
p′
2
be the probability of the input bits leading to the output bits (i.e., the probability of the
linear expression I
2
⊕
O
2
= 0).
(b) If the expression starting with
p
′
1
and
p
′
2
can't do better than , try the next value for
I
2
and
O
2
.
(c) Otherwise, go to Round 3.
2. If none of the input and output masks work, return to Round 1.
Rounds 3, 4, ... , (n - 1):
1. Let the round number be
i.
2. For each possible value of the input bits, I
i
:
(a) Set
O
i
=
O
i-2
⊕
I
i-1
(because of the Feistel structure).
(b) Set
p′
i
to be the probability for the linear expression of
I
i
yielding
O
i
.
(c) If the linear expression involving
p′
1
, p′
2
,. . ., p′
i
is not better than , then try the next value of
I
i
.
(d) Otherwise, call the next round (
i
+ 1).
3. Return to the previous round.
Round n:
1. Set O
n
= O
n-2
⊕
I
n-1
.
2. Set p′
n
to be the maximum probability possible for any input giving O
n
.
3. If the expression using
p′
1
, p′
2
,. . ., p′
n
is better than , then set to be this new expression.
4. Return to the previous round.
AlthoughMatsui'salgorithm worksprettywellforfindinglinear expressionsofDES,ithastwodeficiencies:
1. Several expressions explored will be equivalent to other expressions already searched, because of sym-
metry in the cipher.
2. Several expressions explored are not truly valid candidates.
Tocombatthesedifferences,Ohtaetal.[6]inventedanothersearchalgorithmaimingtoeliminatetheseprob-
lems. Their algorithm is mostly successful in doing this; however, it comes at the cost of increased complexity
and sometimes can require more computing time (such as for DES keys). For more information on their method
and analysis of Matsui's method, see Reference [6].
Search WWH ::
Custom Search