An Evaluation of the Security of
CipherUnicorn-E Against Certain Attacks
David Wagner
December 17, 2001

Executive Summary
This report studies the security of the block cipher CipherUnicorn-E against two classesof attack: differential and linear cryptanalysis. I present the results of a limited time
analysis of this cipher.
The analysis provides strong evidence that CipherUnicorn-E resists conventional
differential and linear cryptanalysis attacks. In light of these results, it seems unlikelythat a differential or linear cryptanalytic attack on the full CipherUnicorn-E construction will succeed without major new ideas.

11 Introduction
CipherUnicorn-E is a 64-bit block cipher proposed in the CRYPTREC standards effort.
In this report, I evaluate the security of CipherUnicorn-E against differential cryptanalysis and linear cryptanalysis.
Section 2 examines whether differential cryptanalysis can be used to mount an attack on CipherUnicorn-E. The answer is no: CipherUnicorn-E appears to be secureagainst conventional differential cryptanalysis. The technical results can be summarized as follows: I argue that the probability of the best differential characteristicof the CipherUnicorn-E round function is upper bounded by 2−21 , and then this implies that the probability of the best differential characteristic is at most 2−126 , which
effectively rules out the possibility of a successful differential cryptanalytic attack
on CipherUnicorn-E. The conclusion is that CipherUnicorn-E has adequate security
against conventional differential cryptanalysis.
Then, Section 3 examines whether linear cryptanalysis can be used to mount an attack on CipherUnicorn-E. This section provides strong evidence that CipherUnicorn-E
is secure against conventional linear cryptanalysis. The technical results are as follows:
no non-trivial linear characteristic for one round has bias larger than 2−12.3 , so there isno linear characteristic for the full cipher with bias larger than 2−74 , and hence linear
cryptanalytic attacks against CipherUnicorn-E can be expected to fail. The conclusion
is that CipherUnicorn-E has adequate security against conventional linear cryptanalysis.

1.1

Caveats

The results of this evaluation should be interpreted with care.
First, this is a limited time evaluation by a single cryptographer. It is widely accepted in the cryptographic community that acquiring enough confidence in a new cipher usually requires years of scrutiny by the cryptographic community at large. While
this report does describe significant evidence for the security of CipherUnicorn-E, it isno substitute for years of public study.
Second, this evaluation was limited in scope: I only studied security against conventional differential and linear cryptanalysis. While this report does provide strong
evidence that these two classes of attacks will not work against CipherUnicorn-E, no
promises can be made about other types of attacks. I have not attempted to evaluate thesecurity of CipherUnicorn-E against generalizations of differential and linear cryptanalysis, such as truncated differential cryptanalysis, higher-order differential cryptanalysis, impossible differentials, boomerang attacks, and so on. Nor have I attempted
to evaluate the security of CipherUnicorn-E against other attacks known in the literature, such as interpolation attacks, integrals, or slide attacks. I am not aware of any
viable attacks on CipherUnicorn-E, but I have not studied other potential methods for
attacking CipherUnicorn-E in any depth.
Third, on a technical note, I have focused primarily on differential characteristics
and linear characteristics, rather than differentials or linear hulls. Recall that differential characteristics specify one way that differences can propagate through the cipher,2whereas differentials specify many ways: characteristics specify “one trail”, while differentials specify “many trails.” From the point of view of security evaluation, there
are two important differences. First, differentials may have higher probability thancharacteristics, and the existence of a high-probability differential is sufficient to breaka cipher, even if no high-probability characteristics exist. Second, characteristics aremuch more amenable to evaluation than differentials: while it is often feasible to boundthe probability of the best characteristic, finding the highest-probability differential istypically an intractable task. Similar comments apply to linear characteristics vs. linear
hulls.
In this report, I study only characteristics, not differentials or hulls. Evaluating thedifferentials and hulls of CipherUnicorn-E appears to be beyond the state of the art,and I do not know how to find a provable bound on their probability. Therefore, I shall
rely on a standard heuristic, which says that the probability of the best differential is
not much larger than the probability of the best characteristic. This heuristic, while notnecessarily justified in principle from a theoretical viewpoint, seems to be accurate inpractice for many ciphers. While I do not expect that this feature of our analysis willcause any inaccuracy, and while this limitation seems to be more or less unavoidable
with the current state of the art in cryptography, the reader should recognize that there
is always the chance that the heuristic could turn out to be inaccurate, and in this casethe security of CipherUnicorn-E would need to be revisited.
That said, the results presented in this report do present good reasons to be quite
confident in the security of CipherUnicorn-E against differential and linear cryptanalysis.

1.2

Notation

I use x ⊕ y for the XOR of x and y, x  y for their sum modulo 232 , and x  y for theleft-shift of x by y positions. I will sometimes write a 32-bit value x in terms of its
four bytes, x = (a, b, c, d), where a denotes the most significant byte and d the leastsignificant, i.e., x = a · 224 + b · 216 + c · 28 + d.

2 Differential Cryptanalysis of CipherUnicorn-E
CipherUnicorn-E is a Feistel cipher with 16 rounds, using a 32-bit round function
F : {0, 1}32 → {0, 1}32 . The security of the cipher against differential cryptanalysis
relies on the non-existence of high-probability differential characteristics ∆X → ∆Y forF. Consequently, we will work towards a upper bound on the probability of the best
differential characteristic for F.
Recall that the probability of a characteristic ∆X → ∆Y for F is defined as
Pr[∆X → ∆Y ] = Pr[F(X) ⊕ F(X ⊕ ∆X) = ∆Y ],defwhere on the right-hand side X is a random variable uniformly distributed on {0, 1}32 .
We will calculate a upper bound on the probability of the best characteristic, i.e., an
estimate for max∆X,∆Y 6=0 Pr[∆X → ∆Y ].
3

In CipherUnicorn-E, the round function F has the structure
F(x) = f (x  k, g(x  k))where f represents the “main stream”, g the “temporary key generation function” (inthe terminology of the designers), and k part of the round subkey. We can analyze theprobability of the best differential characteristic for F in terms of the best differential
characteristics of f and g separately.
I consider each of these two substructures in turn, next. First, I show an upperbound 2−14 for the best characteristic for f . Then, I show an upper bound 2−7 for thebest characteristic for g. The conclusion is that there is there is no characteristic for thefull round function F with probability better than 2−21 . (Most likely the true value ismuch smaller, but this will suffice as an upper bound.)This bound suffices to show that CipherUnicorn-E is secure against conventional
differential cryptanalysis. If we assume that the attacker can bypass the first round andmount a 2-R attack, the attacker will need to find a 13-round differential characteristic.
Every such characteristic involves at least 6 active rounds, and since each active roundhas probability at most 2−21 , we see that the probability of the best 13-round differential
characteristic will be at most 2−21×6 = 2−126 . As such an attack would require vastly
more chosen plaintexts than are available, we conclude that CipherUnicorn-E appears
to be secure against differential cryptanalysis.

2.1

Differential Characteristics of f , the “Main Stream”

The function f is computed as below.
Algorithm f (s, z):
1. Apply T (1), T (2), T (3), T (4) to s to obtain t.
2. Compute u = t  k0 , where k0 is some additional key material.
3. Apply T (1), T (2), T (3), T (4) (in a permuted order determined by four bits of z)
to u to obtain v.
4. X OR a byte of y into v, then apply a T (·) round (which one is selected by z).
5. X OR another byte of z into the result, then apply another T (·) round, and call the result w.
6. Return w as the value of f (s, z).
Any non-trivial differential characteristic for Step 1, above, must include at least
one active T (·)-round. An exhaustive computer search confirms that the probability ofthe best differential characteristic for a single active T (·)-round is 1/27 . Consequently,
we can conclude that the best differential characteristic through Step 1 has probability
at most 1/27 .
Similarly, any non-trivial differential characteristic that goes through Step 3 also
involves an active T (·)-box in Step 3, and thereby contributes another factor of 1/27
(or smaller) to the overall probability. This allows us to argue that the best differential
characteristic for f , i.e., for the main stream, has probability at most 1/27 × 1/27 =2−14 .
At this point, a caveat should be mentioned. The alert reader might ask: are theseprobabilities are truly independent? The answer is not entirely clear. Without the4insertion of the subkey k0 in Step 2, the answer would be a definite ‘no’, and our boundof 214 would be completely unjustified; fortunately, however, Step 2 does introduce
key material, so our bound above may be ok. If Step 2 introduced key material using
the XOR operation, instead of using addition modulo 232 , then the two probabilities for
Step 1 and Step 3 would indeed be independent, since XORing with key material erases
everything except the XOR-difference; consequently, the upper bound of 2−14 would
be fully justified in this case.
Unfortunately, the use of addition rather than XOR complicates matters. I knowof no proof that Steps 1 and 3 should be independent, so in principle, multiplying theprobabilities of Step 1 and Step 3 is not necessarily justified. The theoretical issue isthat the values after Step 2 retain information not only on the XOR-difference before
Step 2, but also some partial information on the values of both inputs to Step 2. Inpractice, though, there is every reason to believe that the use of addition is at least
as good as, and possibly better than, XOR. I tried very hard to find even a contrived
scenario where use of addition could be less secure than XOR, and I could not findone. In practice, addition reduces the differential probability even further, because thecarry bits introduce a limited amount of non-linearity that makes it hard to predict thedifferences entering Step 3.
In summary, then, independence is not strictly 100% guaranteed from a theoreticalstandpoint, but I am confident that in practice the independence assumption is unlikely
to cause inaccuracy in our analysis. This situation, by the way, is a consequence of thedesign philosophy of “adopting a structure that is difficult to analyze”: such a structure
may be difficult for the malicious attacker to analyze, but this philosophy comes withthe disadvantage that it is also difficult for legitimate evaluators to develop reliable
evidence for the security of CipherUnicorn-E. In any case, I fully expect that there isno differential characteristic for f with a probability noticeably exceeding 2−14 . In therest of this report, I will use 2−14 as the upper bound on the probability of the best
differential characteristic for f (the “main stream”).
One might wonder whether this upper bound is very conservative. At first glance, itappears to complete ignore the extra security provided by the modular addition in Step
2 and by the final two K/T -rounds in Steps 4 and 5. However, I do not believe thosefeatures provide as much security as one might expect. In particular, I believe one canfind a differential characteristic for f with probability fairly close to the upper bound.
One possibility might look something like this:T (1)T (2,3,4)∆s −→ (0, 0, 0, ∆t3 ) −→ (0, 0, 0, ∆t3 )(Step 1, prob. 2−7 )k0−→ (0, 0, 0, ∆u3 )T (2,4,3)(Step 2, prob. ≈ 1)
T (1)−→ (0, 0, 0, ∆u3 ) −→ (∆v1 , ∆v2 , ∆v3 , ∆v4 )K(2)(Step 3, prob. 2−7 × 2−4 )T (2)−→ (∆v1 , 0, ∆v3 , ∆v4 ) −→ (∆v1 , 0, ∆v3 , ∆v4 )
K(4)

T (4)

−→ (∆v1 , 0, 0, ∆v4 ) −→ (∆v1 , 0, 0, ∆v4 )where, e.g., ∆z = (0, ∗, ∆v2 , ∆v3 ).

5(Step 4, prob. 1)(Step 5, prob. 1)

We explain the ideas behind the above characteristic in detail next. It is straightforward to find a differential characteristic ∆s → ∆t for the first four T -rounds that holdswith probability 2−7 so that ∆t = (0, 0, 0, ∆t3 ), i.e., ∆t is zero in all but the low byte:
the active round will be the first T -round, and I have verified that one can find many
characteristics for the first T -round that hold with probability 2−7 . We can additionally choose t so that ∆t has low Hamming weight, and then the difference will passthrough the modular addition (Step 2) with high probability (I assume this probability
can be chosen to be very close to 1). We will hope that, through blind luck, Step 3
will use an ordering of the T -boxes that uses T (1) last in both pairs; in this case, thefirst three T -rounds will have probability 1, and we can arrange the final T (1)-round tohave probabilty 2−7 . If we can choose ∆z appropriately, we can ensure that both pairs
use the same T -ordering in Step 3, and then the probability that T (1) appears last is
2−2 . Finally, we can choose ∆z so that the differences entering the last two T -rounds(Steps 4 and 5) are cancelled out by the K-round before passing through the S-boxes,
thereby ensuring that Steps 4 and 5 are passed through with probability 1. We mayneed another factor of 2−2 to control the order of the other T -rounds in Steps 4 and 5.
To summarize the implications of this lengthy discussion, we obtain a carefully
chosen differential characteristic (∆s, ∆z) → ∆w for f that holds with probability closeto 2−18 . This is not too far from the simple upper bound of 2−14 derived above, so I
suspect the 2−14 upper bound probably cannot be significantly improved without a lot
more work. This completes the analysis of f , the “main stream.”

2.2

Differential Characteristics of g, the “Temporary Key Generation Mechanism”

The analysis of g is a bit more involved. The function g incorporates many operations
that exploit the additive structure (rather than the XOR structure) of 32-bit words.
In particular, the Y -rounds use addition modulo 232 as well as left-shift: e.g., computations such as x0 = x  (x  3). A left-shift by k positions can be perhaps bestviewed as multiplication by 2k , and so we find that the Y -rounds correspond to multiplication modulo 232 of the input by some constant. For instance, the above-mentioned
example x0 = x  (x  3) can be equivalently expressed as x0 = (1 + 23 )x mod 232 . We
see that the Y (3, 8, 16) round corresponds to multiplication by (1 +23 )(1 + 28 )(1 +216 )modulo 232 , and the Y (7, 9, 13) round to multiplication by (1 + 27 )(1 + 29 )(1 + 213 ).
Fortunately, both of these constants are odd, so the Y rounds are bijective.
The additive structure of the Y -rounds and presence the subkey additions suggestthat XOR-differentials may not do so well: additive differentials modulo 232 may be
more appropriate. However, the T -rounds are best approximated using XOR-differentials,
not additive differentials, so it is clear that we need to consider both viewpoints.
We recall the generalization of XOR-differentials to other groups. If (x, x∗ ) represents a pair of encryptions, then their XOR-difference and additive-difference aredefined as follows:∆⊕ x = x∗ ⊕ x
def∆ x = x∗
defx = x∗ − x mod 232 .

We note that it is possible to convert between the two types of differences: for instance,6

if ∆⊕ x = 1, then ∆ x = 1 holds with probability about 1/2, or in other words,Pr[∆ x = 1 | ∆⊕ x = 1] = 1/2Pr[∆ x = 3 | ∆⊕ x = 1] = 1/4...

The conversion works this way because of the carry bits in addition. One finds thatthe conversion tends to hold with high probability only for differences with low Hamming weight, or more generally, with a small number of runs of 1’s in their binary
representation.
For convenience in writing long differentials combining both additive and XORdifferentials, we will sometimes subscript the difference itself with the appropriate
symbol to indicate which type of difference is being considered. For instance, 1⊕ → 7
represents the differential holding when F(X ⊕ 1) F(X) = 7. I will consider differentials where we are allowed to use either additive or XOR-differentials at essentiallyevery position, and I will look for an upper bound on the probability of the best differential characteristic for g.
First, note that the Y -rounds have many probability-1 additive differential characteristics.
Y (i, j,k)δ −→ γ(prob. 1)

when γ = (1 + 2i )(1 + 2 j )(1 + 2k )δ mod 232 .
Note that if we know the input difference δ , we can compute the output difference γ
using a single multiplication, and similarly we can go backwards by using the inverse
modulo 232 .
Subkey additions also leave additive differences unchanged (with probability 1).
This makes additive differential characteristics a very effective tool for attacking thesubkey additions and the Y -rounds.
Second, note that we can obtain probability-1 characteristics for the T -rounds if we
use XOR-differences. For instance, we have the following
T (1)(0, a, b, c)⊕ −→ (0, a, b, c)⊕(0, 0, b, c)⊕

T (1),T (2)−→ (0, 0, b, c)⊕(prob. 1)(prob. 1)

We can see that the only difficulty in constructing high-probability differential characteristics for g (the “temporary key generation mechanism”) will be the need to convert between additive and XOR-differences. We have probability-1 characteristics for
all components of g, so if we could convert freely between the two without restriction,
we would have a probability-1 characteristic for g by combining the characteristics forthe components. In real life, though, things don’t work this way: we must convert between additive and XOR-differences to get the characteristics to line up, and this comesat a price of reducing the probability of the characteristic.
It is not hard to see that we need to switch between additive and XOR-differences inat least four positions. The natural places are before and after each of the two segmentsof two T -rounds. Because the interaction of additive and XOR-differences are difficult
to analyze theoretically, due to the complications created by the carry bits, I carried out
7an computer search for the best differential characteristic. In particular, I searched forall differential characteristics in which the T -rounds are passed through with probability 1. This places enough restrictions on the structure of a differential characteristic toexhaustively search all possibilities: there are essentially only 216 possible differences
to consider just before the pair of T (1), T (2)-rounds, and working backwards throughg we can enumerate all possible high-probability characteristics.
The results of this exhaustive computer search are as follows. No characteristics
with probability exceeding 2−13 were found. One of the best characteristics was thefollowing (with values reported in hexadecimal):g

0xB787C072 −→ 0x00007F02

(prob. ≈ 2−13 )There were a number of other characteristic with similar and smaller probabilities. Thisparticular differential characteristic can be expanded, showing intermediate values, as
follows:k0

0xB787C072 −→ 0xB787C072

(prob. 1)

Y (3,8,16)−→ 0xFF8BC602 = 0x008...⊕T (1)−→ 0x008..⊕ = 0x0073C5FE
k00−→ 0x0073C5FE

(prob. 1)(prob. ≈ 2−10 )(prob. 1)

Y (7,9,13)−→ 0x000080FE = 0x0000...⊕T (1),T (2)−→ 0x0000...⊕ = 0x00007F02

(prob. 1)(prob. ≈ 2−3 )A word of warning: These probabilities are very approximate. Because I was searching
primarily for an upper bound on the probability of the best differential characteristic,
it is possible that the true probability of this differential characteristic is considerably
lower. I did not try to confirm whether the full characteristic for g is even possible; instead, I focused on upper bounds for characteristics for each of the components. Also,
I did not spend a lot of effort trying to assess this characteristic from the point of viewof an attacker—rather, I focused on finding an upper bound on the highest probability characteristic, with the goal of showing that no ordinary differential cryptanalytic
attack on CipherUnicorn-E is likely to succeed.
If we try to maximize the probability only of passing through T (1) (and converting
between additive and XOR-differences around this T -round), ignoring the probabilityof the final two T -rounds, the best probability is still fairly low: at most about 2−8 .
One example of such a characteristic, with probability around 2−8 , is,YT (1),

Y

T (1),T (2)0x563BC537 −→ 0xFFF7DDEF −→ 0x00082211
−→ 0x00006C91

−→ · · ·(prob. ≈ 2−8 )(prob. 1)

This suggests that the conversion between additive and XOR-differences is the mainbarrier to high-probability differential characteristics.
8

Returning to the study of the full g function, the results of the computer search canbe summarized as follows. The computer search enumerated all characteristics where
the three T -rounds are passed through with probability 1, i.e., where the S-boxes areinactive. Assuming there are no bugs in my computer program, this shows there are no
characteristics for g from this class with probability better than 2−13 . We can see thatthe conversion between additive and XOR-differences has imposes serious degradationon the probability of characteristics.
We can also consider all characteristics where some T -round is active. I verified exhaustively that there is no characteristic for any active T -round with probability larger
than 2−7 . This shows that, among the characteristics with an active T -round, none haveprobability higher than 2−7 . In fact, I suspect that all such characteristics have a much
lower probability, because if a T -round is active we obtain intermediate differenceswith very high Hamming weight, which makes the probability of passing through theadditions and Y -rounds quite low. As a result, I suspect that there is no characteristic
for g from this class with probability greater than 2−13 , but I have no proof, and I do
not know how to verify this conjecture. In any case, the weaker (and fully-justified)bound of 2−7 will be sufficient for our purposes.
Note that these two classes of characteristics cover all possibilities. In every characteristic, either some T -round is active (and we have a characteristic of the second class),or all T -rounds are inactive (and we have a characteristic of the first class). Therefore,
an upper bound on the probability of the best characteristic is max(2−13 , 2−7 ) = 2−7 .
The conclusion is that there is no differential characteristic for g (the “temporary
key generation mechanism”) that holds with probability greater than 2−7 . Most likely,
the true maximum differential probability is much smaller—I conjecture that it is probably at most 2−13 or so—but despite the existence of partial evidence, I do not knowof any proof for this conjecture. Therefore, I will use only the fully-justified and moreconservative figure of 2−7 .

3 Linear Cryptanalysis of CipherUnicorn-E
Linear cryptanalysis seems to be a much less effective method for attacking CipherUnicornE than differential cryptanalysis. This is perhaps not surprising, because this sort ofconstruction (an “unbalanced, target-heavy generalized Feistel network” [2]) tends tomuch more resistant to linear attacks than to differential attacks. As a consequence,
analyzing the security of CipherUnicorn-E against linear cryptanalysis seems mucheasier than analyzing its security against differential attacks.
Recall that the probability of a linear approximation Γ → Γ0 is defined asPr[Γ → Γ0 ] = Pr[(X · Γ) ⊕ (F(X) · Γ0 ) = 1],
defwhere on the right-hand side X is a random variable uniformly distributed on {0, 1}32
and where x · y denotes the dot-product of two 32-bit vectors. The bias of the linear
approximation Γ → Γ0 is then defined as
Bias[Γ → Γ0 ] = 2| Pr[Γ → Γ0 ] − 1/2|.
def

9Note that biases multiply when we concatenate independently-keyed functions (this is
the content of Matsui’s piling-up lemma), and that a linear characteristic of bias b can
be used in an attack using on the order of 1/b2 known texts (Matsui’s rule of thumb).
We will calculate a upper bound on the bias of the best linear characteristic, i.e., an
estimate for maxΓ,Γ0 6=0 Bias[Γ → Γ0 ].
We start by analyzing the bias of the best linear characteristic for the CipherUnicornE Feistel function. Note that any non-trivial linear approximation for a T -round (inside
the Feistel function) must include at least one active S-box. Moreover, the CipherUnicornE Feistel function includes at least 8 T -rounds. If we let bT denote the bias of the best
linear characteristic for a single T -round, then the bias of the best linear characteristic
for the Feistel function will be at most b8T (again, by the piling-up lemma). This thengives us a bound for the bias of the best 13-round linear characteristic: it can be nolarger than (b8T )6 = b48
T .
I do not know know what the maximum bias bT for a single T -round is. I haveverified computationally that, if we restrict to the case where at most two S-boxes areactive, the best probability is 1/2 ± 44/256, and hence the best bias is 88/256 ≈ 2−1.54 .
This was checked by an exhaustive search over all the 224 such linear characteristics, acomputation with workfactor approximately 232 . Note that every linear characteristic
for a T -round can be specified by a 40-bit quantity: the 8-bit mask Γ entering the S-box
inputs, and a 32-bit mask covering the entire output of the T -round.
If this result also were to extend to the case where three or four S-boxes are active,
we would have a bound 2−1.54×48 ≈ 2−74 on the best bias for the whole cipher. A
linear attack using a characteristic of bias 2−74 would need at least 2148 known texts,
which vastly exceeds the number of texts available to any attacker. Consequently, if
this partial bound extends to the unanalyzed cases, this would be compelling evidence
that CipherUnicorn-E is secure against linear cryptanalysis.
Unfortunately, the task of finding the best linear characteristic for a single T -roundappears challenging. I do not know of any easy way to compute the exact value of bT .
The problem is that the naive approach—namely, enumerating all 240 of the possible
characteristics—requires a very large workfactor (about 248 operations). This meansthat an exhaustive enumeration strategy appears to be out of the reach of today’s computers.
I am forced to leave it as an open problem to estimate the true value of bT . This
seems like an interesting algorithm problem, and there is some hope for algorithmic
improvements in this regard. We note that it is equivalent to the following problem(which is in turn closely connected to coding theory):
Given a 256 × 41 matrix M over GF(2) and a value n ∈ R, check whether
there exists a 41-bit column vector v 6= 0 so that Mv is a vector of Hamming
weight at most n.
The connection is as follows. Fill in each row of the matrix M with the 8-bit input tothe S-boxes, the 32-bit output formed of the T function, and a final column that always
contains a 1 bit. Then there is a one-to-one correspondence between vectors v suchthat Mv has low weight and linear characteristics Γ → Γ0 of the T -round of large bias:
the correspondence is given by v = (Γ, Γ0 , v41 ), and Mv has weight n if and only if
Bias[Γ → Γ0 ] = |n/128 − 1|.
10There is some hope for solving this algorithmic problem. For instance, if we want
to check whether there exists a vector Mv with weight at most n, then we could use thefollowing randomized algorithm:
1. Do the following c × (1 − n/256)−41 times:
2.
Pick 41 random columns of M, and erase the rest. We obtain a 41 × 41 matrix M0 .
3.
For all solutions v to the equation M 0 v = 0 with v 6= 0, do:
4.
If Mv has weight at most n, output v.
5. Output “no solution found.”One can expect that this algorithm will output an incorrect answer with probability
at most e−c . For an error probability of 2−20 and with n = 64, this algorithm will
require about 221 inversions of a 41×41 matrix, corresponding to about 221 ×413 ≈ 237
operations. The output would tell us, with high confidence, whether or not there is any
linear characteristic for the CipherUnicorn-E T -round with bias exceeding 1/2. If theanswer is that there is no such characteristic (as we expect), then this would imply(except for a 2−20 probability of error) that there is no linear characteristic with bias
exceeding 248 for the full CipherUnicorn-E cipher, and this would be sufficient to ruleout the possibility of linear cryptanalytic attacks on CipherUnicorn-E.
Unfortunately, due to time constraints, I have not been able to develop this direction
further. I am forced to leave it as an open problem to determine the probability of thebest linear characteristics for the CipherUnicorn-E S-boxes and T -rounds.
I will note in passing that my brute-force search for good linear characteristics
found a number of linear approximations that seem to contradict the designer’s security
claims for the CipherUnicorn-E S-boxes. For example, here are four linear characteristics of the T -function. I specify the 8-bit mask Γ covering the input byte to the S-boxes
and the 32-bit mask Γ0 = (Γ00 , Γ01 , Γ02 , Γ03 ) covering the output of the T -function (whereΓ0i is the mask for the S-box Si ). All masks are given in hexadecimal.
Pr[D6 → (16,CB, 00, 00)] = 1/2 ± 44/256
Pr[46 → (7A, 00, D1, 00)] = 1/2 ± 44/256
Pr[90 → (00, 32, 73, 00)] = 1/2 ± 44/256
In contrast, the designers’ self-evaluation report seems to claim a maximum probabilityof 1/2 ± 2−3.08 for these approximations [1], which is a puzzling discrepancy. Thereseem to be at least three possibilities: I could be misunderstanding the specification of
the cipher or their analysis; my program could be in error; or the designers’ calculations
could be erroneous. I do not know what the cause of this discrepancy is, and perhaps
it should be investigated further. In any case, the conclusion that CipherUnicorn-E appears to be secure against linear cryptanalysis seems to remain intact given our current
knowledge.

References[1] NEC Corporation, “Self Evaluation Report: CIPHERUNICORN-E,” CRYPTREC
submission, 26 pages, Ver. 3.
11[2] Bruce Schneier and John Kelsey, “Unbalanced Feistel Networks and Block Cipher
Design,” Fast Software Encryption ’96, LNCS 1039, pp.121–141, 1996.

12