CIPHERTEXT The RSA Newsletter Volume 1, No. 1, Fall 1993 A publication of RSA Data Security, Inc. Copyright _ 1993 RSA Data Security, Inc. All rights reserved. For reprints, call your RSA representative. IN THIS ISSUE: Clipper Controversy Continues Page 1 1994 RSA Data Security Conference Page 1 Apple Ships System 7 Pro Page 2 Internet PEM Arrives Page 2 RSA Opens Certificate Services Center Page 3 New Wireless Security Standards Page 4 Arkhon Extends Kerberos With RSA Page 4 Hilgraeve Licenses RSA for Best-Selling Asynch Package Page 5 RSA Licensee Spotlight: Datamedia Page 5 Difficulty of Factoring Page 6 Factoring Challenge Update Page 6 RSA Laboratories Report Page 6 PKCS Update Page 7 Clipper: One Scientist's Perspective Page 7 The SmartCard That Needs No Reader Page 9 1994 RSA Conference Registration Form Page 11 THE CLIPPER CONTROVERSY CONTINUES The government's involvement in cryptography standards and public policy have again provoked strong reactions in the crypto community with the announcement of the Clipper Chip, an encryption scheme with an acknowledged, built-in system for government law-enforcement and intelligence agency monitoring. We present here a relatively technical overview of the proposal. Dr. Martin Hellman offers his personal opinions later in this Newsletter. -Ed. Clipper is an encryption chip developed and sponsored by the U.S. government as part of the Capstone project. Announced by the White House in April, 1993 Clipper was designed to balance the competing concerns of federal law- enforcement agencies with those of private citizens and industry. The law- enforcement agencies wish to have access to the communications of suspected criminals, for example by wire-tapping; these needs are threatened by secure cryptography. Industry and individual citizens, however, want secure communications, and look to cryptography to provide it. Clipper technology attempts to balance these needs by using escrowed keys. The idea is that communications would be encrypted with a secure algorithm, but the keys would be kept by one or more third parties (the "escrow agencies"), and made available to law-enforcement agencies when authorized by a court- issued warrant. Thus, for example, personal communications would be impervious to recreational eavesdroppers, and commercial communications would be impervious to industrial espionage, and yet the FBI could listen in on suspected terrorists or gangsters. In the case of Clipper, each key is split into two parts, each of which is stored at one of two escrow agencies; both parts must be known in order to recover the key. Clipper has been proposed as a U.S. government standard; it would then be used by anyone doing business with the federal government as well as for communications within the government. For anyone else, use of Clipper is strictly voluntary. AT&T has announced a secure telephone that uses the Clipper chip. The Clipper chip contains an encryption algorithm called Skipjack, whose details are classified. Each chip also contains a unique 80-bit unit key U, which is escrowed in two parts at two escrow agencies. Also present is a serial number and an 80-bit "family key" F; the latter is common to all Clipper chips. The chip is manufactured so that it cannot be reversed engineered; this means that the Skipjack algorithm and the keys cannot be read off the chip. When two devices wish to communicate, they first agree on an 80-bit "session key" K. The method by which they choose this key is left up to the implementer's discretion; a public-key method such as RSA or Diffie-Hellman seems a likely choice. The message is encrypted with the key K and sent; note that the key K is not escrowed. In addition to the encrypted message, another piece of data, called the law-enforcement block, is created and sent. It includes the session key K encrypted with the unit key U, then concatenated with the serial number of the sender and an authentication string, and then, finally, all encrypted with the family key. The receiver decrypts the law- enforcement block, checks the authentication string, and decrypts the message with the key K. Now suppose a law-enforcement agency wishes to tap the line. It uses the family key to decrypt the law-enforcement block; the agency now knows the serial number and has an encrypted version of the session key. It presents an authorization warrant to the two escrow agencies along with the serial number. The escrow agencies give the two parts of the unit key to the law-enforcement agency, which then decrypts to obtain the session key K. Now the agency can use K to decrypt the actual message. It has not yet been decided which organizations will serve as the escrow agencies, that is, keep the Clipper chip keys. No law-enforcement agency will be an escrow agency, and it is possible that at least one of the escrow agencies will be an organization outside the government. It is essential that the escrow agencies keep the key databases extremely secure, since unauthorized access to both escrow databases could allow unauthorized eavesdropping on private communications. In fact, the escrow agencies are likely to be one of the major targets for anyone trying to compromise the Clipper system; the Clipper chip factory is another likely target. The encryption algorithm contained in the Clipper chip is known as Skipjack and was designed by the NSA. It uses an 80-bit key to encrypt 64-bit blocks of data; the same key is used for the decryption. Skipjack can be used in the same modes as DES and may be more secure than DES, since it uses 80-bit keys and scrambles the data for 32 steps, or 'rounds'; by contrast, DES uses 56-bit keys and scrambles the data for only 16 rounds. The details of Skipjack are classified, although the government has invited a small group of independent cryptographers to examine the algorithm. The decision not to make the details of the algorithm publicly available has been widely criticized. Many people are suspicious that Skipjack is not secure, either due to oversight by its designers, or by the deliberate introduction of a secret trapdoor. Another consequence of Skipjack's classified status is that it cannot be implemented in software, but only in hardware by government- authorized chip manufacturers. Controversy has arisen in many areas: first, there is controversy about the whole idea of forced escrow of keys. Those in favor of escrowed keys see it as a way to provide secure communications for the public at large while allowing law-enforcement agencies to monitor the communications of suspected criminals. Those opposed to escrowed keys see it as an unnecessary and ineffective intrusion of the government into the private lives of citizens. They argue that escrowed keys infringe their rights of privacy and free speech. It will take a lot of time and much public discussion for society to reach a consensus on what role, if any, escrowed keys should have. The second area of controversy concerns various objections to the specific Clipper proposal, that is, objections to this particular implementation of escrowed keys, as opposed to the idea of escrowed keys in general. Common objections include: the Skipjack algorithm is not public and may not be secure; the key escrow agencies will be vulnerable to attack; there are not enough key escrow agencies; the keys on the Clipper chips are not generated in a sufficiently secure fashion; there will not be sufficient competition among implementers, resulting in expensive and slow chips; software implementations are not possible; and the key size is fixed and cannot be increased if necessary. Silvio Micali has recently proposed an alternative system that also attempts to balance the privacy concerns of law-abiding citizens with the investigative concerns of law-enforcement agencies. Called fair public-key cryptography, it is roughly similar to the Clipper chip proposal but users can choose their own keys, which they register with the escrow agencies. Also, the system does not require secure hardware, and can be implemented completely in software. - Paul Fahn APPLE SHIPS RSA DIGITAL SIGNATURES IN LONG-AWAITED SYSTEM 7 PRO On October 4th, Apple Computer introduced millions of new users to the RSA Digital Signature. The products are called PowerTalk and PowerShare, and they are part of System 7 Pro, a revolutionary new version of the Macintosh's advanced operating system. Evolving personal communications needs, coupled with organizational trends, have fueled demand for a whole new class of applications, which Apple calls collaborative applications, which enable individuals to communicate and work together with each other more effectively. To establish the foundation for such applications, Apple extended its System 7 operating system with a tightly integrated set of capabilities called PowerTalk and PowerShare. PowerTalk and PowerShare consist of five components, tightly integrated with the operating system itself: Messaging, Electronic Mail, Directories, Privacy and Authentication, and Digital Signatures. Every user will have access to RSA Digital Signature technology for messaging authentication and RSA's lightning fast RC4 symmetric stream cipher for server-to-server link encryption. Furthermore, every application developer has access to these services as well, and third party Mac products using PowerTalk's RSA capabilities are available now from Shana Corporation, and many others are coming soon. PowerTalk is compliant with the Public Key Cryptography Standards (PKCS), which Apple helped develop, and users will receive a voucher for a free unaffiliated "residential" digital certificate, good for use with any secure PKCS or Internet PEM-compliant application (see Certificate Services article, next page). For more information on System 7 Pro or PowerTalk and its RSA security implementation, contact Pierre LeClercq at Apple Computer at 408/974-3179. - Kurt Stammberger INTERNET PRIVACY ENHANCED MAIL ARRIVES Several commercial and "freeware" versions of Internet Privacy-Enhanced Mail are available right now. Here are just a few that you can use to start sending encrypted, authenticated mail over the Internet. TechMail Written at MIT, TechMail provides an easy-to-use electronic mail reading program for Macintosh and (soon) Windows platforms. TechMail includes a full implementation of the Internet PEM RFC's, using RSA's TIPEM toolkit as its security "engine." TechMail is a client of the Internet "Post Office Protocol" (or just POP). With POP, E-mail is not directly delivered to a person's PC or Macintosh but instead is delivered to a POP server. This is important when people wish to turn off (or take home with them!) their systems at the end of the day - their mail will be accepted and held at the "Post Office" until they request it. Today, TechMail for the Mac (both SLIP and non-SLIP) is available on the Internet via anonymous FTP from net.dist.mit.edu (in pub/TechMail). Although only the Macintosh versions of TechMail are available today, work is progressing on the Microsoft Windows version which should be available shortly. TIS/PEM and T-Mail TIS/PEM is a non-commercial freeware implementation of Internet PEM that was developed by Trusted Information Systems under contract with ARPA and agreement with RSADSI, and is available in source code for academic research or exploratory use by corporations and individuals on the Internet. TIS/PEM was designed by TIS to be easily integrated into any UNIX-based E-mail message handling package. Currently, TIS/PEM operates on a majority of the UNIX systems used on the Internet, and has also been integrated with the widely used Rand MH Mail User Agent software, which is fully compatible with SMTP- based MTA's (such as Sendmail and MMDF). T-Mail, or "Trusted Mail" is TIS's commercial, supported version of the TIS/PEM product, and is available on multiple platforms. For more information on T-Mail or TIS/PEM, please send requests via E-mail to tispem-support@tis.com, or call Frederick Avolio at TIS at (301) 854-6889. TIPEM 1.1 TIPEM version 1.1 is the latest release of RSA's Toolkit for Interoperable Privacy-Enhanced Messaging. The upgrade includes several new modules which allow developers to create applications that comply to the Internet Privacy- Enhanced Mail (PEM) standards, as well as the commercial Public Key Cryptography Standards (PKCS) established by vendors including Lotus, Apple, Novell and Microsoft. The toolkit, which has been used for major communications security development projects such as Apple's PowerTalk, allows software developers to easily add RSA public key encryption and authentication features to any mail, mail-enabled or messaging-based application. TIPEM is available direct from RSA Data Security, Inc. RIPEM RIPEM is another "freeware" public key encryption program designed for Internet PEM. RIPEM version 1.1 implements a subset of Internet Privacy- Enhanced Mail (PEM), as described in Internet RFC's 1421-1424. RIPEM implements a number of mechanisms to manage public keys. RIPEM can obtain public keys from user-managed files, from Internet key servers, and via the Internet "finger" protocol. The Internet host ripem.msu.edu acts as a RIPEM key server for users who choose to register their keys. RIPEM is for the Macintosh, MS-DOS, Windows NT, OS/2, and all major versions of UNIX. RIPEM is available via anonymous FTP to rsa.com, and via non-anonymous FTP to ripem.msu.edu. RSA CERTIFICATE SERVICES CENTER OPENS FOR BUSINESS Last month, the RSA Certificate Services Center (CSC) officially opened for business. Right now, today, you can obtain real certificates with your name, public key, and organizational affiliation safely embedded in a cryptographically tamper-proof digital document. These RSA digital certificates are your "digital I.D.", needed for use with Apple PowerTalk, Internet Privacy-Enhanced Mail, or any X.509 certificate-based secured application. The Certificate Services Center is designed to provide one-stop shopping for everyone's needs, whether you just need one certificate for yourself Ð or the ability to issue millions for your employees. Getting a Certificate There are two primary types of certificates that are supported by the RSA Certificate Services Center: affiliated and unaffiliated. The first type of certificate has an organizational affiliation; e.g., "John Doe, Engineering, Apple Computer, Inc." The second type of certificate has none: just "John Doe". Of course, any given person may have multiple certificates. There are three ways to get a certificate: 1. You can issue your own affiliated certificates, using RSA's Certificate Issuing System (CIS). When you purchase RSA's Certificate Issuing System (CIS), you establish your company or organization as a Certification Authority. You can issue your own certificates for your employees and affiliates in the RSA Commercial Hierarchy. 2. The CSC can issue affiliated certificates for you, using a CIS housed at the Certificate Services Center ("Co-Issuer Relationship"). Alternately, your company or organization can "rent space" on a CIS housed at RSA's Certificate Services Center. Your organization's RSA private keys are stored inside the CIS and managed by CSC personnel. CSC personnel process requests from your organization and issue digital certificates on your behalf. 3. You can purchase individual unaffiliated certificates directly from the CSC. You can generate a request form for a certificate, known as a Certificate-Signing Request using RSA-licensee packages like Apple's PowerTalk or RSA's own TIPEM developer's toolkit. Once that form is notarized, you send it to the CSC for fulfillment, and the CSC sends back your certificate on diskette or via E-mail. Revoking a Certificate Just like a credit card, occasionally a certificate needs to be "hot listed" or revoked. This situation may arise if the integrity of the certificate is jeopardized in any way, for example: o the owner's RSA Private Key is stolen or compromised; o the certificate owner changes her name (gets married); o the owner of an affiliated certificate loses affiliation (i.e. graduates from a University or is fired from a job) The CSC manages and disseminates Certificate Revocation Lists (CRLs) for the entire hierarchy, and revokes certificates on the behalf of its Co-issuer and Unaffiliated customers. Verifying a Certificate There will be occasions when you want an up-to-the-second check on the validity status of a certificate. The RSA Certificate Services Center offers several different ways to accomplish this: Telephone Ð the CSC maintains an automated voice response unit that gives the current status of any certificate in the entire Hierarchy, simply by keying in the certificate and issuer serial numbers on your touch-tone phone. Internet Ð the CSC maintains an automated certificate status E-mail responder. Modem Ð you can dial directly into the CSC host and gain certificate status information from the RSA Commercial Hierarchy BBS. For more information contact George Parsons, CSC Manager, at 415/595-8782. RSA ENTERS WIRELESS ARENA IN NEW CDPD STANDARDS A group of major cellular carriers recently announced release 1.0 of the Cellular Digital Packet Data specification, an open standard designed to enable customers to send computer data over existing cellular networks. The release of the specification is a milestone for the communications and computer industries, enabling the introduction of a variety of new products and applications to serve business and consumer users who need access to information anytime, anywhere. But what makes the CDPD standards particularly significant is that they are the first cellular specifications to include built-in encryption and authentication, using two technologies in the BSAFE toolkit from RSA Data Security, Inc.: the Diffie-Hellman Key Agreement public key algorithm and the RC4 Symmetric Stream Cipher. The specification will aid applications such as secure wireless electronic mail messages, database queries or credit card authorization. Network manufacturers with CDPD projects under development include AT&T Network Systems, Motorola, Hughes Network Systems, Cascade Communications Corporation and Steinbrecher, Inc. Software companies such as EDS, Alcatel TITN, Retix and Cellular Data, Inc. are already developing platforms that will drive the CDPD engine. A number of hardware companies have also announced plans to introduce CDPD-based products, including Apple, IBM, Eo and Cincinnati Microwave, Inc. Virtually the entire cellular carrier industry is behind the CDPD effort, with funding provided by carriers such as McCaw, NYNEX, PacTel, Ameritech and many others. The CDPD 1.0 specification provides network and customer equipment manufacturers the parameters for building to this nationwide approach that sends packets of data in previously "wasted" or unused bandwidths, such as in the pauses between words in a cellular telephone conversation. The spec includes details of the CDPD architecture, airlink, external network interfaces, network support services, network applications services, network management, radio resource management, radio media access control and, of course, encryption and authentication. Those interested in obtaining a copy of the CDPD specification can contact Tom Solazzo, CDPD Project Coordinator at 714/545-9400 ext. 235. RSA is offering low-cost, standardized BSAFE licensing terms for all CDPD implementors. Contact Paul Gordon at RSA at 415/595-8782 for more information. ARKHON TECHNOLOGIES BUILDING RSA-EXTENDED KERBEROS NETWORK SECURITY SYSTEM Arkhon Technologies. Inc., located in Cerritos, California, has recently joined the RSA family. Arkhon's new enterprise management product requires the distribution and maintenance of private keys throughout a large network, which is divided into a number of Kerberos V domains, and incorporates multiple vendors and protocols. The Arkhon solution to these security requirements, which is being built with RSA's TIPEM toolkit, provides secure key management for any number of distributed Kerberos V servers supporting both logical and physical domains. There are three distinct levels of enterprise management in Arkhon's product: l. the management of the physical network and the distributed communications environment itself; 2. the remote administration and automation of the control functions for distributed nodes of the network; 3. the remote administration and automation of the control functions for sub-systems and application software running on the distributed platforms. Arkhon has joined together with the pre-eminent system software vendors in the industry, including companies such as RSA, Oracle and OCSG. Sometimes called a "virtual corporation", such partnerships allow a group of specialized companies to combine their expertise synergistically to create products with complex functionality in a more timely fashion than traditional software producers. Arkhon's architecture allows the modular incorporation of any required system or application software, providing to the user a single programming interface and a consistent look and feel. Additionally, Arkhon offers consolidated support, training, on-line documentation, and tutorial software for its full product line. Arkhon and its partners constitute the only virtual corporation with complex solutions to the problems of enterprise management. Contact Arkhon at 310/809-0760. - Stan Tomsic, Arkhon Technologies RSA LICENSEE UPDATE You can find RSA technology in more products from more vendors than ever before! Here is a partial list of products available now or coming soon: Security in the OS o Novell NetWare 4.0 o Apple System 7 Pro PowerTalk (AOCE) o Microsoft Windows NT Secure E-mail o Enterprise Solutions X.400 Mail o Trusted Information Systems T-Mail o Datamedia SecurExchange Secure Telephone & Fax o Motorola Commercial STU's o AT&T 3600, 4100 o Secure Communications, Inc. (ICTI) Secure Workgroup o Lotus Notes o Microsoft Windows for Workgroups Secure Electronic Forms o WordPerfect InForms o Delrina PerForm PRO o BLOC F3 Forms Automation Link and Node Encryption o Semaphore Communications NEU's o Racal Datacom Datacryptors o Cylink Link Encryptors o Newbridge Networks TAP System o IBM 4755 and 4753 o Northern Telecom X.25 PDSO Secure Remote Access o Hilgraeve HyperACCESS/5 o ANS CO+RE InterLock o Hughes NetLock TCP/IP o Fischer International RSA/3270 HILGRAEVE LICENSES RSA FOR BEST-SELLING ASYNCH PACKAGE Hilgraeve, Inc. is about to release the very first mass-market asynchronous communications package with RSA encryption capabilities built right in. And the current release of that software, HyperACCESS/5, is already a market leader. HyperACCESS/5 is Hilgraeve's top-of-the-line communications software for DOS, OS/2 and Windows. It is Hilgraeve's flagship product, providing asynchronous communications and remote workstation control via modem, ISDN telephone deskset, networked or RS232 connections. HyperACCESS/5 has received PC Magazine's Editors' Choice Award three out of the last five years for its quality, performance and ease of use. Now, using RSA's BSAFE cryptographer's toolkit, point-to-point encryption will be integrated as a standard feature in future versions of the HyperACCESS/5 product. Founded in 1987, Hilgraeve is a privately-held company, a pioneer developer and patent holder in the field of high performance communications software. For more information on HyperACCESS/5, contact Matt Gray at Hilgraeve at 313/243-0576. RSA LICENSEE SPOTLIGHT: DATAMEDIA'S SECUREXCHANGE Datamedia Corporation, based in Nashua, New Hampshire, joined the RSA family last May with the goal of creating a piece of software that could be used to bring RSA's state-of-the-art security and authentication features to any E- mail system. They have since achieved that goal: the product is called SECURExchange, and it can be used to secure virtually any existing DOS, Windows or Macintosh E-mail system. In analyzing the market potential for this new product, Datamedia realized that while electronic mail networks have become critical parts of the communication infrastructure in most organizations, most commercial E-mail systems have little or no capability to protect sensitive information transmitted over networks. And the E-mail packages that do claim "encryption" features typically use unproven, cryptographically weak homegrown scrambling schemes. In its market survey, Datamedia discovered that many organizations that were aware of the risks inherent in unsecured E-mail transmission of sensitive documents placed tight restrictions on what could and could not be sent via E- mail, thereby devaluing the company's substantial investment in the technology, and forcing the organization back to expensive, inefficient transport mechanisms, such as next day air or sealed interoffice mail for sensitive documents. Datamedia is helping companies gain back the E-mail advantages of speed, convenience and cost savings for any document. Datamedia's product is designed to help organizations realize the full potential of their E-mail investment, by allowing transmission of even the most confidential or tamper-sensitive information over existing unsecured E-mail systems. SECURExhange is an add-in software application that upgrades your existing E- mail infrastructure with privacy, authentication and positive identification features. To accomplish this, SECURExchange uses: RSA Digital Envelopes Files transmitted using SECURExchange can be placed in a secured electronic "envelope" that can only be opened by the addressee. The envelope consists of one or more files which are encrypted using the RSA Public Key Cryptosystem and DES. RSA Digital Signatures Files digitally signed by SECURExchange cannot be tampered with without the recipient's knowledge, and the recipient can furthermore be absolutely assured of the identity of the signer in any given message. RSA Digital Certificates SECURExchange uses industry standard X.509/PKCS Digital Certificates to prove identity and RSA Public Key ownership over a network. Certificates, combined with SECURExchange's compliance to the Public Key Cryptography Standards (PKCS) mean that users can securely communicate worldwide with users of a growing family of secured applications, including Internet Privacy-Enhanced Mail, Apple PowerTalk and BLOC F3 Forms Automation. SECURExchange has been fully tested with many existing electronic mail systems, including cc:Mail, Microsoft Mail, DaVinci Mail, Beyond Mail, Internet, Compuserve, MCI Mail, AT&T EasyLink and many, many more. For more information on SECURExchange, call Datamedia at 603/886-1570. DR. RON RIVEST ON THE DIFFICULTY OF FACTORING (Since the difficulty of "cracking" the RSA algorithm has long been believed to be roughly equivalent to the difficulty of factoring a given RSA modulus, we have decided to reprint one of Ron Rivest's classic papers on the difficulty of the factoring problem. -Ed.) Abstract Here are the results of some simple estimations I have done on the projected difficulty of factoring various sizes of numbers for the next 25 years. The basic question is: "In the year YYYY, what size number will I be able to factor for an investment of $DDDD?" To be specific, I've looked at YYYY= 1990, 1995, 2000, 2005, 2010, 2015 and $DDDD = $25K, $25M, and $25G (that is, $25,000, $25,000,000, and $25,000,000,000). The three levels might correspond to "individual", "corporate", and "national" levels of attack. All calculations are done in 1990 dollars. Each of these estimates is also done in an "high," "average," and "low" point of view. (That is, the high estimates are for the greatest number of digits possible, while the low estimates are for the least number possible.) The estimates are done in terms of MIP-years, a computational unit of power analogous to a "kilowatt-hour" of electricity. Specifically, a MIP-year is the computational power of a one-MIP machine running for one year. A MIP (more correctly, a MIPS) is a "million-instruction per second" machine. Today's workstations run in the 1 to 10 MIPS range, and 100 MIPS machines are under development. One MIP-year corresponds to 3.15x1013 operations. Factoring algorithms To factor a number n with current technology using the best known algorithms, we need a number of operations roughly equal to L(n) = exp (_ ln n ln ln n) (1) (Using, say, the quadratic sieve algorithm.) We use this formula for our "low" estimates, since this is currently achievable. For our "average" estimate, we use the formula A(n) = min (L(n), exp (2.08 (ln n)l/3 (ln ln n)2/3)) (2) This presupposes that the number field sieve (NFS) can be generalized to handle ordinary (cryptographic) numbers, as conjectured in the 1990 ACM STOC article. Finally, for the high estimates, we use the formula H(n) = exp (1.526 (ln n)l/3 (ln ln n)2/3) (3) which is the number of operations that NFS now uses for rarefied numbers. (Achieving this formula would be quite a breakthrough.) Costs of computation I estimate that today a MIP-year costs about $10, as follows. You can buy (parts for) a 10-MIP machine for about $500. With a lifetime of five years, you get 50 MIP-years out of the machine. As for rates of technological progress, for the "low" estimate I assume that technology only advances at 20%/year. For the "average" estimate I assume that technology advances at 33%/year, and for the "high" estimate I assume 45%/year. These are measured in terms of the drop in the cost of a MIP-year in constant 1990 dollars. Thus, under the high estimate, $10 will buy 1.45 MIP- years in 1991 and 2.10 MIP-years in 1992, etc. At this rate, we can estimate the number of MIP-years that can be bought for $1 as follows: Year Low Average High 1990 0.100 0.100 0.100 1995 0.249 0.416 0.641 2000 0.619 1.732 4.109 2005 1.540 7.207 26.340 2010 3.833 30.000 168.800 2015 9,540 124.800 1082.000 2020 23.74 519.500 6935.000 Combining this with our "low" ($25K), "average" ($25M), and "high" ($25G) estimates for dollars available, we arrive at the following chart for the number of MIP-years affordable. (Here T is the abbreviation for "tera," i.e. 1012.) Year Low Average High 1990 2.5K 2.5M 2.5G 1995 6K 10M 16G 2000 15K 43M 103G 2005 38K 180M 658G 2010 96K 750M 4.2T 2015 239K 3.1G 27T 2020 549K 13G 173T That is, in the year 2020, a determined opponent with $25G might be able to afford 173 tera MIP-years to attack a number. Results We now give the number of operations required to factor numbers of various sizes under our low, average, and high estimates (formulas (1), (2), and (3)). These are given in MIP-years. Digits Low Average High 100 74 74 0.1 150 1M 1M 38 200 4G 4G 4K 250 6T 2T 261K 300 5 x 1015 3 x 1014 10M 350 2 x 1018 2 x 1016 252M 400 9 x 1020 1018 5G 450 2 x 1023 6 x 1019 81G 500 4 x 1025 2 x 1021 1T Combining the above charts with some additional calculation, we end up with our low, average, and high estimates for the size of a number (in digits) that an attacker would be able to factor at various points in time. Year Low Average High 1990 117 155 388 1995 122 163 421 2000 127 172 455 2005 132 181 490 2010 137 190 528 2015 142 199 567 2020 147 204 607 Conclusions If one wishes to devise a "standard" based on a 25-year lifetime for an average attack, then a recommendation of 200 decimal digits (665 bits) seems justified. A "super-master" key over the same lifetime might well be chosen to be three times that length (600 decimal digits, or 1994 bits). - Dr. Ron Rivest RSA FACTORING CHALLENGE UPDATE The RSA Factoring Challenge, sponsored by RSA, is essentially a list of very long numbers posted on the RSA host on the Internet (rsa.com). The Challenge serves two purposes: it provides a testing platform for new factoring algorithms, and it also provides data which RSA (and others) use to measure the advance of factoring technology. RSA then turns around and uses these data to recommend key sizes for various customer projects, based on the customer's security needs. The numbers in the factoring challenge are of two types; so-called partition numbers, which can act as a good general assessment of factoring algorithms, and RSA challenge numbers which are numbers of the type that would typically be used as RSA moduli, because they are assumed to be particularly difficult to factor. There are cash prizes for the most successful factorers, although the rules by which the money is distributed ensure that factoring a smaller partition number that has remained unfactored for a relatively long time is rewarded more than the factoring of a larger partition number. Factoring any RSA challenge number is a considerable achievement in itself, and is rewarded accordingly. Prizes vary anywhere from the tens to the thousands of dollars, and unrewarded prize money rolls over in a "kitty" from month to month, much like a State Lottery. Since its inception in March 1991, over a thousand partition numbers have been factored, providing a complex picture of the success of different algorithms for numbers of varying sizes. By contrast, only three RSA challenge numbers, of lengths 100, 110 and 120 decimal digits have been factored. "RSA-110," consisting of 110 decimal digits, required an estimated 75 mips-years of computer time, while "RSA-120," which was successfully factored only last June, consumed over 800 mips-years of computation. From these data it is clear that even a small increase in the length of typical RSA moduli requires the use of considerable additional computing effort. A typical RSA modulus (some 512 bits long, consisting of 155 decimal digits) can be expected to lie well out of reach of current techniques for the foreseeable future. Information and rules for the factoring challenge can be obtained by E-mail from challenge@rsa.com. A thorough review of the data accumulated over the past two years has recently been completed, and will soon be available as an RSA Laboratories technical report. - Dr. Matthew Robshaw RSA LABORATORIES REPORT Over recent months, RSA Laboratories has become increasingly busy. As well as the customary work of technical support and independent consulting, we continue to maintain our close awareness of recent work in the cryptographic community, particularly new results from recent IACR meetings such as Eurocrypt '93. We are releasing an increasing number of RSA Laboratories technical reports and we anticipate the imminent publication of the newly updated version of "Frequently Asked Questions". New projects have included an analysis of the vast quantity of data received as a result of the RSA Factoring Challenge. The challenge was established over two years ago with the aim of assessing the limits in factoring ability. A full analysis of this data is now being concluded and the full report will be available soon. A particularly exciting development has recently become a major research priority at the Labs. Research at RSA Laboratories has revealed a cryptographic technology that could provide a solution to some of the more pressing problems associated with the distribution of data by CD-ROM. Patent applications have been filed, and the project code-named "Arcade". Recently we were pleased to host our first annual RSA Laboratories Seminar Series. Diverse sessions provided not only a full review of many of today's issues, but also news and assessment of the very latest advances within the cryptographic community. We are pleased to report that there was considerable interest in this new venture, with scientists and developers from many of our major licensees attending. Currently, of course, we are quite busy planning technical sessions for January's upcoming 1994 RSA Data Security Conference Ð we hope to see you there! - Dr. Matthew Robshaw PUBLIC KEY CRYPTOGRAPHY STANDARDS UPDATE RSA Laboratories just sent out for comments the first set of revisions to the Public-Key Cryptography Standards. Major improvements include the following: o PKCS #7, the cryptographic message standard, now supports certificate- revocation lists (CRLs), "certificates-only" messages, and messages encrypted with only secret-key algorithms o PKCS #10, a new standard for certification requests, is added. The standard gives compact formats for requesting key certification services such as those offered by RSA Data Security and other certification authorities. Editorial improvements include updates to the references and the addition of a revision history. PKCS #1 now gives a comparison of MD2, MD4, MD5; the overview addresses compatibility between PKCS and new work, including NIST's proposed Digital Signature Standard, ISO/IEC 9796, and ANSI X9.30 and .31; and the examples reflect new naming conventions. The proposed revisions, pending approval by the PKCS participants, should be released in September. Suggestions for further improvements are welcome. Since its publication in June 1991, PKCS has become a part of several standards and products, including Privacy-Enhanced Mail, the NIST/OSI Implementors' Workshop, BLOC F3 Forms Automation, Apple's PowerTalk, Shana Informed, Fischer International's Workflow 2000, and RSA's TIPEM and BSAFE. More is just around the corner. - Dr. Burton S. Kaliski THE CLIPPER CHIP: ONE SCIENTIST'S PERSPECTIVE Dr. Martin Hellman is one of the co-inventors of Public Key technology, a Distinguished Associate of RSA Laboratories, and is currently a professor of Electrical Engineering at Stanford University. -Ed. The CLIPPER and CAPSTONE initiatives have hit the crypto community like an asteroid impacting Earth. Some dinosaurs are likely to become extinct (DES and the lack of a public key standard). But the impact is so great that cryptographic evolution itself might seem threatened: What good is cryptography if someone else can access your key without your knowledge or permission? Here I offer some thoughts on how to maximize the probability of evolution continuing, and perhaps even benefiting from this unexpected impact. (The first I heard of it was in the New York Times!) Looking back to my fight with NIST and NSA over DES in the 1975-80 time frame, I see that fighting them did not work very well. I got a lot of good press, but not one additional bit of key size (my main goal). NSA has immense power to determine what gets manufactured and what does not. As evidence that DES was not an anomaly, AT&T has already decided to shift its 3600 encrypted telephone from DES to CLIPPER. This time, I would like to get more of what I want on the technical side, even though compromise does not make as many headlines. Based on my experience with DES, the algorithm and key size are probably frozen in concrete, but the administrative procedures governing key escrow, and possibly even the secrecy of the SKIPJACK encryption algorithm used by both CLIPPER and CAPSTONE, might still be influenced. Thus, while I would like to see the key size increased from 80 bits (why limit it if keys are escrowed?), and I would prefer triply-encrypted DES to SKIPJACK, that is not where I am putting my main effort. Rather, my main hope is on the following three administrative changes. 1. More than one court order should be required for a key to be divulged. While most judges will not succumb to governmental hysteria over "communist threats" or whatever replaces them, some will think like Richard Nixon, John Mitchell, or J. Edgar Hoover. If multiple court orders would slow the process down too much, an after-the-fact GAO-type audit might suffice, with overly zealous judges removed from future decisions. 2. If even one of the judges involved in the process believes that the wiretap request is an illegal abuse of power, as in Watergate or J. Edgar Hoover' s excesses, penalties should be levied on the requesting of official. At a minimum, the intended target of the wiretap should be officially notified, and I would prefer the official be barred from making any future requests. 3. I would like government officials, from the President on down, to be subject to the same key escrow requirements as the rest of us. This would help insure the safety of the escrow system (they would have a major incentive to make sure it was working!), and would help prevent illegal activities on the part of the government- everything from Iran- Contra-type abuses through illegal wiretapping. Interested readers can obtain the full text of my comments to NIST, on which this article is based, by anonymous ftp over Internet on isl.stanford.edu in the file /pubs/hellman/nist clipper.txt. - Dr. Martin Hellman SMARTDISK - THE SMARTCARD THAT NEEDS NO READER How would you like to get your hands on a single pocket-sized device that could: identify users to the system, store their passwords and crypto-keys and protect access to PCs and data? What if that device plugged straight into the front of most computers without the need for any additional hardware connector, cables or readers? And suppose that it could also provide a trusted time source and generate random numbers Ð would you want one? Well, now you can. It is a SmartDisk; it is shaped like a regular 3.5" floppy and fits into a standard disk-drive but it contains no magnetic media. The SmartDisk is a solid state electronic device containing a microprocessor, memory, real-time clock and special magnetic interface circuitry that allows it to interface directly with floppy disk-drive heads. It has its own embedded operating system firmware Ð SDOS Ð which provides all the functions necessary to support a wide range of computer and data security applications. The SmartDisk is effectively a high performance smartcard which doesn't need a reader. However, in addition to the normal smartcard functions such as password verification and secure data storage, the SmartDisk can also provide hardware "boot protection" for PC access control applications. This is achieved by a unique function within SDOS which, on insertion of the SmartDisk into a disk drive, will output special bootstrap software for direct execution in the PC at power-up (or re-boot) before the PC disk operating system (DOS) is loaded. This special bootstrap is fully programmable by the SmartDisk systems integrator and can be used to gain complete control over the PC environment without the need to install special hardware on the PC's internal bus. The first application available for the SmartDisk is SafeBoot, a complete PC access control package which is virtually unhackable. Unlike most software- only security systems, SafeBoot stores its encryption algorithm and key on the SmartDisk rather than on the PC's hard disk, where they can be relatively easily found using low level software tools such as Norton Utilities. Various other applications are currently under construction by SmartDiskette Security Corporation (supplier of the SmartDisk) and third party vendors. A full range of "SmartDisk Application Integration Tools" is also available including a 'C' language dynamic linkable library (DLL) for Windows applications. For further information contact Gene Wagner or Jon Kaplan at Fischer International at 813/643-1500. - Paul Barrett, SmartDiskette UPCOMING RSA TRADESHOW APPEARANCES National Computer Security Expo Anaheim Hilton & Towers November 8 Ð 9, 1993 1994 RSA Data Security Conference Hotel Sofitel, Redwood Shores, CA January 12 Ð 14, 1994 Networks Expo John B. Hynes Veterans Memorial Convention Center, Boston February 15 Ð 17, 1994 Electronic Mail Association Anaheim Hilton & Towers April 18 Ð 21, 1994 Networld/Interop Spring Las Vegas Convention Center May 4 Ð 6, 1994 Networld/Interop Fall Atlanta, Georgia World Congress Center September 12 Ð 14, 1994 REGISTER NOW FOR THIRD ANNUAL RSA DATA SECURITY CONFERENCE What's happening? RSA Data Security is pleased to announce our third annual Data Security Conference, to be held at the Hotel Sofitel in Redwood Shores, California. The conference is set for Wednesday through Friday, January 12-14 1994. Who should attend? Cryptographers, software developers, product line managers, security analysts, product marketing professionals, mathematicians, secure product buyers, consultants... anyone that has an interest in cryptography and the products that use it. What will be covered? You'll see presentations and products from RSA's major licensees, including Apple, Microsoft, Novell, Lotus and many others... Panel discussions from experts from government and industry... Tutorials going all the way from the basics to the cutting edge of crypto theory and application. A detailed conference & tutorial schedule will be available November 1st. How do I register? Fill out the registration form and fax it back to RSA. Space is extremely limited: we can only admit the first 400 people that register, so sign up now! There will be no registration at the door. $245 admits you to the conference and all tutorials and includes the full hardcopy conference proceedings, a cocktail reception, and breakfast and lunch all three days. Conference Dates: January 12-14, 1994. Registration Deadline: Friday, December 17, 1993. No onsite registration. Tutorial Selection Deadline: Friday, December 17, 1993. Registration Fee: $245 per person (CA residents add applicable sales tax) Registration fee includes breakfast and lunch all three days, admission to the conference and all tutorials, a hardcopy of the full conference proceedings, cocktail reception, and conference souvenir. Tutorial selection forms will be sent to conference registrees starting November 1st. Cancellations are subject to a $50 administrative fee. Travel Information Hotel Sofitel Guaranteed rate $103 per night (415) 598-9000 The Hotel Sofitel offers a complimentary airport shuttle.