[swinard]

I'm having some trouble understanding the "special properties" of the 4th S-Box in the DES cryptographic algorithm. I'm using the text, "Cryptography: Theory and Practice" by Douglas Stinson.

Supposedly, each row can be mapped to any other row in that s-box.

For example, to go from Row 1 to 2, or Row 3 to 4, the following map works for the 4 bits of values of the rows:
(y1, y2, y3, y4) -> (y2, y1, y4, y3) XOR (0, 1, 1, 0)
So, 0->6, 1->4, ..., 15->9

I can see how this works. But for the life of me, I cannot figure out any "similar operations" to go from, say, Row 2 to 3. Does anyone have any knowledge of this? A bit-permutation followed by an XOR (like above) does not work for these rows, as far as I know.

[B-Con]

Supposedly, each row can be mapped to any other row in that s-box.

That's not the *intent* of the s-box, so unless you know that for a fact I would be hesitant to assume that. Note the size of the s-box, each one has 64 values, the number of possibilities for a 6 bit number. The idea behind the s-box is to take a six-digit number, look up it's position in this s-box table, and output the corresponding 4-digit number.

The s-boxes are formatted in 4 rows of 16, but I don't know that there's any direct correlation between rows. The values generated for the s-boxes were done so carefully, by the NSA, actually, but AFIK you're not supposed to be able to correlate all rows of the same s-box to each other. It's possible, when the NSA designed the s-boxes, that they way they did the design only two sets of two rows were chosen to correlate to each other.

Does the book explicitly say that all rows can be mapped to each other in some way?

[swinard]

From the text:

The DES S-box S4 has some unusual properties:
(a). Prove that the second row of S4 can be obtained from the first row by means of the following mapping:
(y1, y2, y3, y4) -> (y2, y1, y4, y3) XOR (0, 1, 1, 0)

(b). Show that any row of S4 can be transformed into any other row by a similar type of operation.

I have verified (a), which also works to map Row 3 to Row 4 (Row 3 is obviously just a permutation of Row 1, as with any other row).

The mapping for Row 2->3, for instance, cannot be of the same form (bit permutation followed by XOR), but I am unable to find any type of mapping/transformation that works.

[B-Con]

Hm, interesting. I've spent some time squinting at rows of binary and have nothing to show for it. I translated the 2nd and 3rd rows into binary:

1101 1000 1011 0101 0110 1111 0000 0011 0100 0111 0010 1100 0010 1010 1110 1001

1010 0110 1001 0000 1100 1011 0111 1101 1111 0001 0011 1110 0101 0010 1000 0100

but found nothing. I was looking for one digit in the 2nd row to always map to, or to the inverse of, it's own value for some position in the third row, but found nothing.

Oddly, consider two mappings (top=2nd row, bottom=3rd row) that I found curious:

1111 0000 

1011 0111

The second mapping requires the presence of an XOR with 3 1s, but the first mapping prohibits that. Unless I'm missing something, my guess would be that you're not looking for something with an XOR like in your first problem.

[Mr.Confuzzled]

Originally Posted by B-Con

Hm, interesting. I've spent some time squinting at rows of binary and have nothing to show for it. I translated the 2nd and 3rd rows into binary:

1101 1000 1011 0101 0110 1111 0000 0011 0100 0111 0010 1100 0010 1010 1110 1001

1010 0110 1001 0000 1100 1011 0111 1101 1111 0001 0011 1110 0101 0010 1000 0100

but found nothing. I was looking for one digit in the 2nd row to always map to, or to the inverse of, it's own value for some position in the third row, but found nothing.

Oddly, consider two mappings (top=2nd row, bottom=3rd row) that I found curious:

1111 0000 

1011 0111

The second mapping requires the presence of an XOR with 3 1s, but the first mapping prohibits that. Unless I'm missing something, my guess would be that you're not looking for something with an XOR like in your first problem.

Hello All. Me and a friend have been puzzled over this as well for quite some time now. We have came to the same conclusions as you before finding this post.

I was wondering if you or anybody else discovered more about this?

The only other thing that we found is that the mapping from Row 2 to Row 3 is a different scheme than the mapping from Row 4 to Row 1, if that is even how Row 1 is generated.

Any Help with this would be awesome. Thanks