T ( z ) c[(s(Z) @ K6)
=
BLOCK CIPHERS
156
To accomplish this, for each candidate (K4,Ks), compute
we
and we use the putative pair ( K G , to find
K7)
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
CMEAalthough 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: MeetintheMiddle
An alternative way to complete the secondary phase is a meetinthemiddle
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 UniquelyDetermined T Elements
I 50 75 100 150
Known Dlaintext blocks
1
˜˜˜
3 6 15 45
Number uniquely determined
First, we provide an intuitive description of the meetinthemiddle 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
T
for a matching R in the table. More precisely, for each ? = ( K 4 ,K5, K6, K7),
I
we find all pairs ( S( u ), R( ) ) , such that
a
(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 metinthemiddle, 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
phase.
A more clever (and more practical) approach to the meetinthemiddle
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
,
BLOCK CIPHERS
158
and similarly for b™, c™, and d™. Next, we create a table 211 with rows of the
forin
a™, b™, c™, d™, K OKI, K2,
,
which are indexed by the 3byte 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
)
3
+
+
T ( a ) = C [ ( S ( a C K G ) K7] a
)I
3
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” ˜
dI
 
˜
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 meetinthemiddle 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 meetinthemiddle attack restricted to
these candidate partial keys.
CMEA Known Plaintext Attack
4.5.6
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 loworder 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 loworder 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 meetinthemiddle 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
exercise.
More Secure CMEA?
4.5.7
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 keydependent. Of course, this could be combined with the previous
suggestion, replacing the Cave Table with a keydependent 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.
BLOCK CIPHERS
160
Akelarre
4.6
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 highlyregarded 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
mistaken.
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
4.6.1
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 128bits. 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 32bit subkeys, where this number of subkeys depends on the
number of rounds. In Akelarre, the input, output, subkey and all intermediate
calculations employ 32bit words. In particular, the 128 bit input block is
treated as four 32bit subblocks, the output consists of four 32bit subblocks
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
1 1
, ,
9
keyed rotation
K13R+4d
L
I
I
f
OutDUt
transfoimation
˜13R+59 K13R+6 ˜13R+74 “13R+t31
Yl
YO y3
y2
Figure 4.12: Akelarre.
ure 4.12, where mixed mode arithmetic operations are employed to combine
the subkey with the four 32bit subblocks 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 32bit 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 128bit input to round T (written as four 32bit
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.
<
Bz,
Let (TO, I )be the output of the box labeled “AR” in Figure 4.12. Then
T
for a given 128bit block (Bo,B1, B2, Bs),we have
(To,
Ti) = AR(Bo CE B2, Bi CE B3),
where we have ignored the dependence on the subkey. The AR function is
defined below.
BLOCK CIPHERS
162
Let ( D OD1, D2,Ds) be the output of round
, Then given B, and T, as
T.
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
32bit words which form the ciphertext block.
The heart of Akelarre is the additionrotation (AR) structure, the details
of which appear in Figure 4.13. One pass through the AR structure can be
viewed as 14 additionrotations, each applied to a 32bit subblock. Each
addition consists of subkey added to the current subblock, 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 32bit
quarterblocks instead of 64bit halfblocks, Akelarre™s additiorirotations can
be viewed as 14 halfrounds. 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 32bit. input.s to the AR structure as WO
and W and the output 32bit words as 20and 2 1 . Note that Wl is processed
1
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 loworder or
the highorder 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 ... ...
(((w1)O
This result is then added (modulo 2 3 2 ) to subkey After six more
K13,.+5.
4.6 AKELARRE 163
Figure 4.13: Akelarre additionrotation structure.
steps, we obtain 2 1 , which is then used t o determine the rotations t o apply
t o WO generate 20.
to
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 128bit
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
tli
BLOCK CIPHERS
164
11

L 
rf
Figure 4.14: Akelarre key schedule (128bit 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
...
...31
(Kz)16 23 (vi+1)24
...
...7
(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 64bit 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 32bit 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 32bit 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 128bit 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(Rr)+4)
= 0,1,. ., ,R  1 K13(Rr1)+5
T K13˜+5
K13(Rr1)+6
K13rf6
K13r+16 K13(Rr1)+16
output K13R+4 neg(K4)
KO
K13Rt5
Ki
K13R+6
K13R+7 K2
K13R+8 K3
BL0CK CIPHERS
166
Akelarre Attack
4.6.2
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
be
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 lefttoright, beginning
with 0.
For a given round, let U = (UO, I ,U2, U s ) be the output of the keyed
U
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
T
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
t
t
Bl
80
Figure 4.15: Akelarre round T.
e be the size of the keyed rotation. << !and
<
Then U =A
Let
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
u
= A << /? = (at, a t + l , . . . > at+127),
<
where the indices are all computed modulo 128. It follows that
and
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 @
9
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
round.
Let ?, be the size of the keyed rotation in round r , for r = 0 , 1 , . . . ,R  1,
/
and define
R 1
CeT.
L =
r=O
5This is an example of foreshadowing.
BLOCK CIPHERS
168
Now let A be the 128bit 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
that
(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
plaintext.
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)
3)=
0
+
where L˜ = L lo.
Now from Figure 4.12 we have
arid
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 64bit equation,
in principle, we can solve for t h e eight unknown 32bit 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 loworder 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 onetime 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?
4.6.3
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 highlyrespected 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).
BLOCK CIPHERS
170
FEAL
4.7
. . .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]
FEAL4 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 FEAL4, consists of four
rounds, and it was designed t o be extremely efficient, with a modest degree
of security. However, devastating attacks on FEAL4 were soon discovered,
rendering the algorithm insecure for virtually any conceivable application.
The developers of FEAL responded by adding more roundsfirst eight rounds
(FEAL8), then a variable number of rounds (FEALN)and with a larger
key (FEALNX).
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 FEAL4. In Section 4.7.2 we present a differential attack
that can recover the 64bit key with a work factor of about 2'' and only
requires four pairs of chosen plaintext blocks. Similar attacks succeed against
FEAL8 (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 FEAL4. Linear
cryptanalysis was invented by Matsui [97], originally as a way t o attack DES.
Linear cryptanalysis is also highly effective against FEAL4.
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 56bit 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
FEAL4, linear and differential attacks are not trivial, and considerable care
is required to actually implement these attacks to recover the key.
FEAL4 Cipher
4.7.1
There are several equivalent descriptions of the FEAL4 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 FEAL4.
FEAL4 is a fourround Feistel Cipher with a block size of 64 bits and
a 64bit key [134]. In our description of the cipher, the key is expanded
into six 32bit subkeys (the original description uses twelve 16bit subkeys).
Our version of FEAL4 appears in Figure 4.16. We ignore the key schedule
algorithm, which is used to derive the subkeys from the 64bit 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 32bit
input to F consists of the four bytes (zg,z1,z˜,zg) the 32bit output is
and
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)
and
+ 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.
=
BL0 CK CIPHERS
172
Figure 4.16: FEAL4.
The F function in Figure 4.17 can be computed as
(4.26)
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 FEAL4.
FEAL4 Differential Attack
4.7.2
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 FEAL4 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
Yl
Yo Y3
Y2
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 ,
then
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.
BLOCK CIPHERS
174
Let P = P @ PI and C™ = Co @ C1, and use similar notation for the
o
intermediate steps of the FEAL4 algorithm. Then by carefully examining
the differences at the intermediate steps of FEAL4, we obtain the results in
Figure 4.18.
Figure 4.18: FEAL4 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 meetinthe
middle. The ciphertexts Co and C are known, as are C™, L˜, and R™. From
1
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: FEAL4 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
1
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
we
(a putative value for ZO), 2 1 , (a putative value for 20). If we find
and
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,
?
3
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 jz+l
we use the notation (A)i...j,
beginning with bit i and ending with bit j of A . Let z be the allzero byte.
Then for a 32bit 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 =
BL0CK CIPHERS
176
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 16bit 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,
0
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 FEAL4, 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 64bit value
= P @ 0˜8080000080800000
o
// Given corresponding ciphertexts
// c = (Lo,Ro) and c = (L1,Rl)
o 1
Y = Lo CB Ro
o
Yi = Li CB Ri
L™ = Lo @ L1
2 = L™ @ 0x02000000
for (ao, a l ) = (OXOO,OXOO) to (Oxff,Oxff)
ao,
Qo = F ( M ( Y 0 ) (0x00, (˜1,oxoO))
CB
ao,
&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 FEAL4 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 FEAL4 cipher. There are several equivalent ways to describe FEAL4,
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 FEAL4 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.
BLOCK CIPHERS
178
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
1
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 32bit word X as X = ( x o , x ˜ ., .. , 2 3 1 ) . Then let S z , , ( X ) the XOR
be
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 loworder bit of x y is the
same as the loworder bit of x @ 9. Consequently,
so that
+ b (mod 256)) << 2) = S7(a CE b ).
<
= Ss((a
S5Go(a,
b) (4.31)
Siniilarly, we have
SSGl(a, b) = S7(a b) CB 1. (4.32)
Let X be the 32bit input to the F function of FEAL4, and Y the corre
sponding 32bit 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 FEAL4.
Taking all terms involving Y t o the lefthand side, we find
(4.33)
(4.34)
(4.35)
(4.36)
Now consider the FEAL4 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 righthand side of this expression. First,
we find
RO).
s 2 3 , 2 9 ( x O ) = s23,29(LO@
BLOCK CIPHERS
180
I 1
Figure 4.21: FEAL4 intermediate steps.
Then from (4.36), we have
and
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 lefthand 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 righthand 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 righthand 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 righthandside 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 attackthe 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)
B
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).
... ...
KO
BLOCK CIPHERS
182
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 righthand side of (4.38), so these bits can be
taken to the lefthand 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
˜3.
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 FEAL4 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 onetime pad can be viewed as confusiononly ciphers,
while transposition ciphers are of the diffusiononly variety.
Within each block, any reasonable block cipher employs both confusion
and diffusion. To see, for example, where confusion and diffusion occur in
FEAL4, first note that FEAL4 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 FEAL4 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 FEAL4, 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 FEAL4, 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
Summary
4.8
Block cipher design is relatively well understood. Consequently, it is not too
difficult to design a plausible block cipheralthough, 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
efficiencyAkelarre is a notable exception, since it is weak regardless of the
number of rounds.
Problems
4.9
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
MAC?
b. Show that Bob will almost certainly detect Trudy™s tampering.
c. What is the probability that Bob does not detect Trudy™s tamper
ing?
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 =
BLOCK CIPHERS
184
a. Explain how to do random access on data encrypted using CTR
mode.
b. Explain how to do random access on data encrypted using CBC
mode.
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.