The strategy for trust in an 'e' world - cryptography and PKI

Trust is always an issue in business - people need to know who they are dealing with, and if they can rely upon information they are purportedly receiving from their business partners. In the real world, you 'know' people, or know their signature. But with modern networks rendering geography obsolete, and newer business models forcing corporates to do business with people they do not know, a rather old technique is coming to the rescue - cryptography. Used largely by governments and military in the past to keep secret messages from falling into the wrong hands, cryptography has today entered the mainstream with ordinary citizens often needing to use cryptography for their day to day needs. This article explains basic concepts behind digital signatures and certificates, and how they work.
Cryptography - a primer

By Mukul Pareek

The need to maintain secrecy of communications has been a need as old as language itself. Used largely by governments and military in the past to keep secret messages from falling into the wrong hands, cryptography has today entered the mainstream with ordinary citizens often needing to use cryptography for their day to day needs, which may range from the need to keep credit card numbers secret to organising Falun Gong demonstrations in Tiannamen square.

If you surf the net, you have probably used cryptography sometimes even without knowing it, in fact each time you shop on the net or provide any personal information, there is a good chance that your browser is communicating securely with the other server using Secure Sockets Layer (SSL) which is based upon the RSA public key cryptography.

This article attempts to present in a nutshell the basic concepts that relate to cryptography as it would work in a commercial environment. It sets the scene for a discussion of digital signatures, digital certificates and public key infrastructure issues.

Cryptography: basic concepts

Data that is capable of being read without any special measures is called cleartext or plaintext. This web page is an example of plaintext which anyone can read. Converting plaintext so that it is readable only by persons aware of the means to convert it to its plainly readable form is called encryption. The converted text is called encrypted text. “FinanceOutlook” is plaintext, while “GjobodfPvumppl” is encrypted text obtained by substituting each letter with the next in the alphabetical series.

Cryptography is the science of using mathematics to encrypt and decrypt data. The substitution algorithm cited earlier which uses shifting characters by one is a very simple example of encryption. Modern cryptography relies upon rather complex mathematical models to build the algorithm that converts plaintext to encrypted text.

The process of converting to encrypted text is called encryption, and the process of converting encrypted text to plaintext is called decryption. The mathematical function that encrypts or decrypts is called the cryptographic algorithm. A ‘key’, which is a user selected password, number or ‘passphrase’, is used as a parameter in the encryption algorithm to convert the plaintext to encrypted text.

The algorithm, the keys, the software and any protocols to make all of these hang together is called a cryptosystem.


Conventional, or secret-key cryptography

Also called symmetric-key encryption, conventional cryptography uses one key for both encryption and decryption. Data Encryption Standard (DES), widely used by the US government, is an example of symmetric encryption.

Conventional cryptography is straightforward and goes with a commonsense understanding of cryptosystems – you use a key to encrypt data, and then use the same key to convert encrypted data to plaintext. Secret-key cryptography has been in use since World War I. The security of the encrypted data depends upon the strength of both the key and the encryption algorithm.


The problem of key distribution

Conventional cryptography is simple, extremely fast and secure provided the key can be kept safe. The true difficulty with conventional cryptography arises with key distribution, ie how do you keep the key safe with the sender and transmit it securely to the intended receiver. In fact, the difficulty of key distribution is the key reason that led to the development of public key cryptography. If you have a means of securely transmitting the key to the receiver, you might as well use the same means to transmit the message itself.

There are other associated problems too. If the secret key is shared between more than one person, there is no way to establish the authenticity of the originator as any person knowing the secret key could have generated a message using that key.

Enter public key cryptography

Public key cryptography has been available since the late 70's, and relies upon a pair of keys, one public and the other private, to encrypt and decrypt messages. Each pair of keys consists of a public key and a private key. The public key is made public by distributing it widely. The private key is never distributed, it is always kept secret. What is different with public key cryptography is that rather than using the same key to encrypt and decrypt data, public key cryptosystems use a matched pair of keys that uniquely complement each other.

The underlying mechanism that makes public key cryptography so useful is that data that has been encrypted with a private key can only be decrypted with the corresponding public key. Similarly, a message that has been encrypted with a widely known public key can only be decrypted by whoever has the private key and no one else. This may sound strange to the lay mind, but believe me, it works. So while it is easy to run the algorithm that converts the plaintext to encrypted text, or cipher-text, it is not possible to run the algorithm in reverse, ie to derive the original message that has been encrypted using the public key again on the cipher-text, or to derive the private key if the plaintext, ciphertext and public key are known.

Another key feature of public key cryptography is that all communications involve only public keys and no private keys are ever shared Key strength is measured in terms of its size, and as a general rule, the larger the key, the more secure it is. Key sizes are expressed in bits, so you can have 40-bit keys, 128-bit keys and so on.

Relationship between private and public keys

Public and private keys come in pairs, there is one public key for a private key and vice-versa. In fact, the public key is derived mathematically once the private key has been chosen by a user. They are mathematically related to each other using complex ‘one-way’ problems. RSA, one of the most widely used encryption methods, relies upon concepts of prime numbers and factorisation to achieve this result. The private key cannot be derived from the public key without excessive effort – excessive in this case meaning something more than all the computational power available in the universe (of course, excluding the possibility of extra terrestrial intelligence with super smart computers!). This excessive effort is also referred to as the ‘computational infeasibility’. Computational infeasibility is always related to the present time, in fact no one can predict how cheap and easily accessible computing power will become. So what is infeasible today may be feasible tomorrow and this is a limitation to which all mathematical cryptography is subject.

128-bit encryption has never been broken. According to RSA Labs, it would take a trillion-trillion years to crack 128-bit encryption using today’s technology.

Till recently the export outside the US of software allowing cryptography stronger than 40-bits was not permitted. Both Microsoft and Netscape had a 40-bit version for non-US customers and 128-bit version for domestic customers. Needless to say, this proved to be a very feeble attempt by the US government to ensure that it retained the ability to crack secret communications occuring outside the US borders. Having no monopoly on intellect however, it was unable to stop the development outside the United States of third party add-ins to browsers that allowed them to exchange messages encrypted with 128-bit keys. This restriction has now been withdrawn.

Conventional and public key cryptosystems compared

While public key cryptosystems overcome a key limitation of conventional cryptosystem, this comes at a price. You need more processing power to encrypt and decrypt messages under a public key cryptosystem, in fact conventional encryption is reckoned to be 1000 times faster than public key encryption. Public keys need to be much larger to ensure the same level of security that is possible with a much smaller conventional key. A conventional 80-bit key has the same strength as 1024-bit public key.

Often, cryptosystems use a combination of both conventional and public key cryptography. PGP for example, uses conventional cryptography to obtain the high security it provides with a smaller key size, and then use public key cryptography to encrypt just the conventional key that was used to encrypt the message.


Commercial significance of cryptography

Cryptography is the underlying technology for digital signatures, digital certificates, and SSL that permits secure communications over the web. These are discussed next.



Digital signatures, digital certificate and PKI


Business, ecommerce in particular, requires secure communications. Spoof attacks, interception of transmissions and other hacking possiblities can make the internet a dangerous place to do business in. Commercial transactions on the web can be successful only if the transacting parties are sure of who they are dealing with. The right technological infrastructure that can successfully thwart such attempts has to be in place if the web is to achieve its true commercial potential. Public key infrastructure (PKI) enabled by cryptography provides such a secure basis.

Digital signatures

A digital signature is the electronic equivalent of a handwritten signature. It provides authentication to a message, and prevents the sender from later denying that he or she did not send the information. Digital signatures use public key cryptography: in its simplest form a message is encrypted with a private key, and if it can be decrypted with the corresponding public key, it establishes the identity of the owner. Since a digital signature uses encryption on the message (which could be an invoice, an advice, a commercial contract), the signature generated would be different for each message. For this reason, it is not possible to simply cut-and-paste somebody’s digital signature from one message and attach it to another. This is because when decrypted, it will give a different result to the altered message.

A digital signature is superior to a handwritten signature in that it cannot be counterfeited and also in that it applies to the whole content of the message that was signed unlike handwritten signatures where the content of the material being signed can potentially be changed later on. A key concept related to digital certificates is ‘non-repudiation’, ie the person who places his or her digital signature cannot later deny that the matter being signed originated from under his own hand. Without the concept of non-repudiation, digital signatures will carry little weight in the commercial world and their usefulness will be severely restricted. The principle of non-repudiation is supported by most modern legislation covering electronic transactions.

The security of a digital signature depends upon the security of the private key. If the private key falls into the wrong hands, the potential for misuse is high and ‘non-repudiation’ may make it difficult to deny commitments that may have been created fraudulently. This is a key limitation for digital signatures over handwritten signatures for unlike the human hand, which can never be compromised (except under duress which if proven makes the actions void anyway), keys can sometimes be stolen even without the owner being aware.

The other key issue that could potentially limit the practical usefulness of digital signatures is that the public keys for a person that another relies upon may have been falsely created. This is the classic man-in-the-middle attack, for example one may create a private key and circulate the corresponding key as belonging to someone else. If another person relies upon such a false public key, communications may actually be happening with an electronic impersonator and not the real person. This is where digital certificates come in.

Digital certificates

An important requirement for public key cryptography to be practically useful is the secure distribution of public keys. The person, whether a sender who encrypts with a public key, or a receiver who uses the public key to decrypt a private key encrypted message must be certain that the public key they are using actually does belong to the correct person. If you are dealing with a very small group of people, they could exchange public keys directly, say using a floppy. This is rarely possible in real life where you may need to deal with a large number of complete strangers and need to be sure of there true identities. This is where digital certificates come in.

A digital certificate is an assurance provided by a third party (called a Certification Authority) that a public key indeed belongs to the purported owner. A digital certificate contains a public key, the name of the person (or corporation) that the key belongs to, and the whole things is authenticated with a digital signature. Generally, the digital signature comes from a trusted source, usually a company called a Certification Authority, for example, Verisign.

The purpose of a digital certificate is to state that the information on the certificate (ie the public key, and the name of the person it belongs to) has been attested by another person or entity. This attestation helps establish the accuracy of the public key, and therefore by implication the authentication and confidentiality of any message that can be decrypted with this public key. It also allows the world at large to send encrypted messages to the owner of that key without worrying about the message falling into unintended hands.

The attestation from the ‘other’ person, usually a Certification Authority, is itself in the form of a digital signature. Which implies that there must be some way of establishing the correctness of the public key of the Certification Authority. Normally in web browsers, which represent the most common and visible usage of public keys and encryption, the public keys of the established certification authorities are shipped with the software itself. These are directly trusted without the user being prompted. When you go for the first time to a site that offers a digital certificate signed by a Certification Authority not included in the list originally bundled with the browser software, you will get a security alert that will tell you the about the certificate and allow you to import it.

(The certificates shipped with Netscape 4.7 can be viewed by selecting Communicator, Tools, Security Info and Certificates from the menu, and those shipped with Internet Explorer 5.0 can be viewed by selecting Tools, Internet Options, tab Content, and Certificates. When you are on a secure website, you can see the security information about the certificate being relied upon, the strength of encryption etc by double clicking the padlock that shows in both Netscape and Microsoft browsers.)

An important thing to remember about digital certificates is that they allow you to establish who you are dealing with – it does not provide any assurance about the integrity of the person or that any transactions that you make with someone with a digital certificate will be honoured. So you still have to watch out for who you are dealing with, a digital certificate will confirm that you are dealing with John but gives no guarantee that John is not a crook.

Public Key Infrastructures (PKIs)

The use of public keys on a large scale requires the bringing together of the resources that will make it possible to do so securely, for example a certificate server that allows users to submit or retrieve public keys, facilities to ensure that certificates are granted to genuine applicants only, and managing all the administrative tasks (such as revocation, when the private key has been compromised) that go with public key technology. Taken together, these are called Public Key Infrastructures, or PKIs for short.

Technically, PKI is the combination of the technologies, infrastucture and practices needed to enable use of public key encryption and digital signatures in distributed applications on a significant scale. The main purpose of PKI is to distribute public keys accurately and reliably to those needing to encrypt messages or verify digital signatures. This employs digital certificates issues by certification authorities mentioned earlier. PKI also covers certificate renewal, revocation, status checking and private key backup and recovery.

PKI performs the following three basic functions:

1. Authentication: Validating the identity of the parties in
communications and transactions

2. Confidentiality: Ensuring that information, even if intercepted, cannot be used by unintended recipients

3. Non-repudiation: Ensuring that transactions once committed are binding and irrevocable

The uses of PKI vary, the most common and visible being the use of SSL (secured sockets layer) by web browsers. Other uses include secure email, firewalls, routers supporting Virtual Private Networks over the internet, and SSO (single-sign-on) to corporate applications.

Hierachy of trust: root and trusted introducers

Often, trust in the world of digital certificates and PKI is hierarchical, ie a digital signature is trustworthy if it is signed by someone whose signature in turn has been attested by someone whose signature is trustworthy. A hierarchy of trust establishes valid trust so long as the validity of any signature can be verified by tracing it back to a directly trusted ‘root’ certificate.

In real life, hierarchies of trust are no longer than two levels, ie a ‘root Certification Authority’ that certifies other trusted introducers simply called ‘certification authorities’. Only the root Certification Authority can certify other certification authorities, and the latter are not empowered to certify more certification authorities.

Public key infrastructures are an important enabler for e-commerce in the digital age, but they are not infallible. The authority of Certification Authorities may be questionable, and legislation to control their business practices - including whom to or how they grant certificates, or how they bestow upon another CA the authority to issue certificates - is still in its infancy. The Practice Statements of most CAs exclude all liability to themselves and one may question whether the certificates they issues are worth anything at all. There may be lax security practices surrounding the CAs own operations leaving customers exposed to security compromises.

However, these do not really undermine either the technology or the need for PKIs. A maturing market and increasing ecommerce will mandate improved business practices and create the legislative infrastructure that is needed. PKI is here to stay and will emerge as a key pillar of the emerging electronic economy.