At the request of the Business Software Alliance (BSA), an ad hoc panel of seven cryptologists and computer scientists met last November to address the question of the minimum key length required to provide adequate security against exhaustive search in commercial applications of symmetric cryptosystems. We have just completed our report.
We adopted a simple, and somewhat conservative, methodology in an effort to gain a realistic understanding of what size keys might actually be vulnerable in practice. It is common in analysis of key length to give all benefit of the doubt to the capabilities of the potential attacker and to make very generous assumptions about the technology and resources that might be available to mount an attack. In our analysis, however, we assumed that the attacker would employ only conventional, commercially-mature technologies and would be limited by budget and time constraints. We used several different technologies to design attack strategies that accommodate the budgets of various hypothetical attackers, from individual ``hackers'' to well-funded enterprises. Our conclusions, therefore, represent an approximation of an ``upper bound'' on the strength of various size keys; I believe more efficient attacks than those we considered might also be possible and should be taken into account by the prudent cryptosystem designer.
The abstract of the report follows below.
A PostScript copy of the full text of the report is available in ftp://ftp.research.att.com/dist/mab/keylength.ps An ASCII version is available in ftp://ftp.research.att.com/dist/mab/keylength.txt
(The report will also likely appear on the BSA's web site shortly).-matt (speaking only for himself) =======================================================================
A Report by an Ad Hoc Group of Cryptographers and Computer Scientists
Matt Blaze (1)
Whitfield Diffie (2)
Ronald L. Rivest (3)
Bruce Schneier (4)
Tsutomu Shimomura (5)
Eric Thompson (6)
Michael Wiener (7)
Encryption plays an essential role in protecting the privacy of electronic information against threats from a variety of potential attackers. In so doing, modern cryptography employs a combination of _conventional_ or _symmetric_ cryptographic systems
encrypting data and _public key_ or _asymmetric_ systems for managing the _keys_ used by the symmetric systems. Assessing the strength required of the symmetric cryptographic systems is therefore an essential step in employing cryptography for computer and communication security.
Technology readily available today (late 1995) makes _brute-force_ attacks against cryptographic systems considered adequate
for the past several years both fast and cheap. General purpose computers can be used, but a much more efficient approach is to employ commercially available _Field Programmable Gate Array (FPGA)_ technology. For attackers prepared to make a higher initial investment, custom-made, special-purpose chips make such calculations much faster and significantly lower the amortized cost per solution.
As a result, cryptosystems with 40-bit keys offer virtually no protection at this point against brute-force attacks. Even the U.S. Data Encryption Standard with 56-bit keys is increasingly inadequate. As cryptosystems often succumb to `smarter' attacks than brute-force key search, it is also important to remember that the keylengths discussed here are the minimum needed for security against the computational threats considered.
Fortunately, the cost of very strong encryption is not significantly greater than that of weak encryption. Therefore, to provide adequate protection against the most serious threats --- well-funded commercial enterprises or government intelligence
agencies --- keys used to protect data today should be at least 75 bits long.
To protect information adequately for the next 20 years in the face of expected advances in computing power, keys in newly-deployed systems should be at least 90 bits long.
Recently, there has been much publicity about a problem inherent in today's personal computers: software on a PC can recognize credit-card numbers as they are typed on the keyboard, with no knowledge of why the number is being typed, what application is running, etc. The RISK here is that such software could be malicious--for example, it could run invisibly in the background and send credit-card numbers it discovers to its creator--anonymously and untraceably. The publicity came in press interviews (San Jose Mercury News, 29 January 1996) and in subsequently distributed material from First Virtual Holdings (FV). The problem is characterized by FV as "fatal", as a "discovery", as "undermining every known credit-card encryption mechanism for Internet commerce", and as having no possible technical defenses or counter-measures.
Is this a RISK? If so, how to characterize it?
The discussion has revolved around four basic claims:
In technical terms, there is certainly a RISK. The scenario described in the newspaper article, and elaborated on by Nat Borenstein (FV's Chief Scientist) is technically accurate: malicious programs can transmit information to parties who oughtn't have it.
This is not news. It has been well understood in the computer security field for, well, about three decades. It is the fundamental threat underlying the security mechanism called Mandatory Access Control. And, I imagine, it's something that makes computer security and virus researchers lose sleep some nights. Indeed, because of this threat, there are those who say they never run any software they haven't personally studied and compiled themselves (though I've often wondered what they do about compilers... and microcode).
The language used to describe the threat ("the flaw ... is fatal"), however, is a bit on the hyperbolic side. First of all, the threat is not unique to Internet commerce: it applies to information processing in general. The threat is equally applicable against numbers that one might enter as account identifiers in a personal finance program, or even against credit-card numbers in a letter written with a word processor (perhaps to inquire about incorrect charges). Such uses are just as vulnerable--one need never even attempt an electronic purchase to "lose" a credit-card number this way. The advice from FV does state "never type your credit-card number into a computer", but it focuses solely on commerce mechanisms, which is a bit misleading.
Secondly, there ARE effective counter-measures, of both a defensive and an offensive nature, other than giving up on credit-card numbers for electronic commerce. FV characterizes the only two possible solutions as "secure hardware add-ons and the First Virtual approach", because in the latter, a user is not required to type credit-card number into a PC. These approaches impose certain costs, risks, and benefits that must be weighed sensibly against corresponding attributes of other approaches. Even if they were the only possible "solutions", they might not be sufficiently cost-effective to be worth using.
Finally, it's important to identify the stakeholders clearly and not to overstate the RISK. Just as one runs certain risks in handing a credit card to a minimum-wage employee, personal computers pose some risks--but who benefits and who bears the costs are critical to a system analysis.
The first claim (ease of keyboard sniffing) is certainly true; the demonstration program shows that nicely.
The second claim (ease of recognition) is more dubious. Certainly, credit-card numbers typed in directly from a keyboard are recognizable, but is that the only practical way to enter them? Of course not. There are several obvious technical counter-measures for this aspect of the threat. For example, one could enter part of the number, back up with cursor keys, and enter the rest of the number. Software could request the number following a simple code (e.g., 0=W, 1=S, 2=Z, generated randomly for each request; a similar approach is used for verifying licensees of much PC game software). Software could display a calculator key-pad for entering the number with mouse clicks. And so on--a little ingenuity goes a long way.
Although these methods may seem a bit clumsy, they need only be used once per credit-card number. That one-time inconvenience would not be an unreasonable burden for users--and data entry errors (which clearly are a risk of such special-purpose interfaces) would be minimal due to precisely the same properties that make credit-card numbers easily recognizable in the first place. Such counter-measures undermine the "fatal flaw" claim, for none of them require an account-based system like FV's; neither do they involve secure hardware.
Of course, malicious software could also be created to defeat any of these approaches, just as it could be created to perform the "extremely difficult" task of defrauding FV's multi-step transaction approach. However, any of these counter-measures removes the most important property of the attack: the ability to recognize credit-card numbers without context. Instead, a significantly more complex directed attack--or, rather, one for each possible application program--is needed to extract the numbers from a deliberately safeguarded user interface.
There is a related threat that relies on the recognizability attribute: finding credit-card numbers stored, say, as ASCII text in memory, on disk, or in network traffic is no more conceptually difficult than recognizing keystrokes. The same sort of context-free recognition is straightforward. However, even a light encryption of such data (e.g., XOR) will foil the simple context-free attack, and require that a recognition program understand the semantics of the data it's looking for. The analysis here applies to such scenarios as well.
The third claim (easy and traceless infiltration) is dubious as well. Truly effective malicious software is DIFFICULT: witness the extremely primitive payloads of most extant PC viruses. Although recognizing the keystrokes may be easy and reliable, neither the process of installation into arbitrary consumer PCs nor the mechanism for returning the information is likely to be. Most people who have ever installed software on a PC, or who have ever used a PC-based communication mechanism, will recognize that these activities have considerable potential to generate errors and anomalous events. Traceless infiltration, however, requires that no such events occur.
Although the great thing about malicious software (from the bad guy's point of view) is that it only needs to be written once and after that, any fool can run it, it still has to be written and to work properly. Capturing credit-card numbers when they are typed as consecutive digits presents an especially easily recognized pattern, so that part of the program's job is simple, but that doesn't affect the compatibility and reliability aspects. Widespread distribution of a credit-card capture program would likely result in compatibility problems throughout its user community--nothing serious, but quite possibly enough to to discover it in the same manner that other viruses are discovered. It's not at all clear that such a program could become widespread without being quickly discovered--which argues against "tracelessly".
This hypothetical (as opposed to FV's laboratory demonstration of partial version of such a program) invisible credit-card capture and delivery program is very similar to a traditional virus payload, except that it need not be self-propagating and its function is more complex (thus, more likely to be detected). It's probably distributed on-line for maximum efficiency, but that could be done with ordinary viruses also. Viruses are bad, and one could even claim that their existence is a "fatal flaw" in personal computers... but we go on computing anyway.
The fourth claim (easy and traceless reporting) also is dubious, for similar reasons. Although there are many potential schemes for sending information back to the perpetrator, these back-channels are likely to be noticeable, due perhaps to volume, perhaps to the appearance of unexpected traffic, or perhaps to errors that occur when a particular back-channel is attempted that doesn't work as expected in some user environment. For example, one proposed scheme involves making postings to "test" newsgroups and encrypting the information in the article's message ID. Technically feasible, yes, but what happens when a user gets an error message about how the PC "Error 07C: Cannot post to misc.test"? If this starts happening on a wide scale, the malicious software (though probably not its author) will soon be discovered.
Finally, it's important to recognize what it might mean for a counter-measure to be called successful. If "successful" means apprehending the criminal perpetrator who created the malicious software, well, that's certainly hard. However, if "successful" means protecting individual consumer credit-card accounts and minimizing the cost to the global financial system, that's much easier. An attack might be detected by noticing anomalies; prevented (offensively) through something like virus-removal technology; or prevented (defensively) through guarded data entry schemes. Although none of these mean that the perpetrator can be found, they do mean that the attack is foiled--and that financial loss is minimized.
These attacks are certainly technically possible, and worth taking some general counter-measures against. It seems unlikely, however, that they would bankrupt either consumers or financial institutions, or that they would become widespread before specific counter-measures (along the lines of anti-virus scanners) were available.
One general problem is worth noting: if such an attack IS perpetrated, tracing perpetrators is damned difficult. However, the propensity of criminals to talk about their activities, to keep diaries, and to get caught doing other criminal (and often stupid) things at least offers some possibilities. I'm actually more worried about lone attackers than about a large-scale organized assault by criminal organizations. Hostile intelligence services (or militaries) are also, to my mind, a bigger threat. For individuals, the economic incentive for credit-card number theft is, to be sure, greater than for simple virus distribution, but profiting from stolen card numbers is fairly risky and difficult on a large scale--one really needs a retail outlet for the information.
Knowing all this, it would clearly be prudent (A) to design and use safeguarded user interfaces and (B) to bring this threat into the scope of things that concern developers of virus counter-measures. But abandon encrypted credit-card numbers as any part of an Internet commerce scheme? That seems like an over-reaction.
The RISK here is one of assuming that a specific technical vulnerability translates directly into a system-wide problem of equal severity, and recourse is inherently impossible. Over-stating the threat can be just as dangerous as ignoring it.Olin Sibert Oxford Systems, Inc.
I was checking my cellular phone account balance using a cellular phone. They offered a payment option which I took. Luckily I miskeyed it because as I sent it I realized that not only had my tones gone out in the clear but they also read it back in case the eavesdroppers weren't sophisticated enough to decode the tones.
This appeared in the latest Educom...
"EVERYONE REMAIN CALM"
The Denver-Rocky Mountain News reports that management at the new $5-billion Denver airport forgot to install an intercom system for the subways that trundle passengers from concourse to concourse, so when the computer controlling the subways broke down, there was no way to communicate with the trapped passengers. The city has now rectified the situation by purchasing six electronic bullhorns. (Telecommunications Policy Report 28 Jan 96 p10)
[Also noted by WYNN@AppleLink.Apple.COM (Wynn, Eleanor,VCA). Now we need to populate the subways with electronic bulls. PGN]
The Forrestal missile launching was an unintended launch, but IMHO, it was more of a training error than a hardware failure.
At the time of the incident, I was the aircraft maintenance officer on the USS INDEPENDENCE (CVA-62), the sister ship of the FORRESTAL. The FORRESTAL had just arrived in the waters off Viet Nam when the "incident" (which killed in excess of 100 men--I don't remember exactly how many) occurred. The FORRESTAL had just come from an eight-month overhaul period, and her crew was inexperienced. Navy ships are required to undergo proficiency inspections, called INSERVs, after long periods of inactivity. The INDEPENDENCE had given FORRESTAL her INSERV, and she had flunked. This was NOT a reflection on the crew, but rather on the fact that they needed more training. The admiral in charge of the INSERV inspection, however, overrode the recommendation of his staff and certified the FORRESTAL as ready for action. The reason given was that the Navy desperately needed the FORRESTAL on station in the Gulf.
A flight deck during flight ops is one of the most hazardous places imaginable. Besides planes taking off or landing, planes and ammunition are being moved around, refueling and defueling is occurring, maintenance vehicles and equipment ("yellow gear") is moving, testing, and/or starting aircraft, and other operations are going on. This is all in a space only one-tenth the size of a land-based airfield. Flight deck personnel need eyes in the back of their head and a sixth sense of where everything is, and must know their jobs instinctively. The FORRESTAL crew was so green that during the inspection, the INDEPENDENCE's flight deck officer left the flight deck and refused to return, considering it too dangerous.
I don't recall the details of the actual incident, save that it involved a plane that had been improperly loaded and armed released a missile at an F-4 that was ready for takeoff on catapult #1 (on the port side forward). Since fuel and ammunition had been improperly placed on the deck, this quickly touched off explosions and fires that ran the length of the deck. I do clearly recall that the reason for the accidental launch was not due to equipment failure: it was caused by aircrew error in both attaching and arming the missiles. (Consider the problem of designing a system that must NOT work until it's ready, and then must not FAIL to work.)
The risk, in other words, was improper training in a complex and hazardous environment. I would hope that the Navy (and other organizations) would take a lesson from this.Pete McVay, firstname.lastname@example.org
1996 IEEE SYMPOSIUM ON SECURITY AND PRIVACY _/_/ May 6-8, 1996 _/_/ _/_/_/ The Claremont Resort, _/ _/ Oakland, California _/ _/ _/_/ Sponsored by the _/_/_/ IEEE Technical Committee on Security and Privacy _/ _/ In cooperation with the _/ _/ International Association of Cryptologic Research _/_/_/ _/ Symposium Committee _/ Dale M. Johnson, General Chair _/_/_/ _/_/ Stephen Kent, Vice Chair _/ _/ _/ John McHugh, Program Co-Chair _/ _/ _/ George W. Dinolt, Program Co-Chair _/_/_/ _/_/_/ _/ _/ _/ PRELIMINARY PROGRAM _/ _/ _/ Subject to Change _/ _/_/
MONDAY, MAY 6
08:30-09:00 WELCOMING REMARKS: Dale Johnson and John McHugh
09:00-10:30 PANEL: Object Management Group CORBA Security Standard
Moderator: Terry Benzel Participants: TBA
11:00-12:00 COVERT CHANNELS
An Analysis of the Timed Z-Channel Ira S. Moskowitz, Steven J. Greenwald, Myong H. Kang
Defining Noninterference in the Temporal Logic of Actions Todd Fine
13:30-15:00 PANEL: Goals for Computer Security Education
Cynthia Irvine, Chair Leslie Chalmers Karl Levitt Steven F. Barnett Jim Schindler Roger R. Schell
15:30-17:00 FIVE-MINUTE RESEARCH TALKS SESSION
Submissions in the form of one-page ASCII abstracts due by e-mail to email@example.com no later than 2 April 1996. See http://www.cs.pdx.edu/SP96/ for more information. Abstracts to be distributed at the conference.
TUESDAY, MAY 7
09:00-10:30 DOMAIN SPECIFIC SECURITY
Security for Medical Information Systems Ross Anderson
Discussion Discussants TBA
Entity Authentication Dieter Gollmann
A Fair Non-repudiation Protocol Jianying Zhou, Dieter Gollmann
Limitations on Design Principles for Public Key Protocols Paul Syverson
Ensuring Atomicity of Multilevel Transactions Paul Ammann, Sushil Jajodia, Indrakshi Ray
View-Based Access Control with High Assurance Xiaolei Qian
Supporting Multiple Access Control Policies in Database Systems Elisa Bertino, Sushil Jajodia, Pierangela Samarati
15:30-17:00 BIOLOGICALLY INSPIRED TOPICS IN COMPUTER SECURITY
An Immunological Approach to Change Detection: Algorithms, Analysis, and Implications Patrik D'Haeseleer, Stephanie Forrest, Paul Helman
A Sense of Self for UNIX Processes Stephanie Forrest, Steven A. Hofmeyr, Anil Somayaji, Thomas A. Longstaff
Cryptovirology: Extortion Based Security Threats and Countermeasures Adam Young, Moti Yung
17:30-19:30 TECHNICAL COMMITTEE MEETING
WEDNESDAY, MAY 8
A Security Model of Dynamic Labeling Providing a Tiered Approach to Verification Simon Foley, Li Gong, Xiaolei Qian
A Communication Agreement Framework of Access Control Martin Roscheisen, Terry Winograd
Decentralized Trust Management Matt Blaze, Joan Feigenbaum, Jack Lacy
Security Properties and CSP Steve Schneider
10:30 11:00 BREAK
11:00 12:30 NETWORKS
Security Flaws in the HotJava Web Browser Drew Dean, Dan S. Wallach
On Two Proposals for On-line Credit-card Payments using Open Networks: Problems and Solutions Wenbo Man
Secure Network Objects Leendert van Doorn, Martin Abadi, Mike Burrows, Edward Wobber
Run-Time Security Evaluation (RTSE) for Distributed Applications Cristina Serban, B. McMillin
12:30 12:45 CONCLUDING REMARKS
12:45 SYMPOSIUM ADJOURNS
>>>>SORRY, NO REGISTRATIONS BY E-MAIL. NO REFUNDS.<<<<
[But PLEASE send Dale an E-mail message requesting the full registration packet, which can be e-mailed to you. PGN]
Please report problems with the web pages to the maintainer