18
$\begingroup$

I'm trying to understand DES and a bunch of other cryptographic systems using S-Boxes.

I have now a quite basic question about how Sboxes work in general. For DES, Sboxes are substituting a 6-bits input for 4-bits output. It is clear for me how this works using the suitable substitution table. What I don't understand though is how the cryptosystem deals with the "loss of information" (at least it seems for me to be a loss of information, but I might be wrong).

If you map 6 bits on 4 you lose information. So there might be more than one 6-bit combination which is mapped on the identical 4-bit combination. As a consequence, after the S-box operation it seems for me that it is not possible to get the original 6 bits again out of your 4-bit result. How is it possible then to decrypt your ciphertext again?

$\endgroup$
12
$\begingroup$

Good question and yes, it would appear that data is lost. And technically, something clearly must disappear as 6 don't go into 4. But consider the overall architecture of DES:

DES overall

Trace the flow of the left and right halves of an individual block of data. You'll see that the 2 full 32 bit words flow unimpeded down though the Feistel network. No information is lost there, it's only XORed with, maintaining the width. So 64 bits go into the block, and 64 bits emerge.

You're actually referring to the internals of the DES cipher function which looks like:-

DES function

and you can identify the s boxes. They indeed accept 6 bits and output 4, so something is lost due to the pigeon principle. But look at the expansion box above the s boxes. Additional bits are created due the permutation, P. So what is lost, never really existed but was created within (and localised to) the cipher function. So similarly for the cipher function, 32 bits go in and 32 bits come out.

The reason this works can be considered by analogy, but don't take it too far. Consider a single round. DES's cipher function operates as a small pseudo random number generator keyed off a sub-key (round key) and the other half of the block's 32 bit data. That is then XORed with the original data to encipher it. The streams then swap and the round functions repeat. So as a (kind of) pseudo random number generator, the cipher function doesn't have to be invertible.

You could actually re-engineer DES using off the shelf hash functions like MD5 or SHA1 (both truncated to 32 bits) to see that transcoding is still possible. It's a common theme in cryptography to consider hash functions as the basis of ciphers, and some more insight can be found with the questions Construct an encryption algorithm using hash function. (I don't know how to handle the 3 way duplicates.)

Designers of these things tend to reflect the key schedule with the main algorithm. Whirlpool is similarly symmetric. I suspect that this was the only way the designers could think to easily expand a 64 bit key using a similar geometry to the main part, and still XOR with 32 bit half blocks. Hence they invented 48 bit sub keys. There's no specific reason on Earth to have 48 bit round keys. They could have been 32 bits and that would have made asymmetric 6 to 4 bit s boxes unnecessary.

$\endgroup$
  • $\begingroup$ For DES choosing 6 inputs and 4 outputs might have been to fit in the expansion permutation (with the goal of creating a faster avalanche effect of the plain text). $\endgroup$ – daniel Oct 5 '17 at 9:38
  • 1
    $\begingroup$ Also the document by D. Coppersmith that says: (This was the largest size that we could accommodate and still fit all of DES onto a single chip in 1974 technology.) So maybe thats why they didn't make s-boxes bigger, 256 bytes of s-box data might have been 'big' back then already. I was going to make this a question but didn't have a good, thing, so I tacked it on as a comment here. $\endgroup$ – daniel Oct 5 '17 at 9:40
8
$\begingroup$

DES uses a Feistel network. The S-box results gets XOR-ed with the other half so no information is lost. It doesn't need to be invertible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.