Slashdot Mirror
Fujitsu Cracks Next-Gen Cryptography Standard
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."
148 PCs * 21 days is around ten years of PC time. Not much in the grand scheme of things.
See my journal for slashdot ID's by year. Mine created in 2005. http://slashdot.org/journal/289875/slashdot-ids-by-year
The real story is going to be how something with (apparently) severe weaknesses became anyone's pet new crypto standard.
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.
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.
"Science flies us to the moon. Religion flies us into buildings." - Victor Stenger
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.
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.
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
asymmetric encryption != symmetric encryption
AES is rated in galaxy lifetimes, not a paltry "millions of years"
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.
Damn it ... 33000 days would be 2^10 ... i meant 8000 days ... time to get some sleep I thinks !
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).
"Believe me!" -- Donald Trump
As all current x86, many ARM and other processors include AES hardware for encoding/decoding.
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.
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
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 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. 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.