FPGA Implementation of an Improved Attack against the DECT Standard Cipher - Information Security and Cryptology-ICISC 2010 - page 181

k . All possible solutions of the system (using 30 equations leads to 2 64 − 30 =2 34
possible solutions) are then checked against some reference keystreams to check
if one of them generates the reference keystream. If so, it can be assumed that
this solution is in fact the correct key for the cipher.

4KeyRanking

To improve the original NTW attack, we introduce a key ranking procedure. The

original NTW attack generates equations of the form i a i k i = where k i is

a bit of the key and a i is either 0 or 1. The left part of the equation only depends
on the feedback polynomials of the registers. The right part of the equation is
either 0 or 1, determined by a voting system. The difference between the number
of votes for 0 and 1 is denoted by

{

0 , 1

}

| p v | . In the original attack, the equations are

sorted by and the topmost equations are assumed to be correct. Using many

equations results only in a small remaining key space which needs to be searched,
but increases the probability that at least one equation is incorrect and the key
is not found in the set of solutions of the linear equation system.
To improve the attack, we first checked, with which probability the individual
equations are correct. We ran 100 experiments against randomly chosen keys and
counted in how many times the first, second, third... equation in A was correct.
The results are shown in figure 1. The first 10 equations in A (see Section 3) are
correct with a probability of at least 99%. This makes it highly unlikely that one
of the first 10 equations is incorrect. Starting from equation 30, the probability
that the equation is correct drops down to 70-60% for equation 55. This makes
these equations only of minor use for the attack and one can assume that at
least one of these equations is incorrect with high certainty.

| p v |

100

90

80

70

60

32768 keystreams
49152 keystreams

50

0 10 20 30 40 50

n'th equation in matrix A

Fig. 1. Success probabilities of the individual equations in matrix A