Ver.3

Cryptographic Techniques
Techniques
Specifica
Specifications
CIPHERUNICORN-E

NEC Corporation

Ver.3

1 OVERVIEW ................................................................
................................................................................................
.........................................................................................
......................................................... 1
1.1 Purpose................................................................................................................................1
1.2 Symbol definitions ..............................................................................................................1
1.3 Bit/byte/word ordering .......................................................................................................2
2 DESIGN PRINCIPLE AND
AND CRITERIA ................................................................
..............................................................................
.............................................. 3
2.1 Data randomizer.................................................................................................................3
2.1.1 Feistel structure ..........................................................................................................3
2.1.2 Initial, final, and intermediate processing.................................................................3
2.2 Round function ...................................................................................................................4
2.2.1 Dual structure..............................................................................................................4
2.2.2 Main stream.................................................................................................................4
2.2.3 Temporary key generation mechanism ......................................................................4
2.2.4 Operators......................................................................................................................5
2.2.5 Operation units............................................................................................................5
2.3 Substitution tables .............................................................................................................5
2.4 Key scheduler .....................................................................................................................6
3 ENCRYPTION ALGORITHM
ALGORITHM................................
RITHM ................................................................
..............................................................................................
.............................................................. 7
3.1 Total structure ....................................................................................................................7
3.2 Data randomizer.................................................................................................................8
3.2.1 Encryption....................................................................................................................8
3.2.2 Decryption ....................................................................................................................9
3.3 L function ..........................................................................................................................10
3.4 F function .......................................................................................................................... 11
3.5 T function ..........................................................................................................................13
3.6 K function..........................................................................................................................14
3.7 Substitution tables ...........................................................................................................15
3.8 Sh table .............................................................................................................................18
3.9 Y function ..........................................................................................................................19
3.10 Key scheduler .................................................................................................................21
3.11 ST function ......................................................................................................................23
REFERENCES ................................................................
................................................................................................
.....................................................................................
..................................................... 26iVer.3

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

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

C:1 block of ciphertext

F{i}: F function of round i (i=0,1,…,15)

L{i}: L function of round i (i=0,1,…,8)

FK{i}[j]: j-th 32-bit extended key for main stream of F{i} (j=0,1)

SK{i}[j]: j-th 32-bit extended key for temporary key generation mechanism of F{i}(j=0,1)

LK{i}[j]: j-th 32-bit extended key for L{i} (j=0,1)

FK{i}: Group of two extended keys for main stream of F{i} (function keys)

SK{i}: Group of two extended keys for temporary key generation mechanism of
F{i} (seed keys)

wk0: 4-bit temporary key

wk1,wk2: 8-bit temporary keys

sh[i][j]: Row-i/column-j element of T function’s input-number table÷ç: Data concatenation∧: Logical product⊕: Exclusive OR (XOR): Addition (mod 232)

x<<n: Left logical shift of x by n bits

x>>n

: Right logical shift of x by n bits

1

Ver.3

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

2

Ver.32 Design Principle and Cri
Criteria
teria
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-E 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.

Block size is 64 bits, the same as that of the Data Encryption Standard (DES), while
secret key length is 128 bits, longer than that of DES. This cipher has been designed forhigh-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 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.1.2 Initial, final, and intermediate 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, and to defend against an attack of
unknown type, 64-bit-wide functions are added before the first round and after the lastround and to every two rounds.

3Ver.3

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.

2.2.3 Temporary key generation mechanism
The 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 possibilityof parallel 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.

4Ver.3

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, two types of operation units areused: 8 and 32 bits.

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} + d
Here:

5

Ver.3matrixA: 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.

6Ver.33 Encryption algorithm
3.1 Total structure
The CIPHERUNICORN-E has a Feistel structure that can use a data block length of
64 bits and a secret key length of 128 bits.
There are 16 rounds with 64-bit-wide processing (L function) performed at every tworound functions (round function means F function).
The key scheduler has a Feistel structure for inputting the secret key. Here, after
shuffling in dummy loops, extended keys are repeatedly extracted while shuffling.
Plain Text
Secret Key 128bits

1blockExtended
Key

Data Randomizer(Encryption)

2624 bits

Key Scheduler

Cipher Text
Figure 3.1 Encryption

Cipher Text
Secret Key 128bits

1blockExtended
Key

Data Randomizer(Decryption)

2624bits

Plain Text
Figure 3.2 Decryption

7

Key Scheduler

Ver.3

3.2 Data randomizer
3.2.1 Encryption[Input]Input]

1 block of plaintext: P =P0÷çP1 (64 bits)
Extended keys for main stream of F function: FK{i} =FK{i} [0] ÷çFK{i} [1] (64bits: i=0,1,…,15)
Extended keys for temporary key generation mechanism of F function:
SK{i} =SK{i}[0] ÷çSK{i}[1] (64 bits: i=0,1,…,15)
Extended keys for L function: LK{j} =LK{j}[0] ÷çLK{j}[1] (64 bits: j=0,1,…,8)[Output] 1 block of ciphertext: C =C0 ÷çC1 (64 bits)
Process]] Shuffling is performed by a 16-round Feistel structure and by an L
[Processfunction that performs 64-bit shuffling every two rounds.

P
LK{0}
L{0}
FK{0},SK{0}F{0}FK{1},SK{1}
F{1}
LK{1}
L{1}
FK{2},SK{2}{2}F

FK{3},SK{3}F{3}FK{15},SK{15}
F{15}
LK{8}
L{8}

C
Figure 3.3 Data randomizer (encryption)

8Ver.33.2.2 Decryption[Input]Input]

1 block of ciphertext: C =C0÷çC1 (64 bits)
Extended keys for main stream of F function: FK{i} =FK{i}[0] ÷çFK{i}[1] (64bits: i=0,1,…,15)
Extended keys for temporary key generation mechanism of F function:
SK{i} =SK{i}[0] ÷çSK{i}[1] (64 bits: i=0,1,…,15)
Extended keys for L function: LK{j} =LK{j}[0] ÷çLK{j}[1] (64 bits: j=0,1,…,8)[Output]
Output] 1 block of plaintext: P =P0÷çP1 (64bits)
Process]] Shuffling is performed by a 16-round Feistel structure and by an L
[Processfunction that performs 64-bit shuffling every two rounds.

C
LK{8}
L{8}
FK{15},SK{15}
F{15}
FK{14},SK{14}
F{14}

LK{7}

L{7}

FK{13},SK{13}{13}

F

FK{12},SK{12}F{12}…
FK{0},SK{0}
F{0}
LK{0}
L{0}

P
Figure 3.4 Data randomizer (decryption)

9Ver.33.3 L function[Input]Input]

Input data: X=XL÷çXR (64 bits)
Extended keys for L{i} function: LK{i} =LK{i}[0] ÷çLK{i}[1] (64 bits)[Output]
Output] Output data: Z=ZL÷çZR (64 bits)[Process] The L function operates on input data and keys according to the following
equations.
ZL=XL⊕(XR∧LK{i}[1])⊕(XL∧LK{i}[0]∧LK{i}[1])ZR=XR⊕(XL∧LK{i}[0])⊕(XR∧LK{i}[0]∧LK{i}[1])LK{i} [0]XL∧

LK{i} [1]

∧

∧

XR

∧

∧

ZL

ZR
Figure 3.5 L function

10Ver.3

3.4 F function[Input] Input data: X (32 bits)
Extended keys for main stream of F{i} function: FK{i} =FK{i}[0] ÷çFK{i}[1] (64bits)
Extended keys for temporary key generation mechanism of F{i} function:
SK{i} =SK{i}[0] ÷çSK{i}[1] (64 bits)[Output] Output data: Z (32 bits)[Process] An F function consists of a main stream section and a temporary key
generation mechanism. After adding in the FK{i}[0] key to 32-bit input data,
the process branches into these two sections. In the main stream section, thefunction executes T functions in input-number order 0, 1, 2, and 3 and thenadds in the FK{i}[1] key. In the following T functions, the input number isdetermined by referencing the Sh table based on wk0. The K function,
moreover, is executed just before each of the last two T functions. The 32-bit
output of the main stream becomes the output of the F function. In thetemporary key generation mechanism, the function adds in the SK{i}[0] key,
executes the Y function (with number of shifts being 3, 8, and 16), andexecutes the T function with input number equal to 0. Then, after adding in
the SK{i}[1] key, the function again executes the Y function (7,9,13) as well as
the T function with input number equal to 0 and 1. In this result, the fourmost significant bits are taken to be wk0, the least significant byte wk1, andthe second lower byte wk2.

11

Ver.3

X

32bitsmain
FK[0]streamT(0)temporary

SK[0]

key

T(1)

Y(3,8,16)

generation
T(2)

T(0)

mechanism

SK[1]

T(3)
Y(7,9,13)

FK[1]T(sh[wk0][0])T(0)T(sh[wk0][1])T(1)T(sh[wk0][2])

wk0

>>28
0xff

T(sh[wk0][3])K(sh[wk0][0])

wk1

∧
0xff

T(sh[wk0][0])K(sh[wk0][1])

wk2

∧

>>8

T(sh[wk0][1])Z
Figure 3.6 F function

12Ver.3

3.5 T function[Input] Input data: X =X0÷çX1÷çX2÷çX3 (32 bits)
Input number: n (n=0,1,2,3)[Output] Output data: Z (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 substitution table.
There are four 8-bit-input/8-bit-output substitution tables denoted as S0, S1,
S2, and S3. The one byte corresponding to the input number uses the output
from the substitution table in question, while the other bytes are exclusive
OR’d with output from the other substitution tables, as shown below.
Z=T(n)Here:
T(0) = S3(X0) ÷ç (S0(X0)⊕X1) ÷ç (S1(X0)⊕X2) ÷ç (S2(X0)⊕X3)
T(1) = (S2(X1)⊕X0) ÷çS3(X1) ÷ç (S0(X1)⊕X2) ÷ç (S1(X1)⊕X3)
T(2) = (S1(X2)⊕X0) ÷ç (S2(X2)⊕X1) ÷çS3(X2) ÷ç (S0(X2)⊕X3)
T(3) = (S0(X3)⊕X0) ÷ç (S1(X3)⊕X1) ÷ç (S2(X3)⊕X2) ÷çS3(X3)
X
X0

S3

X1

S0

X2

S1

S2

X0

X3

S2

S2

X1

S3

X2

S0

Z

T(0)

T(1)

X

X
X2

S3

X3

X1

X0

S0

S0

S1

X2

S2

Z

Z

T(2)

T(3)
Figure 3.7 T function

13

X3

S1

Z

X1

X0

S1

X

X3

S3

Ver.3

3.6 K function[Input] Input data: X =X0÷çX1÷çX2÷çX3 (32 bits)
Input number: n (n=0,1,2,3)
Temporary key: wk=wk1 or wk2 (8 bits)[Output] Output data: Z (32 bits)[Process] The function divides input data into single bytes and performs an exclusive
OR between the byte corresponding to the input number and the temporary
key.
Z=K(n,wk)
Here:K(0,wk) = (X0⊕wk) ÷çX1÷çX2÷çX3
K(1,wk) = X0÷ç (X1⊕wk) ÷çX2÷çX3
K(2,wk) = X0÷çX1÷ç (X2⊕wk) ÷çX3
K(3,wk) = X0÷çX1÷çX2÷ç (X3⊕wk)

14

Ver.3

3.7 Substitution tables[Input]Input data: X (8 bits)[Output] Output data: Z (8 bits)[Process] Data in substitution table Sn at position corresponding to input data is
output.
Z = 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
0 1 0
1 0 0
1 0 1
0 1 0
1 1 0
1 1 0
1 1 1

0
0
1
1
0
1
0
0

0
1
1
0
1
1
0
0

0
1
1
0
0
0
1
1

1
1
0
0
0
0
1
0

1
0
0
1
1
0
0
0

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

15

Ver.3

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

16

Ver.3

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

17

Ver.3

3.8 Sh table[Input] Input data: wk0 (4 bits)
Column number: i (i=0,1,2,3)[Output] Output data: n (n=0,1,2,3)[Process] Data at row wk0 and column i of the Sh table is output to give T-function
input number.
n = Sh[wk0][i]wk0=0,1,…,15 i=0,1,2,3

The Sh table must meet the following conditions.

(1) Elements of row vector (Sh[wk0][0],Sh[wk0][1],Sh[wk0][2],Sh[wk0][3])must be a permutation of 0, 1, 2, and 3.
(2) Row vector (Sh[wk0][0],Sh[wk0][1],Sh[wk0][2],Sh[wk0][3]) must not be arotation of vector (0,1,2,3).
(3) Elements n in column vector (Sh[0][i],Sh[1][i],...,Sh[15][i]) must appear
with equal probability.
For 16 (Sh[wk0][0],Sh[wk0][1],Sh[wk0][2],Sh[wk0][3]) row vectors that satisfy
conditions (1)(2)(3), row number is determined so that, when given a Hamming
weight differential of 1 in wk0, the probability of a differential appearing inSh[wk0][i] is 1/2 if possible. Taking, for example, rows 1 and 2 with elements(0,2,1,3) and (0,2,3,1) for which wk0 differential is 0001(2), we can examine thedifferential in each column and see that there is no differential in columns 0
and 1 while there is one in columns 2 and 3.
Table 3.6 Sh table

Sh =

0
0
0
0
1
1
1
3
3
2
2
3
1
2
2
3

18

2
2
3
3
0
2
3
1
2
0
0
0
3
1
1
1

1
3
1
2
3
0
0
0
1
1
3
2
2
0
3
2

3
1
2
1
2
3
2
2
0
3
1
1
0
3
0
0

Ver.3

3.9 Y function[Input]Input data: X (32 bits)
Input][Constants]
Constants] 2 sets of 3 constants: Const[i][j] (i=0,1 j=0,1,2)[Output] Output data: Z (32 bits)[Process] The function shifts input data by an amount specified by a subset of
constants, and adds the result of this shift to original input data. This
process is repeated two more times using the result of the previous
process as input data.
W0=X+(X<<Const[i][0])W1=W0+(W0<<Const[i][1])Z=W1+(W1<<Const[i][2])Here:(Const[0][0],Const[0][1],Const[0][2])=(3,8,16)(Const[1][0],Const[1][1],Const[1][2])=(7,9,13)

The two sets of three constants are selected according to the following conditions(priority).

(1) Selection of Const[1]Directly after adding in key SK{i}[1] in the temporary key generation
mechanism of the F function:(A) Constants shall be arranged in ascending order, and their values shallbe such that(B) when given a Hamming weight differential of 1, the probability that adifferential appears in each of the 8 bits input to the T function
immediately after Y function (Const[1]) is 1/2 if possible;(C) when given a Hamming weight differential of 2, the probability that adifferential appears in each of the 8 bits input to the T function
immediately after Y function (Const[1]) is 1/2 if possible;(D) when given a Hamming weight differential of 3, the probability that adifferential appears in each of the 16 bits input to the two T functions
immediately after Y function (Const[1]) is 1/2 if possible; and(E) when given a Hamming weight differential of 4, the probability that adifferential appears in each of the 16 bits input to the two T functions
immediately after Y function (Const[1]) is 1/2 if possible.
(2) Selection of Const[0]Here, we use Const[1] left over from (1) above and SK{i}[0]=0 as the key. Thus,
after adding in key SK{i}[0] in the temporary key generation mechanism of the Ffunction:(A) Constants shall be arranged in ascending order, and their values shall19

Ver.3be such that(B) when given a Hamming weight differential of 1, the probability that adifferential appears in each of the 8 bits input to the T function
immediately after Y function (Const[0]) is 1/2 if possible;(C) when given a Hamming weight differential of 1, the probability that adifferential appears in each of the output bits of the temporary key
generation mechanism is 1/2 if possible;(D) when given a Hamming weight differential of 2, the probability that adifferential appears in each of the output bits of the temporary key
generation mechanism is 1/2 if possible;(E) when given a Hamming weight differential of 3, the probability that adifferential appears in each of the output bits of the temporary key
generation mechanism is 1/2 if possible; and(F) treating addition within the Y function as an exclusive OR, as many
input bits to the temporary key generation mechanism as possible shallappear in any of the mechanism’s output bits.

20

Ver.33.10 Key scheduler[Input] Secret Key (128 bits)[Output] Extended keys for main stream of F function: FK{i} (i=0,1,…,15) (64 bits × 16
rounds)Extended keys for temporary key generation mechanism of F function: SK {i}(i=0,1,…,15) (64 bits ×16 rounds)
Extended keys for L function: LK {j} (j=0,1,…,8) (128 bits × 9 rounds)[Process] The key scheduler consists of multiple ST functions (Figure 3.9).
After looping the secret key through the ST function four times, the keyscheduler passes the above result through 32 rounds of the ST function to
generate extended keys.
The order of key generation is shown in Figure 3.8, Figure 3.10, and Figure
3.11. During this process, FK{6~9}[1] is extracted so that the key scheduler
takes on the form of injective mapping.

21

Ver.3

Secret Key 128bits

i=0~3

ST(i)

ST(0)

LK{0}

ST(1)

SK{0}, SK{1}ST(2)FK{0}, FK{1}

ST(3)

LK{1}

ST(0)

SK{2}, SK{3}ST(1)FK{2},FK{3}

ST(1)

LK{3}

ST(2)
See
Fig. 3.11
for details

ST(3)SK{6},FK{6},SK{7},FK{7}
LK{4}

ST(0)

SK{8},FK{8},SK{9},FK{9}

ST(1)
ST(2)

LK{5}

ST(2)

FK{14},FK{15}

ST(3)

LK{8}

Figure 3.8 Key scheduler

22

Ver.33.11 ST function[Input]Input data: X =X0÷çX1÷çX2÷çX3 (128 bits)
Input number: n (n=0,1,2,3)[Output] Output data: Z =Z0÷çZ1÷çZ2÷çZ3 (128 bits)[Process] The ST function has a nested Feistel structure using T functions. The input
number to the T functions is assumed to be in modulo 4.

X0

X1

X2

X3

Z2

Z3

T(n+1)T(n)T(n+2)
T(n+3)

Z0

Z1

Figure 3.9 ST function

23

Ver.3

X0

X1

X2

X3
SK{i}[1]T(n+1)
T(n)SK{i+1}[1]SK{i+1}[0]T(n+2)
T(n+3)

SK{i}[0]

Z0 Z1
Z2 Z3
SK{i}, SK{i+1} extraction (FK extraction is similar)
similar)

X0

X1

X2

X3

T(n+1)
T(n)LK{j}[0]LK{j}[1]T(n+2)
T(n+3)Z0

Z1

LK{j} extraction

Z2

Z3

Figure 3.10 Extended key extraction (1)24Ver.3

X0

X1

X2

X3
SK{6}[1]T

SK{7}[1]TT

SK{6}[0]T

SK{7}[0]FK{6}[0]T

FK{7}[0]T

LK{4}[0]TT

FK{6}[1]FK{8}[1]FK{7}[1]FK{9}[1]T

LK{4}[1]T

SK{9}[1]T{8}

SK [1]

T

SK{8}[0]T{9}SK [0]

T

FK{9}[0]T{8}FK [0]

T

Z0

Z1
Z2 Z3
SK{6~9}, FK{6~9}, LK {4} extraction

Figure 3.11 Extended key extraction (2)25Ver.3

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