. 7
( 16)


+ K7] + z.
T ( z ) c[(s(Z) @ K6)

To accomplish this, for each candidate (K4,Ks), compute

and we use the putative pair ( K G , to find

We are now in precisely the same position as discussed above, except that
here we rule out ( K 4 ,K s ) key pairs instead of ( K GK7) pairs.
Suppose that we find a total of n pairs (Kfi,K7).Then for each of these
we would expect to find about the same number of ( K 4 , K s )pairs, since we
are relying on the same A table in both cases. The attack can be extended to
find putative (K2,K s ) and putative ( K OK l ) ,which enables us to obtain pu-
tative keys ( K OK I ,. . . , K7). The expected number of such keys is about n4,
where n is the number of ( K 6 , K 7 )pairs. Of course, n depends on the num-
ber of known plaintext blocks available. From Table 4.9 we see that if we
have 150 known plaintext blocks available, then we can expect to recover 16
putative keys. This clearly shows that the SCMEA cipher is extremely weak,
and in the next section we show that these results are easily extended to
CMEA-although the known plaintext requirement increases significantly.
However, 150 known plaintext bytes niay be unrealistic in practice. With
just 75 known plaintext blocks available, the number of putative keys would
be almost 244. While this is a significant improvement over an exhaustive
search, where there are 264 possible keys, it is worth considering whether we
can do better, particularly since the equivalent CMEA attack will require
more known plaintext.
We now discuss an alternative approach to the secondary phase of this
attack. This alternative is slightly more complex, but it results in a lower
known plaintext requirement.

Secondary Phase: Meet-in-the-Middle
An alternative way to complete the secondary phase is a meet-in-the-middle
attack, as discussed in 11521. For this attack to be practical, we must have
determined T ( j )for at least four distinct values of j during the primary phase.
This would be indicated by four rows of the A table that each contain a single
one. The expected number of such rows depends on the number of known
plaintext blocks available- typical numbers appear in Table 4.10. From these
tabulated results, we see that this attack will be possible provided somewhat
more than 50 known plaintext blocks are available. However, the attack can
also be used if wf: do not have four uniquely determined values, provided
that we have at least four rows of A , each of which has a small number of
possible T ( j ) .
4.5 CMEA 157

Table 4.10: Number of Uniquely-Determined T Elements

I 50 75 100 150
Known Dlaintext blocks

3 6 15 45
Number uniquely determined

First, we provide an intuitive description of the meet-in-the-middle attack.
Then we consider a more efficient implementation.
Suppose that from the A table, we have uniquely determined T(w), ( b ) , T
T ( c ) ,and T ( d ) , for some a , b, c, and d. Then for each of the 232 choices for
(KO,K1, K2, K 3 ) , we compute

and similarly for b, c, and d. Then we store R = ( R ( a ) , R ( b ) , R ( c ) , R ( d ) )
and the putative key bytes ( K OK1, K2, K3) in a row of a table M . Then M
has 232 rows, which we sort on R.
Next, we work backwards from the T ( a ) ,T ( b ) , ( c ) ,and T ( d ) ,searching
for a matching R in the table. More precisely, for each ? = ( K 4 ,K5, K6, K7),
we find all pairs ( S( u ), R( ) ) , such that

(and similarly for b, c, and d ) , which gives us fi = ( R ( a ) ,
R(b), ( c ) , R ( d ) ) If
R .
we find R in the table M , then we have met-in-the-middle, and thereby found
a key K OK 1 , . . . , K7 for which T ( a ) matches the known value a (according to
the A table), and also for b, c, and d. We can then test each of these putative
keys via trial decryption using known plaintext blocks.
The only tricky part of this attack is that we must invert the Cave Table
entries, and this will often generate more than one possible input value. In
such cases, we need to try them all. Nevertheless, by this approach, the work
factor is essentially the square root of the work required for an exhaustive
search. All that is needed to apply this attack is a set of four T values,
which, given sufficient known plaintext, will be obtained from the primary
A more clever (and more practical) approach to the meet-in-the-middle
attack is given in [152]. As above, we assume that T ( a ) ,T ( b ) ,T ( c ) ,and T ( d )
are known. Then for each possible ( K OK1, K 2 ) , we compute

and similarly for b™, c™, and d™. Next, we create a table 211 with rows of the
a™, b™, c™, d™, K OKI, K2,
which are indexed by the 3-byte quantity (u™ - d˜, b - d™, c - d ™ ) , where the
˜ ™
subtractions are each niod 256. The reason for this strange choice of indexing
will become clear shortly.
Note that the table 211 only has 224 rows, so it is efficient to construct
and requires minimal storage. When the table M is completed, then for
each ( K 4 ,K5, KG,
K7), we find u“ such that

R ( u ) = C[a”]+ a
+ +
S ( a ) = C [ ( R ( a6 K4) K5] a
T ( a ) = C [ ( S ( a C K G ) K7] a
and similarly for b”, c”, and d”. From the definition of a™, we see that

+ K ˜+]
R ( U ) = C[U™

+ K3. It follows that
and, therefore, we have a” = a™

= (u™ + K3) (d™ + Ks) = a
a™™ d” ˜
- -

and, similarly,
d” , b d” , c” d™ , c™
(a” ” (a™ d™ , 6™
d”) d™) ,
- - - - - -

Consequently, we can use a”, b”, c”, and d” to form an index into the table M
corresponding to a™, b™, c™, and d™. Furthermore, assuming that we find a match
in M , we can immediately find a putative K3 from the equation K:$= a” -a˜,
at which point we have recovered the entire putative key K OK1,. . . , K7. We
must test each putative key by trial decryption (or encryption) using the
known plaintext to eliminate false alarms.
Note that the meet-in-the-middle and backtracking attacks can be com-
bined. That is, we could use the backtracking attack to determine puta-
tive ( K b ,K7) pairs (and perhaps, also ( K 4 ,K s ) , depending on the number
of ( K s ,K7) obtained), then do the meet-in-the-middle attack restricted to
these candidate partial keys.

CMEA Known Plaintext Attack
The known plaintext attack on CMEA is almost identical to the SCMEA
known plaintext attack discussed above. In fact, once the A table has been
constructed, the attacks are identical. However, the construction of the A
table is slightly more complex for CMEA and it requires significantly more
known plaintext.
4.5 CMEA 159

To construct the A table for CMEA, we guess a T ( 0 )and use the restric-
tions inherent in the Cave Table to mark 92 entries of each row as impossible
values. This is precisely the same strategy that was employed in the SCMEA
attack discussed above.
For SCMEA, we used (4.18) (and analogous equations involving c1 and c2)
to further increase the density of impossible entries in A . For CMEA, the
approach is the same, except that the equation that corresponds to (4.18) is
slightly more complicated. Specifically, we have

The “V 1” implies that we cannot determine the low-order bit. This reduces
the number of impossible values for a given amount of known plaintext, since
both 0 and 1 must be tested in the low-order bit, and both must be ruled out
before we can mark an entry as impossible. A similar situation holds for the
equations involving c1 and c2. Again, once the A table has been constructed
the attack is the same as the SCMEA attack described above.
It is claimed in [152] that this attack (using the meet-in-the-middle sec-
ondary phase) will succeed on CMEA provided “50 to 80” known plaintext
blocks are available. Problems 16 and 17 ask for more precise empirical esti-
mates. Using only cg, we have found that about 420 known plaintext blocks
are required to uniquely determine T ( 0 ) . From Table 4.8 we see that the
comparable number for SCMEA is 300 blocks. Obtaining analytic results for
the number of required plaintexts would be an interesting and challenging

More Secure CMEA?

Is it possible to slightly modify the CMEA cipher and significantly increase
the security of the cipher? The attacks presented here rely heavily on the fact
that the distribution of the Cave Table entries is highly skewed. Consequently,
if we replace the Cave Table with a fixed permutation of the byte values, these
attacks would likely fail.
There are many other possible modifications of CMEA that might yield
a stronger cipher. For example, one alternative would be t o make the Cave
Table key-dependent. Of course, this could be combined with the previous
suggestion, replacing the Cave Table with a key-dependent permutation. This
would seem to greatly complicate the cryptanalysis of the CMEA cipher. It
might also be interesting to consider whether it is possible to modify the
cipher so that it is reasonably secure, yet the Cave Table remains as it is
currently configured.


It was said in the trials that Akerbeltz presided over the witches™ gatherings,
which happened every Monday, Wednesday and Frida,y.
These gatherings came t o be called akelarre, the “goat meadow.”
- Secret History of the Witches [33]

Akelarre is a block cipher that combines features of two strong block ciphers
with the goal of producing a more efficient strong cipher. Specifically, Ake-
larre uses mixed mode arithmetic, which is a primary cryptographic feature
of the highly respected IDEA cipher, and Akelarre also makes heavy use of
rotations, which are a crucial element in RC5, another highly-regarded block
cipher. By combining important elements from two strong ciphers, you might
expect that Akelarre would itself be a strong cipher. If so, you would be sadly
The Akelarre cipher was proposed in 1996 [3] and within a year, devastat-
ing attacks had been discovered [82]. In fact, Akelarre is an extremely weak
cipher -in spite of (or, more likely, because of) its relatively complex design.
Below, we describe a known plaintext attack, but there is also a ciphertext
only attack, which is only slightly more complex.

Akelarre Cipher
Akelarre is defined for any number of rounds, but its developer conjectured
that it is secure with four rounds. Amazingly, the cipher is insecure for any
number of rounds. The attack we describe is given in [82], and this attack
requires a small amount of work, regardless of the number of rounds. The
weaknesses in Akelarre are also discussed in [50].
The Akelarre block size is 128-bits. The key length can be any multiple
of 64 bits, but for simplicity, we assume here that the key size is the same
as the block length, that is, 128 bits. The difficulty of the attack does not
increase if the key size is increased.
A key schedule algorithm is used t o expand the key into the required
number of 32-bit subkeys, where this number of subkeys depends on the
number of rounds. In Akelarre, the input, output, subkey and all intermediate
calculations employ 32-bit words. In particular, the 128 bit input block is
treated as four 32-bit sub-blocks, the output consists of four 32-bit sub-blocks
and all subkeys are 32 bits.
The encryption algorithm consists of an input transformation, followed
by R rounds, and, finally, an output transformation, as illustrated in Fig-
ure 4.12. The key schedule is also specified as part of the cipher algorithm.
The plaintext block first passes through the input transformation in Fig-
4.6 AKELARRE 161


1 1
, ,
keyed rotation


˜13R+59 K13R+6 ˜13R+74 “13R+t31

YO y3

Figure 4.12: Akelarre.

ure 4.12, where mixed mode arithmetic operations are employed to combine
the subkey with the four 32-bit sub-blocks of plaintext. In Figure 4.12, “@”
is XOR, while the other “plus” operation represents addition modulo 232.
The Akelarre round function is also illustrated in Figure 4.12. We use T
to denote the current round, where r = 0 , 1 , . . . ,R - 1.
Each round begins with a “keyed rotation,” where the right 7 bits of
the 32-bit subkey K13r+4 are used to determine the size of the rotation.
That is, (K13˜+4)25...31, interpreted as an integer, is the amount that the
input is rotated left. Recall that “<<<” is our notation for a left cyclic shift.
Let (Ao,A l , A2, A3) be the 128-bit input to round T (written as four 32-bit
words) and let (Bo,B1, Ba, B3) be the output of the keyed rotation at the
beginning of round r. Then

(Bo,Bi, B3) = (Ao,A1, A2, A3) << (K13r+4)25...31.
Let (TO, I )be the output of the box labeled “AR” in Figure 4.12. Then
for a given 128-bit block (Bo,B1, B2, Bs),we have

Ti) = AR(Bo CE B2, Bi CE B3),

where we have ignored the dependence on the subkey. The AR function is
defined below.

Let ( D OD1, D2,Ds) be the output of round
, Then given B, and T, as
defined above, we havc

( B o69 TI,B C TO, C‚¬ Tl, B3 Q T O ) .
( D O D1, D 2 , 0 3 )
, 13 B2

The Di are the inputs t o the next round, except for the final round, where
they become the inputs t o the output transformation.
After R rounds, there is an output transformation, which consists of an-
other keyed rotation, followed by XOR and addition of subkey words, as
illustrated in Figure 4.12. The result of the output transformation is four
32-bit words which form the ciphertext block.
The heart of Akelarre is the addition-rotation (AR) structure, the details
of which appear in Figure 4.13. One pass through the AR structure can be
viewed as 14 addition-rotations, each applied to a 32-bit sub-block. Each
addition consists of subkey added to the current sub-block, with the addition
taken modulo 232. Each rotation affects 31 bits, as explained below, with the
amount of the rotation determined by the inputs to the AR structure.
Typically, iterated block ciphers split the input in half and then oper-
ate on these halves. Since the AR structure in Akelarre operates on 32-bit
quarter-blocks instead of 64-bit half-blocks, Akelarre™s additiori-rotations can
be viewed as 14 half-rounds. Consequently, it could be argued that one pass
through the AR structure is roughly equivalent to seven rounds of a typical
block cipher, but this is somewhat misleading since each Akelarre addition-..
rotation operation is extremely simple.
In Figure 4.13, we denote the two 32-bit. input.s to the AR structure as WO
and W and the output 32-bit words as 20and 2 1 . Note that Wl is processed
first,; with the bits of WO used to determine the required rotations, and the
resulting output is 2 1 . Then WO processed, with the bits of 2 used to
is 1
determine the rotations, and the resulting output is 20.
The rotations in thc AR structure are left rotations, but they are slightly
different than the standard rotations used in the Akelarre round function
and output transformation. In each AR rotation, either the low-order or
the high-order bit remains fixed (as indicated by a 1 in Figure 4.13) and the
remaining 31 bits (indicated by a 31) are rotated. The amount of the rotation
ranges from 0 to 31 in some steps, and from 0 to 15 in other steps, depending
on whether five or four bits are used to determine the rotation. For example,
the first step in the AR structure consists of a left rotation of bits 0 through 30
of W j , with the rightmost bit (bit 31 in our notation) remaining fixed and
the size of the rotation determined by (W0)27...31 In our standard notation,
this rotation can be written as

<< (W0)27 31)j (W1)31 31).
...30 ... ...

This result is then added (modulo 2 3 2 ) to subkey After six more
4.6 AKELARRE 163

Figure 4.13: Akelarre addition-rotation structure.

steps, we obtain 2 1 , which is then used t o determine the rotations t o apply
t o WO generate 20.
The final piece of the Akelarre algorithm is the key schedule. The precise
details of the key schedule are inconsistent between various documents, so we
follow the algorithm given in the original Akelarre paper [3].
A diagram of the key schedule algorithm appears in Figure 4.14. The key
can be any multiple of 64 bits, but, as mentioned above, we assume a 128-bit
key. The key is split into 1 8 b i t quantities which we label si,for i = 0 , 1 , . . . , 7 .
Define constants

A0 = Oxa49ed284 and A1 = Ox735203de

and let

+ A0 (mod 2 3 2 ) + A , (mod 232)
= s,” and ui = sf


L -

Figure 4.14: Akelarre key schedule (128-bit key).

for i = 0 , 1 , . . . ,7. subkey Ki is given by
Then, for i = 0 , 1 , . . . ,7,

(Kz)O 7 (ui)24...31

( K z... 15 = ( ˜ ) ...n
)˜ 7

( i1 ...23 = ( v i + 1 ) 2 4 ...31
K) 6
... (vi+1)0 ...7.
(K2)24 31

Note that the indices on the vi are taken modulo 8.
Next, for i = 0 , 1 , . . . ,7,
update ui and vi according to

+ An (mod 232) + A1 (mod 232),
and vi = v$
ui = u&
where u = (ui)8...24and v, = (vi)8...24, that is, u consists of the middle 16
, ,
bits of the old ui and v, consists of the middle 16 bits of the old vi. Then
we compute subkey Ki as

(Ki)n 7 = ( u i ) z 4 ...31

(Kz)8 15 = ( % ) O ... 7
(Kz)16 23 (vi+1)24

(KZ)24 ...31 = (W+I)O

for i = 8 , 9 , . . . ,15, where, again, the index on vi must be taken modulo 8. We
continue iterating this process until subkeys Ki, for i = 0 , 1 , 2 , . . . ,13R 8,
have been computed, where R is the number of rounds.
More generally, if the key consists of n 64-bit blocks, a similar process is
used except that we generate 4n subkeys at each level of the key schedule
algorithm, until the requisite 13R + 9 subkeys have been computed.
The precise details of the key schedule algorithm are irrelevant for the
&tack described below. In the attack we will determine certain subkeys,
4.6 AKELARRE 165

then we can recover plaintext using these subkeys without knowledge of the
underlying Akelarre key.
Finally, we need to describe the decryption algorithm. Akelarre is not
a Feistel Cipher, but it is designed so that the same logic can be used to
encrypt and decrypt. However, unlike a Feistel Cipher where we simply need
to use the subkeys in reverse order, in Akelarre, more substantial changes to
the subkeys are required.
Consider a 32-bit word A. Let II: = (A)25,,.31,where II: is interpreted as an
integer, and let y = -x (mod 128). Let neg(A) be the 32-bit word obtained
with the the seven bits represented by y (with leading 0s
by replacing (A)25,,.31
included, if necessary). For example, neg( Oxa5b5c5d5) = Oxa5b5c5ab.
Now consider subkey KISr+4in Figure 4.12. The rightmost seven bits
of this subkey are used to determine the rotation of the 128-bit block. By
using neg(K1sr+4) in place of K1sr+4 during decryption, we can effectively
undo the rotation, since a rotation of 128 is equivalent to no rotation at all.
Using this notation, the encryption subkeys and the corresponding decryp-
tion subkeys are specified in Table 4.11, where T = 0,1,. . . ,R - 1, and - X
is to be taken modulo 232. Then the Akelarre encryption algorithm in Fig-
ure 4.12 is also the Akelarre decryption algorithm, provided the subkeys are
modified as indicated in Table 4.11.

Encryption Decrypt ion
Transformation Subkeys Subkeys
Input KO -K13R+5
K1 K13R+6
K2 K13Rt7
K3 -K13R+8
Round K13r+4 neg(K13(R-r)+4)
= 0,1,. ., ,R - 1 K13(R--r-1)+5
T K13˜+5

K13r+16 K13(R--r-1)+16
output K13R+4 neg(K4)
K13R+7 K2
K13R+8 -K3

Akelarre Attack

The attack we discuss in this section is similar to that in [82]. This attack
requires that we have a small amount of known plaintext available, and that
some statistics of the plaintext are known. For example, it is sufficient if we
know that the plaintext is English, or that the plaintext is ASCII. Given this
information, we can recover part of the key, and we can then recover plaintext
from ciphertext. The paper [82] also contains a ciphertext only attack, which
is only slightly more complex than the attack presented here.
Consider a single round of Akelarre, neglecting the input and output trans-
formations. Let T be the round number, and let A = ( A o , A l , A z , A s ) the
input to round r , where each A, is a 32 bit word. We denote the bits of
each A, as
At = ((132.1, a322+1, . . . ,a 3 2 ˜ + 3 1 ) ,

that is, the bits of A are numbered consecutively from left-to-right, beginning
with 0.
For a given round, let U = (UO, I ,U2, U s ) be the output of the keyed
rotation, let B = (Bo,Bl,Ba,B3) output of the round and, finally,
be the
let 7' = (To, I )the output of the AR structure. These U , B and T variables
are illustrated in Figure 4.15. The individual bits of U , B and T are numbered
in a similar manner as the bits of A.

i round r


Figure 4.15: Akelarre round T.

e be the size of the keyed rotation. << !and
Then U =A
4.6 AKELARRE 167

It immediately follows that

Note that the output of the AR structure does not appear in either of these
equations. However, in this form, the equations are not particularly useful,
since U is an intermediate step of the algorithm. However, if we can write B
in terms of A, then perhaps we can relate the input of the round to the
output, effectively bypassing the complexity of the AR ˜ t r u c t u r e . ˜
We have
= A << /? = (at, a t + l , . . . > at+127),
where the indices are all computed modulo 128. It follows that


and, therefore,

where the “mod 64” in the final term follows from the fact that

is only 64 bits in length. In this way, we can relate the input of a round to
the output simply by

As) << /? (mod 64).
(Bo CE Ba, Bi 6 B3) = (A0C‚¬ (4.20)
A2,A1 @

Since the key and the AR structure do not appear in this equation, we have,
in effect, bypassed the AR structure. Furthermore, we can easily extend this
through all R rounds, since the output of one round is the input to the next
Let ?, be the size of the keyed rotation in round r , for r = 0 , 1 , . . . ,R - 1,
and define
R- 1
L =

5This is an example of foreshadowing.

Now let A be the 128-bit input t o round 0 and let C be the output of the
final round. Then A is the output of the input transformation and C is the
input t o the output transformation.6 From (4.20) and Problem 19, it follows

(Co @ ( 3 2 , C1 @ C:<) (AoCB A2, A1 @ As) << L (mod 64).
< (4.21)

In this form, we have the XOR of output bits written in terms of the XOR
of input bits, with a n unknown rotation L .
If Akelarre did not employ its input and output transformations, then
in (4.21), A would be plaintext and C would be the corresponding ciphertext,
and the ciphertext would immediately provide some information about the
Of course, we must take the input and output transformations into ac-
count. As in Figure 4.12, we denote the plaintext block as X and the corre-
sponding ciphertext block as Y . As above, A is the input t o the first round
and C is t h e output of the last round. Let D be the result after C passes
through the keyed rotation in the output transformation, but before the key
is added and XORed. Let lo be the amount of the rotation in the output
transformation. Then from (4.21) we have

(Ao CE A2,A1 @ As) << L™ (mod 64),
( D O Dz, 1 CB 0 (4.22)

where L˜ = L lo.
Now from Figure 4.12 we have


Substituting these results into (4.22), we find

which relates the plaintext X t o the ciphertext Y , modulo the unknown
rotation L™ arid the unknown subkey words K O K1, Kz, Ks, K13˜+5, I ˜ R + ˜ ,
, K
K 1 3 R f 7 , and KI:WM.
Given sufficient known plaintext, we can solve for the unknown shift and
subkey words in (4.23). Since each known plaintext yields one 64-bit equation,
in principle, we can solve for t h e eight unknown 32-bit subkey words using
˜Try saying that three times. fast.
4.6 AKELARRE 169

four known plaintexts. Then one additional known plaintext will enable us to
solve for the rotation, for a total requirement of five known plaintext blocks.
Suppose we have the required five known plaintexts. Then we can solve for
the Ki and L in (4.23) as follows. For each of the 64 possible choices for L™,

we solve for one bit at a time, beginning from the low-order bit position. It is
necessary to keep track of carry bits and at some steps we must save multiple
possible solutions (i.e., some branching occurs). Also, it is not possible to
uniquely recover all of the subkey words using this approach. We can always
recover K O ,K2, K 1 3 ˜ + 5 ;and K13R+8, but we only determine K1 CB K13R+6
and K2 @ K13˜+7,or K1 @ K13˜+7and K2 @ K13R+6, depending on the
rotation L™. See Problem 20 for a slightly simplified version of this subkey
recovery problem.
Once we have recovered the subkey words and the shift, we are then in a
situation similar to (4.21). At this point, if we are given any ciphertext, we use
the recovered subkey words to obtain the XOR of words of the corresponding
plaintext. This is somewhat analogous to a one-time pad cipher where the
key has been used more than once. At a minimum this leaks information
about the plaintext, and it may be possible to recover the plaintext directly
from the ciphertext, provided that we have sufficient information about the
plaintext. In [82] it is claimed that if we simply know the plaintext is English,
or random ASCII text, then it is possible to recover the plaintext.
The recovery of the plaintext from the ciphertext is considered in Prob-
lem 21, where a slightly simplified version of the problem is given. In practice,
a similar approach could be used on actual Akelarre ciphertext.

Improved Akelarre?

It is interesting that the designers of Akelarre had great confidence in the
security of t™he algorithm [3], primarily because it combines features found in
two highly-respected crypto algorithms. Furthermore, the overall design of
Akelarre is relatively complex. But since the complexity of the cipher is easily
bypassed, it provides no real security. Akelarre illustrates the point that in
cryptography, complexity is no substitute for careful analysis. In any case,
the attack presented here highlights the fact that designing a secure cipher is
a challenging and subtle art.
Akelarre is such a fundamentally flawed cipher that it is difficult to imag-
ine a minor modification that could significantly improve its security. Virtu-
ally the entire complexity of the algorithm lies in the AR structure, which
can, in effect, be bypassed. Any modification that improves the security of
the algorithm would have to force the attacker to deal with the AR structure.
We leave the problem of possible modifications to Akelarre as an exercise (see
Problem 25).


. . .an encipherrnent algorithm that has the safety equal t o DES
and is suitable for software as well as hardware implementation is needed.
The FEAL (Fast data Enciphernient ALgorithm) fills this need.
- Fast Data Encipherment Algorithm FEAL [134]

FEAL-4 is breakable with 5 known plaintexts in 6 minutes.
- A New Method for Known Plaintext Attack on FEAL Cipher [98]

The Fast d a t a Encryption ALgorithm, or FEAL, is a block cipher developed
by Shimizu and Miyaguchi [134] and announced publicly in 1987. The original
version of the algorithm, which is now known as FEAL-4, consists of four
rounds, and it was designed t o be extremely efficient, with a modest degree
of security. However, devastating attacks on FEAL-4 were soon discovered,
rendering the algorithm insecure for virtually any conceivable application.
The developers of FEAL responded by adding more rounds-first eight rounds
(FEAL-8), then a variable number of rounds (FEAL-N)-and with a larger
key (FEAL-NX).
All versions of FEAL are insecure. Nevertheless, FEAL is an historically
important cipher, since it spawned many developments in the field of crypt-
analysis. In particular, Biham and Shamir's differential cryptanalysis [14] was
specifically developed t o attack FEAL. Differential cryptanalysis was then fur-
t,hered honed on the Data Encryption Standard (DES), and it was ultimately
discovered that DES was designed t o resist such attacks. Apparently, differ-
ential cryptanalysis was known by someone involved in the development of
DES (namely, the National Security Agency [140]) almost 20 years before it
was, independently, rediscovered by Biham and Shamir, and it was considered
it serious threat.
In the next section, we consider the original and simplest version of FEAL,
now known as FEAL-4. In Section 4.7.2 we present a differential attack
that can recover the 64-bit key with a work factor of about 2'' and only
requires four pairs of chosen plaintext blocks. Similar attacks succeed against
FEAL-8 (and other versions of FEAL), but the work factor is higher and the
implementations are more complex.
In Section 4.7.3 we discuss the linear cryptanalysis of FEAL-4. Linear
cryptanalysis was invented by Matsui [97], originally as a way t o attack DES.
Linear cryptanalysis is also highly effective against FEAL-4.
Today, linear and differential cryptanalysis are standard tools used t o
analyze all block cipher designs. These powerful techniques can be used t o
probe for potential weaknesses. However, neither technique is generally useful
4.7 FEAL 171

for practical attacks on ciphers. Partly, this is due to the fact that modern
block ciphers are designed with linear and differential attacks in mind, but it
is also due to the fact that these attacks are inherently impractical.
The primary reason for the impracticality of differential and linear crypt-
analysis is that they require large amounts of chosen plaintext (differential
cryptanalysis) or known plaintext (linear cryptanalysis). For example, practi-
cal attacks against DES invariably rely on an exhaustive key search to recover
the 56-bit key, even though linear cryptanalytic attacks with significantly
lower work factors are known. It is simply more effective in practice to pay
the price of a higher work factor rather than to deal with the huge volumes
of data required by these advanced cryptanalytic techniques. Also, it would
generally be impractical to expect to collect huge amounts of known (or cho-
sen) plaintext. In this regard, FEAL is an exceptional block cipher, since
practical linear and differential attacks are possible. Nevertheless, even for
FEAL-4, linear and differential attacks are not trivial, and considerable care
is required to actually implement these attacks to recover the key.

FEAL-4 Cipher
There are several equivalent descriptions of the FEAL-4 cipher. In this sec-
tion, we present a description that is suited for differential and linear attacks;
see Problem 27 for the original description of FEAL-4.
FEAL-4 is a four-round Feistel Cipher with a block size of 64 bits and
a 64-bit key [134]. In our description of the cipher, the key is expanded
into six 32-bit subkeys (the original description uses twelve 16-bit subkeys).
Our version of FEAL-4 appears in Figure 4.16. We ignore the key schedule
algorithm, which is used to derive the subkeys from the 64-bit key, since the
attacks discussed here will directly recover the subkeys. Once the subkeys
have been recovered, it is straightforward to recover the original key, see [14]
for the details.
The FEAL round function F is illustrated in Figure 4.17. The 32-bit
input to F consists of the four bytes (zg,z1,z˜,zg) the 32-bit output is
given by the four bytes (yo, y1, ˜ 2y3). The functions Go and GI each take two
bytes of input and each generates a single byte of output. These functions
are defined as
Go(a,b) = (a b (mod 256)) << 2 < (4.24)
+ b + 1 (mod 256)) << 2,
G I ( ub ) = ( u
, (4.25)
where "<<<" is the left cyclic shift operator. For example,

+ 148 + 1 (mod 256)) << 2
G˜(10000010,lOOlOlOO) (130
23 << 2 = 00010111 << 2
< < = 01011100.

Figure 4.16: FEAL-4.

The F function in Figure 4.17 can be computed as


Of particular interest is the fact that y1 and ˜2 are computed from thc 16
bits of 50 @ 5 1 and 2 2 @ 2 3 . We make use of this fact in the differential attack
on FEAL-4.

FEAL-4 Differential Attack
Differential cryptanalysis is R chosen plaintext attack, where we choose pairs
of plaintext messages whose “diffcrence” satisfies a particular property. The
definition of difference can vary, depending on the attack, but for for FEAL-
4, we use XOR as the difference operation. By considering the XOR of
two inputs, the FEAL-4 cipher is greatly simplified. In particular, since the
key is the same for the two encryptions, the XOR of the subkey effectively
vanishes when considering XOR differences instead of individual encryptions.
4.7 FEAL 173

Yo Y3

Figure 4.17: FEAL F function.

Of course, we are trying to recover the subkey, so at some point we must
use our knowledge of the difference along with the individual encryptions to
determine the subkeys.
A specific input difference is known as a characteristic. A useful char-
acteristic will yield information about the subkey when the characteristic is
pushed through several rounds of the cipher. In this way, we can recover
some information about the subkey.
An example should make the process clear, but before we present our
example, we must establish two facts concerning the FEAL F function. First,
note the obvious fact that if we have A0 = A l , then F ( A 0 ) = F ( A 1 ) . A less
obvious fact is that if
A0 @ A1 = 0 ˜ 8 0 8 0 0 0 0 0 ,
F ( A o )CB F ( A 1 ) = O X O ˜ O O O O O O
That this holds with probability 1 is somewhat surprising, but not difficult to
establish; see Problem 28. This is the crucial fact that enables the differential
attack to succeed.
Now suppose we choose plaintext messagc PO at random and we then
choose plaintext PI so that

= Po @ 0˜8080000080800000. (4.27)

Then PO@ PI = 0x8080000080800000. Since differential cryptanalysis is a
chosen plaintext attack, by assumption, we have the corresponding cipher-
texts, COand C1.

Let P = P @ PI and C™ = Co @ C1, and use similar notation for the
intermediate steps of the FEAL-4 algorithm. Then by carefully examining
the differences at the intermediate steps of FEAL-4, we obtain the results in
Figure 4.18.

Figure 4.18: FEAL-4 differential analysis.

Note that Figure 4.18 represents the XOR of the plaintexts Po and P I , as
well as the XOR of the ciphertexts, and the XOR of all intermediate values.
The fact that the subkeys do not appear in Figure 4.18 is not an error.
The subkeys are identical for the two encryptions, and since the difference
operation is XOR, the subkeys drop out of the diagram.
For any selected pair PO and PI such that P™ = 0x8080000080800000,
Figure 4.18 holds. We now “back up™™ from the ciphertext to meet-in-the-
middle. The ciphertexts Co and C are known, as are C™, L˜, and R™. From
Figure 4.18 we see that
0x02000000@ z,
L™ (4.28)

from which we can solve for 2. We also have
R˜ L˜ Y,

which allows us to solve for
Y™ = 0˜80800000 X ™.
4.7 FEAL 175

Also note that if we know the ciphertext C = ( L ,R ) ,then we compute Y as
Y=L@R, (4.29)
as can be seen from Figure 4.19.

Figure 4.19: FEAL-4 last round.

We are now in a position t o solve for putative values of subkey K3. Sup-
pose we have one pair of chosen plaintexts PO and PI that satisfy (4.27), and
we have the corresponding ciphertexts Co and C1. For these ciphertexts, we
compute 2 from (4.28). Then we compute Yo and Y (corresponding t o Co
and C1, respectively) via (4.29).
There are 232 possible values for subkey K3. Denote a putative value
from (4.29). Then given k3, can determine 2
of K3 as K3. We know YO 0
(a putative value for ZO), 2 1 , (a putative value for 20). If we find
that 2 = 20@21, then I?3 is a possible value for K3 and we save it; otherwise
we know that K3 # K 3 and we discard this choice of K 3 . Using only a single
pair of chosen plaintexts, we will find many putative l that pass this test,
but with four pairs, we expect only the correct K3 t o survive; see Problem 29.
Following the method described in the previous paragraph, the work factor
t o recover K3 is on the order of 232 and four pairs of chosen plaintexts are
required. However, due t o the structure of the F function, it, is possible t o
reduce this work factor t o about 217 as discussed below. But first we require
some additional notation. As in other sections of this book, we adopt the
convention that bits are numbered from left t o right, beginning with 0, and
where j > i, for the string of bit of length j-z+l
we use the notation (A)i...j,
beginning with bit i and ending with bit j of A . Let z be the all-zero byte.
Then for a 32-bit word A , define

M ( A ) = M(ao, a1, a21 a3) = ( 2 , a0 CB a1,a2 CE a3, 2).
The improved attack t o recover K:<consists of a primary and a secondary
phase. In the primary phase, for each possible A = ( z ,ao, a l , z ) , we compute

QO= F ( M ( Y o ) A ) and F ( M ( Y 1 )@ A ) .
@ Q1 =

From the definition of F in (4.26), we see that if A = M ( K 3 ) ,then

We can use this fact to determine a set of A = ( 2 ,ao, a l , 2 ) that are candidate
values for M ( K 3 ) . This allows us to, in effective, determines 16 bits of K3.
IJsing four pairs of chosen plaintexts, we expect to reduce the number of such
candidates to a small number.
For the secondary phase, each survivors of the primary phase is further
tested and in the process we determine the entire subkey K3. Given a siir-
vivor A = ( z , a o , a l , z ) from the primary phase, we can easily determine the
full K3 as follows. First, generate a 16-bit value B = ( b o , b l ) , and test a pu-
tativ: subkey I?3 = (bo, a0 @ b ˜a1 @ b ˜b , ˜ as discussed previously. That is,
,I )
use K3 as the putative subkey K:3 and compute 2 and 21, test whether
0 and
the condit,ion 2 = 2 @ 2 1 holds. If so, then save E ( 3 as a possible K3,
otherwise we know that K3 # K 3 and we select another B . In this way, we
recover K3, or a small number of candidate subkeys.
Assuming that a single chosen plaintext pair PO and PI is, used, the pri-
mary phase of this differential attack appears in Table 4.12 and the secondary
phase is given in Table 4.13. However, using only a single pair of chosen plain-
texts, the number of putative K3 will be large. As mentioned above, we need
to use four chosen plaintext pairs to reduce the number of putative K3 to
one (or a very small number). When more than one chosen plaintext pair is
used, the primary and secondary attacks in Tables 4.12 and 4.13, respectively,
both require slight modifications. In the primary phase, we want to save only
those (ao, u l ) that satisfy the necessary conditions for all plaintext and ci-
phertext pairs. Then in the secondary phase we will have a small number
of survivors (ideally, only one) and these, again, must satisfy the necessary
conditions for all of the plaintext and ciphertext pairs. The precise details of
this attack are left as an exercise; see Problem 30.
After successful completion of this differential attack, we will have re-
covered K3, or a small number of putative K3 values. For simplicity, we
assume a single K3 is obtained. Now we must recover the remaining subkey
values. This can be accomplished by “unzipping” the cipher to successively
obtain K2, K1, K O , and, finally, K4 and Kg. With K3 available, we can deter-
mine the input and the output to the third F function in Figure 4.16 and we
can then determine K2 in a similar manner as was used to find K3. Once K3
and K2 are known, we can then effectively rcniove the last two rounds of
the cipher and attack K1, and so on. There are several subtle points to this
attack that we leave as exercises; see Problem 31 for more details.
Before we move on to consider linear cryptanalysis, there is one issue re-
garding differential cryptanalysis that is worth pondering. In this differential
attack on FEAL-4, the characteristic we used to determine K:i occurs with
4.7 FEAL 177

Table 4.12: Primary Phase of Differential Attack for K3

// Characteristic is 0x8080000080800000
PO= random 64-bit value
= P @ 0˜8080000080800000
// Given corresponding ciphertexts
// c = (Lo,Ro) and c = (L1,Rl)
o 1
Y = Lo CB Ro
Yi = Li CB Ri
L™ = Lo @ L1
2 = L™ @ 0x02000000
for (ao, a l ) = (OXOO,OXOO) to (Oxff,Oxff)
Qo = F ( M ( Y 0 ) (0x00, (˜1,oxoO))
&I = F(M(Yi) @ (0x00, a i r0x00))
if (Qo CB Q l ) 8 ...23 == (2™)8 ...23 then
Save (ao,al)
end if
next (ao,ai)

probability one. Since the invention of differential cryptanalyis, block ciphers
have been designed with differential attacks in mind. Consequently, differcn-
tials that occur with a high probability are unlikely to be found in practice.
Nevertheless, given a differential that occurs with some positive probability p ,
it is still possible to determine information about the subkey. However, the
smaller the value of p , the larger the number of chosen plaintexts that will
be required to determine subkey bits (that is, the larger the amount of data
that is required) and the higher the work factor. Ideally, the designer of a
block cipher would like to make the work for any differential attack at least
as high as that of an exhaustive key search.

4.7.3 FEAL-4 Linear Attack
The attack described here is similar to that given by Matsui and Yamagishi
in [98],with the exception of notation and the format that we use to present
the FEAL-4 cipher. There are several equivalent ways to describe FEAL-4,
and we have chosen a format that is more similar to that given in the previous
section than that used in [98].
For the linear cryptanalysis of FEAL-4 it is convenient to rewrite the
cipher in a slightly different form than was used in the differential attack.
In Figure 4.20, the subkey K4 and K5 appear to have migrated south, as
compared to Figure 4.16. It is not difficult to show that the two formulations
are equivalent, although the values of the subkeys will differ; see Problem 32.

Table 4.13: Secondary Phase of Differential Attack for K3

// Po, PI, Co, C1, Yo,Y1, Z™ as in primary
// Given list of saved ( U O , al) from primary
for each primary survivor (ao, a l )
for (co,c1) = (OXOO,OXOO) to (Oxff,Oxff)
= (co, a0 a3 co, a1 CE c1, c1)
20 = F(Yo @ D )
2 = F(Y1 CE D )
if 20@ 2 == 2 then
Save D // candidate subkey K3
end if
next (co,c1)
next ( a g , a l )

For the linear attack, some additional notation is needed. We denote the
bits of a 32-bit word X as X = ( x o , x ˜ ., .. , 2 3 1 ) . Then let S z , , ( X ) the XOR
of bit i and bit j of X , that is, Sz,J X )= 2 , @ x9. We can extend this to sum
more than two bits, and we also define S z ( X ) 2 , . =
This linear attack exploits the fact that the low-order bit of x y is the
same as the low-order bit of x @ 9. Consequently,

so that

+ b (mod 256)) << 2) = S7(a CE b ).
= Ss((a
b) (4.31)

Siniilarly, we have
SSGl(a, b) = S7(a b) CB 1. (4.32)

Let X be the 32-bit input to the F function of FEAL-4, and Y the corre-
sponding 32-bit output, where the bits are numbered 0 through 31, from left
to right. Then from (4.31) and (4.32) and the formulas for F in (4.26), it is
not difficult to show that
4.7 FEAL 179

Figure 4.20: Another view of FEAL-4.

Taking all terms involving Y t o the left-hand side, we find


Now consider the FEAL-4 diagram in Figure 4.21, which is the same as
that in Figure 4.20, except that we have added labels t o the intermediate
steps. These labels will be used in the analysis below.
Using the notation in Figure 4.21, we have

We now expand each term on the right-hand side of this expression. First,
we find
s 2 3 , 2 9 ( x O ) = s23,29(LO@

I 1

Figure 4.21: FEAL-4 intermediate steps.

Then from (4.36), we have


and we also have

Combining all of these results and rearranging terms, wc obtain the expression
4.7 FEAL 181

where a is a constant bit, independent of the given plaintext and ciphertext.
The precise value of a is

a = S31(K1@ K3 @ K4 @ K5) @ s23,29(K4),
but this constant is unknown in the linear attack, since we are trying to
recover the subkeys. We are able to take advantage of the fact that a is
constant in spite of the fact that it is unknown.
Given a set of known plaintexts and the corresponding ciphertexts, we
can use (4.37) to determine bits of subkey KOas follows. The left-hand side
of (4.37) is unknown, but it is constant. Given a known plaintext, we then
know LO,Ro, L4, and R4, so that the right-hand side of (4.37) is known,
with the exception of KO. We exhaust over all possible choices for KOand
for each choice, we substitute each of our known plaintexts into (4.37). If the
putative KOis correct, then the right-hand side of (4.37) must be constant for
all of the known plaintexts. Consequently, given a sufficient number of known
plaintexts, we can determine a small number of candidate values for KO.This
attack is outlined in Table 4.14.

Table 4.14: Linear Attack to Find Candidates for Subkey KO

// Given (plaintext,ciphertext) pairs (Pi,CZ), = 0 , 1 , 2 , . . . , n 1
i -

f o r K = 0 t o 232 - 1 // putative KO
count[O] = count[1] = O
for i =0 t o R - 1
j = bit computed in right-hand-side of (4.37)
count [ j ] = count [ j ] 1
next i
i f count[O] == n o r count[I] == n t h e n
Save K candidate for KO
end i f
next K

The attack in Table 4.14 is feasible, but we can reduce the work factor
considerably. Here, we only outline this improved attack-the details are left
as an exercise.
We first derive expressions analogous to those in (4.37), using (4.33),
(4.34), and (4.35). Then by combining some of these, we obtain

a = s5,13,21(LO C ROCB L4) @ Si5(Lo @ L4 Q R4)
ROCE K O ) , (4.38)
@ S15F(LO @

where a is a fixed, but unknown, constant. Now let

= ((K0)O 7 @ (K0)8 15, (K0)16 ...23 @ (KO)24 ...31).
... ...

From the first line in (4.26), we see that S15F(Lo@Ro@Ko) (4.38) depends of
only on the bits (J?˜)˜...15,17...˜3. In addition. it follows from (4.30) that bits 9
and 17 of I?o are XORed in the right-hand side of (4.38), so these bits can be
taken to the left-hand side of (4.38) and treated as constant (but unknown)
values. Then we are left with an expression that depends only on the twelve
unknown key bits ( ˜ 0 ) 1 ˜ . . . 1 5 , 1 8 . . . This allows for an exhaustive search for
twelve bits of PO. Similar expressions can be derived that allow for an ex-
tremely efficient attack to recover almost all of the bits of K O ,and the few
remaining bits are easily found by a final exhaustive search. The overall work
factor for this attack is far less than the 232 required for the attack given in
Table 4.14.
The linear crytanalytic attack on FEAL-4 described here is explored fur-
ther in the problems at the end of the chapter. Specifically, Problems 33
through 35 deal with this attack.

4.7.4 Confusion and Diffusion
In his classic paper [133],Shannon discusses confusion and diffusion the in
context of symmetric ciphers. These two fundamental concepts are still guid-
ing principles of symmetric cipher design. Roughly speaking, confusion ob-
scures the relationship between the plaintext and the ciphertext, while dif-
fusion spreads the plaintext statistics through the ciphertext. The simple
substitution and the one-time pad can be viewed as confusion-only ciphers,
while transposition ciphers are of the diffusion-only variety.
Within each block, any reasonable block cipher employs both confusion
and diffusion. To see, for example, where confusion and diffusion occur in
FEAL-4, first note that FEAL-4 is a Feistel Cipher (see Problem 26), where
the Feistel round function is simply F ( X i @ K i ) , with F illustrated in Fig-
ure 4.17, and defined in (4.26).
The FEAL-4 function F does employ both confusion and diffusion, but
only to a very limited degree. The diffusion is a result of the shifting within
each byte, and also the shifting of thc bytes themselves (represented by the
horizontal arrows in Figure 4.17). The confusion is primarily due to the XOR
with the key, and, to a lesser extent, the modulo 256 addition that occurs
within each Gi function. However, in FEAL-4, both the confusion and dif-
fusion are extremely weak as evidenced by the relatively simple linear and
diffcrential attacks presented above.
Later members of the FEAL family of ciphers improved on FEAL-4, with
the stronger versions having better confusion and diffusion properties, thereby
making linear and differential attacks more difficult. However, attacks exist
for a,ll versions of FEAL, indicating that the cipher design itself is fundamen-
t,ally flawed.
4.8 SUMMARY 183

Block cipher design is relatively well understood. Consequently, it is not too
difficult to design a plausible block cipher-although, by Kerckhoffs™ Princi-
ple, such a cipher would not be trusted until it had received extensive peer
review. For example, if we create a Feistel Cipher with a round function
that has reasonable confusion and diffusion properties, and we iterate the
round function a large number of times, it is likely that any attack will be
nontrivial. However, things are much more challenging if we try to design a
block cipher that is as efficient as possible. Two of the three ciphers discussed
in this chapter are weak primarily because they were designed for extreme
efficiency-Akelarre is a notable exception, since it is weak regardless of the
number of rounds.

1. Suppose that we use a block cipher to encrypt according to the rule

What is the corresponding decryption rule? Are there any security
advantages or disadvantages to this mode compared to CBC mode?

2. Suppose Alice has four blocks of plaintext, PO,P I , P2, and P3, and she
computes a MAC using the key K . Alice sends the initialization vector,
denoted IV, the plaintext blocks and the MAC to Bob. However, Trudy
intercepts the message and replaces PI with X so that Bob receives IV,
PO,X , P2, P3, and the MAC.

a. Precisely what does Bob compute when he attempts to verify the
b. Show that Bob will almost certainly detect Trudy™s tampering.
c. What is the probability that Bob does not detect Trudy™s tamper-

3 . Counter (CTR) mode allows block ciphers to be used like stream ci-
phers. The CTR mode encryption formula is

+ 2, K )
Ci = Pi Bs E(1V

and decryption rule us

ci @ E(1V + i, K ) .
Pi =

a. Explain how to do random access on data encrypted using CTR
b. Explain how to do random access on data encrypted using CBC
c. Which is “better” for random access, CTR mode or CBC mode,
and why?

4. Suppose that Alice and Bob always choose the same IV.

a. Discuss one security problem this creates if CBC mode is used.


. 7
( 16)