Fujitsu cracks 923-bit painfully complex crypto

Pitches flexible, almost-uncrackable PBC as future security technique

It took only 148 days, not hundreds of thousands of years, for security researchers in Japan to crack the 923-bit key to a next-generation encryption protocol.

Not that it was easy. The team from Fujitsu, Japan's National Institute of Information and Communications Technology (NICT) and Kyushu University ran advanced cryptanalysis techniques running on 21 PCs running a total of 252 processing cores in parallel to crack a document encrypted using pairing-based cryptography (PBC).

Unlike public-key cryptography, on which most current cryptographic schemes are based, pairing based cryptography doesn't rely on a single string of numbers or key-issuance authority for its encryption.

Instead it uses two groups of numbers that generate a third set when run through any of a series of formulae.

The encryption "key" comes from running values from each of the first two groups though a formula that delivers a result found in the third group, then removing one of the two original groups of numbers.

The sender of an encrypted email might use his or her own list of numbers "A" and a list supplied by the recipient of the email "B," to generate a third set "C" using a pre-defined formula.

The recipient can then decrypt the email using only number groups B and C, though with more difficulty than if he or she possessed groups A and B.

"The known implementations of these pairings – the Weil and Tate pairings – involve fairly complex mathematics," according to notes from a 2004 presentation at MIT by lecturers Ran Canetti and Ron Rivest. "Fortunately, they can be dealt with abstractly, using only the group structure and mapping properties."

Because the encryption/decryption process is so complex and the relationship among the cryptographic-number groups is so flexible, PBC can be used for a variety of different functions, including crypto that would require all three digits to crack, encryption based on the identity of one participant or search encryption that would allow users to search a database for a specific answer without decrypting the whole database.

There's more info at Stanford's PBC Library site, but don't bother unless you're as interested in the calculations and implementation as you are in how PBC might be useful.

PBC has been the subject of enthusiastic academic discussion for more than a decade, but has so far been too complex or too ill-defined to be used as an effective, practical encryption method.

Fujitsu's experiment was designed partly to define just how secure a PBC encryption can be – how long it takes to crack, that is – and partly to jump-start practical development of PBC into commercial products.

The cryptanalysis techniques Fujitsu used are designed not only break the encryption, but to allow the crackers to emulate the authority of the admin who created it – a much harder test.

"As a result, for the first time in the world we proved that the cryptography of the parameter was vulnerable and could be broken in a realistic amount of time," according to Fujitsu's announcement of the PBC project.

Cracking a 923-bit encryption key is a feat in itself, but it's also a world record. The previous record was a successful 2009 attack on an encryption key 676 bits long.

Increasing the key length by a third increased the difficulty of the decryption logarithmatically, so cracking it took "several hundred times the computational power" to crack the new code as it did to crack the old.

There is no indication when or if either PBC or 923-bit-long encryption keys will be used for encryption in commercial security systems.

Read more of Kevin Fogarty's CoreIT blog and follow the latest IT news at ITworld. Follow Kevin on Twitter at @KevinFogarty. For the latest IT news, analysis and how-tos, follow ITworld on Twitter and Facebook.

What’s wrong? The new clean desk test
Join the discussion
Be the first to comment on this article. Our Commenting Policies