Passphrase FAQ: Passphrase attackers

We can assume that a 1 million key per second key cracker is possible. A Pentium executes about 1 instruction per clock cycle with pipelining (see Nick Stam, Inside the Chips. PC Magazine Feb. 21, 1995, pp. 190-199). Using a 200Mhz Pentium and minimal instructions shows us that a small program will run 1 million times per second. The Cyrix 6x86 is faster for an identical clock speed and RISC chips are even faster. This means that without stretching current technology much, we can program a desk top computer and try 1E6 * 60 * 60 * 24 * 365.25 = 3.15576E13 keys per year. A key of random words must be log(3.16E13) / log(74,000) = 2.77 or 3 words to last longer than an average of 6 months. The random 3 word key has all keys searched in about 1 year. In the end, what we are really trying to do is stop a dumb computer attack. The smarter the computer gets, the slower the computer gets. We can always build custom hardware and just use the computer as a monitor or controller.

In an experiment on a 486DX2-66 w/128k cache, a RAM drive was set up, Smartdrv, an unmodified copy of MIT PGP262, and all other files needed were loaded. RAM shadows were enabled, video and BIOS cacheable and any other setting that made it all run faster. A program was written in QBASIC (it comes with DOS 5 and 6.x) to try a passphrase using the passphrase environment variable to send new passphrases to PGP and check exit error codes. PGP was executed with +batchmode.

Using this method, it is possible to try almost two passphrases every second (1.8125 actually). PGP has beeps and delays when errors are detected, but were minimized by some of the settings used. In order to seriously attack a passphrase, you would need to modify PGP to eliminate the delays and speed it up.

The moral is anyone can get a single random word from a small dictionary in about an hour. Most larger dictionaries can be searched in less than a day. Just about anyone has all the tools needed for this attack. The program and the settings needed to do the work are simple enough for any decent high school hacker.

PGP, as well as several other encryption programs, uses IDEA as the conventional cipher. The key for IDEA is 128 bits. We can calculate the brute force key space with 2¹²⁸ = 3.4E38. A special hardware based key cracker for IDEA that can try one billion (1E9) keys per second will take 1.08E22 years to go through all possible keys. You can expect to get most keys in about half that time which will take 5.39E21 years. It is estimated that the sun will go nova in 1E9 years. Since the algorithm is secure, the cryptanalyst has to go after other things like RSA or your passphrase. It is currently beyond our technology to crack an IDEA key by brute force.

Factoring is an easier problem than brute force search of the key space. The only current practical factoring methods for RSA size numbers are the Multiple Polynomial Quadratic Sieve (MPQS) and it's variations, and the Number Field Sieve (NFS). Estimates for the MPQS run around 3.7E9 years for a 200 digit/664 bit number. I should include that no one knows how long it will take to factor numbers larger than about 130 digits (429 bits) except for some special cases. Some net references on numbers that have been factored are RSA129 and The 384 Bit Blacknet Key. You should note that it took a lot less time and computing power to factor a 116 digit (384 bit) key than it took to factor a 129 digit/426 bit key. The NFS factored RSA130 a 130 digit (430 bit) key even faster than RSA129 was factored. RSA is probably the weakest link in PGP, but currently no one knows a good way to factor numbers over 155 digits/512 bits without building special hardware.

Why would anyone want your passphrase? For almost all of us, no one is really interested in what we encrypt. The worst "enemy" we might normally face is a family member that is poking around where they don't belong or maybe the system administrator where your internet account is. Most family members these days probably wouldn't know where to begin attacking a passphrase and even 256 bit RSA would be safe from the computer illiterate crowd. For the really paranoid or fringes of society, the FBI or other major law enforcement agency might be looking. Everyone who knows what they are doing will try to get the passphrase without trying a brute force attack.

If you are investigated by a law enforcement agency, then this is what you might get from the various sources. All your communications would be monitored. When they think they have enough information, the law enforcement agency will hand you a search warrant and they will go away with your computer and disks and probably a lot of other stuff as evidence. They will probably already have copies of plaintext traffic from and to you.

While they are at it, they will probably take you in for questions. Once they have your computer, they will make copies and search the hard drive. If any or all of it is encrypted, they will try to decrypt it including any deleted files that might remain on the hard drive. If your passphrase is anywhere on the hard drive then they have the key to all of the files encrypted to you. Law enforcement has their own computer experts and can call in professionals as needed. Your individual experiences may vary depending on what country you are in.

You can't trust Windows 3.x, Windows 95, OS/2, and any other operating system that swaps memory to the hard drive or that uses virtual memory. For Mac users, the RAM disk may be saved to the hard drive automatically. Several windows users have found their passphrase in the swap file. It should be safe to run PGP in a DOS shell from Windows as long as Windows is inactive or in other words, no DOS windows. Windows programs that shell to DOS seem to directly write the passphrase into the swap file.

There are several programs that will search the entire surface of a disk with little more than point and click. See the section Wiping swap files for more information.

It is also pretty trivial to write a simple program that searches a file for text strings. More serious attacks and deleted files may require one of the many services that recover data from an unreadable disk. The main problem with multitasking systems is one of control. You simply can't effectively control what happens with the things in memory.

On the bigger multi-user systems, it is trivial for anyone with enough access to install snooping programs, make copies of files, and in some cases even directly monitor a user. You can also include networked PCs. On a network, you can control things remotely with the right software. Some network software may even come with programs that allow limited snooping. Using the computer at work could be handing your passphrase to a variety of people. Many people try to get around this problem by using a separate key on the multi-user system and a secure home key.

It is pretty well known that the electronic noise from computers can be monitored and even used. Every wire acts as an antenna radiating any signals that might be on it. These signals can be captured, decoded and displayed. This is called TEMPEST.

The tricky part could be finding the one computer among several identical computers. If there is only one computer, then the spy's job is pretty easy. In some cases, it is much easier to shield a room than to buy specially shielded equipment. The hardest part may be identifying the leaks and plugging them. Every wire into a room could carry a signal out of the room no matter how well the shielding is constructed.

You would have to be pretty important to a major government or corporation before you need to worry about a TEMPEST attack. Some tests with some really basic equipment showed that quite a bit of noise came from a monitor, very little noise was around a steel cased computer, and the keyboard allowed some noise. All cables used during the testing appeared to be shielded and the computer was idle with a variety of data shown on the screen. The detection equipment wasn't very sensitive so there may be more noise than was actually detected.

The best way is probably a key splitting technique. You need to distribute pieces of a passphrase that protects all your regular passphrases. There is a number of ways to do this that will safeguard your keys even if you lose a few friends. A simple method would be to break up the key passphrase into 3 pieces. Then give the pieces to 6 different friends. Do the same thing with your actual passphrase file.

To reconstruct your passphrase you need only 3 of your friends and you have backups. The individual friends can't reconstruct your passphrase and they can't assemble the pieces unless all 3 of them cooperate. The security of this method improves if you use more people, but the most important part is having copies of your keys distributed in a way that you can recover them and no one else can. You should have at least one copy of PGP and your keys some place other than your house. Remember to limit your risks.

I'll contradict myself now. For total security, you shouldn't write your passphrase down anywhere in any form, ever. Storing a passphrase anywhere, even split among friends who each keep a part, isn't perfectly safe.

Writing your passphrase is a breach of security if care is not taken. Many ordinary disposal methods hand your written passphrase to anyone looking. A simple technique with an ordinary pencil will grab a passphrase from a pad of paper after the top sheet where the actual writing took place is removed. Throwing the copy of your passphrase in the trash gives your passphrase to the dumpster divers. Even trash from your house can be searched without much trouble. A wallet isn't a good place if you get hurt or your wallet gets stolen. There are many other problems with things that are written down.