New Encryption System Provides Practical, Unbreakable Protection
Researchers Develop Mathematically Proven Solution to Internet Security Loophole
ZURICH (August 24, 1998) – Mathematicians at IBM Research and the Swiss Federal Institute of Technology (ETH) have co-developed a new public-key cryptosystem that provides the first practical and mathematically proven way to secure information from even the most aggressive Internet hacking attempts.
The new Cramer-Shoup cryptosystem, revealed today at the Crypto? conference at the University of California-Santa Barbara, effectively closes the backdoor on so-called “active” attacks. All current commercially available cryptosystems are potentially vulnerable to active attacks, which are considered to be the most dangerous hacking attempts any cryptosystem might face.
“This system delivers a new level of integrity for Internet communications, and is particularly suited for e-commerce applications such as cyber-auctions, credit card purchases, and protecting private information,” said Jeff Jaffe, general manager for IBM’s security products and services. “Businesses and consumers can have greater confidence in Internet transactions, because we’ve effectively closed down the only way around a cryptosystem’s main line of defense.”
IBM plans to incorporate the new system into a future version of its Vault Registry software, the IBM SecureWay public-key infrastructure product that allows e-commerce transactions to travel across organizational boundaries in a private, secure manner.
“It’s important that we nip this type of powerful attack in the bud,” said Victor Shoup of IBM’s Zurich Research Laboratory, who invented the new cryptosystem with Ronald Cramer for the Swiss Federal Institute of Technology (ETH). “Earlier this year, an active attack decoded information secured by the most widely used encryption system for Web browsers. Our system will prevent this from happening.”
Finesse vs. Muscle
Strong modern cryptosystems are based upon really difficult mathematical problems that are thought to be unsolvable. If a cryptosystem’s underlying problem could be solved, then the cryptosystem’s security could be broken.
“Active” attacks bypass the difficulty of solving the underlying mathematical problem by sending a series of cleverly constructed messages to a publicly accessible server. By analyzing the server’s pattern of responses to the bogus text, an attacker can decode encrypted messages passing through that network. The Cramer-Shoup method thwarts these attacks by delivering the first non-malleable cryptosystem efficient enough for commercial use.
“This is a case of finesse over muscle,” said Charles Palmer, head of IBM Research’s Network Security and Cryptography Group in New York. “Previous systems left open the possibility of indirect attack. This system elegantly denies that access, shunting attackers back to the imposing mathematical problem at the core of the cryptosystem. In this case, it’s the Diffie-Hellman Decision Problem, for which no feasible solution is known.”
“Non-malleable” Vs. “Malleable” Protection
The Cramer-Shoup system extends the research earlier this decade of three computer scientists at IBM’s Almaden Research Center, San Jose, CA. In 1991, Danny Dolev, Cynthia Dwork and Moni Naor recognized that all current cryptosystems were potentially “malleable.” That is, without knowing the decryption key, an attacker could transform an encryption of one message into an encryption of a related message.
This is a serious security flaw because an active attacker could, for example, eavesdrop on a competitor’s encrypted transmission of a bid for a contract and then submit an assuredly lower one — all without knowing the value of the competitor’s bid or even his or her own bid. An active attacker can further exploit the cryptosystem’s malleability to decrypt targeted messages.
“A malleable cryptosystem is like the combination lock on a safe,” says Dwork. “It provides good security, but a skilled safecracker can still open it by listening carefully to the lock mechanism as the dial is turned. An absolutely silent lock mechanism that gives no clue to the combination would be non-malleable and clearly more desirable.”
Non-malleable cryptosystems neutralize active attacks by adding another series of calculations which ensure that the server leaks no information when responding to bogus text. Cramer and Shoup’s major achievement is combining mathematical rigor with efficient operation, as their system requires little more than twice the computing time of current public key cryptosystems.
A Leader in Cryptography
IBM Research has been a leader in encryption research and development since developing the core technology for the Data Encryption Standard in the early 1970s. Other recent contributions in this area by IBM Research include:
In 1990, Moni Naor and Moti Yung designed the first public-key cryptosystem provably secure against a slightly weaker type of active attack.
In 1991, Dolev, Dwork and Naor developed a rigorous, general method for constructing non-malleable cryptosystems. The resulting schemes were too inefficient to be used commercially.
Also in 1991, Dwork, Naor and Dolev developed a non-malleable identification scheme that was the first to be secure against “intruder-in-the-middle” attacks.
In 1994, Mihir Bellare and Phil Rogaway developed a practical public-key cryptosystem that, while not provably secure against active attacks, has been argued to be, until now, the best available protection. RSA Data Security, Inc. has recently proposed this system to make the Secure Sockets Layer web encryption system more secure against active attacks.
Also in 1994, Dwork and Naor created the first practical digital signature scheme that is secure in the strongest sense known.
In 1997, Miklos Ajtai and Dwork developed a new cryptosystem with the extremely desirable property that a random instance of it is as hard to break as the hardest instance of the underlying mathematical problem. Thus the Ajtai-Dwork cryptosystem has — provably — no “bad” keys, those which are easier to break than others in the same system.
The technical paper by Cramer and Shoup that describes their new cryptosystem in detail can be viewed on the World Wide Web at:
http://www.zurich.ibm.com/Technology/Security/publications/1998/CS.pdf.
Source: IBM