Cryptography Reference
In-Depth Information
We decided to look for a strategy to generate highly likely sub key spaces in
an order, so that the key spaces which are most likely to contain the correct
key are generated first. The key spaces should still be described by a linear
equation system and should contain many (at least 2
26
or more) keys, so that
high parallel implementations which can search through such a key space as
developed for the original attack can still be used, communication overhead is
minimized and pipeline stalls due to too small key spaces are avoided. As a
result, at most 36 equations from matrix A should be used.
For the original NTW attack, it is never necessary to compute the success
probability of an equation explicitly. Instead, one can just sort all equations
by
, assuming that equations with a higher difference have a higher success
probability. We decided to compute the explicit probability for an equation from
|
|
p
v
|
. First, one can simulate the attack against 100 random keys (using the same
number of keystreams) and collect all generated equations with their voting
difference and correctness. It is now possible to compute the success probability
P
(
p
v
|
) of an equation using this data and a nearest neighbor smoother or similar
methods (e.g. kernel smoother). We used a k-nearest-neighbor smoother for this
paper.
We did not decide to compute the success probability for an equation from
the line number in the matrix A and the number of keystreams. If a systematic
problem in the keystream recovery method used would exist, this could decrease
the success probability of some equations. Using
|
p
v
|
for computing the success
probability of each equation seems to be more appropriate.
We can formulate our key ranking approach as a best-first-search over a
directed graph: Assuming that we have a set of equations
e
i
with respective
individual success probabilities
P
(
|
p
v
|
) and that the success probabilities are
independent, we can run a best-first-search for the correct key (if we use 64
equations) or for the most promising sub key space (if less than 64 equations are
used). We assume that the set of possible keys or sub key spaces is a directed
graph
G
=(
V,E
). A node
v
consists of a vector
c
that indicates which equation
e
i
is correct (
c
i
= 0) and which of the equations is incorrect (
c
i
=1).Theprob-
|
p
x
i
|
ability that this node represents the correct sub key space is
i
(
).
The node with the highest probability is the node with
c
=(0
,...,
0) where all
equations are assumed to be correct. An edge (
v
1
,v
2
)existsif
v
1
and
v
2
differ
only in a single equation, which is assumed to be correct in
v
1
but assumed to
be incorrect in
v
2
.
We can now run a best-first search for the correct sub key space on this graph
starting at the node with the highest success probability. Using 64 equations
would guarantee that all keys are visited in the exact order of probability, how-
ever we think that the number of equations should be limited so that not too
much time is spent for generating the keys to check and highly parallel hard-
ware like CUDA graphics cards or FPGAs can be used in an ecient way. Using
some kind of data structure for the queue in the best-first-search which allows
inserts, searches and removals in
O
(log(
n
)) makes generating the sub key spaces
very time ecient. However, memory consumption increases because up to
m
|c
i
− P
(
|p
x
i
|
)
|
·
g
Search WWH ::
Custom Search