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.