Slashdot Mirror

← Back to Stories (view on slashdot.org)

Fujitsu Cracks Next-Gen Cryptography Standard

Posted by timothy on from the just-showing-off-now dept.

judgecorp writes "Fujitsu and partners have cracked a cryptogram which used 278-digit (923 bit) pairing-based cryptography. The technology was proposed as a next-generation standard, but Fujitsu cracked it, at this level in just over 148 days using 21 personal computers." Reader Thorfinn.au adds a snippet from Fujitsu's announcement of the break: "This was an extremely challenging problem as it required several hundred times computational power compared with the previous world record of 204 digits (676 bits). We were able to overcome this problem by making good use of various new technologies, that is, a technique optimizing parameter setting that uses computer algebra, a two dimensional search algorithm extended from the linear search, and by using our efficient programing techniques to calculate a solution of an equation from a huge number of data, as well as the parallel programming technology that maximizes computer power."

27 of 99 comments (clear)

  1. Pretty Fast by MyLongNickName · · Score: 4, Insightful

    148 PCs * 21 days is around ten years of PC time. Not much in the grand scheme of things.

    --
    See my journal for slashdot ID's by year. Mine created in 2005. http://slashdot.org/journal/289875/slashdot-ids-by-year
    1. Re:Pretty Fast by SJHillman · · Score: 4, Informative

      Given a modest botnet of around 3000 hosts, this could be cracked in about a day.

      However, note that between the 21 PCs, there were 252 cores - an average of 12 cores per PC, so these desktop PCs were at least reasonably high-end even if still consumer technology.

    2. Re:Pretty Fast by Bigby · · Score: 2

      What does it take to crack 256-bit AES encryption?

      And answer in measurements of PCs or LOCs

    3. Re:Pretty Fast by Bengie · · Score: 4, Interesting

      It is estimated that AES256 would take about 2^200 operations with currently public flaws.

      Hypothetical
      1,000,000,000 computers(1bil computers)
      1,000,000,000,000,000 ops per computer(1peta op)
      1,000,000,000,000,000,000,000,000 ops per second total

      1.6069380442589902755419620923412e+60 ops to break AES256

      1.6069380442589902755419620923412e+60 / (1,000,000,000,000,000,000,000,000 * 60sec * 60min * 24hr * 365days)
      is 50,955,671,114,250,072,156,962,268,275.658 years

      You would have to be quite dedicated and live a long time to break AES with current math/computers.

      My cousin went through an advanced crypto class and his teacher ran the math and it comes down to this. If you had an ideal computer(100% efficient) that consumed the absolute minimum amount of energy that it takes to represent data based on our current laws of physics, you would have to consume all of the heat energy in the entire Milkyway Galaxy. Short of a major flaw in AES, no galaxy-bound computer can break AES.

    4. Re:Pretty Fast by Bengie · · Score: 4, Interesting
      Twofish is decently faster than AES and still quite strong(Twofish almost became AES, was in the final 5), so it is a good alternative. SHA1 is a hash, not a symmetric encryption.

      Unless it uses brute-forcing and is correct on the first guess...

      AES keys are typically randomly generated or based on a hash. AES is strong, so breaking the public key or password to get the AES key is always the best way to "break" AES, but it's really just a side-channel attack. That's not AES's fault.

    5. Re:Pretty Fast by KramberryKoncerto · · Score: 2

      Does everyone use randomized quick sort?

    6. Re:Pretty Fast by Bengie · · Score: 5, Interesting

      Most of the next gen cryptography is about public keys or hashes. AES is still effective, so the weakest link in the chain is going to be passwords or breakable public keys, which would allow an attacker to acquire the AES key during the hand-shake.

      One needs a safe way to transmit the AES key over a public network, like the internet. Public keys are very slow, but semi strong. AES is quite fast and really really really strong. Trying to make asymmetric encryption strong is hard because the public key gives information about the private key.

    7. Re:Pretty Fast by KingMotley · · Score: 3, Insightful

      Sure you can. You just can't do it with an interval of 1.

  2. So much for that idea... by wkcole · · Score: 3, Interesting

    The real story is going to be how something with (apparently) severe weaknesses became anyone's pet new crypto standard.

    1. Re:So much for that idea... by hlavac · · Score: 2

      "Im afraid I can't do that, Dave."

      Conflict of interest. Thats what you get when you want an algorithm used by everyone so it must appear to be absolutely secure but at the same time want it to be insecure for everyone else so you can read everything. You add a subtle vulnerability of a class you believe only you know about and can exploit, then push it as a standard. Then it turns out there are other smart guys out there, oops. Or not and you hit jackpot.

    2. Re:So much for that idea... by wkcole · · Score: 3, Insightful

      Got a reference for that? The Fujitsu PR seems to say otherwise but it suffers from being a weak translation. (which raises the question: WTF is wrong with Fujitsu that they don't have anyone capable of well-written English???)

    3. Re:So much for that idea... by wkcole · · Score: 2

      My Japanese is worthless, but I'm not a large multi-national industrial conglomerate with operations in Japan worth millions of dollars per year that would justify my time and/or money to actually learn Japanese or hire someone who can write a press release in Japanese fluently. If I had a need to issue press releases in Japanese, I'd at least have a native speaker read them to make sure my machine translator hadn't messed up.

    4. Re:So much for that idea... by David+Jao · · Score: 3

      The real story is going to be how something with (apparently) severe weaknesses became anyone's pet new crypto standard.

      Oh my god, uninformed summary is uninformed. Please don't make it any worse with your (even more) uninformed comments.

      I'm a cryptography researcher specializing in pairing-based cryptography. I know this subject well. Here's the real deal. Pairing-based cryptography is just as (in)secure as RSA. Nobody goes around thinking that 923-bit RSA keys are secure. RSA is very widely used. (The current world record for an RSA break is 768 bits, but 1024 bit keys have been disrecommended for a LONG time, and there are teams working on breaking 1024-bit RSA right now that expect to succeed within a few years.) Nobody really expected 923-bit pairing keys to be secure. Those keys are too short. It's nice that these researchers did this, and it's nice that we know exactly how hard it is to break a 923-bit key, but the only take-away lesson here is that short keys are insecure. It does not mean that pairing-based cryptography has "severe weaknesses" or that the whole concept of pairing-based cryptography is somehow insecure.

      I repeat: the key broken in this study was short. The study's conclusions are not very surprising or indicative of any weakness in the underlying protocol.

      Another gross misrepresentation in your comment is the insinuation that pairing-based cryptography is somehow anyone's "pet new crypto standard." The number of international standards documents dealing with pairings is exactly zero.

  3. What algorithm was this? by Urd.Yggdrasil · · Score: 4, Insightful

    This article makes very little sense to me. They don't mention what the crypto algorithm was or who was pushing it as the "next gen standard". I don't know of any proposed cryptographic standard with 923 bit anything.

    1. Re:What algorithm was this? by neonsignal · · Score: 3, Informative

      The Fujitsu press release is light on detail too.

    2. Re:What algorithm was this? by mister2au · · Score: 5, Informative

      For starters:

      - IEEE P1363.3 http://en.wikipedia.org/wiki/IEEE_P1363#Identity-based_public_key_cryptography_based_on_pairings_.28P1363.3.29
      - NIST http://csrc.nist.gov/groups/ST/IBE/index.html

    3. Re:What algorithm was this? by vlm · · Score: 2

      They also carefully avoided whatever their new invention was.
      "it wasn't until this new way of approaching the problem was applied"
      Whats the new way to approach the problem? Well, there isn't one in the article.

      As a press release its almost the perfect opposite of science. Virtually unknown subject so there's little common ground for discussion, no method/experimental details beyond the most flimsy, no conclusion, no verifiable prediction, no suggestion of future work. Other than that, its a great anecdote of somebody did something, somehow, and it took awhile.

      --
      "Science flies us to the moon. Religion flies us into buildings." - Victor Stenger
    4. Re:What algorithm was this? by SJHillman · · Score: 2, Funny

      As a press release its almost the perfect opposite of science.

      So, what you're saying is that Fujitsu used..... magic!

    5. Re:What algorithm was this? by vlm · · Score: 4, Informative

      "I don't know of any proposed cryptographic standard with 923 bit anything."

      Ha I found it, purely by luck. First of all assume the press release went thru a journalism and PR filter so its almost entirely incorrect other than some numbers might not be incorrect.

      I remember reading a paper on implementing IDEA (which is a two decade old, semi-patent-unencumbered algo because its so old) on a Spartan FPGA, which I remember because I fool around with a spartan dev board at home and this is the kind of thing you find when you google for fpga and various crypto system names, etc. Anyway that specific FPGA implementation of IDEA has a latency of ... 923 cycles. So its not 923 bit anything, they're talking about a streaming cryptosystem that takes 923 cycles from the first bit squirts in until that encrypted first bit bit squirts out, and the journalist filter rewrote it. Thats low enough latency for high bandwidth stuff like video, but not so good for voice or keyboard ssh unless you play some games (which is a whole nother topic)

      Anyway, cracking a "mere" 128 bit sample in 148 days or whatever is still kinda interesting, even if its not cracking an entire 923 bit system. Landauer limit alone would imply they had to have cracked the algorithm not just brute forced it.

      http://www.cs.washington.edu/education/courses/cse590g/01sp/fccm00_idea1.pdf

      http://en.wikipedia.org/wiki/International_Data_Encryption_Algorithm

      --
      "Science flies us to the moon. Religion flies us into buildings." - Victor Stenger
    6. Re:What algorithm was this? by jmsp · · Score: 2

      It's explained in the article notes, actually:

      Glossary and Notes
      (...)
      4 Pairing-based cryptography:
              A next-generation cryptography (proposed in 2001) based on a map called pairing, which offers many useful functionalities that could not be achieved by previous public-key cryptography. The security of pairing-based cryptography is based on the intractability of discrete logarithm problem (DLP). DLP is a problem to compute d such that a = gd for given g and a

    7. Re:What algorithm was this? by cryptizard · · Score: 3, Interesting

      This is completely wrong. They are using a pairing based crypto system which you can think of as public key plus extra useful properties. The security of these schemes is based on the bilinear diffie Hellman assumption which is very recent and has not been thoroughly tested. It is very likely that it is still secure but at larger key sizes than previously thought.

  4. Re:and yet by localman57 · · Score: 4, Insightful

    You don't know that. If they can, they aren't going to tell you. And they aren't going to piss away a secret capability that valuable prosecuting some drug-dealer, or kiddie porn maker. For the forseeable future, you'd only use it on matters of highest national interest, and then you'd only act directly on such information if you were resonably sure it wasn't a red-herring specifically designed to test if you can break such encryption.

  5. More detail from NICT by mister2au · · Score: 5, Informative

    NICT has an arguably better press release of the same partnership - it goes in just a little detail (which is better than almost none from Fujistsu)

    http://www.nict.go.jp/en/press/2012/06/18en-1.html

  6. Re:okay by Bengie · · Score: 2

    asymmetric encryption != symmetric encryption
    AES is rated in galaxy lifetimes, not a paltry "millions of years"

  7. Re:Maybe they got lucky... by mister2au · · Score: 2

    I thought the same bu now I don't think so.

    They solved the 676 bit equivalent in 33 days back in 2009 and this is broadly 2^8 more complex ... so would expect roughly 33,000 days

    But they then claim several improvements that represent improvements of "dozens of times", "several times" & "several times" faster respectively ... if these compound it could easily be a 100-fold improvement in speed and then more processing speed/cores as well.

    Data searching technology using two-dimensional space
    Our cryptanalysis has to search the seed of the solution from the huge data base. The previous world-top record used the “line sieve” for this data search, but we extended it to the two-dimensional space called “lattice sieve”, and then its speed was accelerated dozens of times by using our own modification.

    Computing the solution of equations of massive numerical data
    We applied the “Lanczos method” for computing the solution of huge systems of equations obtained from massive numerical data. We improved the computational speed several times by optimizing the program for our computational environments.

    Parallel programming for maximal usage of our computational power
    Our programming code achieved the maximal potential of our computational resources by using the SIMD operation equipped in the recent general-purpose computers. This optimization made our cryptanalysis several time faster.

  8. Twofish is much slower than AES by Anonymous Coward · · Score: 3, Interesting

    As all current x86, many ARM and other processors include AES hardware for encoding/decoding.

    1. Re:Twofish is much slower than AES by Bengie · · Score: 2

      I forgot about that part. With all things fair, Twofish is faster, but like you pointed out, AES is in the hardware, which makes it faster/lower-power.