Forgot your password?
typodupeerror
Security Encryption Japan Math Supercomputing IT

Fujitsu Cracks Next-Gen Cryptography Standard 99

Posted by timothy
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."
This discussion has been archived. No new comments can be posted.

Fujitsu Cracks Next-Gen Cryptography Standard

Comments Filter:
  • by Anonymous Coward on Tuesday June 19, 2012 @08:49AM (#40368515)

    forsty piss!

  • Cold TURD (Score:-1, Offtopic)

    by Anonymous Coward on Tuesday June 19, 2012 @08:50AM (#40368521)

    Frosty piss

  • Pretty Fast (Score:5, Insightful)

    by MyLongNickName (822545) on Tuesday June 19, 2012 @08:53AM (#40368543) Journal

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

    • Re:Pretty Fast (Score:5, Informative)

      by SJHillman (1966756) on Tuesday June 19, 2012 @08:59AM (#40368627)

      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.

      • Ready? (Score:-1, Offtopic)

        by AlwaysResortToRape (2665583) on Tuesday June 19, 2012 @09:27AM (#40368977)

        About six months ago, I was overexerting myself trying to get rid of a terrible virus on a client's PC (I own a PC repair shop and have been fixing computers for over 10 years). Given my level of expertise, I thought I'd be able to get rid of it fairly quickly and without hassle, but as was made evident by my colossal failure, I was horribly, horribly wrong.

        I couldn't remove the virus no matter what method I used. I tried all the latest anti-virus software and all the usual tricks, but it was all in vain. Failure after failure, my life was slowly being sucked away as I spent more and more of my time trying to get rid of this otherworldly virus.

        Frustrated and stressed by my own failure, I began distancing myself from my wife and children. After a few days, I began verbally abusing them, and it eventually escalated into physical abuse. I was slowly losing what remaining sanity I had left. If this had continued for much longer, it is highly probable that I would have committed suicide. A mere shell of what I once was, I barricaded myself in my bedroom and cried myself to sleep for days on end.

        That's when it happened: I found MyCleanPC [mycleanpc.com]! I installed MyCleanPC [mycleanpc.com] right on the client's PC, ran a scan, and it immediately got rid of all the viruses without a single problem. MyCleanPC [mycleanpc.com] accomplished in record time what I was unable to accomplish after a full week. Wow! Such a thing!

        MyCleanPC [mycleanpc.com] is outstanding! My client's computer is running faster than ever! I highly recommend you install MyCleanPC [mycleanpc.com] right this minuteness, run a scan, and then boost your PC speed in record time! MyCleanPC [mycleanpc.com] came through with flying colours where no one else could!

        My client's response? "MyCleanPC [mycleanpc.com] totally cleaned up my system, and increased my speed!" All the PC repair professionals are using MyCleanPC [mycleanpc.com] to solve all of their problems. This should be reason enough for you to switch to MyCleanPC [mycleanpc.com]! It'll speed up your computer, rid it of all viruses, and you'll be able to work productively again! Wow!

        Even if you're not having any obvious computer problems, you could still be in danger. That's why I very highly recommend that you still use MyCleanPC [mycleanpc.com]. After all, it will boost your PC & internet speed to levels you never would think are possible!

        MyCleanPC: For a Cleaner, Safer PC. [mycleanpc.com]

        -----------

        A few weeks ago, I foolishly ran a strange executable file that one of my acquaintances sent me by email. As someone who doesn't know much about computers, at the time, I thought nothing of it. "Why would my acquaintance want to hurt me?" Following this line of thought, I ran the file without question.

        How naive I was. Despite having what was supposedly the best anti-virus software out right then, a virus took over my computer and held it hostage. It was pretending to be a warning from Windows telling me to buy some strange anti-virus software I'd never heard of from a company I'd never heard of to remove the virus.

        This immediately set alarm bells off in my head. "How could this happen? My anti-virus is supposed to be second to none!" Faced with this harsh reality, I decided to take it to a PC repair shop for repair. They gladly accepted the job, told me it'd be fixed in a few days, and sent me off with a smile.

        A few days later, they called me and told me to come pick up my computer. At the time, I noticed that they sounded like whimpering animals, but I concluded that it must just be stress from work. When I arrived, they, with tears in their eyes, told me that the virus was so awful and merciless that they were unable to remove it. "Ah," I thought. "That must be why they sounded so frustrated and pathet

        • Re:Ready? (Score:-1, Offtopic)

          by Anonymous Coward on Tuesday June 19, 2012 @10:32AM (#40369787)

          Go fist yourself, while holding a steak knife.

          And doing so would still provide a more enjoyable experience than using mycleanpc, which is generally considered the herpes of the computing world.

      • by Anonymous Coward on Tuesday June 19, 2012 @10:39PM (#40380173)

        What I want to know is what it would cost to do this in one hour using something like Amazon's EC2. That seems like a fairly good, semi-universal standard reference, as not everyone has their own personal botnet to use.

    • by Bigby (659157) on Tuesday June 19, 2012 @09:03AM (#40368665)

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

      And answer in measurements of PCs or LOCs

      • by Anonymous Coward on Tuesday June 19, 2012 @09:28AM (#40368985)

        My rough estimate would be something like 2^192 PC-years, give or take dozen magnitudes or something equally insignificant.

      • Re:Pretty Fast (Score:5, Interesting)

        by Bengie (1121981) on Tuesday June 19, 2012 @09:31AM (#40369013)
        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.
      • by AlwaysResortToRape (2665583) on Tuesday June 19, 2012 @09:33AM (#40369063)

        About six months ago, I was overexerting myself trying to get rid of a terrible virus on a client's PC (I own a PC repair shop and have been fixing computers for over 10 years). Given my level of expertise, I thought I'd be able to get rid of it fairly quickly and without hassle, but as was made evident by my colossal failure, I was horribly, horribly wrong.

        I couldn't remove the virus no matter what method I used. I tried all the latest anti-virus software and all the usual tricks, but it was all in vain. Failure after failure, my life was slowly being sucked away as I spent more and more of my time trying to get rid of this otherworldly virus.

        Frustrated and stressed by my own failure, I began distancing myself from my wife and children. After a few days, I began verbally abusing them, and it eventually escalated into physical abuse. I was slowly losing what remaining sanity I had left. If this had continued for much longer, it is highly probable that I would have committed suicide. A mere shell of what I once was, I barricaded myself in my bedroom and cried myself to sleep for days on end.

        That's when it happened: I found MyCleanPC [mycleanpc.com]! I installed MyCleanPC [mycleanpc.com] right on the client's PC, ran a scan, and it immediately got rid of all the viruses without a single problem. MyCleanPC [mycleanpc.com] accomplished in record time what I was unable to accomplish after a full week. Wow! Such a thing!

        MyCleanPC [mycleanpc.com] is outstanding! My client's computer is running faster than ever! I highly recommend you install MyCleanPC [mycleanpc.com] right this minuteness, run a scan, and then boost your PC speed in record time! MyCleanPC [mycleanpc.com] came through with flying colours where no one else could!

        My client's response? "MyCleanPC [mycleanpc.com] totally cleaned up my system, and increased my speed!" All the PC repair professionals are using MyCleanPC [mycleanpc.com] to solve all of their problems. This should be reason enough for you to switch to MyCleanPC [mycleanpc.com]! It'll speed up your computer, rid it of all viruses, and you'll be able to work productively again! Wow!

        Even if you're not having any obvious computer problems, you could still be in danger. That's why I very highly recommend that you still use MyCleanPC [mycleanpc.com]. After all, it will boost your PC & internet speed to levels you never would think are possible!

        MyCleanPC: For a Cleaner, Safer PC. [mycleanpc.com]

        -----------

        A few weeks ago, I foolishly ran a strange executable file that one of my acquaintances sent me by email. As someone who doesn't know much about computers, at the time, I thought nothing of it. "Why would my acquaintance want to hurt me?" Following this line of thought, I ran the file without question.

        How naive I was. Despite having what was supposedly the best anti-virus software out right then, a virus took over my computer and held it hostage. It was pretending to be a warning from Windows telling me to buy some strange anti-virus software I'd never heard of from a company I'd never heard of to remove the virus.

        This immediately set alarm bells off in my head. "How could this happen? My anti-virus is supposed to be second to none!" Faced with this harsh reality, I decided to take it to a PC repair shop for repair. They gladly accepted the job, told me it'd be fixed in a few days, and sent me off with a smile.

        A few days later, they called me and told me to come pick up my computer. At the time, I noticed that they sounded like whimpering animals, but I concluded that it must just be stress from work. When I arrived, they, with tears in their eyes, told me that the virus was so awful and merciless that they were unable to remove it. "Ah," I thought. "That must be why they sounded so frustrated and pathet

      • by Anonymous Coward on Tuesday June 19, 2012 @09:40AM (#40369143)

        A very very long time. Symmetric cryptography is much stronger than public key... but the reason public key is so important is that we need some method of doing a key exchange and therefore using public key cryptography allows us to do a key exchange for symmetric cryptography. Public key cryptography generally relies on difficult math problems and apparently this one isn't so difficult. RSA and ECC have limitations and require a lot of resources that make it important to find new methods of public key encryption.
        Here is a story on how long it takes to crack AES:
        "To put this into perspective: on a trillion machines, that each could test a billion keys per second, it would take more than two billion years to recover an AES-128 key"
        Source: The Inquirer (http://s.tt/14cdl)

      • by Thiez (1281866) on Tuesday June 19, 2012 @09:45AM (#40369211)

        Using brute force? On a conventional computer it would require more energy than is available in our galaxy. You can't even count up to 2^256.

    • by AlwaysResortToRape (2665583) on Tuesday June 19, 2012 @09:27AM (#40368973)

      About six months ago, I was overexerting myself trying to get rid of a terrible virus on a client's PC (I own a PC repair shop and have been fixing computers for over 10 years). Given my level of expertise, I thought I'd be able to get rid of it fairly quickly and without hassle, but as was made evident by my colossal failure, I was horribly, horribly wrong.

      I couldn't remove the virus no matter what method I used. I tried all the latest anti-virus software and all the usual tricks, but it was all in vain. Failure after failure, my life was slowly being sucked away as I spent more and more of my time trying to get rid of this otherworldly virus.

      Frustrated and stressed by my own failure, I began distancing myself from my wife and children. After a few days, I began verbally abusing them, and it eventually escalated into physical abuse. I was slowly losing what remaining sanity I had left. If this had continued for much longer, it is highly probable that I would have committed suicide. A mere shell of what I once was, I barricaded myself in my bedroom and cried myself to sleep for days on end.

      That's when it happened: I found MyCleanPC [mycleanpc.com]! I installed MyCleanPC [mycleanpc.com] right on the client's PC, ran a scan, and it immediately got rid of all the viruses without a single problem. MyCleanPC [mycleanpc.com] accomplished in record time what I was unable to accomplish after a full week. Wow! Such a thing!

      MyCleanPC [mycleanpc.com] is outstanding! My client's computer is running faster than ever! I highly recommend you install MyCleanPC [mycleanpc.com] right this minuteness, run a scan, and then boost your PC speed in record time! MyCleanPC [mycleanpc.com] came through with flying colours where no one else could!

      My client's response? "MyCleanPC [mycleanpc.com] totally cleaned up my system, and increased my speed!" All the PC repair professionals are using MyCleanPC [mycleanpc.com] to solve all of their problems. This should be reason enough for you to switch to MyCleanPC [mycleanpc.com]! It'll speed up your computer, rid it of all viruses, and you'll be able to work productively again! Wow!

      Even if you're not having any obvious computer problems, you could still be in danger. That's why I very highly recommend that you still use MyCleanPC [mycleanpc.com]. After all, it will boost your PC & internet speed to levels you never would think are possible!

      MyCleanPC: For a Cleaner, Safer PC. [mycleanpc.com]

      -----------

      A few weeks ago, I foolishly ran a strange executable file that one of my acquaintances sent me by email. As someone who doesn't know much about computers, at the time, I thought nothing of it. "Why would my acquaintance want to hurt me?" Following this line of thought, I ran the file without question.

      How naive I was. Despite having what was supposedly the best anti-virus software out right then, a virus took over my computer and held it hostage. It was pretending to be a warning from Windows telling me to buy some strange anti-virus software I'd never heard of from a company I'd never heard of to remove the virus.

      This immediately set alarm bells off in my head. "How could this happen? My anti-virus is supposed to be second to none!" Faced with this harsh reality, I decided to take it to a PC repair shop for repair. They gladly accepted the job, told me it'd be fixed in a few days, and sent me off with a smile.

      A few days later, they called me and told me to come pick up my computer. At the time, I noticed that they sounded like whimpering animals, but I concluded that it must just be stress from work. When I arrived, they, with tears in their eyes, told me that the virus was so awful and merciless that they were unable to remove it. "Ah," I thought. "That must be why they sounded so frustrated and pathet

    • by adisakp (705706) on Tuesday June 19, 2012 @11:22AM (#40370499) Journal

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

      10 years of today's computer time. If Moore's law holds, 10 years from now, it will be 1 month (~36 days) of computer time. And in 10 more years, it will be 8.5 hours.

      The technology was proposed as a next-generation standard, which means it will take 3-5 years to be adopted as the standard. It'd be nice to have a standard that held up more than another 3-5 years.

  • by wkcole (644783) on Tuesday June 19, 2012 @08:55AM (#40368565)
    The real story is going to be how something with (apparently) severe weaknesses became anyone's pet new crypto standard.
    • by Quakeulf (2650167) on Tuesday June 19, 2012 @09:00AM (#40368631)
      Bad management decision?
    • by L4t3r4lu5 (1216702) on Tuesday June 19, 2012 @09:21AM (#40368879)
      Apparently it was an implementation weakness. The math may still be sound.
      • by wkcole (644783) on Tuesday June 19, 2012 @10:14AM (#40369565)
        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???)
        • by MrBandersnatch (544818) on Tuesday June 19, 2012 @10:49AM (#40370001)

          Its probably machine translated from Japanese. Sadly while the Japanese are doing some incredible research in very diverse areas, most of the translations are very rough and ready. If you want to criticise though, how is your Japanese? ("nihongo wa dou desu ka"?)

          • by wkcole (644783) on Tuesday June 19, 2012 @11:11AM (#40370343)
            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.
          • by Anonymous Coward on Tuesday June 19, 2012 @02:35PM (#40373473)

            I worked with a translation company for a while. Poor translation is a common problem all over the world because good translation requires commitment and resources. In particular, it is a problem among Asian companies. Since people in Japan, China, and other many Asian countries study English all through their school years they consider themselves expert. However, the rule when translating is to always have a native speaker review the translation. The companies, for reasons of pride in their home-trained English abilities or cost, generally don't bother to perform that step. So, you get poor translations.

        • by TapeCutter (624760) on Tuesday June 19, 2012 @11:01AM (#40370195) Journal
          I work for Fujitsu, I'm a native english speaker, I've never been to Japan and can't speak/read/write a word of Japanese. However there are 175K employees so TFA is news to me too. The translation looks like it's a literal translation of a Japanese press release, as opposed to one written by someone with an understanding of the subject. As literal translations go it's a pretty good one (you should see what the auto-translator dumps in my inbox),
        • by Anonymous Coward on Tuesday June 19, 2012 @02:52PM (#40373797)

          Nearly everyone in Japan learns English in High School. It's a very low-pressure treatment using cheap foreign students who don't speak much Japanese. The main point is to make sure everyone passes.

          The result is most people in Japan have a marginal English credit. Combine this peer pool with the culture of saving face and you've got a lot of press releases that seem okay at home.

          Is this a good idea? Well as you say, Fujitsu is a multi-million dollar company -- they seem to be doing okay by it. What you're missing is the big Japanese corporations treat the press pretty well. If this catches interest, they'll make sure professional journalists have good access to the people inside with the details, and better English and Japanese articles will result as things go forward.

          Press releases like this one are better thought of as Search metadata, rather than a final product. They tell the press a rough idea of what's going on in the Company, so they can come do their job. They're not the same thing at all as most Western press releases, which are articles intended to be reprinted wholesale by the "journalists" that we call the press.

    • by hlavac (914630) on Tuesday June 19, 2012 @09:30AM (#40369003)
      "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.
      • by wkcole (644783) on Tuesday June 19, 2012 @10:48AM (#40369987)

        Frankly, that's paranoid. I stopped trying to understand the deep math of leading-edge crypto some years ago as my brain calcified, but I understand enough of it to know that there's no need for intentional sabotage to explain vulnerabilities to innovative attack.

        My question is how *THIS* mechanism has survived as long as it has. I haven't looked at the math in depth, but the broad descriptions I've found make me expect that there must be far-better-than-brute-force attacks on it. This crack isn't the first one to prove that to be the case, if I'm reading the Fujitsu PR right. I'm hoping for a deeper explanation of why pairing-based cryptography is so attractive that what seems like past evidence of diminishing returns from increased nominal complexity didn't kill it off before now.

    • by David Jao (2759) <djao@dominia.org> on Tuesday June 19, 2012 @05:39PM (#40376883) Homepage

      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.

  • by Urd.Yggdrasil (1127899) on Tuesday June 19, 2012 @08:56AM (#40368579)
    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.
    • by neonsignal (890658) on Tuesday June 19, 2012 @08:59AM (#40368619)

      The Fujitsu press release [fujitsu.com] is light on detail too.

    • by ITShaman (120297) on Tuesday June 19, 2012 @09:04AM (#40368677) Homepage

      Another dumb statement in the article:
      "Succh a cryptanalysis would allow an attacker to counterfeit the authority of a system administrator, according to Fujitsu."

      If I had known you could counterfeit authority, I would be sitting behind a really big desk with the flag of my own country behind it...

      • by AlwaysResortToRape (2665583) on Tuesday June 19, 2012 @09:09AM (#40368747)

        Nearly four months ago, I noticed that my internet connection was very sluggish. Eventually getting fed up with it, I began to seek out software that would speed up the gigabits in my router. After an hour of searching, I found what at first appeared to be a very promising piece of software. Not only did it claim it would speed up my internet connection, but that it would overclock my power supply, speed up my gigabits, and remove any viruses from my computer! "This is a fantastic opportunity that I simply can't pass up," I thought. I immediately downloaded the software and began the installation, all the while laughing like a small child. I was highly anticipating a future where the speed of my internet connection would leave everyone else's in the dust.

        I was horribly, horribly naive. Immediately upon the completion of the software's installation, various messages popped up on my screen about how I needed to buy software to remove a virus that I wasn't aware I had from a software company I'd never once heard of. The strange software also blocked me from doing anything except buying the software it was advertising. Being that I was a computer whiz (I had taken a computer essentials class in high school that taught me how to use Microsoft Office, and was quite adept at accessing my Facebook account), I was immediately able to conclude that the software I'd downloaded was, in fact, a virus, and that it was slowing down my gigabits at an exponential rate. "I can't let this insanity proceed any further," I thought.

        As I was often called a computer genius, I was confident at the time that I could get rid of the virus with my own two hands. I tried numerous things: restarting the computer, pressing random keys on the keyboard, throwing the mouse across the room, and even flipping an orange switch on the back of the tower and turning the computer back on. My efforts were all in vain; the virus persisted, and my gigabits were running slower than ever! "This cannot be! What is this!? I've never once seen such a vicious virus in my entire life!" I was dumbfounded that I, a computer genius, was unable to remove the virus using the methods I described. Upon coming to terms with my failure, I decided to take my computer to a PC repair shop for repair.

        I drove to a nearby computer repair shop and entered the building with my computer in hand. The inside of the building was quite large, neat, and organized, and the employees all seemed very kind and knowledgeable. They laughed upon hearing my embarrassing story, and told me that they saw this kind of thing on a daily basis. They then accepted the job, and told me that in the worst case, it'd be fixed in three days from now. I left with a smile, and felt confident in my decision to leave the computer repairs to the experts.

        A week later, they still hadn't called back. Visibly angry, I tried calling them countless times, but not a single time did they answer the phone. Their negligence and irresponsibility infuriated me, and sent me into a state of insanity that caused me to punch a gigantic hole in the wall. Being that I would require my computer for work soon, I decided to head over to the computer repair shop to find out exactly what the problem was.

        Upon entering the building, I was shocked by the state of its interior; it looked as if a tornado had tore through the entire building! Countless broken computers were scattered all about the floor, desks were flipped over, the walls had holes in them, there was a puddle of blood on the floor, and worst of all, I saw that my computer was sitting in the middle of the room laying on its side! Absolutely unforgivable! I soon noticed one of the employees sitting behind one of the tipped over desks (the one that had previously had the cash register on top of it); he was shaking uncontrollably and sobbing. Despite being furious about my computer being tipped over, seeing him in that state still managed to make me less unforgiving. I decided to ask him what happened.

        A few moments passed where the entire r

      • by AlwaysResortToRape (2665583) on Tuesday June 19, 2012 @09:29AM (#40368993)

        About six months ago, I was overexerting myself trying to get rid of a terrible virus on a client's PC (I own a PC repair shop and have been fixing computers for over 10 years). Given my level of expertise, I thought I'd be able to get rid of it fairly quickly and without hassle, but as was made evident by my colossal failure, I was horribly, horribly wrong.

        I couldn't remove the virus no matter what method I used. I tried all the latest anti-virus software and all the usual tricks, but it was all in vain. Failure after failure, my life was slowly being sucked away as I spent more and more of my time trying to get rid of this otherworldly virus.

        Frustrated and stressed by my own failure, I began distancing myself from my wife and children. After a few days, I began verbally abusing them, and it eventually escalated into physical abuse. I was slowly losing what remaining sanity I had left. If this had continued for much longer, it is highly probable that I would have committed suicide. A mere shell of what I once was, I barricaded myself in my bedroom and cried myself to sleep for days on end.

        That's when it happened: I found MyCleanPC [mycleanpc.com]! I installed MyCleanPC [mycleanpc.com] right on the client's PC, ran a scan, and it immediately got rid of all the viruses without a single problem. MyCleanPC [mycleanpc.com] accomplished in record time what I was unable to accomplish after a full week. Wow! Such a thing!

        MyCleanPC [mycleanpc.com] is outstanding! My client's computer is running faster than ever! I highly recommend you install MyCleanPC [mycleanpc.com] right this minuteness, run a scan, and then boost your PC speed in record time! MyCleanPC [mycleanpc.com] came through with flying colours where no one else could!

        My client's response? "MyCleanPC [mycleanpc.com] totally cleaned up my system, and increased my speed!" All the PC repair professionals are using MyCleanPC [mycleanpc.com] to solve all of their problems. This should be reason enough for you to switch to MyCleanPC [mycleanpc.com]! It'll speed up your computer, rid it of all viruses, and you'll be able to work productively again! Wow!

        Even if you're not having any obvious computer problems, you could still be in danger. That's why I very highly recommend that you still use MyCleanPC [mycleanpc.com]. After all, it will boost your PC & internet speed to levels you never would think are possible!

        MyCleanPC: For a Cleaner, Safer PC. [mycleanpc.com]

        -----------

        A few weeks ago, I foolishly ran a strange executable file that one of my acquaintances sent me by email. As someone who doesn't know much about computers, at the time, I thought nothing of it. "Why would my acquaintance want to hurt me?" Following this line of thought, I ran the file without question.

        How naive I was. Despite having what was supposedly the best anti-virus software out right then, a virus took over my computer and held it hostage. It was pretending to be a warning from Windows telling me to buy some strange anti-virus software I'd never heard of from a company I'd never heard of to remove the virus.

        This immediately set alarm bells off in my head. "How could this happen? My anti-virus is supposed to be second to none!" Faced with this harsh reality, I decided to take it to a PC repair shop for repair. They gladly accepted the job, told me it'd be fixed in a few days, and sent me off with a smile.

        A few days later, they called me and told me to come pick up my computer. At the time, I noticed that they sounded like whimpering animals, but I concluded that it must just be stress from work. When I arrived, they, with tears in their eyes, told me that the virus was so awful and merciless that they were unable to remove it. "Ah," I thought. "That must be why they sounded so frustrated and pathet

      • by GiMP (10923) on Tuesday June 19, 2012 @02:13PM (#40373103)

        Being somewhat (but not intimately) familiar with this cryptography methodology, what they're claiming to have done is broken the equivalent of a signing-authority key. This is worse than with a CA in PKI, however, because this key can be used for encryption and decryption, it isn't only a signature used for validation/verification.

        Essentially, Identity-based systems use a single "master key" which is used to create all the other keys, and can be used to decrypt all of the messages encrypted with those keys, and to regenerate private keys. The advantage of this type of system is that given your own private key, you can deterministically solve for a peer's public key. This is why it is called pair-cryptography.

        The disadvantage is that there is a single master key that can be compromised. Until now, it had been thought that this key would be difficult to compute.

    • by vlm (69642) on Tuesday June 19, 2012 @09:11AM (#40368761)

      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.

      • by SJHillman (1966756) on Tuesday June 19, 2012 @09:16AM (#40368801)

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

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

      • by Anonymous Coward on Tuesday June 19, 2012 @10:13AM (#40369559)

        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.

        Reminds me of my masters thesis.

    • by vlm (69642) on Tuesday June 19, 2012 @09:32AM (#40369031)

      "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 [washington.edu]

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

      • by cryptizard (2629853) on Tuesday June 19, 2012 @11:36AM (#40370663) Homepage
        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.
        • by vlm (69642) on Tuesday June 19, 2012 @12:03PM (#40371061)

          Could be, I'm just working on numerology. I can't find anything when googling for 923 bits, although I found the IDEA FPGA implementation easy enough and I remember reading it in the past too. Its not "real crypto" if no one else knows about it. Or another way to put it is everyone in the field knows that if no one knows the algo then its probably pretty insecure, so the surprise is...

          Maybe the journalist filter tried to pass 1024 bits thru a metric to english translation system resulting in 923 bits.

          • by cryptizard (2629853) on Tuesday June 19, 2012 @04:46PM (#40375815) Homepage
            The key can be any size, just like in RSA. They likely chose 923 as a number they thought they could reasonably break. This is similar to the RSA contests where they try to find the largest semi-prime that they can factor (it is never a round number).
          • by Anonymous Coward on Thursday June 21, 2012 @05:44AM (#40395987)

            Go to page 3 of this paper : http://www.nict.go.jp/en/press/2012/06/PDF-att/20120618en.pdf

            They solved the super singular curve in GF(3^97) by converting over finite field in GF (5^582) (I strongly suspect this is actually GF (3^5 82) ). I don't know the details of how solving GF (3^5 82) means a difficulty 923 bits.

            The point is that as shown in the paper of the previous record in 2010 https://lib-repos.fun.ac.jp/dspace/bitstream/10445/4856/2/shirase_2010_01_pkc.pdf, 97 is the smallest size that was considered large enough to be safe in practice to use in pairing cryptography implementations.

    • by Anonymous Coward on Tuesday June 19, 2012 @09:33AM (#40369047)

      They mention that this is a pairing based system. Unfortunately, the type of pairing isn't specified, and there are hundreds of pairing based schemes out there.

      For those not familiar with pairings and IBE, this quote from the fujitsu website may help:

      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.

      5 Identity-based encryption:

      A type of public-key encryption in which the public key of a user is some unique information about the identity of the user (e.g. a user's email address). It does not require authentication of public keys unlike former public-key cryptosystems.

      The year of 2001 here presumably refers to the Boneh-Franklin [wikipedia.org] scheme (paper on springer behind paywall [springerlink.com]), which also immediately showed the usefulness of pairing crypto by creating the first efficient identity-based encryption scheme (wiki). Basically, IBE is any scheme where one can use an arbitrary string as the public key (assuming the other party has previously obtained the private key). There are some caveats involved (and proposed solutions for them), but I would recommend taking a crypto course if you're interested.

      As an aside, it should be noted that pairings were originally developed to break certain cases of elliptic curve based schemes (eg. ECDSA [wikipedia.org], which is slowly coming into usage now), so it may be that the same thing happens here.

    • by AlwaysResortToRape (2665583) on Tuesday June 19, 2012 @09:34AM (#40369073)

      About six months ago, I was overexerting myself trying to get rid of a terrible virus on a client's PC (I own a PC repair shop and have been fixing computers for over 10 years). Given my level of expertise, I thought I'd be able to get rid of it fairly quickly and without hassle, but as was made evident by my colossal failure, I was horribly, horribly wrong.

      I couldn't remove the virus no matter what method I used. I tried all the latest anti-virus software and all the usual tricks, but it was all in vain. Failure after failure, my life was slowly being sucked away as I spent more and more of my time trying to get rid of this otherworldly virus.

      Frustrated and stressed by my own failure, I began distancing myself from my wife and children. After a few days, I began verbally abusing them, and it eventually escalated into physical abuse. I was slowly losing what remaining sanity I had left. If this had continued for much longer, it is highly probable that I would have committed suicide. A mere shell of what I once was, I barricaded myself in my bedroom and cried myself to sleep for days on end.

      That's when it happened: I found MyCleanPC [mycleanpc.com]! I installed MyCleanPC [mycleanpc.com] right on the client's PC, ran a scan, and it immediately got rid of all the viruses without a single problem. MyCleanPC [mycleanpc.com] accomplished in record time what I was unable to accomplish after a full week. Wow! Such a thing!

      MyCleanPC [mycleanpc.com] is outstanding! My client's computer is running faster than ever! I highly recommend you install MyCleanPC [mycleanpc.com] right this minuteness, run a scan, and then boost your PC speed in record time! MyCleanPC [mycleanpc.com] came through with flying colours where no one else could!

      My client's response? "MyCleanPC [mycleanpc.com] totally cleaned up my system, and increased my speed!" All the PC repair professionals are using MyCleanPC [mycleanpc.com] to solve all of their problems. This should be reason enough for you to switch to MyCleanPC [mycleanpc.com]! It'll speed up your computer, rid it of all viruses, and you'll be able to work productively again! Wow!

      Even if you're not having any obvious computer problems, you could still be in danger. That's why I very highly recommend that you still use MyCleanPC [mycleanpc.com]. After all, it will boost your PC & internet speed to levels you never would think are possible!

      MyCleanPC: For a Cleaner, Safer PC. [mycleanpc.com]

      -----------

      A few weeks ago, I foolishly ran a strange executable file that one of my acquaintances sent me by email. As someone who doesn't know much about computers, at the time, I thought nothing of it. "Why would my acquaintance want to hurt me?" Following this line of thought, I ran the file without question.

      How naive I was. Despite having what was supposedly the best anti-virus software out right then, a virus took over my computer and held it hostage. It was pretending to be a warning from Windows telling me to buy some strange anti-virus software I'd never heard of from a company I'd never heard of to remove the virus.

      This immediately set alarm bells off in my head. "How could this happen? My anti-virus is supposed to be second to none!" Faced with this harsh reality, I decided to take it to a PC repair shop for repair. They gladly accepted the job, told me it'd be fixed in a few days, and sent me off with a smile.

      A few days later, they called me and told me to come pick up my computer. At the time, I noticed that they sounded like whimpering animals, but I concluded that it must just be stress from work. When I arrived, they, with tears in their eyes, told me that the virus was so awful and merciless that they were unable to remove it. "Ah," I thought. "That must be why they sounded so frustrated and pathet

    • by Anonymous Coward on Tuesday June 19, 2012 @09:40AM (#40369147)

      Well, it kinda looks like a factorization record to me, but there's probably some additional weakness they get to exploit.. Doesn't look particularly interesting, considering that these kinds of key sizes have been considered "broken" for a while already.

    • by bzipitidoo (647217) <bzipitidoo@yahoo.com> on Tuesday June 19, 2012 @10:05AM (#40369467) Journal

      I surmise that "pairing-based cryptography" is just some weird new name someone dreamed up for Public Key Cryptography, as that uses algorithms that work on a pair of keys. Marketing and customers are so anxious to have the next big thing that the marketing people routinely dress up old ideas in new terms, and customers eagerly latch on. Both often realize what they're doing, but they hope others, including journalists and government bureaucrats responsible for choosing and approving standards, are fooled. Shows how little they truly care about security when they go running for the obscurity and lies, and not just to try to cover up problems, but more as a marketing ploy.

      Which algorithm they used, who knows? RSA? Diffie-Hellman? Clearly, they went the brute force route. And to help the brute force attack along, they deliberately went with an unusual and short number of bits, thus proving very little. They didn't break the algorithm itself. Most asymmetric algorithms need something like double the number of bits to be as secure as a typical good symmetric algorithm. 923 bits may be acceptable for a symmetric algorithm, but is shaky for RSA. These days, there is doubt that 1024 bits is enough for RSA, and users are strongly urged to go with at least 2048 bits.

      The usual thing to do in a public key system is use the asymmetric algorithm only to securely transmit a key for a symmetric algorithm, then use the symmetric algorithm and key for the message itself, as that is faster. The way the article reads, they may have hacked up their own poor version of a public key system, omitting the symmetric algorithm, and using the asymmetric algorithm for the message. Possibly they aren't even doing the public part, keeping both keys of a key pair secret. There's no way to tell on any of that, not from the minimal info in the article.

    • by betterunixthanunix (980855) on Tuesday June 19, 2012 @10:07AM (#40369499)

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

      Suite B

    • by Anonymous Coward on Tuesday June 19, 2012 @11:35AM (#40370647)

      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.

      It's next-gen. Don't you know ANYTHING about marketing? Next-gen is clearly newer than something with multimedia, which in turn is superior to CD-quality, which trumped hi-fi and color. But God help us all if they crack newer buzzword systems. I shudder to think of a world where the enemy has cracked our HD, 4G, or wifi cryptos, or worse, our most advanced weapon yet, cloud crypto.

      But don't worry, we've got our best writing teams working around the clock to come up with newer, more innovative marketing buzzwords. Once we've attached those to crypto methods, we'll be unstoppable!

    • by Anonymous Coward on Tuesday June 19, 2012 @11:52AM (#40370885)

      Obviously it is an elliptic-curve-pairing-based algorithm, though I don't know which. On some decent enough courses on elliptic curve cryptography, pairing-based protocols (http://en.wikipedia.org/wiki/Pairing-based_cryptography) can be seen.

      A pairing on an elliptic curve is something that might be more familliar to math majors in number theory. Basically, it is a non-degenerated bilinear form on an elliptic curve. Famous pairing includes Weil pairing(http://en.wikipedia.org/wiki/Weil_pairing). They are firstly useful tools in math of elliptic curve. Secondly, since it is a bilinear form compatible with everything (group structure, etc.), it can be used to effectively mask information.

      A handful of protocols are pairing-based, and their strength depends a priori on concrete utilization of pairing. A usual protocol is to mask a Diffie-Hellman-alike exchange with a pairing so that it appears to be a difficult Diffie-Hellman problem in a large and complex group while all computation stays in a small and simple group for efficiency. The strength, my personal guess, is the strength to solve Diffie-Hellman in the large group.

  • by Anonymous Coward on Tuesday June 19, 2012 @09:03AM (#40368673)

    The odds are 1 in whatever gazillion that the first thing you try will be the right thing.

    • by vlm (69642) on Tuesday June 19, 2012 @09:17AM (#40368809)

      The odds are 1 in whatever gazillion that the first thing you try will be the right thing.

      Yeah but more specifically, no one seems to know if "148 days" is 90% or 9% of the way thru a random search of solution space. The extremes are unlikely in proportion, like a 9% search success is probably only going to happen 1 in 11 trials.

      Could "148 days" be a 100% guaranteed successful exact solution along the lines of it takes exactly "148 days" of calculations to solve and doing it in 147 is impossible and 149 is a waste of time? Who knows.

      • by Cajun Hell (725246) on Tuesday June 19, 2012 @11:51AM (#40370873) Homepage Journal

        no one seems to know if "148 days" is 90% or 9% of the way thru a random search of solution space. The extremes are unlikely in proportion, like a 9% search success is probably only going to happen 1 in 11 trials.

        It doesn't matter.

        It only matters if they were 0.0001% (that's not actually enough zeros; I'm being figurative) of the way through the keyspace. If they were as high as 1% and just happened to get lucky, that's enough to show that it doesn't take ludicrous amounts of time, and "ludicrous amounts of time" is where the bar currently is and what we all want from any serious crypto. Hiding your love letters from your little sister should require more resources to crack than the NSA ever hopes to have (not because it makes sense, but because you can).

    • by mister2au (1707664) on Tuesday June 19, 2012 @10:05AM (#40369463)

      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.

  • by Anonymous Coward on Tuesday June 19, 2012 @09:05AM (#40368685)

    the CIA/FBI/NSA with a trillion dollar budget can't even crack 128bit AES...

    • Re:and yet (Score:5, Insightful)

      by localman57 (1340533) on Tuesday June 19, 2012 @09:19AM (#40368841)
      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.
      • by Anonymous Coward on Tuesday June 19, 2012 @10:17AM (#40369597)

        Well, that's a pretty bold thing to say considering that you could be replying to e.g. NSA head or someone crazy enough to have proven the minimum number of operations to reverse the algorithm in the generic case.

  • by fuzzyfuzzyfungus (1223518) on Tuesday June 19, 2012 @09:19AM (#40368833) Journal
    Given how long it takes for something to go from 'new' to 'common' and from 'common' to 'deprecated' and from 'deprecated' to 'finally dead, thank god'(and, for the spooks out there, the fact that storage is cheap and certain decade or decades-old messages may still be interesting...), the idea that anything only a few powers of ten away from trivial crackability was even being considered seems like a Very Bad Thing.

    252 cores is pretty tiny by the standards of a reasonably motivated attacker. Aside from botnets, 12 cores/1U is relatively cheap commodity gear at this point. Even without springing for the fancy high-density stuff, you could shove 3 times that, with room for switches, into a rack. Toasty, sure, but possible.
    • by localman57 (1340533) on Tuesday June 19, 2012 @09:20AM (#40368869)
      Or, just rent a cloud server for a little while.
    • by kasperd (592156) on Tuesday June 19, 2012 @01:57PM (#40372851) Homepage Journal

      Given how long it takes for something to go from 'new' to 'common' and from 'common' to 'deprecated'

      Common and deprecated are not mutually exclusive. Something can stay common long after it has become deprecated. Seeing technologies remaining common for a decade after they became deprecated is one of the main reasons for the 'thank' in the 'finally dead, and thank god for that' state that you mentioned.

    • Trivial rule of thumb: Any encryption method, to not be considered excessively weak now, must not be considered excessively weak (expected lifespan of method + time information to remain sealed afterwards) years into the future, even after Moore's Law is taken into consideration.

      Thus, if you've a cypher that you expect to use for the next 20 years to protect data that will be under a 100 year rule before disclosure, it has to be resilient to attack for 120 years. Chip performance roughly doubles every 18 months, so you've 80 rounds of doubling within the secure lifetime of the data. (I'm going to ignore the increasing use of botnets and distributed computing, and say that these will simply compensate for the physical limitations of what can be done on the silicon itself.)

      2^80 is crudely 10^24. That's definitely more than a few powers of ten!

      I would consider this to be the absolute minimum safe bufferzone against brute-force attacks. Why? After all, most data isn't under a hundred year rule. Because civil servants are LAZY BASTARDS!!! You HAVE to assume that they will use cheap, widely-available tools, not suitable ones. This means you HAVE to assume that the level of security necessary is capable of withstanding the absolutely-guaranteed abuse the cypher will suffer.

  • by mister2au (1707664) on Tuesday June 19, 2012 @09:19AM (#40368843)

    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 [nict.go.jp]

  • by Anonymous Coward on Tuesday June 19, 2012 @09:29AM (#40368995)

    My ROT14 is still going strong.
    Yes, ROT14. Nobody would ever suspect ROT13+1.

  • by Captain.Abrecan (1926372) on Tuesday June 19, 2012 @09:36AM (#40369091)
    Where are all the people who are saying that it takes millions of years to crack encryption? What, this shit is useless afterall?
  • by Anonymous Coward on Tuesday June 19, 2012 @10:46AM (#40369955)
  • by Anonymous Coward on Tuesday June 19, 2012 @04:00PM (#40375021)

    They'll never clean that mess up... That just means even more contamination going into the ocean

  • by cryptizard (2629853) on Tuesday June 19, 2012 @05:11PM (#40376299) Homepage
    Pairing based cryptography is a relatively new kind of crypto that can be thought of as public-key plus some extra useful properties (makes Identity Based Encryption [wikipedia.org] possible for instance). It does not say in the article which particular scheme they are using, but one of the big ones is Boneh-Franklin [wikipedia.org]. Just as the security of RSA is based on the hardness of factoring, most pairing schemes are based on the hardness of something called the Bilinear Diffie-Hellman problem.

    It may be tempting to deride this scheme for the fact that it was broken so quickly, but there are extenuating circumstances to consider. Unlike a symmetric cipher like AES, where an arbitrary key is essentially just as good as any other key, asymmetric ciphers have a much more nuanced keyspace. To start with, not every value in the keyspace can actually be used as a key. Using AES as an example again, you can choose any 128-bit value and it will work as a key for AES-128. In contrast, for RSA to work the key (modulus) must be a product of two large primes. In the space of all 1028-bit numbers, there are many such numbers but they are very sparsely distributed. This means that you need a much larger key size for RSA than AES to get the same amount of security. To complicate things further, the two factors cannot be too close together (lest they be broken with Fermat's factorization algorithm) nor can they be one larger than a number with many small factors (broken by Pollard's p-1 algorithm). In short, there are many things to consider and, although it is accepted that larger keys will be more secure, it is often not straightforward to figure out exactly how large a key should be to provide adequate security.

    Now, the reason I digressed a bit there was to show that, although asymmetric encryption has proven security (which widely used block ciphers do not), it is often difficult to judge how secure certain keys and key sizes are without years or decades of researchers examining the cipher. Pairing based cryptography is a relatively new field and it is quite possible that researchers have underestimated the key size needed for adequate security, even though the underlying system is still secure. The information given in the article seems to point to that as being the case since they have not discovered any major theoretical break, only a way to speed up checking of possible keys.
  • by Anonymous Coward on Wednesday June 20, 2012 @02:23AM (#40381477)

    This is as much a feat as those RSA factoring challenges are. Which is to say, interesting incremental progress, but not a big surprise to cryptographers.

    They broke discrete logarithm over F(3^(6*97)), which would allow an attack on a pairing-based crypto scheme with an elliptic curve over F(3^97). The (well-known) existence of such attacks, and the excellent fit offered by certain F(p) curves, are why most cryptographers don't use those fields. Still, you can find implementations, such as http://homepage1.nifty.com/herumi/crypt/pairing.html. The most common implementations these days use 256-bit prime fields with 3072-bit output, or something of that magnitude. Without a mathematical breakthrough, this attack would take about as long on such a field as factoring a 3072-bit number, or breaking 128-bit AES. The attack on 923 bits was easier than 923-bit factoring, because it is more efficient against F(small^big) than it is against F(big^small).

    The size 923 bits is not entirely arbitrary. When using small-prime extension fields, you need to use 2^prime 3^prime to avoid "descent" attacks. The size 97 = 96+1 (with 96 being very composite) might also allow for some sort of speedup, or maybe it's just a computer-convenient sizing thing. So the next size is 3^(101*6), which is about 960 bits of output, but the implementation I linked goes straight to 3^(193*6), double the size.

    Pairings really are considered (by cryptographers) as a candidate next-generation cryptosystem, and have been studied in this role for about a decade. They are similar to traditional elliptic-curve cryptosystems, whose security is relatively well understood. The usefulness of pairings mostly isn't because of improved security, but rather because many more protocols can be implemented with them. Fujitsu obliquely references a master-key system called "identity-based encryption", which usually uses pairings (though it can use RSA-style math or lattices as well; the RSA-like systems are much slower; the lattices are much newer and thus edgier, and have huge public keys). They are correct that IBE is more brittle than traditional PKI: compromise the master key and it's game over for everyone. Still, in some situations IBE's brittleness may be outweighed by its usefulness.

  • by Anonymous Coward on Thursday June 21, 2012 @07:58PM (#40405767)

    For those interested - here's further analysis including commentary from a world-renowned expert on pairing based cryptography - Prof. Dan Boneh at Stanford:

    "Variants of the algorithm used in the recent announcement have been known since 1994, and have been considered by researchers in the pairing based cryptography community. The result shows an efficient implementation of the algorithm, but does not change the overall security analysis of pairing based cryptography." – Professor Dan Boneh, Stanford University.

    more details here:

    http://superconductor.voltage.com/2012/06/understanding-the-recent-fujitsu-discrete-log-calculation.html

"Consistency requires you to be as ignorant today as you were a year ago." -- Bernard Berenson

Working...