Cryptography Reference
In-Depth Information
probability is twice the random association 2
−8
. Theorem 10.4.4 is a Glimpse-
like theorem on HC-128 that shows the leakage of state information into the
keystream with a probability ≈ 2
−15
, that is much more than 2
−31
(two times
the random association 2
−32
). This probability is in fact two times the square-
root of the random association. However, in RC4, the Jenkins' Correlation
turns the key-state correlations into key-keystream correlations that lead to
practical attacks. On the other hand, in case of HC-128, no key-state corre-
lations have been found so far. So the state leakage in HC-128 keystream, as
of now, does not lead to any real attack on HC-128.
10.5 Constructing Full-State Given Only Half-State In-
formation
Recently, it has been shown in [137] that the knowledge of any one of
the two internal state arrays of HC-128 along with the knowledge of 2048
keystream words is su
cient to construct the other state array completely in
2
42
time complexity. Though this analysis does not lead to any attack on HC-
128, it reveals a nice combinatorial property of HC-128 keystream generation
algorithm. Moreover, the secret key being derivable from any state [97], only
half of the state is now su
cient to determine the key uniquely. This analysis
can also serve as a general model to study stream ciphers that have a similar
dual state internal structure. We present this analysis in this section.
There are two internal state arrays of HC-128, P and Q, each containing
512 many 32-bit words. The keystream is generated in blocks of 512 words.
Within a block, one of these arrays gets updated and the keystream word is
produced by XOR-ing the updated entry with the sum of two words from the
other array. The role of the two arrays is reversed after every block of 512
keystream words generation.
10.5.1 Formulation of Half-State Exposure Analysis
Without loss of generality, let us consider four consecutive blocks B
1
, B
2
,
B
3
and B
4
of keystream generation such that Q is updated in blocks B
1
and B
3
and P is updated in blocks B
2
and B
4
. Suppose the keystream
words corresponding to all of these four blocks are known. Henceforth, by
the symbols P and Q, we will denote the arrays after the completion of block
B
1
and before the start of block B
2
. After the completion of block B
2
, Q
remains unchanged and P is updated to, say, P
N
. After the completion of
block B
3
, Q would again be updated to, say, Q
N
.
