Domenick J. Dellino
June 25, 1996
"It may roundly be asserted that human ingenuity cannot concoct a cipher which human ingenuity cannot resolve."
—Edgar Allan Poe
Introduction
Public and Private Keys
One-Way Functions
Keys and "Strong Cryptography"
How Hackers Are Able to Break the Systems
The Importance of Standards
Toward a Standard for Encryption and Authentication
Microsoft's Run at Security on the Internet
Bibliography and Suggestions for Further Reading
Along with the growth of digital global connectivity commonly called the Internet, a new breed of electronic vandals has emerged. Their favorite targets are the data streams and deep pools of information once thought by government, corporations, and even ourselves to be secure from interlopers.
The current perpetrators of these digital break-ins, kidnappings, and black marketeering include students, researchers, mathematicians, hackers, activists, and joyful troublemakers from around the world. They are not necessarily carrying on in the spirit of the virus writers of the 1980s. In fact, many of them have hacked through corporate firewalls and intercepted secure and encrypted messages with a diverse collection of goals in mind—such as a nonlethal means to notoriety, a way of earning a bounty for discovering holes in the ether, or even academic pursuit. Indeed, much of the encryption-hacking done today has served to make the systems that protect our privacy more secure.
Apparently, that's just exactly what happened when Eric Perlman, a 15-year-old tenth grader in Berkeley, California, recently found at least four serious bugs in JavaScript™, including one that enabled him to track visitors to different Web sites and to capture information from their "cookie" files. Cookie files are where Internet browsers such as Microsoft® Internet Explorer and Netscape Navigator store vital user information including registration numbers and even, potentially, credit card information.
Fortunately, his ability to manipulate Netscape's code was no fluke. He and his father, an Internet guru for Pacific Bell, were Netscape beta testers who reviewed prereleased versions of the software. Although his bugs have been addressed, Perlman's exploits raise potentially serious questions about the security of JavaScript.
Why has data become so threatened? Reasons abound. For one thing, the quantity and breadth of electronic data has increased dramatically from a few years ago. These data now include financial information, corporate secrets, source code, and passwords, in addition to the simple e-mail or the job control language (JCL) that constitutes the main diet of data sent to mainframes in past years. Furthermore, that vulnerability has been extended to more fronts. In the context of the Internet, security now refers to protecting the published information of the site itself, to storing security information at the site, and to the secure transmission of data between the client and the server. So, while protective measures are far more robust than before, there is not only more economic motivation for hackers, but also more computing resources and advanced algorithms available for code-breaking.
The message offered by Robert Morris, Sr., a recently retired senior scientist at the National Security Agency (NSA) at Crypto '95 at the University of California at Santa Barbara seems to be the following: "Never underestimate the time, expense, and effort an opponent will expend to break a code." For accounts of attacks on government and corporations, see the article "Your Worst Nightmare" (Violino 1996).
We are now aware that the attacks on our security Internet are coming, but that knowledge is not always enough to suggest precisely which countermeasures to launch.
This article provides an introduction to the key concepts of security: encryption, authentication, private and public keys, digital signatures, secure commerce, code signing, and certificate authorities.
The science of concealing messages has been vital to diplomatic and military security for centuries. Cryptographic techniques, of course, have come a long way since the simple substitution ciphers that date back to the days of Julius Caesar.
Modern security systems rely on encryption, which is the transformation of data into a form unreadable by anyone without a "decryption key" (kind of like a secret decoder ring). In a multi-user setting, encryption allows secure communication over an insecure channel.
Until recently, cryptography systems used the same key to encrypt and decrypt a file. With these systems, the strength of the algorithm and the key determined the level of security. The best algorithms are those that retain their strength even if the algorithm is public. These systems are called private-key, or symmetric, cryptosystems, and their advantage is speed. A major disadvantage of private-key cryptography, however, is key management, since each pair of individuals who wants to communicate must have a unique shared key. For example, if you needed to encrypt communication with five people, you would need to generate five keys to keep your data secure (using the same private key with all five would allow each to access information intended for the others). Since an intruder who learned a key would be able to read any messages encrypted by that key, you must distribute private keys for symmetric systems securely, which may be difficult if you communicate over a network.
To address the problems of key management, public-key or asymmetric cryptography was developed. In this scheme, each key actually consists of two parts: the encryption half (the "public key") and the decryption half (the "private key," which unlocks data encrypted with the matching public key).
This "fail-safe" system allows a more convenient key distribution method—anyone who wants to communicate with you can use your public key. Moreover, intruders can't use an intercepted public key to decrypt files. The downside is that public key cryptosystems are typically slower than private ones.
Until recently, there weren't any easy-to-use programs that implemented public key cryptography. The advent in the early 1990s of Pretty Good Privacy (PGP), a high-security cryptographic software application for MS-DOS®, UNIX, VAX/VMS and other computers helped change that. Now, the ease-of-use barrier is becoming a thing of the past.
A one-way function is a mathematical function that is significantly easier to perform in one direction (the forward direction) than in the inverse direction. One might, for example, compute the function in minutes but only be able to compute the inverse in months or years. A trapdoor one-way function is a one-way function where the inverse direction is easy if you know a certain piece of information (the trapdoor), but is difficult otherwise.
Public-key cryptosystems are based on (presumed) trapdoor one-way functions. The public key gives information about the particular instance of the function; the private key gives information about the trapdoor. Whoever knows the trapdoor can perform the function easily in both directions, but anyone not knowing the trapdoor can perform the function only in the forward direction. The forward direction is used for encryption and signature verification; the inverse direction is used for decryption and signature generation.
In almost all public-key systems, the larger the key, the greater the difference between the efforts necessary to compute the function in the forward and inverse directions (for someone lacking the trapdoor). For a digital signature to be secure for years, for example, it is necessary to use a trapdoor one-way function with inputs great enough that someone without the trapdoor would need many years to compute the inverse function.
All practical public-key cryptosystems are based on functions thought to be one-way, but which have not been proven to be so. This means that it is theoretically possible that an algorithm could be discovered that can compute the inverse function easily without a trapdoor; this development would render any cryptosystem based on that one-way function insecure and useless. The fact that most cryptosystems employ keys that expire after a year partly serves to provide a safety net for this theoretical flaw.
The "key" is what locks and unlocks the encryption on secured messages or data. It is a very large number—typically the factor of an even larger prime number. Just how large is extremely important. The larger the number, the more difficult it is (geometrically) to figure it out and crack the encryption.
Government agencies consider "strong" encryption systems (such as RSA, a public key cryptosystem named for its inventors: Ron Rivest, Adi Shamir, and Len Adelman) those which use asymmetric algorithms with key sizes of more than 512 bits or symmetric algorithms (such as DES, IDEA, and RC5) with key sizes of more than 40 bits (often referred to as "40/512 crypto"). Remember that because the public key is known in an asymmetric system, more bits would be required to keep it secure than in a private, or symmetric, system.
Since government encryption policy is heavily influenced by the agencies responsible for gathering domestic and international intelligence—the FBI and the NSA, respectively—the government is compelled to balance the conflicting requirements of making strong cryptography available for commercial purposes while still making it possible for those agencies to break those codes, if need be.
Most cryptographers, however, don't consider 40/512 cryptography "strong" at all. In fact, RSA's mathematicians have for several years considered 40/512 cryptography to be "commercially inadequate," and currently recommend that domestic customers use at least 80/768 cryptography.
Government agencies often prefer to use the terms "strategic" and "standard" to differentiate encryption systems. "Standard" refers to algorithms that have been drafted and selected as a federal standard—DES (Data Encryption Standard) is the primary example. The government defines "strategic" as any algorithm that requires "excessive work factors" to attack successfully. Unfortunately, the government rarely publishes criteria for what it defines as "acceptable" or "excessive" work factors.
If, however, the key size is, say, more than 40 digits, then its exportability (and whether or not it can be used legally in certain applications) becomes an issue. The U.S. government usually classifies strong cryptography on the U.S. Munitions List as an export-controlled commodity, just like tanks and missiles. The reasoning is that during wartime, strong cryptography in an enemy's hands can be used to decipher crucial communications or can be used for criminal purposes.
Former NSA scientist Morris has outlined two general ways to crack a cryptosystem. One is to exploit an unintended weakness or mistake. As Morris put it, "Look for plaintext." In the jargon of the field, plaintext is a message in words that anyone can read—before the message gets scrambled. No matter how baffling the task of code breaking might seem, very fallible human beings are the ones who must employ the sophisticated means of encryption, and sometimes they fail. Sometimes, when one least expects it, a passage—or even an entire message—might somehow lie unencoded within seemingly impenetrable code. In that case, you can read it as easily as a newspaper.
The other method is to unleash a frontal assault on the crypto by directing more resources—both computational and intellectual—toward breaking the code than the system designers would have ever thought possible.
Perhaps a good way to distinguish between the two methods is to imagine you have your friend Jerry's ATM card. It's your challenge to crack his PIN. You might begin by trying his address or the last 4 digits of his phone number. You might try each of them backwards and if that fails, perhaps his birthday or even the numbers he always plays at the track. If you guess correctly, your success is a measure of Jerry's lack of subtlety.
Employing a frontal assault, on the other hand, you start with 0000. If that doesn't work you try 0001, and so on. This is obviously a much more tedious and time-consuming method, but with only 10,000 combinations to process, it is bound to work eventually.
But what about much larger numbers? "Factoring" is the underlying, presumably difficult-to-solve problem upon which several public-key cryptosystems, including RSA, are based. Factoring is the act of splitting an integer into a set of factors. For example, the factors of 15 are 3 and 5; the factoring problem is to find 3 and 5 when given 15. That's easy. But what about 63,354,827,631? Or how about a 254-digit number? Prime factorization requires splitting an integer into factors that are prime numbers; every integer has a unique prime factorization. Multiplying two prime integers together is easy, but as far as we know, factoring the product is much more difficult.
Factoring an RSA key or "modulus" would allow an attacker to figure out the private key; thus, anyone who can factor the modulus can decrypt messages and forge signatures. The security of RSA, therefore, depends on making factoring difficult, although significant advances in the mathematics of factoring have emerged in recent decades that make the task somewhat easier. Therefore, factoring researchers still consider the possibility that a quick-and-easy factoring method might be discovered quite remote.
Suffice it to say, factoring large numbers takes more time than factoring smaller numbers. This is why the size of the modulus in RSA determines how secure an actual use of RSA is: The larger the modulus, the longer it takes to factor, and thus the more resistant to attack the RSA implementation is. For a complete discussion of the science of factoring and the higher mathematics brought to bear, visit the RSA Secure Data site.
The RSA system was the first manifestation of the breakthrough in theoretical public key cryptography. To prove the system's soundness, Rivest, Shamir, and Adelman were asked in the late 1970s to devise a challenge.
Rivest picked an RSA key of 129 digits, encoded a message with it and offered U.S.$100 to anyone who could decode the message. The three inventors felt their C-note was as secure as their code. After all, Rivest estimated that it would take a supercomputer 40 quadrillion years (that's a 40 with 15 zeros) to break the code. Even if one did not accept that time frame (which Rivest later said was a miscalculation), a much shorter time—say a billion years, or even a few million—would ensure that anyone breathing today would be long gone before the secret of the RSA-129 message would be revealed.
Fifteen years later, the public-key encryption scheme had spread into many security systems, and the RSA-129 key was still unbroken. That's when, in 1992, a 21-year-old M.I.T. electrical engineering graduate student named Derek Atkins first saw the PGP program, which was based on the RSA key. Atkins immediately recognized its importance and joined the worldwide, unpaid development team that works on new versions of the software. But as Atkins talked to friends about the program, he began to wonder what attacks might work against it.
It is worth noting that since 1977 when Rivest posited his RSA-129 challenge, advancements in the mathematics of factoring had advanced at a steady pace. Thus, with the help of these advancements and the software written by Atkins and his team to gather what they called the "needles"—the possible factors of very large prime numbers—they set out to crack RSA-129. From September 1992 to April 1993, they employed more than 1,600 computers, from desktop PCs to Bellcore's 16,000-processor MasPar supercomputer, the equivalent of about 5,000 MIPS years. When Atkins and the others guessed that they had enough unit vectors, or "needles," for the calculation, they gathered them to find the private key. On April 26, 1993—roughly eight months after they started—Atkins posted the key for RSA-129 on the Net:
We are happy to announce that RSA-129 =
11438162575788886766923577997614661201021829672124236256256184293
5706935245733897830597123563958705058989075147599290026879543541 =
3490529510847650949147849619903898133417764638493387843990820577 *
327691329932667709549961988190834461413177642967992942539798288533
Applying the key yielded the message: "The magic words are squeamish ossifrage." An ossifrage is a large predatory bird of the vulture family, ranging from the mountainous regions of southern Europe to China and having a wide wingspan and black plumage. Not surprisingly, Rivest had forgotten what the message contained.
Atkins and his team donated the money to the Free Software Foundation. It is only fair to report that Rivest, aware of recent advancements in factoring algorithms, had resolved to himself that one day he might have to write the check for $100. "[My original estimate of 40 quadrillion years] was probably accurate for the analysis of the fastest algorithm we knew about at the time, but technology was moving fast on the factoring frontier," Rivest said.
It is also important to note that breaking the RSA-129 does not mean that PGP in particular, or RSA encryption in general, is weak. An RSA key based on a 129-digit prime is only 425 bits long. Atkins later calculated that had his team attempted the same task, using the same factoring algorithm with the recommended RSA key of 1,024 bits, their computers would still be working on the problem—for a few more million years.
We have touched upon a number of concepts and terminology associated with sophisticated cryptography in the sections above. Now, let's move on to some of the other key issues and how they relate to the strategy Microsoft is planning for the future.
Microsoft has made a strong commitment to supporting existing Internet standards. Microsoft is actively participating in the Internet Engineering Task Force (IETF), World Wide Web Consortium (W3C), and other organizations. Recent examples include the Personal Information Exchange (PFX) protocol submitted to the W3C Digital Signature Initiative; the code signing proposal submitted to the W3C; and the Transport Layer Security (TLS) standard aimed at creating a single secure channel standard.
Standards are the force behind the success and power of the Internet. These include:
To that end, Microsoft will support all HTML extensions, file formats, languages, and protocols that its customers require to create compelling software solutions. Microsoft will continue to research and monitor Internet technology, such as Java™ and HTML, including noncompliant but popular HTML extensions. As Microsoft moves forward in addressing the challenges of the Internet, it will continue to work with the standards bodies to ensure that it is openly publishing its proposed extensions, protocols, and file formats.
To be effective, security systems need to be usable as well as secure. It stands to reason that prohibitively hard-to-use schemes, which require new passwords and separately designed server components will simply not be used as often as a scheme built into the design of the components already in use.
What this means to end users is that, no matter which platform or browser is used, the security component should be transparent. Let's consider again the case of Alice. Alice has spent hours at the office getting digital IDs, keys, and encrypted messages on her office IBM-compatible PC with the "Brand X" browser. She needs to continue her work at home on her Macintosh with the "Brand Y" browser. She should also be able to take her digital IDs to a friend's house, to a mall, or to a kiosk. If she does not have this capability, she will be locked into using one machine, one platform, and one brand of browser. The challenge is to continue to define and adopt standards to allow Alice to go anywhere and do anything irrespective of which tools she employs.
Standards are critical to establishing a common security framework for communicating among applications or providing access to information to users on various platforms. One of the first successes has been the unification of a standard for credit card-like transactions over the Internet.
Visa, MasterCard, Netscape, Microsoft, and others have worked to combine the two formerly dominant specifications for the secure transaction of commerce over the Internet: Secure Transaction Technology (STT) and Secure Electronic Payment Process (SEPP). By June 1996, this combined specification—Secure Electronic Transactions (SET)—will be finalized. The results of this cooperation show that standards are achievable and beneficial not only for developers, but also for the end users if we still desire to be able to use any platform and any browser to connect to the Internet. Clearly, both industry and customers benefit from a single standard for commercial transactions.
Microsoft is also pursuing an effort to create a single standard for the transfer of secure business and personal communications over insecure phone lines. A central component of this effort is to develop a method of authentication.
Encryption and authentication go hand in hand in a secure Internet or intranet environment. Each, though distinctly different, play an important role in allowing users to pass information that is unreadable except by the intended recipient and in verifying the identify of the sender.
Authentication in a digital setting is a process whereby the receiver of a digital message can be confident of the identity of the sender and/or the integrity of the message. Authentication protocols can be based on either conventional secret-key cryptosystems like DES or on public-key systems like RSA or Microsoft's PCT. In public-key systems, authentication uses digital signatures.
In this article, authentication generally refers to the use of digital signatures, which are the equivalent of handwritten signatures for printed documents: The signature is an unforgeable piece of data asserting that a named person wrote or otherwise agreed to the document on which the signature appears. The recipient, as well as a third party, can verify both that the document did indeed originate from the person who signed it and that the document has not been altered since it was signed. A secure digital signature system thus consists of two parts: a method of signing a document so that forgery is unfeasible and a method of signature verification. Furthermore, secure digital signatures cannot be repudiated; that is, the signer of a document cannot later disown it by claiming it was forged, since each digital signature is registered with a Certificate Authority (CA).
There are currently two widely used standards for such secure communications: Netscape's Secure Sockets Layer (SSL) and Microsoft's Private Communication Technology (PCT). As was the case with SET, both developers and end users would benefit greatly from a single standard.
To help facilitate movement in that direction, Microsoft has created a discussion draft called Secure Transport Layer Protocol (STLP), which is rapidly becoming Transport Layer Security (TLS). This specification starts with Netscape's SSL version 3.0 and adds features from Microsoft's PCT version 2.0 based on feedback from cryptographers and implementers. It is intended to provide a simpler and more robust implementation than SSL or PCT, with added scalability, improved security, and the additional functionality needed for wider application of the specification. For an expanded discussion of standards and Microsoft's goals for security technology, plus an invitation to software developers to submit their security technologies, see Microsoft Submits Draft on Security Interoperability to W3C (http://microsoft.com/intdev/security/secw3c-f.htm).
Of course, a lot of work has to be done besides participating with standards bodies and posting press releases. One of Microsoft's contributions has been to integrate these standards into all of its Internet development. In terms of implementation, with an Internet Information Server solution running on Windows NT, privacy becomes a matter of mouse clicks away for a site administrator.
Microsoft's support for SSL 2.0 and 3.0, and Private Communication Technology (PCT) 1.0, for example, secures general-purpose business and personal communications on the Internet or intranets by providing the following:
Microsoft has announced a collection of technologies to address the concerns of Fortune 500 corporate information service (IS) groups, independent software vendors (ISVs), and Webmasters interested in the convergence of the corporate intranet and the public Internet. The Microsoft Internet Security Framework—a comprehensive set of public-key and password-based security technologies—provides the ability to:
The Microsoft Internet Security Framework accomplishes this without requiring replacement of an existing security model. Instead, it builds on the Windows operating system security model and also provides an extensible architecture that integrates these security technologies into this model.
As mentioned earlier, it is extremely important that users feel comfortable storing personal security information, such as credit card numbers and private keys, on their computers and that this information be available—subject to a user's approval—to different programs such as browsers and e-mail applications. To satisfy these requirements, one technology emerging from the Microsoft Internet Security Framework is the "digital wallet."
The wallet resides on a user's computer (or another hardware device such as a smartcard). It securely stores personal security information such as private keys, credit card numbers, and certificates. Like all Microsoft Security Framework services, it has standard programming interfaces that make it accessible to other programs in a protected and controlled fashion. The contents of the wallet can be transported across machines, platforms, and browsers using the PFX protocol. An access control policy determines who has access to the information.
Internet Explorer 3.0 contains a simple certificate store or database to support client authentication. The wallet is slated initially to ship in a release of Internet Explorer (all platforms) and will eventually be integrated into the Windows operating system.
For more information, check out the Microsoft Internet Security Framework.
Not since the first software was made available on CD-ROM have software publishers and independent developers alike been so excited about a new way to distribute their work. Via the Internet, manuals, upgrades, patches, even full release software can be made almost instantly accessible to users at a fraction of the manufacturing and distribution costs. With the security problems of online commerce largely addressed, online delivery of software has the potential to eliminate not only some components of costly order processing but also to lower the cost of goods. No longer must publishers provide disks, perfect-bound manuals, expensive packaging, or environmentally destructive packing foam, not to mention suffering the costs and delays implied in shipping.
But wait! This "wonder channel" for software delivery is not without its potential problems. Besides the considerable download time required to transfer large applications, the security risks associated with downloading software over the Internet include "Trojan Horse" attacks, viruses, counterfeit publishing and "gray market" losses, and even the malicious modification of code. That's where code signing comes in.
Code signing solves these problems by eliminating two of the major risks to users who download code: (1) it ensures the user that they are receiving the code from the software maker, and (2) it alerts the user if the code has been modified since it was signed by the software publisher.
Code signing uses some of the same concepts already discussed in this document and is explained in "Microsoft Authenticode Technology" on Microsoft's Security Advisor Web site at http://microsoft.com/security/.. If you need more information or have specific questions, please send e-mail to safecode@microsoft.com.
The advantage of code signing is that it enables the recipient to identify who published the software before downloading it as well as verify that no one tampered with it. Authors of ActiveX™ controls and other enhancements to Internet tools should be able to recognize this benefit immediately.
Microsoft Internet Explorer 3.0 supports code signing. For a description of the security features employed in Microsoft's Internet Explorer, including digital code signing and CryptoAPI 1.0, see "Using Authenticode" and the Microsoft Internet Security Framework
Microsoft and VeriSign, Inc., the leading provider of digital authentication products and services, have announced they will jointly promote secure authentication and distribution of software over the Internet. The companies have worked together to define a set of technologies for content signing using Digital Signatures and Digital IDs. A Digital ID, a kind of digital "passport" or "credential," is a user's public key that has itself been "digitally signed" by a trusted party, such as a network security director, MIS help desk, or VeriSign, Inc. Microsoft will be incorporating the technology into the appropriate Internet development components.
For related information, call VeriSign at (415) 961-7500 or visit the VeriSign Web site (http://www.verisign.com/).
A certificate is analogous to a notary seal on a document. It must be kept current and subject to verification on a certificate revocation list (CRL). If a certificate is revoked—as a credit card is revoked—the document it is attached to should be treated as suspect. Just as a bank cannot force people to cut up their credit cards, a Certificate Authority (CA) cannot force the destruction of all copies of a certificate. Therefore, someone who is going to use a certificate should check it against a CRL to ensure the validity of the certificate and the recipient must have a convenient way to make that determination. That's where the Certificate Server comes into play.
The Certificate Server is designed to make certificate management tasks as simple as possible by issuing, managing, and revoking certificates. Because the Microsoft Internet Security Framework is an integral part of the Windows NT security model, certificates can be mapped to a Windows NT group. This means that you can use the standard Windows NT administrative tools, such as access control lists, to handle Internet security matters. The Certificate Server will also be integrated with BackOffice™.
The Certificate Server is integrated with an Open Database Connectivity–compliant database such as Microsoft SQL Server™ that holds such information as CRLs, auditing information about certificates that were issued, and copies of certificates. Some key features of the Certificate Server are:
For information on how to obtain a certificate, see "Frequently Asked Questions About Authenticode". For a complete discussion of the features in this section, see "The Microsoft Internet Security Framework".
Barrus, Karl L. "Protecting Your Privacy." Network Computing, April 1, 1995.
Berg, Al. "Spinning Your Web with Windows NT: Speed, Security, Interface Make Platform Ideal for Today's Generation of Web Servers." LAN Times, December 18, 1995, vol. 12, no. 26, p. 73(2).
Coffee, Peter. "Real Grounds for Java Jitters." PC Week, April 8, 1996, vol. 13, no. 14, p. 84(1).
Higgins, Kelly Jackson. "Swarming Your Sites: Secure Web Sites Attract Hackers." CommunicationsWeek, April 8, 1996, no. 605, p. 37(4).
Levy, Steven. "Wisecrackers." Wired, March 1996.
Linthicum, D. "RSA Connects Virtual Private Networks Across Internet." Distributed Computing Monitor, March 1996, vol. 11, no. 3, p. 22(3).
Rodriguez, Karen. "Safety on the 'Net: Can Encryption Offer Peace of Mind to Nervous Network Managers?" CommunicationsWeek, March 25, 1996, no. 602, p. 1(3).
RSA Data Security, Inc. "Frequently Asked Questions About Cryptography Export Laws." 1996.
RSA Laboratories. RSA Cryptography Today FAQ. Archive name: cryptography-faq/rsa/part1 1993.
Taft, Darryl K. "Netscape's Navigator: Teenager Responsible for Hacking Out Bugs in Popular Netscape Browser." Computer Reseller News, April 29, 1996, p. 1(1).
Violino, Bob. "Your Worst Nightmare." InformationWeek, February 19, 1996, p. 34(3).