29 August 1998
Date: Sat, 29 Aug 1998 12:48:36 +0100 (BST) From: George Foot <georgefoot@oxted.demon.co.uk> Subject: Public Key Cryptography To: ukcrypto mailing list <ukcrypto@maillist.ox.ac.uk> I have been diffident about posting the following Article because of its length. But I have been urged by several prominent contributors to this mailing list to post the Article as it would be of interest. I am grateful for their advice and concern. The message is a plea to examine more attentively the situation of the operating company and of the operators themselves in attempting to use Public Key systems. George ----------------------------- The Privacy of Electronic Communications. A Critique of Public Key Cryptosystems. SUMMARY: A presentation of the drawbacks inherent in Public Key Cryptosystems and the difficulties and hazards which can be expected to arise in practice especially from the point of view of an operator in a commercial environment. The reader needs to be familiar with the concept of Public Key Cryptography. (1) INTRODUCTION The invention of Public Key Cryptography was a brilliant achievement. It demonstrated the possibility of employing two Keys for the encryption of messages to be transmitted electronically of which only one Key had to be kept secret. The proposal was that one of the Keys (The Public Key) should be published so that it would be available to anyone desiring to communicate securely with the owner of the corresponding Private Key. But in the outcome several problems have appeared for which no good solutions have been found. In the following discussion the emphasis is on operating difficulties and operating hazards which need more attention than they are receiving at the present time. (2) THE PRIVATE KEY: The owner is expected to keep his Private Key secret for all-time for otherwise deception is possible by anyone who becomes possessed of that Private Key: Deception includes posing as the real owner of the Private Key and also surreptitiously eavesdropping on messages intended for the real owner. Another deceptive practice is for the real owner deliberately and falsely to declare that he has lost his Private Key or that it has been stolen and in this way to evade responsibilities he has undertaken in encrypted messages which did in fact originate with him. It is very difficult to keep something secret for an extended period of time when it has to be employed every day and guarded every night -- the more so obviously when the owner of a Private Key is a company or other organization engaged in large scale business at numerous locations. In daytime the Private Key has to be employed in encrypting messages during which it is present and accessible from computers or possibly it can be extracted from connecting cables or magnetic fields. The secret is probably shared amongst employees some of whom may become disaffected with the company for which they work and maliciously reveal the Private Key to competitors and some of whom may have been planted in the company by competitors for the sole purpose of learning its secrets -- one may imagine that a lucrative blackmarket in company keys will develop. To place something in a safe at night may guard it from a casual thief but not from a person who seizes an opportunity to make a copy of the key of the safe -- in fact security becomes translated from a mathematically astronomic level to the very much lower level applying to the security of the safe key. The practice of guarding Keys with a password or phrase which has a security level greatly inferior to that of the cryptosystem which it is supposed to protect is an example of carelessness in this respect. Apart from other considerations the considerable vigilance which is necessary to operate any security system cannot be maintained at a sufficiently high level and be continued ceaselessly over long periods by human beings who are concerned with day-to-day problems relating to their duties and distracted not infrequently by various personal worries. Lapses on the part of operators are the commonest weaknesses in any security system. Moreover it is impossible to imagine that a large business will operate with a single Private Key controlling the whole of the encrypted traffic within that company and between that company and its many customers, suppliers and other contacts. A much more complex structure will emerge and many Private Keys will require to be guarded. It is the vulnerability of the Private Key which is the inherent weakness of a Public Key Cryptosystem. The loss of a Private Key for whatever reason is a disaster which, in practice, is very likely to occur and almost impossible to prevent. (3) THE PUBLIC KEY: There is as yet no experience of the use of Public Key Cryptography on a large scale and consequently the original idea lingers that Public Keys can be assumed to be accurate and authentic if certified by the signatures of people known to each other. Another idea is that Public Keys should be published in a Directory which can be consulted whenever a Public Key is required. If Public Key Cryptography were in common use worldwide, the number of Public Keys required would be very large. The impracticability of searching printed volumes for a particular Key in these circumstances is obvious -- some form of electronic search would be required: This is already necessary to obtain a telephone number or a Web URL. The issue of Privacy introduces a further problem of some complexity since the correctness and the authenticity of any Key derived from a public record of Keys cannot be assumed. It has been suggested that a Central Register should be established which would hold Public Keys and issue them on request with a certificate of authenticity. This does not solve the problem because there can be no guarantee that a Key certified in this manner is accurate. Who is responsible for losses incurred if the Key issued is not valid ? Will there be separate Registers in each country ? Will they hold Keys of nationals of other countries ? Will they charge for their services ? Will they advertise ? Will the need for commercial viability affect their integrity ? Will they maintain the accuracy of their records on a daily basis ? An hourly basis ? Continuously ? Will they be able to ensure that their staff is not infiltrated by persons who intend to issue false Keys as a part of some ingenious plan for criminal fraud? Most countries are loath to surrender any of their traditional powers to monitor covertly all electronic communications between their citizens. In large part this attitude stems from the desire of clandestine intelligence agencies within government to retain their privileges. It is proposed therefore by many governments to regulate electronic communications in such a manner that government control is maintained and to this end legislation for compulsory registration of Certification Authorities is under discussion. This would change the role of Certification Authorities very considerably bringing the prospect of government control of their activity. It is a legitimate fear that a tolerant attitude initially will be followed by legislation which progressively restricts the free use of cryptography in the civil sector. Another proposal is to create Trusted Third Parties (TTPs), the function of which at the moment is ill-defined. It is the inclusion of the word "Trust" in the title which gives rise for concern because it has no significance in that context. Trust is established progressively between two people as the outcome of transactions over a period of time which have been completed to their mutual satisfaction and after the growth of a respect for each other‘s character and reliability. We do not trust other people on first acquaintance and we are unlikely to conduct any business with them involving risk of financial loss until relationships have matured. Any plan suggesting that Trust can be established by the intervention of a Third Party should be treated with suspicion. A major weakness inherent in a Public Key Cryptosystem is the difficulty of withdrawing a Public Key which is no longer valid -- this difficulty needs emphasis because it could bring Public Keys methods into disrespect. The problem is simple to explain but an effective solution does not exist and possibly is impossible to find. A Public Key may be discarded for any of a number of reasons: The most critical is that the corresponding Private Key is known to be compromised so that further use will bring serious risks for the owner of that Private Key. Or the owner may wish to change his Private Key and hence his Public Key at intervals as a sensible precaution: Or the Public Key may have been put into circulation deliberately without knowledge of the person who is said to be the owner -- very possibly for malicious reasons or as part of a conspiracy to defraud him: Or there may simply be a mistake in the Public Key being used because of an error in transcription made by a Certification Authority: Or the nature of the business associated with the Public Key may have changed or trading may have been discontinued: Or there may be legal injunctions against the use of the Public Key because of some dispute at law: Or the level of security offered by a particular Public Key may have been found to be insufficient: Or the Public Key may have existed in the private domain and have been published by mistake: Or two companies may have acquired the same Public Key by the merging of business interests: Or the Public Key may be associated with some criminal action which it is desired to conceal. The difficulty is that a Public Key which has been in use for some time will exist in many forms: As an entry in Central Registers and Certification Authorities throughout the world: On the computers of the numerous customers of a company some of whom trade with the company regularly and some spasmodically and some no longer but who have recorded the Public Key at an earlier time: On a company‘s printed literature which is retained in the archives of a large number of other companies: On the computers of lawyers, government departments, trade associations, competitors, and endless other organisations with which the company may have had need for secure communications in the past: On newspapers, TV advertisements and other publicity material used by the company at any time: On other storage media of which there is no record. It follows that there is no way in which a Public Key can be withdrawn with assurance that it will cease to be employed. The extent to which this would bring discredit on a Public Key system has yet to be determined -- but the effect would be cumulative. It is also to be remembered that security considerations require that Keys should be changed frequently which implies that worldwide use of Public Key Cryptography would require that thousands of Keys be changed every day for one reason or another -- which in fact may be infeasible. It is significant and disconcerting that current discussion centres on establishing methods for Key Distribution without consideration of the much more intractable problem of Key Annulment. (4) ESCROW Government control becomes extended further if a government bans the use of cryptography entirely unless messages can be intercepted and decrypted surreptitiously by government agencies with ease. To ensure that this presents no problem to the government, some countries have proposals to ban cryptography unless Keys are made available to the government in advance -- either directly or by one of several escrow methods which have been devised for this purpose. Experience proves and instinctive reasoning indicates that it is imperative if secrets are to be maintained that secret information be disclosed to the fewest possible people: To suggest that secret information be made available to one or more government agencies using electronic means for its conveyance and storage within a network in which means are provided for accessing that information covertly by other agencies within a bureaucracy in which humans and human failings play an essential part and to declare that no mishandling and leakage of the information will occur is ludicrous: To believe that nobody will ever fail in his duty to safeguard it is naive: To fail to consider the possibility that somebody will infiltrate the system for personal advantage, for blackmail, for malice or for other prejudicial reasons is shortsighted. Apart from other considerations, the volume of secret material to be handled if escrow were mandatory would be impossibly large and the delays arising in consequence may be unacceptable. Although the possibility of securing international agreement to escrow and thus to universal government access to international message traffic is small -- individual countries are unlikely to sanction the custody of their national Keys by other countries -- the issue is unsettling and the lack of progress in reaching a decision is unfortunate. (5) TECHNIQUES Currently discussion of Public Key Cryptography centres on RSA and PGP. RSA is generally consider to be secure if the length of Key chosen is sufficiently long. However attempts to break RSA are intensive and success with longer Key lengths is reported frequently. The response is to increase the Key length employed for encryption but this can only be done at the expense of increasing computational load -- the battle therefore becomes a contest between larger and larger computers. It is true that computers of greater capacity are becoming available at lower cost but nevertheless it is not rewarding to squander computer power in this manner and older and slower computers are penalised. PGP is one of the hybrid systems which employs RSA for Key creation and Key exchange and then reverts to a more traditional single Key cryptosystem for message transmission because less computatonal capacity is required and quicker speeds can be achieved. Examples of these secondary cryptosystems are IDEA, DES, CAST and Blowfish. Security in these circumstances is limited to the security provided by the single key cryptosystem of which experience is limited and it may be an illusion that security is equivalent to the much better known and respected RSA system itself. Another inherent drawback of Public Key Cryptosystems is that the Public Key and the Modulus are published and therefore can be subjected to continuous cryptoanalysis without any limit of time -- thereby greatly increasing the chance that the system will be broken. In fact the published accounts of breaking Public Keys are rated for efficiency by the time necessary to break a Key of a specified length. Moreover, breaking the Key enables the cryptoanalyst surreptitiously to learn the contents of every message sent with that Key both after and before the Key was broken. (6) DIGITAL SIGNATURES Much weight has been given to the possibility of confirming the origin of an electronic transmission if double encryption is employed in a manner which utilises the Public Keys of both sender and receiver. This is technologically a brilliant concept but not a very serviceable feature. In the first place it is supposed that the evidence of origin produced in this manner will satisfy the very rigorous examination to which it will be subjected by the legal system. The debate which is being conducted at the present time shows that this is far from the case. Legal experts have expressed themselves as dissatisfied and uneasy with the arguments presented to them. It is now generally conceded that the issue of digital signatures should be separated from discussions relating to encryption. The term Digital Signature can be considerd to be unsatisfactory inasmuch as there is no significance in it being digital and also that it is clearly of a different nature from a written signature. Tortured attempts to define various types of Digital Signatures strongly suggest that a better term should be coined. (7) REALITY Why use a Public Key Cryptosystem ? There is an appeal in the idea of Public Keys which can be published by everybody and become available to everyone else but the idea is more romantic than sensible. For communication with another person or company for the first time the first exchanges are likely to be in plaintext. It will be rare that the context of the message does not provide the identity of the distant terminal -- in ordinary business usage we send for a catalogue and in further messages may probe for more detailed specifications without any misconception arising concerning the company with which we are in contact: So has business been conducted from time immemorial. There is no new element arising because we are in electronic contact until and unless we reach the stage in negotiation when privacy becomes important. Our need is for a simple method of encrypting those portions of our electronic communications which need protection from other eyes. For that purpose Public Key Cryptosystems are subject to all the drawbacks which have been described above. George Foot. -- George Foot georgefoot@oxted.demon.co.uk Web Page. http://www.oxted.demon.co.uk
[Selected responses follow:}
To: ukcrypto@maillist.ox.ac.uk Subject: Re: Public Key Cryptography Date: Sat, 29 Aug 1998 16:41:45 +0100 From: Markus Kuhn <Markus.Kuhn@cl.cam.ac.uk> Thanks for posting your paper "A Critique of Public Key Cryptosystems", which I have read with great interest, but on which I also would like to make a few critical remarks. George Foot wrote on 1998-08-29 11:48 UTC: > Moreover, breaking the Key enables the > cryptoanalyst surreptitiously to learn the contents of every > message sent with that Key both after and before the Key was > broken. This particular aspect is is only a problem of relatively early and simple implementations of public key COMSEC systems, such as PGP 2.6. Not only is the scientific literature full of practical key management protocols that provide excellent forward and backward secrecy, these mechanisms are even very widely implemented and used today. For instance, I am typing this email over an X11 connection that is secured by the Secure Shell protocol (SSH). Even if the 768-bit public server key that was transmitted at the beginning of this session were broken by an effort orders of magnitude more expensive than the Manhattan and Apollo project together, this would still allow only access to the sessions that I started within a period of one hour. The server key of SSH is regenerated every hour, and becomes meaningless for other communication after this period. Similarly, NSA's recently declassified KEA algorithm provides forward and backward confidentiality and a break of the Double-Diffie-Hellman key exchange protocol used there would only give you access to a single message, just to name a second system with similar protection. Quite similarly, many of the risks of applications of public key cryptosystems that were outlined in your paper have already been answered in the scientific literature with carefully designed protocols and application scenarios. I think the message should not be that public key applications have inherent drawbacks compared to traditional security mechanisms, but just that their correct design is an intellectually challenging task which should certainly not be left to someone who has just read an introductory textbook on the subject and understood the basic principles (as it is unfortunately the case with many of the currently fielded products). With very carefully specified and implemented applications, we can generate a business communication infrastructure that will reduce the probability of successful fraud by several orders of magnitude. It would be naive to assume that cryptography can provide 100% security and can protect against any kind of espionage and fraud. However, I am convinced that cryptography allows to set up digital contract mechanisms that are in any respect as least as secure as the extremely weak protections that we have at the moment in the form of traditional mechanisms such as handwritten signatures, tamper-evident paper documents, etc. I know of NOT A SINGLE documented case of commercial fraud that was possible because a criminal has successfully broken one of the crypto systems that have survived years of public academic scruteny. On the other hand, we are all using incredibly insecure open-password payment systems such as credit and debit cards, where between 0.5% and 1.0% of the money transferred through the system has to be used for insurance fee to cover the damage caused by every-day fraud. If well-designed cryptographic systems start to replace current low-security payment schemes such as credit cards or paper and metal cash, we can expect that fraud will be reduced significantly by several orders of magnitude. The remaining technical fraud will become the spectacular and ingenious exception instead of the common practice that it is today. All that counts in the end is the insurance fee that has to be paid for covering the financial risks involved in the usage of the system. Both the existence and the requirement of absolute security are a naive illusion. In the case of technical problems such as the updating of key-revocation lists, the system designer only has to make the usual engineering trade-off between communication cost and acceptable fraud risk. Credit card system do already today perform online checks only with certain probabilities and the probability and frequency of the checks depend of course on the amount of money that is asked to be authorized. Fraud with computer systems usually happens because of incompetence and plunder during the implementation and operation of the system and not because of successful cryptanalysis. The by far most trustworthy reviewer of security system designs and implementations is the international academic community. Therefore it is essential that cryptosystems, protocol designs, and *all* levels of the implementation are fully openly available for public scruteny over a period of at least a year before a large scale cryptographic application is allowed to enjoy a level of trust comparable to the trust we have in traditional business practice. The requirement for open implementations of security software requires *major* rethinking in the involved industry towards modern paradigms such as international standardization and open source development of both system and application software. If you do not understand why for instance only operating systems with open source code can be trusted then consider this example: Apparently there is evidence brought up in the current Caldera vs. Microsoft lawsuit that demonstrates that Microsoft operating systems contains code that specifically detects certain competitor products and modifies the behaviour of the operating system such that the competitor product has malfunctions or performs badly in the hope that the customer does not understand the fraud and will switch to a Microsoft product. Rogue software vendors are not just a theoretical risk any more today, especially not in the non-competitive system software market in which we got unfortunately over the past decade. This and its security implications for our business infrastructure should in my opinion worry us much more than the perceived problems that your Critique of Public Key Cryptosystems talked about, for many of which there are known solutions. Markus -- Markus G. Kuhn, Security Group, Computer Lab, Cambridge University, UK email: mkuhn@acm.org, home page: <http://www.cl.cam.ac.uk/~mgk25/>
Date: Sat, 29 Aug 1998 19:12:27 +0100 From: Ian Brown <I.Brown@cs.ucl.ac.uk> To: ukcrypto@maillist.ox.ac.uk Subject: Re: Public Key Cryptography George Foot wrote: > In the following discussion the emphasis > is on operating difficulties and operating hazards which need more > attention than they are receiving at the present time. You're absolutely right that operating difficulties are a big problem, but I think your strong conclusion relies on some weak propositions. Markus makes an important point: systems that use one public key to encrypt all traffic to an individual are rather badly designed. Ideally, interactive protocols (like Diffie-Hellman) should be used that use new keys for each session. In any case, key pairs used for encryption should be as short-lived as possible. Keys used for *authentication* will be longer lived (and are what will be used in public-key infrastructures) but your paper talks about encryption, not signing. The compromise of private long-lived keys does lead to all sorts of problems: hopefully smartcard-type systems where the private key is supposed never to leave the card will become far more widespread (modulo the problems with current "tamper resistant" chips that Cambridge and others have identified.) > A major weakness inherent in a Public Key Cryptosystem is the > difficulty of withdrawing a Public Key which is no longer valid > -- this difficulty needs emphasis because it could bring Public > Keys methods into disrespect. The problem is simple to explain > but an effective solution does not exist and possibly is > impossible to find. Well, try reading the SPKI documents. They get rid of the idea of certificate revocation lists and instead concentrate on positive re-authorisation. They compare this to original credit card systems, where Visa published a list of stolen cards weekly that would be rejected, to current systems where on-line positive authorisation of cards is used. > However attempts to break RSA are > intensive and success with longer Key lengths is reported frequently. Paul Leyland has answered this question here rather well before. 1024-bit or higher RSA keys are absolutely *infeasible* to break with current techniques, regardless of the computational power you throw at them. It would need new mathematical techniques that performed hugely better than those we have today; in which case, 2048, 4096 or however long keys would likely be vulnerable also. > PGP is one of the hybrid systems which employs RSA for Key creation > and Key exchange and then reverts to a more traditional single Key > cryptosystem for message transmission because less computatonal > capacity is required and quicker speeds can be achieved. Examples > of these secondary cryptosystems are IDEA, DES, CAST and Blowfish. > Security in these circumstances is limited to the security provided > by the single key cryptosystem of which experience is limited and it > may be an illusion that security is equivalent to the much better > known and respected RSA system itself. DES is rather better analysed than RSA, and is the default symmetric algorithm (in its TripleDES incarnation) for the OpenPGP standard. IDEA has also been much-analysed since its use in PGP 2.x. > Another inherent drawback of Public Key Cryptosystems is that > the Public Key and the Modulus are published In RSA, the exponent and modulus *are* the public key. > and therefore can be > subjected to continuous cryptoanalysis without any limit of time > -- thereby greatly increasing the chance that the system will be > broken. This is a fundamental part of designing a public-key cryptosystem -- those that have survived any length of time limit this chance to an incredibly, incredibly small size. > In fact the published accounts of breaking Public Keys > are rated for efficiency by the time necessary to break a Key > of a specified length. As are attempts to break symmetric keys. > Much weight has been given to the possibility of confirming the > origin of an electronic transmission if double encryption While RSA encrypts with a private key to sign data, other cryptosystems can't be said to do this -- DSA, just for one, which doesn't *have* an encryption function by design. This is a common misuse of terminology. Ian.