Cryptography Reference
In-Depth Information
where
for 0 ≤ i ≤ 11, l
i
= (P[500 + i])
(0)
,u
i
= 256 + (P[500 + i])
(2)
& for 12 ≤ i≤ 511, l
i
= (P
N
[i−12])
(0)
,u
i
= 256 + (P
N
[i−12])
(2)
.
(10.17)
⊕P
N
[i] of system (10.16) of equations
are known for all i = 0,1,...,511. Thus, there are 512 equations in ≤ 512
unknowns. Simply applying Gauss elimination would require a complexity of
512
3
= 2
27
. However, according to Lemma 10.5.1, a unique solution does not
exist for any such system and hence a different approach is required to solve
the system.
Here l
i
, u
i
and the right-hand side s
2,i
Lemma 10.5.1. Suppose r + s linear equations are formed using variables
from the set {x
1
, x
2
, ..., x
r
, y
1
, y
2
, ..., y
s
}. If each equation is of the form
x
i
+y
j
= b
ij
for some i in [1,r] and some j in [1,s], where b
ij
's are all known,
then such a system does not have a unique solution.
Proof: Consider the (r+s)×(r+s) coe
cient matrix A of the system with
the columns denoted by C
1
,...,C
r+s
, such that the first r columns C
1
,...,C
r
correspond to the variables x
1
,...,x
r
and the last s columns C
r+1
,...,C
r+s
correspond to the variables y
1
,...,y
s
. Every row of A has the entry 1 in
exactly two places and the entry 0 elsewhere. The first 1 in each row appears
in one of the columns C
1
,...,C
r
and the second 1 in one of the columns
C
r+1
,...,C
r+s
. After the elementary column transformations C
1
← C
1
+
... + C
r
and C
r+1
← C
r+1
+ ... + C
r+s
, the two columns C
1
and C
r+1
has
1's in all the rows and hence become identical. This implies that the matrix
is not of full rank and hence a unique solution does not exist for the system.
The left-hand side of every equation in system (10.16) is of the form Q[l
i
]+
Q[u
i
], where 0 ≤ l
i
≤ 511. Taking r = s = 256,
x
i
= Q[i− 1], 1 ≤ i ≤ 256 and y
j
= Q[255 + j], 1 ≤ j ≤ 256, we see that
Lemma 10.5.1 directly applies to this system, establishing the non-existence
of a unique solution. At this stage, one could remove the redundant rows to
find a linear space which contains the solution. However, it is not clear how
many variables need to be guessed to arrive at the final solution. A graph
theoretic approach has been used in [137] to derive the entries of the array Q
e
ciently, by guessing the value of only a single variable.
Definition 10.5.2. System (10.16) of 512 equations can be represented in
the form of a bipartite graph G = (V
1
,V
2
,E), where V
1
= {0,...,255}, V
2
=
{256,...,511} and for each term Q[l
i
] + Q[u
i
] of (10.16), there is an edge
{l
i
,u
i
≤ 255 and 256 ≤ u
i
∈V
2
. Thus, |E| = 512 (counting repeated edges, if
any). We call such a graph G, with the vertices as the indices of one internal
array of HC-128, as the index graph of the state of HC-128.
}∈E, l
i
∈V
1
and u
i
Lemma 10.5.3. Let M be the size of the largest connected component of the
index graph G corresponding to block B
2
. Then M out of 512 words of the
array Q can be derived in 2
32
search complexity.