Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
February 12th, 2008, 02:16 AM
 swinard
Registered User

Join Date: Feb 2008
Posts: 3
Time spent in forums: 50 m 33 sec
Reputation Power: 0
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.

#2
February 12th, 2008, 05:23 PM
 B-Con
Crypto-Con

Join Date: Apr 2004
Location: Frisco, Texas
Posts: 6,704
Time spent in forums: 1 Month 6 Days 6 h 45 m 21 sec
Reputation Power: 1235
Quote:
 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?
__________________
- "Cryptographically secure linear feedback shift register based stream ciphers" -- a phrase that'll get any party started.
- Why know the ordinary when you can understand the extraordinary?
)

#3
February 12th, 2008, 05:32 PM
 swinard
Registered User

Join Date: Feb 2008
Posts: 3
Time spent in forums: 50 m 33 sec
Reputation Power: 0
From the text:

Quote:
 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.

#4
February 13th, 2008, 03:45 PM
 B-Con
Crypto-Con

Join Date: Apr 2004
Location: Frisco, Texas
Posts: 6,704
Time spent in forums: 1 Month 6 Days 6 h 45 m 21 sec
Reputation Power: 1235
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:
Code:
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:
Code:
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.

#5
May 8th, 2011, 06:50 PM
 Mr.Confuzzled
Registered User

Join Date: May 2011
Posts: 1
Time spent in forums: 12 m 10 sec
Reputation Power: 0
Quote:
 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: Code: 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: Code: 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.

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

 Viewing: Dev Shed Forums > System Administration > Security and Cryptography > Crypto Algorithm Question - DES - Properties of the 4th S-Box?