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.
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 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:
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.
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.
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
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
Chapter Start
Skip to Next Chapter
Table of Contents
Main Page
Home Page