#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2011
    Posts
    31
    Rep Power
    4

    Reproduce an S-Box


    Someone is able to explain in detail the construction and operation of the DES S-Box, which from n input bits input, produces an output of m bits, with m <n?
    How can I get these properties?
    The process is reversible? How can I get the initial bits from those produced by the S-Box?

    Thanks in advance for your answers.
  2. #2
  3. I'm Baaaaaaack!
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Jul 2003
    Location
    Maryland
    Posts
    5,538
    Rep Power
    244
    I don't recall the details, but there is plenty of open source code on the 'net. The starting conditions of the box is not random, but is fixed. There was a lot of effort that went into choosing the best starting bits, so don't just make up your own. Single DES (the original algorithm) is considered highly broken and shouldn't be used for anything. Triple DES is considered weak and is generally accepted (if I recall correctly) as being able to be brute forced within a week, but is typically used for on-line finance transactions that only need to be secure for a few minutes, so is still regularlly used. If you want to secure something long-term (decades or longer) do NOT use DES or triple DES. AES, particularlly the higher bit versions, is considered safe even against the efforts of nation states. There are other algorithms that are also considered safe (Blowfish comes immediately to mind), but never implement your own version, _always_ use an open source version that has been vetted and is in wide use. OpenSSH, if I recall, has all the common algorithms implemented and is a widly used tool and thus has been vetted by experienced people.

    If you are just monkeying around, then you shouldn't be asking anyone, you should be figuring it out yourself.

    My blog, The Fount of Useless Information http://sol-biotech.com/wordpress/
    Free code: http://sol-biotech.com/code/.
    Secure Programming: http://sol-biotech.com/code/SecProgFAQ.html.
    Performance Programming: http://sol-biotech.com/code/PerformanceProgramming.html.
    LinkedIn Profile: http://www.linkedin.com/in/keithoxenrider

    It is not that old programmers are any smarter or code better, it is just that they have made the same stupid mistake so many times that it is second nature to fix it.
    --Me, I just made it up

    The reasonable man adapts himself to the world; the unreasonable one persists in trying to adapt the world to himself. Therefore, all progress depends on the unreasonable man.
    --George Bernard Shaw
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2011
    Posts
    31
    Rep Power
    4
    I only can't understand how you can produce an output smaller then the input and then obtain again the starting bits.
  6. #4
  7. I'm Baaaaaaack!
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Jul 2003
    Location
    Maryland
    Posts
    5,538
    Rep Power
    244
    Conceptually encryption is nothing more complex than xor-ing the bits of the plaintext data with a bitstream from a pseudo random number generator (prng). There are all sorts of fancy ways of making it look different, but that is how it all boils down. If you have a very 'strong' prng then you have a very difficult cypher to break. It has been years (likely a decade if I thought about it) since I had to be responsible for knowing the guts of DES (or any other algorithm), so I am speaking from fuzzy memory, but what I (think) I recall is that the s-box took the bits of the previous input and used it to generate a new series of bits in much the same way that a prng works. A prng takes a single seed and delivers a long series of non-repeating (apparently) random numbers (the very best don't repeat for huge intervals, like 2^128), but you could look at the s-box injection as reseeding the prng. It is all about what you are familiar with, I studied prngs before I started to learn about encryption algorithms, so I relate best to those analogies.

    My blog, The Fount of Useless Information http://sol-biotech.com/wordpress/
    Free code: http://sol-biotech.com/code/.
    Secure Programming: http://sol-biotech.com/code/SecProgFAQ.html.
    Performance Programming: http://sol-biotech.com/code/PerformanceProgramming.html.
    LinkedIn Profile: http://www.linkedin.com/in/keithoxenrider

    It is not that old programmers are any smarter or code better, it is just that they have made the same stupid mistake so many times that it is second nature to fix it.
    --Me, I just made it up

    The reasonable man adapts himself to the world; the unreasonable one persists in trying to adapt the world to himself. Therefore, all progress depends on the unreasonable man.
    --George Bernard Shaw
  8. #5
  9. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,643
    Rep Power
    4248
    Originally Posted by mitakeet
    I don't recall the details, but there is plenty of open source code on the 'net. The starting conditions of the box is not random, but is fixed. There was a lot of effort that went into choosing the best starting bits, so don't just make up your own.
    Yep, there was a very good reason why they picked those specific values for the S-boxes. For years, a rumor persisted that the NSA had picked those values because they had a secret way to recover the key. The real reason was only revealed many years later. It turned out that when the public discovered the concept of differential cryptanalysis, someone noticed that the initial values chosen for the S-boxes made DES exceptionally resistant to differential cryptanalysis and if they'd changed a couple of values or changed the algorithm slightly, then it would become much easier to crack.

    That's when one of the designers at IBM came clean. It turned out that the IBM guys were aware of differential cryptanalysis many years before the general public (and when they showed their discovery to the NSA, they found that the NSA also knew about this technique a few years before the IBM guys discovered it) and had deliberately designed DES to be resistant to it. After talks with the NSA, it was decided that if they showed the design ideas behind DES, it might also reveal the techniques of differential cryptanalysis, which might weaken the ability of America to break other countries codes. Hence, they didn't reveal why they picked those particular S-box values and their thought process behind it.
    Last edited by Scorpions4ever; October 30th, 2012 at 06:02 PM.
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2011
    Posts
    31
    Rep Power
    4
    I agree with your reasoning, but currently I'm not focusing on the algorithm DES or its S-Box specifically, but I'm interested in the method that allows to obtain from an input a smaller output through which you can later retrieve the original bits.
  12. #7
  13. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2011
    Posts
    31
    Rep Power
    4
    If the function E expands the block, after the key is applied to the block and the function S reduces the block, if the two functions don't match, S is the inverse of E, how is it possible that the process is reversible ?
  14. #8
  15. I'm Baaaaaaack!
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Jul 2003
    Location
    Maryland
    Posts
    5,538
    Rep Power
    244
    You are probably much better off exploring a forum devoted to encryption, or at least math.

    My blog, The Fount of Useless Information http://sol-biotech.com/wordpress/
    Free code: http://sol-biotech.com/code/.
    Secure Programming: http://sol-biotech.com/code/SecProgFAQ.html.
    Performance Programming: http://sol-biotech.com/code/PerformanceProgramming.html.
    LinkedIn Profile: http://www.linkedin.com/in/keithoxenrider

    It is not that old programmers are any smarter or code better, it is just that they have made the same stupid mistake so many times that it is second nature to fix it.
    --Me, I just made it up

    The reasonable man adapts himself to the world; the unreasonable one persists in trying to adapt the world to himself. Therefore, all progress depends on the unreasonable man.
    --George Bernard Shaw

IMN logo majestic logo threadwatch logo seochat tools logo