[Next] [Up/Previous] [Index]

SAFER (Secure And Fast Encryption Routine)

This algorithm is of interest for several reasons. It is designed for use in software. Unlike DES, or even IDEA, it does not divide the block into parts of which some parts affect others; instead, the plaintext is directly changed by going through S-boxes, which are replaced by their inverses for decryption.

Description of SAFER

SAFER uses eight rounds. The first step for a round is to apply the first subkey for the round to the eight bytes of the block. The operation by which each byte of the subkey is applied to each byte of the block depends on which byte is used: the sequence is

XOR, add, add, XOR, XOR, add, add, XOR

Then, the S-box is used. Those bytes to which the subkey was applied by an XOR go through the regular S-box; those bytes to which it was applied by addition go through the inverse S-box.

The S-boxes:

The regular box represents 45 raised to successive powers modulo 257 (with the modulo 257 result then squeezed into a byte by being taken modulo 256):

  1  45 226 147 190  69  21 174
120   3 135 164 184  56 207  63
  8 103   9 148 235  38 168 107
189  24  52  27 187 191 114 247

 64  53  72 156  81  47  59  85
227 192 159 216 211 243 141 177
255 167  62 220 134 119 215 166
 17 251 244 186 146 145 100 131

241  51 239 218  44 181 178  43
136 209 153 203 140 132  29  20
129 151 113 202  95 163 139  87
 60 130 196  82  92  28 232 160

  4 180 133  74 246  19  84 182 
223  12  26 142 222 224  57 252
 32 155  36  78 169 152 158 171
242  96 208 108 234 250 199 217

  0 212  31 110  67 188 236  83
137 254 122  93  73 201  50 194
249 154 248 109  22 219  89 150
 68 233 205 230  70  66 143  10

193 204 185 101 176 210 198 172
 30  65  98  41  46  14 116  80
  2  90 195  37 123 138  42  91
240   6  13  71 111 112 157 126

 16 206  18  39 213  76  79 214
121  48 104  54 117 125 228 237
128 106 144  55 162  94 118 170
197 127  61 175 165 229  25  97

253  77 124 183  11 238 173  75
 34 245 231 115  35  33 200   5
225 102 221 179  88 105  99  86
 15 161  49 149  23   7  58  40 

Since the second S-box is the inverse of the first, it can be thought of as containing logarithms base 45 modulo 257, although, given the intractability of the discrete logarithm problem, it is not calculated that way directly, but is instead just the inverse of the preceding one:

128   0 176   9  96 239 185 253
 16  18 159 228 105 186 173 248
192  56 194 101  79   6 148 252
 25 222 106  27  93  78 168 130

112 237 232 236 114 179  21 195
255 171 182  71  68   1 172  37
201 250 142  65  26  33 203 211
 13 110 254  38  88 218  50  15

 32 169 157 132 152   5 156 187
 34 140  99 231 197 225 115 198
175  36  91 135 102  39 247  87
244 150 177 183  92 139 213  84

121 223 170 246  62 163 241  17
202 245 209  23 123 147 131 188
189  82  30 235 174 204 214  53
  8 200 138 180 226 205 191 217

208  80  89  63  77  98  52  10
 72 136 181  86  76  46 107 158
210  61  60   3  19 251 151  81
117  74 145 113  35 190 118  42

 95 249 212  85  11 220  55  49
 22 116 215 119 167 230   7 219
164  47  70 243  97  69 103 227
 12 162  59  28 133  24   4  29

 41 160 143 178  90 216 166 126
238 141  83  75 161 154 193  14
122  73 165  44 129 196 199  54
 43 127  67 149  51 242 108 104

109 240   2  40 206 221 155 234
 94 153 124  20 134 207 229  66
184  64 120  45  58 233 100  31
146 144 125  57 111 224 137  48 

Then the second subkey for the round is applied to the block. This time, the sequence of operations complements that used previously:

add, XOR, XOR, add, add, XOR, XOR, add

Then, the different bytes are mixed together without using a bit transpose. Instead, arithmetic is used.

The first byte is replaced by twice the old first byte plus the old second byte. The second byte is replaced by the old first byte plus the second byte. Only the last eight bits of the sums are kept, of course.

This same method of combining the bytes is applied to the third and fourth bytes, the fifth and sixth bytes, and the seventh and eighth bytes.

Then the bytes are interchanged; after the interchange, the order of the bytes becomes

1 3 5 7 2 4 6 8

in terms of which byte each byte was before.

The mixing is performed on pairs of bytes again, and then the interchange, and then the mixing.

After the eighth round, an extra subkey is applied in the same way as the first subkey of each round.

The following diagram illustrates a round of SAFER:

Decryption

Unlike most other block algorithms, SAFER is inverted by doing the reverse of each step, in reverse order, without the possibility of achieving the same result merely by some alteration of the subkeys used.

The reverse of the method of mixing pairs of bytes is this: to get the old first byte, subtract the new second byte from the new first byte. The old second byte is the new second byte minus the old first byte, which is the same as twice the new second byte minus the new first byte.

Subkey generation

In the original version of SAFER, the first 64-bit subkey was the key itself. To generate successive subkeys, the individual bytes of the key were given a circular left shift of 3 bits between the rounds, and the current result is then XORed with a fixed constant for each round.

These constants are:

(for the first subkey, 0)
16733B1E8E70BD86
477E2456F1778846
B1BAA3B7100AC537
C95A28AC64A5ECAB
C66795580DF89AF6
66DC053DD38AC3D8
6AE9364943BFEBD4
9B68A0655D57921F
715CBB22C1BE7BBC
63945F2A61B83432
FDFB1740E6511D41
8F29DD0480DEE731
7F01A2F739DA6F23
FE3AD01CD1303E12
CD0FE0A8AF82592C
7DADB2EFC287CE75
1302904F2E723385
8DCFA981E2C4272F
7A9F52E115382BFC
42C708E409555E8C

The first several constants are given, enough for up to 10 rounds. Originally, six rounds were proposed for SAFER, but this was increased to 8. The constants are also derived mathematically.

SAFER SK

A new version of SAFER, SAFER SK, has a more secure key schedule.

The 64-bit key is expanded by one byte, that byte being the XOR of all the previous bytes. For generating the first subkey, that byte is ignored; for the second, where the key would have been used, one instead takes the eight bytes starting with the second byte of the nine-byte expanded key; for the second, start with the third, and after the ninth go back to the first; and so on.

SAFER SK-40

A 40-bit version of SAFER-SK also exists, with the starting nine-byte expanded key beginning with bytes 1 to 5 being the 40-bit key, and the remaining bytes being, in order:

byte 1 xor byte 3 xor 129
byte 1 xor byte 4 xor byte 5 xor 66
byte 2 xor byte 3 xor byte 5 xor 36
byte 2 xor byte 4 xor 24

SAFER-128, SAFER SK-128

The 128-bit key schedule, both for SAFER and SAFER-SK, consists of using the first subkey and the other odd subkeys from the sequence generated from the right half of the key, and the second and the other even subkeys from the sequence generated from the left half of the key.


[Next] [Up/Previous] [Index]

Next
Chapter Start
Skip to Next Chapter
Table of Contents
Main Page Home Page