Ver.2

Cryptographic Techniques
Specifications
CIPHERUNICORN-A

NEC Corporation

Ver.2

1 OVERVIEW ................................................................
................................................................................................
.........................................................................................
......................................................... 1
1.1 Purpose................................................................................................................................1
1.2 Symbol definitions ..............................................................................................................1
1.3 Bit/byte/word ordering .......................................................................................................1
2 DESIGN PRINCIPLE AND
AND CRITERIA ................................................................
..............................................................................
.............................................. 2
2.1 Data randomizer.................................................................................................................2
2.1.1 Feistel structure ..........................................................................................................2
2.1.2 Initial/final processing.................................................................................................3
2.2 Round function ...................................................................................................................3
2.2.1 Dual structure..............................................................................................................3
2.2.2 Main stream.................................................................................................................3
2.2.3 Temporary key generation mechanism ......................................................................4
2.2.4 Operators......................................................................................................................4
2.2.5 Operation units............................................................................................................4
2.3 Substitution tables .............................................................................................................5
2.4 Key scheduler .....................................................................................................................5
3 ENCRYPTION ALGORITHM
ALGORITHM................................
HM ................................................................
..............................................................................................
.............................................................. 6
3.1 Total structure ....................................................................................................................6
3.2 Data randomizer.................................................................................................................7
3.2.1 Encryption....................................................................................................................7
3.2.2 Decryption ....................................................................................................................9
3.3 F function .......................................................................................................................... 11
3.4 A3 function ........................................................................................................................13
3.5 Multiplication of constants ..............................................................................................14
3.6 Tn function........................................................................................................................15
3.7 Substitution tables ...........................................................................................................16
3.8 Key scheduler ...................................................................................................................19
3.9 MT function.......................................................................................................................25
REFERENCES ................................................................
................................................................................................
.....................................................................................
..................................................... 26iVer.2

1 Overview
1.1 Purpose
These specifications describe the design principle, design criteria, and encryption
algorithm of CIPHERUNICORN-A, a 128-bit block cipher.

1.2 Symbol definitions
These specifications make use of the following notation.
P: 1 block of plaintextC: 1 block of ciphertext

IKj: 32-bit extended keys used in initial/final processing (j=0,1,...,7)Fi: F function of round i (i=0,1,...,15)

FKai,FKbi : 32-bit extended keys used in main stream of Fi (function keys)
SKai,SKbi : 32-bit extended keys used in temporary key generation mechanism ofFi (seed keys)
EKi: Group of four extended keys FKai, SKai, FKbi, SKbi used by Fi.

úç: Data concatenation∧: Logical product⊕: Exclusive OR (XOR): Addition (mod 232)
: Subtraction (mod 232)⊗

: Multiplication (mod 232)

x>>n

: Right logical shift of x by n bitsx<<<n: Left rotation of x by n bits

1.3 Bit/byte/word ordering
These specifications use big endian notation.
Q:

128-bit data (quad word)D:

64-bit data (double word)W:

32-bit data (word)B:

8-bit data (byte)E:

1-bit data (bit)Given the above, the following holds.
Q = D0 ÷ç D1= W0 ÷ç W1 ÷ç W2 ÷ç W3= B0 ÷ç B1 ÷ç B2 ÷ç……÷ç B15= E0 ÷ç E1 ÷ç E2 ÷ç…………………………÷ç E127

1

Ver.22 Design Principle and Criteria
Two methods that have been found to be effective in mounting attacks on block ciphersof any structure are linear cryptanalysis and differential cryptanalysis. These methods
use shuffling bias in the data randomizer function to infer information on a key.
Shuffling bias often originates in the base shuffling process. A structure in which
shuffling bias cannot be detected in the base process is therefore desirable.
Against the above background, we decided to design CIPHERUNICORN-A so thatshuffling bias does not appear in the round function, the base process of data shuffling.
This was evaluated by statistically investigating the relationship between input andoutput.
In addition, to perform a uniform evaluation of encryption algorithms in the design
process, we established a common evaluation scale in examining input and output withthe encryption algorithm treated as a black box. We specified, in particular, the following
items as constituting a state with no bias and sufficient shuffling, and we checked for thisstate using a statistical technique that we adopted for this purpose.
•

A highly probable relationship between input and output bits does not exist.

•

A highly probable relationship between output bits does not exist.

•

A highly probable relationship between a change in input bits and a change in
output bits does not exist.

•

A highly probable relationship between a change in key bits and change in output
bits does not exist.

•

An output bit that has a high probability of being 0 or 1 does not exist.

Cipher input/output specifications are the same as those of the Advanced Encryption
Standard (AES), that is, a block size of 128 bits and the capability of using a secret key
length of 128, 192, or 256 bits. This cipher has been designed for high-speed operation on
a 32-bit processor.

2.1 Data randomizer
2.1.1 Feistel structure
The Feistel structure has been adopted as the base structure of this cipher because of
the following advantages.
•

Encryption and decryption have the same structure•

Encryption and decryption can be performed at about the same speed•

No limitations are set on the structure of the round function•

The Feistel structure has been thoroughly analyzed

2Ver.22.1.2 Initial/final processing
To prevent input to the 1st round function and input to the last round function frombecoming known and making an attack easy to mount, initial and final processing havebeen added.

2.2 Round function
2.2.1 Dual structure
The round function adopts a dual structure that guarantees the security of one part ofthe structure if the other should be cracked. It consists of a main stream section andtemporary key generation mechanism that input extended keys (function key and seed
key, respectively). A temporary key is created by the temporary key generation
mechanism and combined with the main stream.

seed key

temporary key
generation
mechanism

temporarykeymain stream
function key

Figure 2.1 Dual structure of round function

2.2.2 Main stream
The structure of the main stream has the following properties.
•

Bijective if the temporary key is fixed•

Data is sufficiently shuffled in the main stream itself.

3

Ver.22.2.3 Temporary key generation mec
mechanism
hanismThe structure of the temporary key generation mechanism has the following
properties.
•

The temporary key is output uniformly throughout its possible range.

•

The structure is simpler than that of the main stream (considering the possibility ofparallel processing).

•

The structure differs from that of the main stream (difference in structure
guarantees security).

•Size of temporary key is made shorter than that of seed key.

•

Data is sufficiently shuffled in the temporary key generation mechanism itself.

Because the temporary key generation mechanism is simpler in structure than themain stream, an adversary is likely to mount an attack on this mechanism first. Even if
the temporary key should become known, however, it is expected that the existence ofmultiple seed-key candidates will make it difficult to infer the secret key or function key
from the seed key.

2.2.4 Operators
Considering a 32-bit processor to be the basic form of implementation for this cipher,
we have adopted operators that can be processed at high speed on this kind of platform.
We have also combined operations having different algebraic structures with the aim ofmaking the cipher stronger.

2.2.5 Operation units
As a countermeasure to truncated differential attack, three types of operation units
are used: 8, 32, and 64 bits.

4

Ver.2

2.3 Substitution tables
Four 8-bit input/output tables are used as a set of substitution tables. Each of these
8-bit input/output tables must satisfy the following conditions.
•Bijective•

Maximum differential probability of 2–6•

Maximum linear probability of 2–6•

An algebraic degree of 7•

Input/output polynomials of high degree and many terms•

Average number of diffusion bits (number of output bits changed due to change in
one input bit) equal to 4.0•

No fixed points

The method adopted here to generate a substitution table that satisfies the above
conditions is to use an inverse function over a Galois field (GF) of 28 in combination with
an affine transformation.
An inverse function over a GF (28) is a bijective function with an algebraic degree of 7
known to have a maximum linear and differential probability of 2-6 (best case). The
degree of its input/output polynomials is also high at 254. By incorporating an affine
transformation, the number of terms in the input /output polynomials can be expected toincrease.
In order to use a combination of four 8-bit input/output tables, moreover, a different
irreducible polynomial was adopted for each table.
The following equation is used to generate a substitution table.
S(x) = matrixA{ (x + c)-1 mod g} + dHere:matrixA: GF(2) 8×8 bijective matrixc,d: 8-bit constants (other than 0)g: 8th-degree irreducible polynomial

After selecting matrixA, c, d, and g by random numbers, a search is made for a
substitution table that satisfies the above conditions.

2.4 Key scheduler
The structure of the key scheduler has the following properties.
•

Mapping from the secret key to extended keys is injective.

•

Each of the extended keys is affected by all information in the secret key.

•

A highly probable relationship between the secret keys and extended keys oramong the extended keys does not exist (secure against related-key attacks).

•

The structure makes use of the constituent elements of the round function.

5Ver.2

3 Encryption algorithm
3.1 Total structure
The CIPHERUNICORN-A has a Feistel structure that can use a data block length of
128 bits and a secret key length of 128, 192, or 256 bits. There are 16 rounds withaddition/subtraction of extended keys performed as initial/final processing. The keyscheduler has a modified Feistel structure for inputting the secret key. Here, after
shuffling the secret key in dummy loops, extended keys are repeatedly extracted while
shuffling.

P

128-bit
Secret key

128-bit

Data
Randomizer

Extended key(16 rounds)(32-bit×72)

Key
Scheduler

2304-bit

192-bit
256-bit128-bitC

Figure 3.1 CIPHERUNICORN-A total structure

6Ver.2

3.2 Data randomizer
randomizer
3.2.1 Encryption[Input]1 block of plaintext: P =P0 ÷ç P1 ÷ç P2 ÷ç P3 (128 bits)
Extended keys for F function: EKi =FKai ÷ç SKai ÷ç FKbi ÷ç SKbi
(128 bits: i=0,1,...,15)
Extended keys for initial/final processing: IKj (32 bits: j=0,1,...,7)[OutPut] 1 block of ciphertext: C =C0 ÷ç C1 ÷ç C2 ÷ç C3 (128 bits)[Process] The system inputs one block of plaintext, adds (mod 232) extended keys
as initial processing, shuffles data by a 16-round Feistel structure,
subtracts (mod 232) extended keys as final processing, and outputs one
block of ciphertext.

for i=0,…,3 do{
W0i = PiIKi}
for i=0,…,14 do{
Wi+10÷çWi+11 = Wi2÷çWi3
Wi+12÷çWi+13 = (Wi0÷çWi1) ⊕ Fi(Wi2÷çWi3, EKi)}
W162÷çW163 = W152÷çW153
W160÷çW161 = (W150÷çW151) ⊕ F15(W152÷çW153, EK15)
for i=0,…,3 do{
Ci = W16i

IKi+4

}

7

Ver.2P
IK0

IK1 IK2
EK0

IK3

F0

…

16 rounds

EK15

F15
IK4

IK5

IK6

IK7

C
Figure 3.2 Data randomizer (encryption)

8Ver.2

3.2.2 Decryption[Input]1 block of ciphertext: C =C0÷çC1÷çC2÷çC3 (128 bits)
Extended keys for F function: EKi =FKai÷çSKai÷çFKbi÷çSKbi
(128 bits: i=0,1,...,15)
Extended keys for initial/final processing: IKj (32 bits: j=0,1,...,7)[Output] 1 block of plaintext: P =P0÷çP1÷çP2÷çP3 (128 bits)[Process] The system inputs one block of ciphertext, adds (mod 232) extended
keys as initial processing, shuffles data by a 16-round Feistel structure,
subtracts (mod 232) extended keys as final processing, and outputs one
block of plaintext.

for i=0,…,3 do{
W0i = Ci

IKi+4}
for i=0,…,14 do{
Wi+10÷çWi+11 = Wi2÷çWi3
Wi+12÷çWi+13 = (Wi0÷çWi1) ⊕ F15-i(Wi2÷çWi3, EK15-i)}
W162÷çW163 = W152÷çW153
W160÷çW161 = (W150÷çW151) ⊕ F0(W152÷çW153, EK0)
for i=0,…,3 do{
Pi = W16i

IKi

}

9

Ver.2CIK4IK5 IK6
EK15

IK7

F15

…

16 rounds

EK0

F0
IK0

IK1

IK2

IK3

P

Figure 3.3 Data randomizer (decryption)10Ver.2

3.3 F function[Input]Input data: X = Xl÷çXr (64 bits)
Extended key for Fi function: EKi = FKai÷çSKai÷çFKbi÷çSkbi
(128 bits)[Constants]
Constants] Multiplication constants: Const0 =0x7e167289, Const1 =0xfe21464b[Output] Output data: Y = Yl÷çYr (64 bits)[Process] An F function consists of a main stream section and a temporary key
generation mechanism. In the main stream section, the function adds
extended keys FKai and FKbi to 64 bits of input data, executes the A3
function, performs multiplication of constants, and executes the Tn
functions. In the temporary key generation mechanism, the function
adds extended keys SKai and SKbi to 64 bits of input data, performs
multiplication of constants, passes result through the Tn functions,and produces a temporary key. This key is used to shuffle main stream
data and generate 64 bits of output data.
WK00 = SKai0

WK 1 = SKb

i

Xr
Xl

WK10 = WK00 ⊗ Const0
WK11 = WK01 ⊕ T0(WK10)
WK21 = WK11 ⊗ Const1
WK20 = WK10 ⊕ T0(WK21)
WK30 = WK20 ⊗ Const1
WK31 = WK21 ⊕ T0(WK30)
WK41 = WK31 ⊗ Const0
WK40 = WK30 ⊕ T0(WK41)
WK51 = WK41 ⊕ T1(WK40)
WK50 = WK40 ⊕ T1(WK51)
WX00 = FKai0

WX 1 = FKb

i

Xl
Xr

WX10÷çWX11 = A3(WX00÷çWX01)
WX20 = WX10 ⊗ Const0
WX21 = WX11 ⊕ T0(WX20)
WX31 = WX21 ⊗ Const1
WX30 = WX20 ⊕ T0(WX31)

11

Ver.2

WX41 = WX31 ⊕ T1(WX30)
WX40 = WX30 ⊕ T1(WX41)
WX51 = WX41 ⊕ T2(WX40)
WX50 = WX40 ⊕ T2(WX51)
WX61 = WX51 ⊕ T3(WX50)
WX60 = WX50 ⊕ T3(WX61)
k = (WK51 >> 2) ∧ 0x3
WX71 = WX61 ⊕ Tk(WX60)
k = WK51 ∧ 0x3
WX70 = WX60 ⊕ Tk(WX71)
Yl = WX70 ⊕ WK50
Yr = WX71 ⊕ WK50

0xfe21464b

0x7e167289

SKa
temporary key
generation
mechanism

T1

T1

T0

T0

T0

T0

SKb
>>2
∧

∧

0x3

0x7e167289

0x3

0xfe21464b
0x7e167289 FKa

Xl

Yl
main
stream

Tk

Tk

T3

T3

T2

T2 T1

T1 T0

T0

Yr

A3
0
23
41

FKb
Xr

0xfe21464b

Figure 3.4 F function

12Ver.2

3.4 A3 function[Input]Input data: X (64 bits)[Constants]
Constants] Three constants: const0=0, const1=23, const2=41
Criteria for determining constants:•

One constant is zero (performance considerations).

•

The number of output bits required in the inverse operation todetermine 1 input bit becomes maximum (43).

•

All 64 input bits appear in the lower 3 bytes of each 32-bit group in
thedivided output (related to subsequent processing).

Six sets of constants were found as a result of performing an
exhaustive search for constants that satisfy the above criteria. Of these,
only one set featured constants that were both prime numbers, and it
was this set that was selected.
[Output] Output data: Y (64 bits)[Process] The function performs three left rotations on input data separately as
specified by the constants, performs an exclusive OR on the resulting
three sets of data, and outputs the result.
Y = (X <<< const0) ⊕ (X <<< const1) ⊕ (X <<< const2)

13

Ver.2

3.5 Multiplication of constants[Input]Input data: X (32 bits)[Constants] Two constants: Const0 = 0x7e167289, Const1 = 0xfe21464b
Criteria for determining constants:•

Odd number (to preserve bijection)•

Hamming weight is 16 (1/2 of number of bits in constant)•

All bits of input data X affect upper 8 bits of input to function T0.

•

When “shift + XOR” is substituted for multiplication and adifferential of no more than 3 bits is given, the T0 function’s input(upper 8 bits) differential is not 0 or 0xff.

A search was performed for constants that satisfy the above criteria
and four were found to exist. When using each of these constants in
actual multiplication, the two constants indicated above were found toresult in few high-probability relationships between input differential
and output differential.
[Output] Output data: Y (32 bits)[Process] Input data is multiplied by a multiplication constant and the result is
output.
Y = X ⊗ Constn

n=0,1

14

Ver.2

3.6 Tn function[Input]Input data: X = X0÷çX1÷çX2÷çX3 (32 bits)
Input number: n (n=0,1,2,3)[Output] Output data: Y (32 bits)[Process] The function divides input data into four bytes and treats the bytecorresponding to the input number as the input value to a substitutiontable. There are four 8-bit-input/8-bit-output substitution tables
denoted as S0, S1, S2, and S3 in order from high to low bytes.
For the Tk function, k is given as input and takes on a value of 0, 1, 2,
or 3.
Y = S0(Xn) ÷çS1(Xn) ÷çS2(Xn) ÷çS3(Xn)

X = X0÷çX1÷çX2÷çX3
Y = Y0÷çY1÷çY2÷çY3
Y0

S0

Xn

Y1

S1

Xn

Y2

S2

Xn

Y3

S3

Xn

Figure 3.5 Tn function

15

Ver.2

3.7 Substitution tables[Input]Input data: X (8 bits)[Output] Output data: Y (8 bits)[Process] Data in substitution table Sn at position corresponding to input data is
output.

Y = Sn(X)n=0,1,2,3

The equation for generating each of the four substitution tables is as follows.
Sn (x) = matrixA{ (x + c)-1 mod g} + d
Table 3.1 Substitution table parametersSnmatrixA

c

g

d

S0

{0x23, 0x4e, 0x9c, 0xb1, 0x49, 0xd8, 0xc6, 0xe4}

233

0x11d

28

S1

{0x7e, 0x2a, 0xef, 0x52, 0x34, 0xa2, 0x70, 0xd7}

26

0x165

171

S2

{0x32, 0x04, 0x8f, 0x83, 0x89, 0x67, 0xcf, 0x3b}

43

0x14d

155

S3

{0x34, 0x20, 0xba, 0xd0, 0x66, 0xd7, 0xb2, 0xa8}

200

0x171

47

Here, matrixA = {0x23, 0x4e, 0x9c, 0xb1, 0x49, 0xd8, 0xc6, 0xe4}of S0 indicates theGF(2) 8×8 matrix shown below.

matrixA =

0
0
1
1
0
1
1

0
1
0
0
1
1
1

1
0
0
1
0
0
0

1 1 1

0
0
1
1
0
1
0

0
1
1
0
1
1
0

0
1
1
0
0
0
1

1
1
0
0
0
0
1

1
0
0
1
1
0
0

0 0 1 0 0

Note that irreducible polynomial g = 0x11d = 100011101(2) of S0 is the following
polynomial.
g = x8 + x4 + x3 + x2 + 1

16

Ver.2

Table 3.2 Substitution table S0
S0(0)=149, S0(1)=111, …………, S0(255)=92
149 111 237 155 21 85 108 76 236 75 193 84 22 138 89
5
51 145 13 153 148 163 86 59 204 175 91 117 126 70 144 10
248 146 201
0 97 208 23 214 147 234 66 65 226 57 210 224
172 40 154 87 178 235 135 220 110 121 96
8
9 53 241 105
143 169 182 139 112 16 183 67 233 39 197 74 166 218 231 242
161 159 192 37 177 228 47 119 14 18 244 56
3 195 239 219
33 167 26 180 54 61 58 222
4 30 191 34 107 249 142 150
95 42 124 25 232 181 120 93
5 68
6 48 129 41 104 73
188 165 212 160 250 141 123 216 94 238 81 202
7 122 196 17
207 102 184 189 243 72 206 12 200 225 164 176 247
1
2 254
71 185 229 187 251 137 69 168 50 24 171 173 158 221 127 27
252 114 152 82 209 38 203 128 215 213 36 174 134 179 90 118
80 246 253 125 29 44 15 227 98 205 255 77 198 194 133 130
79 103 78 49 19 140 109 211 223 63 64 151 62 217 170 83
136 45 115 199 20 46 190 240 132 28 162 230 131 106 32 88
157 31 43 156 113 186 35 101 52 60 11 100 116 245 99 92

Table 3.3 Substitution table S1
S1(0)=174, S1(1)=255, …………, S1(255)=53
174 255 161 109 254 40 95 67 33 124 133 58 224 238 129 56
137 57 169 87 221 220 163 84 14 239 171 138 74 192 66 104
8 250 43 115 126 88 212 103 62 82 143
4 117 226 28 155
65 156 139 183 235 125 217 116 111 237 157 68 160 184 213 172
170 132 73
2
1 232 92 249 136 106 175
59 140 38 191
50 251 85 12 27 48 46 52 145 78 168 159 100 188 16 227
26 198 244 205 178 72 142 162 51 246 241 128 194 177 122 20
144 49 83 166 247 225 11
7 102 242 185 18 150 165 121 98
93 197 70 151 75 118 202 216 108 207 15 112 99 35 101 69
86 61 79 110 13 218 149
6 134 29 36 131 181 154 180 230
77 193 164 17 211
3 209 105 94 206 44 19 60 123 10 31
130 195 76 208 54 252 219 203 199 39 189 80 167 90 32 30
233 64 245 182 120 231 127 47 22 135 55 114 234 41 21 81
173 223 23 253 153 25 45 248 97 179 186 119 200 146 187 210
0 228 24 190 141 236 63 201 96 113 240 147 229 91 107 214
89 59 152 215 176 204 243 148 42 158 71 34 222 37 196 53

17

Ver.2

Table 3.4 Substitution table S2
S2(0)=37, S2(1)=34, …………, S2(255)=124
37 34 162 132 134 220 91 143 41 45 229 247 98 178 68 56
212 97 70 15 58 72 216 208 14 96 214 217 133 179 28 154
120 123 83 100 235
3 230 160 193 245 164 155 255 175 79 148
227 219 23 95 111 11 87 104 163 203 189 29 156 173 211 64
157 53 196 89 81
4 84 16 192 74 13 181 20 184 57 183
90 119 93 207 38 131 94 60 116
1 213 122
5 101 144 117
75 46
8 172 170 152 231 210 66 54 10 187 128 204 12 102
243 115 137 147 159 233 59 221 253 112 165 198 105 222 234 153
43 201 121 180 86 205 225 242 182 55 63 232 254 44
9 21
136 65 114 31 40 49
0 36 169 22 249 35 62 17 174 248
158 151 24 50 176 108 67 127 150 18
2 168 194 171 195 145
99 25 80 224 33 200 197 118 161 61 142 77 190 209 48 139
238 206 42 125 239 237 52 223 88 167 26 130 76 191
7 71
215 27 126
6 251 51 241 129 135 246 244 146 32 177 73 82
226 110 78 186 240 141 166 69 107 85 103 149 250 109 202 19
113 140 138 39 185 228 106 47 252 199 188 92 218 30 236 124

Table 3.5 Substitution table S3
S3(0)=24, S3(1)=252, …………, S3(255)=34
24 252 144 121 17 42 77 127
2 35 173 21 129 58 105 113
112 229 185 189 76 204 209 87
5 96 82 99 133 140 66 64
192 107 194 220 16 68 183 171 219 51 92 13 152 86 135 123
98 174 103 156 157 59 145 155 158
8 231 132 83 49 23 32
85 69 251 36 233 238 222 149 37 248 26 18 125 11 137 253
79 52 56 95 241 187 44 167 124 102 227 115 212 142 154 93
247 211 33 28 67 10 147 225 215 210 246 160 131 73 65 57
1 182 180 199 207 126 216 224 61 81 202 196 146 188 119 128
50 30 91 161 89 12 195 74 235 223 226 172 245
7 218 159
242 217 208 38 163 45 39
4 62 136 104 179 88 197
60
141 190 243 214 109 162 60 165 198 228 221 164 106 101 203 236
143 48 110 80 176 78 234 181 97 84 20 70 29 168 27 72
71 90 255 19 254 114 25 230 47 43 100 178 40 41 249 186
150 205 184 201 139 75 54 22 63 244 108 175 46 169 240 153
151 116 122 232 166 117 14 94 111 206 237 177 200 31 170 120
213 53 148 15 55 239
3 191 134 250 193
9 130 118 138 34

18

Ver.2

3.8 Key scheduler[Input]Secret key: M = M0÷çM1÷ç……÷çMLINE-1 (LINE=4(128 bits),
LINE=6(192 bits),
LINE=8(256 bits))[Output]

Extended keys for F function: EKi (i=0,1,…,15) (128 bits × 16 rounds)
Extended keys for initial/final processing: IKj (j=0,1, …,7) (32 bits × 8)

[Process] The key scheduler consists of multiple MT functions.
In its basic structure, the secret key is first passed through a dummy
loop of MT functions three times where the number of rounds of MT
functions in each loop depends on the length of the secret key. After
this, the secret key is passed through 16 rounds of MT functions 9times. Each of these passes generates 8 32-bit extended keys. There
are 4, 6, and 8 rounds of MT functions in each dummy loop for
secret-key lengths of 128, 192, and 256 bits, respectively. These are notinterchangeable.
Figure 3.12 shows how these generated extended keys are used.
cnt = 0n = 16+2;
Wi=Mi (i = 0,…,LINE-1)
for i = 0,..,2 do{for j = 0,..,LINE-1 do{Wj÷çW(j+1)%LINE = MT(Wj÷çW(j+1)%LINE)}}
for i = 0,..,(16+2)/2-1 do{for j = i*16 ,…, i*16+8-1 do{
Wj%LINE÷çW(j+1)%LINE = MT(Wj%LINE÷çW(j+1)%LINE)}
for j = i*16+8 ,…, i*16+16-1 do{

19

Ver.2

Wj%LINE÷çW(j+1)%LINE = MT(Wj%LINE÷çW(j+1)%LINE)
WK[cnt++] = W(j+1)%LINE}}

IK0 = WK[0 ];IK1 = WK[n ];IK2 = WK[n*2];
IK3 = WK[n*3];
IK4 = WK[n -1];
IK5 = WK[n*2-1];
IK6 = WK[n*3-1];
IK7 = WK[n*4-1];
for i = 0,…, 16-1 do{
FKai = WK[

1+i];

i

SKa = WK[n +1+i];
FKbi = WK[n*2+1+i];
SKbi = WK[n*3+1+i];}

20

Ver.2M(128-bit) = M0 || M1 || M2 || M3 (Mn:32-bit)
M0

M1

M2

M3

MT
MT
3 timesMT
MT

Figure 3.6 Key scheduler dummy loop (128-bit secret key)

M(192-bit) = M0 || M1 || M2 || M3 || M4 || M5 (Mn:32-bit)
M0

M1

M2

M3

M4

M5

MT
MT
MT
3 timesMT
MT
MT

Figure 3.7 Key scheduler dummy loop (192-bit secret key)21

Ver.2M(256-bit) = M0 || M1 || M2 || M3 || M4 || M5 || M6 || M7 (Mn:32-bit)
M0

M1

M2

M3

M4

M5

M6

M7

MT
MT
MT
MT
3 times

MT
MT
MT
MT

Figure 3.8 Key scheduler dummy loop (256-bit secret key)

MT0

MT7

MT8
9 times(i=0,1,…,8)

key8*iMT9
key8*i +1

MT15
key8*i +7

Figure 3.9 Key scheduler extraction of extended keys (128-bit secret key)22

Ver.2

MT0

MT7

MT8
9 times(i=0,1,…,8)

key8*iMT9
key8*i +1

MT15
key8*i +7

Figure 3.10 Key scheduler extraction of extended keys (192-bit secret key)

MT0

MT7

MT8
9 times(i=0,1,…,8)

key8*iMT9
key8*i +1

MT15
key8*i +7

Figure 3.11 Key scheduler extraction of extended keys (256-bit secret key)23

Ver.2

key0

key18

key36

key54

IK0

IK1

IK2

IK3

key1

key19

key37

key55

FKa0

SKa0

FKb0

SKb0

EK0

key2

key20

key38

key56

FKa1

SKa1

FKb1

SKb1

EK1

key15

key33

key51

key69

FKa14

SKa14

FKb14

SKb14

EK14

key16

key34

key52

key70

FKa15

SKa15

FKb15

SKb15

EK15

key17

key35

key53

key71

IK4

IK5

IK6

IK7

Figure 3.12 Extended key correspondence24Ver.2

3.9 MT function[Input]Input data: X = X0÷çX1 (64 bits)[Constant] Multiplication constant: Const = 0x01010101
Criteria for determining constant:•

Odd number (to preserve bijection)•

32-bit input data are accumulated in the upper 8 bits (T0 function
input) of multiplication output.

•

Hamming weight is minimum among all constants satisfying theabove two conditions.

The constant indicated above satisfies the above criteria and was thus
selected.
[Output] Output data: Y = Y0÷çY1 (64 bits)[Process] The function multiples the upper 32 bits of input data by the constant
Const and inputs the result into the T0 function. It then performs an
exclusive OR between the output of this T0 function and the lower 32
bits of input data and outputs the result.
Y0 = X0 ⊗ Const
Y1 = X1 ⊕ T0(Y0)

X=X0÷çX1

Y=Y0÷çY1

X0

X1

0x01010101

T0

Y0

Y1

Figure 3.13 MTfunction

25

Ver.2

References[1]

M. Matsui, “Linear Cryptanalysis Method for DES Cipher,” EUROCRYPT’93, LNCS765,
pp.386-397, Springer-Verlag, 1994.

[2]

E. Biham and A. Shamir, “Differential Cryptanalysis of DES-like Cryptosystems (Extended
Abstract),” proceeding of CRYPTO’90, pp.2-21, 1990.

[3]

T. Jakobsen and L.R. Knudsen, “The Interpolation Attack on Block Ciphers,” FSE’97,
LNCS1267, pp.28-40, Springer-Verlag, 1997.

[4]

L.R. Knudsen and T.A. Berson, “Truncated Differentials of SAFER,” FSE’96, LNCS1039,
pp.15-25, Springer-Verlag, 1996.

[5]

E. Biham, “New Types of Cryptanalytic Attacks Using Related Keys,” EUROCRYPT’93,
LNCS765, pp.398-409, Springer-Verlag, 1994.

[6]

E. Biham, “On Matsui’s Linear Cryptanalysis,” EUROCRYPT’94, LNCS950, pp.341-355,
Springer-Verlag, 1994.

26