RSA: 56-bit crypto too weak

Encryption software vendor RSA Data Security just spent another $10,000 proving its point to the federal government.

The company awarded the cash prize to a group called the Bovine RC5 Effort that cracked 56-bit encryption code, the strongest encryption allowed by U.S. law for export without the use of key escrow or recovery schemes. RSA's point: 56-bit code isn't strong enough.

It took a group of 4,000 teams using tens of thousands of computers linked over the Internet 210 days to crack the code. The decrypted message read, "It is time to move to a longer key length."

The cracked key challenge is the fourth of 13 challenges presented by the company since January of this year. The first, a 40-bit key, was cracked in three hours for a $1,000 prize. The second, a 48-bit key, was cracked in 13 days for a $5,000 prize.

The third, broken in June, was also a 56-bit key. But that crypto was cracked more quickly than the latest code because it used the government's Data Encryption Standard (DES), which contains weaker algorithms, according to RSA vice president of marketing Scott Schnell. The other 12 key challenges use the RC5 standard.

The remaining nine key challenges increase in strength in increments of 8 bits each. Key bits increase exponentially, each single bit doubling the key's strength.

The method used to crack the first four keys is known as "brute force," whereby a network of computers combines processing power to try each of the possible combinations. In the case of 56-bit encryption, that amounts to more than 72 quadrillion, or 72,057,594,037,927,936, possibilities. The right combination was found after 47 percent of the possibilities had been tried.

RSA and other encryption advocates want the government to approve the unrestricted export of 128-bit keys. They argue that U.S. companies are at a disadvantage to competitors in Germany, Ireland, Japan, and other countries with fewer or no encryption restrictions.

"It's the equivalent of telling U.S. auto manufacturers that they couldn't export a car that went faster than 55 mph," said Schnell.

Congress has been engaged in a pitched battle for more than a year to ease export limits on encryption. Momentum has swung back and forth between free-encryption advocates and supporters of law enforcement agencies such as the FBI, which wants to control not only the export of encryption, but its domestic use as well.

Meanwhile, contest participants face the challenging nine remaining codes, especially the final 128-bit code that the company would like to export without restrictions. When does RSA expect contestants to crack that code?

"Never," Schnell said. While noting that changes in computing power and mathematical theory could prove him wrong, he nevertheless predicted that "the Sun will be extinguished before the 128-bit challenge is cracked."