Toshiba Corporation September 2001 1   Design principle 2   Design criteria
3 ✓Toshiba Corporation 2000–2001, All Rights Reserved
✓Toshiba Corporation 2000–2001, All Rights Reserved
2
1
Design principle
We describe the design principle of Hierocrypt–L1 in this section. We consider that the following points are important. ● Sufficient security against major attacks ● High performance on smartcards and middleware ● Efficiency in implementation ● Transparency of the design To satisfy these conditions, we determined to use the nested SPN structure in the data randomizing part, and the Feistel structure in the key scheduling part.
Data randomizing part
1.1
We chose the SP network (SPN, for short) as a fundamental structure of the proposed ciphers.  The SPN structure is a fundamental structure of block ciphers The SPN structure has the following advantages. ● It has an established design recipe based on the coding theory. ● It does not have plain path unlike the Feistel structure. ● Apparent weak keys are difficult to occur compared with the Feistel struc- ture. ● High speed encryption in a hardware implementation. On the other hand, the disadvantages are as follows. ● The area tends to be bigger than the Feistel structure, as the designs of encryption and decryption are different. ● As the width of diffusion is as twice as the Feistel structure.
1.1.1
Nested SPN structure
The nested SPN structure is a hierarchical structure, where a higher-level S-box consists of the lower-level SP network. The branch numbers are hierarchically assured in the nested SP network. The calculational cost is cheaper than the original homogeneous SPN structure, because the width of diffusion is localized for the lower-level diffusion layer, and because the word number in MDS coding decreases in the higher-level diffusion layer. We propose to impose the following conditions in designing a nested SPN cipher [6, 5]. (i) The final round of SPN consists only of an S-box layer without the follow- ing diffusion layer in all levels. (ii) Each diffusion layer is MDS in all levels. (iii) The number of rounds is even in all levels except for the highest level. (iv) Bit-wise key additions are located directly before all lowest-level S-box layers and directly after the final lowest-level S-box layer. The condition (i) is introduced so that both encryption and decryption have the same structure [9, 3, 4]. The condition (ii) is derived from the fact that the branch number is assured by two consecutive rounds. The number of parallel S-boxes is four in the lower level, and two in the higher level. We chose following parameters for Hierocrypt–L1. (a)  The lowest-level S-box is 8-bits (b) Data randomizing part consists of the 2-level SPN structure (the higher- level and the lower-level SPN) (c) The lower-level structure is 2-round SPN (d) The diffusion layer sizes are four times as much as that of S-box in the lower levels, and twice as much as that of S-box in the higher level These conditions were determined by the following reasons. (a)8-bit is the upper-bound of S-box size where a table-lookup implementation is realistic. (b) SP networks with more than two layers are not efficient in calculational cost. (c) The minimum SP network where the active S-box number can be assured efficiently is two-round SPN (SPS). (d) The number of parallel S-boxes should be small to save the calculational cost.
Simplicity and flexibility of the nested SPN structure
1.1.2
The nested SPN structure is very simple and highly transparent. Its S-boxes and diffusion layers in each level can be designed independent to some extent, and it is easy to be flexible over the change of block cipher size.
1.2
Key scheduling part
In designing the key scheduling part, it is needed to avoid the decrease of effec- tive key length because of a simple relations between extended keys as for the security. At the same time, we impose a condition that the calculational time for round key is shorter than that for data randomization, so that the initial delay is sufficiently short. The key scheduling part consists of the intermediate key update part and the round key generation part, both parts have iterative round structures. As the key length of Hierocrypt–L1 is 128-bit, intermediate key update part is designed so that its block size is 128-bit and its round function is bijective. An SP network of 128-bit block is expensive in calculational cost. As the key scheduling part should operates faster than the data randomization part, we adopt the following constitution. The 128-bit key data divides into two 64-bit halves. One half is iteratively updated by a bijective linear transformation. The other half is a 64-bit Feistel network where the "round key" is supplied from the former one. The intermediate key update part for Hierocrypt–L1 takes a round-trip type, where the update operations are reversed around the center of round structure. We call the rounds before the turning-back as plaintext side, and the rounds after the turning-back as ciphertext side. The round-trip structure gives a short initial delay even in the on-the-fly decryption. The round key for the data randomizing part of Hierocrypt–L1 is generated by concatenating four 32-bit data which are linear combinations of intermediate key bits. The linear combinations should be appropriately chosen so that weak keys do not appear, that is, there are no simple relations between the round keys. Round-dependent constants are added to the linear transformation part of intermediate key update part, in order to avoid a periodical pattern to appear. Here the constants are made from the square roots of the small integers.
2
Design criteria
2.1
Items of design criteria
Security
2.1.1
The most fundamental security criterion is the key length, which express the se- curity against the exhaustive key search (or the brute force search). Besides the key length, the security measures against the following attacks are important. (1a) Differential cryptanalysis; (1b) Linear cryptanalysis; (1c) higher-order differential cryptanalysis; (1d) Interpolation attack; (1e)  SQUARE-dedicated attack; (1f) truncated differential attack; (1g) impossible differential attack. Performance   As for the performance in encryption and decryption, the fol- lowing items are important. (2a) speed of the data randomizing part; (2b) key establishment time; (2c) speed of the on-the-fly key scheduling. Implementation efficiency   The following items are important for the im- plementation efficiency. (3a) the object code is short; (3b) required RAM is small; (3c) required ROM is small.
5
2.2
Design of the components
2.2.1
s (lower-level S-box)
The S-box is the only nonlinear component. In designing the S-box, we consider the following points are most important. (i) the maximum differential/linear probability; (ii)  algebraic order; (iii) the number of terms in polynomial expressions; (iv) nonexistence of a simple algebraic structure. At first, we impose the S-box to take the minimum values for differential and linear probabilities: The condition can be satisfied by appropriate power functions over GF(2 8 ).  But, if the power function is used as the S-box, the algorithm may be very weak against algebraic attacks such as the higher-order differential attack or the interpolation attack. Therefore, we insert bijective linear transformations both before input and after output of the power function. s(x(8)) = Add(Power(Perm(x(8))) , Y(8) = Perm(x(8)) ,  Yi(1) = Xπ[i](1) Power : GF(28) → GF(28) Power (x(8)) = x(8) 247 Add ( x (8) ) = x (8) ⊕ 0x7 . The power index 247 is chosen because it has the maximum value among the indices where the maximum differential/linear probability is 2 − 6 . The primitive polynomial for GF(2 8 ) is z 8 + z 6 + z 5 + z + 1. The additional constant 0x7 has been chosen because the input-output Ham- ming weight distribution is near to that of the random function (the correlation coefficient is 0.09375).
2.2.2
mds」（lower-level diffusion） The design criteria for mds L is as follows. (i)  maximum distance separable (MDS) map; (ii) circulant; (iii) the number of terms in a polynomial expression (bitwise) is maximum. The criterion (i) assures that no less than 5 lower-level S-boxes s are active in the active higher-level S-box xs containing 8 lower-level S-boxes. The criterion (ii) is for small implementation. The criterion (iii) is for a high security against algebraic attacks such as the higher-order differential cryptanalysis and the interpolation attack. We consider a combination function of the S-box and mds L -function connecting to it, which has an 8-bit input and a 32-bit output. We chose the combination function whose weighted term sum is maximum under the constraint (i) and (ii). In the weighted term sum of function, a term of order n is counted as n . The lower-level diffusion mds L satisfying the criteria (i)~(iii) is determined by the following procedure. 1. Make a circulant matrix with elements which satisfy the criterion (iii). 2. If the matrix is MDS, go to the following clause. Otherwise, return the preceding clause. 3. Calculate the total sum of weighted term sums for matrix elements for the matrix and its inverse. And add both total sums. If the result of the preceding clause is larger than the maximal value before, make it the new maximal value. 4. Return to the first clause. 5. Choose the one with the lowest calculational cost, from the upper candi- dates chosen by the term sum. As the result of the above procedure, the following mds L is obtained.
Here, the matrix elements are expressed in hexadecimal.
2.2.3   MDSH (higher-level diffusion)
In designing MDSH, we consider the following items are important. (i) MDS matrix (ii) byte-wise multiple-path property (iii) the number of connections between bytes should be as few as possible. The condition (i) indicates that the matrix is an MDS map for two 32-bit word. Here, let MDS(m,n) be an MDS map for m parallel n -bit words. As Proposition 2 of references [6, 5] shows, MDS(32,4) consists of eight parallel MDS(4,4).  When all MDS(4,4) are the same, MDSH is nothing but the combination of byte-wise XOR's and is expressed as 8×8 matrix. The SQUARE-dedicated attack is efficient against reduced versions of the major SPN-type ciphers SQUARE and Rijndael. The attack is applicable to up to 6-round. We let multiple-path property be a property that there are no less than two byte-wise connections between any pair of higher-level S-boxes( xs ) in two consecutive rounds. The condition (ii) requires that M DSH satisfies the multiple-path property for both forward and backward directions. The necessary and sufficient condi- tion for multiple-path property of MDSH is that all elements of MDS(2,4) are elements of { 3, 5, 6, 7, A, B, C, E }. The condition (iii) is required for a small implementation in hardware. The circulant condition was not imposed on for Hierocrypt–L1, because an exhaustive search of good matrices are feasible without the circulant condition when the matrix size is 2×2. The higher-level diffusion MDSH satisfying the criteria (i)~(iii) is deter- mined by the following procedure. 1. Make a matrix by components of GF(2 4 ) which satisfy the multiple-path property. 2. If the matrix is MDS, go to the following clause. Otherwise, return the preceding clause. 3. Calculate the inverse matrix.  If all elements satisfy the multiple-path property, go to the following clause. Otherwise, return to the preceding clause. 4. Let the matrix be a candidate for MDSH. We have obtained the following matrix by the procedure in the preceding subsubsection (without circulant condition). 5 7 A B Here, the matrix elements expressed in hexadecimal are the elements GF(2 4 ), where the primitive polynomial for GF(2 8 ) is z 8 + z 6 + z 5 + z + 1.
2.2.4   P(n) (permutation for key scheduling)
P(n) is used as a diffusion layer of the key scheduling part. We impose the following conditions. (i) The calculational time per round is shorter than that for the data ran- domizing part. (ii) It has the scalability for the change of input-output data size. (iii) It is highly diffusive (to make it difficult to infer the encryption key from the extended key). (iv) It is a bijective function (to prevent the key degree of freedom from de- generating). (v) MDS property is not required (we considered the tradeoff between speed and security). By the above conditions, we chose the following linear transformation for (4n)- bit data.
This linear transformation is written as the combination of two involution- type linear transformations.

9
3
Algorithm of Hierocrypt–L1
3.1
Notations
An n-bit value is basically expressed with the subscript "( n )". For example, the value X(n) is an element of GF(2)n. A value expressed by a capital(s) describes an element of no less than 16 bits A value expressed by a small letter(s) describes an element of less than 16 bits. We adopt the bigendian convention. When a value X ( mn ) is expressed as a concatenation of m pieces of n-bit length, each piece is expressed with the sub- script i(n) (i = 1,2,...,m), that is X(mn) = X1(n)||X2(n)|| · · · ||Xm(n). Further- more, X(mn) and X i(n) are expressed as the following concatenations: X(mn) = x1(1)||x2(1)|| · · · ||xmn(1) , Xi(n) = Xni-n+1(1)||xni-n+2(1)|| · · ||xni-n+n(1) · The following shows an example of concatenation expression of a 64-bit value X(64)・ X(64) = X 1(32) || X(64) , X i (32) = X4i-4+1(8)||X4i-4+2(8)|| · · · ||X4i-4+4(8) ,  i = 1,2, X j = x 8j −8+1(1) || x j −8+2(1) || Note that the LSB of the value X i (n) (i=1,2,. . . ,m) is x in (1), which is the in-th MSB of X(mn) •
3.2
Structure
The structures of data randomization part and the key scheduling part are described in this section. Fundamental operations used there are described in the next section.
3.2.1
Encryption
The 6-round encryption of Hierocrypt–L1 consists of 5 operations of round func- tion ρ , an operation of XS -function, and the final key addition ( AK ) . The number of rounds is 6. The 64-bit value X (64) is the output of the i-th operation of round function ρ (i = 1,2,...,5). The plaintext P(64) is assigned to the 0-th value X(0) The value X (t) is the output of the t-th operation of ρ -function for the input and the round key K (t) = ρ(X(t-1) , K(t), t = 1,2,··· ,5. Similarly, X (64) is the output of XS-function for the input X (64) and the final key K (128) = XS(X(64), K(128)
10
The ciphertext C (64) is given as the addition (XOR, exclusive or) between the 6th round output X (6) and the first half of the final key K (7)

3.2.2
Decryption
The decryption of Hierocrypt–L1 is the inverse of encryption, and consists of the final key addition, the inverse of XS-function (XS-1), and 5 inverse operations of round function (ρ− 1 ).
11
The plaintext P(64) is given as the final output X(64) P(64) =
Key scheduling
3.2.3
The main part of key scheduling consists of the intermediate key generation part and the round key generation part, preceded by the intermediate key initializa- tion. The intermediate key part recursively generates intermediate key outputs Z(t) 28) (t = 1,2, . . . ,7), and the round key generation part generates round keys K (128) ( t = 1,2,...,7) from the corresponding intermediate keys. The intermediate key Z ( t ) and the round key K ( t ) are divided into 4 pieces. To generate the intermediate keys, the σ -function is used for 5 ≤ t ≤ 7, and the σ− 1 -function is used for 5 ≤ t ≤ 7. Under the recursion rule, the intermediate key values are symmetric with regard to the point t = 4.
3.2.4
Round-dependent constants
To prevent periodic patterns from appearing in the intermediate key generation, and to improve resistance against the related key attack, we introduce round- dependent constants additions to the intermediate key generation part.  The round-dependent constants have been made by combining two from the four 32-bit values which are given as binary expansions of irrational numbers. H 0 = 0x5A827999 = trunc( √ 2/4), H 1 = 0x6ED9EBA1 = trunc(√3/4), H 2 = 0x8F1BBCDC = trunc(√5/4), H 3 = 0xCA62C1D6 = trunc(√10/4). H 4 = 0xF7DEF58A = trunc(√15/4), Where, trunc(x) = | 2 32x |
12
13
3.2.5
Preprocessing
The encryption key is used as the intermediate key Z(-1) K1(32) || K2(32) || K3(32) || K4(32) = K1(128)) Z(-1) Z(−1) = K 3(32) , Z(-1) = K4(32) - = K 1(32) , = K 2(32) , [Pre-whitening] (σο-function) The pre-whitening is done, before iterative operation by the σ -function.  The pre-whitening operation σ 0 is made from σ by removing P( 16 ) As the round-dependent constant G (32) , the following 64-bit concatenated value is used. = Ho (32) 3.2.6 Round function for intermediate key (σ-function) The intermediate key Z(t) is generated by the operation σ up to t = 4, and afterwards by the inverse operation σ− 1 . The sequence of intermediate keys is symmetric with respect to the point t = 4 for this round-trip-type scheduling. Z(t) = Z(8-t)  , 4 ≤ t ≤ 7 . We call the region: (1 < t < 4) as the plaintext side, and the other region: (5 ≤ t ≤ 7) as the ciphertext side, corresponding to the position in the data randomizing part. [Iterative update of intermediate key(plaintext side)] (1 ≤ t ≤ 4) interface   Z(t) W (t
14

[Iterative update of intermediate key(ciphertext side)] (5 ≤ t ≤ 7) interface
3.2.7
Round key generation
The different rules are applied to generate a round key from the corresponding intermediate key for the plaintext side and the ciphertext side. (1 ≤ t ≤ 4) [Round key generation(plaintext side)]
15
[Round key generation(ciphertext side)] (5 ≤ t ≤ 7)

Fundamental operations
3.3
In this section, we explain fundamental operations using in the encryption al- gorithm explained in a previous section. Fig 3 summarize relation among fun- damental operations.
16
Round function( ρ )
The ρ -function, which is the round function of the data randomization part, is a composite function of the XS -function and the MDSL -function. The input data are the X(64) and the K(128) • interface  Y(64) = ρ(X(64), K(128)) definition ρ (X (64), K (128) ) = M DSH (XS (X (64), K (128) )) ・ 3.3.2
XS-function
X S -function is a composite function of the S -function, key addition, and M D S L - function. interface  Y(64) = XS(X(64), K(128)) definition K 1(64) || K 2(64) = K (128)
XS (X(64), K (128) ) = S (MDSL (S (X(64) ⊕ K 1(64) )) ⊕ K 2(64) ·
3.3.3  S-function
The S -functions consists of parallel operations of s-function. interface  Y(64) = S (X(64)) definition x1(8)||x2(8)|| · · · ||x8(8) = X(64) ,
Y(64) = s(x1(8))||s(x2(8))|| · · · ||s(x8(8))
3.3.4 s-function
The s-function is a nonlinear transformation for 8-bit input/output value, which is given as the following table where all numbers are represented in hexadecimal. interface  Y(8) = s(x(8),
3.3.1
3.3.5
MDSL-function
The MDSL -function consists of parallel operations of mdsL -function for 32-bit subdata. interface  Y(64) = MDSL (X(64)) definition X 1(32) || X 2(32) = X (64) ; Y(64) = mdsL(X1(32))||mdsL(X2(32))
3.3.6
mds」-function
The mds L -function is a linear transformation which is represented by 4 × 4 matrix multiplication where all matrix and vector elements are regarded as elements of GF(2 8 ). interface  Y(32) = mdsL(X(32)) definition x1(8) || x2(8) || x3(8) || x4(8)  =  X(32) Y(32) = Y1(8) ||Y2(8) ||Y3(8) ||Y
The inverse function of mds_-function, mds_ 1 -function is given by following definition. interface   X(32) = mds[1(Y(32)] definition Y1(8) ||Y2(8) ||Y3(8 = 
Here, 8-bit data x (8) and the matrix element α (in hexadecimal) are regarded as elements of GF(2 8 ) related as follows.
s 28 + + z 5 + z + 1 is used as the primitive polynomial The polynomial p(z) = for the Galois field GF(28
18
3.3.7
MDSH-function
The MDSH-function is a linear transformation consisting of exclusive or's be- tween 8-bit subdata x i (8) (E GF(2) 8), where i = 1,2,...,16 ; and MDSH is represented by the following matrix form. interface  Y(64) = MDSH (X(64)) definition x1(8)||x2(8)|| · · · ||x8(8) = X(64) , Y(64) = Y1(8) ||Y2(8) ||        ||Y8(8)  ,
The inverse function of MDSH -function, MDSH -function is given by fol- lowing definition. interface  X(64) = MDSH (Y(64)) definition Y1(8)||Y2(8)|| ··· ||Y8(8) = Y(64) X(64) = x1(8) || x2(8) || ··· || x8(8)

3.3.8
P(n)-function
The P(n) function consists of the a linear transformation for the input X(4n) which is a concatenation of four n-bit values x i ( n ) ( i = 1,2,3,4) where each
19
element is regarded as an element of GF(2)". interface  Y(4n) = P(n) (X(4n)) definition x1(n) || x2(n) || x3(n) || x4(n) = X(4n) ,
Y(4n) = Y1(n) || Y2(n) || Y3(n) || Y4(n) ,
The inverse function P(n)-1 , is given by the following equation. interface  X(4n) = P(n)- 1 (Y(4n)) definition Y1(n) ||Y2(n) ||Y3(n) ||Y4(n) = Y(4n) X(4n) = X1(n) || X2(n) || X3(n) || X4(n) ,

20
3.3.9
M5-function
The M5 -function consists of a 32-bit linear transformations, where each 8-bit subdata is regarded as an element of GF(2) 8 . interface  Y(32) = M5 (X(32)) definition x1(8) || x2(8) || x3(8) || x4(8) = X(32) ,
Y(32) = Y1(8) || Y2(8) || Y3(8) || Y4(8) ,

21
3.3.10
MB-function
The MB-function consists of a 32-bit linear transformations, where each 8-bit subdata is regarded as an element of GF(2) 8 . interface  Y(32) = MB (X(32)) definition x1(8) || x2(8) || x3(8) || x4(8)  =  X(32)  , Y1(8)

3.3.11
F g -function
The F o -function is a nonlinear function which consists of the s-functions and the P(π)-functions. interface  Y(32) = F σ (X(32)) definition ×1(8)||×2(8)||×3(8)||×4(8) = X(32) ,
Y(32) = P(8) (s(x1(8))||s(x2(8))||s(x3(8))||s(x4(8))| [1] E. Biham and A. Shamir. Differential cryptanalysis of DES-like cryptosys- tems. Journal of Cryptology, Vol. 4, No. 1, pp. 3–72, 1991. [2] M. Matsui. Linear cryptanalysis method for DES cipher. In Eurocrypt'93, LNCS 765, pp. 386–397. Springer Verlag, 1994. [3] J. Daemen, L.R. Knudsen, and V. Rijmen. The block cipher SQUARE. In Fast Software Encryption (4), LNCS 1267, pp. 149–165, 1997. [4] J. Daemen and V. Rijmen. AES Proposal: Rijndael, 2000. [5] K. Ohkuma, H. Muratani, F. Sano, and S. Kawamura. Specification and assessment of the cipher Hierocrypt. Technical Report of IEICE(Japan) ISEC2000-7, 2000. [6] K. Ohkuma, H. Muratani, F. Sano, and S. Kawamura. The block cipher Hierocrypt. In Selected Areas in Cryptography 2000, LNCS 2012, pp.72–88, 2000. [7] S. Hong, S. Lee, J. Lim, J. Sung, and D. Cheon. "Provable security against differential and linear cryptanalysis for the SPN structure". In Fast Soft- ware Encryption 2000, LNCS 1978, Springer-Verlag, pp.273–283, 2000. [8] L.R. Knudsen and T.A. Berson. "Truncated differentials of SAFER". In Fast Software Encryption (5), pp. 15–25, LNCS 1039, 1996. [9] V. Rijmen, J. Daemen, B. Preneel, A. Bosselaers, and E. DcWin.  The cipher shark. In Fast Software Encryption(3), LNCS 1039, pp. 99–112, 1996. [10] S. Lucks. "Attacking seven rounds of Rijndael under 192-bit and 256-bit keys". In The third AES Conference, 2000. [11] M. Matsui. Cryptanalysis of a reduced version of the block cipher E2. Fast Software Encryption'99, Vol. LNCS 1636, , 1999. [12] M. Matsui, "New Block Encryption Algorithm MISTY", Fast Software En- cryption, 4th International Workshop Proceeding, LNCS 1267 , Springer- Verlag, 1997, pp.54-68. [13] H. Muratani, K. Ohkuma, F. Sano, M. Motoyama, and S. Kawamura. Proposition of a 64-bit version of Hierocrypt. Technical Report of IPSJ(Japan) CSEC11-8, Vol. 11, No. 8, 2000. [14] K. Ohkuma, H. Muratani, F. Sano, M. Motoyama, and S. Kawamura. A revised nested SPN cipher. Technical Report of IPSJ(Japan) CSEC11-7, Vol. 11, No. 7, 2000.