How Secure is PGP?


Assuming you trust IDEA, PGP is the closest you're likely to get to military-grade encryption - Bruce Schneier

This was written in response to a posting by dunadan007@aol.com to alt.hackers.malicious 29 May 1996 07:09:13 -0400, also to put my own thoughts in order. Primarily my own thoughts plus a small amount of refinement after reading the references listed below. I have tried to keep it relatively simple in order that it is applicable to a wide audience as I see little point in duplicating what others have already produced. Those who want to dig deeper should pull up the references listed at the end.

The security of an encryption system depends upon a lot more than the encryption algorithms used. It depends upon the context in which it is used and the societal need for that use. Therefore whilst I have concentrated upon the security of the algorithms I have tried to touch upon the other aspects.

Assuming no bugs, and a good implementation, more on this later, then the security rests on the security of the RSA algorithm.

Assuming a one-to-one equivalence, then the security rests on the difficulty of factoring large numbers into their primes. This is dependent on the power of computers and current mathematical theory. The power of computers makes only marginal difference as the power to crack at one end can be more than compensated for at the other end by the use of larger key sizes.

The security therefore rests on the difficulty of factoring large numbers. There could be a major breakthrough in factoring which would render all RSA encryption visible. This is thought to be unlikely, but what is needed is a formal mathematical proof, otherwise it is simply that no one has found a better method. Similarly a formal mathematical proof is required to show the equivalence between RSA and factoring, otherwise there could be a breakthrough in cracking RSA through an entirely different route. Again thought highly unlikely, but this is not the same as a clearly demonstrated impossibility.

To return to the initial assumption, the implementation. Phil Zimmermann has published the source code which has been subjected to intense scrutiny. No one has yet found a flaw.

A flaw that was found in an earlier version was that the random number generator that produces the IDEA session key was not as unpredictable as previously thought. This has been fixed.

The security of the system rather than PGP itself is threatened by a design flaw or possibly a bug. I always tell people to write protect their floppies. With PGP this is not possible as it tries to write to the floppy when checking signatures. Let's assume you've just received a shareware package and you are pleased to see that it has a detached PGP signature enabling you to check it for tampering. If you do this with the shipped floppy, PGP will attempt to write to the floppy. If you unprotect the floppy you then run the risk of not only catching a virus but also corrupting the files. A work around is to copy the file and associated signature to a temporary directory and perform the test there.

It is possible to check the integrity of the shipped PGP package but not once the files have been unzipped. The executable files should have their own detached signatures (proposed PGP distribution enhancement). These files can then be checked at a later date for possible corruption. PGP should have built in self-checking (proposed PGP enhancement). This is not foolproof (there are ways for a virus to get around it) but it's better than nothing and it will detect most viruses and whether PGP has been corrupted. This would take time to perform therefore I suggest a self-check switch.

The wipe switch (-w) is none too good. It does not go to the end of an allocation unit, nor does it remove pointers to the file location. If an undelete utility is used it is possible to recover the deleted sectors. These will be scrambled but at least an attacker knows where to start. I recommend the use of my own Wipe utility (part of SECURE) as it does not have these problems.

I'm not convinced that any electronic shredding can be 100% effective. Probably the only really secure data destruction is to electronically shred, destroy the disk, then scatter the remains to the four corners of the earth. Environmentally this is a disaster. A sounder environmental solution would be to electronically shred, the file could be encrypted first, but only with an encryption package that overwrites the original file (PGP does not); then low level reformat; followed by anonymous disposal of the disk through a charity or second-hand shop. The new user would (hopefully) lack the ability to recover the disk contents and would (hopefully) thoroughly recycle the contents.

One possible Machiavellian scenario. NSA discovers a gaping flaw. They seek to have PGP banned and harass Phil and associates to make their point in the full knowledge that activists will ensure that PGP is widely used and widely spread around. I did imply it was far fetched, but remember who we are dealing with.

I read a book a few years ago that detailed the CIA's activities in Central America with the Contra's. I think it was by an investigative journalist working for TV. If a few titles can be thrown at me I may remember the title then I can add it to the list of references. Even better if anyone has a spare copy they don't want!

As discussed, algorithmic methods are currently infeasible or unknown. Similarly a brute force attack. If we take the IDEA key then with a key of 128 bits we are talking of 2128 possible keys, a lot of keys to search. 2128 --> 3.4 x 1038

     340,282,366,920,938,463,463,374,607,431,768,211,456

On average we would have to search half the key space - 2127

     170,141,183,460,469,231,731,687,303715,884,105,728

A brute force attack on a small RSA key is feasible. What is classed as small gets larger each year. RSA-129, a 129 digit key, was cracked using 5,000 mips-years. In 1977 this was thought impossible to crack. To put this in context my PGP key, as is most users, is 1024-bits. Using the same amount of computing resources it would take many millions of years to crack my key (assuming no advances in factoring algorithms).

A single mips-year is a computer continuously number crunching at the rate of a million instructions per second for one year.

A 129 digit key translates to a 429-bit key. This is too close to comfort to the 512-bit key that many users are still using. Every additional 10 bits is very roughly a doubling of the computational power required to crack a key. It is within the bounds of possibility for a company with several hundred workstations to crack a 512 bit key of a competitor. This could be done as a background task stealing spare CPU cycles. As many companies have discovered to their cost it is all too easy to steal a march on a competitor by stealing their secrets than it is to do some hard work.

A crippled version of PGP could be circulated. The session key generator could be sabotaged to only generate a small subset of possible keys, but sufficiently large to go undetected. Examination of an encrypted file would reveal nothing wrong as the IDEA key would be legitimate. Similarly the sequence would be one of many possible sequences. An attacker only has to search through this reduced key space. The beauty of this fix is that once a key is found the attacker only has to search from that point onwards using a known algorithm to decrypt any subsequent message.

A $1,000,000 deposit to a bright student in a Swiss bank account should suffice. Far cheaper than the purchase cost of the computers required to search the entire IDEA key space.

The CIA director of counter-intelligence was got for less than two million dollars, his wife came free!

Then upload as a later version to fix a bug and a NSA back door and it would be rapidly taken on board by a gullible user population.

Another way to frig PGP would be to encrypt the session key with a master key and bundle that with the encrypted file. Think of it as an invisible recipient on the command line. This should not involve more than a minor modification. It would probably be detectable by examination of the headers, but how many people scrutinise their headers? A more subtle variation would be to embed the extra key somewhere within the file. One possibility would be to have some invisible end of file marker, followed by the third party key. The trick is to get an unmodified version of PGP to accept these files with no complaint.

The same encrypted message 'I wanna tell you a secret' could be surreptitiously inserted into every encrypted file. It may aid crypto analysis. It would though encounter the same problem of fooling genuine versions of PGP as the above modification.

May be someone, somewhere has cracked PGP and is keeping real quiet about. Yeah, and may be pigs will really fly. Hackers and crackers like to brag, have to brag, have a compelling, deep-seated, pathological need to brag. Crypto cracking is hot news. Were someone, somewhere to crack PGP the news would spread faster than a bush fire in the dry season.

We are happy if it takes millions of years to crack our code, less than happy if it's a few centuries, distinctly unhappy if a few seconds. A few seconds makes it possible, but not practicable to monitor everyone's e-mail, assuming we all use encryption. What unfortunately does become practicable is the monitoring of dissident groups within a state.

The power of the encryption used is sufficiently strong that the weak link becomes the pass phrse. Why search for all possible keys when it is considerably cheaper to search the pass phrase space? If we take into account the redundancy of the Enlish linguige (equally applicable to any forign lanquage) and ibnoring any attpmts at randomness then our search space is many orders of magnotude less than the key space.

Redundancy is why you can still read the above inspite of my many spelling mistakes. Were English to lack redundancy then a single error in the previous paragraph would render it unintelligible. It may be unintelligible for other reasons but that will be down to my lack of clarity or the inability of the reader to comprehend.

An example of minimal redundancy is an executable file. If corrupted it is likely to fail - every bit counts.

If we consider a password of arbitrary size and choose any letter at random then the search space would be 26 raised to the number of characters. Let's assume an average word size of eight characters. 268 is 2.09 x 1011, compare this with the less than 140,000 word entries in my Concise Oxford English Dictionary.

Deliberate spelling mistakes are a way of improving our pass phrases by reducing the redundancy. The only problem is that this has to be done in some regular manner to enable us to remember our pass phrase.

The problem is made worse if we access many systems. Our attempts at misspelling may have a regularity that it detectable.

The use of several systems highlights the problem. We can probably remember one long pass phrase but can we remember several? We can not use the same pass phrase on several systems as the breach of our pass phrase on one weak system will cause a breach on all the systems we use. Back to the weakest link again.

I felt pleased when I had a pass phrase in excess of 60 characters. The only problem was I had great difficulty in remembering it and even more in correctly typing it in. I once spent the best part of an afternoon trying to type it in correctly.

There is therefore a very unhappy compromise between the randomness of the pass phrase, its length and the ability to remember it.

The temptation is to write down the pass phrase which then introduces a different security compromise.

The accepted wisdom has always been 'never write down your pass phrase'. Maybe it's time we gave this some second thought. The increase in security by the use of a longer or more random pass phrase may outweigh the risks of discovery. Our pass phrase should not be so complex that we have to consult a written form each time it is used, but it can come in handy to jolt our memory for a pass phrase that is difficult to remember, or hasn't been used in a while. I was once away for a few weeks and on my return I had great difficulty in remembering my pass phrase!

A possible compromise may be to pick something out of a book at random. Then all you have to do is remember the page. Ideally this would be across more than one sentence but only a fragment of each thus having no real sense.

	of access to your secret key Although this 

It is important not to to get too hung up on the weakness of the pass phrase. Eight random words will make the pass phrase more secure than the IDEA key. For practical purposes it can be less as it will still involve hell of a lot of attempts. The weakness of the pass phrase in only of relevance if we are worried about our system being attacked. If it is simply a question of access to our traffic then it is irrelevant as to be of use it will also require our secret key. Using a dictionary of 140,000 words, choosing eight random words will give 140,0008 --> 1.48 x 1041 (cf key space 3.4 x 1038). Deliberate misspelling of the original plain text message reduces the redundancy and this may hinder crypto analysis. With PGP this is hardly likely to have any effect as the plain text message is compressed prior to encryption, thus removing any redundancy. As discussed, where this can best be used to advantage is in the construction of a pass phrase.

One of the worst cases of password misuse that I have ever seen was at a local Technical College. Students were given a User ID that consisted of their course code plus a sequential serial number for each student on the course. Their password was, yes you've guessed it, their User ID. The students were supposed to change their password but when do students ever do what they are supposed to? To make matters worse, if that's possible, I know of at least one case where the method of giving the students their password was to hand out a sheet in class listing all the students and their User ID. Whether this procedure was typical I don't know. I found it difficult to comprehend why they bothered with the passwords at all.

The weakness of any public key system rests on the public key itself. If you do not have the recipient's key then you are encrypting the message for someone else and at the very least denying access to the recipient. A possible scenario is substitution of the key. Message goes to attacker, attacker reads message, re-encodes and forwards on to recipient.

Always sign your key, this prevents tampering; always have others sign your key, this enables verification of the key; regularly check the key on servers, this prevents substitution.

Ironically the person who posted the question had not signed his key!!! A dangerous oversight when posting to a malicious hackers news group.

Another possible weakness to consider is that you of course have taken every precaution but the weak link is the recipient. You have encoded a message that hopefully only the recipient can read. If security at the recipient's end is lax then maybe all and sundry can read the message. This is a point to always bear in mind when sending encrypted e-mail to a third party.

Ultimately the security of PGP depends upon denial of access to your secret key. Although this is normally viewed as someone having direct access to the system this should be seen in a wider sense. A virus has access to your system.

Viruses and Trojans are a topic in their own right and I refer to

Whilst on the subject of Trojans Phil Zimmerman warns of the existence of Trojan versions. If the genuine item lacks a back door or any obvious implementation flaws then circulate a version that does. I have put together a disk that has a large amount of PGP information and of course PGP. I can not be absolutely certain but so far all my checks have not shown it to be fake. Copies of this disk can be obtained direct from myself at the price of £5-00 (five pounds sterling).

The UK government is testing the water for a ban on encryption, as no doubt are many other governments around the world. I'm doing my best to get PGP spread around and to heighten awareness of the need for encryption. Help is needed. Monitor the press. Any editorial hinting at key escrow or a ban on hard crypto get a letter off to the editor. To wait until legislation is introduced will be too late as it will take too long to build up momentum. [see my paper Why Use Pretty Good Privacy?]

The security of the algorithms can be seen as theoretical security. Everything else can be viewed as practical security. Pass phrases fall between the two.

For virus detection I recommend that Windows software not be used. The same could be said for the use of Windows front ends for PGP. There is too much going on that we can not say what is going on. In a multi-tasking environment there are other processes running.

Within a specific implementation there is disk swapping. This is not cleaned up or laundered in any way (Windows is too slow already). The disk can be mined for information in much the same way as a rubbish bin.

A person, or a virus, could make a substitution for your key pair, that is a substitution of your private and public keys. As soon as you have generated your keys you should take a copy. Periodically check your secret key against the backup copy. PGP can be requested to perform a complete keyring check. I would also advise making a hard copy printout of your public key fingerprint. Apart from its usefulness in handing to other people so that they may check the validity of your public key, you can use it yourself to periodically check the key's validity.

How much effort do you wish to throw at the problem? The person can be filmed, their telephone bugged, the computer electronically scanned, keystrokes sampled, networks sniffed, IPs spoofed, routers attacked. If you are using PGP remotely, packet sniffers could be used (this is really no different to monitoring your plain text e-mail). We are now in a different ball game. If you are worth this much effort then you have slightly bigger problems than worrying about the theoretical security of PGP.

Never underestimate the resources an attacker will deploy to crack an encryption system. If the gain exceeds the investment it is a profitable deal. Multi-million dollar drug deals are common place. The banks routinely use DES for the transfer of electronic funds. The 56-bit key used for DES is weak. A dedicated DES key cruncher can be built for less than one million dollars. It can be made faster by increasing the investment. Is it worth the Mafia making such an investment?

If I wanted your pass phrase I'd break in and install a keyboard monitor. How many people check what is loaded by the batch file? A more sophisticated attack would be the use of a boot sector stealth virus. This is unlikely to be detected as few people do a thorough virus check. The virus would monitor for PGP. Only when PGP was used for signing or decrypting would it record the keystrokes, which would be placed in a small hidden file. The file size is sufficiently small that I could store it in slack disk space. Every machine unbeknowest to its user could have the secret key squirrelled away. This information could be recovered at a later date by physical access to the machine, or possibly the virus could send it out down the line. Having served its function the virus would remove itself.

To avoid this problem boot from a known clean floppy and use PGP from a write protected floppy.

Pass phrase crunching, key space crunching is very costly. It is a lot cheaper to kidnap and torture the individual or a member of his family. This scenario should not be lightly dismissed as I have direct personal experience of it happening.

What the new ball game has done and that is the most any good encryption system can do is to shift the balance. Without PGP a general trawl can reel in masses of information. With PGP we are back to the pre-electronic era. The same amount of effort has to be expended as is needed to steam open mail, tap telephones et cetera. It may be a breach of human rights, contrary to existing legal protection but to justify this amount of effort there has to be some overwhelming reason for the effort whatever the legal niceties. In the real world this is probably the best we can ever achieve.

A Practical Random Pass Phrase Generator

All you require is a large dictionary and a coin. The coin is used to perform a binary search of the dictionary. Flip the coin; heads choose the first half of the dictionary; tails the second half. Continue in this manner until you are down to a page. Heads chooses the first column, tails the second; heads the top column half, tails the bottom. Eventually you will have a word. Repeat the process to get seven more words.

In a trial run this gave

  bless bat alcohol foredeck algolagnia yearbook fowl rebroadcast
Anything better than a 70,000 word dictionary will give a search space greater than the IDEA key. With a 50,000 word dictionary its only marginally less - add another word and the search space is considerably greater.

Two problems; remembering a random list of words; spelling long or unfamiliar words. The latter can be an advantage if we always make the same mistake. An extra level of randomness has been introduced, but if this is a regular personal trait it could be duplicated. This though takes us full circle as only through the monitoring of our correspondence could such a trait be detected!

Pass Phrase in a Foreign Language

There are conflicting noises heard as to the relative merits of a foreign language pass phrase. My own thoughts are that it depends upon the context in which it is used and the form of the attack.

If I type my pass phrase in a language foreign to an observer and that observer catches a glimpse of what I'm typing it will appear as a jumble of random characters, on the other hand if I type my pass phrase in a language native or known to the observer the observer is likely to be able to reconstruct my pass phrase due to the redundancy of the language.

If the attack is in the form of a dictionary attack, it will gain some advantage but not a lot.

Spanish and English are two of the world's richest languages. To give some ball park figures let's assume I have a bilingual dictionary Inglés-Español that has double my English vocabulary of 140,000 words, that is 280,000 words. Choosing eight random words will give a search space of 280,0008 --> 3.7 x 1043. This increases the search space beyond that of my English dictionary but not greatly so (a couple of orders of magnitude). I could obtain the same effect by either using a larger English dictionary, or adding one more word to my pass phrase. The latter has the greater effect. 140,0009 --> 2.1 x 1046.

The main advantage of using a second or foreign language or a mix of the two would be to flummox the opportunist or casual attacker.

Information

A message contains information if it tells us something that we did not know before. The higher the information content the greater the degree of surprise.

A plot of a DC voltage is a straight horizontal line. It contains no information apart from the initial voltage level as whenever we look at the plot the information content is always the same. If the voltage level was 5 volts then we always expect to find 5 volts.

A sinusoidal waveform is changing therefore we expect some information. Unfortunately not. The change is periodic and predicted by a simple formula. At any point in time provided that I know the initial conditions I can predict the state of the waveform.

When I read a book it conveys information - that's why I read it. An example is Along Came A Spider a novel about a sociopath. From one page to the next it's impossible to predict what will happen next. It's also a very good book.

The above example from my random phrase generator has a high information content as no matter how much of the sequence we expose we can not predict the next word(s). If you randomly pick any of my sentences and slowly expose each successive word it will not come as a complete surprise - the information content is lower.

Similarly by picking out any word, if you mask out letters it will not be too difficult to fill out the blanks. With the word in context it becomes even easier to fill out the blanks. The higher the redundancy, the lower the information content.

Compare the following pass phrase with my random pass phrase

     And they all lived together in a little crooked house
It contains two more words but about the same number of characters as my random pass phrase. It is easy to remember partly because it has some sense, but more because it a line from a rhyme. For these reasons it contains less information than my random phrase. As a pass phrase it is fairly useless, partly because it is part of a well known rhyme but also because it is a key phrase from the Agatha Christie novel Crooked House.

When devising a pass phrase we try to maximise the information content, that is lower the predictability. The higher this information content or unpredictability the higher the entropy.

The higher the entropy the greater the security.

Can the Security be Improved?

The intrinsic security of PGP and the underlying algorithms is good and is not in need of improvement, where improvements can be made is in the use of the encrypted data which may possibly add many orders of magnitude to the security.

PGP encrypted files carry a header stating that PGP was used and the encryption method. This at least tells an attacker where to start and what tools to use, even if that attack using current technology and mathematical knowledge may not be successful. The headers can be stripped off. All that is then left is a file of random data - digital white noise. There is nothing to say what the file is, that it has been encrypted or how it has been encrypted. It could have been encrypted using triple DES, a propriety algorithm, IDEA, RSA, knapsacks ...

Removal of headers removes the weak link, the human element, upon which undue pressure can be applied. In the absence of a header there is no Key ID to link the file to a key owner.

Henry Hastur has developed a program called Stealth that strips out PGP headers. The recipient uses Stealth to re-insert the headers prior to decryption with PGP.

All files have structure. The file you are reading is an ASCII file, an executable file has structure (if not it could not run, and it is the lack of a recognised structure or an identifiable deviant structure that is used by heuristic scanners to identify possible virus infections), an image file may lack internal structure but it will usually have a header to give some structure. Removal of PGP headers will leave a file of digital white noise, with nothing to identify it, this very lack of structure may in itself trigger off an alert. We don't know what it is therefore that in itself is suspicious.

Using a technique known as steganography the encrypted file with or without headers (ideally without) can be embedded in a high entropy file such as a sound file or an image file. The file is then used as a carrier. Transfer of encrypted files between parties may trigger an alert, not the exchange of image files.

During a chance meeting with a Malaysian acquaintance we discussed the use of PGP. I offered him a copy of PGP to take back to Malaysia. Whilst he could see the advantages of possessing a copy he declined my offer as he said the very act of using encryption would bring him to the attention of the authorities and to emphasise his point he held an imaginary gun to his head and pulled the trigger. Were my acquaintance and his colleagues to exchange image files it's doubtful that anyone would give them a second glance.

Asian tigers never change their stripes. Several years ago my acquaintance was thrown into gaol for attending a student demonstration. Malaysia actively monitors the e-mail of all Malaysian students studying abroad.

Tools also exist to convert the ascii armoured file into nonsense verse. This does not hide the encrypted file, rather it disguises it. To the casual observer, and probably computer key word search programs, there is nothing unusual to attract attention.

Trusted Third Parties

Governments around the world are pushing for key escrow, and by implication a ban on hard crypto. The UK Government has just (June 1996) proposed a key escrow compromise - the key(s) will be held by a Trusted Third Party. Trusted by whom I don't know. Nor whether such a scheme would be mandatory or voluntary. When I have more information on this proposal I'll release a paper.

Hot News! Users to deposit their key with a government approved TTP, key to be revealed on production of warrant, users may use cryptosystem of their choice, scheme appears to be voluntary, legislation pending.

Because of where they are coming from TTPs have a bad smell, but they can be used to advantage by PGP users. It is all too easy to lose a key. Lose - loss of pass phrase, keyring destruction, virus attack, wiping of a disk et cetera. A lost key means permanent denial of access - the ultimate security nightmare. If a key is lodged with a trusted friend the situation can be recovered. Ideally the key would be cut in half (proposed PGP enhancement). If the location of a key is discovered and undue pressure is applied to release the key it would be of little use without its matching half. You may wish to leave instructions for the release of your key upon your untimely demise. Your benefactors may not be too pleased that they can't gain access to your ill-gotten gains hidden in Swiss numbered bank accounts because the numbers of those accounts are securely locked away.

If you have not already done so I strongly recommend that you take a backup copy of your secret key and store in a very safe place whether or not you make use of a trusted friend.

Under this scheme it is you who decide who to trust (not the government or their agents) in the same way as it is you who decides whose certifying signature you trust to verify a public key.

Traffic Analysis

In the 1960s the FBI detected a major Mafia conspiracy not by what was said to whom, but who was talking to whom, when the conversations took place and where the participants were located. This is known as traffic analysis.

If all your e-mail is plain text and along comes an encrypted one it may trigger an alert. If all the e-mail is encrypted there is nothing unusual. It also means all the messages have to be decrypted to find the one secret one.

There is a slight downside. It takes time to encrypt and decrypt messages. From the security viewpoint, every encrypted message that an attacker can obtain is one more tiny piece of the jigsaw. Even though this small advantage is probably more than outweighed by having to wade through large numbers of encrypted messages the more an attacker has to work on the easier it is to crack an encryption scheme.

Who is talking to who may provide as much information as the message content itself.

Anonymous remailers provide a cut-out so that it is not possible to see the originator. If I wished to send something securely I'd use a transient account. Then even if the message could be back tracked there would be nothing to link it to myself. Aficionados of remailers use a chain of remailers - the sender is only known to the first, the ultimate recipient to the last.

Anonymous remailers provide a delaying tactic but they should not be seen as providing absolute security. The administrators may be forced to hand over your true ID, the system could be hacked or the security in some way breached, they could be infiltrated, there could be a 'sting operation' et cetera. Incorrect use of the remailer can accidentally release your true ID or make it easier for others to discover it. Any mail sent via a remailer should always be encrypted. Anonymous remailers are a means to protect the innocent, they are not a shield to hide behind to harass other users. Many system administrators have said they will release the true ID of users who abuse their system.

The PGP header contains the KeyID, this may be used to identify the recipient.

Key Exchange

The problems associated with conventional encryption systems are well known. The need for a secure means of key exchange, the need to guard the key, unmanageable large number of keys for a large number of communicating parties. Public key systems appear to avoid these problems - the key not only is made public, but it is a distinct advantage to broadcast far and wide. Unfortunately there is no such thing as a free lunch and and all we do is replace our original set of problems with a different set. The primary problem now is that of key substitution and key tampering.

To illustrate the problems and put forward a few solutions I'll use a few of Schneier's characters. Alice and Bob wish to communicate, Mallory is a malicious attacker, Trent is a trusted arbitrator, David and Carol may at some stage join in.

Man-in-the-Middle Attack

Alice and Bob exchange keys. Unbeknown to them, Mallory intercepts their key exchange and substitutes his own keys. Alice and Bob encrypt their messages and forward to each other. Mallory intercepts these messages, extracts any useful information (using his own substituted keys), he then re-encrypts using the genuine keys. Bob and Alice are none the wiser.

Bob and Alice need not have exchanged their keys directly. They may have got them from Trent's trusted key server. Mallory can intercept the key transfer as before, he also has the opportunity to substitute a key on Trent's server and although Trent is a byword for integrity Mallory has yet to meet someone he can't corrupt.

Interlock Protocol (Rivest & Shamir)

Alice sends part of her encrypted message to Bob. On receipt Bob sends part of his encrypted message to Alice. Alice on receipt of his part message sends the remainder of her encrypted message. Bob on receipt of the remainder of Alice's encrypted message puts the two parts together, decrypts, then sends his latter half to Alice. Mallory is still able to intercept but he can not do anything with a part message, he needs the whole. The best Mallory can do is sever the connection. If Bob and Alice have the wrong keys they will be unable to read their correspondence. Bob and Alice will be denied the opportunity to communicate but at least they will be aware that something is wrong.

This protocol can be implemented in PGP by sending an encryption of the encrypted message's signature as the first part, then sending the encrypted message as the second part. It is infeasible for Mallory to substitute another message to match the encrypted signature, nor can he anticipate the coming message and substitute an alternative message as the signature function is one-way.

Key Signatures

PGP attempts to avoid these problems by the use of key signatures. Whilst it appears to remove the problem it merely moves the problem further down the line.

Now when Alice and Bob exchange keys or download from Trent's trusted key server they notice that their keys have been signed by Dave and Carol. This now begs the question 'how do they obtain a genuine copy of these keys?' ad infinitum. Luckily for Bob and Alice, Alice went to school with Carol and at a recent school reunion they took the opportunity to exchange keys, Bob and Dave are regular drinking cronies and exchanged keys some time ago. They each can therefore verify each others keys with a genuine key from a third party. The rest of us may not be so lucky.

The only key you can explicitly trust is one that you have acquired in person from someone you know. With all other keys steps have to be taken to minimise the risk. Obtain the key direct from the person via a number of different routes. All the keys should be identical. Use the key fingerprint as a back up, obtain the fingerprint through a tamper proof medium, fax, letter, telephone conversation, publication in a journal et cetera. Be wary of the signatures. Each of these has to be checked out with the same degree of rigour as the key they are supporting. The most vulnerable way to transfer a key is through Internet.

Always do a test transfer of trivial information to establish the link. Using the interlock protocol will establish whether or not Mallory is substituting. What it will not do is establish whether Mallory is impersonating Bob or Alice.

Always self-sign your own key. This will not prevent substitution, but it will prevent tampering. I can easily create a fake key for Bill Clinton. I can also create a large number of keys with which to sign the key though some people may suspect something odd when they see signatures of JFK, Elvis Presley, Jimi Hendrix, Billy Holiday, Buddy Holly.

My Public Key Fingerprint

pub  1024/B09CC89D 1996/04/22 Keith Parkins <10 GU14 6QJ England>
Key fingerprint  2A 66 6A 8F 91 42 48 C8  48 98 38 AD 2F D3 45 08

AT&T PathServer

As discussed, key exchange is a problem. AT&T are running an experimental service that goes some way to alleviating this problem.

You have downloaded a key, even though it may have signatures these are not a great deal of help if you do not have trusted versions of the corresponding keys. I have spent hours, if not days checking signatures ad infinitum.

PathServer, developed by Mike Reiter and Stuart Stubblebine, automates this process. Given an unknown key, and a trusted key (either your own or one that you have received in person) it will plot one or more paths between the keys, the paths are not permitted to cross or overlap.

The system is not foolproof and I can see a number of security holes. PathServer is hooked into the existing world net of key servers, thus it is only as good as its source. PathServer could have bugs, or possibly cheats. The link to PathServer is not secure.

The user does have some control over PathServer cheating. Once the path(s) are established, the user can download the connecting keys from other sources and perform checks on his own system.

PathServer helps to build confidence in a key. It is a step in the right direction.

Exotic Scenarios

I have unashamedly lifted these straight out of Bruce Schneier's excellent book Applied Cryptography (which I strongly recommend to anyone with an interest in cryptography) and mixed in a few thoughts of my own.

Virus Key Crunchers

As discussed, a cooperative effort can be used to crack keys. The main problem is obtaining that cooperation. A stealth boot sector virus could be released. Its activity, to steal spare CPU cycles for key crunching. Because it is stealing spare cycles it would not have a noticeable effect on performance and is likely to go unnoticed. Contrary to the claims made by vendors, virus scanners are not very effective and until a virus is drawn to their attention and is built into their scanners it will continue to go undetected. The vendors could be leant upon not to detect it. If they fail to cooperate viruses could be released to target their products. Once a key is cracked, its result could be transmitted down a modem or the virus could change mode and now spread with the broken key in the hope that a copy will be picked up. Alternatively an error message could be displayed together with a number for a free phone telephone help line. The error code to be read off screen would be the cracked key.

Chinese Lottery

The vast majority of consumer electronics are manufactured in the Pacific Rim. As labour costs rise in each country more and more of that production is being relocated to China. Each radio and TV could have a built in key cracking chip. Mass production keeps the production costs down. The Chinese government broadcasts the keys it wishes to crack. Millions of radios and TVs crunch away with their purpose built chips. Eventually 'bingo' and the result is displayed on a LCD or TV screen. The lucky listener 'phones the hot line to claim her prize.

These scenarios could be used to crack any key encryption system, not just PGP.

Document Fingerprinting

It is possible to produce a number of unique variations of the same document. This is not a technique unique to PGP.

When I wrote my paper on UK escrow proposals it went through several revisions. The sense of the document did not change. All that was altered were subtle spelling mistakes. Each revision was distributed. My subtle mistakes could, if I so wished, be used to track any copy of the document back to source. My subtle mistakes could have been introduced deliberately. I then have a tracking mechanism.

A paper with a ragged right margin has white space at the end of each line. On paper it is just that, white space. In electronic format each line is terminated with carriage return, line feed (MSDOS, other systems handle lines differently). I could at the end of each line add an extra blank character. Given 128 lines to play with, my document would have as many unique variations as the IDEA key space. I could automate the process, a random variation for each and every recipient, their names added to a database. Should there be any query or the document be secret I can trace back to source.

References

In case of difficulty go to the two main PGP Web pages as they maintain very good links, these guys also have interesting home pages with many good links for cryptography and security. When I find some spare Web space I shall be launching a UK PGP Web site.

Stale Schumacher International PGP Home Page

Francis Litterio, Why You Should Sign Your Own Public Key

Arnold G Reinhold, Results of a Survey on Pass Phrase Usage

Grady Ward, How to Choose a Passphrase FAQ

Randall T. Williams, Passphrase FAQ

infiNity, The Feasibility of Breaking PGP: The PGP attack FAQ

Key logging utilities, keyboard snoops

Packet sniffers

Concise Oxford English Dictionary, Ninth Edition, OUP, 1995

Keith Parkins, Virus: A computer malaise, Book on Disk, 1995

Simson Garfinkel, PGP: Pretty Good Privacy, O'Reilly & Assoc, 1995

Bruce Sterling, The Hacker Crackdown, Viking, 1993

R L Rivest, A Shamir & L Adleman, A Method for Obtaining Digital Signatures and Public Key Cryptosystems, Communications of the ACM, Vol 21, No 2, February 1978

Ron Rivest Cyphertext, RSA Nesletter, Vol 1, No 1, Fall 1993

Ron Rivest & Adi Shamir, How to Expose an Eavesdropper, Communications of the ACM, vol 27, no 4, April 1984, p 393-395

Derek Atkins et al, The Magic Words are Squeamish Ossifrage, Advances in Cryptology - AsiaCrypt '94 Proceedings, Springer-Verlag, 1995, p 263-277

Along Came A Spider

Keith Parkins, Why Use Pretty Good Privacy?, 1996

Keith Parkins, Incalculability, to be published

Keith Parkins, UK Proposals for a Key Escrow Encryption System, 1996

Keith Parkins, Privacy in an Electronic Age, 1996

Phil Zimmermann, Why do you need PGP?

Henry Hastur, Stealth

Eric Milbrandt, Steganography Info and Archive

Keith Parkins, SECURE - encryption and secure file deletion

Paul Elliot Cypher Rant: Reasons why private cryptography should not be regulated

Francis Litterio, Anonymous Remailers

Andre Bacard, Anonymous Remailer FAQ

Bruce Schneier, Applied Cryptography, 2nd Ed, Wiley, 1996

Agatha Christie, Crooked House, 1949

Crispin Aubrey, Who's Watching You?, Penguin Books, 1981

Bob Woodwood, Veil: The Secret Wars of the CIA 1981-1987, Simon & Schuster, 1987

Anthony Summers, Official and Confidential: The Secret Life of J Edgar Hoover, Gollancz, 1993

Athan Theoharis (Ed), From the Secret Files of J Edgar Hoover, Elephant Paperbacks, 1993

Alan Friedman, Spider's Web: Bush, Saddam, Thatcher and the Decade of Deceit, Faber & Faber, 1993

Seumas Milne, The Enemy Within: MI5, Maxwell and the Scargill Affair, Verso, 1994

(c) Keith Parkins August 1996 rev 18


This paper is also available as a signed text file.


Home ~ Index ~ PGP ~ Why use PGP ~ Web of Trust ~ Quick Reference ~ My Key
(c) Keith Parkins 1996-1997 -- June 1997 rev 7