Evaluation of TOYOCRYPT-HS1
January 17, 2001
Information Security Research Centre
Queensland University of Technology
Ed Dawson, Andrew Clark, Helen Gustafson,
Bill Millan, Leonie Simpson

TABLE OF CONTENTS
1
2

Executive Summary ...............................................................................................3
Description of TOYOCRYPT-HS1 .......................................................................4
2.1
Notation..........................................................................................................4
3
Structural Aspects ..................................................................................................4
3.1
LFSR Operation .............................................................................................4
3.2
Analysis of the nonlinear function.................................................................4
3.3
Key Management ...........................................................................................6
3.4
Modes of Operation .......................................................................................64
Keystream Properties .............................................................................................7
4.1
Period .............................................................................................................7
4.2
Linear Complexity .........................................................................................7
4.3
Statistical Analysis.........................................................................................7
5
Possible Attacks .....................................................................................................8
5.1
Simple Attacks ...............................................................................................8
5.2
Divide and Conquer Attacks..........................................................................9
5.2.1
Attack procedure....................................................................................9
5.2.2
Attack algorithm ..................................................................................10
5.2.3
Implementation issues for the attack....................................................10
5.2.4
Attack complexity................................................................................11
5.3
Correlation Attacks ......................................................................................11
5.3.1
Fast Correlation Attacks ......................................................................11
5.3.2
Linear Cryptanalysis ............................................................................11
5.3.3
Conditional Correlation Attacks ..........................................................12
5.3.4
Inversion Attack...................................................................................12
5.4
Differential Cryptanalysis............................................................................12
5.5
Discussion ....................................................................................................12
6
Implementation ....................................................................................................13
6.1
Software .......................................................................................................13
6.2
Hardware......................................................................................................14
6.3
Key Generation ............................................................................................14
7
Conclusion ...........................................................................................................15
8
References............................................................................................................16
9
Appendices...........................................................................................................18

2

Evaluation of TOYOCRYPT-HS1 Algorithm
1 Executive Summary
This is a report on the analysis of the stream cipher, TOYOCRYPT-HS1. For thisalgorithm the evaluators have
(i)
(ii)
(iii)
(iv)
(v)

analysed structural aspects;
evaluated basic cryptographic properties;
evaluated security from attack;evaluated statistical properties;
surveyed the speed.

TOYOCRYPT-HS1 is a binary additive stream cipher which uses the output ofpseudorandom number generator (PRNG) TOYOCRYPT-HR1 for its keystream.
The TOYOCRYPT-HR1 algorithm is a standard design for a PRNG using a linear
feedback shift register (LFSR) together with a nonlinear Boolean function. This
design produces a sequence with provable security properties in relation to period andhigh linear complexity. The sequences analysed displayed white-noise statistics. The
algorithm is secure from standard cryptographic attacks including linear cryptanalysis
and correlation attacks. However, the evaluators have identified three different flaws
with the algorithm.
Flaw 1 Divide and Conquer Attack
There is a possible divide and conquer attack which is significantly faster than
exhaustive key search. We have described a simple method to change the algorithm tocorrect this flaw.
Flaw 2 Operational Speed in Software
The algorithm is very slow in software for many applications. The designers of thealgorithm have recognised this problem and have included a parallel mode ofoperation to increase speed. However, it should be noted that this will also increase
the key length and further this adaption can be applied to most PRNG’s.
Flaw 3 Key Generation
The process of using the key to generate a new primitive polynomial is very slow formany applications. The evaluators are of the opinion that due to this problem a fixed
LFSR will need to be used in many applications.

32 Description of TOYOCRYPT-HS1
The TOYOCRYPT-HS1 is a binary additive stream cipher. A binary additive stream
cipher, where both the plaintext and keystream are sequences of bits and theciphertext is the bitwise modulo two addition of the two streams, is the most common
form of synchronous stream cipher. The keystream generator is the criticalcomponent in the security of this type of stream cipher. The keystream sequence isthe output sequence from TOYOCRYPT-HR1.
The TOYOCRYPT-HR1 pseudorandom sequence generator consists of a single
regularly clocked 128-bit linear feedback shift register (LFSR) and a nonlinear
Boolean function, f, of 127 input variables. The function f is used as a nonlinear filter
function, and the generator is known as a nonlinear filter generator. The algebraic
normal form of function f is given in the Appendix B. The keystream is generated byapplying the nonlinear function f to the contents of 127 of the 128 stages of the LFSR.
Each time the LFSR is clocked, an output bit is produced.
The TOYOCRYPT-HR1 keystream generator has two 128-bit keys: a fixed key and a
stream key. The fixed key consists of the coefficients of the LFSR characteristic
polynomial, and is selected such that the characteristic polynomial is primitive andirreducible on F2. There are approximately 2120 such polynomials. The stream key isused to form the LFSR initial state, and is an arbitrary 128 bits, except for the all zero
initial state. Thus there are 2128 – 1 possible stream keys. Hence, the effective key sizeis 248.
2.1

Notation

Let the LFSR output sequence be denoted d = {d (t )}t∞=0 . Let the contents of the 128
stages of the LFSR at time t be denoted x0(t), x1(t), … , x127(t). Then d(t) = x0(t-1),
for t ≥ 1. Denote the sequence of inputs to the filter function f as X = { X (t )}t∞=0
where X(t) = {x0(t), x1(t), …, x125(t), x127(t)}. Note that x126(t) is not used as input to f.
Then the output sequence of the nonlinear filter generator is the keystreamz = {z (t )}t∞=0 , where z(t) = f(X(t)), for t ≥ 0.

3 Structural Aspects
3.1 LFSR Operation
The LFSR uses a Galois configuration rather than the more standard Fibonacciconfiguration. The Galois configuration offers a significant increase in speed over the
Fibonacci configuration in both software and hardware. In software we would
estimate on the average about a four to five times improvement in speed. The speed of
an LFSR implemented using the Galois configuration is independent of the number oftaps in the feedback polynomial since it does not require individual bits to be
extracted for use in calculating the next output bit. The Galois configuration also has
the effect that LFSR state bits change in time (due to XOR with the feedback bit).
3.2 Analysis of the nonlinear function
Linear feedback shift registers are commonly used in pseudorandom number
generators, as the properties of sequences produced by LFSRs are well known, theirimplementation in hardware or software is easy, and they allow for fast encryption

4and decryption rates. However, LFSR sequences are easily predicted from a shortsegment. For an LFSR of length 128, the entire period of the LFSR output sequencecan be determined from only 128 successive terms in the sequence if the feedback
polynomial is known, and from only 256 successive bits if the feedback polynomial isunknown [MASS 69]. This vulnerability to known plaintext attacks makes LFSRs
unsuitable for use as pseudorandom sequence generators on their own. One way tomake use of the good properties of LFSR sequences while avoiding the weakness dueto their linearity is to introduce nonlinearity by using a nonlinear Boolean function
operating on the contents of several stages of a regularly clocked LFSR. The choiceof Boolean function used contributes significantly to the cryptographic security of thepseudorandom sequence generator. In this section, the Boolean function f, used as
nonlinear combining function in the TOYOCRYPT-HR1 pseudorandom sequence
generator, is examined.
The nonlinear feedforward function f is a Boolean function that takes as input thecontents of 127 of the 128 stages of the LFSR and produces a single output bit. In[SPEC HR1] it is described as f : F2128 → F2 , although, as x126(t) is not used in f, it ismore properly described as f : F2127 → F2 . For simplicity, in this section of the report,
denote the contents of the stages of the LFSR as x0, x1, x2,… x127. (that is, drop the (t)).
As in [SPEC HR1], consider the following division of the LFSR: X = {x127, x126, XL ,XR,} where XL = {x125, x124, … , x63} and XR = {x62, x61, … , x0}.
The function f consists of a single linear term, sixty-three quadratic terms, and threeother terms of orders four, seventeen and sixty-three, respectively. The linear term isx127. The quadratic terms are products, each with one factor from XL and the otherfrom XR. Note that all terms of order greater than two are products for which all
factors are stages within XR. This is a potential weakness, which may be exploited ina divide and conquer style attack (see Section 5.2).
A basic condition for nonlinear filter generators for cryptographic applications is thatthe output sequence is balanced. This is true only if the combining function f isbalanced. As the function f is linear in the variable x127, then it is balanced. Thus the
symbol frequency of the output sequence, z, is the same as for the underlying LFSR
sequence, d.
The nonlinearity of a Boolean function is defined to be the minimum Hamming
distance between the function and any affine function. If the nonlinearity is low, thenthe function is closely approximated by an affine function, a weakness which is
exploited by fast correlation attacks. For Boolean functions with an even number of
n −1

n
−1
2

inputs, n, the maximum nonlinearity is known to be 2 − 2 , and is obtained by aclass of Boolean function known as bent functions. The subfunction h is a bent
function (note that f = h + x127 ) of 126 variables, with nonlinearity Nh = 2125- 262 (see[ROTH 76]). Bent functions are not balanced, so are unsuitable for use as combining
functions. The function f has a bent subfunction, to provide high nonlinearity, but has
an additional linear term to provide balance. For the function f, with n = 127, thenonlinearity is 2126 – 263. This implies that the bias available to any linear correlation
is upper bounded by 2-64. This value is sufficiently low to provide security (seeSection 5).
Further examination of the quadratic terms of the function f was performed. For eachquadratic term xixj, i ∈ XR and j ∈ XL, the difference j-i was calculated. The
5

differences range in value from 17 (for x62x79) to 102 (for x17x119 and x19x121).
Interestingly, as illustrated by the last example, the differences are not necessarily
unique. Differences of 34, 48, 53, 56,66,69,70,89,91,96 and 102 each occur for two
terms, the difference 50 occurs for three terms, and the difference 72 occurs for 4
terms (see Appendix C). The existence of multiple quadratic terms with common
differences is a potential weakness. As an example to illustrate the way this can be
exploited, consider the two quadratic terms x3x75 and x6x78. Whatever the value of theterm x3x75, after clocking the LFSR three times, this value is now held by x6x78 (withdue allowance for the Galois configuration of the LFSR). There are sixty-three
quadratic terms, so the proportion of quadratic terms with common differences isquite small, and perhaps cannot be fully exploited in an attack. However, changing
the arrangement of the quadratic terms in the filter function could eliminate thispotential weakness entirely. A simple way to do this is to select a different 63 bit
permutation.
3.3 Key Management
There is a 256 bit key which has two components. One component is 128 bits, called
the stream key, which is used as initial state vector for LFSR. A second component is
128 bits, called the fixed key, which is used to generate primitive polynomials todefine tap settings for LFSR using Algorithm 4.6 from [SPEC HS1]. This process isvery slow (see Section 6.3) since many different fixed keys would need to be tested
before a primitive polynomial is found. The time taken for this process may cause
problems in certain applications as explained further below.

In certain applications it is possible to overcome this problem with having to checkmultiple fixed keys by having the primitive polynomial generated offline. This
process works well in key management processes called key transport where one
party in the communication process actually creates keys. However there are many
key management protocols where this is not possible. For example, in the key
agreement process which uses the Diffie-Hellman Key Agreement algorithm eachparty in a key generation process inputs a random number. These are combined
together to form the actual key using exponentiation process. This process in mostapplications needs to be done online. This is very costly in terms of time andcommunication bandwidth if this process is required to be repeated multiple times.
It is the opinion of the evaluators, due to the above problem with the generation ofprimitive polynomials, that in many applications a fixed LFSR will be used. This
reduces the key to the 128 bit initial state vector of LFSR.
3.4 Modes of Operation
The TOYOCRYPT-HR1 algorithm is especially slow in software. In order toovercome this problem the designers have included a parallel mode of operation. This
involves the generation of n independent sequences in parallel (see [SPEC HR1])
where n is less than or equal to the word size of the processor. This leads to higher
speed for keystream generation (see Section 6.1). There is nothing unique about thisprocess. This method can be applied to almost any keystream generator. However, it
should be noted that a much larger key size is required for this parallel mode.

6

4 Keystream Properties
For keystream sequences to be used in stream ciphers which provide cryptographic
security, the keystream must possess certain basic properties. These include a large
period, large linear complexity and white-noise statistics.
Experimental results, which are included below for linear complexity and statisticalanalysis, were obtained by the evaluators using the CRYPT-X package. This is astatistical package which was designed previously by the evaluators for analysing
encryption algorithms. The relevant pages from the CRYPT-X manual have been
included as Appendix A.
4.1 Period
The keystream properties cited in [EVAL HR1] relating to period were verified. Thatis, for the TOYOCRYPT-HR1 keystream generator, the period of the sequence
produced by the keystream generator is Pz = 2128 –1.
4.2 Linear Complexity
The linear complexity test checks for the minimum amount of knowledge required toreconstruct the whole stream using a linear feedback shift register. It is difficult todetermine exactly the linear complexity of a sequence from TOYOCRYPT-HR1
equal in length to the complete period. However, bounds for this linear complexity
can be found. The evaluators are in agreement with the results in [EVAL HR1] thatthe linear complexity of a keystream sequence of length Pz has a lower and upperbound of 2124 and 2127. The selection of higher products of degree 2, 4, 17 and 63
means that the linear complexity profile of the keystream should approximately
follow the n/2 line for strings of length n.

In order to obtain empirical evidence for the linear complexity and linear complexity
profile we applied the tests from the CRYPT-X package. These linear complexity
tests were applied to ten TOYOCRYPT-HR1 output bit-streams each of length 106
bits. The results gave linear complexity values extremely close to that expected for
random data (i.e. half the bit-stream length). For more detailed results see Appendix
D. The results for the linear complexity profile indicate that, as the bit-streamincreases in length, the changes in linear complexity maintain the expected value ofhalf the stream length. These results demonstrate that the whole bit-stream is required
to re-construct the stream itself - thus giving an attacker no advantage in being able tocreate the bit-stream with a smaller number of output bits.
4.3 Statistical Analysis
A preliminary statistical analysis was carried out on TOYOCRYPT-HR1, in order toconfirm the results in [EVAL HR1]. This analysis included three tests, namely a bitfrequency test, a subblock test on 4-bit subblocks, and a runs distribution (including
the longest run). The tests were applied to 100 streams of length 20,000 bits each.
The test results show that 9 of the 300 tests (or 0.03) gave p-values below 0.05. These
results support the randomness of the TOYOCRYPT-HR1 output. The evaluators
confirmed these results using the CRYPT-X package.

Further statistical analysis was carried out by the evaluators. The above tests plus
additional statistical randomness tests from CRYPT-X were applied to much longer
7

output streams from TOYOCRYPT-HR1. A further measure of sequence complexity
was added to check the period of the output stream. The tests are based on the
hypothesis that the measure obtained from the output stream supports randomness.
The p-values obtained for the tests represent the probability that such a sample result
would be obtained if the algorithm produces a random stream. Very small p-values
would support non-randomness.
The sequence complexity test was applied to binary output streams of 106 bits (due tothe amount of time required for the test), using ten different keys. The remaining tests
were applied to ten binary output streams of 107 bits.
The subblock tests were applied to the output stream by dividing the bit-stream into
non-overlapping subblocks of lengths ranging from 2 to 30 bits. The maximum
subblock length of 30 was determined from the length of the file and the limitations of
the test applied.
Statistical Analysis Results
The results of the CRYPT-X tests are summarised using p-values in Appendix E. The
lowest p-value for any one test is 0.0007, with 24 of the 340 p-values obtained falling
below 0.05. This represents a proportion of 0.07 of the tests applied, which is above
the 0.05 level, yet not significant. Hence these results supports the randomness of theoutput from TOYOCRYPT-HR1.

5 Possible Attacks
In this section of the report, possible known plaintext attacks on the nonlinear filter
generator are investigated. It is assumed in the discussion that the structure of thegenerator is known to an attacker, and that only the keys are unknown.
For most of these attacks, the discussion assumes that the fixed key (the LFSR
feedback function) is known, and only the stream key (that is, the initial state of the
LFSR) is unknown. Such a situation is possible, as it is likely that the fixed key canbe obtained through reverse engineering (if in hardware), or by examining sourcecode (if in software). Note that if the attacks on the nonlinear filter generator are
unsuccessful when the fixed key is known, then they will also be unsuccessful when
the fixed key is unknown.
Generally, in the case where both the stream key and the fixed key are unknown, thecomputational complexity of attacks on the generator is equal to the computational
complexity of the attack for a known fixed key multiplied by 2120 (the number ofpossible LFSR feedback functions). However, this is not always the case. For
example, the simple attack based on linear complexity [MASS 69] does not require
knowledge of the LFSR feedback function, or even the length of the LFSR, so thecomplexity of this attack is unchanged by knowledge of the fixed key. However, all of
the more sophisticated attacks outlined in Section 5.2 and 5.3 below require
knowledge of this LFSR. Hence, in the case where the LFSR is unknown thecomplexity of each attack should be multiplied by a factor of 2120.
5.1 Simple Attacks
There are four simple, classical attacks on pseudorandom sequence generators. These
are brute force attacks, in which exhaustive search of the keyspace is conducted;

8attacks based on short period; attacks based on low linear complexity and statistical
attacks where the output sequence is sufficiently non-random. Assuming the fixed key
is known, for a brute force attack on the TOYOCRYPT-HR1 pseudorandom sequence
generator, there are 2128–1 stream keys to be tested. For an attack based on repetitionof the period, more than 2128–1 bits of keystream must be observed. Similarly, an
attack based on the linear complexity would require a known keystream segment of atleast 2125 bits, and very likely more, say 2128 bits. The statistical analysis described in
Section 4.3 identified no weakness which could be used in an attack. Thus the
TOYOCRYPT-HR1 keystream generator is resistant to these simple attacks, as the
keyspace is too large to permit exhaustive search, the period and linear complexity are
too high to be the basis of attacks and subsequences examined displayed white-noise
statistics.
5.2 Divide and Conquer Attacks
Divide and conquer attacks are commonly applied to keystream generators withmultiple component LFSRs. The attacks work on the components of the generator
separately and sequentially solve for the individual subkeys, generally the initial statesof the component LFSRs. This style of attack is not commonly used on nonlinear
filter generators, as these have a single LFSR. However, as noted in Section 3, theinputs to the function come from distinct sections of the LFSR: XL, XR, and x127. This
property of the Boolean function f may be exploited in an attack performed in a divideand conquer manner by considering these sections of the LFSR as separate
components. A similar approach was used to attack the ORYX cipher [WAGN 98].
The attack is conducted under the assumption that the fixed key (the LFSR feedback
function) is known. An outline of the procedure for a divide and conquer attack on
the TOYOCRYPT-HR1 keystream generator follows.
5.2.1 Attack procedure
The attack targets XR. For an assumed initial state of XR, the values of the terms of fof order greater than two are known, and one factor in each of the quadratic terms is
also known. Thus the keystream bit can be equated to a known linear combination ofx127 and some of the bits of XL. The identity of these bits is known from a
combination of the known quadratic terms in the filter function together with theassumed value of XR. A branching search process using a linear consistency test
[ZENG 90] can be used to determine whether the guessed initial state of XR was
correct.

The search process in the attack procedure is iterative. In each iteration, a value forx127 is guessed, a linear equation obtained, and a consistency check made. If theequation is consistent with previous linear equations, the guessed value of x127 and the
known feedback function are used to step the LFSR. The process is repeated, forminga path of successive consistent guesses. Note that each guess involves choosing one
of two possible values for x127, and so marks a branching point on the path. Note alsothat each time the LFSR is stepped, another bit of XL is obtained, reducing the numberof unknown variables in the subsequent linear equations.
If, in some iteration, a linear equation is obtained which is inconsistent with previous
equations, then assume that a guessed value of x127 is incorrect. Retrace the path ofguesses to the last branching point. Discard all linear equations obtained after thispoint. Change the guessed value, and begin to trace out another path. If all possible
paths result in inconsistencies, then the guessed initial state of XR was incorrect.

9

5.2.2 Attack algorithm
Input:The LFSR feedback polynomial; the observed segment of the pseudorandom
output sequence of length N, {z (t )}tN=−01 .
1. Set t=0. Initially, the pool of linear equations is empty.
2. Guess the contents of XR(t).
3. Guess the contents of x127(t). Note this is a branching point.
4. Substitute values from XR(t) and x127(t) into f to form a linear equation in terms of bitsof XL Equate to the known keystream bit z(t).
5. Check whether the new linear equation is consistent with all previous equations inpool. If consistent, add to pool. If inconsistent, go to Step 7.
6. Increment t. If t≤N, step the LFSR, using the known feedback function and theguessed value of x127(t) and go to Step 3. If t>N, go to Step 10.
7. Go back along the path of guesses for x127(t) to the last branching point. Change
the value of t to reflect this retracing of the path. Delete from the pool those linear
equations obtained after this point. Change the value of x127(t), and note that thisis no longer a branching point. Go to Step 4.
8. If all paths are searched without finding a path of consistent guesses equal to thelength of the known keystream, then the guessed contents of XR(0) were obviously
wrong. Go to Step 1.
9. Correct guess for XR forms part of LFSR initial state, use correct path of guessedvalues of x127 to recover the rest of the LFSR initial state.
10. Stop the procedure.
Output: Initial state of LFSR.
5.2.3 Implementation issues for the attack
The attack involves guessing the initial contents of XR, assuming the guess to becorrect, using this guess and the further guessed contents of x127 to form a pool oflinear equations, and testing whether each new linear equation is consistent with thosealready in the pool. If inconsistencies arise for a guessed value of x127, we conclude
that the guessed value was incorrect.
5.2.3.1 False alarms
A false alarm occurs when a wrong guess is not detected; that is, when the linear
equations are consistent, even though the initial guess for XR is incorrect. Note thatthe guessed value of XR and the first guessed value of x127 are used to form the firstlinear equation in the pool. As this is the first equation, no inconsistencies will be
detected at this point. However, as the iterative process continues, each guessed valueof x127 gives an extra linear equation, while removing one variable. That is, for the
first iteration, we have one linear equation in (potentially) 63 variables, for the second
iteration, we have two linear equations in 62 variables, and so on. If our path ofguessed values continues, by the 32nd iteration, there will be 32 linear equations in 32
variables. Of course, it is possible that inconsistencies will have been detected before
reaching this point. Certainly it is unlikely that an incorrect initial state will produce a
set of consistent linear equations for many iterations past this. The probability ofdetecting a wrong guess increases with each iteration.
5.2.3.2 Missing the event
Missing the event occurs when the correct initial state is not identified. In this case, if
the initial value of XR, and subsequent path of values for x127 are guessed correctly,
then all linear equations will be consistent. Thus, the correct initial state will always
be identified when tested. The probability of missing the event is zero.

10

5.2.3.3 Effect of length of known keystream
This is a known plaintext attack. To perform this attack, at least 65 bits of thepseudorandom output sequence must be known. One bit of keystream is required foreach guessed value of x127 and, after the initial guess of XR, a path of 65 consecutive
correct guesses for x127 is required to fill the LFSR. Additional bits can be used toresolve any possible ambiguity.
5.2.4 Attack complexity
This divide and conquer attack requires exhaustive search of the keyspace for XR, anda linear consistency test for each additional guess of x127. For the correct initial stateof XR, a series of 128 – 63 = 65 correct guesses of x127 is needed to complete therecovery of LFSR initial state. For a wrong guess of XR, inconsistencies in the pool oflinear equations should be detected before more than 32 iterations of the algorithm.
The complexity of the divide and conquer attack is therefore expected to be O(295). It
should be noted that this is only an approximation of the complexity. Due to themagnitude of this complexity no computer simulations to verify this value have been
performed. As noted above, there are many uncertainties in the attack model making it
difficult to determine the probability of a false alarm.

5.3 Correlation Attacks
Divide and conquer correlation attacks had their origin in a paper by Siegenthaler in1985 [SIEG 85], in which an attack on a nonlinear combiner generator was presented.
The attack is based on a model in which the keystream is viewed as a noisy version ofan underlying LFSR sequence, with the noise assumed to be additive and independentof the underlying sequence. The correlation between each of the inputs to a combining
function and the output could be exploited, to sequentially recover the initial states of
the component LFSRs. The attack required sequential exhaustive search of the initialstates of the component LFSRs, so would perform no better than exhaustive search if
applied to a nonlinear filter generator.
5.3.1 Fast Correlation Attacks
Fast correlation attacks are correlation attacks that outperform exhaustive search overthe initial states of the component LFSRs. Meier and Staffelbach proposed such an
attack on the nonlinear combiner generator in 1989 [MeSt 89]. The attack was
modified and applied to the nonlinear filter generator by Forre [FORR 90]. However,the complexity of this attack is still exponential in the length of the LFSR. If applied
to TOYOCRYPT-HR1, the complexity would be O(2128), which is infeasible.
Additionally, the success of the attack is dependent on the values of crosscorrelation
between the output sequence and the underlying LFSR; for crosscorrelation values
which are much less than 75%, as is the case for TOYOCRYPT-HR1, the attack is not
successful.
5.3.2 Linear Cryptanalysis
Linear cryptanalysis of stream ciphers was investigated using a linear sequential
circuit approximation by Golic [GOLI 94]. This attack was applied to nonlinear filter
generators in [SALM 97]. This attack is a more efficient fast correlation attack on the
nonlinear filter generator than that described in Section 5.3.1. The attack is based ona model in which the keystream is regarded as a noisy version of some linear
transform of the underlying LFSR sequence, with the probability of noise different
from one half [GOLI 96]. Hence the keystream sequence satisfies the same linear
recurrence as the LFSR sequence, again with probability different from one half. It
was shown that fast correlation attacks using iterative probabilistic error correction

11can be successfully applied to the nonlinear filter generator provided the level of noise
is not too close to 0.5, and if enough low weight parity checks can be obtained. The
probability of noise depends on the correlation coefficients of the filter function tolinear functions, and may be close to 0.5 if the filter function is close to a bent
function. The precomputational complexity of this attack is exponential in thenumber of inputs to the filter function, and the computational complexity is
proportional to the length of known keystream and the average number of paritychecks per bit used. For the filter function specified for TOYOCRYPT-HR1, thenumber of inputs to the filter function makes the attack infeasible, as theprecomputational complexity is O(2127). Additionally, the probability of noise (ascalculated in [EVAL HR1]) is given by p = 1 − 2 −64 . This noise value is so close to2

0.5 that unconditional fast correlation attacks will not be successful, regardless of theexistence or otherwise of the low-weight parity check polynomials these attacks
require.
5.3.3 Conditional Correlation Attacks
The attacks outlined above are unconditional correlation attacks. There exist otherconditional correlations in nonlinear filter generators that have been exploited inattacks. In [ANDE 95] an augmented filter function is considered, so that thecorrelation between blocks of successive input and output bits may be considered.
The attack requires precomputation with computational complexity exponential infour times the number of LFSR stages spanned by the inputs to the filter function, thatis O(2512), and so is infeasible to apply to TOYOCRYPT–HR1.
5.3.4 Inversion Attack
Another attack on nonlinear filter generators is the inversion attack [GOLI 96]. For
this attack, the nonlinear filter generator is viewed as a finite input memory combiner,
with one input and one output. The input memory space is the number of LFSR
stages spanned by the inputs to the filter function. Although not a correlation attack,the inversion attack essentially exploits the correlation to recover the unknown LFSR
sequence from an assumed input memory state. The computational complexity of theattack is exponential in the size of the input memory space. For TOYOCRYPT-HR1,
the input memory space is 128, and so the computational complexity is O(2128).
Therefore it is infeasible to apply the inversion attack to TOYOCRYPT–HR1.

5.4 Differential Cryptanalysis
Differential attacks are not generally applicable to stream ciphers. This is primarily
because the attacker has no ability to change internal data of a stream cipher operation.
Differential cryptanalysis was originally developed in relation to block ciphers [seeBS90] where it exploited the attackers ability to generate the encryptions/decryptionsof specially chosen pairs of text, under the same key. As the keystream generator of a
stream cipher is a deterministic finite state machine initialized by the key, the conceptof a differential attack is not meaningful in the context of stream ciphers, where every
message is supposed to be encrypted under a separate key.
5.5 Discussion
In this section of the report, the security of the TOYOCRYPT-HR1 pseudorandom
sequence generator has been examined with respect to common attacks on LFSRbased keystream generators. The TOYOCRYPT-HR1 design produces sequenceswith long period and large linear complexity, so that simple attacks based on theseproperties are infeasible. Also, the large number of inputs and high nonlinearity of

12the filter function f provides resistance to correlation attacks, including fast correlationand conditional correlation attacks, and to the inversion attack. These attacks were
examined under the assumption that the structure of the generator was known to thecryptanalyst, and that only the stream key was unknown. The attacks were no better
than a brute force attack: an exhaustive search of the stream key keyspace.
Of the possible attacks examined, only a divide and conquer attack outperformed thebrute force attack. In the case where the LFSR is known the expected complexity ofthe divide and conquer attack is O(295), a considerable reduction from the 2128
possible stream keys. In the case where the LFSR is not known this complexity should
be multiplied by 2120. Note that it may be possible to slightly reduce the complexityof this attack by using the repeated common differences in quadratic terms describedin Section 3.3. The amount of known plaintext required for this attack is extremely
small, only 65 bits.
The divide and conquer attack is possible only because of a feature of the filter
function f: all of the inputs to the higher order terms of the function come from XR, a
63-bit section of the LFSR. This attack can be made more difficult by a minor
adjustment to f. By taking the inputs to these higher order terms from stages spanningthe entire LFSR, the attack becomes infeasible. This minor adjustment will retain the
nonlinearity and balance of f provided that the constraints of the bent function
construction are satisfied, (see [ROTH 76]).

6 Implementation
As discussed above, the structure of TOYOCRYPT-HS1 is relatively standard for a
stream cipher. It uses standard components, namely a linear feedback shift register(LFSR) and a nonlinear Boolean function. The Galois representation of the LFSR is
used to enhance the efficiency of its implementation. This is important since the
LFSR will generally be the bottleneck in a stream cipher implementation (as it is in
this case).
6.1 Software
The TOYOCRYPT-HR1 specification [SPEC HR1] describes two software
implementations – a serial implementation and a parallel implementation. The
parallel implementation is significantly more efficient but implements a slightly
different mode of operation in that it generates a number of independent sequences inparallel rather than a single keystream sequence.

The evaluators agree with the analysis (in [SPEC HR1], Section 6.3) of the number ofoperations required in the computation of f (420 operations) and the number ofoperations required to update the LFSR (639 operations). The total number ofoperations given for the serial (650) and parallel (1060) implementations for thegeneration of one and Len bits (where Len is the word size of processor), respectively,
also appear to be correct.
The serial mode of TOYOCRYPT-HR1 was implemented (but not optimised) in C onan Intel Pentium processor by the review team and was found to run at speeds similar
to those reported in the Section 6.2 of [EVAL HR1]. The results of the serial
implementation in software show that the cipher will encrypt at only 9.56kbps on a
RISC processor at 20MHz. The evaluators agree with the developers comment that13

an implementation in assembly language would at most improve this speed by a factorof 2 to 3. The speed of the serial implementation in software appears to be far below
what is considered acceptable by today’s standards.
The parallel implementation generates up to Len independent keystream sequences inparallel. Each of the independent keystreams requires a separate initial state S andfeedback polynomial C. The parallel implementation would run approximately 1.6
times slower than the serial implementation but could compute up to Len keystream
sequences in parallel. On a 32-bit RISC processor running at 20MHz the parallel
implementation will encrypt 32 independent keystreams at an overall rate of 174kbps.
This speed would be unacceptable for high bandwidth applications.
The bitslice technique presented in the parallel implementation is not specific to the
TOYOCRYPT-HR1 algorithm and could be applied to any similar stream cipher
which is based on bit operations.
The size of the program code for the TOYOCRYPT-HR1 algorithm is extremely
small, making it suitable for implementation in devices with memory restrictions suchas smart cards.
6.2 Hardware
The TOYOCRYPT-HS1 self evaluation report [EVAL HS1] describes the results ofsimulations of hardware implementations on two different platforms. The first, an
FPGA implementation, gives encryption rates of between 81 Mbps (worst case, notoptimised for speed) and 418 Mbps (best case, optimised for speed) depending upon
the circuit size and for a range of voltages. The second platform tested was a gatearray processor with the reported data rates ranging from 223 Mbps (worst case) to790 Mbps (best case).

It was not feasible for the evaluators to verify these results. As expected, hardware
implementations of stream ciphers are much faster than software implementations.
The encryption rates given for hardware implementations of the TOYOCRYPT-HR1
algorithm are adequate for most applications. For applications requiring very highbandwidths (> 1Gbps) this algorithm would not be suitable.
6.3 Key Generation
The TOYOCRYPT-HR1 key includes a 128-bit value, C, which represents thecoefficients of a monic primitive polynomial of degree 128. The key setup times
quoted in the TOYOCRYPT-HR1 documentation (Section 6.2 of [EVAL HR1]) do
not include the non-negligible time required to compute this polynomial. Algorithm
4.6 of [SPEC HR1] describes an algorithm for generating C. This algorithm isidentical to previously known techniques [MOV 97] and requires first finding a monic
irreducible polynomial before testing that it is primitive. As the self evaluationsuggests (Section 3 of [EVAL HR1]), there are precisely:φ (2 m − 1)m

≈ 2119.9976

monic primitive polynomials of degree m=128. This agrees with the TOYOCRYPTHR1 designers’ evaluation that the effective key space is reduced from 256 bits to 248
bits (128 bits from S and 120 bits from C).
14

The proportion of random monic polynomials of degree m that are irreducible is 1/m.
And the complexity of the test for irreducibility is O((lg m)(lg 2)m2) [MOV 97]. For
m=128, the proportion of irreducible polynomials that are primitive is approximately:φ (2 m − 1)2m

≈ 0.4992

Thus, on average, one would expect to perform 64 irreducibility tests and two tests ofprimitiveness to find a suitable C. The high complexity of the tests for irreducibility
and primitiveness suggest that the time required to find a suitable polynomial may beconsiderable.
The evaluators performed a software implementation (not optimised for speed) of thealgorithm for generating random monic primitive polynomials of degree 128 which
took a number of minutes, on the average, to complete. It is expected that a highly
optimised implementation would take several seconds to generate a suitable
polynomial. This is an important consideration when re-keying of the algorithm isrequired (see Section 3.3 of this report).

7 Conclusion
TOYOCRYPT-HS1 is a stream cipher that uses TOYOCRYPT-HR1 to generate its
keystream. The security of TOYOCRYPT-HS1 depends directly on the security of
TOYOCRYPT-HR1 as a PRNG.
The TOYOCRYPT-HR1 pseudorandom number generator has been designed using a
LFSR together with a nonlinear Boolean function. The evaluators agree with thereport [EVAL HS1] that the standard keystream properties of large period, large linear
complexity and white-noise statistics are satisfied by this generator. However, theevaluators have identified three major areas of concern.
Firstly, we have outlined a divide and conquer attack which requires only a small
amount of known keystream and has complexity approximately O(2215) if the LFSR is
unknown and O(295) if known. In comparison an exhaustive key search hascomplexity of O(2248) and O(2128) respectively for these two cases. It is possible toprevent this attack by a minor adjustment to nonlinear filter function (see Section 5.4).
The second area of major concern relates to the speed of TOYOCRYPT-HR1 insoftware. The performance of TOYOCRYPT-HR1 in software is very slow. The
designers of algorithm have recognised this problem and have included a parallelmode of operation. The evaluators agree that this process will speed up operation.
However it should be noted that this will also require a much larger key size.
The third major area of concern relates to generation of primitive polynomials as partof the key rather than using a fixed LFSR. As we have noted this process is extremely
slow and may not be suitable for many cryptographic applications such as protocols
involving Diffie-Hellman key agreement. Due to this it may be necessary to use afixed LFSR in many applications, reducing the effective key size to 128 bits.
The second and third area of concern relate to implementation issues. There seems to
be no simple way to overcome these problems.
15

8 References[ANDE 95]
R. J. Anderson, Searching for the optimum correlation attack, In Fast Software
Encryption – Leuven’94, Volume 1008 of Lecture Notes in Computer Science, pages
137-143. Springer-Verlag, 1995.
[BS 90]E. Biham and A. Shamir, Differential cryptanalysis of DES-like cryptosystems, In
Advances in Cryptology – CRYPT0 ’90, Volume 537 of Lecture Notes in Computer
Science, pages 2-21. Springer-Verlag, 1991.
[EVAL HR1]
Self Evaluation Report TOYOCRYPT-HR1. Technical Document, October 2000.
[EVAL HS1]
Self Evaluation Report TOYOCRYPT-HS1. Technical Document, October 2000.
[FORR 90]
R. Forre, A fast correlation Attack on nonlinearly feedforward filtered shift-register
sequences. In Advances in Cryptology – EUROCRYPT ’89, Volume 434 of Lecture
Notes in Computer Science, pages 586-595. Springer-Verlag, 1990.
[GOLI 94]
J. Golic, Linear cryptanalysis of stream ciphers, In Fast Software Encryption –Leuven’94, Volume 1008 of Lecture Notes in Computer Science, pages 154-169.
Springer-Verlag, 1995.
[GOLI 96]
J. Dj. Golic, On the security of nonlinear filter generators, In Fast Software
Encryption – Cambridge’96, Volume 1039 of Lecture Notes in Computer Science,
pages 173-188. Springer-Verlag, 1996.
[MASS 69]
J. L. Massey, Shift Register Synthesis and B.C.H. decoding, IEEE Trans. Inform.
Theory, IT-15:122-127, January 1969.
[MeSt 89]
W. Meier and O. Staffelbach, Fast correlation attacks on certain stream ciphers,
Journal of Cryptology, 1(3):159-167, 1989.
[MOV 97]
A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied
Cryptography, CRC Press, 1997.
[ROTH 76]
O. S. Rothaus, On bent functions, Journal of Combinatorial Theory(A), Volume 20,
pages 300-305, 1976
[SALM 97]
16

M. Salmasizadeh, L. Simpson, J. Dj. Golic and E. Dawson, Fast correlation attacks
and multiple linear approximations, In Information Security and Privacy – ACISP’97,
Volume 1270 of Lecture Notes in Computer Science, pages 228-239. Springer-Verlag,
1997.
[SIEG 85]
T. Siegenthaler, Decrypting a class of stream ciphers using ciphertext only, IEEE
Trans. Comput., C-34:81-85, January 1985.
[SPEC HR1]
Cryptographic Techniques Specifications TOYOCRYPT-HR1. Technical Document,
October 2000.
[SPEC HS1]
Cryptographic Techniques Specifications TOYOCRYPT-HS1. Technical Document,
October 2000.
[WAGN 98]
D. Wagner, L. Simpson, E. Dawson, J. Kelsey, W. Millan and B. Schneier,
Cryptanalysis of ORYX, In Workshop on Selected Areas in Cryptography (SAC’98),
Volume 1556 of Lecture Notes in Computer Science, pages 296-305. SpringerVerlag, 1998.
[ZENG 90]
K. C. Zeng, C. H. Yang and T. R. N. Rao, On the linear consistency test (LCT) in
cryptanalysis with applications, In Advances in Cryptology – CRYPT0 ’89, Volume
434 of Lecture Notes in Computer Science, pages 164-174. Springer-Verlag, 1990.

17

9 Appendices18

Appendix A. Description of Statistical Tests
This appendix gives a mathematical description of the statistical tests used.

A.1 Mathematical Description of Stream Cipher Tests
This section contains a mathematical description of each of the tests. In each case an
example is given to illustrate a particular test. The first five tests examine thehypothesis that the bit stream was based on Bernoulli trials where the proportion ofones and zeros is 12 . The two complexity tests examine the knowledge that a small
subsection of the bit stream can be used to produce the remainder of the stream. If thisis possible the string would not be considered to be random, especially in relation toits use in a stream cipher.
The recommended size of a sample stream to test depends on the size of the average
message which is being encrypted using the keystream. i.e. If an average cryptogram
has size five million bits then one should use test samples of this length. It should be
noted that not all of the tests can be applied to a string of this length due tocomputational limitations. For example, in the linear complexity test one would needto examine a smaller substring of the keystream. It is recommended that strings oflength at least 100000 bits be used for testing.

A.1.1 Frequency Test
The frequency test checks that there is an equal proportion of ones and zeros in the bit
stream. For randomness the proportion of ones and zeros in the bit stream should beapproximately equal, since any substantial deviation from equality could result in a
successful cryptanalytic attack on the cipher. For example, assume that a cryptanalyst
attacking the stream cipher knows the type of plaintext being used, e.g. standard
English text coded in 8-bit ASCII, and the keystream has 43 of the bits zero. Under thisassumption the cryptanalyst knows the frequency distribution of the plaintext in termsof single bits, digraphs and trigraphs. With this knowledge the cryptanalyst could
recover a substantial amount of the plaintext, using ciphertext alone.
The number of ones in a random binary sequence follows a binomial distribution,with mean n2 and variance n4 . This may be approximated using a normal distribution.
The following notation is used:
n = total number of bits;n0 = number of zeros;
n1 = number of ones;
n1= proportion of ones in the sequence.
n
The aim of the frequency test is to determine how the proportion of ones, p̂ , in thesample stream of length n bits, fits into the hypothesised distribution where theproportion of ones, π = 0.5 and the variance, σ 2 = 41n . This is a two-tailed test [BHATpˆ =77]. The standardised normal test statistic is : z = 2 n ( pˆ − 0.5) . The significanceprobability value, p, of the normal distribution is calculated for this statistic. Thismeasures the probability of obtaining a number of ones equal to or further from themean of n2 than this sample gives for the hypothesised (where π = 0.5 and σ 2 = 41n ).
A small significance probability indicates a significant result (i.e., the stream isconsidered to be non-random). For large values of n ( n > 100000 ) a highly significant
19result (significance probability < 0.001) indicates a possible weakness in the cipher
and it is recommended that no further tests be carried out on this sample as theimbalance of ones and zeros may effect their results.
It should be noted that passing the frequency test does not mean the stream is notpatterned. The following highly patterned streams, where the number of ones andzeros are equal, will pass the frequency test:
11111111..........00000000.........
10101010101010.....................
Hence further testing is required to obtain knowledge of any patterns in the stream.
Example:Test stream:
10100010000101110001011000111010101010101010000001
Calculations and results:
n = 50σ 2 = 4×150
n1 = 21pˆ = 0.42

z = 50 (0.42 − 0.5) = −1.13137
p = 0.2579
Interpretation:
25.79 % of bit streams of length 50 will have a number of ones equal to or further
from the mean of 25, for the hypothesised distribution, than this sample. This sample
satisfies the frequency test.

A.1.2 Binary Derivative Test
The binary derivative is a new stream formed by the exclusive-or operation on
successive bits in the stream. Successive binary derivative streams may be obtained
from each new binary derivative, each one being of length one less than its
predecessor [CARR 88].
The proportion of ones in the i-th binary derivative gives the proportion of
overlapping (i+1)-tuples from the original stream in one of two known groupings ofthese (i+1)-tuples. This will be explained for i = 1 and i = 2 .
When i = 1 (first binary derivative) we are looking at the overlapping two-tuples: 00,
01, 10, 11 (in the original stream).
The proportion of ones in the first binary derivative, p̂(1) , gives the proportion of thetotal number of 01 and 10 patterns in the original stream.
p̂(1) > ½ means there is a larger proportion of the group of 01 and 10 two-tuples (inthe original stream).
p̂(1) < ½ means there is a larger proportion of the group of 00 and 11 two-tuples (inthe original stream).
A combination of the frequency test on the original stream and its first binary
derivative is equivalent to testing that there is an equal number of these four
overlapping two-tuples in the original stream. This replaces the well-known Serial
Test [DAWS 91].
When i = 2 (second binary derivative) we are looking at overlapping three-tuples:
000, 001, 010, 011, 100, 101, 110, 111 (in the original stream). The proportion ofones in the second binary derivative, p̂( 2) , gives the proportion of the total number of
001, 011, 100, 110 patterns in the original stream.

20

p̂( 2) > ½ means there is a larger proportion of the group of 001, 100, 110, and 011
three-tuples.
p̂( 2) < ½ means there is a larger proportion of the group of 000, 010, 101, and 111
three-tuples.
A combination of the frequency test on the original stream and a similar test on thefirst and second binary derivatives, tests that there is an equal number of the eightoverlapping three-tuples in the original stream, for practically all cases. If a cipher
gives a satisfactory result to these tests AND also the change point test, then it can beconsidered to generate equal numbers of the overlapping three-tuples.
Notation:
n1 (i ) = number of ones in the i - th derivativen1 (i )
= proportion of ones in the i - th derivativen−i
The frequency test is applied to each stream and the standardised normal variable isfound for the proportion of ones in each of the first two binary derivatives:
z (i ) = 2 n − i ( pˆ (i ) − 0.5) , for i = 1,2 .
The significance probability value, pi , of the normal distribution is calculated foreach statistic. A small significance probability indicates a significant result. For largen ( n > 100000 ) a highly significant result (significance probability < 0.001) indicatesa possible weakness in the cipher.
pˆ (i ) =Example:Test stream:
10100010000101110001011000111010101010101010000001
Calculations and results:
D1 : 1110011000111001001110100100111111111111111000001
D2 : 001010100100101101001110110100000000000000100001

Frequency test on first binary derivative (D1) :n1 (1) = 30
n −1
2 = 24.5pˆ (1) = nn1 −(11) = 5030−1 = 0.61224
z (1) = 2 49 (0.61224 − 0.5) = 1.57143
p1 = 0.1161
Interpretation:
11.61 % of bit streams of length 49 will have a number of ones equal to or further
from the mean of 24.5, for the hypothesised distribution, than this sample. This
sample satisfies the frequency test on the first binary derivative.
Since the frequency test is satisfied for the original stream and the first binary
derivative then the cipher can be regarded as producing an equal number ofoverlapping two-tuples.
Frequency test on second binary derivative (D2) :n1 ( 2) = 16n −2
2 = 24pˆ ( 2) = nn1 −( 22) = 5016−2 = 0.333
z ( 2) = 2 48 (0.333 − 0.5) = −2.3094
p2 = 0.0209
21

Interpretation:
2.09 % of bit streams of length 48 will have a number of ones equal to or further
from the mean of 24, for the hypothesised distribution, than this sample. This
sample satisfies the frequency test on the second binary derivative.
Even though the frequency tests on the original stream and the first and second binary
derivatives were all satisfied, the cipher will still have to satisfy the change point test
before regarding it as producing an equal number of overlapping three-tuples.

A.1.3 Change Point Test
At each bit position, t, in the stream the proportion of ones to that point is compared tothe proportion of ones in the remaining stream.
The difference or change in these proportions is compared for all positions in the bit
stream. The bit where the maximum change occurs is called the change point. The
test applied determines whether this change is significant for a binomial distribution
where the proportion of ones in the stream is expected to be 0.5.
This test is very useful for detecting patterned streams which have passed thefrequency test on the stream and the first two binary derivatives. Even if π = 12 and thestream has passed the frequency test it could be, for n = 106, that π = 14 for the first
500000 bits and π = 43 for the second 500000 bits. This is not considered to be a good
pseudorandom sequence to be used as a keystream, and the change point test would
detect such cases.
This test is also useful for checking that there is an equal number of overlapping
three-tuples for streams which have passed the frequency test on the original stream
and also on the first two binary derivatives.
The hypothesis to be tested is that there is no change in the proportion of ones
throughout the whole stream. The statistic [PETT 79] used is U[ t ] = n × S[ t ] − t × S[ n ]wheren = total bits in stream
S [n ] = total ones in stream
S [t ] = number of ones to bit t
The maximum absolute value of this statistic is found:
Max = Maximum of ABS(U [t ]), for t = 1K n
The significance probability, p, associated with this statistic is approximated by:−

2 Max 2nS [ n ]( n − S [ n ])p=e.
For small values of p the actual significance probability is smaller than that calculated.
The smaller the value of p then the more significant the result. For large streams ahighly significant result, p < 0.001, indicates a possible weakness in the algorithm.
Example:Test stream:s = 10100010000101110001011000111010101010101010000001
Calculations and results:
n = 50S [n ] = 21

t = 43S [t ] = 20
Max = 50 × 20 − 43 × 21 = 97

22

−

p=e
Interpretation:

2×97 250×21( 50− 21)= 0.5390

The actual significance probability of the change in the proportion of ones is lessthan 53.9%. This result indicates there is no significant change in the proportion ofones in the bit stream. This sample satisfies the change point test.

A.1.4 Subblock Test
The stream is divided into S non-overlapping subblocks, each of length b. Any
fractional subblocks remaining are ignored. For a stream of length n, the number ofsubblocks is the integral part of  nb  , i.e. S =  nb  .
For a subblock size of b ≤ 16 a test of uniformity is applied – i.e., there should be anequal number of each b bit pattern. The test compares the observed number of each b
bit pattern with S 2 b .
2 b 2 −1 2
∑ f i −S [BEKE 82], where fi is the frequency of
S i =0subblock pattern whose equivalent decimal value is i. This statistic is compared witha chi-square distribution with degrees of freedom equal to 2 b − 1 . For values of b > 6
the normal distribution may be used to approximate the chi-square distribution.
Limitations: The minimum length required for the stream to test for randomness
using b-bit subblocks is 5b × 2 b bits.
For a subblock size of b > 16 the repetition test is applied. The repetition test
measures the number of repeated patterns in a sample of S subblocks, each containingb bits. Given the binary stream is divided into S b-bit subblocks then, for a random
stream, each of the N = 2 b possible binary b-bit patterns is equally likely to occur.
As the block length increases and N → ∞ , with a sample of size S → ∞ whereS
N → 0 , then the distribution of the number of subblock repetitions in the sampleb

The test statistic used is χ 2 =−Sapproaches a Poisson distribution with a mean of λ = S − N (1 − e N ) . WhenS = 8 N the mean converges to 32, for large values of b (say b > 16). The Poisson
distribution is well approximated by the normal distribution for λ = 32 .
The test requires a count of the number of subblock repetitions, r. (Note that if aparticular pattern occurs three times, then this would add two to the number ofrepetitions).
The number of b-bit subblocks required for the test is S = 8 N , and gives λ ≈ 32 .
The procedure is to sort the subblocks and then determine the number of repetitions, r.
r−λ
The test statistic is z =(standard normal statistic for a Poisson distribution with
λa mean equal to λ ), and is compared with the standard normal distribution. A twotailed test applies since both too few or too many repetitions may indicate nonrandomness of the stream.
The required stream length to apply the repetition test using b-bit subblocks isb+3

b × 2 2 bits. This is considerably less than the length of stream required to apply the
uniformity test for subblocks of the same size. Since the stream lengths required arevery large, no sample stream will be shown. Instead, the following data will be used
to illustrate a test calculation for the uniformity test:23

b = 8 (hence the uniformity test is applied)n = 100000
100000 = 12500
S= 8 
Number of 8 bit patterns = 2 8 = 256
Assume f 0 = 45, f1 = 50, K , f 255 = 44, to give :28 255 2∑ f i − 12500 = 260 (say)12500 i =0
Degrees of freedom = 255

χ2 =z = 2 × 260 − 2 × 255 − 1 = 0.24248
p = 0.4042
Interpretation:
40.42% of all possible streams of length 100000 will have a distribution of 8-bit
subblocks less uniform than this sample shows. This sample satisfies the
subblock test for subblocks of length 8.
The following data is used to illustrate a test calculation for the repetitions tests:
b = 18 (hence the repetition test is applied)n = 100000
N = 218 = 262144
18

S = 22+3= 4096

Stream length tested = 4096 × 18 = 36864 bitsr = 38 (say)38 − 32= 1.06066
32
p = 0.1444

z=Interpretation:
14.44% of all possible streams of length 36864 will have a 18-bit subblock
repetition count further from the mean (32) than this sample shows. This
sample satisfies the subblock test for subblocks of length 18.

A.1.5 Runs Test
The runs distribution test compares the distribution of the number of runs of ones
(blocks) and zeros (gaps) with that expected under randomness. For a random binary
stream where Pr(1) = Pr( 0) = 12 there should be an equal number of number of blocks
and gaps of the same length. Based on Golomb's postulates, the expected number ofruns of length i for a random binary stream should be 21i of the number of runs, and foreach length there should be an equal number of runs of ones and zeros, i.e.
sE( r0i ) = E( r1i ) = Run, where Runs indicates the number of runs in the binary stream.
2 i +1
The hypothesis to be tested is that the distribution of runs in the stream fits a binomial
population for which Pr(1) = Pr( 0) = 12 . The test applied is adapted from [MOOD40].

24

The long runs are added together to form new variables s0k and s1k corresponding ton0

the number of gaps and blocks of length k or more, where s 0 k = ∑ r0i and n0 is thei=knumber of zeros in the stream.
By adding the long runs together a certain amount of information will be lost. In orderto minimise the amount of information lost, it is recommended here thatk = log 2 n5+1 − 1 .
For a stream of length n = 106 this would give a maximum value of k = 16, and hence
the number of gaps of length 16 or more would be added together to give s0,16 and thenumber of blocks of length 16 or more would be added together to give s1,16.
Explanation of terms:
n = number of bits in stream
n1 = number of ones in the bit stream
r0i = number of runs of 0 of length i
s 0i = number of runs of 0 of length i for i < k

s 0 k = number of runs of 0 for lengths ≥ k
r1i = number of runs of 1 of length i
s1i = number of runs of 1 of length i for i < ks1k = number of runs of 1 for lengths ≥ k
The variables:r − n ( 12 ) 2+i
u i = 1ii = 1,..., k − 1n
s − n( 12 ) k +1
u k = x k = 1knr0i − n ( 12 ) 2+i
u k +i = y i =i = 1,..., k − 1nn −1n
u 2k = z = 1 2nare asymptotically normally distributed with zero means and variances andcovariances:σ( x i , x i ) = σ( y i , y i ) = ( 12 ) i +2 − ( 2i − 1)( 12 ) 2 i +4σ( x i , x j ) = σ( y i , y j ) = (1 − i − j)( 12 ) i + j+ 4σ( x i , x k ) = −(i + k )( 12 ) i + k +3σ( x k , x k ) = ( 12 ) k +1 − ( 2k + 1)( 12 ) 2 k + 2
σ( x i , y j ) = (5 − i − j)( 12 ) i + j+ 4σ( x k , y j ) = ( 4 − k − j)( 12 ) k + j+3σ( x i , z ) = σ( y i , z ) = (i − 2)( 12 ) i+3σ( x k , z ) = ( k − 5)( 12 ) k + 2
σ( z, z ) = σ zz = 14
Test procedure:
1.
Determine k.
2.
Take a sample stream of n bits from a stream cipher. Determine the number ofruns of each length to give s1i and s 0i for i = 1,..., k .
25

3.
4.

Calculate u j for j = 1,...,2k using above formulae.

[ ]Determine S = [σ ij ] which is a 2k × 2k matrix. Calculate S −1 = σ ij = [σ ij ] .
−1This will require obtaining the inverse of a matrix of up
to 32 (1024) elements for n ≤ 106 bits. Calculate
Q = uT S −1u = ∑ σ ij u i u j which follows a χ 22 k distribution (chi-squared
2

distribution with 2k degrees of freedom). There are ( 2k ) 2 terms in this sum.
2k

Q = ∑ σ ii u i + 2∑ σ ij u i u j
2

i =1

i< j

The significance probability value, p, of the chi-squared distribution is calculated forthis statistic. A small value of p indicates a significant result. For large streams ahighly significant result, p < 0.1% , indicates a possible weakness in the algorithm.
The runs test can be used to support results from the previous tests. Failure of the runs
test indicates that there is a bad distribution of run lengths or that there are no runs
recorded above a certain length that are expected to occur for streams of the sample
size. The zero frequencies recorded will result in a higher chi-squared statistic thus
giving a smaller significance probability.
Example:Test stream:
10100010000101110001011000111010101010101010000001
Calculations and results:
n = 50
total runs = 31
n1 = 21k = log 2 n5+1 − 1 = log 2 515 − 1 = 2
s 01 = 10, s 02 = 5, s11 = 13, s12 = 3
13 − 50( 12 ) 3

u1 = x 1 =u2 = x2 =u 3 = y1 =u4 = z =50
3 − 50( 12 ) 3
50
10 − 50( 12 ) 350
121 − 2 (50)

= 0.9545941546018= −0.4596194077713= 0.5303300858899= −0.5656854249492
50σ( u1 , u1 ) = σ( u 3 , u 3 ) = ( 12 ) 3 − ( 2 − 1)( 12 ) 6 = 0.109375
σ( u1 , u 2 ) = −3( 12 ) 6 = −0.046875σ( u 2 , u 2 ) = ( 12 ) 3 − 5( 12 ) 6 = 0.046875σ( u1 , u 3 ) = 3( 12 ) 6 = 0.046875σ( u 2 , u 3 ) = 1( 12 ) 6 = 0.015625σ( u1 , u 4 ) = σ( u 3 , u 4 ) = −1( 12 ) 4 = −0.0625
σ( u 2 , u 4 ) = −3( 12 ) 4 = −0.1875σ( u 4 , u 4 ) = σ 44 = 0.25
Elements of the inverse matrix, S-1 :26

σ11 = 6 23 , σ12 = −5 13 , σ13 = −4, σ14 = −3 13 , σ 21 = −5 13 , σ 22 = −5 13 , σ 23 = 0, σ 24 = −5 13 ,σ 31 = −4, σ 32 = 0, σ 33 = 12, σ 34 = 2, σ 41 = −3 13 , σ 42 = −5 13 , σ 43 = 2, σ 44 = − 13 .

Q = 8.4733.. follows a χ 24 distribution.
p = 0.076
Interpretation:
7.6% of bit streams of length 50 will have a distribution of run lengths further fromthe expected distribution than this sample gives. This sample satisfies the runs
distribution test.

A.1.6 Sequence Complexity Test
The sequence complexity, c(s), is the number of different substrings encountered as
the stream, s, is viewed from beginning to end [LEMP 76].
Example (n = 16) :s=1001111011000010
Marking in different substrings :s = 1/0/0 1/1 1 1 0/1 1 0 0/0 0 1 0/
Here the sequence complexity c(s) = 6
A threshold value of sequence complexity is used to measure the randomness of asequence. This threshold value is logn2 n where n is the total bits in the stream. A stream
with a sequence complexity measure below this threshold value would be considered
to be patterned, ie not random. For the example given, the threshold value = 164 = 4 .
Hence the stream is not considered patterned.
An expected value for the sequence complexity of a random stream of the same lengthis calculated using the following algorithm [GUST 96]:i = 2;
c = 2;
while (i < n ) do
begin
i −1)
i = i + log(
log( 2 )  + 2;

c = c + 1;
end;
if ( n < i ) then c = c − 1;
It is expected that a good pseudo-random number sequence has a sequence
complexity which is close to this value. It should be noted that the expected value ofsequence complexity is always greater than the threshold value. However, a bit stream
will only be considered to not satisfy the sequence complexity test if the value of c(s)is less than the threshold value.
The sequence complexity is used to replace the autocorrelation test which iscommonly used to determine any periodicity in the pseudorandom number generator.
Periodicity would greatly reduce the number of "different" substrings encountered.
Hence c(s) would be low and fall below the threshold value. [DAWS 91]

ExampleTest stream:
10100010000101110001011000111010101010101010000001
Calculations and results:27n = 50c(s) = 10
Threshold value = 8.859191
Expected value = 13
Interpretation:
This sample stream is considered random based on the sequence complexity test.

A.1.7 Linear Complexity Test
A.1.7.1 Linear Complexity
The linear complexity test checks for the minimum amount of knowledge (bits)
needed to reconstruct the whole stream. Every finite stream, s, can be produced by alinear feedback shift register (LFSR). The length of the shortest LFSR which willproduce the stream is said to be the linear complexity of the stream, which will bedenoted by L(s).
If the value of L(s) is L then 2L consecutive terms can be used to reconstruct thewhole sequence using the Berlekamp Massey algorithm. [MASS 69] Hence, in order
to avoid stream reconstruction, the value of L should be large.
Example:01011001010100100111100000110111001100011101011111101101
This shortest recurrence relation which will create this sequence is:u(t + 6) = u(t + 5) ⊕ u(t + 4) ⊕ u(t + 1) ⊕ u(t )where ⊕ is addition mod 2, and the first bit is u(0).
For example:
u (6) = u (5) ⊕ u ( 4) ⊕ u (1) ⊕ u (0).
If t = 0 then0 = 0 ⊕1⊕1⊕ 0
u (7) = u(6) ⊕ u (5) ⊕ u( 2) ⊕ u(1).
If t = 1 then1 = 0 ⊕ 0 ⊕ 0 ⊕1
u (8) = u (7) ⊕ u (6) ⊕ u (3) ⊕ u ( 2).
If t = 2 then0 = 1⊕ 0 ⊕1⊕ 0This means that the linear complexity, L(s), of this sequence is six. If any twelve
consecutive bits are known then the whole sequence can be reconstructed. [MASS 69]
It should be noted that some keystreams can pass all the previous tests yet possess avery small linear complexity. An example of this is an m-sequence (see [RUEP 84]).
An m-sequence has a period of length 2 L − 1 and a linear complexity of L. An msequence has the best possible distribution of zeros and ones for a sequence of
period 2 L − 1 . In this fashion an m-sequence appears to be statistically random interms of tests A.1.1 to A.1.6. In fact m-sequences are commonly used as white noise
generators. However, in terms of their use in a stream cipher an m-sequence offers
very low security. Knowledge of only 2L consecutive bits of the keystream is needed
to derive the defining LFSR and hence determine the whole keystream.
For large n, L(s) is approximately normally distributed with µ = n2 , σ 2 = 86
81 [RUEP84], [KREY 81]. Using the standardised normal statistic z =8186( L( s ) − n2 ) thesignificance probability value, p, of the normal distribution is calculated.
Since only low values of L(s) signify a possible weakness to the cipher, only a
one-tailed test (lower tail) need apply. A small value of p indicates a significant result.
For large streams a highly significant result ( p < 0.1% ) indicates a possible weakness
in the algorithm.

28

The linear complexity test by itself can classify as random, streams which may behighly patterned, or contain large substrings which are highly patterned. Some of theprevious test results should support this. e.g. a stream of n2 − 1 zeros followed by aone, and then followed by a repetition of these n2 terms, has a linear complexity of n2 .
This stream would be classified as being random using the linear complexity test.
Clearly, such a stream is highly patterned and would not satisfy the previous tests.
However, it is possible to construct a stream of length n which would pass all theprevious statistical tests, and have a linear complexity of approximately n2 yet would
contain a large highly patterned substring. Hence the following linear complexity
profile tests are carried out.
A.1.7.2 Linear Complexity Profile
Since some highly patterned streams can give a linear complexity measure close to n2 asecond test measures the change in the linear complexity profile of the stream as each
bit is added. Let s(i) be the substring formed by taking the first i bits of s. If L(s(i))
for i = 1,...,n denotes the linear complexity of s(i) then the values of s(i) are defined
to be the linear complexity profile of s and should follow approximately the 2i line

[MASS 69]. A failure in this test would highlight any large deviations from the 2i line,
which would appear for strings passing the linear complexity test and containing anylarge highly patterned substrings. A change in linear complexity signifies a jump.
There are two tests relating to the Linear Complexity Profile:
A.1.7.3 Linear Complexity Profile – Number of Jumps
Let the total number of jumps be F. For large n, F is approximately normally
distributed with µ = n4 and σ 2 = n8 [CART]. The standardised statistic for the numberof jumps is z =8n( F − n4 ) . The significance probability, p, for this standardised

statistic is calculated. Since a small number of jumps would indicate a sequence
within which patterns may exist, a one-tailed test (lower tail) is applied. A smallvalue of p ( p < 0.1% ) indicates that the number of jumps in linear complexity is low,
and there may be patterns in the stream which would indicate a possible weakness inthe cipher.
A.1.7.4 Linear Complexity Profile – Jump Size
If a stream passes the test on the number of jumps in linear complexity, then the
distribution of jump heights may be investigated. The height of a jump is thedifference in linear complexity when a change occurs. Let the total number of jumps
in linear complexity be F, where f i is the number of jumps of height i. For a random
string based on Bernoulli trials where the probability of a one on each trial is one half,
the probability, p i that a given jump has height i is given by p i = ( 12 ) i . Hence theexpected number of jumps of height i, e i , is given by e i = p i × F .

(f i − e i ) 2[CART 87]. The maximum valueei
i =1
of i = m is determined from the condition for the chi-squared test, that e i > 5 . The
number of degrees of freedom, m − 1 , is determined from the sample taken.
The significance probability value, p, of the chi-squared distribution is calculated forthis statistic. A small significance probability indicates a significant result – i.e., themThe chi-squared statistic used is χ 2 = ∑29

stream is considered to be non-random. For large samples a highly significant
result, p < 0.1% , indicates a possible weakness in the algorithm.

ExampleTest stream:
10100010000101110001011000111010101010101010000001
Calculations and results:
Linear Complexity Testn = 50µ = n2σ 2 = 8681
L( s ) = 25
z=

81
86

( 25 − 502 ) = 0

p = 0 .5
Interpretation:

50 % of bit streams of length 50 will have a linear complexity less than this sample.
This sample satisfies the linear complexity test.
Hence 2 × L( s ) = 50 bits (the whole stream) is needed to reconstruct the stream using
the Berlekamp-Massey algorithm.
Linear Complexity Profile - Number of jumps
F = 15z=

850(15 − 504 ) = 1

p = 0.8413
Interpretation:
84.13% of streams of length 50 will have a number of jumps in linear
complexity less than this sample. This sample satisfies the test on the numberof jumps in linear complexity.
Linear Complexity Profile – Jumps size
f1 = 11, f 2 = 2, f 3 = 0, f 4 = 1, f 5 = 1.
e1 = 7.5 Since ei < 5 for i > 2 , then these values are combined to give e2+ = 7.5 .
The corresponding values of f i are combined to give f 2+ = 4 .

χ 2 = (11−77.5.5) + ( 4−77.5.5) = 3.27
2

2

Degrees of freedom = m − 1 = 2 − 1 = 1
p = 0.0707
Interpretation:

Approximately 7.07% of bit streams of length 50 will have a sump size distribution
further from the expected distribution than this sample gives. The sample satisfies
the test on the distribution of the linear complexity jump size.

A.2 Bibliography30

[BEKE 82][BHAT 77]
[CARR 88]

[CART 87]

[DAWS 91]
[DAWS 98]

[DIFF 79]

[FOLK 84]
[GUST 96]

[KOLC 66]

[KREY 81]
[LEMP 76]
[MASS 69]

[MAUR 92]
[MARS 84]

[MASS 69]
[MOOD 40]
[PETT 79]
[RUEP1 84][RUEP2 84][STEP 86]

H. Beker and F.Piper, Cipher Systems: The Protection ofCommunications, Northwood Books, London, 1982.
G. Bhattacharyya and R. Johnson, Statistical Concepts and Methods,
John Wiley & Sons, 1977.
J.M. Carroll and L.E. Robbins, “Using binary derivatives to test an
enhancement of DES”, Cryptologia, Vo1 12 number 4, 1988, pp 193208.
G. Carter, “A statistical test for randomness based on the linear
complexity profile of a binary sequence”, Technical Report for Racal
Comsec Ltd., 1987.
E.P. Dawson, Design and Cryptanalysis of Symmetric Ciphers, PhD
Thesis, Queensland University of Technology, 1991.
E.P. Dawson and H.M. Gustafson, “A Method for measuring Entropyof Symmetric Cipher Key Generators”, Computers and Security, Vol.
17 No. 2, pp 177 - 184, 1998.
W. Diffie and M.E. Hellman, “Privacy and Authentication: An
Introduction to Cryptography”, Proceedings of the IEEE, Vol. 67, No.
3, March 1979, pp 397-427.
L.J. Folks, “Combination of Independent Tests”, Handbook of
Statistics, Vol. 4, Elsevier Science Publishers, 1984, pp 113-121.
H.M. Gustafson, Statistical Analysis of Symmetric Ciphers, PhD
Thesis, Queensland University of Technology, Brisbane Australia,
1996.
V.F. Kolchin, “The Speed of Convergence to Limit Distributions in
The Classical Ball Problem”, Theory of Probability and its
Applications, 11, 1966, 128-140.
E. Kreysig, Introductory Mathematical Statistics, John Wiley andSons, 1981.
A. Lempel and J. Ziv, “On the complexity of finite sequences”, IEEE
Trans. on Information Theory, Vol.IT-22, Jan.1976,pp 75-81.
J.L. Massey, “Shift register sequences and BCH decoding”, IEEE
Transactions on Information Theory, Vol. IT-15, Jan. 1969, pp 122127.
U.M. Maurer, “A Universal Statistical Test for Random Bit
Generators”, Journal of Cryptology, 1992, 5, pp 89-105.
G. Marsaglia, “A Current View of random Number Generators”,
Proceedings of the Sixteenth Symposium on the Interface, Computer
Science and Statistics, Editor L. Billard, Elsevier Science Publishers,
1984. pp3 - 10.
J.L. Massey, “Shift Register Sequences and BGH Decoding”, IEEE
Trans. on Information Theory, Vol. IT-15, Jan. 1969, pp 122-127.
A.M. Mood, “The distribution theory of runs”, Ann. Math. Statist.,
Vol 11, 1940, pp 367-392.
A.N. Pettitt, “A non-parametric approach to the change - point
problem”, Appl. Statist., Vol. 28 No. 2, 1979, pp 126-135.
R.A. Rueppel, New Approaches to Stream Ciphers, PhD Thesis,
Swiss Federal Institute of Technology, 1984.
R.A. Reuppel, “Analysis and Design of Stream Ciphers”, SpringerVerlag, 1986.
M.A. Stephens and R.B. D'Agostino, “Tests based on EDF Statistics”,
Goodness of Fit Techniques, in Statistics, Textbooks andMonographs; Vol. 68, Marcel Dekker Inc., 1986, pp 97-193.
31

[WEBS 86]

A.E. Webster and S.E. Tavares, “On the Design of S-Boxes”,
Advances in Cryptology: Crypto' 85, Springer-Verlag, 1986, pp.
523-530.

32

Appendix B.
Algebraic Normal form of TOYOCRYPT-HR1 Boolean function f.

f(x0, x1,…,x125, x127) = x127
⊕ x24x63 ⊕ x41x64 ⊕ x27x65 ⊕ x32x66 ⊕ x35x67 ⊕ x50x68⊕ x8x69 ⊕ x18x70 ⊕ x1x71 ⊕ x36x72 ⊕ x53x73 ⊕ x26x74⊕ x3x75 ⊕ x7x76 ⊕ x11x77 ⊕ x6x78 ⊕ x62x79 ⊕ x37x80⊕ x31x81 ⊕ x12x82 ⊕ x9x83 ⊕ x34x84 ⊕ x51x85 ⊕ x61x86⊕ x25x87 ⊕ x23x88 ⊕ x45x89 ⊕ x14x90 ⊕ x0x91 ⊕ x20x92⊕ x46x93 ⊕ x38x94 ⊕ x40x95 ⊕ x13x96 ⊕ x28x97 ⊕ x2x98⊕ x49x99 ⊕ x54x100 ⊕ x5x101 ⊕ x60x102 ⊕ x47x103 ⊕ x4x104⊕ x16x105 ⊕ x52x106 ⊕ x59x107 ⊕ x55x108 ⊕ x10x109 ⊕ x57x110⊕ x22x111 ⊕ x15x112 ⊕ x56x113 ⊕ x48x114 ⊕ x29x115 ⊕ x44x116⊕ x39x117 ⊕ x58x118 ⊕ x17x119 ⊕ x43x120 ⊕ x19x121 ⊕ x21x122⊕ x42x123 ⊕ x33x124 ⊕ x30x125⊕ x10x23x32x42⊕ x1x2x9x12x18x20x23x25x26x28x33x38x41x42x51x53x59⊕x0x1 … x62

33

Appendix C.
Sorted input differences for quadratic terms – TOYOCRYPT-HR1

Index for first factor
62
50
53
41
61
35
32
51
36
27
24
60
37
45
54
46
26
59
31
34
49
18
55
57
52
40
38
47
56
58
8
25
23
11
48
7
28
1
12
3
6
20
44
9
14

Index for second factor
79
68
73
64
86
67
66
85
72
65
63
102
80
89
100
93
74
107
81
84
99
70
108
110
106
95
94
103
113
118
69
87
88
77
114
76
97
71
82
75
78
92
116
83
90

Difference
17
18
20
23
25
32
34
34
36
38
39
42
43
44
46
47
48
48
50
50
50
52
53
53
54
55
56
56
57
60
61
62
65
66
66
69
69
70
70
72
72
72
72
74
76
34

43
39
42
13
29
16
22
0
33
30
2
5
15
10
4
21
17
19

120
117
123
96
115
105
111
91
124
125
98
101
112
109
104
122
119
121

77
78
81
83
86
89
89
91
91
95
96
96
97
99
100
101
102
102

Bold type has been used for table entries to emphasise multiple quadratic terms with acommon difference.

35Appendix D.
Results of Linear Complexity Tests on TOYOCRYPT-HR1

Length of output stream = 1,000,000 bits.
Number of streams = 10
Test
Linear Complexity
LC p-value
LC - Jumps
LC - Jump Size

Key1
4999
98
.0261
.2623
.7099

Key2
4999
98
.0261
.5113
.6622

Key3
5000
02
.9739
.2965
.3050

Key4
5000
01
.8341
.1926
.6306

Key5
5000
00
.5000
.4050
.8919

Key6
5000
00
.5000
.3429
.6059

Key7
4999
99
.1659
.0812
.1111

Key8
5000
00
.5000
.5214
.7357

Key9
5000
00
.5000
.2415
.0931

36

Keya
5000
00
.5000
.8261
.0269

Appendix E.
Results of CRYPT-X Tests on TOYOCRYPT-HR1
Length of output stream = 10,000,000 bits.
Length of output stream = 1,000,000 bits. (Sequence Complexity Test)
Number of streams = 10
Test
Frequency
Binary Derivative (1)Binary Derivative (2)Change Point
Subblock b = 2
Subblock b = 3
Subblock b = 4
Subblock b = 5
Subblock b = 6
Subblock b = 7
Subblock b = 8
Subblock b = 9
Subblock b = 10
Subblock b = 11
Subblock b = 12
Subblock b = 13
Subblock b = 14
Subblock b = 15
Subblock b = 16
Subblock b = 17
Subblock b = 18
Subblock b = 19
Subblock b = 20
Subblock b = 21
Subblock b = 22
Subblock b = 23
Subblock b = 24
Subblock b = 25
Subblock b = 26
Subblock b = 27
Subblock b = 28
Subblock b = 29
Subblock b = 30
Runs Distribution
Longest Run Length
Sequence Complexity

Key1
.6561
.2094
.1034
.5793
.3439
.0185
.6667
.7335
.0859
.5260
.4062
.6126
.6075
.4800
.0358
.2134
.6850
.4584
.0252
.0047
.4795
.8597
.3768
.5959
1.000
.2888
1.000
.4795
.1116
.4795
.4795
.4795
.1116
.8082
25
5079
5

Key2
.6557
.2092
.1033
.5994
.9706
.0604
.2959
.4502
.0020
.1514
.4001
.1129
.0945
.2656
.3106
.8827
.6993
.6548
.0083
.2159
.4795
.5959
.4795
.4795
.1573
.1116
.3768
.1116
.7237
.8597
.4795
.5959
.0771
.8084
25
5079
5

Key3
.6557
.2090
.1033
.5790
.3434
.0826
.1012
.4864
.0412
.3687
.1335
.0659
.2173
.1368
.2596
.6305
.2170
.6577
.0007
.5959
.4795
1.000
.5959
.2888
.4795
.1116
.0518
.3768
.0771
.1573
.1573
.8597
.3768
.8083
25
5079
4

Key4
.6557
.2090
.1033
.5787
.9706
.0185
.2760
.1967
.0978
.9734
.1879
.0882
.2728
.4871
.0389
.1608
.7144
.2402
.1570
.7237
.8597
.3768
.3768
.4795
.7237
.1573
.3768
.2888
.5959
.7237
.8597
.2888
.7237
.8083
25
5079
5

Sequence Complexity: Threshold value = 50,441

Key5
.6552
.2090
.1033
.5787
.3429
.0603
.6656
.4876
.5439
.4454
.1365
.3296
.3865
.3414
.7884
.3686
.8451
.0536
.7279
.4795
.2888
.3768
.4795
.2159
.7237
.3768
.8597
.1573
.8597
.8597
.4795
.0339
1.000
.8084
25
5079
4

Key6
.6557
.2088
.1034
.5787
.9705
.0826
.2955
.7332
.7844
.4265
.0177
.5648
.5614
.2927
.0069
.9117
.9438
.0607
.5014
.4795
.5959
.0518
.8597
.2888
1.000
.4795
.8597
.5959
.5959
.5959
.5959
.0771
.2888
.8086
25
5079
5

Key7
.1705
.1675
.1970
.0833
.3290
.0300
.7999
.3051
.4027
.8331
.1423
.7061
.3586
.4013
.6168
.7010
.7418
.0451
.1228
.1116
.8597
.0518
.8597
.2159
1.000
.2888
.2888
.2159
.0027
1.000
.4795
.3768
.8597
.6265
21
5082
9

Key8
.6833
.8527
.9728
.2228
.1736
.2895
.1191
.3836
.8225
.3242
.2726
.0562
.6457
.0724
.2688
.4549
.2320
.9187
.6901
.2888
.1116
.5959
.2159
.7237
.0771
.0399
.8597
.4795
.4795
1.000
.5959
.1116
.3768
.1958
23
5077
1

Key9
.5858
.8064
.9496
.0930
.6109
.7957
.1647
.4255
.6383
.8283
.3422
.9982
.0902
.3623
.6880
.6942
.4656
.3087
.7545
.1116
.3768
.8597
.8597
.1573
.1573
.2159
.4795
.4795
1.000
.3768
1.000
.7237
.2159
.8627
24
5079
9

Mean value = 50172

Session Keys Used (HEX):
1: 00000000000000000000000000000001
2: 00000000000000000000000000000002
3: 00000000000000000000000000000004
4: 00000000000000000000000000000008
5: 00000000000000000000000000000010
6: 00000000000000000000000000000020
7: 38b3c50fd5b1bccc49e786ebf28f5a51
8: 04b81a3a854e38b6775cbf4caeb4f1e5
9: f2a09ae954cda165661efc765aeeb0c3
a: 9f9e5ded6e10cfa557c1fe0ed02f1f3f
Fixed key (in HEX): ecb91d4ce0badb56023ca06869e92a2f

37

Keya
.0163
.1070
.4803
.7717
.0971
.1030
.0772
.3310
.4330
.5846
.0840
.8099
.0264
.1006
.9286
.8530
.9309
.4361
.3233
.2888
.0771
.0339
.0216
.3768
.2888
.7237
.8597
.8597
.1573
.4795
1.000
.8597
.1116
.7661
23
5074
2

Appendix F.
Results of Entropy Tests
Distribution of Subblocks

Length of output stream = 1 Gigabyte
Number of streams = 1
Subblock
p-value
size
Ones
Runs
40
.1772
.2998
48
.3579
.1554
56
.0300
.9347
64
.2233
.7193
128
.4774
.9479
256
.0700
.7785
512
.5697
.2228
1024
.9494
.5528

38