A Comparison of a Public and a Secret Key Cryptosystem

Adam Donlin, SE4H. 29th February, 1995.


Introduction

Why Cryptography is necessary in a Distributed System

Supporting the facilities of a distributed system, such as resource distribution, requires the use of an underlying message passing system. Such systems are, in turn, reliant on the use of a physical transmission network, upon which the messages may physically be communicated between hosts.

Physical networks and, therefore, the basic message passing systems built over them are vulnerable to attack. For example, hosts may easily attach to the network and listen in on the messages (or 'conversations') being held. If the transmissions are in a readily understandable form, the eavesdroppers may be able to pick out units of information, in effect stealing their information content.

Aside from the theft of user data, which may be in itself of great value, there may also be system information being passed around as messages. Eavesdroppers from both inside and outside the system may attempt to steal this system information as a means of either breaching internal access constraints, or to aid in the attack of other parts of the system. Two possibly worse scenarios may exist where the attacking system may modify or insert fake transmissions on the network. Accepting faked or modified messages as valid could lead a system into chaos.

Without adequate protection techniques, Distributed Systems are extremely vulnerable to the standard types of attack outlined above. The encryption techniques discussed in the remainder of this report aim to provide the missing protection by transforming a message into a form where if it were intercepted in transit, the contents of the original message could not be explicitly discovered. Such encrypted messages, when they reach their intended recipients, however, are capable of being transformed back into the original message.

There are two main frameworks in which this goal may be achieved, they are named Secret Key Encryption Systems and Public Key Encryption Systems.

Secret Key Encryption Systems

Secret key encryption uses a single key to both encrypt and decrypt messages. As such it must be present at both the source and destination of transmission to allow the message to be transmitted securely and recovered upon receipt at the correct destination. The key must be kept secret by all parties involved in the communication. If the key fell into the hands of an attacker, they would then be able to intercept and decrypt messages, thus thwarting the attempt to attain secure communications by this method of encryption.

Secret key algorithms like DES assert that even although it is theoretically possible to derive the secret key from the encrypted message alone, the quantities of computation involved in doing so make any attempts infeasible with current computing hardware. The Kerberos architecture is a system based on the use of secret key encryption.

Public Key Encryption

Public key systems use a pair of keys, each of which can decrypt the messages encrypted by the other. Provided one of these keys is kept secret (the private key), any communication encrypted using the corresponding public key can be considered secure as the only person able to decrypt it holds the corresponding private key.

The algorithmic properties of the encryption and decryption processes make it infeasible to derive a private key from a public key, an encrypted message, or a combination of both. RSA is an example of a public key algorithm for encryption and decryption. It can be used within a protocol framework to ensure that communication is secure and authentic.

Data Privacy through Encryption

There are two aspects to determining the level of privacy that can be attained through the Kerberos and RSA systems. To begin with, there is an analysis of the security of the two systems from an algorithmic view. The questions raised at this stage aim to consider exactly how hard it is to derive a private or secret key from encrypted text or public keys.

Currently, one of the main secret key algorithms is DES, although two other more recent algorithms, RC2 and RC4 have also arisen. The size( i.e. length) of keys employed in processes is considered to be a useful metric when considering the strength of cryptology. This is because, longer key sizes generally make encrypted text more difficult to decrypt without the appropriate key.

The DES algorithm has a maximum key length of approximately 50 bits. Current consensus is that this range of key size yields keys that are strong enough to withstand attacks using current technologies. The algorithms fixed size nature may, however, constrain it in the future when hardware and theoretic advances are made. The RC2 and RC4 algorithms also have bounded maximum key sizes that limit their usefulness similarly.

A major problem associated with secret key systems, however, is their need for a secure channel within which keys can be propagated. In Kerberos, every client needs to be made aware of its secret key before it can begin communication. To do so without giving away the key to any eavesdroppers requires a secure channel. In practice, maintaining a channel that is completely secure is very difficult and often impractical.

A second aspect to privacy concerns how much inferential information can be obtained through the system. For example, how much information is it possible to deduce without explicity decrypting actual messages. One particularly disastrous situation would be if it were possible to derive the secret or private keys without mounting attacks on public keys or encrypted messages.

In Kerberos, there is a danger that the ability to watch a client progress through the authentication protocol is available. Such information may be enough to mount an attack on the client by jamming the network at strategic points in the protocol. Denial of service like this may be very serious in a time critical system.

In pure algorithmic terms, RSA is a strong. It has the ability to support much longer key lengths than DES etc. Key length is also only limited by technology, and so the algorithm can keep step with increasing technology and become stronger by being able to support longer key lengths.

Unlike secret key systems, the private keys of any public key system need never be transmitted. Provided local security is strong, the overall strength of the algorithm gains from the fact that the private key never leaves the client.

RSA is susceptible to information leakage, however, and some recent theoretic work outlined an attack plan that could infer the private key of a client based on some leaked, incidental information. Overall however, the RSA authentication protocol is not as verbose as the Kerberos equivalent. Having fewer interaction stages limits the bandwidth of any channel though which information may escape. A verbose protocol like Kerberos's simply gives an eavesdropper more opportunity to listen and possibly defines a larger and more identifiable pattern of interaction to listen for.

Server Authentication

Kerberos is a system geared primarily towards secure authentication of access requests and identity. It achieves this through a three stage protocol. As clients progress through the protocol they gain more confidence in the server's authenticity based on a protocol whereby a server is deemed trustworthy if it can return a piece of secret information known originally only to the client that is passed as a message to the server. The message is encoded prior to transmission in a key that only the proper destination server can understand.

This general algorithm is applied at first to the main repository, where Kerberos stores copies of every secret key (known as the Key Distribution Centre, or KDC), which is assumed not to have been compromised. In the event that the KDC is compromised, no communication in the system can be trusted until the repository regains integrity.

In RSA, a server is simply another process with a public/private key pair. If a server can understand a message containing some secret piece of information, known only to the originating client initially, that was sent to it in an encrypted form using its own public key, then returning the secret information to the originating client (using its public key) will gain the clients trust. The client may assume that the responding server is legitimate as only the legitimate server could decrypt the original message.

The main sticking point in this protocol is believing whether or not the initial message is being encoded using the correct public key. Often to determine the correct public key for a service (if it is not initially known) a client must ask a public key server. An attacker successfully impersonating the public key server may supply the client with a fake key, claiming that it is the correct public key for the required server when, in actuality, the impostor can decrypt the supplied key and is waiting to steal the messages.

RSA uses 'certificates' that can be attached to a reply to authenticate the public key of the sender. The certificates themselves are trusted because they are issued from a higher authority (a Certificate Authority, CA) whom, it must be assumed, has validated the contents of the certificate.

The trust of the certificate issuer in this situation is similar to the trust required of the key repository in Kerberos. If can be argued that trust can be broken between the client and certificate issuer. If a false certificate is presented to a trusting client, the client has no defences and may simply believe the false certificate.

The main difference between the two parallel situations is that, loss of trust in a CA does not breech the entire system, as a compromise of the Kerberos KDC would do. Instead, only clients fooled into accepting the fake certificates would be affected.

Data Integrity

RSA, as a public key cryptosystem, supports the notion of digitally signing a document by appending a ``digital signature'' to the main body text of the document. To prove that the signature corresponds to the message body, and hasn't been copied from another of the senders messages by an impostor, each signature is made message specific by the sender before the message is sent.

A technique called hashing is used to derive a 'unique' identifier (or "message digest") that corresponds to the message being sent. Each identifier is probabalistically unique to the point that it is unlikely that any other meaningful message may map to the same digest. Well known digest functions MD2, MD4 and MD5 are algorithmically strong in the respect that they produce digests that are probabilistically unique within an appropriately wide context.

By encrypting the digest with the private key of the sender, no other person may alter it in transit, except in the unlikely event that they have the private key of the sender. Anyone may decrypt the signature using the sender's public key. This yields the original message digest which can be compared with a hashed version of the received version. If the two digests don't match, then the message has been corrupted or vandalised.

All in all, digital signatures provide an elegant method of detecting unauthorised modifications to information in transit, or even in storage. Performing the hashing operations on top of any standard encryption may incur a cost, but the overall idea is to not have to encrypt bulky general messages in their entirety if they only need protection against modification, rather than against snooping.

The cost of encrypting an entire message would theoretically be larger than the total cost of hashing the entire message into a smaller "digest" and then encrypting that digest. This is only acceptable, however for messages that require protection against modification and not against snooping.

The main limitation of digital signatures are their dependency on an authentic public key. If the receiver is fooled into using the wrong public key then an impostor can craft his own signatures and pass false information.

Kerberos doesn't provide any explicit support for verifying that a message hasn't been tampered with. Because all messages are encrypted with the appropriate keys, the transmissions are assured to be secure within the domain of a particular KDC (provided, of course, the KDC hasn't been compromised).

To communicate outside the domain of it's local KDC, however, a client must validate itself with the remote KDC. Although communication outside the domain is possible, it creates tenuous long links which are possibly more prone to attack. Their size attracts attention and logically there are more points to attack.

To be sure of authenticity, all data transmitted in a Kerberos system needs to be encrypted by the sender using an appropriate key that was gained by communicating with the KDC.

Conclusions

Security is a broad issue and this report has only addressed a narrow area of techniques that, provided appropriate security policies are defined and adhered to, will facilitate a secure system. The need for adequate security policies, however, is an important issue and worthwhile stressing at this stage. Poor security policies will work to hamper any security mechanisms, no matter how sophisticated and complete those mechanisms appear to be.

Algorithmically, the RSA public key system appears to be much stronger and scalable than the private key alternatives of DES, RC4 and RC2. The fact that the US government has licensed the RC4 and RC2 algorithms attests to their weakness, given current US legislation and protocols regarding the export of cryptographic software and systems. There is no such thing as a free lunch, however, and for the stronger RSA security there is a processing cost that needs to be paid.

Given the possibly sensitive nature of Government data, and the probability that real time encryption/decryption will not be high priority requirements in most data processing environments, such strong algorithmic methods are justified.

Looking beyond the algorithmic level to the system architecture, even the alternative Kerberos system with an expensive secure channel still places all the systems eggs in one fragile basket, {\em i.e.} the fact that the main Kerberos server is a failure point for the whole security system makes operating such a system an unjustified risk. Even with secure channels initially, the kerberso system isn't complete in its support of the required issues (explicit data integrity support, for example).

The similar case scenario for the RSA version of a public key system revealed that the system was structured in such a way that, even if a main public key server was compromised, the in impersonator still must convince each client to accept false keys. Access in the event of failure is not a system wide default in the RSA system, as opposed to the Kerberos system.

We would therefore recommend the use of a public key based system, using a cryptographic technique like RSA as the base of the security mechanisms.

Finally, further studies into the use of hybrid systems that combine Public and Secret key architectures, may also be warranted.