adamj@web5h.berkeley.edu (Adam J. Richter) (02/10/88)
Here's a note for you cryptography wizards out there.
Assuming that there isn't some kind of bug in the program I used to
deduce this, I think I've found an interesting property of the
S-boxes. I have no idea how this might be useful and I have no idea
whether this property is a strength of DES, a weakness of DES, an
irrelevant artifact of DES, or a bug in my program. (Source code is
at the end.)
Consider the following question. For s-box S, input bit I,
and output bit O, how many input bit combinations that have input bit
I set result in output bit O being set, for s-box S? (Or, "how many
input-ouptput pairs for s-box S have both input bit I and output bit O
set?")
The average should be 16. Half of the 64 6-bit inputs will
have input bit I set and an average of half of those comibinations
should result in output bit O being one; half will result in output
bit O being zero.
It seems that the last two input bits of *ALL* the s-boxes
follow this prediction exactly, as does the 3rd-to-the-last input bit
of the last s-box and the first bit of the second. There are plenty
of other combinations for which there is a 50/50 chance of input bit I
being set, given that output bit O of s-box S is also set. However,
there are no other places where all output bits for some input bit, or
all input bits for some output bit, have this property.
The next page is the output of my program, editted for
readability. I've seperated the last two input bits to illustrate my
point. The page after the next is the source code to the program that
generated the table. (I've edited the output a bit.) A bug in the
program is not unlikely. I played with DES a few months ago and then
found other things to do.
--Adam J. Richter
adamj@widow.berkeley.edu
In how many of the possible input combinations are both input
bit I and output bit O set?
Input bit (I): 0 1 2 3 4 5
S-box 0:
output bit 0: 15 17 18 17 16 16
output bit 1: 15 15 15 17 16 16
output bit 2: 15 15 13 15 16 16
output bit 3: 17 15 14 16 16 16
S-box 1:
output bit 0: 16 15 16 16 16 16
output bit 1: 16 17 17 14 16 16
output bit 2: 16 17 15 16 16 16
output bit 3: 16 16 15 16 16 16
S-box 2:
output bit 0: 17 14 16 16 16 16
output bit 1: 15 16 19 17 16 16
output bit 2: 16 17 16 17 16 16
output bit 3: 16 16 15 17 16 16
S-box 3:
output bit 0: 16 15 14 15 16 16
output bit 1: 18 15 16 15 16 16
output bit 2: 18 15 16 17 16 16
output bit 3: 16 17 18 15 16 16
S-box 4:
output bit 0: 18 17 16 17 16 16
output bit 1: 15 15 17 15 16 16
output bit 2: 15 16 16 16 16 16
output bit 3: 18 16 15 16 16 16
S-box 5:
output bit 0: 16 16 17 17 16 16
output bit 1: 16 17 15 16 16 16
output bit 2: 17 17 14 16 16 16
output bit 3: 17 17 17 14 16 16
S-box 6:
output bit 0: 16 16 14 15 16 16
output bit 1: 17 17 16 17 16 16
output bit 2: 18 16 15 16 16 16
output bit 3: 17 18 14 15 16 16
S-box 7:
output bit 0: 17 15 16 16 16 16
output bit 1: 16 15 17 16 16 16
output bit 2: 15 16 16 16 16 16
output bit 3: 15 17 15 16 16 16
[The rest of this posting is source code. Hitting "n"
now would be a good idea.]
------------------------------ CUT HERE ------------------------------------
static char S[8][64] = {
14, 4,13, 1, 2,15,11, 8, 3,10, 6,12, 5, 9, 0, 7,
0,15, 7, 4,14, 2,13, 1,10, 6,12,11, 9, 5, 3, 8,
4, 1,14, 8,13, 6, 2,11,15,12, 9, 7, 3,10, 5, 0,
15,12, 8, 2, 4, 9, 1, 7, 5,11, 3,14,10, 0, 6,13,
15, 1, 8,14, 6,11, 3, 4, 9, 7, 2,13,12, 0, 5,10,
3,13, 4, 7,15, 2, 8,14,12, 0, 1,10, 6, 9,11, 5,
0,14, 7,11,10, 4,13, 1, 5, 8,12, 6, 9, 3, 2,15,
13, 8,10, 1, 3,15, 4, 2,11, 6, 7,12, 0, 5,14, 9,
10, 0, 9,14, 6, 3,15, 5, 1,13,12, 7,11, 4, 2, 8,
13, 7, 0, 9, 3, 4, 6,10, 2, 8, 5,14,12,11,15, 1,
13, 6, 4, 9, 8,15, 3, 0,11, 1, 2,12, 5,10,14, 7,
1,10,13, 0, 6, 9, 8, 7, 4,15,14, 3,11, 5, 2,12,
7,13,14, 3, 0, 6, 9,10, 1, 2, 8, 5,11,12, 4,15,
13, 8,11, 5, 6,15, 0, 3, 4, 7, 2,12, 1,10,14, 9,
10, 6, 9, 0,12,11, 7,13,15, 1, 3,14, 5, 2, 8, 4,
3,15, 0, 6,10, 1,13, 8, 9, 4, 5,11,12, 7, 2,14,
2,12, 4, 1, 7,10,11, 6, 8, 5, 3,15,13, 0,14, 9,
14,11, 2,12, 4, 7,13, 1, 5, 0,15,10, 3, 9, 8, 6,
4, 2, 1,11,10,13, 7, 8,15, 9,12, 5, 6, 3, 0,14,
11, 8,12, 7, 1,14, 2,13, 6,15, 0, 9,10, 4, 5, 3,
12, 1,10,15, 9, 2, 6, 8, 0,13, 3, 4,14, 7, 5,11,
10,15, 4, 2, 7,12, 9, 5, 6, 1,13,14, 0,11, 3, 8,
9,14,15, 5, 2, 8,12, 3, 7, 0, 4,10, 1,13,11, 6,
4, 3, 2,12, 9, 5,15,10,11,14, 1, 7, 6, 0, 8,13,
4,11, 2,14,15, 0, 8,13, 3,12, 9, 7, 5,10, 6, 1,
13, 0,11, 7, 4, 9, 1,10,14, 3, 5,12, 2,15, 8, 6,
1, 4,11,13,12, 3, 7,14,10,15, 6, 8, 0, 5, 9, 2,
6,11,13, 8, 1, 4,10, 7, 9, 5, 0,15,14, 2, 3,12,
13, 2, 8, 4, 6,15,11, 1,10, 9, 3,14, 5, 0,12, 7,
1,15,13, 8,10, 3, 7, 4,12, 5, 6,11, 0,14, 9, 2,
7,11, 4, 1, 9,12,14, 2, 0, 6,10,13,15, 3, 5, 8,
2, 1,14, 7, 4,10, 8,13,15,12, 9, 0, 3, 5, 6,11,
};
static char flagTable[64][16]; /* from,to */
static char numOnes[6][4]; /* frombit, tobit */
void ClearOnesTable ()
{
int frombit, tobit;
for (frombit = 0; frombit < 6; frombit++)
for (tobit = 0; tobit < 4; tobit++)
numOnes[frombit][tobit] = '\0';
}
void BuildOnesTable (sbox)
int sbox;
{
int frombit, tobit;
int from;
for (frombit = 0; frombit < 6; frombit++) {
int frommask = 1 << frombit;
for (tobit = 0; tobit < 4; tobit++) {
int tomask = 1 << tobit;
for (from = 0; from < 64; from++)
if ((from & frommask) && (S[sbox][from] & tomask))
numOnes[frombit][tobit]++;
}
}
}
void PrintOnesTable_Vertically ()
{
int frombit, tobit;
for (frombit = 0; frombit < 6; frombit++) {
int total_to = -64;
printf ("from bit %d: ", frombit);
for (tobit = 0; tobit < 4; tobit++) {
printf (" %d", numOnes[frombit][tobit]);
total_to += numOnes [frombit][tobit];
}
printf (" (%d)", total_to);
printf ("\n");
}
}
void PrintOnesTable_Horizontally ()
{
int frombit, tobit;
for (tobit = 0; tobit < 4; tobit++) {
int total_from = -16*6;
printf ("output bit %d: ", tobit);
for (frombit = 0; frombit < 6; frombit++) {
printf (" %d", numOnes[frombit][tobit]);
total_from += numOnes [frombit][tobit];
}
printf (" (%2d)", total_from);
printf ("\n");
}
}
void DoOnesTable (sbox)
int sbox;
{
ClearOnesTable ();
BuildOnesTable (sbox);
printf ("S-box %d:\n", sbox);
PrintOnesTable_Horizontally ();
}
void ClearFlagTable ()
{
int from, to;
for (from = 0; from < 64; from++)
for (to = 0; to < 16; to++)
flagTable[from][to] = 0;
}
void AddFlagTable (boxNum)
int boxNum;
{
int from, to;
for (from = 0; from < 64; from++) {
to = S [boxNum][from];
flagTable [from][to]++;
}
}
void DisplayVertically ()
{
int from, to;
for (from = 0; from < 64; from++) {
if (from < 10)
printf (" %d: ", from);
else
printf ("%d: ", from);
for (to = 0; to < 16; to++)
if (flagTable[from][to])
printf ("%x", flagTable[from][to]);
else
printf (" ");
printf ("\n");
}
}
void DisplayHorizontally ()
{
int from, to;
for (to = 0; to < 16; to++) {
if (to < 10)
printf (" %d: ", to);
else
printf ("%d: ", to);
for (from = 0; from < 64; from++) {
if (flagTable[from][to])
printf ("%x", flagTable[from][to]);
else
printf (" ");
}
printf ("\n");
}
}
int TotalDistance (to)
int to;
{
int from;
int result = 0;
for (from = 0; from < 64; from++)
result += flagTable [from][to]*from;
return result;
}
main (argc, argv)
int argc;
char **argv;
{
int sbox;
for (sbox = 0; sbox < 8; sbox++)
DoOnesTable (sbox);
}
Adam J. Richter adamj@widow.berkeley.edu
....!ucbvax!widow!adamj
Home: (415)549-6377
Sun room: (415)642-7762lindsay@kelpie.newcastle.ac.uk (Lindsay F. Marshall) (02/15/88)
One of the crytopgraphy gurus (I cant remember which one) published a paper on this last year. He showed the regularity, but couldnt find a way to compromise DES using it. Lindsay -- Lindsay F. Marshall, Computing Lab., U of Newcastle upon Tyne, Tyne & Wear, UK ARPA: lindsay%cheviot.newcastle@nss.cs.ucl.ac.uk JANET: lindsay@uk.ac.newcastle.cheviot UUCP: <UK>!ukc!cheviot!lindsay