From: Matt Blaze <mab@crypto.com>
Date: Thu, 10 Aug 95 01:45:04 PDT
To: cypherpunks@toad.com
Subject: "S-1" key schedule
Message-ID: <199508100853.EAA13204@crypto.com>
MIME-Version: 1.0
Content-Type: text/plain


Well, I have to admit I've been staying up late playing with the "S-1"
cipher that was posted here earlier.  Hal Finney already noted what is
clearly a bug in the code; only half the key schedule is ever used,
and only in the first 16 of the 32 rounds.  Even assuming that that
is a typo rather than intentional, "S-1" still appears to suffer from
key-related weaknesses.

The key expansion function in "S-1" produces a skewed key schedule
given uniformly distributed 80 bit input keys.  Here's a histogram
of the distribution of key schedule bytes produced by all 2^32 ways
of generating each byte (each key schedule byte is a function of the
F functions applied to four selected input keys bytes).  The expected
value for each line is 16777216.  For just about any conventional block
cipher, (e.g., DES) we'd expect this graph to be absolutely flat.  Yet
here some values are more than 5% away from expected.  This behavior
appears to be a consequence of the non-uniform distributon of "S-1"'s
F output values, which are used to create the expanded key.

This does not bode well for "S-1"; it means that some key bytes are
applied against the ciphertext slightly more often than others, even when
the input key itself is uniformly chosen.  (Ditto for the outputs of the F
functions themselves, even when their inputs are uniformly distributed,
but that's still another story).

Still, this may not be fatal; the key schedule is still much larger than
the keyspace, so there might not be any easy way for the cryptanalyst to
exploit this property to any great advantage.  It is possible that the
cipher's structure somehow cancels this out in some non-obvious way
that manages to provide a flat 2^80 keyspace, but it's hard to see
exactly how.

My money still says the "TOP SECRET" markings and other clues that
suggest that "S-1" has something to do with Skipjack are a hoax.

-matt


key   number
val  produced #/exptd
--   -------- -------
00 = 16396100 (0.977) ***************************************************
01 = 16153930 (0.963) **************************************************
02 = 15820450 (0.943) *************************************************
03 = 16197600 (0.965) **************************************************
04 = 16142020 (0.962) **************************************************
05 = 15907790 (0.948) *************************************************
06 = 16300820 (0.972) **************************************************
07 = 16471530 (0.982) ***************************************************
08 = 16439770 (0.980) ***************************************************
09 = 16165840 (0.964) **************************************************
0a = 16126140 (0.961) **************************************************
0b = 16693850 (0.995) ****************************************************
0c = 16503290 (0.984) ***************************************************
0d = 16221420 (0.967) **************************************************
0e = 15931610 (0.950) *************************************************
0f = 16705760 (0.996) ****************************************************
10 = 16933000 (1.009) ****************************************************
11 = 16682900 (0.994) ****************************************************
12 = 16338500 (0.974) ***************************************************
13 = 16728000 (0.997) ****************************************************
14 = 16670600 (0.994) ****************************************************
15 = 16428700 (0.979) ***************************************************
16 = 16834600 (1.003) ****************************************************
17 = 17010900 (1.014) *****************************************************
18 = 16978100 (1.012) *****************************************************
19 = 16695200 (0.995) ****************************************************
1a = 16654200 (0.993) ****************************************************
1b = 17240500 (1.028) *****************************************************
1c = 17043700 (1.016) *****************************************************
1d = 16752600 (0.999) ****************************************************
1e = 16453300 (0.981) ***************************************************
1f = 17252800 (1.028) *****************************************************
20 = 16916480 (1.008) ****************************************************
21 = 16666624 (0.993) ****************************************************
22 = 16322560 (0.973) ***************************************************
23 = 16711680 (0.996) ****************************************************
24 = 16654336 (0.993) ****************************************************
25 = 16412672 (0.978) ***************************************************
26 = 16818176 (1.002) ****************************************************
27 = 16994304 (1.013) *****************************************************
28 = 16961536 (1.011) *****************************************************
29 = 16678912 (0.994) ****************************************************
2a = 16637952 (0.992) ***************************************************
2b = 17223680 (1.027) *****************************************************
2c = 17027072 (1.015) *****************************************************
2d = 16736256 (0.998) ****************************************************
2e = 16437248 (0.980) ***************************************************
2f = 17235968 (1.027) *****************************************************
30 = 16416750 (0.979) ***************************************************
31 = 16174275 (0.964) **************************************************
32 = 15840375 (0.944) *************************************************
33 = 16218000 (0.967) **************************************************
34 = 16162350 (0.963) **************************************************
35 = 15927825 (0.949) *************************************************
36 = 16321350 (0.973) ***************************************************
37 = 16492275 (0.983) ***************************************************
38 = 16460475 (0.981) ***************************************************
39 = 16186200 (0.965) **************************************************
3a = 16146450 (0.962) **************************************************
3b = 16714875 (0.996) ****************************************************
3c = 16524075 (0.985) ***************************************************
3d = 16241850 (0.968) **************************************************
3e = 15951675 (0.951) *************************************************
3f = 16726800 (0.997) ****************************************************
40 = 16908220 (1.008) ****************************************************
41 = 16658486 (0.993) ****************************************************
42 = 16314590 (0.972) **************************************************
43 = 16703520 (0.996) ****************************************************
44 = 16646204 (0.992) ****************************************************
45 = 16404658 (0.978) ***************************************************
46 = 16809964 (1.002) ****************************************************
47 = 16986006 (1.012) *****************************************************
48 = 16953254 (1.010) ****************************************************
49 = 16670768 (0.994) ****************************************************
4a = 16629828 (0.991) ***************************************************
4b = 17215270 (1.026) *****************************************************
4c = 17018758 (1.014) *****************************************************
4d = 16728084 (0.997) ****************************************************
4e = 16429222 (0.979) ***************************************************
4f = 17227552 (1.027) *****************************************************
50 = 17003210 (1.013) *****************************************************
51 = 16752073 (0.999) ****************************************************
52 = 16406245 (0.978) ***************************************************
53 = 16797360 (1.001) ****************************************************
54 = 16739722 (0.998) ****************************************************
55 = 16496819 (0.983) ***************************************************
56 = 16904402 (1.008) ****************************************************
57 = 17081433 (1.018) *****************************************************
58 = 17048497 (1.016) *****************************************************
59 = 16764424 (0.999) ****************************************************
5a = 16723254 (0.997) ****************************************************
5b = 17311985 (1.032) ******************************************************
5c = 17114369 (1.020) *****************************************************
5d = 16822062 (1.003) ****************************************************
5e = 16521521 (0.985) ***************************************************
5f = 17324336 (1.033) ******************************************************
60 = 17147760 (1.022) *****************************************************
61 = 16894488 (1.007) ****************************************************
62 = 16545720 (0.986) ***************************************************
63 = 16940160 (1.010) ****************************************************
64 = 16882032 (1.006) ****************************************************
65 = 16637064 (0.992) ***************************************************
66 = 17048112 (1.016) *****************************************************
67 = 17226648 (1.027) *****************************************************
68 = 17193432 (1.025) *****************************************************
69 = 16906944 (1.008) ****************************************************
6a = 16865424 (1.005) ****************************************************
6b = 17459160 (1.041) ******************************************************
6c = 17259864 (1.029) *****************************************************
6d = 16965072 (1.011) *****************************************************
6e = 16661976 (0.993) ****************************************************
6f = 17471616 (1.041) ******************************************************
70 = 16792580 (1.001) ****************************************************
71 = 16544554 (0.986) ***************************************************
72 = 16203010 (0.966) **************************************************
73 = 16589280 (0.989) ***************************************************
74 = 16532356 (0.985) ***************************************************
75 = 16292462 (0.971) **************************************************
76 = 16694996 (0.995) ****************************************************
77 = 16869834 (1.006) ****************************************************
78 = 16837306 (1.004) ****************************************************
79 = 16556752 (0.987) ***************************************************
7a = 16516092 (0.984) ***************************************************
7b = 17097530 (1.019) *****************************************************
7c = 16902362 (1.007) ****************************************************
7d = 16613676 (0.990) ***************************************************
7e = 16316858 (0.973) **************************************************
7f = 17109728 (1.020) *****************************************************
80 = 16920610 (1.009) ****************************************************
81 = 16670693 (0.994) ****************************************************
82 = 16326545 (0.973) ***************************************************
83 = 16715760 (0.996) ****************************************************
84 = 16658402 (0.993) ****************************************************
85 = 16416679 (0.979) ***************************************************
86 = 16822282 (1.003) ****************************************************
87 = 16998453 (1.013) *****************************************************
88 = 16965677 (1.011) *****************************************************
89 = 16682984 (0.994) ****************************************************
8a = 16642014 (0.992) ****************************************************
8b = 17227885 (1.027) *****************************************************
8c = 17031229 (1.015) *****************************************************
8d = 16740342 (0.998) ****************************************************
8e = 16441261 (0.980) ***************************************************
8f = 17240176 (1.028) *****************************************************
90 = 17416210 (1.038) ******************************************************
91 = 17158973 (1.023) *****************************************************
92 = 16804745 (1.002) ****************************************************
93 = 17205360 (1.026) *****************************************************
94 = 17146322 (1.022) *****************************************************
95 = 16897519 (1.007) ****************************************************
96 = 17315002 (1.032) ******************************************************
97 = 17496333 (1.043) ******************************************************
98 = 17462597 (1.041) ******************************************************
99 = 17171624 (1.024) *****************************************************
9a = 17129454 (1.021) *****************************************************
9b = 17732485 (1.057) *******************************************************
9c = 17530069 (1.045) ******************************************************
9d = 17230662 (1.027) *****************************************************
9e = 16922821 (1.009) ****************************************************
9f = 17745136 (1.058) *******************************************************
a0 = 17581410 (1.048) ******************************************************
a1 = 17321733 (1.032) ******************************************************
a2 = 16964145 (1.011) *****************************************************
a3 = 17368560 (1.035) ******************************************************
a4 = 17308962 (1.032) ******************************************************
a5 = 17057799 (1.017) *****************************************************
a6 = 17479242 (1.042) ******************************************************
a7 = 17662293 (1.053) *******************************************************
a8 = 17628237 (1.051) *******************************************************
a9 = 17334504 (1.033) ******************************************************
aa = 17291934 (1.031) ******************************************************
ab = 17900685 (1.067) *******************************************************
ac = 17696349 (1.055) *******************************************************
ad = 17394102 (1.037) ******************************************************
ae = 17083341 (1.018) *****************************************************
af = 17913456 (1.068) *******************************************************
b0 = 17048640 (1.016) *****************************************************
b1 = 16796832 (1.001) ****************************************************
b2 = 16450080 (0.981) ***************************************************
b3 = 16842240 (1.004) ****************************************************
b4 = 16784448 (1.000) ****************************************************
b5 = 16540896 (0.986) ***************************************************
b6 = 16949568 (1.010) ****************************************************
b7 = 17127072 (1.021) *****************************************************
b8 = 17094048 (1.019) *****************************************************
b9 = 16809216 (1.002) ****************************************************
ba = 16767936 (0.999) ****************************************************
bb = 17358240 (1.035) ******************************************************
bc = 17160096 (1.023) *****************************************************
bd = 16867008 (1.005) ****************************************************
be = 16565664 (0.987) ***************************************************
bf = 17370624 (1.035) ******************************************************
c0 = 16705850 (0.996) ****************************************************
c1 = 16459105 (0.981) ***************************************************
c2 = 16119325 (0.961) **************************************************
c3 = 16503600 (0.984) ***************************************************
c4 = 16446970 (0.980) ***************************************************
c5 = 16208315 (0.966) **************************************************
c6 = 16608770 (0.990) ***************************************************
c7 = 16782705 (1.000) ****************************************************
c8 = 16750345 (0.998) ****************************************************
c9 = 16471240 (0.982) ***************************************************
ca = 16430790 (0.979) ***************************************************
cb = 17009225 (1.014) *****************************************************
cc = 16815065 (1.002) ****************************************************
cd = 16527870 (0.985) ***************************************************
ce = 16232585 (0.968) **************************************************
cf = 17021360 (1.015) *****************************************************
d0 = 16949520 (1.010) ****************************************************
d1 = 16699176 (0.995) ****************************************************
d2 = 16354440 (0.975) ***************************************************
d3 = 16744320 (0.998) ****************************************************
d4 = 16686864 (0.995) ****************************************************
d5 = 16444728 (0.980) ***************************************************
d6 = 16851024 (1.004) ****************************************************
d7 = 17027496 (1.015) *****************************************************
d8 = 16994664 (1.013) *****************************************************
d9 = 16711488 (0.996) ****************************************************
da = 16670448 (0.994) ****************************************************
db = 17257320 (1.029) *****************************************************
dc = 17060328 (1.017) *****************************************************
dd = 16768944 (1.000) ****************************************************
de = 16469352 (0.982) ***************************************************
df = 17269632 (1.029) *****************************************************
e0 = 16953650 (1.011) ****************************************************
e1 = 16703245 (0.996) ****************************************************
e2 = 16358425 (0.975) ***************************************************
e3 = 16748400 (0.998) ****************************************************
e4 = 16690930 (0.995) ****************************************************
e5 = 16448735 (0.980) ***************************************************
e6 = 16855130 (1.005) ****************************************************
e7 = 17031645 (1.015) *****************************************************
e8 = 16998805 (1.013) *****************************************************
e9 = 16715560 (0.996) ****************************************************
ea = 16674510 (0.994) ****************************************************
eb = 17261525 (1.029) *****************************************************
ec = 17064485 (1.017) *****************************************************
ed = 16773030 (1.000) ****************************************************
ee = 16473365 (0.982) ***************************************************
ef = 17273840 (1.030) *****************************************************
f0 = 16573690 (0.988) ***************************************************
f1 = 16328897 (0.973) ***************************************************
f2 = 15991805 (0.953) *************************************************
f3 = 16373040 (0.976) ***************************************************
f4 = 16316858 (0.973) **************************************************
f5 = 16080091 (0.958) **************************************************
f6 = 16477378 (0.982) ***************************************************
f7 = 16649937 (0.992) ****************************************************
f8 = 16617833 (0.991) ***************************************************
f9 = 16340936 (0.974) ***************************************************
fa = 16300806 (0.972) **************************************************
fb = 16874665 (1.006) ****************************************************
fc = 16682041 (0.994) ****************************************************
fd = 16397118 (0.977) ***************************************************
fe = 16104169 (0.960) **************************************************
ff = 16886704 (1.007) ****************************************************