Analysis of Hierocrypt-3
January 12, 2001

Executive Summary
This report presents the results of a limited time evaluation of the block cipher
Hierocrypt-3.
No flaws nor weaknesses have been identified in the design which could leadto cryptanalytic attacks with respect to the state-of-the-art.
This report contains attacks which are better than the attacks reported by
the designers. However, the security margin for Hierocrypt-3 with the proposed
number of rounds seems to be adequate for many years still with respect to the
known attacks today.
The design of Hierocrypt-3 is very close to the design of Rijndael which has
been selected as the Advanced Encryption Standard in the U.S.A. We believethat in case there should be reported new attacks on Rijndael this could also
apply to Hierocrypt-3 and the other way around, at least to a certain degree.
Finally we mention that this report is the result of a limited time of review,and the analysis was performed without access to computer code implementing the block cipher. A longer, concentrated analysis might reveal properties
of Hierocrypt-3 which we were not able to detect. What speaks in favor of
Hierocrypt-3 is its simple design which facilitates for an easy analysis. It is easy
relatively to other designs to get convinced about the strength of Hierocrypt-3
against differential and linear cryptanalysis.

1Analysis of Hierocrypt-3

2Contents
1 Structural features and characteristics

3

2 Differential and linear cryptanalysis

33 Truncated differentials and linear hulls

44 Integral cryptanalysis

55 Other cryptanalysis

7

6 Survey of previous results

7

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

8
8
8
9
9
10
10
10
11
11
12
12
12
13

Analysis of Hierocrypt-3

13Structural features and characteristics

Hierocrypt-3 is an iterated block cipher with 128-bit blocks and allows for threedifferent key sizes to be compliant with the AES [30].
Hierocrypt-3 borrows elements from the block cipher Rijndael [10] but there
are differences. Hierocrypt-3 defines a 32-bit S-box XS from an 8-bit S-box S
and a linear transformation M DSL . The 32-bit input to XS is split into four
bytes, and each byte is evaluated through S. The 32-bit output of S is input
to M DSL , which is constructed from the parity-check matrix of an MDS-code.
The four bytes in the output of M DSL is then input again to S, and the four
output bytes form the output of XS. Before each evaluation of S a key byte is
combined to the input via the exclusive-or operation. The linear transformation
M DSH is a permutation on 16 bytes constructed from the parity-check matrixof an MDS-code. Now we can describe the outline of the cipher. The 128-bit
plaintext is split into four words of each 32 bits. Each word is input to XS, andthen all four words are input to M DSH . This is repeated five, six or seven times
depending on the key length. Finally an output transformation is applied which
consists of four applications of the XS S-box together with a final addition ofsome subkeys. The output transformation allows for similar encryption anddecryption routines. We shall call the application of four XS boxes the “XSlayer”, the linear transformation the “M DSH -layer”, the application of 16 times
the S-box S the “S-box layer” and finally the application of four times the
M DSL -function the “M DSL -layer”.
The design principles of the data randomization part are rather clear. The
principles behind the constructions in the key-schedule are not as easy to understand. However, we found no flaws in the description nor any reason to believethat the key-schedule is weak in any way.

2

Differential and linear cryptanalysis

In the following we evaluate Hierocrypt-3 with respect to differential and linear
cryptanalysis. A difference of two bit-strings of equal lengths is defined via theexclusive-or operation.
The S-box. The S-box in Hierocrypt-3 is constructed from a power polynomial over GF (28 ) together with an affine mappings used to destroy the mathematical structure. The power polynomial is f (x) = x247 in GF (28 ). It is
well-known that an S-box constructed from an inverse function in a Galois field
has highest achievable nonlinearity plus that the differential properties of thisfunction are the best one can hope for. f (x) has an easy connection to the3
inverse function. Note that x247 = x−8 = (x−1 )2 in GF (28 ). Since squaring
over GF (28 ) is a linear function, it follows that f (x) = x247 has differential andlinear properties similar to that of x−1 .
The number of active S-boxes in a characteristic for Hierocrypt-3 are very
easy to calculate for two rounds. In two consecutive rounds there will be atleast 5 active 32-bit S-boxes (XS). Inside each active XS-box there will be atAnalysis of Hierocrypt-3

4

least 5 active 8-bit S-boxes (S). In total for two rounds of Hierocrypt-3 there
will be at least 25 active 8-bit S-boxes.
First we examine the subcomponents of Hierocrypt-3. It follows from theuse of parity-check matrices of MDS-codes, that for M DSL the branch number
is five, that is, if there is s active S-boxes in the four-byte inputs, s = 1, . . . , 4,then there are at least 5 − s active S-boxes in the four-byte outputs. And for
M DSH the branch number is also five, that is, if there is s active 32-bit XSboxes in the inputs, s = 1, . . . , 4, then there are at least 5 − s active XS-boxesin the outputs.
The S-box has a maximum differential and linear probability of 2−6 [27], see
Appendix for the definition of linear probability.
Thus, in a traditional differential attack or in a traditional linear attack, theprobabilities of two-round characteristics can be bounded by (2−6 )25 = 2−150 .
This means that for 4 rounds of Hierocrypt-3 the chances that a differential or
linear attack will be applicable are very small. First of all, it would require thatthe attacker count over unrealisticly many key bytes, secondly, the probabilityof the involved characteristics are too small to facilitate any realistic attack.

3

Truncated differentials and linear hulls

The above analysis considered characteristics, see Appendix. Even stronger
tools are differentials and truncated differentials. In the following we consider
truncated differentials, but often refer to them as simply, differentials. It is
possible that there exist several characteristics which can be combined into a
differential. There have been block cipher cases in the past, where the differentials have a much higher probability than for corresponding characteristics.
Also, it could be that several differential can be combined into a truncateddifferential.
For Hierocrypt-3 it seems that the best strategy for truncated differentials is
to consider the values of blocks of 8 or 32 bits. That is, one only distinguishes
between cases where blocks of 8 or 32 bits have a zero difference or a nonzero
difference. However, note that the probabilities of truncated differentials must,in general, be higher than 2−128 to make any sense in an attack. The reason forthis is, that the differential only specifies the exact values in a subset of all 128
bits, whereas the remaining bits can take any values. As an example, consider atruncated differential for Hierocrypt-3 which specifies only 32 bits. Then there
are 96 bits in the differential which are not predicted. Thus for a randomly
chosen permutation there is such a differential with a probability of 2−32 . If
the truncated differential specifies say 64 bits, the probability should be higher
than 2−64 to be distinguished from that of a randomly chosen permutation.
Assume first that a pair of 128-bit texts is specified by the exclusive-or
difference, (x0 , x2 , x2 , x3 ), where each xi represents a 32-bit quantity. We shallwriteG(x0 , x1 , x2 , x3 ) → (y0 , y1 , y2 , y3 )Analysis of Hierocrypt-3

5

if texts of differences (x0 , x1 , x2 , x3 ) can result texts of differences (y0 , y1 , y2 , y3 )after one application of a function G. Then the following type of differential
could be possible(a, b, c, d)

XS→(e, f, g, h)(e, f, g, h)

M DSH

→

(i, 0, 0, 0)(i, 0, 0, 0)

XS→(j, 0, 0, 0)(j, 0, 0, 0)

M DSH(k, l, m, n)→

where it holds that a, b, c, and d and e, f, g, and h have values such that someof the byte differences involved are zeros. And similarly for k, l, m, n. Thisdifferential could be iterated to any number of rounds. Let us first ignore theprobability through the first XS-layer. The probability of the above combinations through the M DSH -layer is not known to us. It seems hard to calculate
and the design principles behind M DSH are not clear on this point. However,
we conjecture that this probability is at most 2−48 , since it seems that thiswould involve at least six bytes in the differences to cancel out in the function
M DSH , but the probability is perhaps even lower. If the above differential isiterated to four rounds plus an XS-round, the bound on the probabilities is2−96 . Since this differential would only specify the exact value of only 96 bits,
this gives no advantage for an attacker as compared to attacking a randomly
chosen permutation. Therefore, it seems that Hierocrypt-3 with five or morerounds is not vulnerable to an attack based on truncated differentials.
The above estimates can be translated into the case of linear hulls in muchthe same manner. Thus, we conclude that Hierocrypt-3 with five or more rounds
does not seem vulnerable to an attack based on linear hulls.

4

Integral cryptanalysis

The best known attack on Rijndael [10] is an attack which was originally first
applied to the block cipher Square [9]. The attack is generalised under the nameof “integral cryptanalysis” in [21]. Since Hierocrypt-3 is reminiscent of Rijndael
and uses very similar components we shall examine Hierocrypt-3 with respect
to this attack.
In [2] the designers examine Hierocrypt-3 with respect to the integral attackand conclude that it applies to fewer S-box layers than Rijndael. However, as
we shall show next there is an integral attack which applies to at least as many
S-box layers as in the known attack on Rijndael.
Consider a collection of 232 plaintexts which differ in one of the four 32-bit
words, that is, the texts are all different in the inputs to one XS S-box but
identical in the remaining three words. Then since XS is a bijective mapping
this is also the case after the first XS-layer.
By construction of the M DSH transformation, it holds that after the first
M DSH -layer, the texts are all different in each of the four 32-bit words. In otherAnalysis of Hierocrypt-3

6words, in each word the 232 texts take a value once only. But then since XS isa bijective mapping, it holds that after the second XS-layer, in each word the
232 texts take a value once only. After the second M DSH -layer the exclusive-orof all 232 texts is zero in each of the four words. This follows by construction of
the M DSH linear transformation.
In summary there is an integral consisting of 232 chosen plaintexts, for which
the exclusive-or sum after two rounds of Hierocrypt-3 is zero in each of four 32bit words. This integral can be used to attack Hierocrypt-3 reduced to five S-box
layers. Note that two rounds of Hierocrypt-3 consists of four S-box layers. In
the following when talking about “layers” we shall mean S-box layers. This isalso the convention used by the designers.
Consider five layers of Hierocrypt-3 and the above integral. It follows that
one can find the keys of the fifth layer, byte by byte, by guessing the value of
one key byte and decrypt all texts through one layer of S-boxes. The values of
the keys for which this sum is zero are candidates for the secret key. However,
it is not necessary for each key byte to compute these values for all 232 texts. It
sufficies to consider the ciphertexts whose values in the particular byte occurs
an odd number of times. The reason for this is, that if a value in one byte of
the ciphertexts occurs an even number of times, then for any guess key byte,
the exclusive-or sum of the values obtained by computing back through the Sbox will sum to zero. Thus for each byte position one needs to consider only
on the average 128 texts. To filter out any wrong value of the key, the above
attack must be executed twice. In total one key byte in the last round can be
determined in time about 216 S-box evaluations.
All in all, there is an attack on Hierocrypt-3 reduced to five layers, whichfinds the last round key using about 233 chosen plaintexts and in time equivalent
to the time of doing 219 S-box evaluations, which in time is equivalent to about
212 encryptions. This should be compared to the designers’ best attack on thesame variant, which requires 232 chosen texts and operates in time 2168 .
The attack can be extended to Hierocrypt-3 reduced to six layers by guessing
an additional 32 bits of key material. This is similar to the attacks on Rijndael
and to the attacks described by the designers [2]. In a first variant of this
attack on Square [8] and on Rijndael [10] the time complexity was estimatedto the time of about 272 encryptions. However, in [12] this was improved tojust 244 encryptions by introducing short-cut strategies in the key-search. This
improvement applies as well to the attack presented here on Hierocrypt-3. In
summary, there is an attack on Hierocrypt-3 reduced to six layers, which finds
the last round key using about 236 chosen plaintexts and in time equivalent to
the time of doing 250 S-box evaluations, which in time is equivalent to about 244
encryptions. This should be compared to the designers’ own estimates that the
integral attack is not applicable to Hierocrypt-3 reduced to six or more layers.
The attack on 6 layers can be extended to 7 layers by guessing even more
key material, in a manner quite similar to the attacks on Rijndael. Thus, for
Hierocrypt-3 with seven rounds, a simple extension the 6-round attack would
require at least 2172 operations, so such attacks are clearly extremely expensive.
We conclude this section by noting that the integral attack applies at leastAnalysis of Hierocrypt-3

7

as well to six layers of Hierocrypt-3 as to six rounds of Rijndael. Also, we feelthat there are some possibilities in trying to extend this to seven layers otherthan the above mentioned one for Rijndael. We are convinced however thatthe above method of integrals will not apply for the minimum twelve layers ofHierocrypt-3.

5

Other cryptanalysis

In this section we consider other attacks. First of all, there are trivial attacks
which apply to all block ciphers. An exhaustive key search will take 2k operations to succeed, where k is the key size. Also, the “matching ciphertext attack”
applies in ECB and CBC mode, but requires about 2n/2 ciphertext blocks tosucceed with good probability, where n is the block size. With n = 128 as inHierocrypt-3, 264 ciphertext blocks are required after which an attacker would
be able to deduce information about the plaintext blocks.
Higher order differentials. This attack applies to ciphers which uses nonlinear
components of a low algebraic degree. Hierocrypt-3 uses S-boxes of a highnonlinear order and together with the relatively complex linear transformations,the probability that a higher order differential attack could be applicable is verysmall.
The slide attacks, the non-surjective attacks and the “mod n” attacks do
not seem applicable to Hierocrypt-3 .
The interpolation attacks apply to ciphers which use simple mathematical functions only. Hierocrypt-3 uses mathematical functions in the S-boxes,
however the affine mappings in the S-boxes together with good linear transformations have a good effect in thwarting the interpolation attacks.
The key-schedule of Hierocrypt-3 uses components of the data randomization
part plus several linear transformations which together seem to avoid any clear
patterns in the deduced round keys. We found no reasons to believe that there
exist related-key attacks nor any (particularly) weak keys.
A last small remark is, that in §3.2.5 of [1] an operation ρ0 is defined byremoving P (32) from the operation ρ. We think the designers mean to define
the function σ0 from the function σ.

6

Survey of previous results

The only previous results on Hierocrypt-3 that we are aware of are those of thedesigners themselves [2].

Analysis of Hierocrypt-3

A

8

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

A.1

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

A.2

The matching ciphertext attack

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

Analysis of Hierocrypt-3

A.3

9Differential cryptanalysis

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

A.4

Truncated differentials

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

Analysis of Hierocrypt-3

A.5

10

Impossible differentials

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

A.6

Higher-order differentials

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

A.7

Linear cryptanalysis

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

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

A.8

Mod n cryptanalysis

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

A.9

Related-key attacks

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

Analysis of Hierocrypt-3

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

A.10

Interpolation attack

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

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

A.11

Non-surjective attack

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

A.12

Slide attacks

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

Analysis of Hierocrypt-3

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

A.13

Integral Attacks

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

References[1] Toshiba Corporation.
September 15, 2000.

Specification on a Block Cipher:

Hierocrypt-3.

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

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

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