Uncrackable? or media hype?

Nathan D. T. Boyd (boydn@graphics.lcs.mit.edu)
Wed, 07 May 1997 19:54:21 -0400

How could it be uncrackable? Is that theoretically possible?
It would have to be adaptive, no?


Uncrackable encryption? IBM says yes By John Dodge May 6, 1997 5:42 PM PDT PC Week Online

Researchers at IBM's Almaden Research Center Lab in San Jose, Calif., claim they have discovered public key encryption that is uncrackable, solving a problem that has defied mathematicians for 150 years.

While IBM officials cautioned that the complex math involved in the technology is "more scientific than practical," they said the discovery represents an invincible way to protect private computer information from unwanted viewing.

Even if IBM's claims are true, security is already so good, the advance may simply give IBM bragging rights, said two security experts, who expressed doubts that the discovery constitutes any significant practical advance.

"It sounds significant from a mathematical point of view. But large key sizes (with existing technology) are uncrackable today. And smaller keys can be exported. It's not clear to me how much better this makes things, but it's nice to crow about," said Ira Machefsky, an analyst with Giga Information Group, of Santa Clara, Calif.

IBM CEO and Chairman Louis Gerstner has repeatedly said tight security is a top concern to IBM's largest corporate customers. His sentiments were echoed by IBM's top Internet strategist Tuesday.

"Perhaps no technology is more important to the success of the Internet than security, so everyone can be assured that their payments, privacy and property rights are absolutely protected," said Irving Wladawsky-Berger, general manager of IBM's Internet Division.

Unfortunately, the most powerful technology does not always win, said Larry Dietz, a vice president with Zona Research Inc. in Redwood City, Calif. "The security market is run more by marketing and perception than it is by technology. Build a better mousetrap and nobody uses it because nobody wants dead mice," he said.

Moreover, IBM, headquartered in Armonk, N.Y., could face laws that could compromise the technology because export laws require authorities to have a back door to crack the system under certain legal circumstances. "It faces questions like that," said Dietz.

IBM said the advent of public key cryptography in the 1970s introduced the notion that the security of an encryption scheme, also known as a "cryptosystem," depends on the difficulty that an eavesdropper would have in solving the underlying mathematical problem on which the system is based -- even when the eavesdropper is using the world's most powerful supercomputers. As computers get faster and are able to solve difficult problems more quickly, data security systems must also improve apace, IBM officials acknowledged.

Indeed, that's why uncrackable systems are a moving target, said Dietz.

"In the real world, there is no such thing as uncrackable. Because uncrackable today does not mean uncrackable in 2027," he said.

The new IBM cryptosystem relies on finding a "unique shortest vector" in an n-dimensional lattice, a problem mere mortals don't understand, but one that has defied mathematicians for more than a century. The scheme's inventors are computer scientists Miklos Ajtai and Cynthia Dwork of IBM's Almaden Research Center.

"No one yet knows how to prove that any one of the underlying problems in use today is absolutely impossible to solve," says Ajtai. "Until that happens, the best we can do is to show that a new cryptosystem is hard to crack."

Nate Boyd                        MIT Computer Graphics Group, NE43-249
mailto:boydn@graphics.lcs.mit.edu                   617.258.5090 [tel]
http://lumina.lcs.mit.edu/People/boydn/www          617.253.6652 [fax]