Die Sicherheit des geheimen Schlüssels |
- SUMMARY
- EXPLANATION
- The Security of the Cryptographic Methods Used by PGP
- The Cipher IDEA
- The Public Key Cryptosystem RSA
- The Hashfunction MD5
- Attacks on the Use of PGP
- Security-relevant Actions
- How to Deal with Your Passphrase
- Attacks on Your Passphrase
- What Is a Good Passphrase ?
- The Newer the Better ? - Versions of PGP
- References to Other Sources of Information
- A Final Request
There are two possible strategies to attack the security of PGP:
which try to make use of the possible weakness of cryptographic methods used by PGP compromising the reliability and security of PGP fundamentally, and
which try to exploit weaknesses of the practical use of PGP. These attacks intend to compromise the passphrase to gain access to the user's secret key or try to deceive other people by distributing faked public keys.
Theoretical attacks on PGP will be unsuccessful, as I will prove subsequently, because the use of RSA-keys of sufficient length makes it practically impossible to gain the user's secret key. The security of cryptographic methods is not merely based on religous faith but can be justified by the history of failed attempts to break them. As theoretical security is based on the results of recent research in the field of computer science it has to be constantly reviewed in the light of new knowledge.
With the pointlessness of attacks on the cryptographic methods the attention of potential datafiends is shifting towards the weaknesses due to the daily use of the secret key. You have to consider a huge number of practical problems if you don't want to put the security of PGP to risk unintentionally. Most important is maintaining the secrecy of your passphrase which protects your secret key because maintainig this secrecy is a problem most people do underestimate dramatically.
For encryption of the text PGP (subsequently I mean PGP-2.6.x) uses IDEA, which is symmetric and works with a key of 128 bits of length, for instance
EXCURSION
Why should it remain impossible for a computer to test all possible IDEA-keys in the near future rather quickly ?
Because as a matter of principle a computer will not have the necessary efficiency. According to todays state of physical research which in future could change the spreading of information in every imaginable computersystem is limited by the speed of light.
Not even the results of current "experiments measuring velocities higher than the speed of light" do contradict that fact.If you assume the size of a high-performance computer system performing keytests is 0.3 mm for electronic or optical transfer of information, it can only perform 1 000 000 000 000 operations (10^{12}) per second, otherwise it has to be smaller. Over a period of 317 years or 10 003 759 200 seconds that will sum up to 10 003 759 200 000 000 000 000 operations. This ability to perform no more than 10^{22} operations during 317 years is truely not sufficient for testing 10^{22} different IDEA-keys because every keytest requires more than a single operation cycle. But even if it was possible to do a keytest that fast, the large number of 10^{38} IDEA-keys would be searched for no more than 0.000 000 000 000 000 029 percent. Thus a specific IDEA-key will not be found even if "lots" of those high-performance computers will work parallel to test the keys.
This argument is based on empirical assumptions and therefore it can be refuted by experience. But without doubt it is definitely wrong to suppose "efficiency of any size" for future computer systems.
The secure performance of the public key cryptosystem guarantees:
The RSA cryptosystem basically uses three different and very long numbers (e,d,n), even if one of those numbers actually is chosen very small due to the technical implementation of the cipher, the security of the cipher will not be reduced. Two of them, the public key e and the modulus n are used to encrypt a message. The message to be encrypted in principle is understood as a very long number itself which will be raised to the power of e, the recipient's public key, and the modulus n will then be subtracted from the result until it gets smaller than n. This remainder (mod n) is the cryptogram or the encrypted message ready to be sent to the recipient. The recipient himself applies the same procedure to the cryptogram to decrypt it. Again the encrypted message is understood as a very long number being raised to the power of d, the secret key, which miraculously yields the original message after the remainder has been computed using the modulus n. Just one single number d strictly has to be kept secret whereas the method of computation and both publicly known numbers e and n as well as the cryptogram need not to be made secret and can safely be analyzed by everybody.
But the RSA cryptosystem only works well, if the three numbers fit together
"in an appropriate way". Matching this condition is ensured by the
process of generating a pair of keys which also gives a fine recipe for cracking
the whole cryptosystem.
To generate a pair of keys you have to find two very large primes, p and q, which
make up the modulus as a product (n = p*q). You can derive both interesting numbers,
e and d, which form the actual pair of keys, very quickly from these two primes
being thrown away finally.
An attacker who knows the modulus n, say p*q, only needs to find out which
primes the modulus is composed of, in other words he or she just has to
factor the modulus, after that determinating the secret key is a matter of
seconds. Fortunately the problem of factoring
is a job causing an awful lot of work if numbers are concerned which consist of
several hundred decimal digits, so this is a practically insoluble problem
.
The security of the RSA cryptosystem therefore depends on the fact, that it is practically impossible to factor the large known modulus n. So nobody can infer the two primes p and q from his or her knowledge of the publicly known modulus to gain the secret key.
The Previous History of Factoring
- 70-digit numbers will be factored today (1998) on a workstation within 10 hours.
- 100-digit numbers will be factored on a workstation within 1 year.
- 129-digit numbers :
In August 1977 Martin Gardner asked the readers of Scientific American to factor
114 381 625 757 888 867 669 235 779 967 146 612 010 218 296 721 242 362 562 561 842 935 706 935 245 733 897 830 597 123 563 958 705 058 989 075 147 599 290 026 879 543 541 .
Some 16 years later, in April 1994 the factors were presented by Paul Leyland (University of Oxford), Michael Graff (University of Iowa) and Derek Atkins (MIT). They had been supported by over 600 volunteers running a computerprogram written by K. Lenstra (Bell Labs, Morristown, New Jersey) on their workstations at night sharing the work of factoring over the internet.
- 140-digit numbers are the smallest numbers not having been factored in 1996.
They will be factored within about 5 years using large-scale networking.- 160-digit numbers:
In 1996 experts expect factoring to be possible within about 5 years using a new method of factoring known as number field sieve.- 200-digit numbers:
The time for factoring is estimated at 52 000 000 years in 1998.
Using a minimal key length of 1024 bit corresponding to an RSA-modulus of at least 309 decimal digits, it is guaranteed that RSA can be considered safe for the near future as long as there will be no fundamental advance in the factoring of large numbers. Even today lots of PGP-keys are certified with key lenghts of 2048 bit corresponding to 617 decimal digits.
To protect yourself from these attacks you should avoid to sign a document, which could contain arbitrary hidden data, for instance an unknown word-processor document containing information (on formatting) which is not to be seen in the plain text. Because the chosen-ciphertext-attack is based on the fact, that an attacker is able to smuggle some skilful chosen data into the message, so that an encryption with the secret key turns out to be actually a decryption of the message or at least part of it. But even if the attacker was successful he would not get the secret key itself.
Without any doubt mathematics has made considerable progress within recent years in factoring very large numbers which has been discussed in detail by J. Buchmann in the June-issue of Scientific American 1996. Using advanced computer technology massively, totally different methods of factoring have been developed which essentially differ from conventional methods.
In 1985 W. Lenstra developed a method based on elliptic curves, which made it possible to find factors of 30 decimal digits size within three weeks using current workstation technology. This method is successful even if the number which has to be factored consists of several thousand decimal digits. If the RSA-modulus is composed of a small and a large factor, the small one could be found within an acceptable period of time. So it is essential that two sufficiently large primes of almost the same size are used for RSA-key generation to prevent fast factoring of the modulus.
A different method known as quadratic sieve requires the solution of a system of linear equations consisting of a huge number of linear equations and unknown quantities. Using this method a 120-digit RSA-number was sucessfully faktored in 1993, although 252222 equations with a total of 245810 unknown quantities had to be solved. This work which would have taken almost 50 years using a single workstation could be parallelized, so that it could be done within a much shorter period of time. The method of number field sieves which is based on a similar principle but works much faster than the quadratic sieve was successfully used in 1996 for the factoring of a 130-digit RSA-number.
Considering the progress of factoring over the last ten years one could expect 150-digit numbers to be factored in the near future even if today no known algorithm is able to perform this job within a reasonable amount of time. But it is still possible that a totally new algorithm will be found which would make todays secure RSA-keys absolutely worthless. So it will be essential to observe new developements in the field of factoring and to consider them carefully when evaluating the length of RSA-keys.
Of course it is possible that some other text will accidentally produce the same
hashvalue because even if the number of different hashvalues is very large, it is
also limited. But such a collision could not be constructed intentionally
because you have to try about 10^{38} variations to find one.
The one-way-function does not give any clue for an appropriate choice of the
forgery and the possibility to get the same hashvalue from any two different texts
is only:
0.000 000 000 000 000 000 000 000 000 000 000 000 029 percent
(1/2^{128}).
The Birthday-Attack on MD5
How many people are required to make the possibility for two of them having their birthday on the same day reach 50 percent ?
The wrong answer is: 365/2 = 182 people.Actually you only need 23 people which is far less than expected, and transferred to forging a digital signature, the forger can benefit from this situation considerably. If she does not intend to forge a certain document but rather confines herself to submit a document for signing by the potential victim and she has already found a forged document with the same MD5-fingerprint, forging someone's digital signature is possible, using such a "suitable pair of documents" (benign and malicious document).
The number of pairs of documents she has to check until she will certainly find one working pair is no longer 2^{127} (170 141 183 460 469 231 731 687 303 715 884 105 728), "but merely" 2^{64} (18 446 744 073 709 551 616) that is 10^{19} pairs of documents. Finding a working pair of documents still is "bloody lotta work", but can not be considered as impossible (see my argumentation concerning the brute-force-attack on IDEA-keys).
Proof
With N different documents (benign and malicious all in all) there are N(N-1)/2 pairs. Given that there are K = 2^{128} different hashvalues the probability of two different documents sharing the same hashvalue is 1/K. To be on the safe side one must try at least half of N^{2} pairs of documents, for if the probability for a collision should be 50 percent, 2^{64} pairs of documents will be sufficient.
(N^{2} * 1/K) / 2 = 0,5 Among those 18 446 744 073 709 551 616 different pairs one will probably be suitable for forging a digital signature.
N = sqrt(K) = 2^{64}.
RESULT Using sufficient long keys an attack on cryptographic methods used by PGP is practically pointless. This "theoretical security" has to be evaluated with respect to current results of cryptographic research.
Fortunately most of the everyday tasks can be carried out without any difficulties, because only public keys are used. If you want to check the signatures of your emails you have received you only have to apply the public key of the sender. Even if you send confidential information to other people you have to encrypt them using the public key of the recipient.
But adding such a public key of an unknown person to your keyring, i.e to the file which collects all the public keys is definitely a security-relevant action, because by adding the new public key you definitely recognize that the available public key you often have received from non-reliable sources (i.e. key-servers) is actually identical with the public key as it was initially generated by that person himself. That could be a problem if you don't know that person or if you can only communicate with him or her using an unreliable channel like the internet which frequently happens.
Of course you could add a new public key to your keyring as "untrusted" without applying your secret key but as soon as you want to accept a pubic key as reliable you have to certify it by yourself using the secret key for signing the key.
So how can you judge the reliability of an unknown public key? PGP offers two different ways to solve that problem. You can obtain the FINGERPRINT of the public key through a direct and reliable contact with that person comparing this first hand information with the fingerprint of the public key you have received from unreliable sources. If that confirms the authenticity of the public key you can certify this new key by yourself signing the new key with your secret key while adding it to your keyring.
But if the new public key has already been certified by a certification authority you trust adding this key to your keyring does not require your signature of the key. Although the premise would be that you have signed the public key of the certification authority and you have consented to certify new public keys by the certification authority, which is a security-relevant action itself.
But even if you add a non-certified key to your keyring you only have to confirm the authenticity of the new key once by signing it. During your everyday use of the different people's public key your own secret key will never be used. So security-relevant actions do reduce to signing own documents (as the "crowning finish" of your creative work) and to decrypting messages meant only for your eyes.
Please pay attention to the fact, that whenever such a security-relevant action is carried out, you always have to enter your passphrase!
Because if you aren't requested to enter your passphrase then your passphrase is stored somewhere or not been set anyway, which makes its compromitation drastically easier or there is something foul with your PGP working environment, especially with your binary you are using. As soon as that happens to you once, you should change your passphrase which makes your secret key be encrypted freshly and you should scan the security of your working environment thoroughly (may be with the help of others). With multi-user systems there is the danger of someone getting access to the superuser's password or tampering with the working environment by making use of weaknesses of certain system programs in gaining root permission. So it is usually advisable to inform your system administrator if you observe such a "queer behaviour" of your environment.
If somebody got to know your passphrase he or she just needs to get your secret key (ring) to be able to sign in your name or read your private data. Practically you could try to prevent someone to copy your secret key ring by using file-permissions provided by the operating system. Although with a suitable networking environment, one could restrict the access to sensible data it can not be guaranteed that the encrypted secret key ring will not fall into the hands of other people, i.e as a result of burglary. Of course during normal operation there is a fundamental difference between a responsibly administered multiuser system and an utterly unprotected desktop PC. But because of the fact, that in the worst case the theft of your secret key ring is to be expected the quality of your passphrase is essential which protects your secret key from being (mis)used.
Some texteditors create temporary files on their own, which hold a copy of the text during editing. After finishing those "tempfiles" will usually only be deleted not "wiped", leaving sensitive data undestroyed on the medium.
Also your passphrase is at risk to appear on a storage medium, if your operating system is extending its memory by "swapping" . While UNIX does separate this swap-space from the rest of the filesystem, so that someone has to gain root access to analyse it, MS-WINDOWS directly stores parts of the memory to disk. Therefore with some luck everyone who has access to your harddisk could find your passphrase or parts of confidential information in the swapfile in plain text. Especially in a networking environment a swapfile is a serious danger to your passphrase. It definitely would be the least to avoid swapping while using WINDOWS or at least to wipe the swapfile before turning off your computer, because deleting does not destroy the contents of your swapfile.
UNIX restricts the ability to examine any blocks of data to the person of the system administrator. In principle he or she also has access to the memory (/dev/kmem) and can search for your passphrase in the memory during the execution of your PGP-process. Do not hesitate to speak to your system administrator about this problem. A responsible system administrator will put himself to a lot of trouble to prevent others from using the superuser's password and he or she will be able to assure you that your passphrase will not be at risk by root access. At this point the security of your secret key depends on the ethos and professionality of another person who is responsible for the UNIX system.
But without any big effort
"key-logging utilities" or
"key-press snooping tools" can be installed in operating systems without access control (DOS/WINDOWS) which will detect every key pressed, storing them somewhere
or sending them over the network.
Those keyloggers replace some parts of the operating system, which control the
keyboard input by tampered code thus leading to an alteration of the operating
system. With computers runnig DOS or WINDOWS everybody will be able to install
keyloggers without any difficulties, if he or she has access to your harddisk.
But such an alteration could be done by a boot virus as well.
To get an efficient protection against these alterations of the operating system
it is necessary to check the intactness of the corresponding routines of the
operating system regularly before you use PGP. This could be done by generating
MD5-fingerprints of relevant parts of the operating system comparing them with
the actual software-fingerprints (may be automatically) to ensure a change of
the operating system not to remain undetected.
Using UNIX "key-logging" requires access to the corresponding device files (terminals) which normally is not permitted to other people. An alteration of the input routines of the operating system is possible only with root access. But the X Window Sytem (X11R6) which is the graphical user interface for UNIX features a conceptual design error, which could be exploited for "key-press-snooping" without root access. You will find comprehensive information about this in Rune Braathen's Crash Course in X Windows Security. You should always avoid to enter your passphrase during a X Window session and you should switch to the character based console if possible. But if you cannot do so, you could restrict access to your X server to your localhost using the UNIX command "xhost -", so you could only be threatened by users who have already logged into your local computer.
Some PGP-shells have been developed for WINDOWS which comfortably save users the trouble of using PGP with its commandline options. Instead the processes of decryption, signing and key management have been hidden behind some "fancy buttons and checkboxes". Clearly there is a danger that entering your passphrase within a shell will cause undesirable side effects, especially if the PGP-shell is distributed as pure binary without a publication of the source code.
Following the support of JAVA, JAVA-script and ACTIVE-X by the new generation of
web browsers
a severe lack of security has become known, because unauthorized access to
private local data over the network has been permitted due to the implementation of
these new features. The concerted action of the software industry to deliver
"brand-new features" in a premature and imperfect condition will
certainly damage the security of the browsers in their further development -
particularly, if you take into account the rivalry between Microsoft and Netscape.
The demand for comfort and user-friendliness, lots of users call for, causes
suspicion of an increase of security-relevant attacks using applets
and "hostile webpages" in future. Even today some
websites
intend to cause destructive effects based on JAVA-applets. So in future
those pages could also be dedicated to the purpose of hidden information gathering.
You can face these dangers best, if you do not use your system for PGP and as a
platform for testing web browsers simultaneously.
Because of the fact that you should never forget your passphrase, otherwise your secret key is useless, solutions have to be found that will work safe. At this point two different strategies can be offered to guarantee the memory ot the passphrase, both leading to a loss of security.
Both strategies do raise the question what length will be required to make a passphrase still secure. My argument concerning the efficiency of a future computersystem has shown, that it will be sufficient to ensure, that the work for "systematic guessing" the passphrase will reach about 10^{22} operations. If you choose your passphrase in a way that in principle there are 10^{22} possible passphrases, you certainly are on the safe side. To cause this amount of work 72 bits or 9 Bytes will be sufficient, because this will leave 2^{72} or 4,7 * 10^{21} variations.
The number of characters could be reduced further by using more than those 16
hexadecimal characters (0-9A-F). Using not only all lower and upper case letters
but also every special character you can enter through the keyboard resulting in
some 70 different sysmbols, 12 of those randomly chosen characters
will be sufficient to cause the required work
(70^{12} = 1,4 * 10^{22}).
Then may be your passphrase would be e8ZWr!ySFt?m.
By using the <SHIFT>, <CTRL> and <ALT>-keys and the combination
<CTRL><ALT> as well you can easily increase the number of different
characters to 160, which results in an unbeatable 10-character
passphrase like
G<ALT>)a<CTRL>#Hs<CTRL><ALT>e.3<ALT>wY
.
So the gain you have achieved using the meta keys is rather modest and you simply cannot construct a secure passphrase with less than 10 characters!
A dictionary contains may be 60000 different items, so an arbitrary choice of five different items would again produce plenty of combinations (60000^{5} = 7,7 * 10^{23}). But your secure passphrase salmagundi_latrine_warning_gowk_marathon now has a lenght of 36 characters, a price you have to pay for the fact, that you only need to remember the order of the five different words, which all have meaning now.
One single word chosen from a dictionary is clearly useless as a passphrase. R. T. Williams describes the attempt of testing PGP-passphrases using lowtech computer technology (PC-486 and PGP-2.6.2). Performing at least two keytests per second one easily covers 172800 words a day, so every dictionary will be searched exhaustively within a short period of time.
If you still want to use a single word as a passphrese, it is advisable to choose a random-looking word, which has no meaning for anyone except you. Twcae,pwcab. would be no poor candidate for my passphrase, if nobody could get the idea that it reflects the quotation of I. Kant "Thoughts without content are empty, perceptions without concepts are blind". But those who know that I am busy with philosophy professionally might get this idea, so this passphrase is totally useless for me. But if you can invent such an "abbreviation", nobody who knows you would possibly assume, this would be a good passphrase given an appropriate length and spending plenty of <CTRL><ALT>.
RESULT The PROTECTION of your PASSPHRASE is the crucial factor which determines the security of PGP. The trouble you are taking to choose a good passphrase and to make your working environment secure but also your consciousness of the various possibilities of practical attacks on the use of PGP builds the basis of your security and the basis of the trust of others in the value of cryptographic applications like PGP as well.
Fortunately PGP-5.x is backward-compatible, so RSA-keys which have been generated with PGP-2.6.x are still valid and all signed documents can be checked and all encrypted messages can be decrypted without limitation. All three methods RSA, IDEA and MD5 can still be used in PGP-5.x. Additionally PGP-5.x puts a new type of key at the user's disposal (actually two keys, one for signing (DSS) and one for encryption (DH/ElGamal)), which is supposed to make the latest advances in cryptography available to the user. In the new version PGP-5.x the Secure Hash Algorithm (SHA-1) with 160 bits replaces the old 128-bit hashfunction MD5. Digital signatures will be generated using the Digital Signature Algorithm (DSA) with a maximum "key-length" of 1024 bit instead of the RSA cryptosystem. And asymmetric encryption, which was previously done by RSA, will be performed by a variation of the ElGamal public key algorithm (Diffie/Hellman variation) which uses keys of maximal 4096 bits for encryption. For symmetric encryption in addition to IDEA PGP-5.x offers a variety of algorithms including CAST (128 bit) and triple-DES (168 bit).
This raises the question how high the security of the new methods especially DSA and ElGamal/Diffie-Hellman has to be valued compared to MD5 and RSA. Which problem is to be solved by a potential datafiend - analogous to the problem of factoring with RSA - to gain the secret key ?
Both the Digital Signature Algorithm and the ElGamal algorithm use the following
relation between the secret key X and the public key Y :
The DSS (Digital Signature Standard) restricts the size of the prime P to 1024 bits, which appears as a minor restriction compared to the RSA algorithm which commonly uses 1024-2048 bits. But it's more important for the datafiend, that this standard restricts the secret key to 160 bits as well. Therefore it is enough to check a relevant part of the numbers between 0 and 2^{160} to find the secret key, while the size of the prime does only increase the time for calculation of one single test but does not increase the amount of possible secret keys.
The range of numbers for secret keys is still very large, but it would be a misunderstanding to confuse the size of the secret key (which is always 160 bit) with the size of the DSS-key (that is the length of the used prime). Additionally the range of possible secret keys might be restricted more, if an analysis of the random number generator, which produces the secret keys, will give further hints. Whether or not the range of secret keys is also restricted to some extend with the ElGamal algorithm would be a worthwhile study beeing quite releant for the valuation of the security of the new method.
It would be wrong to misunderstand this mechanism as a "comfortable replacement" for encryption to groups, which already exists. Because while using the facility to send a confidential message to different individuals simultaneously is based on a voluntary decision of the sender, the inscription of a second key into the user's key certificate will surely be equivalent to abolishing his privacy in computer networks. As much as this mechanism would be in accordance with the organisational needs of trade and industry, this compulsatorily deposition of a copy of every confidential message at a central supervisory authority does clearly contradict an efficient protection of the user's privacy and personality - and most important, it contradicts the original intention of the project Pretty Good Privacy .
The obvious dangers which raise from the abolition of the user's self-responsibility by this forced mechanism of supervision will come in effect, if the new key format is introduced under the cloak of "cryptographic innovation" and will then be sanctioned as a legal format within the scope of legal endevours towards regulation of cryptography. The legitimate interest in message recovery could be satisfied by "encryption to groups" on the basis of self-responsibility of the user as well, without forcing every possible sender of a confidential message to deposit a readable copy of the message at a central authority by using the supervision-key. If the responsibility for the sensitive use of cryptographic methods shall be exercised by self-responsible individuals in future, it is essential not only to use the old key format without CAF (PGP-2.6.x) but also to warn of the threatening dangers of those new features to prevent their creeping adoption without open discussion. One could hope, that the efforts of developing an open standard for PGP (OpenPGP) will result in a clear exclusion of the possibility to link a user's public key with any other key.