Public Key Cryptography
George Foot
georgefoot at oxted.demon.co.uk
Sat, 29 Aug 1998 12:48:36 +0100 (BST)
The Privacy of Electronic Communications.
A Critique of Public Key Cryptosystems.
I have been diffident about posting the following Article because=20
of its length.
But I have been urged by several prominent contributors to this=20
mailing list to post the Article as it would be of interest. =20
I am grateful for their advice and concern.
The message is a plea to examine more attentively the situation=20
of the operating company and of the operators themselves in=20
attempting to use Public Key systems.
George
-----------------------------
=20
The Privacy of Electronic Communications.
=20
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=20
practice especially from the point of view of an operator in a=20
commercial environment. =20
The reader needs to be familiar with the concept of Public Key=20
Cryptography.
(1) INTRODUCTION
The invention of Public Key Cryptography was a brilliant achievement.
=20
It demonstrated the possibility of employing two Keys for the encryption=20
of messages to be transmitted electronically of which only one Key=20
had to be kept secret.=20
The proposal was that one of the Keys (The Public Key) should be=20
published so that it would be available to anyone desiring to=20
communicate securely with the owner of the corresponding Private Key.
But in the outcome several problems have appeared for which no good=20
solutions have been found. In the following discussion the emphasis=20
is on operating difficulties and operating hazards which need more=20
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=20
otherwise deception is possible by anyone who becomes possessed of=20
that Private Key: Deception includes posing as the real owner of=20
the Private Key and also surreptitiously eavesdropping on messages=20
intended for the real owner. Another deceptive practice is for the=20
real owner deliberately and falsely to declare that he has lost his=20
Private Key or that it has been stolen and in this way to evade=20
responsibilities he has undertaken in encrypted messages which did=20
in fact originate with him.
It is very difficult to keep something secret for an extended period=20
of time when it has to be employed every day and guarded every night --=20
the more so obviously when the owner of a Private Key is a company or=20
other organization engaged in large scale business at numerous locations.
In daytime the Private Key has to be employed in encrypting messages=20
during which it is present and accessible from computers or possibly=20
it can be extracted from connecting cables or magnetic fields. The=20
secret is probably shared amongst employees some of whom may become=20
disaffected with the company for which they work and maliciously reveal=20
the Private Key to competitors and some of whom may have been planted=20
in the company by competitors for the sole purpose of learning its=20
secrets -- one may imagine that a lucrative blackmarket in company keys=20
will develop.
To place something in a safe at night may guard it from a casual=20
thief but not from a person who seizes an opportunity to make a=20
copy of the key of the safe -- in fact security becomes translated=20
from a mathematically astronomic level to the very much lower level=20
applying to the security of the safe key. The practice of guarding=20
Keys with a password or phrase which has a security level greatly=20
inferior to that of the cryptosystem which it is supposed to protect=20
is an example of carelessness in this respect.
Apart from other considerations the considerable vigilance which=20
is necessary to operate any security system cannot be maintained=20
at a sufficiently high level and be continued ceaselessly over=20
long periods by human beings who are concerned with day-to-day=20
problems relating to their duties and distracted not infrequently=20
by various personal worries. Lapses on the part of operators are=20
the commonest weaknesses in any security system.
Moreover it is impossible to imagine that a large business will=20
operate with a single Private Key controlling the whole of the=20
encrypted traffic within that company and between that company=20
and its many customers, suppliers and other contacts. A much=20
more complex structure will emerge and many Private Keys will=20
require to be guarded.
It is the vulnerability of the Private Key which is the inherent=20
weakness of a Public Key Cryptosystem. The loss of a Private=20
Key for whatever reason is a disaster which, in practice, is very=20
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=20
on a large scale and consequently the original idea lingers that =20
Public Keys can be assumed to be accurate and authentic if certified=20
by the signatures of people known to each other. Another idea is=20
that Public Keys should be published in a Directory which can be=20
consulted whenever a Public Key is required.
If Public Key Cryptography were in common use worldwide, the number=20
of Public Keys required would be very large. The impracticability=20
of searching printed volumes for a particular Key in these=20
circumstances is obvious -- some form of electronic search would be =20
required: This is already necessary to obtain a telephone number=20
or a Web URL. =20
The issue of Privacy introduces a further problem of some=20
complexity since the correctness and the authenticity of any Key=20
derived from a public record of Keys cannot be assumed. It has=20
been suggested that a Central Register should be established=20
which would hold Public Keys and issue them on request with a=20
certificate of authenticity. This does not solve the problem=20
because there can be no guarantee that a Key certified in this=20
manner is accurate. =20
Who is responsible for losses incurred if the Key issued is not=20
valid ? Will there be separate Registers in each country ? Will=20
they hold Keys of nationals of other countries ? Will they=20
charge for their services ? Will they advertise ? Will the=20
need for commercial viability affect their integrity ? Will=20
they maintain the accuracy of their records on a daily basis ?=20
An hourly basis ? Continuously ? Will they be able to ensure=20
that their staff is not infiltrated by persons who intend to=20
issue false Keys as a part of some ingenious plan for criminal=20
fraud ?=20
Most countries are loath to surrender any of their traditional =20
powers to monitor covertly all electronic communications between=20
their citizens. In large part this attitude stems from the=20
desire of clandestine intelligence agencies within government=20
to retain their privileges. It is proposed therefore by many=20
governments to regulate electronic communications in such a=20
manner that government control is maintained and to this end=20
legislation for compulsory registration of Certification=20
Authorities is under discussion. This would change the role=20
of Certification Authorities very considerably bringing the=20
prospect of government control of their activity. It is a=20
legitimate fear that a tolerant attitude initially will be=20
followed by legislation which progressively restricts the free=20
use of cryptography in the civil sector.
Another proposal is to create Trusted Third Parties (TTPs), the=20
function of which at the moment is ill-defined. It is the=20
inclusion of the word =94Trust=95 in the title which gives rise=20
for concern because it has no significance in that context. =20
Trust is established progressively between two people as the=20
outcome of transactions over a period of time which have been=20
completed to their mutual satisfaction and after the growth of=20
a respect for each other=91s character and reliability. We do=20
not trust other people on first acquaintance and we are unlikely=20
to conduct any business with them involving risk of financial=20
loss until relationships have matured. Any plan suggesting=20
that Trust can be established by the intervention of a Third=20
Party should be treated with suspicion.
A major weakness inherent in a Public Key Cryptosystem is the=20
difficulty of withdrawing a Public Key which is no longer valid=20
-- this difficulty needs emphasis because it could bring Public=20
Keys methods into disrespect. The problem is simple to explain=20
but an effective solution does not exist and possibly is=20
impossible to find.
A Public Key may be discarded for any of a number of reasons: =20
The most critical is that the corresponding Private Key is=20
known to be compromised so that further use will bring serious=20
risks for the owner of that Private Key. Or the owner=20
may wish to change his Private Key and hence his Public Key at=20
intervals as a sensible precaution: Or the Public Key may have=20
been put into circulation deliberately without knowledge of the=20
person who is said to be the owner -- very possibly for malicious=20
reasons or as part of a conspiracy to defraud him: Or there=20
may simply be a mistake in the Public Key being used because=20
of an error in transcription made by a Certification Authority: =20
Or the nature of the business associated with the Public Key may=20
have changed or trading may have been discontinued: Or there may=20
be legal injunctions against the use of the Public Key because of=20
some dispute at law: Or the level of security offered by a particular=20
Public Key may have been found to be insufficient: Or the Public Key=20
may have existed in the private domain and have been published by=20
mistake: Or two companies may have acquired the same Public Key by=20
the merging of business interests: Or the Public Key may be=20
associated with some criminal action which it is desired to conceal.
The difficulty is that a Public Key which has been in use for=20
some time will exist in many forms: As an entry in Central Registers=20
and Certification Authorities throughout the world: On the computers=20
of the numerous customers of a company some of whom trade with the=20
company regularly and some spasmodically and some no longer but who=20
have recorded the Public Key at an earlier time: On a company=91s=20
printed literature which is retained in the archives of a large=20
number of other companies: On the computers of lawyers, government=20
departments, trade associations, competitors, and endless other=20
organisations with which the company may have had need for secure=20
communications in the past: On newspapers, TV advertisements and=20
other publicity material used by the company at any time: =20
On other storage media of which there is no record.
It follows that there is no way in which a Public Key can be=20
withdrawn with assurance that it will cease to be employed. =20
The extent to which this would bring discredit on a Public=20
Key system has yet to be determined -- but the effect would be=20
cumulative. It is also to be remembered that security considerations=20
require that Keys should be changed frequently which implies that=20
worldwide use of Public Key Cryptography would require that thousands=20
of Keys be changed every day for one reason or another -- which in=20
fact may be infeasible. =20
It is significant and disconcerting that current discussion centres=20
on establishing methods for Key Distribution without consideration=20
of the much more intractable problem of Key Annulment.
(4) ESCROW
Government control becomes extended further if a government bans=20
the use of cryptography entirely unless messages can be intercepted=20
and decrypted surreptitiously by government agencies with ease. =20
To ensure that this presents no problem to the government, some=20
countries have proposals to ban cryptography unless Keys are made=20
available to the government in advance -- either directly or by one=20
of several escrow methods which have been devised for this purpose.=20
Experience proves and instinctive reasoning indicates that it is=20
imperative if secrets are to be maintained that secret=20
information be disclosed to the fewest possible people: To=20
suggest that secret information be made available to one or more=20
government agencies using electronic means for its conveyance and=20
storage within a network in which means are provided for accessing=20
that information covertly by other agencies within a bureaucracy=20
in which humans and human failings play an essential part and to=20
declare that no mishandling and leakage of the information will=20
occur is ludicrous: To believe that nobody will ever fail in his=20
duty to safeguard it is naive: To fail to consider the possibility=20
that somebody will infiltrate the system for personal advantage,=20
for blackmail, for malice or for other prejudicial reasons is=20
shortsighted.
Apart from other considerations, the volume of secret material=20
to be handled if escrow were mandatory would be impossibly large=20
and the delays arising in consequence may be unacceptable.
Although the possibility of securing international agreement to=20
escrow and thus to universal government access to international=20
message traffic is small -- individual countries are unlikely to=20
sanction the custody of their national Keys by other countries=20
-- the issue is unsettling and the lack of progress in reaching=20
a decision is unfortunate.
(5) TECHNIQUES
Currently discussion of Public Key Cryptography centres on RSA and=20
PGP. RSA is generally consider to be secure if the length of Key=20
chosen is sufficiently long. However attempts to break RSA are=20
intensive and success with longer Key lengths is reported frequently.
The response is to increase the Key length employed for encryption but=20
this can only be done at the expense of increasing computational=20
load -- the battle therefore becomes a contest between larger and=20
larger computers. It is true that computers of greater capacity are=20
becoming available at lower cost but nevertheless it is not rewarding=20
to squander computer power in this manner and older and slower computers=20
are penalised. =20
PGP is one of the hybrid systems which employs RSA for Key creation=20
and Key exchange and then reverts to a more traditional single Key=20
cryptosystem for message transmission because less computatonal=20
capacity is required and quicker speeds can be achieved. Examples=20
of these secondary cryptosystems are IDEA, DES, CAST and Blowfish.
Security in these circumstances is limited to the security provided=20
by the single key cryptosystem of which experience is limited and it=20
may be an illusion that security is equivalent to the much better=20
known and respected RSA system itself.
Another inherent drawback of Public Key Cryptosystems is that=20
the Public Key and the Modulus are published and therefore can be=20
subjected to continuous cryptoanalysis without any limit of time=20
-- thereby greatly increasing the chance that the system will be=20
broken. In fact the published accounts of breaking Public Keys=20
are rated for efficiency by the time necessary to break a Key=20
of a specified length. Moreover, breaking the Key enables the=20
cryptoanalyst surreptitiously to learn the contents of every=20
message sent with that Key both after and before the Key was=20
broken. =20
=20
(6) DIGITAL SIGNATURES
Much weight has been given to the possibility of confirming the=20
origin of an electronic transmission if double encryption is=20
employed in a manner which utilises the Public Keys of both sender=20
and receiver.
This is technologically a brilliant concept but not a very=20
serviceable feature. In the first place it is supposed that the=20
evidence of origin produced in this manner will satisfy the very=20
rigorous examination to which it will be subjected by the legal=20
system. The debate which is being conducted at the present time=20
shows that this is far from the case. Legal experts have expressed=20
themselves as dissatisfied and uneasy with the arguments presented=20
to them. =20
It is now generally conceded that the issue of digital signatures=20
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=20
that it is clearly of a different nature from a written signature.=20
Tortured attempts to define various types of Digital Signatures=20
strongly suggest that a better term should be coined.=20
=20
(7) REALITY
Why use a Public Key Cryptosystem ? =20
There is an appeal in the idea of Public Keys which can be=20
published by everybody and become available to everyone else=20
but the idea is more romantic than sensible. =20
For communication with another person or company for the first=20
time the first exchanges are likely to be in plaintext. It will=20
be rare that the context of the message does not provide the=20
identity of the distant terminal -- in ordinary business usage=20
we send for a catalogue and in further messages may probe for=20
more detailed specifications without any misconception arising=20
concerning the company with which we are in contact: So has business=20
been conducted from time immemorial. There is no new element=20
arising because we are in electronic contact until and unless we=20
reach the stage in negotiation when privacy becomes important.
Our need is for a simple method of encrypting those portions of=20
our electronic communications which need protection from other=20
eyes. For that purpose Public Key Cryptosystems are subject=20
to all the drawbacks which have been described above.
=20
George Foot.
--=20
George Foot
georgefoot@oxted.demon.co.uk
Web Page. http://www.oxted.demon.co.uk