Analysis of Cipherunicorn-A
January 12, 2001

Executive Summary
This report presents the results of a limited time evaluation of the block cipher
Cipherunicorn-A.
The round function of Cipherunicorn-A is very complex, which makes it hardto analyse. We have outlined a few surprising properties of the round function.
First we discovered a differential which specifies 32 bits in the 64-bit outputs
with a probability orders of magnitudes higher than for a random function. Also,
it holds with a high probability that up to four rounds of the Feistel network
inside the round function can be ignored. Our findings are not sufficient toestablish cryptanalytic attacks faster than an exhaustive search for the key.
But it is felt that there are potential in the round function of Cipherunicorn-Afor cryptanalysis of a substantial number of rounds. However, we believe thatwith respect to the state-of-the-art a cryptanalytic attack on all 16 rounds ofCipherunicorn-A is likely not to exist or to be of a very high complexity.
Finally we mention that this report is the result of a limited time of review,and the analysis was performed without access to computer code implementing
the block cipher. A longer, concentrated analysis might reveal properties ofCipherunicorn-A which we were not able to detect.

1Analysis of Cipherunicorn-A

2

Contents
1 Structural features and characteristics

3

2 Differential cryptanalysis

4

3 Linear cryptanalysis

9

4 Other cryptanalysis

10

5 Survey of previous results

10

A Block Ciphers in General
12
A.1 Exhaustive key search . . . . . . . . . . . . . . . . . . . . . . . . 12
A.2 The matching ciphertext attack . . . . . . . . . . . . . . . . . . . 12
A.3 Differential cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . 13
A.4 Truncated differentials . . . . . . . . . . . . . . . . . . . . . . . . 13
A.5 Impossible differentials . . . . . . . . . . . . . . . . . . . . . . . . 14
A.6 Higher-order differentials . . . . . . . . . . . . . . . . . . . . . . . 14
A.7 Linear cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . 14
A.8 Mod n cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . 15
A.9 Related-key attacks . . . . . . . . . . . . . . . . . . . . . . . . . . 15
A.10 Interpolation attack . . . . . . . . . . . . . . . . . . . . . . . . . 16
A.11 Non-surjective attack . . . . . . . . . . . . . . . . . . . . . . . . . 16
A.12 Slide attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
A.13 Integral Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

Analysis of Cipherunicorn-A

1

3

Structural features and characteristics

Cipherunicorn-A is an iterated block cipher with 128-bit blocks and allows forthree different key sizes to be compliant with the AES [30]. The structureof Cipherunicorn-A is the well-known Feistel network and it runs in 16 rounds.
The Feistel round function consists itself of two smaller (64-bit) Feistel networks
whose outputs are combined by exclusive-ors to form the output of the round
function. The two smaller Feistel networks run in respectively ten and six
rounds together with several other components, e.g., multiplications by somefixed constants. We shall call these networks the main stream and the secondary
stream, respectively. It is claimed by the designers that each one of these two
smaller Feistel networks by themselves provides enough “shuffling” of the data.
It is shown in this report that this claim is not fully justified.
The complexity of the Feistel round function is relatively big comparedto other known Feistel ciphers. In Cipherunicorn-A there is a total of 16 T functions, which consists of an evaluation of four S-boxes on the same input
byte, six multiplications modulo 232 , four additions modulo 232 , two 32-bit rotations and three other bitwise logical operations. The four S-box evaluations
can be performed as one table lookup, if a table of size about 1 Kbytes is precomputed.

An unusual property
Next we report of an unusual property in the both the main stream and thesecondary stream of the round function. Consider the four rounds of the mainstream starting with a round after the second round containing T0 . Then it holds
that the 64-bit texts are unaltered with probability 2−16 . Consider Figure 3.4
in [2] and the following figure where an eight-tuple gives the values of the eightbytes in the inputs and outputs to one Feistel round in the round function ofT
Cipherunicorn-A. →k specifies which round function is considered and in which
direction the output of Tk is computed.
(x0 , x1 , x2 , x3 , x4 , x5 , x6 , x7 )→kT

(x0 , x1 , x2 , x3 , y4 , y5 , y6 , y7 )(z0 , z1 , z2 , z3 , y4 , y5 , y6 , y7 )T`←(x0 , x1 , x2 , x3 , y4 , y5 , y6 , y7 )(z0 , z1 , z2 , z3 , y4 , y5 , y6 , y7 )Tm→(z0 , z1 , z2 , z3 , x4 , x5 , x6 , x7 )(x0 , x1 , x2 , x3 , x4 , x5 , x6 , x7 )Tn(z0 , z1 , z2 , z3 , x4 , x5 , x6 , x7 ).

←As seen the ciphertext after four rounds equals the plaintext. The fact follows
from the observations that if in the first and third rounds the inputs to Tk and
Tm are equal, and if in the second and fourth rounds the inputs to T` and Tn are
equal, then the quantities output from the round functions in every second roundcancel out, and the output of the four rounds equal the input of the four rounds.
These two events have a probability of about 2−8 each. This is an approximation
only, since the events in the four rounds are not independent. Thus, for anyof such four rounds, there are many fixed points, approximately 248 . Since theAnalysis of Cipherunicorn-A

4

S-boxes were designed not to have any fixed points, this observation could be incontradiction to the design principles of the designers. Note that for a general
64-bit Feistel cipher the above phenomenon would hold with a probability of
only 2−64 .
In the secondary stream a similar phenomenon holds for the last three rounds
in the six-round Feistel construction. Assume the byte input to T0 in the thirdlast round equals the byte input to T1 in the last round. In this case theoutputs of the secondary stream which is exclusive-ored to the outputs of themain stream come from the first three rounds in the secondary stream. Thus
with probability 2−8 the main output from the secondary stream is computedin only three Feistel rounds using T0 in every round.

2

Differential cryptanalysis

In this section we evaluate Cipherunicorn-A with respect to differential cryptanalysis. A difference of two bit-strings of equal lengths is defined via theexclusive-or operation. The Feistel round function consists itself of two smaller(64-bit) Feistel networks with respectively ten and six rounds.
In the following we examine the different components of the Feistel round
function with respect to differential cryptanalysis.
The addition of subkeys modulo 232 is not a linear operation with respect
to the differences defined. However it is well-known that differences of small
Hamming weights stay differences of small Hamming weights with a high probability through modular additions [20]. For example, two texts different in one
bit only will remain different in only one bit after a modular addition with aprobability of 1/2 in general, and with probability 1 if the difference is in themost significant bit. Let us examine this in more detail. Consider two 32-bit
words A and B and a subkey K. Integer addition of a constant word K to words
A and B which only differ in few bits does not necessarily lead to an increaseof bit differences in the sums A + K and B + K. This may be illustrated by
the following special cases: Suppose the words A and B only differ in the mostsignificant bit. Then it follows that A + K and B + K also differ in only themost significant bit. Suppose next that the words A and B only differ in thei-th bit, i < 31. Then it can be shown that with probability 12 , A + K and
B + K also differ in only the i-th bit. If we use the binary representation ofwords, i.e., A = aw−1 2w−1 + · · · + a1 2 + a0 , and similarly for B and K, thebinary representation of the sum Z = A + K may be obtained by the formulaezj = aj + kj + σj−1 and σj = aj kj + aj σj−1 + kj σj−1 ,(1)where σj−1 denotes the carry bit and σ−1 = 0 (cf. [32]). Using these formulae
one sees that A + K and B + K with probability 14 differ in exactly two (consecutive) bits. Suppose now the words A and B already differ in exactly twoconsecutive bits. Then again using the formulae (1) one can see that with probability 41 , A + K and B + K differ in exactly one bit and that with probability
3
8 , A + K and B + K differ in exactly two (not necessarily consecutive) bits.

Analysis of Cipherunicorn-A

5

Thus with probability 58 the words A + K and B + K differ again in at most
two bits if A and B differ in two consecutive bits. Using the formulae (1) one
could discuss relations between integer addition and bit differences in a moregeneral setting. However the above suggests that addition of subkeys can only
moderately contribute to an avalanche effect of bit differences. Therefore, let
us first replace the modular addition of the keys by an exclusive-or of the keys.
The A3 function in the main stream is linear with respect to the exclusiveor operation. Therefore, we shall ignore the A3 function in the search for gooddifferentials. For any differential found by ignoring the A3 function one caneasily compute the differential input difference before the A3 function.
We use the following notationG(x0 , x1 , x2 , x3 ) → (y0 , y1 , y2 , y3 )if texts of differences (x0 , x1 , x2 , x3 ) can result texts of differences (y0 , y1 , y2 , y3 )after one application of a function G, where each xi and yi are byte values.
Let ⊗ denote a multiplication of one of the two constants modulo 232 used in
Cipherunicorn-A. Then the following differentials hold with probability one.
(a, 0, 0, 0)→⊗(A, 0, 0, 0)(a, b, 0, 0)⊗→(A, B, 0, 0)(a, b, c, 0)⊗(A, B, C, 0).

→Here a, b, c, A, B, and C denote some nonzero values of a byte. In other words,
if a pair of texts are equal in the lower s bytes, 1 ≤ s ≤ 4, then the texts after
a multipication of a constant modulo 232 have the same property. There is aneven stronger result, namely if a pair of texts are equal in the lower s bits, then
the texts after a multipication of a constant modulo 232 have the same property.
In particular, the following characteristic (where hx is hexadecimal notation)⊗(80x , 0, 0, 0) → (80x , 0, 0, 0)(2)holds with probability one. In plain words, two texts different in only themost significant bit are also different in only the most significant bit after themultiplication of an odd constant modulo 232 .
Next let us consider the smaller Feistel rounds inside the Cipherunicorn-A
Feistel round function.
Let us first consider the main stream. This is a ten-round Feistel network,
consisting of first a modular addition of two subkeys to the round input, thenone application of the A3 function, then two Feistel rounds using the nonlinear
function T0 , then two Feistel rounds using the nonlinear function T1 , then two
Feistel rounds using the nonlinear function T2 , then two Feistel rounds using thenonlinear function T3 , and finally two Feistel rounds using the nonlinear function
Tk , where k is a two-bit value specified by data in the secondary stream.
By(x0 , x1 , x2 , x3 , x4 , x5 , x6 , x7 )T→k(y0 , y1 , y2 , y3 , y4 , y5 , y6 , y7 )Analysis of Cipherunicorn-A

6

we shall denote one round of the Feistel network (with 64-bit inputs and outputs)in Cipherunicorn-A, where Tk is used as the nonlinear function. Also, when
considering two rounds of the Feistel network we shall denote the differentials
as follows(x0 , x1 , x2 , x3 , x4 , x5 , x6 , x7 )→kT(y0 , y1 , y2 , y3 , y4 , y5 , y6 , y7 )(x0 , x1 , x2 , x3 , x4 , x5 , x6 , x7 )Tk(z0 , z1 , z2 , z3 , z4 , z5 , z6 , z7 ),←so that the differential is depicted in analogue to the figure of [1].
Also, when considering two consecutive rounds with T0 as the nonlinear
function we shall assume that the multiplications of the constants are included,
cf. [1].
Then the following general types of differentials with two rounds are possible(a, 0, c, d, e, 0, g, h) →1

T(a, 0, c, d, e, 0, g, h)

T1(a, 0, c, d, e, 0, g, h)(a, 0, c, d, e, 0, g, h) ←T(a, b, 0, d, e, f, 0, h) →2 (a, b, 0, d, e, f, 0, h)T(a, b, 0, d, e, f, 0, h) ←2 (a, b, 0, d, e, f, 0, h)T(a, b, c, 0, e, f, g, 0)→3(a, b, c, 0, e, f, g, 0)

T3(a, b, c, 0, e, f, g, 0)← (a, b, c, 0, e, f, g, 0).

All these two-round differentials have probability one, where a, b, c, d, e, f, g, andh denote arbitrary byte values. Also, the following differentials over six rounds
have probability one.
T(a, 0, 0, 0, b, 0, 0, 0)→1 (a, 0, 0, 0, b, 0, 0, 0)(a, 0, 0, 0, b, 0, 0, 0)←1(a, 0, 0, 0, b, 0, 0, 0)

T2→ (a, 0, 0, 0, b, 0, 0, 0)(a, 0, 0, 0, b, 0, 0, 0)←2(a, 0, 0, 0, b, 0, 0, 0)

T3→ (a, 0, 0, 0, b, 0, 0, 0)(a, 0, 0, 0, b, 0, 0, 0)

←3

T

T

T

(a, 0, 0, 0, b, 0, 0, 0)(a, 0, 0, 0, b, 0, 0, 0)(a, 0, 0, 0, b, 0, 0, 0),

where a and b are any byte values. At the end of the main stream in the round
function of Cipherunicorn-A two rounds of encryption is performed using Tk in
the smaller Feistel rounds, where k is specified by the secondary stream. Clearly,
the two-round differentialT(a, 0, 0, 0, b, 0, 0, 0)→k (a, 0, 0, 0, b, 0, 0, 0)(a, 0, 0, 0, b, 0, 0, 0)←kT(a, 0, 0, 0, b, 0, 0, 0),Analysis of Cipherunicorn-A

7holds with probability (1/4 ∗ 3/4)2 ' 1/32. Note that the probability that k has
one of the values 1, 2, or 3 in one round for one text is 3/4, and the probability
that for the other text one gets the same value of k is 1/4.
The above differentials can be concatenated and the following differential
over eight (8) rounds holds with probability 1/32.
T(a, 0, 0, 0, b, 0, 0, 0)→1(a, 0, 0, 0, b, 0, 0, 0)

T1← (a, 0, 0, 0, b, 0, 0, 0)(a, 0, 0, 0, b, 0, 0, 0)→2(a, 0, 0, 0, b, 0, 0, 0)

T2← (a, 0, 0, 0, b, 0, 0, 0)(a, 0, 0, 0, b, 0, 0, 0)→3(a, 0, 0, 0, b, 0, 0, 0)

T3← (a, 0, 0, 0, b, 0, 0, 0)(a, 0, 0, 0, b, 0, 0, 0)→k(a, 0, 0, 0, b, 0, 0, 0)

Tk

T

T

T

(a, 0, 0, 0, b, 0, 0, 0)(a, 0, 0, 0, b, 0, 0, 0)(a, 0, 0, 0, b, 0, 0, 0)(a, 0, 0, 0, b, 0, 0, 0)← (a, 0, 0, 0, b, 0, 0, 0),

where a and b are any byte values.
Next we consider the case where T0 is used as the nonlinear function. Consider the following two-round differential.
(80x , 0, 0, 0, a, b, c, d) →0

T(80x , 0, 0, 0, 0, 0, 0, 0)T0(80x , 0, 0, 0, 0, 0, 0, 0)(80x , 0, 0, 0, 0, 0, 0, 0) ←of probability 2−8 . To see why this differential has probability 2−8 note that the
inputs to the function T0 in the first round are of difference 80x because of (2).
For any values of these two 8-bit inputs, the corresponding 32-bit outputs can be
determined and therefore also the exclusive-or of the two 32-bit outputs. Thus,
for any two 8-bit inputs to T0 one can compute the values of a, b, c, and d, suchthat the differential above has probability one in the first round. The differential
has probability one in the second round, since there will be equal inputs to thefunction T0 because of (2). Clearly, one cannot know with certainty the inputs
to T0 in the first round, since in the Feistel round function the initial operationis the addition of some unknown keys. However, one can guess one of the 8-bit
inputs with probability 2−8 , the other 8-bit input can then be easily calculated.
By combining the above results we find that the following differential overten rounds of the main stream holds with probability 2−13 .
(80x , 0, 0, 0, a, b, c, d)→0T(80x , 0, 0, 0, 0, 0, 0, 0)(80x , 0, 0, 0, 0, 0, 0, 0)T0←(80x , 0, 0, 0, 0, 0, 0, 0)(80x , 0, 0, 0, 0, 0, 0, 0)T1→(80x , 0, 0, 0, 0, 0, 0, 0)(80x , 0, 0, 0, 0, 0, 0, 0)T1←(80x , 0, 0, 0, 0, 0, 0, 0)(80x , 0, 0, 0, 0, 0, 0, 0)T2(80x , 0, 0, 0, 0, 0, 0, 0)→Analysis of Cipherunicorn-A

8
T(80x , 0, 0, 0, 0, 0, 0, 0)←2 (80x , 0, 0, 0, 0, 0, 0, 0)(80x , 0, 0, 0, 0, 0, 0, 0)→3 (80x , 0, 0, 0, 0, 0, 0, 0)(80x , 0, 0, 0, 0, 0, 0, 0)←3 (80x , 0, 0, 0, 0, 0, 0, 0)(80x , 0, 0, 0, 0, 0, 0, 0)→k (80x , 0, 0, 0, 0, 0, 0, 0)(80x , 0, 0, 0, 0, 0, 0, 0)←k (80x , 0, 0, 0, 0, 0, 0, 0),

T

T

T

T

Clearly, this differential holds also if we incorporate the A3 function, since thisis linear, cf. the above discussion. The probability of the differential throughthe complete main stream depends on the Hamming weights of the byte values
a, b, c, and d. Thus, according to the above considerations, one could optimise
the probability by finding values of a, b, c, of d of minimum Hamming weights.
In the best cases each of these are of Hamming weight 1, in which case theprobability drops by a factor of 2−4 .
Let us next consider the secondary stream. This is a six-round Feistel network, consisting of first a modular addition of two subkeys to the round input,
then four Feistel rounds using the nonlinear function T0 , and finally two Feistelrounds using the nonlinear function T1 . The left half of the secondary stream
is exclusive-ored to both output halves of the main stream. The right half ofthe secondary stream is used to specify two indices for a choice of a Tk functionin the main stream, thus only four bits of the right half is used. This immediately gives rise to a differential for the whole round function but where theinitial key additions are replaced with exclusive-ors. It holds with probability
2−13 that two inputs of difference (80x , 0, 0, 0, a, b, c, d) where a, b, c, d have someprecomputed fixed values, result in texts of difference (e0 , f, g, h, e, f, g, h) wheree and e0 differ only in the most significant bits. Thus, this still gives 32 bitsof information about the output differences at the cost of a probability of only
2−13 . This follows from the fact that the same 32 bits of the outputs of the secondary stream are exclusive-ored to both 32-bit halves in the output of the mainstream. We did assume that the keys were added bitwise modulo 2 instead ofmodulo 232 in the main stream. However, as discussed above, if the differential
has a low Hamming weight in the input differences this will only decrease theoverall probability with a small factor.
Moreover, there are nontrivial cases for the secondary stream. Consider thefollowing six-round differential.
(0, 0, 0, 0, a, b, c, d) →0

T(0, 0, 0, 0, a, b, c, d)T0(0, 0, 0, 0, 0, e, f, g) ←(0, 0, 0, 0, 0, e, f, g)

T0(0, 0, 0, 0, 0, e, f, g) →(0, 0, 0, 0, 0, e, f, g)

T0(l, m, n, p, h, i, j, k) ←(0, 0, 0, 0, h, i, j, k)

T1(l, m, n, p, h, i, j, k) →(l, m, n, p, q, r, s, t)

T1(l, m, n, p, q, r, s, t)(0, 0, 0, 0, q, r, s, t) ←

Analysis of Cipherunicorn-A

9The probability in the first round is one, since the inputs to T0 are equal. In thesecond round after the multiplication with the constant, there is a probability of
about 2−8 that the inputs to T0 are equal. Consequently, the probability in thethird round is one again. The values in the differential follows now from the factthat if the pair of bytes input to T0 in the fourth round and the pair of bytes
input to T1 in the sixth round are equal, then differences cancel out and theleft halves of the secondary stream are equal. If we let α and β be the two byte
values input to T0 in the fourth round, then the probability that the inputs to T1
in the sixth round are α, β or β, α is in total 2−15 . Thus, in total this six-rounddifferential has a probability of 2−23 . Note that the right halves are not specified
any further in this differential. Only four bits are used of the right halves, andin this case it can be assumed that these bits are random. This differential could
have some good applications in a differential for the whole round function, since
the contribution from the secondary stream with respect to differences amountto the four bits used to select two times one of four functions in the main stream.
Finally, one should try to look for differentials which go through both themain stream and the secondary stream with a high probability. Although wehave not been able to make much progress on this in the time frame set forthis work, it is believed that there exist such differentials of high probabilities.
However, it is also believed that the probabilities for such differentials are low
enough, such that attacks on 16 rounds of Cipherunicorn-A will be of very highcomplexity, if possible at all.

3

Linear cryptanalysis

In this section we consider attacks based on linear cryptanalysis. In the following
we examine the different components of the Feistel round function with respect
to linear cryptanalysis.
First we note that the A3 function helps complicate linear attacks, since each
output is a sum of three input bits. Thus in linear characteristics considering
one or a few bits, A3 has the effect of involving additional bits which complicate
analysis.
The addition of subkeys modulo 232 is not a linear operation respect to the
exclusive-or operation. However it is well-known that there is a linear relationof maximum bias in the least significant bits.
We use the following notationG(x0 , x1 , x2 , x3 ) → (y0 , y1 , y2 , y3 )to denote that texts with bit masks (x0 , x1 , x2 , x3 ) are correlated to outputsof the function G with bit masks (y0 , y1 , y2 , y3 ). As before, let ⊗ be denote a
multiplication of one of the two constants modulo 232 used in Cipherunicorn-A.
Then the following linear characteristic holds with probability one.
⊗(0, 0, 0, 0x1) →(0, 0, 0, 0x1)

Analysis of Cipherunicorn-A

10

Thus, there is a linear approximation of the least significant bits of maximum
bias for both modular addition and modular multiplication modulo 232 .
The S-boxes used in the Tk -functions are all constructed from the inverse
function over GF (28 ), which is known to be highly nonlinear [27].
The only approach we have been able to find is the traditional one of tracing
bits round per round and combining these into relations over several rounds. In
the round function of Cipherunicorn-A this approach would require to incorporate at least the output of eight or more S-boxes per round. Since the S-boxes
are highly nonlinear this approach is not likely to enable attacks on more thana few rounds of Cipherunicorn-A and far less than the specified 16 rounds.

4

Other cryptanalysis

In this section we consider other attacks. First of all, there are trivial attacks
which apply to all block ciphers. An exhaustive key search will take 2k operations to succeed, where k is the key size. Also, the “matching ciphertext attack”
applies in ECB and CBC mode, but requires about 2n/2 ciphertext blocks tosucceed with good probability, where n is the block size. With n = 128 asin Cipherunicorn-A, 264 ciphertext blocks are required after which an attacker
would be able to deduce information about the plaintext blocks.
Higher order differentials. This attack applies to ciphers which uses nonlinear
components of a low algebraic degree. Cipherunicorn-A uses S-boxes of a highnonlinear order in a relatively complex round function, and the probability thata higher order differential attack could be applicable is very small.
The slide attacks, the integral attacks, the non-surjective attacks and the“mod n” attacks do not seem applicable to Cipherunicorn-A .
The interpolation attacks apply to ciphers which use simple mathematical
functions only. Cipherunicorn-A uses mathematical functions in the S-boxes,
however the affine mappings in the S-boxes together with the A3 function seems
to have a good effect in thwarting the interpolation attacks.
The key-schedule of Cipherunicorn-A does not seem to allow for related-key
attacks. Since the round keys are encrypted in relatively many rounds using
both modular multiplications and S-box lookups, it is unlikely that any easily
identified weak keys or pairs of related keys exist.

5

Survey of previous results

The only previous results on Cipherunicorn-A that we are aware of are thoseof the designers themselves [2]. In the self evaluation report the designers
spend most of the time discussing statistical tests of the round function of
Cipherunicorn-A which were performed. However it is widely believed thatsuch round function tests are not adequate as a tool for measuring the securityof the full cipher. Resistance against statistical tests for the full cipher is on theother hand a necessary condition for a secure cipher although not a sufficientAnalysis of Cipherunicorn-A

11

condition. It is relatively easy to construct ciphers which pass these tests but
for which there are efficient short-cut attacks. The comparison with the five
AES finalist block ciphers is not fair. As an example, it is well-known that the
Rijndael round function does not achieve full diffusion in one round, but theconstruction guarantees that this is achieved after two rounds.

Analysis of Cipherunicorn-A

A

12

Block Ciphers in GeneralIn the following we give a compressed overview of the state-of-the-art of blockcipher cryptanalysis, and outline the following known attacks.
1. Exhaustive Key Search
2. Matching Ciphertext Attacks
3. Differential Cryptanalysis
4. Truncated Differential Attacks
5. Higher-order Differential Attacks
6. Linear Cryptanalysis
7. Related-key Attacks
8. Non-surjective Attacks
9. Interpolation Attacks
10. Mod-n Attacks
11. Slide Attacks
12. Integral Attacks

A.1

Exhaustive key searchThis attack needs only a few known plaintext-ciphertext pairs. An attacker
simply tries all keys, one by one, and checks whether the given plaintext encrypts
to the given ciphertext. For a block cipher with a k-bit key and n-bit blocks thenumber of pairs of texts needed to determine the key uniquely is approximately
dk/ne. Also, if the plaintext space is redundant, e.g., consists of English or
Japanese text, the attack will work if only some ciphertext blocks is available.
The number of ciphertext blocks needed depends on the redundancy of thelanguage.

A.2

The matching ciphertext attack

The matching ciphertext attack is based on the fact that for block ciphers of m
bits used in the modes of operations for the DES [29] after the encryption of
2m/2 blocks, equal ciphertext blocks can be expected and information is leaked
about the plaintexts [7, 16, 26].

Analysis of Cipherunicorn-A

A.3

13

Differential cryptanalysis

The most well-known and general method of analysing conventional cryptosystems today is differential cryptanalysis, published by Biham and Shamir in 1990.
Differential cryptanalysis is universal in the sense that it can be used against
any cryptographic mapping which is constructed from iterating a fixed round
function. One defines a difference between two bit strings, X and X 0 of equal
length as∆X = X ⊗ (X 0 )−1 ,(3)where ⊗ is the group operation on the group of bit strings used to combine
the key with the text input in the round function and where (X)−1 is theinverse element of X with respect to ⊗. The idea behind this is, that thedifferences between the texts before and after the key is combined are equal,i.e., the difference is independent of the key. To see this, note that(X ⊗ K) ⊗ (X 0 ⊗ K)−1 = X ⊗ K ⊗ K −1 ⊗ X 0−1 = X ⊗ (X 0 )−1 = ∆X.
In a differential attack one exploits that for certain input differences the distribution of output differences of the non-linear components is non-uniform.
Definition 1 An s-round characteristic is a series of differences defined as ans + 1-tuple {α0 , α1 , . . . , αs }, where ∆P = α0 , ∆Ci = αi for 1 ≤ i ≤ s.
Here ∆P is the difference in the plaintexts and ∆Ci is the difference in the
ciphertexts after i rounds of encryption. Thus, the characteristics are lists of
expected differences in the intermediate ciphertexts for an encryption of a pairof plaintexts. In essence one specifies a characteristic for a number of rounds
and searches for the correct key in the remaining few rounds. In some attacks
it is not necessary to predict the values α1 , . . . , αs−1 in a characteristic. The
pair (α0 , αs ) is called a differential. The complexity of a differential attack isapproximately the inverse of the probability of the characteristic or differential
used in the attack.

A.4

Truncated differentials

For some ciphers it is possible and advantageous to predict only the values ofparts of the differences after each round of the cipher. The notion of truncateddifferentials was introduced by Knudsen [18]:Definition 2 A differential that predicts only parts of an n-bit value is calleda truncated differential. More formally, let (a, b) be an i-round differential. If
a0 is a subsequence of a and b0 is a subsequence of b, then (a0 , b0 ) is called an
i-round truncated differential.
A truncated differential can be seen as a collection of differentials. As an example, consider an n-bit block cipher and the truncated differential (a0 , b), wherea0 specifies the least n0 < n significant bits of the plaintext difference and b
specifies the ciphertext difference of length n. This differential is a collection
0of all 2n−n differentials (a, b), where a is any value, which truncated to the n0
least significant bits is a0 .

Analysis of Cipherunicorn-A

A.5

14

Impossible differentials

A special type of differentials are those of probability zero. The attack was first
applied to the cipher DEAL [19] and later to Skipjack [4]. The main idea isto specify a differential of probability zero over some number of rounds in theattacked cipher. Then by guessing some keys in the rounds not covered by thedifferential one can discard a wrong value of the key if it would enable the cipher
to take on the differences given in the differential.

A.6

Higher-order differentials

An sth-order differential is defined recursively as a (conventional) differentialof the function specifying an (s − 1)st order differential. In order words, an
sth order differential consists of a collection of 2s texts of certain pairwise,predetermined differences. We refer to [22, 18] for a more precise definition ofhigher order differentials.
In most cases one considers differences induced by the exclusive-or operationand the field of characteristic 2. The nonlinear order of a function f : GF (2n ) →GF (2n ) is defined as follows. Let the output bits yj be expressed as multivariate
polynomials qj (x) ∈ GF (2)[x1 , . . . , xn ], where x1 , . . . , xn are the input bits. The
nonlinear order of f is then defined to be the minimum total degree of any linear
combination of these polynomials. The higher order differential attacks exploit
the following result.
Corollary 1 Let f : GF (2n ) → GF (2n ) be a function of nonlinear order d.
Then any dth order differential is a constant. Consequently, any (d + 1)st orderdifferential is zero.
The boomerang attack [33] can be seen as a special type of a second-orderdifferential attack. This variant applies particularly well to ciphers for which
one particular (first-order) differential applies well to one half of the cipher, andwhere another particular (first-order) differential applies well to the other halfof the cipher.

A.7

Linear cryptanalysis

Linear cryptanalysis was proposed by Matsui in 1993 [23]. A preliminary versionof the attack on FEAL was described in 1992 [25]. Linear cryptanalysis [23] isa known plaintext attack in which the attacker exploits linear approximationsof some bits of the plaintext, some bits of the ciphertext and some bits of thesecret key. In the attack on the DES (or on DES-like iterated ciphers) the linear
approximations are obtained by combining approximations for each round under
the assumption of independent round keys. The attacker hopes in this way tofind an expression(P · α) ⊕ (C · β) = (K · γ)(4)Analysis of Cipherunicorn-A

15

which holds with probability pL 6= 12 over all keys [23], such that |pL − 12 |, called
the bias, is maximal. In (4) P, C, α, β, γ are m-bit strings and ‘·’ denotes thedot product. The bit strings α, β, γ are called masks.
Definition 3 An s-round linear characteristic is a series of masks defined asan (s + 1)-tuple {α0 , α1 , . . . , αs }, where α0 is the mask of the plaintexts and αiis the mask of the ciphertexts after i rounds of encryption for 1 ≤ i ≤ s.
As for differential cryptanalysis one specifies a linear characteristics for a numberof rounds and searches for the keys in the remaining rounds, we refer to [23] formore details. A linear attack needs approximately about b−2 known plaintexts
to succeed, where b is the bias of the linear characteristic used.
Also, the concepts of linear hulls, the analogue to differentials as opposed tocharacteristics in differentials cryptanalysis, has been defined in [28].
Finally, in [24] it has been shown that if one defines the quantity q = (2p−1)2where p is the probability of a linear characteristic or hull, then when combining
several linear characteristics one can multiply their q values to get the q-valueof the combination. Sometimes the q values are referred to as the “linear probability”, which is somewhat misleading, but nevertheless seems to be widely
used.

A.8

Mod n cryptanalysis

In [14] a generalisation of the linear attacks is considered. This attack is applicable to ciphers for which some words (in some intermediate ciphertext) are biased
modulo n, where n typically is a small integer. It has been shown that cipherswhich uses only bitwise rotations and additions modulo 232 are vulnerable tothese kinds of attacks.

A.9

Related-key attacks

There are several variants of this attack depending on how powerful the attacker
is assumed to be.
1. Attacker gets encryptions under one key.
2. Attacker gets encryptions under several keys.
(a) Known relation between keys.
(b) Chosen relation between keys.
Knudsen used the methods of 1 by giving a chosen plaintext attack of the firstkind on LOKI’91 [15], reducing an exhaustive key search by almost a factor offour. The concept “related-key attack” was introduced by Biham [3], who also
introduced the attack scenarios of 2, where the encryptions under several keys
are requested. Knudsen later described a related key attack on SAFER K [17]and Kelsey, Schneier, and Wagner [13] applied the related key attacks to a wide
range of block ciphers. It may be argued that the attacks with a chosen relation

Analysis of Cipherunicorn-A

16

between the keys are unrealistic. The attacker need to get encryptions under
several keys, in some attacks even with chosen plaintexts. However there exist
realistic settings, in which an attacker may succeed to obtain such encryptions.
Also, there exists quite efficient methods to preclude the related key attacks[13, 11].

A.10

Interpolation attack

In [12] Jakobsen and Knudsen introduced the interpolation attack on blockciphers. The attack is based on the following well-known formula. Let R be afield. Given 2n elements x1 , . . . , xn , y1 , . . . , yn ∈ R, where the xi s are distinct.
DefinenXYx − xjf (x) =yi.
(5)xi − xj
i=1
1≤j≤n,j6=i

f (x) is the only polynomial over R of degree at most n − 1 such that f (xi ) = yi
for i = 1, . . . , n. Equation (5) is known as the Lagrange interpolation formula(see e.g.,[6, page 185]). In the interpolation attack an attacker constructs polynomials using pairs of plaintexts and ciphertexts. This is particularly easy if
the components in the cipher can be expressed as easily described mathematical functions. The idea of the attack is, that if the constructed polynomials
have a small degree, only few plaintexts and their corresponding ciphertexts arenecessary to solve for the (key-dependent) coefficients of the polynomial, e.g.,using Lagrange’s interpolation. To recover key bits one expresses the ciphertext
before the last round as a polynomial of the plaintext.

A.11

Non-surjective attack

In [31] Rijmen-Preneel-De Win described the non-surjective attack on iterated
ciphers. It is applicable to Feistel ciphers where the round function is not surjective and therefore statistical attacks become possible. In a Feistel cipher one cancompute the exclusive-or of all outputs of the round functions from the plaintexts and the corresponding ciphertexts. Thus, if the round functions are notsurjective this gives information about intermediate values in the encryptions,which can be used to get information about the secret keys.

A.12

Slide attacks

In [5] the “slide attacks” were introduced, based on earlier work in [3, 15]. In
particular it was shown that iterated ciphers with identical round functions,that is, equal structures plus equal subkeys in the rounds, are susceptible toslide attacks. Let Fr ◦ Fr−1 ◦ · · · ◦ F1 denote an r-round iterated cipher, where
all Fi s are identical. The attacker tries to find pairs of plaintext P, P ∗ andtheir corresponding ciphertexts C, C ∗ , such that F1 (P ) = P ∗ and Fr (C) = C ∗ .
Subsequently, an attacker has twice both the inputs and outputs of one roundof the cipher. If the round function is simple enough, this can lead to very

Analysis of Cipherunicorn-A

17

efficient attacks. To find such pairs of texts, one can in the worst case apply thebirthday paradox, such that one such pair is expected from a collection of 2n/2
texts, where n is the block size.

A.13

Integral Attacks

These attacks are sometimes referred to as the “Square attack”, since it was
first applied to the block cipher Square [9, 8]. The attack on Square slightly
modified also applies to the block ciphers Crypton and Rijndael [10].
In [21] these attacks are generalised under the name of “integral cryptanalysis”. In differential attacks one considers differences of texts, in integral cryptanalysis one considers sums of texts. In ciphers where all nonlinear functions
are bijective, it is sometimes possible to predict a sum of texts, even in the cases
where differential attacks are not applicable. The main observations are that ina collection of texts which in a particular word take all values exactly equally
many times, the value of the words after a bijective function also take all values
exactly equally many times. Also, assume that s words have this property andthat in the cipher a linear combination of the s words are computed (with respect to the group operation considered). Then it is possible to determine also
the sum of all linear combinations in a collection of texts. This attack is still
today the best attack reported on Rijndael which has been the selected for the
Advanced Encryption Standard.

References[1] NEC Corporation. Cryptographic Techniques Specifications: CipherunicornA.
[2] NEC Corporation. Self Evaluation Report: Cipherunicorn-A.
[3] E. Biham. New types of cryptanalytic attacks using related keys. In T. Helleseth, editor, Advances in Cryptology: EUROCRYPT’93, LNCS 765, pages
398–409. Springer Verlag, 1993.
[4] E. Biham, A. Biryukov, and A. Shamir. Cryptanalysis of Skipjack reduced
to 31 rounds using impossible differentials. In J. Stern, editor, Advances in
Cryptology: EUROCRYPT’99, LNCS 1592, pages 12–23. Springer Verlag,
1999.
[5] A. Biryukov and D. Wagner. Slide attacks. In L. R. Knudsen, editor, Fast
Software Encryption, Sixth International Workshop, Rome, Italy, March
1999, LNCS 1636, pages 245–259. Springer Verlag, 1999.
[6] P.M. Cohn. Algebra, Volume 1. John Wiley & Sons, 1982.
[7] D. Coppersmith, D.B. Johnson, and S.M. Matyas. Triple DES cipher blockchaining with output feedback masking. Technical Report RC 20591, IBM,
October 1996. Presented at the rump session of CRYPTO’96.

Analysis of Cipherunicorn-A

18[8] J. Daemen, L. Knudsen, and V. Rijmen. Linear frameworks for block ciphers.
Design, Codes, and Cryptography. To appear.
[9] J. Daemen, L. Knudsen, and V. Rijmen. The block cipher Square. In
E. Biham, editor, Fast Software Encryption, Fourth International Workshop,
Haifa, Israel, January 1997, LNCS 1267, pages 149–165. Springer Verlag,
1997.
[10] J. Daemen and V .Rijmen. AES proposal: Rijndael. Submitted
as an AES Candidate Algorithm. Description available from NIST, see
http://www.nist.gov/aes.
[11] I.B. Damgård and L.R. Knudsen. Two-key triple encryption. The Journalof Cryptology, 11(3):209–218, 1998.
[12] T. Jakobsen and L. Knudsen. The interpolation attack on block ciphers. In
E. Biham, editor, Fast Software Encryption, Fourth International Workshop,
Haifa, Israel, January 1997, LNCS 1267, pages 28–40. Springer Verlag, 1997.
[13] J. Kelsey, B. Schneier, and D. Wagner. Key-schedule cryptanalysis of IDEA,
G-DES, GOST, SAFER, and triple-DES. In Neal Koblitz, editor, Advancesin Cryptology: CRYPTO’96, LNCS 1109, pages 237–251. Springer Verlag,
1996.
[14] J. Kelsey, B. Schneier, and D. Wagner. Mod n cryptanalysis, with applications against RC5P and M6. In L. Knudsen, editor, Fast Software Encryption, Sixth International Workshop, Rome, Italy, March 1999, LNCS 1636,
pages 139–155. Springer Verlag, 1999.
[15] L.R. Knudsen. Cryptanalysis of LOKI’91. In J. Seberry and Y. Zheng,
editors, Advances in Cryptology, AusCrypt 92, LNCS 718, pages 196–208.
Springer Verlag, 1993.
[16] L.R. Knudsen. Block Ciphers – Analysis, Design and Applications. PhD
thesis, Aarhus University, Denmark, 1994.
[17] L.R. Knudsen. A key-schedule weakness in SAFER K-64. In Don Coppersmith, editor, Advances in Cryptology - CRYPTO’95, LNCS 963, pages
274–286. Springer Verlag, 1995.
[18] L.R. Knudsen. Truncated and higher order differentials. In B. Preneel,
editor, Fast Software Encryption - Second International Workshop, Leuven,
Belgium, LNCS 1008, pages 196–211. Springer Verlag, 1995.
[19] L.R. Knudsen. DEAL - a 128-bit block cipher. Technical Report 151,
Department of Informatics,University of Bergen, Norway, February 1998.
Submitted as an AES candidate by Richard Outerbridge.
[20] L.R. Knudsen and W. Meier. Improved differential attack on RC5. In Neal
Koblitz, editor, Advances in Cryptology - CRYPTO’96, LNCS 1109, pages
216–228. Springer Verlag, 1996.

Analysis of Cipherunicorn-A

19[21] L.R. Knudsen and D. Wagner. Integral cryptanalysis. In preparation, 2001.
[22] X. Lai. Higher order derivatives and differential cryptanalysis. In R. Blahut,
editor, Communication and Cryptography, Two Sides of One Tapestry.
Kluwer Academic Publishers, 1994. ISBN 0-7923-9469-0.
[23] M. Matsui. Linear cryptanalysis method for DES cipher. In T. Helleseth,editor, Advances in Cryptology - EUROCRYPT’93, LNCS 765, pages 386–
397. Springer Verlag, 1993.
[24] M. Matsui. New structure of block ciphers with provable security against
differential and linear cryptanalysis. In D. Gollman, editor, Fast Software
Encryption, Third International Workshop, Cambridge, UK, February 1996,
LNCS 1039, pages 205–218. Springer Verlag, 1996.
[25] M. Matsui and A. Yamagishi. A new method for known plaintext attackof FEAL cipher. In R. Rueppel, editor, Advances in Cryptology - EUROCRYPT’92, LNCS 658, pages 81–91. Springer Verlag, 1992.
[26] U.M. Maurer. New approaches to the design of self-synchronizing stream
ciphers. In D.W. Davies, editor, Advances in Cryptology - EUROCRYPT’91,
LNCS 547, pages 458–471. Springer Verlag, 1991.
[27] K. Nyberg. Differentially uniform mappings for cryptography. In T. Helleseth, editor, Advances in Cryptology - EUROCRYPT’93, LNCS 765, pages
55–64. Springer Verlag, 1993.
[28] K. Nyberg. Linear approximations of block ciphers. In A. De Santis,
editor, Advances in Cryptology - EUROCRYPT’94, LNCS 950, pages 439–
444. Springer Verlag, 1995.
[29] National Bureau of Standards. DES modes of operation. Federal Information Processing Standard (FIPS), Publication 81, National Bureau of Standards, U.S. Department of Commerce, Washington D.C., December 1980.
[30] National Institute of Standards and Technology. Advanced encryption algorithm (AES) development effort. http://www.nist.gov/aes.
[31] V. Rijmen, B. Preneel, and E. De Win. On weaknesses of non-surjectiveround functions. Designs, Codes, and Cryptography, 12(3):253–266, 1997.
[32] R.A. Rueppel. Analysis and Design of Stream Ciphers. Springer Verlag,
1986.
[33] D. Wagner. The boomerang attack. In L. R. Knudsen, editor, Fast Software
Encryption, Sixth International Workshop, Rome, Italy, March 1999, LNCS
1636, pages 156–170. Springer Verlag, 1999.