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."

Comments

Re:What algorithm was this?

[neonsignal]

The Fujitsu press release is light on detail too.

Re:Pretty Fast

[SJHillman]

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:What algorithm was this?

[mister2au]

For starters:

- IEEE P1363.3 http://en.wikipedia.org/wiki/IEEE_P1363#Identity-based_public_key_cryptography_based_on_pairings_.28P1363.3.29
- NIST http://csrc.nist.gov/groups/ST/IBE/index.html

More detail from NICT

[mister2au]

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

Re:What algorithm was this?

[vlm]

"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

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