Cryptography Reference
In-Depth Information
In the PRGA, k is used for updating S as well as for masking the output.
Input:
1. Key-dependent scrambled array S[0...N −1].
2. Key-dependent secret variable k.
Output: Pseudo-random keystream bytes z.
Initialization:
i = j = 0;
Output Keystream Generation Loop:
i = (i + 1) mod N;
j = (j + S[i]) mod N;
k = (k + S[j]) mod M;
Output z = S [(S[i] + S[j]) mod N + k)] mod M;
S [(S[i] + S[j]) mod N] = (k + S[i]) mod M;
Algorithm 9.2.4: GGHN PRGA
A distinguished attack on NGG using only 100 keystream words appeared
in [186]. Later, GGHN was attacked in [183] that built a distinguisher based on
a bias in the first two words of the keystream, associated with approximately
2
30
secret keys.
In 2005, an RC4-like stream cipher Py (pronounced Roo) was submit-
ted [17] to the eSTREAM project. The cipher produces two 32-bit words as
output at each step. A building block of the cipher is rolling arrays. The
designers of Py define the rolling array to be a vector whose entries are cycli-
cally rotated by one place at every step. Py uses one word variable s and
two rolling arrays P and Y , where P is a permutation over Z
256
, indexed by
0,...,255, and Y is a 260-word array of 32-bit words, indexed by −3,...,256.
The key schedule of Py initializes the variable s and the array Y from the
secret key. We omit the key scheduling here and discuss only the keystream
generation. Interested readers may look into [17] for further details.
In [17], a variant of Py, called Py6, was also presented, where the permu-
tation P is reduced to be over Z
64
(i.e., each entry is of 6 bits) and the size
of Y is reduced to 68 entries, each being a 32-bit word. The speed of Py6 is
essentially the same as Py. The smaller size of the internal state allows only
faster key and IV setup.
In 2006, a distinguishing attack on Py was reported [140]. It requires
2
84.7
randomly chosen key/IVs and the first 24 output bytes for each key. To
resist this attack, the designers of Py came up with a variant, called Pypy [18].
However, a series of papers [77,189-191] revealed several weaknesses of the Py
family of ciphers and the cipher could not reach the final round of eSTREAM.
Again the designers of Py came up with some variants [19], tweaking the IV
setup, but these variants were also attacked [151-154].
