Evaluation of MULTI-S01
January 17, 2001
Information Security Research Centre
Queensland University of Technology
Ed Dawson, Andrew Clark, Helen Gustafson,
Bill Millan, Gary Carter

TABLE OF CONTENTS
1
2
3

Executive Summary .................................................................................................... 3
Description of MULTI-S01 ........................................................................................ 5
Structural Aspects ....................................................................................................... 5
3.1
The MULTI-S01 Keystream Combining Operation........................................... 5
3.2
Panama Structural Aspects ................................................................................. 6
3.3
Equivalent Keys .................................................................................................. 6
3.4
Mode of Operation and Key Management.......................................................... 6
3.5
Bit Dependencies of Panama Algorithm in Stream Cipher Mode...................... 7
3.6
Long Message Techniques.................................................................................. 8
4
Keystream Properties .................................................................................................. 8
4.1
Period .................................................................................................................. 8
4.2
Linear Complexity .............................................................................................. 9
4.3
Statistical Analysis.............................................................................................. 95
Possible Attacks ........................................................................................................ 10
5.1
Simple Attacks .................................................................................................. 10
5.2
Divide and Conquer Attacks............................................................................. 10
5.3
Correlation Attacks ........................................................................................... 11
5.4
Linear Cryptanalysis ......................................................................................... 11
5.5
Differential Cryptanalysis................................................................................. 12
5.6
Attacks on the Integrity Check ......................................................................... 13
5.6.1
Wiretapper Attack..................................................................................... 14
5.6.2
Insider Attack............................................................................................ 14
5.7
Other attacks ..................................................................................................... 16
6
Implementation ......................................................................................................... 16
6.1
Software ............................................................................................................ 16
6.2
Hardware........................................................................................................... 17
7
Conclusion ................................................................................................................ 17
8
References................................................................................................................. 18
9
Appendices................................................................................................................ 20

2

Evaluation of MULTI-S01 Algorithm
1 Executive Summary
This is a report on the stream cipher MULTI-S01. The MULTI-S01 cipher uses Panama
output as the keystream for a block-based chaining operation which provides a message
integrity check. Thus the MULTI-S01 cipher provides an extra service beyond that
normally associated with stream ciphers. The proposed mode of operation adds two
integrity check blocks to the message length.
In this report the evaluators discuss all relevant aspects of MULTI-S01. In particular we
discuss the properties of the operations involved and their suitability for the stated design
goals. Critical aspects of the design are examined and the requirements for its correct
operation are noted. For this algorithm the evaluators have(i) analysed structural aspects;(ii) evaluated the basic cryptographic properties;(iii) evaluated the security from attack;(iv) evaluated the statistical properties;(v) surveyed the speed.
There are several specific claims that are made for MULTI-S01 in the abstract of[MULTI-S01]. The security claims are that MULTI-S01..
1. achieves high security of data confidentiality, assuming a secure PRNG.
2. high security of data integrity
3. an attacker cannot determine any part of PRNG output just from known plaintexts.
The performance claims are that MULTI-S01
1. operates faster than encryption algorithms based on block ciphers.
2. pre-computation of the random sequence is easy to do.
In this report we examine the accuracy of these claims. Our results may be summarized
by noting that the following two basic flaws have been found in MULTI-S01.
FLAW 1 Lacks Robustness
The security claims, while strictly true, are not robust in that they fail to be true under aminor violation of the key management rules. It is vitally important that implementationsof MULTI-S01 adhere strictly to the key management rules that require a new key to be
used for every encryption.
FLAW 2 Attacks on integrity check
With knowledge of the key, it is a simple task for an insider to find two messages which
produce the same integrity check. This is a serious flaw in integrity check mechanism.
3

Due to these two flaws, especially Flaw 2, the evaluators would not recommend theadoption of MULTI-S01 Algorithm as a standard.
We finally note that the lack of a theoretical proof for the security of the PRNG Panama
is clearly a potential weakness in this system. It is interesting that a scheme that relies soheavily on the security of the underlying PRNG has been defined to use Panama, which iscertainly very fast but unfortunately has no proof of security. Given the existence ofdesign methods and criteria for provably secure stream ciphers, it is clear that the designof MULTI-S01 is more strongly influenced by performance efficiency than by the needfor future security.

4

2 Description of MULTI-S01
The MULTI-S01 cipher is an entire message encryption algorithm. A new key is used forevery new message. The encryption process can be outlined as follows.

1. Create the key material (A, all Bi and S) by running Panama on the combination of
key K and diversification parameter Q.
2. Pad the message to a multiple of 64 bits using standard means. Then append two
blocks with key and redundancy data.
3. Encrypt block “i” by XOR with 64-bits of Panama output: Bi. Store this as Fi
4. Multiply each block by the 64-bit value A, using the designated finite field.
5. XOR Fi-1 by the result of (b) to make ciphertext block “i”.
The decryption operation is the reverse of encryption, with the provision that if theredundancy values do not match, then the ciphertext is deemed invalid and the recovered
plaintext is not output. Decryption is as follows.

1.
2.
3.
4.

Execute Panama(K,Q) to produce the key material {A, Bi, S}
Decrypt each block by XOR with Fi-1 data, multiply by A-1, and XOR with Bi.
Check that the calculated redundancy values agree with what was expected.
Either output the recovered plaintext block “i”, or declare it to be invalid.

The Panama stream cipher is constructed as a large buffer that is slowly updated, together
with a state that is quickly changed by a nonlinear operation and XOR with buffermaterial. The internal data of the Panama cipher is initially set to zero. Then the key anddiversification data (each a block of 256 bits) are PUSHed into the cipher. Then 32 blank
PULLs are performed to diffuse the input data around the buffer and state. After this theoutput bits are taken 256 bits per subsequent PULL operation. These PUSH and PULL
operations are described in detail in [DAEM 98].

3 Structural Aspects
3.1 The MULTI-S01 Keystream Combining Operation
The typical method for combining keystream and plaintext for stream ciphers is the bitwise
exclusive-or (XOR). This provides perfect secrecy for each bit but does still allow ciphertexts
to be altered during transmission so that altered plaintext is recovered. In the worst case thismay allow an attacker to subtly alter the semantic meaning of a message, for example
changing the account number of a bank transaction.
To foil this attack, the MULTI-S01 algorithm uses a block chaining method to prevent
ciphertext alteration. Firstly, finite field multiplication allows changes within a block to alter
many plaintext bits. Secondly, the XOR of internal data from the previous block, together
with the encoding of redundancy information, provides a mechanism for any alterations toresult in the wrong value of redundancy being recovered. Any decryption that results in an
invalid redundancy value is declared invalid, and the recovered “plaintext” is not revealed.

5The features we would wish from an integrity check is that it will reject any altered ciphertext,
and that passing the test establishes the validity of the recovered plaintext. Attack scenarios
against the integrity check are discussed in Section 5.6. These attacks demonstrate tat the
integrity check mechanism is seriously flawed.

3.2 Panama Structural Aspects
Panama has several thousand internal memory bits. Without obvious structural weaknesses,
this is probably sufficient to provide resistance to conventional attacks. These aspects are
discussed in Section 5.
The cycle structure of Panama is unknown. This relates to the lack of proof for theminimum period. There may be many separate cycles for each initialisation by K,Q, or
they may all be on the same large cycle, merely out of phase. There may even be cycles
that exist for the operation of iterated PULLS in Panama, but are never achieved inpractice since there are no values of K,Q that create initial data that exist on those cycles.
We contrast these uncertainties with the theoretical proof that exists for the period andcycle structure of traditional LFSR based stream ciphers: where all keys produce thesame (albeit shifted) keystream that has maximal period. It may be that different K,Qvalues cause Panama output sequences that have different periods, so that not all keys
would offer equal security. It is possible (but certainly improbable) that there exists small
cycles for Panama, so that there would exist weak keys in the sense that the induced
sequences have period smaller than the message length.
3.3 Equivalent Keys
The existence of equivalent keys was noted in [SELF], as corollary 1 in Section 2.3, where it
was used to demonstrate the property of perfect secrecy. While we agree with this, there arealso disadvantages of equivalent keys which the evaluators point out here.
In MULTI-S01, there are equivalent keys that reduce the effective keyspace by a factor of 264.
This reduces the size of the keyspace from 2256 to 2192. For any given triple of plaintext
message, key and associated ciphertext, there is a set of 264 keys that satisfy the triple. To see
this, consider changing the value of A to any other value, then the values of all Fi change to
new values, and so there will be some different value of Bi that allows the plaintext blocks toremain unchanged. Thus there exists 264 -1 other equivalent sets of keys {A,Bi,S}. Whether
these could have been generated by any original key K and diversification parameter Q is
unknown. In implementations where there is no method of “authenticating” the key material{A,Bi,S} there is no barrier to a key falsification attack, and hence a third party can beconvinced that a different key {A’,B’i,S’} was used in an encryption. This demonstrates thatthe key management is vital to the security of MULTI-S01.

3.4 Mode of Operation and Key Management
MULTI-S01 is a stream cipher. The confidentiality of the plaintext is guaranteed by the factthat every message is encrypted with distinct key material. Contrast this style of key
management with that for block ciphers: many messages can be encrypted with the same key.
It is somewhat dangerous for this stream cipher to be presented as a block encryption
mechanism, since the differing key management requirements of these schemes result in theopportunity for a devastating attack. In particular, if MULTI-S01 is ever used in a mannerthat allows two (or more) messages to be encrypted under the same key, then a powerful
differential-style attack can recover the value of A. Then, following the comments above, theentire key becomes known. Subsequently, any additional message that is encrypted under the6same key will be recoverable from the ciphertext alone. The attack can be undertaken as achosen text or a known text attack, with very little data requirements. Either way the attack
can be done in real time. Details of this attack appear in Section 5.5.
The significance of this attack will depend on the application context. For example in asituation where MULTI-S01 is chosen for use as the in-house encryption method for acompany, then distributing a Trojaned version of the encryption software that does notchange the key for every new message would allow the attack whenever two known
plaintexts are available. This condition might be easily met if a standard header wereencrypted at the start of every message. Then the attack would allow real time decryption of
any ciphertext. Of course, this attack is true for any stream cipher, but we feel that MULTIS01 is more likely to become vulnerable to the attack since it adopts a block mode that may
encourage it to be used like a block cipher. Moreover, the consequences of such a mistake arecatastrophic for the security of the cryptosystem.
This example shows that the keys do need to be changed for every message. The security of
MULTI-S01 depends critically upon the correct key management techniques.

3.5 Bit Dependencies of Panama Algorithm in Stream Cipher Mode.
We have written a computer program that traces exactly those sets of K,Q bits upon whichstate bits depend. This allowed the diffusion properties of Panama to be studied. It was foundthat the key initialisation process is a very thorough mixing.
Summary: all state bits depend on all input K,Q bits after 5 of the 32 blank PULLS during the
set-up phase. Thus there is over six times the effort required to achieve completeness: this isthorough mixing, when compared to DES [FIPS DES] that achieved completeness after 5/16
of its operation.
Each bit of the state depends on exactly the same number of K,Q bits as every other bit in thesame word. This greatly simplifies the presentation of this data. We now present the range
taken by the number of K,Q bits that influence the state bits, over all of the 17 words in thestate. The table below shows the influence after a small number of PULLS, to illustrate therate at which the influence increases.
Number of PULL
operations
0
1
2
3
4
5

Number of influencing
K,Q bits (512 total)
3- 7
31 - 36
162 - 187
389 - 413
510 - 512
512This data shows that all bits in a word have the same level of dependence on the initial K and
Q values, so that we have proved there do not exist “weak” bits positions, in the sense of bitsthat depend on relatively few of the initial K,Q bits. We find the diffusion of Panama to besatisfactory, and we find no exploitable weaknesses in this aspect of the cipher.

7

3.6 Long Message Techniques
The MULTI-S01 algorithm has a specific method to deal with long messages: they arebroken up into portions of 238 bits each, indexed from 0, which are each then encrypted as 232
blocks under the same key K, but different diversification parameters Q. The standard
method is to let Q equal the index of the sub-message. The redundancy value R is stated to be
the same as Q for each encryption. As R is 64 bits and Q is 256 bits it seems that R must be
set to the 64 least significant bits of Q. We note that it is not clear from [MULTI-S01] how R
is determined for standard, or short, messages.
This splitting of large messages has the effect of placing an upper bound of 2-32 on theprobability that a random ciphertext will pass the integrity check. While this is a fineambition, we note that the overall complexity of the random forgery attack is constant at
264, as set by the block size in bits (see Section 5.6).

4 Keystream Properties
The evaluators analysed the basic keystream properties of the Panama algorithm which
provide cryptographic security. These include a large period, large linear complexity andwhite-noise statistics. It should be noted that for the Panama algorithm there are no
theoretical results which can be applied to measure these properties, unlike LFSR based
keystream generators where these properties are known.
Experimental results, which are included below for linear complexity and statisticalanalysis, were conducted by the evaluators using the CRYPT-X package. This is astatistical package which was previously designed by the evaluators for analysing
encryption algorithms. The relevant pages from the CRYPT-X manual have been
included in Appendix A.
4.1 Period
The actual period of the Panama algorithm is difficult to determine. All together there are2512 keystream sequences that can be generated from Panama by selecting values for key,K, and diversification parameter value, Q. As mentioned in Section 3.3 there is a small
probability that some of these sequences are equivalent. In order to determine theexpected period of one of these sequences the evaluators are of the opinion that a suitablemodel is a block cipher in output feedback mode (OFB). As shown in [DAVI 82] thisperiod can vary greatly. However it is possible to determine an expected value for theperiod by applying the birthday paradox. For block ciphers in OFB mode the expectedperiod depends on the length of the input block to generator, n, and the number of bits
which are feedback, L. If L = n then expected period is approximately 2n-1 and for L < nnthe expected period is approximately 2 2 −1 . In the case of the Panama cipher we have n =544 and L = 256. This would mean that the expected period is approximately 2273.
We should emphasise that the actual periods of different keystreams produced by Panama
most likely will have a large variance. However the expected results above indicate thatfor any given sequence there is a high probability that this period is extremely large.

8

4.2 Linear Complexity
Since there is no theoretical support for the linear complexity of Panama, empirical tests
on the value of linear complexity and the linear complexity profile have been investigatedusing the CRYPT-X package. The linear complexity tests were applied to the ten Panama
output streams of length 106 bits, and 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 B. The results for the linear complexity profile indicate that, as the
bit-stream increases in length, the changes in linear complexity maintain the expectedvalue of half the stream length. These results support the randomness of the output fromPanama, based on linear complexity. These results support the fact that the whole bitstream is required to re-construct the stream itself - thus giving an attacker no advantage
in being able to create the bit-stream with a smaller number of output bits.
4.3 Statistical Analysis
The statistical randomness applied to Panama are the tests explained in the CRYPT-X
package (see attached documents), namely the frequency, binary derivative, change point,
subblock, runs distribution, sequence complexity, and linear complexity tests. 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 asample result would be obtained if the algorithm produces a random stream. Very small
p-values would support non-randomness.
The first five tests were applied to binary output streams of 107 bits, and the twocomplexity tests were applied to binary output streams of 106 bits (due to the amount oftime required for the tests), using ten different keys.
The subblock tests were applied to the output stream by dividing the bit-stream into nonoverlapping subblocks of length 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.
Results of Statistical Analysis
The results give the lowest p-value for any one test as 0.001, with 13 of the 360 p-values
obtained falling below 0.05. This represents a proportion of 0.036 of the tests applied,which is below the 0.05 level, and so supports the randomness of the output from Panama.
For more detailed results see Appendix C.
In the results of the statistical analysis of Panama presented in [SELF] there is recorded a
run of length 32 in a sample of 221. We agree that this is a rare event with a small
probability. In order to investigate this in more detail the length of the longest run wasrecorded for the samples of 107 bits. The length of the longest run in these larger samples
that the evaluators analysed was 29 (Key 5), whereas the remaining keys gave thelongest runs as 28. Hence, together with the results of the runs test applied from CRYPTX package, this indicates there is no problem with the distribution of runs in samples
generated by Panama.
The sequence complexity test provides an effective method of detecting periodicity or
periodic patterns in the bit-stream. In the bit-streams tested all sequence complexity
9values exceeded both the threshold value and the average value of sequence complexity
for bit streams of length 106. These results support the conclusions on the period ofPanama in Section 4.1 above.

5 Possible Attacks
The majority of the literature discusses attacks on stream ciphers that adhere to the LFSR
combiner/filter model, in order to achieve provable properties with regard to period andlinear complexity. The Panama cipher avoids these models and uses large internal
memory, with the result the standard attack strategies seem to be ineffective. On the other
hand, there are no proofs for even the basic security properties. Despite the lack of proof,
however, we feel that the memory size and structure of Panama is sufficiently complex toensure that the security of the cipher cannot be compromised. The possible attacks are
categorised and examined individually in the next few paragraphs.
In this section we also consider attacks against the integrity check. We have establishedthe complexity of random forgery attacks made by a wiretapper, and also assessed theability of an insider to cheat the system. These integrity attacks are discussed in moredetail in Section 5.6.
5.1 Simple Attacks
Simple attacks are those based on exhaustive search, period, linear complexity, andstatistical attacks on non-uniform output. The memory size of Panama is clearly so largethat exhaustive search is infeasible. The period of Panama (see also Section 4.1) is (veryprobably) not less than 2273. This is obtained by considering the Panama structure to be
similar to a block cipher in OFB mode, with less then the full amount of feedback [DAVI82]. The linear complexity is also likely to be very large. Note that so long as the period
and linear complexity are larger than the amount of data being encrypted under a single
key, then the scheme can be said to be operationally secure, ie., it is secure so long as thecorrect operation of the key management is maintained. It seems likely that the period
and linear complexity of Panama are both many orders of magnitude larger than any
feasible message length, and so Panama appears to be operationally secure against thebasic attacks. However, we re-state that there is no proof for the minimum period orlinear complexity of Panama.
5.2 Divide and Conquer Attacks
Divide and conquer attacks are applicable where the structure of a keystream generator
can be exploited by assuming some known data, and the remaining bits can be recovered
faster than exhaustive search. In the case of Panama the total memory size is several
thousand bits, and there is no clear way to conduct a divide and conquer attack so that it
results in a break faster than exhaustive search.
There is a two bit rotation in the buffer update process, and this value is not relatively
prime to the size of buffer data, so that the buffer may be considered to be two separate
buffers of half the size, which do not interact directly. This observation might lead to a
divide and conquer attack , except for the fact that these two half buffers do interact

10indirectly via the effect of the state data. This interaction serves to prevent the attack
being effective.
5.3 Correlation Attacks
Correlation attacks can be performed where the model of a noisy LFSR sequence is used
to exploit correlations between state bits and output bits, and in particular correlations
with single bits are preferred. Our analysis of the Boolean function that underlies thenonlinear state update transformation indicates that no biases exist with fewer than 3
input bits, or equivalently that the function is second order correlation immune [SIEG 85].
This, combined with the vast internal memory, make correlation attacks on Panama
appear to be infeasible. All non-zero correlations have probability 0.5 ± 2-3. These
correlations are not great enough to make the attack feasible, given the order ofcorrelation immunity and the large size of the internal memory. We conclude that
correlation attacks against Panama are infeasible.
5.4 Linear Cryptanalysis
The basic approach for linear cryptanalysis of block ciphers, as pioneered by Matsui[MATS 93] is the collection of a sufficiently large number of data samples, so that any
available input/output correlations can be used to correctly determine the values of key
bits. The bias provided by a set of linearly independent modulo 2 equations is given by
the piling-up lemma, which relies on the equations being independent, and all internal
values cancelling out leaving a linear expression for key bits in terms of known plaintext
and ciphertext bits.
Linear cryptanalysis of stream ciphers using a linear sequential circuit approximation wasinvestigated by Golic [GOLI 94], where a general attack was suggested that exploits ageneral statistical weakness of output blocks which exceed the size of the internal
memory. These attacks are especially effective against stream ciphers based on LFSR
combination/filtering. However, structures such as Panama are not particularly
susceptible to this attack. Given a suitable nonlinear Boolean function (which Panamahas) then the dominant factor affecting the complexity of the linear attack is the size ofthe internal memory. According to [GOLI 94], the complexity of finding useful linear
correlations, is at least O(2m), where m is the size of the internal memory in bits. As
Panama has 8736 internal memory bits, the attack is infeasible.
The evaluators suggest that the wrong model for linear cryptanalysis of stream ciphers
was employed in [SELF], and that the approach described in [GOLI 94] should be used.
We have several criticisms of the analysis in [SELF]:
1) The approach in [SELF] ignores the 256 bits of additional state data that is not output
at each PULL operation, but is fed back into the buffer.
2) In addition, [SELF] contains a claim that linear correlations involving one bit exist for
the nonlinear operation in Panama, which have bias of 2-3. We strongly disagree withthese claims, as an exhaustive search of the appropriate Boolean function properties
reveals that there are exactly 64 linear correlations with a bias of 2-3, but these biases
exist only for input masks of weight 3 or more. In fact, all other linear approximations
have no bias at all, so that the Panama state update transformation is immune tocorrelations with linear functions of 2 inputs or fewer. This means that the Booleanfunction in Panama satisfies second order correlation immunity, which is a very
desirable property in stream ciphers as it places a lower bound on the complexity of a11

correlation attack. The details of this Boolean function, and its analysis, appear in
Appendix D.
3) The number of independent equations required to complete the cryptanalysis is statedwithout evidence in [SELF] as 63. However, our analysis suggests that at least 256
independent equations for single buffer/key bits are required. This would greatly
increase the data requirements for an attack.
We conclude that, due to the very effective and complex nonlinear mixing operation of
Panama, conducting any linear cryptanalytic attack would require infeasible amounts ofmemory and computation.
5.5 Differential Cryptanalysis
Firstly, we note that 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. We recall that differential cryptanalysis was originally developed inrelation to block ciphers (see [BS90]) where it exploited the attackers ability to generate
the encryptions/decryptions of specially chosen pairs of text, under the same key. As the
keystream generator of a stream cipher is a deterministic finite state machine initialisedby the key, the concept of a differential attack is not meaningful in the context of stream
ciphers, where every message is supposed to be encrypted under a separate key.
However, in the case that two MULTI-S01 messages are encrypted with the same key,then we note the possibility for a powerful attack that recovers the value of the A key.
Once that is found the other Bi and S keys can be found easily. The attack works asfollows.
Given two different messages (which may be no more than a single block each),encrypted under the same (but unknown) key, we have two different ciphertexts.
Alternatively, in a chosen ciphertext attack, we may select the exact XOR difference inthe ciphertext block and observe the effect on the recovered plaintext. The attack canproceed either way, and we note that only the key A affects the XOR differences, since
all other keys are XORed, and so cancel out.
Analysis of the finite field multiplication (FFM) operation reveals that all output bits aresecond order, or quadratic, Boolean functions of the bits in the fixed multiplication input,
which is the key A. It follows from results in [LAI 94], [MILL 95] that the Booleanfunction of the derivative of FFM is linear in these input bits. Hence the XOR differencein the recovered plaintext gives 64 bits of information that can be used as the right handside data for a set of 64 simultaneous equations in the 64 unknown A bits. The matrix is
specified by the polynomial used to determine the finite field representation, so thismatrix is public information, and the same for any key being used. If this matrix is nonsingular, then a unique solution exists and can be found by inverting the matrix. If, on theother hand the matrix does not have 64 linearly independent equations, then extra
equations can be obtained by repeating the attack on messages of length greater than one
block. With high probability a set if linearly independent equations will be obtained fromthe encryption of very few blocks. The complexity of matrix inversion is polynomial in
the size of the matrix. Here the matrix is 64*64, so no more than a couple of thousand
fast operations are required to invert it. We conclude that the complexity of this attack is12

so very low that it is quite feasible to perform in real time. Of course it is only applicable
if the strict key management requirements of stream ciphers is violated.
5.6 Attacks on the Integrity Check
The security of MULTI-S01 has been investigated in relation to its capability ofproviding an integrity check.. The complexity of creating a wrong ciphertext that does
satisfy the integrity check is 264 block encryptions. This value depends entirely on theblock size. There is a message length/time/probability tradeoff in the attack, so, forexample, there exists a probability of 2-32 that a single message of size 232 blocks will
satisfy the integrity check. This probability might be too high for some secure
applications.
Our analysis has shown that the integrity check performs correctly in one aspect: given a
fixed ciphertext and the corresponding key there is only one possible plaintext that could
have been sent. To see this, consider the decryption of the last two blocks of a message,
which are the integrity check blocks. If the last two blocks are confirmed as equalling S
and R then the chaining data Fn-2 must be correct. Tracing the effects backwards indecryption for each block reveals that the recovered plaintext blocks are correct.
However, we note from [SELF] that the possibility to alter the ciphertext and yet pass theintegrity check is non-zero. In fact it has been shown that the probability for a random nblock ciphertext to pass the decryption integrity check is given by the proportion of the A
key values which are the solution to a polynomial of degree n-2 in A. As there are at mostn-2 different solutions, the maximum probability of passing the integrity check with eachtry is (n-2)/(264-1). As the number of blocks of a message in never more than 232, we seethat the probability for a randomly selected ciphertext to pass the integrity check is no
more than 2-32. The complexity of making the attempt at this maximum probability is theencryption of 232 blocks. The overall complexity of the attack is 232 * 232=264. Hence thecomplexity of the random forgery attack is given by the number of bits per block: 64.
Increasing the block size will directly increase resistance to the forgery attack and makethe integrity check more reliable.
We visualise two possible attacks on the integrity check of MULTI-S01. The first
involves an eavesdropper(wiretapper) who randomly alters the ciphertext hoping theresulting ciphertext passes the receiver’s integrity check. The second involves an insider
who knows the fixed value A, message M, and ciphertext C enabling such a person to
make changes to the ciphertext which are guaranteed to pass the receiver’s integrity
check. Note that message M consists of the first n-2 blocks of the plaintext P.
We refer to the following equation that appears towards the end of section 2.4.1 in[SELF].
0 = ⊕ i =0...n ' −2 δ n ' −i −1 A − (i +1)(1)This is the equation that must be satisfied for an altered ciphertext to pass the receiver’s
integrity check. Note that if C i is the original ciphertext block then C i ⊕ δ i represents thealtered ciphertext C* i .

13

5.6.1 Wiretapper Attack
In this attack, the wiretapper selects some δ i ’s at random and hopes that they satisfy
equation (1). As per [SELF], the probability that the randomly chosen δ i ’s satisfy
equation (1) is the probability that the actual value of A used is one of the n-2 possible
values of A that satisfy equation (1) for the chosen δ i ’s. This probability is (n-2)/(2 64 -1)
as appears in [SELF]. Given that the largest value of n is 2 32 this probability is upperbounded by approximately 1/2 32 . Thus, the complexity of this attack is approximately
2 32 . Even if the chosen δ i ’s result in a ciphertext that passes the receiver’s integrity
check, it is highly unlikely that the plaintext, resulting from the altered ciphertext, will bemeaningful, so in some sense this attack represents a denial of service. Note that this
attack is a ciphertext only attack, since the wiretapper need only have access to theciphertext. Note further that such an attacker cannot verify the success or otherwise of theattack.
In the light of the note at the end of the preceding paragraph and the complexity of theattack, we do not believe that this attack is a serious threat to MULTI-S01 which is inagreement with the analysis in [SELF].
5.6.2 Insider Attack
In the second attack, we are assuming the insider has access to the value A, message M
and ciphertext C. While in [SELF] knowledge of A is specifically denied, it is plausiblethat either the sender or the receiver could act maliciously and deny sending or receivinga particular message, and be able to demonstrate as proof, a different message thatsatisfies the integrity check. This attack is clearly more menacing in that it is possible forthe attacker to select δ i ’s guaranteed to pass the integrity check as follows.
Since the attacker has knowledge of the value A, such a person can substitute this value
into equation (1) and get a linear relationship among the n-1, δ i ’s. The attacker can thenchoose δ i = 0 for i = 0 to n-3 and i = n, then make a judicious selection for δn-2 andfinally set δn-1 to be a certain predetermined value which will guarantee the receiver will
have an altered message that will pass the integrity check.
The attacker carries out the following steps.
1.
2.
3.
4.

Change Cn-2to C*n-2.
Determine P*n-2 = (Cn-2⊕ C*n-2) ⊗ A −1 ⊕ Pn-2.
Determine C*n-1 = Pn-2⊕ P*n-2⊕ Cn-1.
Send ciphertext C i for i = 1 to n-3 and for i = n, and C*n-2 and C*n-1.

The proof is as follows.
By the decryption algorithm
P*n-2 = (C*n-2 ⊕ Fn-3) ⊗ A −1 ⊕ Bn-2

(2)

and
14

Pn-2 = (Cn-2⊕ Fn-3) ⊗ A −1 ⊕ Bn-2(2) ⊕ (3) gives(3)

P*n-2 ⊕ Pn-2 = (C*n-2 ⊕ Fn-3 ⊕ Cn-2 ⊕ Fn-3) ⊗ A −1

(4)

Thus, P*n-2 = (C*n-2 ⊕ Cn-2) ⊗ A −1 ⊕ Pn-2

(5)

Now S = (C*n-1 ⊕ F*n-2) ⊗ A −1 ⊕ Bn-1
and S = (Cn-1 ⊕ Fn-2) ⊗ A −1 ⊕ Bn-1

(6)
(7)

(6) ⊕ (7) gives
C*n-1 = Cn-1 ⊕ Fn-2⊕ F*n-2= Cn-1 ⊕ Pn-2 ⊕ P*n-2(8)

A simple example with n = 4 has been implemented and is described below.
Panama parameters (K & Q) as per supplied test vectors:
K: bcfb8d1629964f571bea19eacdd1a9a8870622392094af2bc18e6942eb017b0f
Q: 70b91d006387740d0397095a33de361f4a631b3023f06c6a2e3c0cb2647f26bb
R: 0000000000000000
Output from Panama:
A: 0D8B8EF7C5814F2F
B1: 0431A2CEFB23CBA4
B2: BFF041318C4F63E8
B3: 65F97EC547EC7B63
B4: 82CFE82374CD5CC0
S: 19AE68546A9DCDAF( A-1: 5AA6FCBEC904B0CA )Message
P1: FE61A5EE9147C270
P2: A944B97E03269A33
Ciphertext
C1: 84A1CB62375A8DD2
C2: B4905ED917F05E15
C3: 0F918ACD813EEBB0
C4: 33EEA7357B9BAFDA
Let
C2*: 7AD3EFA784A51367( selected at random )Then
P2*: 5E3D8D13E061F8BB( = ( ( C2 ⊕ C2* ) x A-1 ) ⊕ P2 )andC3*: F8E8BEA062798938( = P2 ⊕ P2* ⊕ C3 )Decrypting ( C1 | C2* | C3* | C4 ) gives
P1’: FE61A5EE9147C270( = P1 )15

P2’: 5E3D8D13E061F8BB
P3’: 19AE68546A9DCDAF
P4’: 0000000000000000( = P2* )( = S )
( = R )The significance of the above result is the ability of this second type of attacker to forge ameaningful message. The attack can be applied to any message, of any length. Given two
blocks of changed ciphertext, say blocks i and i+q, then the recovered plaintext is alteredfor consecutive blocks {i, i+1, …, i+q-1}, and is subsequently identical to the originalplaintext, including satisfying the integrity check. We note that this simple example has
only two blocks of ciphertext being altered. A real attack may change any number of
ciphertext blocks, so long as the last alteration restores the plaintext to the original, thus
allowing the integrity check to succeed.
The above attack is possible because the integrity check is really only a function of thelast 3 plaintext blocks. What is really needed is for the integrity check to be a function ofa greater number of plaintext blocks. The check should mimic a block cipher in Cipher
Block Chaining (CBC) mode where the last output is a function of all the input blocks.
As an example, for a similar attack to be performed on the Data Encryption Standard(DES) [FIPS DES] in CBC mode, the birthday paradox implies that the complexity
would be 2 32 since the block length of DES is 64. For the Advanced Encryption Standard(AES) this figure is 2 64 since the block length is 128. Complexities of 2 32 and 2 64 areacceptable from a designer’s point of view but the simplicity of the above attack(especially the determinism plus also the flexibility to choose the position of altered
blocks) indicates a serious flaw in the design of MULTI-S01.
5.7 Other attacks
The Inversion attack [GOLI 96] is prevented by the large memory. The requirements are
exponential in the total memory size (which is 8736 for Panama), so it is straightforward
to conclude that the inversion attack against Panama is infeasible.
A reconstruction attack was found to be very effective against the mobile
telecommunications algorithms ORYX [WAGN98] and CAVE [MILL98]. These attacks
exploited a fundamental weakness of those algorithms. Well designed ciphers will be
resistant to reconstruction attacks due to the increased time and data requirements. In
particular the Panama cipher is far too complex to attack by reconstruction: there is nofast way of rejecting a bad guess for any set of data. We conclude that Panama is secureagainst the reconstruction attack.

6 Implementation
In this section we investigate the implementation issues for the MULTI-S01 algorithm.
Section 4 of the self evaluation report [SELF] gives details of both software and hardware
implementations of the MULTI-S01 algorithm.
6.1 Software
Panama (the MULTI-S01 “engine”) is well suited to 32-bit processors because of its
heavy use of 32-bit word operations. The Panama algorithm can also be optimised for
64-bit processors. The MULTI-S01 algorithm (which “wraps” Panama) performs a 6416

bit finite field multiplication which is better suited to 64-bit processors. The figures
quoted in the self evaluation report (Section 4.1 of [SELF]) of 270Mbps on a 64-bit
processor running at 600MHz and 55Mbps on a 32-bit processor running at 350Mhz
highlight the difference in performance between 32-bit and 64-bit processors.
The evaluators were able to confirm that the Panama implementation is extremely
efficient running at approximately 730Mbps on a Pentium III 650MHz processor. The
overhead of the MULTI-S01 enhancements (especially the finite field multiplication)
significantly reduces the performance (especially on computers with 32-bit processors).
The code size and memory stack utilisation figures quoted (Table 8, Section 4.1 of[SELF]) indicate that a software implementation of MULTI-S01 on a memory-poor
device, such as a smart card, would be feasible.
6.2 Hardware
Section 4.2 of [SELF] describes logic circuit designs and gate size and throughput
evaluations for MULTI-S01. The hardware implementation described is actually asimulation and the document states that the quoted figures may actually be slower inpractice. The throughput rates of 8.3-9.1Gbps for a speed-optimised implementation, and620-730Mbps for a gate-count-optimised implementation, if correct, are impressive andindicate suitability for all but the most bandwidth-intensive applications.

7 Conclusion
The evaluators have conducted a thorough analysis of the properties of the Panama and
MULTI-S01 algorithms. There are some observed flaws in MULTI-S01, relating to theintegrity check mechanism and also the key management. We also point out that there areseveral problems with the analysis of [SELF].
The prospect of attacks on the integrity check mechanism are significant. For this reason
MULTI-S01 should not be used for high-security applications. Also the catastrophic
results of violating the key management imply that only fully trusted implementations of
MULTI-S01 should be used in any case. The evaluators suggest that MULTI-S01 be redesigned to address these issues before it is considered as a future standard.
We note that the lack of proof for the security properties of Panama remains a concern, as
other schemes do have proof of basic requirements. On the other hand, there seems to be
no pressing reason to doubt the security of Panama, and all of our analyses on thatalgorithm suggest that, with high probability, it has no exploitable weaknesses. An
advantage of this scheme is the very high rate of data throughput.

17

8 References[BS 90]E. Biham and A. Shamir, Differential Cryptanalysis of DES-like cryptosystems, In
Advances in Cryptology – Crypto’90, Volume 537 of Lecture Notes in Computer Science,
pages 2-21, Springer-Verlag, 1991.
[DAEM 98]
J. Daemen and C. Clapp, Fast hashing and Stream Encryption with Panama, Proceedingsof Fast Software Encryption Conference, Volume 1372 of Lecture Notes in Computer
Science, pages 60-74, Springer-Verlag, 1998.
[DAVI 82]
D.W. Davies and G.I.P. Parkin, The average cycle size of Key stream in Output feedback
Encipherment. Cryptography, Proceedings of Burg Feuerstein Conference, Volume 149
of Lecture Notes in Computer Science, pages 263-280, 1982.
[FIPS DES]
Federal Information Processing Standard: The Data Encryption Standard, US National
Bureau of Standards, 1977
[GOLI 94]
J. Dj Golic, Linear Cryptanalysis of Stream Ciphers, Proceedings of Fast Software
Encryption – Leuven ’94, Volume 1008 of Lecture Notes in Computer Science, pages
154-169, Springer-Verlag, 1994.
[GOLI 96]
J. Dj. Golic, On the Security of Nonlinear Filter Generators, In Proceedings of Fast
Software Encryption – Cambridge ’96, Volume 1039 of Lecture Notes in Computer
Science, pages 173-188, Springer-Verlag, 1996.
[LAI 94]
X. Lai, Higher Order Derivatives and Differential Cryptanalysis, in Communications andCryptography: Two sides of one tapestry, pages 227-233, Kleuwer Academic Publishers,
1994[MASS 69]
J. L. Massey, Shift Register Synthesis and B.C.H. Decoding, IEEE Trans. Inform.
Theory, IT-15:122-127, January 1969.
[MATS 93]
M. Matsui, Linear Cryptanalysis method for DES cipher, In Advances in Cryptology Eurocrypt’93, Volume 765 of Lecture Notes in Computer Science, pages 386-397,
Springer-Verlag, 1994.

18

[MILL 95]
W.L. Millan, Low order approximation of cipher functions, In Proceedings of CPAC
1995, LNCS Vol. 1029, pages 144-155, Springer-Verlag, 1995.
[MILL 98]
W.L. Millan, Cryptanalysis of the Alleged CAVE Algorithm, In Proceedings of ISISC’98,
Seoul, December 1998.
[MULTI-S01]
A Symmetric Key Encryption Algorithm MULTI-S01, Technical Document, October2000.
[SELF]
Self Evaluation Report MULTI-S01. 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, Springer-Verlag, 1998.

19

9 Appendices20

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 the hypothesisthat the bit stream was based on Bernoulli trials where the proportion of ones 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 this is possible the string
would not be considered to be random, especially in relation to its 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 notedthat not all of the tests can be applied to a string of this length due to computational
limitations. For example, in the linear complexity test one would need to examine asmaller substring of the keystream. It is recommended that strings of length 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 this assumption
the cryptanalyst knows the frequency distribution of the plaintext in terms of 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, withmean 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. This21

measures the probability of obtaining a number of ones equal to or further from the meanof 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
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 the imbalance ofones 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 and zeros
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 fromthe 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 newbinary 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 of these (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 (in theoriginal stream).
p̂(1) < ½ means there is a larger proportion of the group of 00 and 11 two-tuples (in theoriginal stream).

22

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 of ones in thesecond binary derivative, p̂( 2) , gives the proportion of the total number of 001, 011, 100,110 patterns in the original stream.
p̂( 2) > ½ means there is a larger proportion of the group of 001, 100, 110, and 011 threetuples.
p̂( 2) < ½ means there is a larger proportion of the group of 000, 010, 101, and 111 threetuples.
A combination of the frequency test on the original stream and a similar test on the firstand second binary derivatives, tests that there is an equal number of the eight overlapping
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 be considered 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 for eachstatistic. A small significance probability indicates a significant result. For large n( n > 100000 ) a highly significant result (significance probability < 0.001) indicates apossible 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:

23

11.61 % of bit streams of length 49 will have a number of ones equal to or further fromthe 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 of overlapping 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
Interpretation:
2.09 % of bit streams of length 48 will have a number of ones equal to or further fromthe 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 the frequency
test on the stream and the first two binary derivatives. Even if π = 12 and the stream 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 threetuples 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:
p=e−

2 Max 2nS [ n ]( n − S [ n ]).

24

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−

p=eInterpretation:

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

The actual significance probability of the change in the proportion of ones is less than
53.9%. This result indicates there is no significant change in the proportion of ones inthe 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 of subblocks 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
The test statistic used is χ =∑ 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 with achi-square distribution with degrees of freedom equal to 2 b − 1 . For values of b > 6 thenormal 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 containing b bits. Given
the binary stream is divided into S b-bit subblocks then, for a random stream, each of theN = 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 → ∞ where NS → 0 , then the distributionof the number of subblock repetitions in the sample approaches a Poisson distribution
b

2

−

S

with a mean of λ = S − N (1 − e N ) . When S = 8 N the mean converges to 32, for large

25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 two-tailed
test applies since both too few or too many repetitions may indicate non-randomness ofthe 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 are verylarge, no sample stream will be shown. Instead, the following data will be used toillustrate a test calculation for the uniformity test:
b = 8 (hence the uniformity test is applied)n = 100000
100000 
S== 12500 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:

26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 andgaps of the same length. Based on Golomb's postulates, the expected number of runs oflength i for a random binary stream should be 21i of the number of runs, and for eachlength 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. The
2 i +1
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].
The long runs are added together to form new variables s0k and s1k corresponding to then0number of gaps and blocks of length k or more, where s 0 k = ∑ r0i and n0 is the number
i=kof zeros in the stream.
By adding the long runs together a certain amount of information will be lost. In order tominimise the amount of information lost, it is recommended here that k = log 2 n5+1 − 1 .
For a stream of length n = 106 this would give a maximum value of k = 16, and hence thenumber 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 < k27

s1k = number of runs of 1 for lengths ≥ k
The variables:
r1i − n ( 12 ) 2+iui =i = 1,..., k − 1n
s − n( 12 ) k +1
u k = x k = 1kn
r − n ( 12 ) 2+i
u k +i = y i = 0ii = 1,..., k − 1nn −1n
u 2k = z = 1 2nare asymptotically normally distributed with zero means and variances and covariances:σ( 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 .
3.
Calculate u j for j = 1,...,2k using above formulae.

4.

[ ]

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
2

follows a χ 22 k distribution (chi-squared 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
i =1

2

i< j

The significance probability value, p, of the chi-squared distribution is calculated for thisstatistic. 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.
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 asmaller significance probability.

28

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 :σ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 from theexpected 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 thestream, s, is viewed from beginning to end [LEMP 76].
Example (n = 16) :s=1001111011000010
29

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 tobe patterned, ie not random. For the example given, the threshold value = 164 = 4 . Hencethe stream is not considered patterned.
An expected value for the sequence complexity of a random stream of the same length iscalculated 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 of sequence
complexity is always greater than the threshold value. However, a bit stream will only beconsidered to not satisfy the sequence complexity test if the value of c(s) is less than thethreshold value.
The sequence complexity is used to replace the autocorrelation test which is commonlyused 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:
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 toreconstruct the whole stream. Every finite stream, s, can be produced by a linear30

feedback shift register (LFSR). The length of the shortest LFSR which will produce thestream is said to be the linear complexity of the stream, which will be denoted by L(s).
If the value of L(s) is L then 2L consecutive terms can be used to reconstruct the whole
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 a verysmall linear complexity. An example of this is an m-sequence (see [RUEP 84]). An msequence has a period of length 2 L − 1 and a linear complexity of L. An m-sequence has
the best possible distribution of zeros and ones for a sequence of period 2 L − 1 . In thisfashion an m-sequence appears to be statistically random in terms 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 [RUEP 84],

[KREY 81]. Using the standardised normal statistic z =8186( L( s ) − n2 ) the significanceprobability 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 thealgorithm.
The linear complexity test by itself can classify as random, streams which may be highly
patterned, or contain large substrings which are highly patterned. Some of the previous
test results should support this. e.g. a stream of n2 − 1 zeros followed by a one, and thenfollowed 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 ispossible to construct a stream of length n which would pass all the previous statisticaltests, 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.
31

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 thelinear 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 any large 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 distributedwith µ = n4 and σ 2 = n8 [CART]. The standardised statistic for the number of jumps is

z=

8
n

( 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 small value 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 in the 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 the differencein 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 basedon 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 the expected number ofjumps of height i, e i , is given by e i = p i × F .

(f i − e i ) 2[CART 87]. The maximum value ofei
i =1
i = m is determined from the condition for the chi-squared test, that e i > 5 . The numberof degrees of freedom, m − 1 , is determined from the sample taken.
The significance probability value, p, of the chi-squared distribution is calculated for thisstatistic. A small significance probability indicates a significant result – i.e., the stream isconsidered to be non-random. For large samples a highly significant result, p < 0.1% ,indicates a possible weakness in the algorithm.
m

The chi-squared statistic used is χ 2 = ∑ExampleTest stream:
10100010000101110001011000111010101010101010000001
Calculations and results:

32

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 theBerlekamp-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 number of jumps inlinear 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 thetest on the distribution of the linear complexity jump size.

A.2 Bibliography[BEKE 82]
[BHAT 77]

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.
33

[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]

[WEBS 86]

J.M. Carroll and L.E. Robbins, “Using binary derivatives to test an
enhancement of DES”, Cryptologia, Vo1 12 number 4, 1988, pp 193-208.
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 Entropy ofSymmetric 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 and Sons,
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 122-127.
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 and Monographs;
Vol. 68, Marcel Dekker Inc., 1986, pp 97-193.
A.E. Webster and S.E. Tavares, “On the Design of S-Boxes”, Advances in
Cryptology: Crypto' 85, Springer-Verlag, 1986, pp. 523-530.

34

Appendix B.
Results of Linear Complexity Tests on Panama

Length of output stream = 1,000,000 bits.
Number of streams = 10
Test

Key
1

Key
2

Key
3

Key
4

Key
5

Key
6

Key
7

Key
8

Key
9

Key
a

Linear Complexity 500000 500000 500001 500000 499999 500000 500000 500000 500002 500000
LC p-value.500 .500 .834 .500 .166 .500 .500 .500 .974 .500
LC profile – Jumps .814 .357 .791 .801 .074 .037 .467 .715 .498 .090
LC Profile – Jump .419 .750 .186 .908 .921 .198 .077 .015 .745 .584
Size

Secret Keys Used (64 HEX):
Key1: bcfb8d1629964f571bea19eacdd1a9a8870622392094af2bc18e6942eb017b0f
Key 2: 0000000000000000000000000000000000000000000000000000000000001
Key 3: 0000000000000000000000000000000000000000000000000000000000002
Key 4: 0000000000000000000000000000000000000000000000000000000000004
Key 5: 0000000000000000000000000000000000000000000000000000000000008
Key 6. 70b91d006387740d0397095a33de361f4a631b3023f06c6a2e3c0cb2647f26bb
Key7: 008cf9209a7df04d2d2a990b08b8fec3 bad772b3f0c401fce5cf1db8cfebd599
Key8: bad772b3f0c401fce5cf1db8cfebd599008cf9209a7df04d2d2a990b08b8fec3
Key9: f878de38af18a9a1098bd8dc9f9c5e015d5ae4d5004fcd1bbf37a779bb1fce2b
Keya: 5d5ae4d5004fcd1bbf37a779bb1fce2b f878de38af18a9a1098bd8dc9f9c5e01

35

Appendix C.
Results of Statistical Randomness Tests on Panama

Length of output stream = 10,000,000 bits.
Length of output stream = 1,000,000 bits. (Sequence Complexity Test)
Number of streams = 10
Test
Key Key Key Key Key Key Key
1
2
3
4
5
6
7
Frequency.073 .705 .059 .580 .894 .071 .247
Binary Derivative.181 .375 .058 .599 .192 .272 .622
(1)
Binary Derivative.915 .487 .318 .625 .626 .956 .551
(2)
Change Point.964 .964 .964 .964 .964 .964 .964
Subblock b = 2.351 .895 .153 .855 .993 .089 .104
Subblock b = 3.248 .088 .153 .716 .302 .100 .412
Subblock b = 4.194 .015 .290 .675 .593 .339 .173
Subblock b = 5.621 .079 .681 .953 .623 .595 .411
Subblock b = 6.913 .124 .848 .787 .502 .491 .172
Subblock b = 7.590 .344 .001 .994 .030 .166 .474
Subblock b = 8.787 .022 .961 .459 .048 .468 .495
Subblock b = 9.776 .202 .406 .793 .587 .463 .812
Subblock b = 10.452 .805 .764 .963 .505 .484 .902
Subblock b = 11.533 .796 .791 .586 .546 .211 .654
Subblock b = 12.052 .117 .246 .689 .418 .589 .382
Subblock b = 13.654 .351 .447 .434 .861 .624 .955
Subblock b = 14.392 .028 .852 .908 .294 .215 .684
Subblock b = 15.554 .424 .253 .347 .580 .513 .140
Subblock b = 16.362 .554 .079 .353 .939 .606 .340
Subblock b = 17.596 .860 .216 .724 1.00 .724 .860
Subblock b = 18
.216 .596 .216 .724 .289 .379 .724
Subblock b = 19.860 1.00 .289 .052 .860 .216 .377
Subblock b = 20.860 .377 .596 .596 .860 .860 .157
Subblock b = 21.112 .860 .596 .596 .289 1.00 .058
Subblock b = 22.724 .480 .480 .880 .596 .480 .724
Subblock b = 23.596 .596 .596 .724 .860 .480 .377
Subblock b = 24
1.00 .377 .596 1.00 .860 .724 .724
Subblock b = 25.480 .480 .480 .860 .112 .216 .289
Subblock b = 26.377 .860 1.00 .596 .860 .724 .724
Subblock b = 27
1.00 .480 .860 .216 .724 .052 .860
Subblock b = 28.377 .157 .596 .112 .289 .377 .724
Subblock b = 29.724 .077 .112 .377 .596 .860 .724
Subblock b = 30.724 .860 .216 1.00 .052 .596 .860
Runs Distribution.773 .145 .547 .574 .509 .229 .994
Longest Run
28
28
28
28
29
28
28

Key
8
.009
.855

Key
9
.212
.460

Key
a
.134
.559

.597

.585

.700

.964
.028
.101
.257
.234
.265
.464
.392
.842
.403
.059
.389
.195
.447
.328
.128
.112
.377
.596
.596
.289
.724
.596
.377
.724
.596
.077
.377
.860
.860
.702
28

.964
.364
.077
.347
.610
.452
.706
.300
.626
.555
.577
.506
.461
.856
.676
.181
.596
.724
.480
1.00
.724
.860
.052
.289
.289
.480
.860
.289
.860
.480
.615
28

.964
.212
.468
.034
.838
.411
.688
.198
.029
.629
.067
.188
.299
.001
.502
.764
.596
.860
.724
.480
.289
1.00
.596
.596
.860
.289
.724
.377
.724
.480
.493
28
36

50787 50783 50774 50753 50776 50744 50773 50775 50789
Sequence
Complexity
Linear Complexity .500 .500 .834 .500 .166 .500 .500 .500 .974
LC profile – Jumps .814 .357 .791 .801 .074 .037 .467 .715 .498
LC Profile – Jump .419 .750 .186 .908 .921 .198 .077 .015 .745
Size
Sequence Complexity on 106 bits: Threshold value = 50,441 Mean value = 50172

50811

.500
.090
.584

Secret Keys Used (64 HEX):
Key1: bcfb8d1629964f571bea19eacdd1a9a8870622392094af2bc18e6942eb017b0f
Key 2: 0000000000000000000000000000000000000000000000000000000000001
Key 3: 0000000000000000000000000000000000000000000000000000000000002
Key 4: 0000000000000000000000000000000000000000000000000000000000004
Key 5: 0000000000000000000000000000000000000000000000000000000000008
Key 6. 70b91d006387740d0397095a33de361f4a631b3023f06c6a2e3c0cb2647f26bb
Key7: 008cf9209a7df04d2d2a990b08b8fec3 bad772b3f0c401fce5cf1db8cfebd599
Key8: bad772b3f0c401fce5cf1db8cfebd599008cf9209a7df04d2d2a990b08b8fec3
Key9: f878de38af18a9a1098bd8dc9f9c5e015d5ae4d5004fcd1bbf37a779bb1fce2b
Keya: 5d5ae4d5004fcd1bbf37a779bb1fce2b f878de38af18a9a1098bd8dc9f9c5e01

37

Appendix D.
Details of the Nonlinear Boolean Function in Panama

The nonlinear operation of Panama consists of three parts: a nonlinear combination ofwords, word rotations, and the XOR combination of these values. This results in every bitof the state being a function of 9 bits of the previous state. (Here we ignore the extra
XOR with buffer data). Due to the regular design, these Boolean functions all have thesame structure, which we may represent as follows (where addition is mod 2)
f(x)=x1 + x2x3 + x3 + x4 + x5x6 + x6 + x7 + x8x9 + x9 + 1
This Boolean function has been analysed by Walsh-Hadamard Transform (WHT) and all of
the possible linear correlations have been found. There are 64 linear functions with whichf(x) is uncorrelated. These 64 linear functions are exactly all those which include the terms
x1,x4, and x7. These linear functions all have weight 3 or more. All other linear functions
have zero correlation with f(x). Hence, f(x) is second order correlation immune, an important
fact not previously reported. The only non-zero WHT values are 64. The available linear bias
is then given by 64/512=2-3.

38