Forgot your password?
typodupeerror
Encryption Security IT

17% Smaller DES S-box Circuits Found 45

Posted by Soulskill
from the still-bigger-than-a-breadbox dept.
solardiz writes "DES is still in use, brute-force key search remains the most effective attack on it, and it is an attractive building block for certain applications (the key size may be increased e.g. with 3DES). Openwall researchers, with funding from Rapid7, came up with 17% shorter Boolean expressions representing the DES S-boxes. Openwall's John the Ripper 1.7.8 tests over 20 million combinations against DES-based crypt(3) per second on a Core i7-2600K 3.4 GHz, which roughly corresponds to a DES encryption speed of 33 Gbps."
This discussion has been archived. No new comments can be posted.

17% Smaller DES S-box Circuits Found

Comments Filter:
  • A tight datapath-driven layout on standard S-boxes has the potential to recover more area. just sayin...

    • by Anonymous Coward

      That's true, but don't forget that on standard S-boxes the non-polynomial coefficients are 3A-congruent with the inverse configuration. You can't just generalise this across all sub-expressions, as Lehey proved. So you are right for some specific constraints on standard tightly-bound S-boxes, but that is not applicable in this case. You really have to focus on the general Booleans for any improvement. And 17% isn't too far from the theoretical limit of 22% either. So kudo's for the team!

      • by Anonymous Coward

        My hat is off to you for the longest stream of plausible technobabble I've ever heard.

    • Re:ONLY 17%? (Score:5, Insightful)

      by solardiz (817136) on Friday July 01, 2011 @03:13PM (#36636596) Homepage

      We were not the first to generate and try to optimize Boolean expressions for the S-boxes. Other researchers worked on this before, starting 1997 when Eli Biham wrote his classic paper on bitslice DES. 17% is our improvement compared to those previous results. To me, it is impressive that after 14 years and numerous attempts by others, including successful ones, it was still possible to improve on the previous best results by as much as 17% at once. My gut feeling is that further improvements, while definitely possible, will be more limited. But the again, some people I spoke to had thought that our 17% was not possible.

  • This means the NSA won't have hardware versions of this running until next Tuesday.
  • by DriedClexler (814907) on Friday July 01, 2011 @03:09PM (#36636548)

    Why did it take so long to find a shorter boolean expression? Aren't there programs that take in a truth table and churn through all the expressions that can generate it? And isn't the S-box I/O size pretty small to begin with?

    • by TheLink (130905)
      Because most of the very smart people are more interested in doing other things?
    • Determining whether two boolean circuits are equivalent is a famously difficult problem to solve. In fact, it can be reduced to SAT (http://en.wikipedia.org/wiki/Boolean_satisfiability_problem) which was the very first algorithm that was shown to be NP-complete, which in general means it is impractical to solve on real computers.

      • by NoSig (1919688) on Friday July 01, 2011 @03:32PM (#36636752)
        Huge SAT problems are routinely solved on computers. In fact the CPU in your computer was probably formally tested in software by solving a huge SAT problem. NP-completeness does not necessarily mean that a problem can't be solved in practice even if it is huge. Complexity theory does provide an approximation to what is tractable, but it isn't all that accurate.
      • Sure, but you're not being given an arbitrarily large input size; it's something like 8 input/8 output at most. The traveling salseman problem isn't horrendously intractable if you only have e.g. 10 cities.

    • by solardiz (817136)

      6-to-4 is large enough that you can't realistically find a perfect solution (the absolute smallest gate count) on present computers and given present knowledge. You can do it for 5-to-1, though. Also, generic Boolean expression minimization tools produce relatively poor results for DES S-boxes; specialized algorithms are the way to go. IIRC, I tried Espresso - http://en.wikipedia.org/wiki/Espresso_heuristic_logic_minimizer [wikipedia.org] - in late 1990s. It couldn't even get close to Matthew Kwan's results from 1998, wher

  • What I thought was interesting about the S-box, was the obfuscation they introduced by where they selected the look-up bits from. Just re-order the S-box and use a straight 6 bit index....
  • Both are no competition for AES at all. Also, 3DES is still of dubious security and DES can be brute-forced at home today. So this is really non-news, as it does not hold any relevance for people that care about having secure encryption.

    • by solardiz (817136)

      Slow? DES used to be slow prior to bitslicing. The 33 Gbps figure I mention is on par with that for AES using specialized instructions, but without reliance on such instructions. Sure, 3DES is 3x slower. But even for 3DES we get around 10 cycles/byte on one CPU core, which is on par with AES without specialized instructions. That said, data encryption with DES/3DES is in fact not the primary intended use for our results. We realize perfectly well that people want to hear "AES" these days.

      DES is being used f

      • by owlstead (636356)

        AES is a pretty good algorithm, but I don't think it is good enough precisely because of the side channel weaknesses. I would imagine that another round of competition within the crypto community is necessary right after the SHA-3 competition. Currently, 3DES is probably a better choice for many functions than AES because of the possible side channel attacks.

        Regarding the hashing, you are probably better off choosing Skein. It comes with it's own cipher (Threefish), which would also allow some more interest

        • Question: given that you can't really prove the security of any encryption algorithm, why isn't enciphering data with multiple algorithms and independent keys more common? Is it too difficult to do or perhaps too slow and impractical?
          • by owlstead (636356)

            It's slow, impractical (we're having enough problems with protocols) and may not offer the same security as simply adding more rounds or complexity to existing algorithms. It's likely to take more memory (think embedded or smart card) as well. It may not help at all against many side channel attacks. And as I said, most of the time it's not the algorithm that's the problem. It's the system that it is deployed in that's vulnerable, not the algorithm itself.

            Think XML encryption. Very nicely spec'ed, but try a

      • by gweihir (88907)

        I do understand your arguments. The primary problem I have with it is that as it can be brute-forced, you need to take a lot more care when using it as building block. True, if you really understand what you are doing, it can be used securely in a number of ways. Using it as part of a hashing-scheme is valid. However, DES is entirely unsuitable for its primary purpose, namely encryption, today. And when doing hashing, it competes against a number of hash functions as well. The article was lacking these limi

  • If I encrypt a string with DES, and you intercept it but I didn't tell you it's DES, can you tell by inspecting the ciphertext that it's DES (and then use DES cracking tools to crack it)?

    • by owlstead (636356)

      Nowadays, if the block size is 8 bytes, you can be pretty sure it is DES or triple DES. Keeping the algorithm secret has never worked well in cryptography.

      Decrypting single DES is now so easy* that the attacker would probably try it as one of the first things. DES is considered only good enough for real time crypto where offline analysis is not feasible or useful.

      So the short answer is yes.

      *as long as you've got enough to work on

      • by Doc Ruby (173196)

        So if I encrypt with DES, then run a trivial extra transform (eg. ROT12(destext)), it won't be exactly DES and just running undes(ciphertext) won't decrypt it.

        My point isn't to be annoying. It's that there could be value to DES between parties that know it's "DES + ROT12", or whatever trivial function is added, despite DES itself being without real protection value. Especially since DES is now so fast to run.

One man's "magic" is another man's engineering. "Supernatural" is a null word. -- Robert Heinlein

Working...