Researchers close security gap in the Internet

Zurich, Switzerland, 24 August 1998—Two mathematicians, one at the Swiss Federal Institute of Technology (ETH) in Zurich and the other at IBM Research - Zurich in Rüschlikon, have co-developed the world's first feasible public-key cryptographic system that has been mathematically proved to protect encoded information from even the most aggressive hacking attacks.

None of the encryption systems commercially available today has been proved to provide absolute security against so-called "active"' attacks. Such attacks are especially devious because, unlike ordinary attacks, they do not attempt to solve the mathematical problem underlying the encryption and thus break the code. Instead, the attacker interacts with the decryption system by sending a series of cleverly crafted text files to a publicly accessible server, which possesses the secret decryption key. By analyzing the server's responses, the attacker can break the encryption code. Cryptographers call this an "adaptive chosen-ciphertext attack". Known to cryptographers for nearly two decades, this kind of attack is considered the most aggressive that any cryptosystem should be expected to withstand. Until now, however, no mathematically sound and yet practically feasible solution has been found.

The threat posed by active attacks in practice was shown earlier this year by a scientist at Bell Labs (USA), who managed to decode information secured by Secure Sockets Layer (SSL), Version 3.0, the standard encryption system used for Web browsers.

This security gap has now been closed by a new encryption scheme invented in Switzerland by Ronald Cramer of the Institute of Theoretical Computer Science at the Swiss Federal Institute of Technology (ETH) in Zurich and Victor Shoup of IBM Research - Zurich in Rüschlikon. Both the attack on SSL and the new Cramer-Shoup encryption system were presented at the technical conference "Crypto '98" being held this week at the University of California at Santa Barbara, USA.

Security against attacks with reasonable effort All public-key encryption systems comprise a pair of public and private keys that are related by a mathematical problem considered too difficult to be solved within a reasonable amount of time. The public key is used to encrypt messages, which can be decrypted only by someone who possesses the private key. The core of the problem with active attacks is that the holder of the private key usually cannot distinguish between legitimate and manipulated encryptions. By responding to a manipulated text, the holder of the private key divulges crucial information that allows the hacker to break the code. This problem has been studied by scientists at IBM's Almaden Research Center in California since 1991. Their work resulted in mathematically exact definitions of cryptosystems that are secure against such attacks, and they developed the first mathematically proved secure system. For general practical use, however, the required computational effort was too great.

Cramer and Shoup's major achievement is combining mathematically proven security with the efficient operation required for practical use. They provide a rigorous proof that their cryptosystem can be broken only by solving a problem known among mathematicians as the Diffie-Hellman Decision Problem. So far, no practical solution to this problem has been found, and it is a commonly accepted conjecture in cryptography that no such solution exists. The Cramer-Shoup cryptosystem requires about two to three times the computing time of systems in use today, which are based on the same mathematical problem but provide less security. IBM plans to incorporate the new system into a future version of its Vault Registry, the IBM SecureWay public-key infrastructure product.