Cryptography Reference
In-Depth Information
solutions need to be tracked in parallel, when
m
equations are used and
g
sub
key spaces have been generated.
4.1
Performance Results
Executing the old attack against 100 randomly chosen keys only resulted in 71%
success rate with 2
15
keystreams available and 2
42
keys checked. Using our new
key ranking method allowed us to recover the key in 90% of all tests, with also
2
42
keys checked in total. We used 35 instead of 22 equations, but checked the
8192 most likely sub key spaces. Figure 2 includes more details.
100
90
80
70
60
50
40
30
20
10
old NTW attack
new attack
0
0
8192
16384
24576
32768
40960
49152
57344
65536
keystreams available
Fig. 2.
Success rate of the improved attack
Another advantage of our key ranking strategy is, that the attack time doesn't
need to be fixed at the beginning of the attack. Using just a single equation sys-
tem has the disadvantage that all solutions are checked in an order not depending
on their probability. Checking an equation system with 2
n
solutions will give the
correct key after having checked 2
n−
1
solutions in average (if all equations in the
system are correct). Using our approach makes it possible to start the attack with
some reasonable parameters and then just wait for the correct key. If a lot of equa-
tions in A are correct, the correct key will be found much faster in average than
with the original approach. If A contains a lot of incorrect equations, the attack
will take longer, but one can decide to continue or cancel the attack at any point of
time (assuming that enough main memory for the best-first-search is available).
To speed up the final search through all generated sub key spaces, we present
an FPGA implementation of the final search in the next part of this paper.
5 FPGA Implementation
FPGAs are very well-suited for an implementation of the final search phase of a
sub key space. Linear Feedback Shift Registers form the main part of the DSC
Search WWH ::
Custom Search