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
- Virus: A computer malaise - Keith Parkins
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 <href="catolog.txt">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 isused 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 rebroadcastAnything 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 aforeign 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 wedid 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 ofcharacters 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 isgood 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 byimplication 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 bywhat 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 arewell 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, Malloryintercepts 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 Bobsends 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 keysignatures. 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 anexperimental 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'sexcellent 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 thePacific 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 thesame 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 theymaintain 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
-
http://www.stack.urc.tue.nl/~galactus/remailers/passphrase-faq.html -
http://colossus.net/wepinsto/wsft_f/wspp_f/passfraz.html -
http://zifi.genetics.utah.edu/crypto/crypto.html -
ftp://ftp.infonexus.com/pub/Philes/Cryptography/PGP/PGPpassphraseFAQ.gz
infiNity, The Feasibility of Breaking PGP: The PGP attack FAQ
-
http://www.cranfield.ac.uk/docs/Email/PGP/pgp-attack-faq.txt -
ftp://infonexus.com/pub/Philes/Cryptography/PGP/PGPattackFAQ.gz
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
Org Link
