Cryptography Reference
In-Depth Information
Input: Two key-dependent internal state arrays:
1. P[0...511];
2. Q[0...511];
Output: Pseudo-random keystream words s
t
's.
i = 0;
repeat
j = i mod 512;
if (i mod 1024) < 512 then
P[j] = P[j] + g
1
(P[j ⊟ 3],P[j ⊟ 10],P[j ⊟ 511]);
s
i
= h
1
(P[j ⊟ 12])⊕P[j];
end
else
Q[j] = Q[j] + g
2
(Q[j ⊟ 3],Q[j ⊟ 10],Q[j ⊟ 511]);
s
i
= h
2
(Q[j ⊟ 12])⊕Q[j];
end
i = i + 1;
until enough keystream bits are generated ;
Algorithm 10.1.2: HC-128 PRGA
10.2 Linear Approximation of Feedback Functions
The analysis in this section is based on [105]. Two functions g
1
,g
2
used
in HC-128 are of similar kind. The two addition (“+”) operations in g
1
or
g
2
are believed to be a source of high nonlinearity. However, good linear
approximation can be found by using the result of linear approximation of the
addition of three integers.
Linear approximations of modulo-2
n
addition of k many n-bit integers
have been studied in [172]. For k = 2, the probability of the equality of XOR
and modulo-2
n
sum in the b-th least significant bit tends to
2
as b increases.
Below, the case for k = 3 is briefly discussed, an instance of which would be
used in approximating g
1
,g
2
.
Recall that the b-th least significant bit of an n-bit word w is given by
[w]
b
, 0 ≤ b ≤n−1, i.e.,
w = ([w]
n−1
,[w]
n−2
,...,[w]
1
,[w]
0
).
This notation is also extended to [w]
b
, where b > n− 1. In that case, [w]
b
means [w]
b mod n
.
Let X,Y,Z be three n-bit integers;
S = (X + Y + Z) mod 2
n
