Crypto Algorithm Question - DES - Properties of the 4th S-Box?

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.

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?

From the text:



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.

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:

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:

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