Cryptography Reference
In-Depth Information
of 512 keystream words. Thus, the required amount of data is 4 512 = 2
11
no. of 32 (= 2
5
)-bit keystream words.
From Step 1 in the First Phase up to Step 7 of the Second Phase, the
total time required is linear in the size of P (or Q), i.e., of complexity 2
9
.
Step 8 in the Second Phase of Algorithm 10.5.1 can be performed through
depth-first search which requires O(|V
1
| + |V
2
| + |E|) time complexity. For
|V
1
| = 256 and |E| = 512, the value turns out to be 2
10
. After
this, the guess in Step 10 of Algorithm 10.5.1 consumes 2
32
time and for each
such guess, the complete Phases 3, 4 and 5 together take time that is linear in
the size of the array Q, i.e., of complexity 2
9
. Thus, the total time required
is 2
9
+ 2
10
+ 2
32
2
9
< 2
42
.
Note that for system (10.16) of equations, one must verify the solution
by first generating some keystream words and then matching them with the
observed keystream, as is done in the Fifth Phase of Algorithm 10.5.1. During
Step 10 in the Second Phase, one may exploit the cycles of the largest com-
ponent to verify correctness of the guess. If the guessed value of a variable in
a cycle does not match with the value of the variable derived when the cycle
is closed, we can discard that guess. However, in the worst case, all the 2
32
guesses have to be tried and if there is no conflict in a cycle, the guess has
to be verified by keystream matching. Thus, it is not clear if there is any
significant advantage by detecting and exploiting the cycles.
| = 256, |V
2
10.6 Design Modification with Respect to Known Ob-
servations
This section is also based on [137] which advocates two design goals.
• to guard against the available analysis in literature and
• not to sacrifice the speed in the process.
Thus, an attempt is made to keep the same structure as the original HC-128
with minimal changes.
h
1
(.) as well as h
2
(.) makes use of only 16 bits from the 32-bit input and
this fact leads to all the vulnerabilities discussed so far in this Chapter. Thus,
the form of h
1
(.),h
2
(.) must be modified so as to incorporate all the 32 bits
of their inputs. In the new versions of these functions (equation (10.19)),
XOR-ing the entire input with the existing output (sum of two array entries)
is suggested. However, certain precautions may need to be taken so that other
security threats do not come into play.
h
1
and h
2
are modified as follows.
(Q[x
(0)
] + Q[256 + x
(2)
])⊕x.
h
N1
(x)
=
(10.19)
(P[x
(0)
] + P[256 + x
(2)
])⊕x.
h
N2
(x)
=
