Thirteen Reasons to

Say 'No' to Public Key Cryptography

Table of contents

Introduction

This document records observations on challenging aspects of a "breakthrough" technology in the field of information security, called "public key cryptography" (PKC). This document does not contain a tutorial on the relevant concepts. Furthermore, because it records observations on diversified perspectives, from digital systems architecture to regulatory issues, no single reader profile is assumed. The author personally went through the entrepreneurial process of 1) discovering and studying this breakthrough technology, 2) applying it to the development of an application, that is electronic payments by fax, for a niche market, that is, business-to-business payments in the Canada and the US, and 3) crusading in the marketplace against innovation adoption inertia. The observations recorded here were learnt mainly through this experience. At the time of writing this document, the author promotes a by-product of his previous R&D activities, a cryptographic key management procedure called SAKEM, which is indeed an alternate strategy between the classical usage of secret-key cryptography and the complete adoption of PKC.

Realistically, no conclusion is easily drawn from the assortment of observations reported here. In any given application of PKC, some observations will be more relevant than others.

The Global System View

• 1. The "Public Key Infrastructure" Requirement. The much debated public key infrastructure is a pre-requisite the full materialization of PKC benefits. It represents an industry-wide initiative, where the industry is actually the information security function across diverse industrial sectors (banking, Internet services, public sector administration, ...). The cost of this major undertaking, if it ever completes, is inevitably going to be charged to the routine use of PKC!
  
  
• 2. Liability Issues. Essentially, a Certification Authority is a witness of the "public digital signature key" of a given user (namely the user whose name appears in a security certificate). The reliability of the (electronic) evidence provided by a certification authority depends on its operational standards of integrity, and ultimately on its liability exposure. Thus, paradoxically, any well-financed entity is better out of the certification authority business. Accordingly, banks should trust only themselves as a certification authority, which defeats the economies of scale anticipated from the PKC.
  
  
• 3. Distribution of (CRL) Certificate Revocation List. A "certificate revocation list" (CRL) is a black-list of "digital signature certificates" that has been formally issued at one point but later found to be compromised or otherwise unreliable. The need for CRL distribution arises from the on-going nature of a security certificate, which is otherwise prima facie evidence. A CRL is like the fine-printed list of stolen credit card numbers that retailers used to verify, many years ago prior to the advent of on-line credit card autorization terminals. For the PKC security, CRLs nust be carefully prepared, timely distributed to all interested parites, and systematically taken into account whenever a digital signature is verified. This is a challenging data processing function, especially if a fully-meshed public key infrastructure is envisioned. The CRLs look like a nuisance or system bug that defeats the very purpose of PKC, that is the avoidance of a central authority with on-line processing capability.
  
  
• 4. The "Power of the Installed Base" Effect. It is a well known fact that coming second in a market created by technological advances is extremely challenging. The DES secret key cipher originated from IBM research activities and was first published in 1976. While DES was adopted and fielded by the banking industry in the early 1980's, the intricacies of the public key algorithms were discussed in academic circles. Nowadays, the banking industry is upgrading fielded DES equipment and software with reinforced triple-DES capability, and the public key algorithms are still mainly out of the banking industry market. If the PKC gets a second chance now, it is because the computing paradigms move from corporate-centric computing to the wilderness of the Internet frontier. The conservative-minded banking industry may still prefer traditional DES-based solutions for a number of security applications in the Internet world as well.

The Education Challenge

• 5. End-user Education. To use the PKC for a given purpose, an end-user must first obtain a "security certificate." But actually, the most sensitive piece of information is some "private digital signature key," and the security certificate usually need no special confidentiality protection. On top of that, the digital signature capability is usually protected with a user's password. And these relationships between certificates, keys, and passwords should be clear and simple for end-users!
  
  
• 6. Education Issue for IT Professionals: The market for cryptographic equipment and software is somewhere between 0.25% and 0.5% of the total market for information technology (IT). Knowing that, one shouldn't be surprised by the lack of awareness and education among IT professionals when it comes to PKC, which is still seen as a newcomer in the narrow field of information security. The cost of educating IT professionals is comparatively higher with PKC (compared with classical cryptography) because 1) the technology is more complex, 2) there are currently fewer applications to be taken as examples, and 3) the PKC seems to have more implications for computer application design (classical cryptography seems more entrenched in file systems, database management systems and communications interfaces).
  
  
• 7. Criticalness of the Education Challenge. In the process of educating end-users and IT professionals, there is an implied vulnerability to "social engineering attacks." This occurs when a trainer establishes doubtful behaviours in a group of trainees, while the trainees' confidence in the trainer advice is essential for the education to be effective. With the intricate subtleties of PKC, the trainer may even unintentionally mislead the trainee audience. An example of this is to stress the importance of protecting security certificates from misappropriation, overlooking the private signature key. Once a user community has been trained in one way, it is extremely difficult to reverse the users' understanding of the security mechanisms. In this perspective, the fact that the promoters of PKC seldom mention some of the issues raised in this document is worrysome.

Patent and "National Security" Issues

• 8. Patent Issues. Today, there are many software publishers and hardware manufacturers that are licensees of RSA Data Security Inc., the U.S. technology licensor for the foremost public key algorithm, RSA. Nonetheless, PKC patent issues are still a nuisance for many players in the IT sector. Accordingly, many vendors will wait until the demand for PKC is expressed by a significant portion of their market. If your organization needs this feature now from such a given vendor, the wait may be hurting. Paradoxically, the economic advantage granted to the RSA patent holder facilitated the dominant market position for the RSA algorithm, despite the existence of related algorithms, that is, where the "public exponent" is 2 (e.g. see ISO/IEC 9796:1991, Information Technology - Security Techniques - Digital Signature Scheme Giving Message Recovery), which appear to be outside the scope of the RSA patent.
  
  
• 9. "National Security" Issues. Vendors face yet another dilemma from the export control regulations intended to safeguard the "national security:" their product development budget for PKC can be supported by sales from limited geographical areas. Also, effective security may be at stake: when key sizes are restricted by "national security" regulations, the security impact is much more difficult to estimate in the case of PKC algorithms than for secret key ones.

Outstanding Technical Issues

• 10. Secure Storage of Secret Keys. Any cryptographic technique is based on short secrets, called cryptographic keys, that must be kept secret by their legitimate users. In most cases, including PKC, the secret keys are so long that they can't be remembered by a normal person. The association between a secret key and its legitimate user is best secured when the secret key is stored in a portable digital memory device ("security token") in the form of a plastic card, key fob, or wallet-style device. In the case of PKC, a direct connection is always required between the security token and the rest of the digital world (this is because the input and output data to a PKC operation, say a digital signature, are also very long). This latter requirement is the source of many PKC product incompatibilities.
  
  
• 11. Extremely Compute-Intensive Algorithms. By any count, the PKC operations are extremely compute-intensive. They repeatedly perform computations on very large numbers (e.g. 300 digits long). The steadily declining cost of digital integrated circuits did not solve this issue in the general case. On the low end of the computing power spectrum, the cheap microprocessor revolution is creating a myriad of new products, from the smartcard to digital cellular telephones, in which the processing power and memory size are kept to a bare minimum due to extreme cost sensitiveness. Very few of thses products have spare computing power for PKC operations. Of the more powerful computing environments, it is the personal computer that benefited most from the declining cost of digital electronics (the price per MIPS is relatively higher in the data processing centers of large organizations). So, the PKC operations are easily accomodated in the PC environment, but much less so elsewhere. Apparently, implementors of PKC sometimes take implementation shortcuts that might compromise security for faster response times, greater throughput or cost effectiveness (e.g. the "low RSA public exponent" when the implementation is vulnerable to the chosen ciphertext attack, or using password alone to protect the secrecy of one's signature private key).

Inherent Vulnerabilities of PKC Techniques

• 12. Attacks on Key Management: Cryptographic key management procedures is always an area of possible vulnerability. In the conversion from classical cryptography to PKC, new forms of attacks must be considered. As an example, a private signature key is often "locked" with a password, but the management rules for this password must be revised in the conversion to PKC. The typical user registration procedure starts with a default password, e.g. the user name, and forces a password modification on the first use of the password. This is inadequate for PKC because the private signature key is vulnerable before the first password modification (the private signature key lasts much longer than the password). More involved attacks may be mounted if a certification authority's public key is not integrity-protected. This requirement applies to any "top-level" certification authority, hence the need for integrity mechanisms over and above the digital signature verification algorithm. With the classical cryptography, the solution to the equivalent chicken-and-egg problem is the "terminal master key." The confidentiality protection provided by a terminal master key could be a used as a basis for integrity protection, but the terminal master key was suposedly removed by the PKC paradigm. More realistically, implementers of PKC would use proprietary schemes or algorithms to provide integrity protection for a few public keys for selected certification authorities. They may use proprietary schemes now, or wait until the relevant attacks are actually experienced.
  
  
• 13. Subtle Failure Scenarios In the body of academic literature about PKC, there are discussions about the "chosen ciphertext attack." Some of these references are mainly of theoretical interests, but the chosen ciphertext attack has practical implications as well. The author is not aware of any literature review from an implementation perspective, but the following observations may be made. (A) A lower public exponent implies a greater vulnerability, to the point where every cryptosystem based on public exponent 2 must explicitly counter the chosen ciphertext attack. (B) In terms of digital system architecture, it is not sufficient to "have secure processors do every computations based on private keys;" the hash function that preceedes a digital signature must be done by the same secure processor as the digital signature itself. (C) The chosen ciphertext attack is most likely to be attempted with the help of insiders, notably computer application programmers. Another type of subtle attack which has also been recognized early by academics is the man-in-the-middle attack. As its name implies, this attack is hosted in the network between unsuspecting parties in a secure exchange (e.g. in a protocol gateway). The classroom example of the man-in-the-middle attack applies to the key exchange protocol based on the Diffie-Hellman algorithm, which partly explains why the RSA algorithm is nowadays more widespread. Reviewers of public key cryptosystems should try to discover vulnerabilities created by combinations of known attack scenarios. As fielded public key cryptosystems get loaded with monetary value, powerful adversaries will do the same.
  
  
• 14. Fear of a Global System Collapse? With the current practice, the security of PKC rests on the difficulty of a few simple mathematical problems applied to very large numbers (e.g. find the prime factors 17 and 43 of 731=17×43, given only "731", when "731" is actually 300 digits long). In the very unlikey event that a major breakthrough occurs in the relevant specialized field of mathematics (that is, computational number theory), every single application of the PKC could become obsolete overnight. The candidate replacement algorithms can not be readily identified, but their properties are deemed to be radically different from anything in use today (e.g. the huge size of public keys for the McEliece algorithm based on the algebraic coding theory).

CONNOTECH Experts-conseils Inc.
9130 Place de Montgolfier
Montréal, Québec, Canada, H2M 2A1
Tél.: +1-514-385-5691 Fax: +1-514-385-5900