Fujitsu Cracks Next-Gen Cryptography Standard 99
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."
Pretty Fast (Score:5, Insightful)
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)
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.
Re: (Score:3)
What does it take to crack 256-bit AES encryption?
And answer in measurements of PCs or LOCs
Re:Pretty Fast (Score:5, Interesting)
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.
Re: (Score:1)
Then the energy required is 'considerably less' than all the energy in the galaxy.
On the other hand... If it is such a strong encryption, why isn't everybody using it on everything?
Why would we continue to use Blowfish / twofish / HSA1 (with salt if it isn't linkedin)/ etc. etc.?
Re:Pretty Fast (Score:5, Interesting)
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.
Twofish is much slower than AES (Score:3, Interesting)
As all current x86, many ARM and other processors include AES hardware for encoding/decoding.
Re: (Score:3)
Re: (Score:2)
Re: (Score:2)
Why are we suing AES then? Serpent is even better. It's just slower.
Oh, that's why everyone isn't using AES, either. Speed vs strength. Sometimes speed wins out.
Re: (Score:2)
That must be why "they" want us to change to a different technique.
Re:Pretty Fast (Score:5, Interesting)
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.
Re: (Score:2)
Don't forget stream ciphers esp. with authentication.
eSTREAM is attempting to select the next generation. Salsa is looking strong. http://en.wikipedia.org/wiki/ESTREAM [wikipedia.org]
Public/Private: RSA seems to be ok for now, but there are no proofs stating that factorization is actually a hard problem.
Hashing: SHA3 is being competed for right now, my money is on BLAKE. http://en.wikipedia.org/wiki/NIST_hash_function_competition [wikipedia.org]
Re: (Score:2)
That is assuming you are going to brute force the entire key space, but usually you only need to brute force all possible passwords that could be entered up to a certain length. You might still be thwarted by a very long password, but something like 20 characters is very breakable with today's technology.
Somewhere in a secret datacentre there is probably a big machine using GPUs to brute force passwords on AES encrypted data.
Re: (Score:2)
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.
Re:Pretty Fast (Score:4, Insightful)
Sure you can. You just can't do it with an interval of 1.
Re: (Score:2)
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.
Re: (Score:2)
Note: Moore's law has nothing to do with performance, it is a measure of transistors per IC.
So much for that idea... (Score:4, Interesting)
Re: (Score:1)
Re: (Score:2)
Re:So much for that idea... (Score:4, Insightful)
Re: (Score:2)
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"?)
Re: (Score:3)
Re: (Score:2)
They probably never intended this to be a major international story. What it boils down to is that short keys are insecure, hardly a revelation. Something for the Japanese press only, with an English translation as an afterthought.
Re: (Score:2)
Re: (Score:2)
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.
Re: (Score:2)
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 fir
Re:So much for that idea... (Score:4)
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.
What algorithm was this? (Score:5, Insightful)
Re:What algorithm was this? (Score:4, Informative)
The Fujitsu press release [fujitsu.com] is light on detail too.
Re: (Score:1)
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...
Re: (Score:2)
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
Re:What algorithm was this? (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 [wikipedia.org]
- NIST http://csrc.nist.gov/groups/ST/IBE/index.html [nist.gov]
Re: (Score:2)
So is P1363.3 an actual standard, or just a proposed standard?
Re: (Score:1)
The article summary had it correct with "was proposed as a next-generation standard"
IEEE and potentially NIST (amongst others) were proposing it and/or looking at what applications it might be suitable for.
Re: (Score:2)
Re: (Score:3)
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 anecdot
Re: (Score:3, Funny)
As a press release its almost the perfect opposite of science.
So, what you're saying is that Fujitsu used..... magic!
Re: (Score:1)
As a press release its almost the perfect opposite of science.
So, what you're saying is that Fujitsu used..... magic!
More specifically, religion. A press release is marketing, after all.
Re:What algorithm was this? (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 [washington.edu]
http://en.wikipedia.org/wiki/International_Data_Encryption_Algorithm [wikipedia.org]
Re: (Score:3, Interesting)
Re: (Score:2)
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.
Re: (Score:1)
Re: (Score:1)
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 an
Re: (Score:1)
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
Re: (Score:2)
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
Re: (Score:2)
I don't know of any proposed cryptographic standard with 923 bit anything.
Suite B
Re: (Score:2)
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.
Re: (Score:2)
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 amount
Re: (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 cryptanaly
Re: (Score:1)
Damn it ... 33000 days would be 2^10 ... i meant 8000 days ... time to get some sleep I thinks !
Re:and yet (Score:5, Insightful)
This would be what we call "bad". (Score:2)
252 cores is pretty tiny by the standards of a reasonably motivated attacker. Aside from
Re: (Score:2)
Re: (Score:2)
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.
Re: (Score:2)
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 mo
More detail from NICT (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 [nict.go.jp]
Re: (Score:3)
AES is rated in galaxy lifetimes, not a paltry "millions of years"
Re: (Score:2)
AES is probably secure, but it DOES make use of ideas that have been found to have -potential- weaknesses, which means AES may in turn have potential weaknesses (although that's not guaranteed to be the case). Time to brute-force is only important if you have to brute-force. AES was entered into a contest that looked at security for the next 20-or-so year. I think AES will last the expected lifespan, but it won't last even one solar lifespan, let alone a galaxy's.
Pairing Crypto (Score:1)
It may be tempting to deride th