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.