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.
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
My ROT14 is still going strong.
Yes, ROT14. Nobody would ever suspect ROT13+1.
Where are all the people who are saying that it takes millions of years to crack encryption? What, this shit is useless afterall?
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.
The US just built the world's fastest supercomputer.
The funny part is that he believes someone will actually go through the effort of reading all that, or that it will promote the product.
As all current x86, many ARM and other processors include AES hardware for encoding/decoding.
Are you dumb? There are many versions of it and a lot of them are hilarious. A lot of people here read them entirely simply for the humor.
They'll never clean that mess up... That just means even more contamination going into the ocean
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.
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.
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