Announcement: SAFER SK-64 and SAFER SK-128

[Lars Knudsen]

Announcement

by James L. Massey

of a STRENGTHENED KEY SCHEDULE

for the cipher SAFER

(Secure And Fast Encryption Routine),
for both 64 and 128 bit key lengths.

The original version of "SAFER", which is a non-proprietary cipher
that to the best of my knowledge is free for use by anyone without
violation of any proprietary rights, was called SAFER K-64 to emphasize
that the user-selected key was 64 bits long. This cipher was introduced in
the following paper:

J. L. Massey, "SAFER K-64: A Byte-Oriented Block-Ciphering Algorithm," pp.
1-17 in Fast Software Encryption (Ed. R. Anderson), Lecture Notes in
Computer Science No. 809. New York: Springer, 1994.

Almost immediately after the announcement of this cipher, we began
to receive requests for a modification that would permit the use of a 128
bit key. The length 128 is quite natural because the cipher uses 128 bits
from the key schedule in each round of encryption. A 128 bit key schedule
for SAFER, which has the desirable property that, when the the two halves
of the key are identical, the subkeys produced by this key schedule
coincide with those produced by the key schedule for SAFER K-64, was
proposed by the Special Projects Team of the Ministry of Home Affairs,
Singapore. The designers of this key schedule relinquished all proprietary
rights to this key schedule, which we then accepted as the key schedule for
SAFER K-128. Except for the different subkeys produced by their key
schedules, SAFER K-64 and SAFER K-128 encrypt in exactly the same way.
SAFER K-128 was announced in the following paper:

J. L. Massey, "SAFER K-64: One Year Later," presented at the K. U. Leuven
Workshop on Algorithms, Leuven, Belgium, 14-16 December, 1994, and to
appear in Fast Software Encryption II (Ed. B. Preneel), to be published by
Springer-Verlag in the Lecture Notes in Computer Science Series, 1995.

In the announcement of SAFER K-64, it was recommended to use 6
rounds of encryption and specified that not more than 10 rounds be used.
For SAFER K-128, 10 rounds were recommended and a maximum of 12 rounds was
specified.

Having announced a freely available and non-proprietary cipher, we
consider it our responsibility to inform present and prospective users of
this cipher should any significant weaknesses be found in it. The first
substantial "weakness" of which we are aware was discovered by Lars Knudsen
about February of this year and concerns the use of SAFER for hashing. It
is not uncommon to use secret-key ciphers within a public hashing scheme.
The strength of the cipher for such hashing depends on the difficulty of
producing `collisions', i.e., of finding two distinct plaintext/key pairs
that yield the same ciphertext. When the plaintext and ciphertext are 64
bit strings, the median number of distinct plaintext/key pairs that must be
chosen uniformly at random before such a collision is found is close to
2^(-32). By some very clever cryptanalysis, Knudsen devised a method to
produce such collisions for SIX-round SAFER K-64 after choosing only about
2^(24) distinct plaintext/key pairs, i.e., about 256 times as fast as by
random guessing. (Because SAFER K-128 reduces to SAFER K-64 when the two
halves of the 128-bit key coincide, Knudsen's attack also applies to SAFER
K-128.) Last week in his paper, "A Key-Schedule Weakness in SAFER K-64,"
presented at Crypto '95 in Santa Barbara, California, Knudsen described his
attack. This attack exploits the fact that, for r-round SAFER K-64 and
SAFER K-128, changing one byte of the secret key changes only the byte in
this same position in all 2r + 1 round keys. Two round keys differing in
only one byte will sometimes encrypt a round input to the the same round
output. Knudsen was able to select two secret keys differing in only one
byte in such a way that both keys encrypt between 2^(22) and 2^(28)
plaintexts in the same way for six rounds. This is the phenomenon that he
then exploited to produce collisions about 256 times faster than by random
guessing when SIX-round SAFER K-64 is used within standard hashing schemes.
He also found pairs of secret keys that encrypt about 2^(15) plaintexts in
the same way for EIGHT rounds, but this is not enough to give an advantage
over random guessing in producing collisions. He also determined that
there are NO pairs of secret keys that encrypt many plaintexts in the same
way for TEN or more rounds. Knudsen also showed that this key-schedule
"weakness" could be exploited in a chosen plaintext attack on SIX-round
SAFER K-64 of the so-called related-key type that undesirably often
recovers 8 bits of the key using about 2^(45) chosen plaintexts--this
attack is not very realistic but it seems significant that it arises from
the same key-schedule weakness as does the more realistic hashing attack.

About three months ago, we received an advance copy of the paper,
"An Analysis of SAFER," by Sean Murphy, which has been submitted for
publication to the Journal of Cryptology. In a very elegant analysis,
Murphy showed that there is a rank-4 (i.e., 4 byte) submodule that is
invariant under the Pseudo-Hadamard Transform (PHT) [which is the linear
transformation on eight bytes that is used within SAFER as the primary
mechanism for obtaining diffusion within the cipher] and that this rank-4
submodule depends on only six of the eight input bytes to the PHT.
Because, for r-round SAFER K-64 and SAFER K-128, changing one byte of the
secret key changes only the byte in this same position in all 2r + 1 round
keys, it follows that there is a 4-byte linear function of the plaintext
and a 4-byte linear function of the ciphertext whose joint statistics
depend on only six of the eight key bytes in SAFER K-64 and on only twelve
of the sixteen key bytes in SAFER K-128. This observation does not appear
to lead to any practical attacks on either
SAFER K-64 or SAFER K-128, but it again suggests that it was a bad idea in
the original SAFER key schedules to confine the influence of each byte of
the user-selected key to the subkey bytes in the same position, which is
the same weakness that Knudsen had exploited.

Lightning having struck twice in the same place, we decided that it
would be advisable now to adopt a new key schedule for SAFER, with our
apologies to those users who have already implemented SAFER K-64 and/or
SAFER K-128 in hardware or software, even though no practical attack has
yet been found for SAFER K-64 with 8 or more rounds or for SAFER K-128. In
his paper mentioned above, Knudsen suggested a modification to the earlier
key schedules for SAFER that neutralizes the hashing attaack and
related-key attacks that he had formulated. These modified 64-bit and
128-bit key schedules also remove the weakness found by Murphy in that the
joint statistics mentioned above now depend on all bytes of the key.
Knudsen has given us his written assurance that he relinquishes all
proprietary rights to these modified key schedules and we are thus adopting
them for use with SAFER. To minimize confusion with the old key schedules,
we are calling the ciphers with the new key schedules

SAFER SK-64 and SAFER SK-128

where the "SK" stands for "Strengthened Key schedule". We are also
changing the recommended number of rounds for SAFER SK-64 to 8, with a
minumum of 6 rounds and a maximum of 10 rounds. For SAFER SK-128, we keep
the previous recommendation of 10 rounds with a maximum of 12 rounds.

An innovative feature of Knudsen's key schedules is the addition of
a ninth "parity byte" to the 8 byte user-selected key in SAFER SK-64 and to
each half of the 16 byte user-selected key in SAFER SK-128. This has the
desirable effect of causing two different user-selected keys to differ in
at least two bytes after the expansion with the parity byte. As in the
original key schedule, there is a further rotation within bytes of the
user-selected key before it is added to a "key bias" to produce a round
subkey. New is that the eight bytes selected for addition to the "key
bias" are selected from the nine-byte expanded user-selected key(s) on a
rotating basis, i.e., first bytes 1,2,3,4,5,6,7,8 are used, then bytes
2,3,4,5,6,7,8,9 are used, then bytes 3,4,5,6,7,8,9,1 are used, etc. This
remedies the weakness of the key schedules for SAFER K-64 and SAFER K-128
where changing one byte of the secret key changes only the byte in this
same position in all 2r + 1 round keys.

Attached to this announcement are TURBO PASCAL programs for both
SAFER SK-64 and SAFER SK-128, together with examples of encryption to
assist interested persons in checking their own implementations of these
ciphers. These TURBO PASCAL programs constitute the official description
of the ciphers SAFER SK-64 and SAFER SK-128.

TURBO PASCAL PROGRAM FOR SAFER SK-64

PROGRAM Full_r_Rounds_max_10_of_SAFER_SK64_cipher;

VAR a1, a2, a3, a4, a5, a6, a7, a8, b1, b2, b3, b4, b5, b6,
b7, b8, r: byte;
k: ARRAY[1..21,1..8] OF byte; k1: ARRAY[1..9] OF byte;
logtab, exptab: ARRAY[0..255] OF integer; i, j, n, flag: integer;

PROCEDURE mat1(VAR a1, a2, b1, b2: byte);
BEGIN
b2:= a1 + a2;
b1:= b2 + a1;
END;

PROCEDURE invmat1(VAR a1, a2, b1, b2: byte);
BEGIN
b1:= a1 - a2;
b2:= -b1 + a2;
END;

BEGIN
{This portion of the program computes the powers of the primitive
element 45 of the finite field GF(257) and stores these numbers
in the table "exptab". The corresponding logarithms to the base
45 are stored in the table "logtab".}
logtab[1]:= 0;
exptab[0]:= 1;
FOR i:= 1 TO 255 DO
BEGIN
exptab[i]:= (45 * exptab[i - 1]) mod 257;
logtab[exptab[i]]:= i;
END;
exptab[128]:= 0;
logtab[0]:= 128;
exptab[0]:= 1;

flag:= 0;
writeln;
writeln('Enter number of rounds r (max. 10) desired then hit CR');
readln(r);

REPEAT
BEGIN
writeln;
writeln('Enter plaintext in 8 bytes (a byte is an integer');
writeln('between 0 and 255 incl. with spaces between bytes)');
writeln('then hit CR.');
readln(a1, a2, a3, a4, a5, a6, a7, a8);
writeln('Enter a key in 8 bytes then hit CR.');
readln(k[1,1],k[1,2],k[1,3],k[1,4],k[1,5],k[1,6],k[1,7],k[1,8]);
k1[1]:= k[1,1]; k1[2]:= k[1,2]; k1[3]:= k[1,3]; k1[4]:= k[1,4];
k1[5]:= k[1,5]; k1[6]:= k[1,6]; k1[7]:= k[1,7]; k1[8]:= k[1,8];
writeln;
writeln('PLAINTEXT is ', a1:8,a2:4,a3:4,a4:4,
a5:4,a6:4,a7:4,a8:4);
writeln('The KEY is ', k[1,1]:8,k[1,2]:4,k[1,3]:4,k[1,4]:4,
k[1,5]:4,k[1,6]:4,k[1,7]:4,k[1,8]:4);

{The next instruction appends a "parity byte" to the key K1.}
k1[9] := k1[1] xor k1[2] xor k1[3] xor k1[4] xor
k1[5] xor k1[6] xor k1[7] xor k1[8];
{The next instructions implement the key schedule
needed to derive keys K2, K3, ... K2r+1 from the input key K1.}
FOR n:= 2 TO 2*r+1 DO
BEGIN
{Each byte of the key K1 is further left rotated by 3.}
FOR j:= 1 TO 9 DO k1[j]:= (k1[j] shl 3) + (k1[j] shr 5);
FOR j:= 1 TO 8 DO
BEGIN
{The key bias is added here to the further right rotated K1.}
k[n,j]:= k1[((j+n-2) mod 9) + 1] + exptab[exptab[9*n+j]];
END;
END;

{The r rounds of encryption begin here.}
FOR i:= 1 TO r DO
BEGIN

{Key 2i-1 is mixed bit and byte added to the round input.}
a1:= a1 xor k[2*i-1,1]; a2:= a2 + k[2*i-1,2];
a3:= a3 + k[2*i-1,3]; a4:= a4 xor k[2*i-1,4];
a5:= a5 xor k[2*i-1,5]; a6:= a6 + k[2*i-1,6];
a7:= a7 + k[2*i-1,7]; a8:= a8 xor k[2*i-1,8];

{The result now passes through the nonlinear layer.}
b1:= exptab[a1]; b2:= logtab[a2];
b3:= logtab[a3]; b4:= exptab[a4];
b5:= exptab[a5]; b6:= logtab[a6];
b7:= logtab[a7]; b8:= exptab[a8];

{Key 2i is now mixed byte and bit added to the result.}
b1:= b1 + k[2*i,1]; b2:= b2 xor k[2*i,2];
b3:= b3 xor k[2*i,3]; b4:= b4 + k[2*i,4];
b5:= b5 + k[2*i,5]; b6:= b6 xor k[2*i,6];
b7:= b7 xor k[2*i,7]; b8:= b8 + k[2*i,8];

{The result now enters the linear layer.}
mat1(b1, b2, a1, a2);
mat1(b3, b4, a3, a4);
mat1(b5, b6, a5, a6);
mat1(b7, b8, a7, a8);

mat1(a1, a3, b1, b2);
mat1(a5, a7, b3, b4);
mat1(a2, a4, b5, b6);
mat1(a6, a8, b7, b8);

mat1(b1, b3, a1, a2);
mat1(b5, b7, a3, a4);
mat1(b2, b4, a5, a6);
mat1(b6, b8, a7, a8);

{The round is now completed!}
writeln('after round',i:2,a1:8,a2:4,a3:4,a4:4,
a5:4,a6:4,a7:4,a8:4);
END;

{Key 2r+1 is now mixed bit and byte added to produce the
final cryptogram.}
a1:= a1 xor k[2*r+1,1]; a2:= a2 + k[2*r+1,2];
a3:= a3 + k[2*r+1,3]; a4:= a4 xor k[2*r+1,4];
a5:= a5 xor k[2*r+1,5]; a6:= a6 + k[2*r+1,6];
a7:= a7 + k[2*r+1,7]; a8:= a8 xor k[2*r+1,8];
writeln('CRYPTOGRAM is', a1:8,a2:4,a3:4,a4:4,
a5:4,a6:4,a7:4,a8:4);
writeln;
writeln('Type 0 and CR to continue or -1 and CR to stop run.');
read(flag);
END
UNTIL flag < 0;
END.


EXAMPLES OF ENCRYPTION WITH SAFER SK-64

Examples of Encryption with SAFER SK-64 (i.e., with the strengthened key
schedule of 64 bits.)

PLAINTEXT is 1 2 3 4 5 6 7 8
The KEY is 0 0 0 0 0 0 0 1
after round 1 131 177 53 27 130 249 141 121
after round 2 68 73 32 102 134 54 206 57
after round 3 248 213 217 11 23 68 0 243
after round 4 194 62 109 79 24 18 13 84
after round 5 153 156 246 172 40 72 173 39
after round 6 154 242 34 6 61 35 216 28
CRYPTOGRAM is 21 27 255 2 173 17 191 45

PLAINTEXT is 1 2 3 4 5 6 7 8
The KEY is 1 2 3 4 5 6 7 8
after round 1 223 98 177 100 46 234 13 210
after round 2 182 246 230 93 158 14 48 89
after round 3 45 234 128 149 40 101 10 134
after round 4 30 17 249 236 158 120 69 100
after round 5 1 200 182 241 0 127 152 162
after round 6 144 85 94 214 5 38 65 150
CRYPTOGRAM is 95 206 155 162 5 132 56 199




TURBO PASCAL PROGRAM FOR SAFER SK-128

PROGRAM Full_r_Rounds_max_12_of_SAFER_SK128_cipher;
{Choosing both halves of the key to coincide gives the same result as for
encrypting with this same 64 bit sequence as the key for SAFER SK-64.}

VAR a1, a2, a3, a4, a5, a6, a7, a8, b1, b2, b3, b4, b5, b6, b7, b8, r: byte;
k: ARRAY[1..25,1..8] OF byte; ka: ARRAY[1..9] OF byte;
kb: ARRAY[1..9] OF byte;
logtab, exptab: ARRAY[0..255] OF integer; i, j, flag: integer;

PROCEDURE mat1(VAR a1, a2, b1, b2: byte);
BEGIN b2:= a1 + a2; b1:= b2 + a1; END;

PROCEDURE invmat1(VAR a1, a2, b1, b2: byte);
BEGIN b1:= a1 - a2; b2:= -b1 + a2; END;

BEGIN
{The program here computes the powers of the primitive element 45 of the
finite field GF(257) and stores these in the table "exptab". Corresponding
logarithms to the base 45 are stored in the table "logtab".}
logtab[1]:= 0; exptab[0]:= 1;
FOR i:= 1 TO 255 DO
BEGIN
exptab[i]:= (45 * exptab[i - 1]) mod 257;
logtab[exptab[i]]:= i;
END;
exptab[128]:= 0; logtab[0]:= 128; exptab[0]:= 1;

flag:= 0; writeln;
WRITELN('Enter number of rounds r (max. 12) then hit CR.');
READLN(r);

REPEAT
BEGIN
WRITELN;
WRITELN('Enter plaintext in 8 bytes with spaces');
WRITELN(' between bytes, then hit CR.');
WRITELN('(A byte is an integer between 0 and 255 inclusive.)');
READLN(a1, a2, a3, a4, a5, a6, a7, a8);
WRITELN('Enter left half of key (Ka) in 8 bytes then hit CR.');
READLN(ka[1],ka[2],ka[3],ka[4],ka[5],ka[6],ka[7],ka[8]);
WRITELN('Enter right half of key (Kb) in 8 bytes then hit CR.');
READLN(kb[1],kb[2],kb[3],kb[4],kb[5],kb[6],kb[7],kb[8]);
WRITELN;
WRITELN('Key Ka is', ka[1]:4,ka[2]:4,ka[3]:4,ka[4]:4,
ka[5]:4,ka[6]:4,ka[7]:4,ka[8]:4);
WRITELN('Key Kb is', kb[1]:4,kb[2]:4,kb[3]:4,kb[4]:4,
kb[5]:4,kb[6]:4,kb[7]:4,kb[8]:4);
WRITELN('PLAINTEXT is ', a1:8,a2:4,a3:4,a4:4,a5:4,a6:4,a7:4,a8:4);

{The next instruction appends a "parity byte" to keys Ka and Kb.}
ka[9] := ka[1] xor ka[2] xor ka[3] xor ka[4] xor
ka[5] xor ka[6] xor ka[7] xor ka[8];
kb[9] := kb[1] xor kb[2] xor kb[3] xor kb[4] xor
kb[5] xor kb[6] xor kb[7] xor kb[8];

{The next instructions implement the key schedule
needed to derive keys K1, K2, ... K2r+1 from the
128 bit input key (Ka, Kb).}
{K1 is set equal to Kb.}
FOR j:= 1 TO 8 DO k[1,j]:= kb[j];
{Each byte of the key Ka is right rotated by 3.}
FOR j:= 1 TO 9 DO ka[j]:= (ka[j] shr 3) + (ka[j] shl 5);
FOR i:= 1 TO r DO
BEGIN
{Each byte of keys Ka and Kb is further left rotated by 6.}
FOR j:= 1 TO 9 DO
BEGIN
ka[j]:= (ka[j] shl 6) + (ka[j] shr 2);
kb[j]:= (kb[j] shl 6) + (kb[j] shr 2);
END;
{The key biases are added to give the keys K2i-1 and K2i.}
FOR j:= 1 TO 8 DO
BEGIN
k[2*i,j]:= ka[((j+2*i-2) mod 9) + 1] + exptab[exptab[18*i+j]];
k[2*i+1,j]:= kb[((j+2*i-1) mod 9) + 1] + exptab[exptab[18*i+9+j]];
END;
END;
{The r rounds of encryption begin here.}
FOR i:= 1 TO r DO
BEGIN
{Key 2i-1 is mixed bit and byte added to the round input.}
a1:= a1 xor k[2*i-1,1]; a2:= a2 + k[2*i-1,2];
a3:= a3 + k[2*i-1,3]; a4:= a4 xor k[2*i-1,4];
a5:= a5 xor k[2*i-1,5]; a6:= a6 + k[2*i-1,6];
a7:= a7 + k[2*i-1,7]; a8:= a8 xor k[2*i-1,8];

{The result now passes through the nonlinear layer.}
b1:= exptab[a1]; b2:= logtab[a2]; b3:= logtab[a3]; b4:= exptab[a4];
b5:= exptab[a5]; b6:= logtab[a6]; b7:= logtab[a7]; b8:= exptab[a8];
{Key 2i is now mixed byte and bit added to the result.}
b1:= b1 + k[2*i,1]; b2:= b2 xor k[2*i,2];
b3:= b3 xor k[2*i,3]; b4:= b4 + k[2*i,4];
b5:= b5 + k[2*i,5]; b6:= b6 xor k[2*i,6];
b7:= b7 xor k[2*i,7]; b8:= b8 + k[2*i,8];

{The result now enters the first level of the linear layer.}
mat1(b1, b2, a1, a2); mat1(b3, b4, a3, a4);
mat1(b5, b6, a5, a6); mat1(b7, b8, a7, a8);
{The result now enters the second level of the linear layer.}
mat1(a1, a3, b1, b2); mat1(a5, a7, b3, b4);
mat1(a2, a4, b5, b6); mat1(a6, a8, b7, b8);
{The result now enters the third level of the linear layer.}
mat1(b1, b3, a1, a2); mat1(b5, b7, a3, a4);
mat1(b2, b4, a5, a6); mat1(b6, b8, a7, a8);

{The round is now completed!}
WRITELN('after round',i:2,a1:8,a2:4,a3:4,a4:4,a5:4,a6:4,a7:4,a8:4);
END;

{Key 2r+1 is now mixed bit and byte added to produce the cryptogram.}
a1:= a1 xor k[2*r+1,1]; a2:= a2 + k[2*r+1,2];
a3:= a3 + k[2*r+1,3]; a4:= a4 xor k[2*r+1,4];
a5:= a5 xor k[2*r+1,5]; a6:= a6 + k[2*r+1,6];
a7:= a7 + k[2*r+1,7]; a8:= a8 xor k[2*r+1,8];
WRITELN('CRYPTOGRAM is',a1:8,a2:4,a3:4,a4:4,a5:4,a6:4,a7:4,a8:4); writeln;
WRITELN('Type 0 and CR to continue or -1 and CR to stop run.');
READLN(flag);
END
UNTIL flag < 0;
END.

EXAMPLES OF ENCRYPTION WITH SAFER SK-128

Examples of Encryption with SAFER SK-128 (i.e.,
with the strengthened key schedule of 128 bits.)

PLAINTEXT is 1 2 3 4 5 6 7 8
KEY Ka is 0 0 0 0 0 0 0 1
KEY Kb is 0 0 0 0 0 0 0 1
after round 1 131 177 53 27 130 249 141 121
after round 2 68 73 32 102 134 54 206 57
after round 3 248 213 217 11 23 68 0 243
after round 4 194 62 109 79 24 18 13 84
after round 5 153 156 246 172 40 72 173 39
after round 6 154 242 34 6 61 35 216 28
after round 7 100 31 172 67 44 75 133 219
after round 8 78 226 239 135 210 83 93 72
after round 9 72 64 46 195 163 159 243 114
after round10 3 133 76 190 191 52 220 123
CRYPTOGRAM is 65 76 84 90 182 153 74 247

PLAINTEXT is 1 2 3 4 5 6 7 8
KEY Ka is 1 2 3 4 5 6 7 8
KEY Kb is 0 0 0 0 0 0 0 0
after round 1 64 214 74 216 103 222 26 54
after round 2 61 14 68 15 46 111 124 80
after round 3 197 124 96 59 255 24 2 30
after round 4 63 59 214 103 236 166 153 24
after round 5 66 254 26 45 152 223 5 122
after round 6 89 47 58 105 161 38 135 45
after round 7 19 202 174 44 57 206 52 25
after round 8 78 179 113 208 169 26 121 22
after round 9 53 17 81 215 120 37 206 246
after round10 189 177 9 0 186 82 208 253
CRYPTOGRAM is 255 120 17 228 179 167 46 113

PLAINTEXT is 1 2 3 4 5 6 7 8
KEY Ka is 0 0 0 0 0 0 0 0
KEY Kb is 1 2 3 4 5 6 7 8
after round 1 95 186 209 220 166 66 213 10
after round 2 200 65 189 120 96 135 42 166
after round 3 64 169 43 166 132 171 31 40
after round 4 199 167 76 189 145 158 241 19
after round 5 71 55 184 212 108 198 77 108
after round 6 173 197 139 11 17 48 97 59
after round 7 17 51 142 4 170 7 207 124
after round 8 62 205 253 225 167 179 228 202
after round 9 133 168 127 138 193 243 34 226
after round10 59 194 69 220 220 231 123 148
CRYPTOGRAM is 73 201 157 152 165 188 89 8