Print 22 comment(s) - last by JPForums.. on Jun 21 at 3:52 PM

Researchers who developed standard claimed it would take "thousands of years to crack", but it took only 148 days

We're living in either a dark, dysmal time for cryptographers or a golden, glorious age for hackers depending on how you look at it.  Casual hackers are making short work of supposedly modestly-secure older hashing standards like MD5, and even supposedly-super-secure "strong" encryption techniques are falling to novel attacks.

I. Pair-Based Cryptography Continues to Fall in Security 

The latest victim in the march of progress is pairing-based cryptography, an approach that was thought to hold the key to super-secure future communications.  Japanese electronics giant Fujitsu Ltd. (TYO:6702), Kyushu University, and Japan’s National Institute of Information and Communications Technology (NICT) cracked a 278-digit (923-bit) cryptogram, easily besting the previous world record of 204 digits (676 bits).

Researchers who worked with pair-based cryptography have in the past expressed confidence that 900+ bit cryptograms would take hundreds of thousands of years to crack.  But Fujitsu, et al. achieved the feat in a mere 148.2 days -- less than half a year -- running on a 21-computer cluster with 252 cores.

Fujitsu cracking
Fujitsu has cracked an encryption that was previously estimated to take "hundreds of thousands of years" to break. [Image Source: Fujitsu]

By employing parallel programming methods and other novel techniques to the attack, the research team was able to cut the time that would have been required by a less state-of-the-art brute force attack with previous methods.

II. Cat and Mouse -- No System is Unbreakable

Fujitsu warns that the shocking success should serve as a warning to security firms that what seems like reliable standards may be crackable sooner than they think, and unsafe not too long after that.  Writes the company:

As cryptanalytic techniques and computers become more advanced, cryptanalytic speed accelerates, and conversely, cryptographic security decreases.  Therefore, it is important to evaluate how long the cryptographic technology can be securely used.

We were able to overcome this problem by making good use of various new technologies, that is, a technique optimising 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 maximises computer power.

Cryptography today is facing a two-side assault.  On the one side are the crackers, looking to employ novel methodology to reverse advance encryption.  On the other side are the exploiters, looking to identify and leverage fundamental flaws in the implementation, flaws which sabotage the reliability of the underlying methods.

Hacker proof
Unbreakable security is a fantasy. [Office Hackery]

Some public keys encrypted by the RSA standard were recently found to have "no security at all".  The culprit, said Swiss researchers who published their findings in February, was improper generation.  Likewise in 2010 Norwegian researchers published [abstract] results indicating quantum cryptography could be cracked via attacking the photon detectors that implemented the encryption via quantum mechanical effect.  Here, the quantum cryptography itself was likely strong enought to stand up to any direct assault, but the glaring weak spot was the encoders/decoders in the system, which could be hijacked with traditional attacks.

Of course security researchers will surely scramble on to new and safer protection schemes.  But it's more clear than ever that uncrackable encryption is anything but.

Source: Fujitsu

Comments     Threshold

This article is over a month old, voting and posting comments is disabled

By geddarkstorm on 6/19/2012 4:44:03 PM , Rating: 3
I gotta say, this whole field of cryptography is seriously fascinating to me. It's a gigantic math puzzle, and that people can be so clever as to crack these supposedly impossible schemes, just goes to show that ingenuity is one things we haven't figured out how to encrypt against.

I wouldn't say it's a dismal type for cryptographers; as if I was one I would be excited by this. It means there's so much more room for improvement and whole new unconventional ways of thinking, to finally make something that's secure on practical scales. Still, important to remember that if something can ever be decoded (even legitimately), it is never 100% secure. Someone could still steal your one-time-pad, after all!

RE: Incredible
By geddarkstorm on 6/19/2012 4:45:11 PM , Rating: 5
And by "type" I meant to type "time". Someone has apparently encrypted the Edit feature!

RE: Incredible
By JKflipflop98 on 6/19/2012 4:51:02 PM , Rating: 2
This is one of those things that really can go on forever. There will always be some dude selling the latest "crack-proof" software, then there will always be the guy that breaks it.

You're only actually buying very small window of safety. 148.2 days, in this case. Pretty cool. And scary.

RE: Incredible
By Colin1497 on 6/19/2012 5:05:17 PM , Rating: 2
And 148 days is 14 hours in just a few years.

RE: Incredible
By StevoLincolnite on 6/19/2012 10:35:46 PM , Rating: 2
This is one of those things that really can go on forever. There will always be some dude selling the latest "crack-proof" software, then there will always be the guy that breaks it. You're only actually buying very small window of safety. 148.2 days, in this case. Pretty cool. And scary.

For sure.
Plus with GPU compute the venerable PC gets orders of magnitudes of compute performance at relatively modest prices... Making earlier Encryption methods easier to break.

It's not unusual to see a high-end gaming PC break the 2 Teraflop mark with 1-2 GPU's which is faster than allot of Super Computers with hundreds of processors from a decade ago.

RE: Incredible
By Calin on 6/20/2012 4:49:03 AM , Rating: 3
Encryption is (as of now) based on integer calculations, not floating point ones (or totally standard floating point implementations that differs on out-of-necessary-precision digits would not be compatible).
And as the GPUs are floating point compute monsters (but integer-compute puppies), cracking encryption on GPU clusters doesn't seem too probable.
I'd say FPGA specially programmed would be a better match for cracking encryption

RE: Incredible
By RedemptionAD on 6/20/2012 11:56:02 AM , Rating: 2
With Intel's recent release of Knights Corner, the cluster used could be equipped with that rather than a GPU array, and reduce the time considerably. A larger botnet or other shared computing platform could also decrease the amount of time required to break it to hours, rather than days. It seems that true security will require a proprietary seperate piece of hardware from the current methods.

RE: Incredible
By Autisticgramma on 6/20/2012 12:18:06 PM , Rating: 2
I don't believe hardware is the answer. I'm sure the TSMC wouldn't agree, however, once its hard coded, and deployed. Its difficult to update, and maintain the tit for tat.

If its hard coded, all you have to do, is crack the device, once.


RE: Incredible
By JediJeb on 6/19/2012 6:22:07 PM , Rating: 1
If you make a scheme that after 5 unsuccessful attempts it erases the data, then that might work. Though if you keep losing your data due to unsuccessful attempts that would also be really bad.

RE: Incredible
By MGSsancho on 6/19/2012 9:18:43 PM , Rating: 2
Computers are fast enough via software or accelerators to really be using stronger algorithms and/or more rounds. Weaker schemes are easier and faster but we really need to be using stronger stuff.

RE: Incredible
By Jeffk464 on 6/19/2012 11:25:38 PM , Rating: 4
Anyone else feeling less secure about their online banking and investing then ever before?

AES broken?
By Biff0rz on 6/19/2012 5:04:27 PM , Rating: 1
It doesn't really say which algorithm was broken, if it's not AES who cares?

RE: AES broken?
By Qapa on 6/19/2012 9:40:26 PM , Rating: 3
Symmetric-key algorithms don't go those key lengths yet...

Triple-DES, AES, (...) generally are still in the 1xx bits.

So we are talking about public key algorithms (like RSA, ...).

And who cares? Anyone that wants to sign anything digitally... that is a possibility for instance in many countries for legal stuff... governments already allow lots of stuff to be done like that.. some companies also already allow that for signing stuff, and for making emails really secure... on that note, some people were (are?) fans of PGP, which uses that type of keys...

RE: AES broken?
By JPForums on 6/20/2012 8:19:00 AM , Rating: 2
So we are talking about public key algorithms (like RSA, ...).

Actually, we are talking about PBC algorithms.

Though they are apparently more complex than public key algorithms, they aren't necessarily more secure. Complexity sometimes creates areas of weakness that are hard to see. That said, the recommended RSA key length is 2048 or larger as 1024 bit was called into question into 2003.

... on that note, some people were (are?) fans of PGP, which uses that type of keys...

Not exactly.
PGP encryption uses a serial combination of hashing, data compression, symmetric-key cryptography, and, finally, public-key cryptography; each step uses one of several supported algorithms.

RE: AES broken?
By JPForums on 6/20/2012 8:00:40 AM , Rating: 2
It doesn't really say which algorithm was broken ...

PBC (Pairing-Based Cryptography) algorithms.

By Gondor on 6/19/2012 6:37:46 PM , Rating: 1
Researchers who worked with pair-based cryptography have in the past expressed confidence that 900+ bit cryptograms would take hundreds of thousands of years to crack. But Fujitsu, et al. achieved the feat in a mere 148.2 days -- less than half a year -- running on a 21-computer cluster with 252 cores.

So if key was lengthened by one bit (to 901 bits) they would have taken them 1 year to brute force it. If it was lengthened to 1024 bits it would have taken them about 1E37 years to break it.

Our universe is estimated to be ~15 * E9 years old; in other words it would have taken them about 700000000000000000000000000000000000 times the lifespan of our universe to crack it using existing etchnology ... assuming technology doesn't improve in any way in the next ~1063382400000000000000000000000000000 years.

1024 bit crypto is not only perfectly doable with today's technology, it should be the mandatory minimum.

Sooooooo ... while I appreciate technology advances (which enable Microsoft to come up with software twice as bloated as the previous incarnation that still runs about as slow on hardware twice as fast !) I don't think there's really a need to be worried. Yes, I'm sure crappy software exists that can be broken in a matter of seconds/minutes./hours/days/years but that doesn't mean you should be using it - insist on safer option !

RE: Fascinating
By DigitalFreak on 6/19/2012 7:51:49 PM , Rating: 2
So... It took them only 3 years to go from cracking 676 bit encryption to cracking 923. At this rate, they should be able to break 1024 in a similar amount of time within a year or two.

RE: Fascinating
By Qapa on 6/19/2012 9:26:02 PM , Rating: 2
Well, not really...

Imagine that in 1 years 1024 bits can be cracked in 6 months with that computer...

Two problems:
1 - Any document you "legally" sign, after those 6 months of having the keys being used are actually worthless - anything can be signed with your both public keys now!
2 - That computer seemed like a week one, for anyone wanting to go in strength to get potentially zillions of dollars (as being able to sign documents for other people is worth that), so put a really good supercomputer and it would maybe be done in 1 week or even 1 day... and now 1024 bits is unusable.

In security, you must adequate what is being secured to the security employed, so...

1024b can only be used for stuff that u don't mind as having as public, like having a normal wooden door at your house.

2048b can be used safely for a few years (to be confirmed every year with new methods like this one), like installing a great safe at home or even at a bank (the probability of being taken is low)

4096b can be used safely for several/lots of years (to be confirmed every few years), like having something at the safe where money gets printed (security measures are really huge)

So don't trust public key crypto with 1024b for anything you really can't have it made public!

Same thing for symmetric-key algorithms (AES, ...) 128b maybe considered fine, but if you really want it safe, use 256b... that way when 128b gets cracked you'll hear about it and have time to move to 512b :)

By Shadowmaster625 on 6/20/2012 10:52:57 AM , Rating: 1
It cannot be broken if it is not even known. Millions of photos could be uploaded to facebook, each one with slightly altered data, altered according to an algorithm to encode any message anyone wants. And unless you have the original, unmodified image file, you simply have absolutely no way of knowing whether or not an image contained a message, much less be able to break it. Encryption methods like this simply can not be broken, mainly because you have no way of knowing if someone uploaded a doctored image, due to the fact that there is so much random noise in a high res photo. "Certain entities" are literally light years ahead of the mainstream when it comes to modern cryptography. If someone wants to communicate on the internet today and not be spied upon, rest assured they can do it.

By JPForums on 6/21/2012 3:52:18 PM , Rating: 2
OK, I'll bite. If you want to detect the presence of hidden data in a picture, it is possible. A simple method (and thus only applicable to simple cases) would be to run a noise removal algorithm of you choice on the photo and store it as photo'. Then run a difference between photo' and photo and store the result as noisemap. Run FFTs on noisemap. Then you can compare its frequency response White Gaussian Noise. You'll find that the response is less uniform across frequencies than noise if there is a hidden message.

Keep in mind this is a simple example that makes assumptions as to the type of noise you would expect to see as well as simplifying the process of obtaining the noisemap. Also specialized wavelets may work better for obtaining the frequency response than FFTs. That said, the frequency responses of many sources of noise are known entities and there are multiple methods that can be used to obtain a noisemap.

Once a picture is known to have a hidden message we are basically back to standard cryptanalysis where the picture could be considered the salt. Just like with standard algorithms, the more messages encrypted with the same key (especially if they also use the same salt), the more information that is available to try to crack it.
Easy? No.
Impossible? Also No.

Not so fast
By Jaybus on 6/20/2012 2:20:20 PM , Rating: 2
"Cat and Mouse -- No System is Unbreakable"

That depends on your definition of unbreakable. It is remotely possible to guess the correct key on the first try, no matter how many bits. It is always possible to find the key by trying every possible combination. But generally, "unbreakable" means that there is not possible to devise an attack that is any faster than a brute force attack. The one-time pad cipher is the only cipher that has been mathematically proven to be unbreakable by that definition, but it is indeed deemed to be "unbreakable".

By SlyNine on 6/21/2012 2:16:54 AM , Rating: 2
Is AES 128 still safe? lol

"We basically took a look at this situation and said, this is bullshit." -- Newegg Chief Legal Officer Lee Cheng's take on patent troll Soverain

Most Popular ArticlesAre you ready for this ? HyperDrive Aircraft
September 24, 2016, 9:29 AM
Leaked – Samsung S8 is a Dream and a Dream 2
September 25, 2016, 8:00 AM
Inspiron Laptops & 2-in-1 PCs
September 25, 2016, 9:00 AM
Snapchat’s New Sunglasses are a Spectacle – No Pun Intended
September 24, 2016, 9:02 AM
Walmart may get "Robot Shopping Carts?"
September 17, 2016, 6:01 AM

Copyright 2016 DailyTech LLC. - RSS Feed | Advertise | About Us | Ethics | FAQ | Terms, Conditions & Privacy Information | Kristopher Kubicki