| Home | Free books | Who we are | Contact us | Sitemap |

How electronic encryption works

A survey on secure email and private electronic data


WITH STRONG encryption, you can safely send private email or keep confidential things on your laptop without worrying about it getting stolen. But you need to know what you are doing.

I wrote this survey after I'd spent a couple of years helping corporate clients set up secure email systems. Secure email was convenient for us both. Neither of us had to retype anything (compared to the hassles of faxes). And I didn't have to worry about information going to the wrong person by mistake (which happens with faxes).

What qualifies me to write on this complex topic? The same thing that might qualify anyone: I have looked into it in detail, stay alert for changes, and I am prepared to be corrected. (And note the small print that comes later). I also have a degree in mathematics, and this is a mathematical subject -- it is in part, though much about the business use of cryptography is a kind of cultivated common sense. If you're not mathematical, the common-sense side of what I have gathered together here should help. It's common sense I have picked up from those in the know, and it is the bigger part of getting all this right.

by Jim Heath

Cryptography in business?
How Internet email works
Security risks with email
Encrypted email can be completely secure
Why encrypted email is better than faxes
Down to details: how electronic encryption works
RSA + IDEA = PGP
Possible attacks on PGP
Security procedures needed with PGP
Other email encryption systems
Encryption laws in a few countries
Paranoia may be wise these days
After all that: what encryption system should you use?
Secure website forms

11 Feb 2013: Things have moved on since I wrote this, with new apps that take all the trouble out of secure electronic communication. Phil Zimmermann, originator of PGP, was one of the capable hands at work. But I will leave the following long article, for whatever historical or educational use it may have.


© 1997-2005 Viacorp. All rights reserved.


Before we start...

  1. This document is copyright, but you can make any 'fair use' of it under copyright law. That of course doesn't include poor-attitude things like re-publishing the work (or parts of it) and claiming it's yours, or copying it to another website or mirroring it, or putting parts of it in some other document or website and implying you wrote those parts, or using any of it in a publication that you sell. You get the idea.

  2. This survey was published in April 1997 and updated many times. If you live in Australia and you're interested, there are copies of the original edition in the public library systems there.

  3. One person emailed me to say that 'organisation' and such words are spelled with a z, not s. Ah, but not in the UK or in this great country where we have the kangarooz.

  4. Small print: It would not be prudent for me to give guarantees about the information and advice in this document. The content itself makes it plain why. So the information and advice is offered without any responsibility or liability on any account whatsoever on the part of the author or copyright holder.

  5. What about 9/11? I can't see any reason to change anything, or take anything down. All this material is well-known, published in books, and it's everywhere... if somewhat scattered. If terrorists use the main method discussed here (PGP), they would stand out like someone pulling on a black balaclava and walking through an airport. And bring down traffic analysis on all their communications.. the kind of chatter index that the White House talks about. The same for the other crypto systems. Except steganography, which has been much discussed on the net already -- as a possible sweet system for terrorists -- but I don't do much more than define what it is. Meanwhile, there's the whole other side: how can businesses (chemical companies, for example), protect their own communications against terrorist snooping? Except for good encryption, how? I haven't heard any answer.


3 Oct 2003
Perth, Australia




Cryptography in business?

There are so few who can carry a letter of any substance without lightening the weight by perusal.

-- Cicero to Atticus, 61 BC

Some businesses began using strong cryptography about twenty years ago. They seemed to do it in the half-instinctive way they used office safes and armoured-car services. Banks used DES (the US Data Encryption Standard) to secure the electronic transfers between branches, and later in ATMs. And any business with a computer had some kind of password system, either to control access to the computer or to certain disk files. It was just done. No one made much fuss about it.

Little by little, things changed. Very strong cryptography left the shadows of national security organisations and started to look like an essential business tool -- not least for exercising a 'duty of care' for information in stored electronic files or sent over electronic networks.

Business use of encryption will keep growing. There are four main reasons:

1. Computers have changed greatly. Twenty-five years ago most computers were centralised, in locked rooms and were looked after by people with arcane vocabularies. An electronic link to the outside was unusual. And if there was a link, it was along a dedicated line. Security threats in those days were mostly from insiders: people abusing their accounts, theft of data and sometimes vandalism. These threats were managed by keeping the computers behind locked doors and accounting scrupulously for resources.

Today computers are here, there and everywhere, including people's private offices. Most computers are now connected into networks. So central management isn't feasible and security is harder to manage. Much harder.

2. Messages and electronic files now move along insecure networks, not just along dedicated lines. There is no security on the Internet. And even an internal LAN can be broken into if there's just one insecure dial-in modem.

3. Faxes have proved hard to manage for sending confidential material. It is difficult to maintain a 'need to know' system when anyone walking by a fax machine can glance at what comes in. Also, faxes are sometimes sent to the wrong number. And fax interception is now technically simple -- even broadband fax interception from satellite or microwave links. Some fax systems are now sold that encrypt the transmission, but they can leave a manager hovering near the fax machine and waiting for an incoming call -- because the message still comes out in plain view. A smarter system is proving to be point-to-point encryption for email.

4. A new sort of encryption system was born in 1977 -- the RSA public-key system. It elegantly gets around one of the main problems of the old-style encryption systems: how to get a copy of the encryption 'key' to the person you want to communicate with. With the RSA system, there are two keys (very large integers). The 'public key' can be sent down an insecure network. It can only be used to encrypt a message. Once encrypted, only the person whose PC holds the complementary 'private key' can decrypt the message.

For all these reasons, encryption is spreading fast in business. The US Chamber of Commerce surveyed 1600 US business users and found that 17% of companies used encryption for confidentiality in 1995. They expect this figure to rise to 60% by the year 2000.

The 1996 Ernst & Young and Information Week annual security survey of 1300 information security managers found that 26% used file encryption, 17% telecommunications encryption, and 6% public-key cryptography.

In December 1996, Trusted Information Systems of Glenwood, Maryland, listed 1393 encryption products created and distributed by 862 companies in at least 68 countries. About 60% were from the US. Almost half of the products used DES, the old standard. At their annual conference in January 1997, RSA Data Security said they expected the number of RSA public-key encryption systems to exceed 100 million in the first quarter of 1997.

I have no figures for Australia. But I suspect it isn't right to assume that Australia is more or less keeping pace with the US. Australians may love certain kinds of technology, but there is a problem: America restricts export of strong encryption products, and these restrictions apply to Australia. Exceptions are made, but special US licenses have to be applied for. This means it usually isn't possible to buy off-the-shelf US encryption products that are anything like as secure as those used regularly in the US. And when it is possible, it isn't always easy. This means that many Australian companies that might want strong encryption would have to use encryption products from outside the US (no serious disadvantage, as I will explain later).

Note, June 1999: There's been a lot of change in two years. Strong encryption products are made almost everywhere now. One way they compete against US products is to stress that US export versions are deliberately weakened. This report appeared on 10 June 1999: Growing Development of Foreign Encryption Products in the Face of U.S. Export Regulations, by the Cyberspace Policy Institute at George Washington University. It lists countries and a summary of their encryption products. Be prepared to blink. There are lots of products.

Managers may first think all this is a matter for their IT departments. Not quite. Cryptography is a black art to many IT people (witnessed by some of the easily breakable encryption systems that have been innocently built into commercial software). This innocence wouldn't surprise cryptographers: they know how strangely difficult it is to scramble data so that no statistical hooks are left that can be used to haul out the message. Which leads to questions about which products are secure, how you can tell (or find out), and exactly what's on offer in this mysterious but beguiling field.

A light seems to go on for managers when they find out there is a way to send a file or message to someone without having to worry at all about other people intercepting or reading it -- even if the message goes wildly astray.


How Internet email works

I will start slowly. This gets complicated pretty fast.

First, most business people have heard that the Internet is insecure, not to say perilous. This applies to Internet email -- a swift, convenient, and friendly looking system. Maybe too friendly looking, considering the dangers.

An email 'address' typically looks like gsmith@ibm.com, or swithers@complex.is, or sugar8@pepsi.com. The general form is somebody@IPaddress.

'Somebody' identifies the person the email is for. In an organisation, the identifier is usually the person's first initial and last name, jammed together. 'gsmith' for George Smith. It is customary to write it all in lowercase (although email addresses aren't case-sensitive).

The IP (Internet Protocol) address is a 32 bit number that identifies the network the email is going to, as well as a definite computer in that network. Nobody would want to type in long numbers as email addresses, so there's a built-in Internet translation system that lets numerical IP addresses be written in mnemonic form as alphabetic characters. Something called the Domain Name Service associates the mnemonic names for networks with the 32-bit IP addresses that the computers on the Internet actually use.

Once an email is 'sent', it is launched down a complex -- in fact unpredictable -- path to the recipient. It goes from one computer to another, down a route that's determined on the fly by network traffic and the decisions of 'routers' along the way (sort of traffic-control computers).

The computers connected to the Internet work according to a set of communication protocols that you usually see shortened to 'TCP/IP' (Transfer Control Protocol/ Internet Protocol). But there are many other Internet protocols at work besides just those two. One of the other protocols is the Simple Mail Transfer Protocol (SMTP). A UNIX program called Sendmail is active on each Internet computer that takes on the email-delivery job. A lot of Sendmail's work amounts to taking email from the In basket and putting it in the Out basket. The email arrives at a computer, and Sendmail just redirects it to the next computer. An email can make a lot of hops. And the path can be surprising: an email going from Perth to Melbourne in Australia might include a hop in Singapore or Los Angeles.

At the end of the line, when the email gets to its destination, another program usually takes over. The Post Office Protocol (POP) saves the email for delivery to the recipient -- when the person next logs in, or right away if the person's PC is connected at the time.

The Internet email system is fault-tolerant and reliable. And it doesn't matter what kind of computer is used at the sending or receiving end. Messages can be sent between Macs, PCs, UNIX machines, and mainframes. Most messages arrive in a couple of hours, often in seconds, even from around the world.


Security risks with email

Ordinary mail that goes in an envelope can be tampered with. It sometimes happens. But there's no feasible way to scan the contents of all the letters that move through the postal system every day. But with email, there is a way. And certain people and organisations are tempted to do it.

I mentioned that email usually passes through several computers on its way to the recipient. There is no technical obstacle to stop the people who administer those computers from automatically scanning all the email that passes through their machines. Software can search for keywords, for certain people's names, or for email addresses. The 'interesting' emails can automatically be copied and then looked at later. The people sending and receiving the email wouldn't know it was happening.

A similar thing can be done by hackers. They can plant passive software (a 'sniffer') in the path of all email going through a computer. Then receive copies of all the email the sniffer selects: maybe the ones with credit-card numbers, certain people's names and words like 'password'.

Some hackers do this as a kind of sport. ("Fourteen-year-old hacker caught stealing credit-card numbers.") Others have a less sporting interest: rich criminals with hired technical help, industrial spies, or governments. This goes on day and night, and will continue.

Email interception is one danger. There are also email scams. People get forged messages. It is easy to fake the sender's name and address in an ordinary email. If the person getting the faked email is taken in by it, it may turn out to be expensive or embarrassing.


Encrypted email can be completely secure

John wants to send an email message to Herman, his contract manager in Germany. John types the message on his screen (or gets his secretary to type it on hers). When the message is worded the way John wants it, he or his secretary clicks an 'encrypt' option on the mailer software. It verifies the name of the person he wants to encrypt to -- Herman -- from a list of people that John has 'public keys' for. The encryption software then automatically mixes and re-mixes every binary bit of the message with a key, and then mixes that key with every binary bit in Herman's public key. Result: a digital mess that can only be unscrambled by the same software, but using Herman's private key.

In Germany, the scrambled message pops up in Herman's email. He selects the 'decrypt' option on his mailer. The software asks him for his passphrase. He types this in, and that decrypts his private key (a very long number stored on his hard drive, which he doesn't have to remember or even look at). Enormous calculations then take place and Herman's software reverses the mess created by John's software. And John's original message appears on Herman's screen.

But what if John's message were intercepted by Black Hat? It would do Black Hat no good at all. It's hopeless to unscramble the message without Herman's private key, and Black Hat doesn't have that. And Black Hat can't work out Herman's private key by knowing what his public key is. No one can. Which is why the public key can safely be made public.

It is theoretically possible to calculate the private key from the public key, but 'computationally infeasible' (as cryptographers sincerely put it). Even if Black Hat ran the fastest computer on the planet to work on the calculation, his bones would be dust and the planet's continents would be in very different positions, and still the calculation wouldn't be finished. (This isn't exaggerating.)

And there's something else. If John wants to, he can add a 'digital signature' to his message. It's like a mathematical watermark that can be checked by Herman's software. Herman can be sure that the message came from John, not from someone impersonating John. After all, anyone can send Herman an encrypted message using Herman's public key. That's what it is there for. Anyone could say they are John. But only John can digitally sign a message that can be verified by anyone who has John's public key.

The digital signature also proves the message hasn't changed a jot since John signed it. Even one extra blank space anywhere, and Herman's software would tell him: 'bad signature'.

Digital signatures are as secure as the encrypted message itself. They cannot be faked -- not in any 'computationally feasible' time.


Why encrypted email is better than faxes

Two security problems with faxes are obvious:

  • They are sometimes sent to the wrong number by mistake. The correct fax number can be transposed, or simply the wrong number used. And there can also be disturbances in the telephone network that mysteriously connect faxes to the wrong number.

  • A fax can be read by anyone who happens to be near the fax machine. In some offices, the 'need to know' principle reigns. But it's hard to enforce without giving all the key people a personal fax machine. Instead, people resort to phoning the person they want to fax, making sure they will be standing by the fax machine, then sending the fax.

A third security risk is less obvious: interception. A fax line can be bugged and all the faxes read -- incoming and outgoing. Technically it's easy to do. One prominent case was in 1990, when Japanese hackers were caught stealing information from US corporations by intercepting their faxes. And this is getting easier. These days it's no problem to scan satellite or microwave links for fax messages. A bit of home-built equipment can monitor satellite traffic. For someone who can spend more money, there are commercial fax interception units that can monitor up to 150 fax transmissions from a 6,000-line satellite.

The risks from this broadband interception are severe. A company's faxes can be intercepted just because of the route they take through the common carriers -- not because the company is a target for industrial spies or hackers. Satellite signals cross national borders. Faxes can be intercepted in nations with no privacy concerns.

Apart from the security risks with faxes, there's also the inconvenience of having to retype faxed material that's received, or to struggle to scan it -- if your office needs to work on it. (A 70-page contract, with some details to be changed.) Much better if the document arrived by email. Then it can be used direct in a wordprocessor or spreadsheet program. Herman in Germany can load John's revised contract document into his word-processor, make any small changes he needs to after talking to the client, and print out a contract to be signed. Or send it all back to John first, for his approval -- duly encrypted and digitally signed by Herman.


Down to details: how electronic encryption works

The intricacies of relating key variations and working principles to the real strength of the encryption/decryption equipment were, and are, virtually unknown to almost all buyers, and informed decisions as to the right type of on-line, off-line, key-generation, etc., which will meet buyers' security needs, have been most difficult to make.

-- R. M. Davies, National Bureau of Standards Special Publication 500-27, Feb 1978.

This is a large topic. I will only cover things that are useful to know for practical business purposes. That includes some crypto vocabulary.

One of the main points to take in about electronic encryption is there are many 'qualities' of it. The systems range from one sort that's never been broken and never will be, to encryption that looks scrambled and impenetrable to a novice, but can be broken by an expert in seconds -- just with a pen and paper.

One of the hard tasks facing business people -- and their consultants -- is to find out which encryption products are suited for which purposes. Otherwise encryption products may have to be judged on the sales talk, or on the prestige of a company name. Unfortunately, some sincere sales people can be selling a weak encryption product. And some very large companies have sold encryption products that have been embarrassingly easy to break into.

Encryption software isn't like ordinary software: if there's a small flaw in ordinary software, it may only mean that in certain cases a spell checker doesn't catch a mistake, or the keyboard locks up in some rare circumstances. With encryption software, a small flaw can let experts -- benign or malicious -- walk right in. And the intrusion probably won't be noticed until a lot of damage is done.

It may be reassuring to start by saying a bit about the unbreakable sort of encryption: the one-time pad. Russian spies in the Cold War used such a system. Messages intercepted by the US were unbreakable, they still are unbreakable and always will be. Each message was encrypted with a random 'key' as long as the message, and decrypted with the same random key. It's like bombing the message with random numbers. If the person receiving the bombed-out message has a copy of the random numbers that were used, it is easy to work out the original message. Without the random numbers, impossible.

There are both paper and electronic versions of one-time pads. It is said to be used in communicating with nuclear subs, and for some embassy communications. It was apparently used in securing the hot line (remember that?) between Washington and Moscow. It is completely secure, but needs alert management. The random numbers have to be shared between sender and receiver. And once a run of random numbers has been used, it must never be used again. To do this right, both sender and receiver destroy the random numbers they've used (burn them, if they're on a pad, or erase them if they're on disk). The key is gone -- for good.


11 Dec 97. I'll add something that may strike you as bizarre, or useful, or both: if someone had a gun to your head and demanded the key for a one-time-pad message you'd sent, you could give them a prepared 'key' that produced any message you wished. The prepared key would unscramble the message and produce -- let's say -- text from the Bill of Rights. Only the right key, which you don't reveal, would unlock the message that had your disturbing lab report or whatever. Some captured Israeli spies were known to have used that dodge: they produced a 'key' with a great show of reluctance, but it revealed a message that was only mildly incriminating. Shrug.

From the unbreakable, we have encryption systems that range all the way down to the weak password systems in most word-processors and common office-suite software. They are typically written by software people with little knowledge of cryptography, judging from the results. There's even a company that makes a business selling software that will break into these weak systems (for the legitimate purpose of recovering lost passwords -- but anyone can buy the software). You can download their demo software from http://www.accessdata.com/. The demo will break ten-character passwords for Microsoft Word, Excel, and Money, as well as for WordPerfect, Lotus 123, and Novell Netware. For $190 you can buy software from them that will break passwords of any length.

To rely on such weak encryption is to hope that if a hacker gets into your system, or your laptop is stolen, that the thief is an ignoramus.

Security through obscurity: a poor system

Before getting to the encryption, I'd better say something about another area of misplaced confidence. It's relying on obscurity to protect information. This is sometimes used in 'protecting' electronic files.

What Security Through Obscurity means is that a system is thought secure if nobody outside a select group can find out anything about how it works. Examples are hiding account passwords in binary files and trusting that nobody will find them.

The group of people who know the secret system need to be trusted for as long the system is used. If the secret gets out, that's the end of the security. One person in a bad temper about the company, one person bribed, one person who drinks too much, and the security can vanish.

Security Through Obscurity is on the decline, because the computing world is now full of networks and there are many more users who understand computer programming. Even ordinary users know more details about how a system works. And many users have advanced technical knowledge about their computer's operating system. In their spare moments, they may make shrewd guesses about where things are hidden or how they are 'obscured'.

In contrast, a strong encryption system can afford to stand out in full view. Everything about how the system works can be made public. The security lies in the strength of the system itself and in keeping the 'key' secret. No key, no entry -- no matter how well anyone knows the system itself. It's like publishing the details about a strong lock or safe (which is done sometimes). The bad guys will find out anyway, and publishing the information shows confidence. No matter how much anyone knows, it won't help them unless they have a key.

In abstract talk, the difference is between a system that is algorithmically secure (Kerberos, for example, if you've heard of that one), rather than just philosophically secure ("no one would ever look here").

Symmetric key cryptography

Much is said about 'keys' in cryptography. Let's look at one:

01101011100110011101010100111000111000100100010010101001

That's a 56-bit key. A long binary number, agreeable to computers and very uncongenial to humans -- so encryption systems are organised so that people never have to deal with the keys. They only have to deal with passwords (or "passphrases" when they get long, messy and secure). The software takes care of handling the keys and the calculations.

In a symmetric-key encryption system, two people first agree on a pass phase. Maybe by phone or fax. If they know what they're doing, they may pick something like:

ruBRbeQ5mod,**&_ocOEan99[

The encryption software turns that into a binary number. Then uses that number (key) to encrypt all outgoing messages. The mathematical module used for encrypting the message is called the algorithm. The whole system is referred to as a cipher.

At the receiving end, each incoming message is decrypted using the same key. The receiver types in the agreed passphrase, the software converts it to the binary key, and uses that to decrypt the ciphertext (the incoming encrypted message). Out of that comes plaintext -- the original message, in readable form.

So the same key is used to encrypt and decrypt. Hence 'symmetric key'. And these encryption systems are called 'symmetric key ciphers'.

If the encryption software has mathematically strong foundations, these systems are extremely secure. Some of them are so secure that no one has found any way to break them, except to try all possible keys. And if the number of possible keys is enormous, then trying all the keys can be -- yes, 'computationally infeasible'. Later I'll talk about what that means in years.

There are two symmetric ciphers I want to discuss. They are both 'in the open'. Their cipher systems have been published and can be scrutinised by anyone who thinks he (usually a 'he') is clever enough to find a weakness. After a while, when no one has succeeded and claimed a place in the Cryptographic Hall of Fame, everyone begins to be confident that the cipher is resistant to attack.

DES

DES stands for Data Encryption Standard, as I mentioned earlier. It's the first standard cipher the business world had. It is twenty years old and still widely used. But it is aging and getting much less secure. A knowledgable attacker who can afford plenty of expensive computer equipment can now break DES fairly easily. National security organisations can break it in a blink.

What we might call the 'search for DES' started in 1973. The US National Bureau of Standards asked for proposals for a standard cipher. They wanted a cipher that:

  • gave a great deal of security

  • was completely specified and easy to understand

  • depended for its security on its keys, not on the secrecy of the encryption and decryption method

  • would be available to all users

  • was efficient to use

  • was capable of being evaluated for its security

  • would be exportable.

IBM came up with the winner. Their cipher was published by the National Bureau of Standards in 1975. By then it had been checked by anyone who was interested, including the National Security Agency. IBM offered a world-wide, royalty-free license (after a deal with the National Bureau of Standards). The cipher was soon known simply as DES.

In 1981, the American National Standards Institute approved DES as a standard for business use. Banks made much use of it, and it jumped the Pacific and was also written into banking standards for Australia (Australian Standard 2805.5.3). DES was quietly built into all kinds of software applications and hard-wired into much encryption equipment (ATMs for example). As software, it protects computer networks (in Kerberos) and a variant of DES called CRYPT(3) is still used to protect the password file in UNIX systems. Because it was a standard, any system using DES could talk to any other system using it (but they always had to find a secure way to agree on the key to use).

The key length is 56 bits (like the one I showed at the beginning of this section). That's the useful key length: another eight bits is added for error-checking and that doesn't add to the key's strength. The key is churned against the message data to a degree that might amaze anyone who had never seen the detailed workings of DES. When I first looked at the system (years ago, in a Scientific American article), I was sceptical it was possible to undo the encryption and get the message back. Yet the same key, reversed, and put through the same process is all it takes to decrypt the message. (No problem, because the computer does the work.)

No one has published a system for cracking DES, except the brute force method of trying all keys until one works. There is a system called differential cryptanalysis that can theoretically narrow down the number of keys that need to be tried, but the method assumes you have some way of pumping vast numbers of test messages through the DES system you're trying to crack and observing what encrypted messages come out.

A more practical worry is DES's key length. With a 56-bit key, there is a large but definite limit to the number of keys you need to check -- on average 255, which is the same as 3.6x1016. Pick an acceptable time for cracking a key (say two hours) and you know how many keys you have to check per second (5 trillion). That may sound impossible, but isn't. A $10 Application-Specific Integrated Circuits (ASICs) chip can test 200 million keys per second. ASICs need a lot of engineering investment and need to be turned out in quantity to be economical, but well-off commercial or criminal groups could do it, and national security agencies can do it easily. A $10m investment in ASICs will build a DES-cracker that can break a key every six minutes, and a $300m investment can break a key every twelve seconds. (Time estimates from Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security, by Matt Blaze, Whitfield Diffie, Ronald L. Rivest, Bruce Schneier, Tsutomu Shimomura, Eric Thompson, and Michael Wiener, January 1996.)

IDEA

The creators of IDEA -- Xuejia Lai and James Massey -- set out to build a more secure type of DES. In 1990 they called their first try PES (Proposed Encryption Standard). They then fixed some things to make it stronger, added an 'I' for 'improved' and announced the IPES cipher. In 1992 they changed the name to IDEA (International Data Encryption Algorithm). IDEA is now patented in many countries.

IDEA uses a 128-bit key. That's long, and completely secure, if the only way to break in is to keep trying keys until one works. To quote William Crowell, Deputy Director of the US National Security Agency:

You may have heard news accounts of a University of California Berkeley student who recently decrypted a message that was encrypted with a 40-bit key using 250 workstations as part of a contest from RSA Inc.... If that Berkeley student was faced with an RSA-supplied task of brute forcing a single PGP-based (128-bit key) encrypted message with 250 workstations, it would take him an estimated 9 trillion times the age of the universe to decrypt a single message... If all the personal computers in the world -- ~260 million computers -- were put to work on a single PGP-encrypted message, it would still take an estimated 12 million times the age of the universe, on average, to break a single message (assuming that each of those workstations had processing power similar to each of the Berkeley student's workstations).

So the key is certainly long enough.

The IDEA cipher has some similarities to DES in the way it works. It encrypts blocks of 64 bits of the message at a time. It goes through several calculation 'rounds' where it works on mixing the message and the key into a mind-boggling mess. (DES has sixteen rounds and IDEA has eight.) After each round, IDEA shifts the key around and swaps around bits of the 64-bit block.

IDEA is a very strong cipher. It is public and has withstood all attempts to crack it. Bruce Schneier, author of Applied Cryptography, says: "IDEA is based on some impressive theoretical foundations and, although cryptanalysis has made some progress against reduced-round variants, the algorithm still seems strong. In my opinion, it is the best and most secure block algorithm available to the public at this time."

Which means the only method of attack is brute force, by trying all possible keys. Computationally infeasible. In plain talk: hopeless.

Other symmetric systems

DES will have a large room of its own in any cryptographic museum -- even if DES isn't quite history yet. And IDEA is already prominent because it's the symmetric cipher used in PGP.

But I don't want to leave this topic without pointing out that there are many more symmetric ciphers than just DES and IDEA. Some are weak, some strong, some are quick to compute, others are slow -- but there is no shortage. And some have imaginative names. Here's a sampler:

BLOWFISH

CA-1.1

CAST

CRAB

Enigma

FEAL

GOST

Hill

KHAFRE

KHUFU

LOKI

Lucifer

Madryga

MMB

NSEA

PKZIP

Playfair

RC5

REDOC

SAFER

SEAL

Skipjack

SXAL8/MBAL

Vigenere

WAKE

Public key cryptography

Symmetric-key systems like DES and IDEA assume that the people communicating have another way to communicate that is also very secure. Otherwise, how would they agree on what key to use? And that leads to another difficulty: if one key is agreed on -- maybe at a meeting -- and that same key was used for all communication, anyone who managed to get hold of that key could read all intercepted messages.

A better system would be to change the keys regularly -- daily or even more often. There could be a disk-full of keys, and the keys could be changed according to some agreed schedule. The Germans ran their Enigma machines that way during WWII.

But what about setting up secure communications between people who haven't ever met? Maybe they live in different countries. And what if they have only insecure channels of communication? Well, there's way.

In 1976, Whitfield Diffie and Martin Hellman at Stanford University proposed a system called 'public key encryption'. Their idea was translated into a practical method a year later by Leonard Adleman, Ron Rivest and Adi Shamir at the Massachusetts Institute of Technology. The system was soon known as RSA, after the names of the inventors. A user's RSA software first generates a pair of keys. Each is a large integer -- more than 600 digits in some cases. The two keys are related mathematically in a peculiar and useful way: either key can be input into certain mathematical software and used to encrypt a message, and the other key can later be input to the same software to decrypt it. Encrypt with one key, and the other will decrypt.

The software generates the two keys and chooses one as the 'public key'. The owner can give that out freely, even send it over insecure channels like the Internet. All that can be done with it is to encrypt a message. Once a message is encrypted, even the person who encrypted it can't decrypt it.

But can't mathematicians use a person's public key to somehow calculate what the matching private key is? No. If the public key is long enough, it's one of those computationally infeasible tasks. And the public key can be made as long as security requires.

The private key stays on the owner's hard drive. It's protected itself by strong encryption and a long passphrase. People also normally keep one or more copies of their private key offline on floppies (in a safe or whatever).

In practice, RSA isn't used to encrypt messages. RSA is secure and convenient, but heavy on computation. Most messages would take a long time to encrypt and decrypt. Instead, RSA is used as a secure way to send a key for a symmetric cipher like DES or IDEA. Those symmetric keys aren't enormously long, so they don't take long to wrap in what you might picture as an 'RSA security envelope'. What goes down the wire is a message encrypted with a symmetric key, and a copy of the key used (wrapped up in the RSA envelope). At the receiving end, the decryption software first unwraps the RSA envelope, extracts the symmetric key, and uses that key in the symmetric cipher to decrypt the message itself.

This system also means that a different symmetric key can be used for each message. Indeed, that's the way it's done. The software picks the symmetric key at random. So if one intercepted message were broken into (highly unlikely), it would give no information about any other messages that had been intercepted.

A message can be encrypted with several different public keys. That way the Chosen Ones can each decrypt the message, but no one else can. It's useful for sending a message to a distribution list, for example. Also, the person who sends the message often encrypts it with his or her public key (to solve the problem of people encrypting things without saving a copy first, and locking themselves out).

These multiple encryptions are done by creating several RSA envelopes: one RSA envelope for each person who's allowed to read the message. Each envelope contains the symmetric key that was used to encrypt the message itself. The same symmetric key for everyone. The encrypted message then goes down the line along with several RSA envelopes. Each envelope can only be opened by one person: the person who has the right private key to open it. When a person's software opens the RSA envelope, it always finds the same thing: the symmetric key used to encrypt the message. The software uses that to decrypt the message itself.

RSA is almost always used that way: as a secure wrapper to transmit a symmetric key. The symmetric key may be DES, or IDEA or any other. Many commercial encryption systems now use this approach.

Digital signatures

Digital signatures rely on the fact that an RSA message can be encrypted with the private key, then decrypted with the public key.

One simple-minded way for Kevin to digitally sign a message would be to encrypt it with his private key. (An impractical method, but instructive to follow through.) Anyone with Kevin's public key could then decrypt the message. That means everyone, if Kevin's public key is truly public. And decrypting Kevin's message successfully proves it came from Kevin. No one but Kevin could have produced an encrypted file that would work that way.

This isn't a brilliant kind of digital signature. It would be painfully slow, because the whole message would be encrypted and decrypted using RSA. (Unless the message was just: "OK. See you Monday at 9AM.") Also, anyone with Kevin's public key could read the message. Kevin probably doesn't want that.

Instead, he could start by encrypting the message with his private key, as before. But then encrypt that encrypted file with Tanya's public key (say the message is to her, and he wants to prove he sent it). This system would work fine, if everyone was patient enough to wait for the files to encrypt and decrypt. Tanya's software would first decrypt the outer envelope of Kevin's message. It would use Tanya's private key for that. That would reveal another encrypted file, and her software would recognise it could decrypt that with Kevin's public key. When that was done, and a clear message came out, the message must have come from Kevin.

If this was the way digital signatures worked, they wouldn't have much place in digital commerce. Too slow. Instead -- and this is a mouthful -- a cryptographically secure one-way hash function is used to compress the message for the purposes of making the digital signature. Taking that in smaller bites:

  • A mathematical system is used that will scramble and crunch any electronic file down to a fixed number of bits (128 bits is typical, and I'll use that as an example). You can start with a file that has War and Peace on it, or a tiny file that just says "Don't forget the dog food." But you always get a 128-bit sequence, but different for each message.

  • Well, almost always different. There are many more possible messages of all sizes (especially if we call them 'messages' even if they don't make sense) than there are strings of 128-bit digits. So somewhere out there in the universe of possible 'messages', there have to be some pairs of messages that will crunch down to the same 128-bit 'hash.' War and Peace might just possibly have the same 128-bit hash as "Don't forget the dog food." But the chances are very, very slight. So it is sensibly shrugged off. There are 3.4x1038 possible 128-bit numbers. With a well-constructed hash function, the chances of actually being able to exhibit two messages with the same hash are entirely remote. It is a big number, 1038.

  • And there's more: the mathematical hash function can't be worked backwards. If you start with a 128-bit number (choose one at random, say), then there's no feasible way to find any message, even a nonsense one, that will hash to that number. This matters, because if a hash is meant to stand for the message, in a compressed form, then it had better not be possible for Black Hat to cook up his own message that has the same hash. And why? Because then you'd have two messages with the same 'signature.' (You've guessed it: the hash is (almost) the digital signature.)

  • Almost, because there is nothing 'personal' yet about the hash. It's an antiseptic mathematical process. File --> (crunch) --> hash. This hash goes with this electronic file (and with no other file that anyone can find).

  • But what if the hash of a message was encrypted with Kevin's secret key? The hash is a short thing, and easy for RSA to encrypt. No waiting. What if Kevin sent his message and the encrypted hash along with it? What could Tanya make of that? Well, her software could re-calculate the hash of the message that has arrived on her screen. It would be the same hash that Kevin's software had calculated (provided the message hadn't been changed.) Next Tanya's software would decrypt the encrypted hash that came with the message. The fact that the software could decrypt it with Kevin's public key proves it came from Kevin. And the fact that the hash that's revealed matches the hash that Tanya's software just computed proves the message is the same that Kevin sent. All done. QED, you might say.

  • So a digital signature is made like this: File --> (crunch) --> hash --> (encrypt with private key) --> digital signature.

The digital signature can be separate from the file, or tacked on at the bottom. Here's a separated digital signature made by me:

-----BEGIN PGP MESSAGE-----

Version: 2.6.3ia

iQEVAwUBM1HX3frQmI8kGPQBAQGWWAgAmd36+ds4YdVXNfzlK+zvYwcnYoXJ211H
Kc8Vdav5YQ5Gm7qEMdTOyTNns5d8z02oQk4PnnxE8AFBT+UfGAIYLT9g6yjdvLcS
GRcJtneTr73OqJeY0w0SvHOBmBxNnd2bfv9D3jo4WaCIxG4TJGCNP82brVfh+UcD
HWa+PXw8Lxl5w2ChbQMfv4YoVpJvKtSaJnSD/5/ZBtH07Hppz2bfUxY/wcnPSznZ
28/wdD66s97HbUmDN+2c+z/QHpcg2OnZGAF/acdhisFbjEGCpl7jjv1i55rZO0MY
qSnPq+cZsYf2M/R48S4QjBIi5UgdLx9GPmIjlD5AFv29Zap3JO4X5A==
=7gLs

-----END PGP MESSAGE-----

Save that as a file, and run it through the right software, and you'll get a message that says:

File has signature. Public key is required to check signature. Please enter filename of material that signature applies to:

Type in the right filename, and you get a message like this:

Good signature from user "jim heath <jheath@viacorp2.com>"

If you didn't pick the right file, or the text in it didn't match exactly, you would get a message like this:

Bad signature from user "jim heath <jheath@viacorp2.com>"

And contemplate for a second what that means. First, it acknowledges that the signature is one produced by me. It is a signature for something. The fact that it's bad means you picked the wrong file to associate it with, or that the file had changed.

A digital signature can be attached to the bottom of a readable email message, like this:

-----BEGIN PGP SIGNED MESSAGE-----

1 Jan 1997

Perth, Australia

Herman, please do not go ahead with the order for the 4 million
tonnes of alumina. Instead, contact Dr. Smiley and let him know we
will be considering it again at the Board Meeting on 11 Jan and will
let him have our decision then.

Jim Heath

-----BEGIN PGP SIGNATURE-----

Version: 2.6.3ia

Charset: cp850

iQEVAwUBM1HeovrQmI8kGPQBAQHMqgf/atqUN0d4gXLQ5jZ8hsLEkGW1Eb16xdv9
Kg5EhpxEZMV3tvdnNY5JL0E+n/QoEMo9aN/z04YTuwx2zZJCo6Uq4aND8lkzxynh
Yb/yIwAyEnorlfanWXt/MNtO0vwZooiqGgIGTc8SHIyOgGuahH87i7rafz5RAQbz
NqqVJHTWQo/xcMNbQ+uLP9+nWyhnXB562cY5bicOf39rBrtGkeN2dKUxgHNxmR/f
QkHwypohUSLnhlFAi7VgzifqdNjj5Gme35NCUkKRSt8Pnyef7h0LLABXb/XOr/AQ
7D1J4kg4GDOXANp5WdzabT8DJjDCYn3ZFGlmKH9XsbJ71rfMAMCIGg==
=w7lI

-----END PGP SIGNATURE-----

If you saved that message as a file, and tested it with the encryption software, it would tell you: whether the signature was a signature at all, and if it was a signature, whether or not it matched the text above.

Last, the same message can be signed and then encrypted. Then there's no way to tell it's signed -- except by the person it's intended for. The signature is hidden inside the encryption. Such a message looks like this:

-----BEGIN PGP MESSAGE-----

Version: 2.6.3ia

hIwDMRtVGxfOuHUBA/4uSEf1Ae7P88qGkl9Dcr7r6NpcFHzbFYlH4AvA4ai6kzn7
1qzmQfv6xIOJN7dyRf4GkEiE0qYUrvNty+3baIeZQnWxJvvh2DQTKdrUg6Ke0tZP
v5A0y+crAK2rkc00M0X/Ptownlzi6LWktXD4rswvJyc6wrgEtaRlpVZuNygEEIUB
DAP60JiPJBj0AQEH/ijA3QuFFxQmjbGJ7yPhE1ora8gLqS3yyn0E9dq+phtov+jG
nXO2DuNdbKlObegd1OSUsl5TKIHQibYwJ/AqYyWjaDXsaKT64OXjggIkn8LqxqlK
8VWw7acZLWnGgXXWLDwQajti00aQhAtJCo8qO9kwwU4vnEjqeQXAom23TlO0urGt
ftYTMVmbpcYnw40ViY9zKXUx0pmzsDwXQW3v2qO+rXUe+Nxndk2iFfEFh5v1HSLV
Ju4wu+LEAh0zHtZ0Yn454PAOR6S7Nyc/4UGcFtrtTVb4YTPCwatbzQGVupFzxLhx
/a9HIyvQ091wSKHdpDehxJRTgqvg5Qy5cFoHWe2mAAACOuG7IFrRNXDJJOJqGUzM
AriZBaiEp6ME2EaMHiuE2gFAmyTFlXC46Q3LxxYt31qTgQaQf0oLGktMBa8+JqwV
6/0iwwQk7Vvf+a9BNOaBEcV58LY6ES7XSzL6LOMHPRN2P4sANYtfQnqmJyPd/2Wp
0kSNJA/n9kNiDFkVluCh03NaV1oOYD3vb1Yp1AdT2zB7MDTDlsRnK5F6CgiomjL+
XhqzPAxvxfiUYAWEAF1/wnn9XxGo6bDxxQP/7+gxfE+MPsSJkfBJ9nsuUhIqv6Gv
LhcVRcGbnQBxAfMug2pICIULV+0NddeRuftgTzXbJYggSFi0PUSlVZdTM/gaDnxK
YHpPw2bJBCrX3BAPfjPGna2q+r3lQAYH56ck+wl7i6YoPbiaCGcIIjnv3UjEFZ2V
rFWmEWr1cJ+/pkMo7fG+bsMyytIXXTNYYdIMWdQyBXhOyhYBnl8jFCcHMyLyBXnN
gqGu9GgPe6Kww7n12JgshHz5EedLUhb4MFeY0FZyDPeGAOlQQuks0LkYFxM65+Vr
DMs2fbeaRXgv7rd6V/kRopta22JpH284kd0akrLOu7IVIIAU1vLCQ5+QaYCyF4Z5
q/tXkKAVprlxs4l+8k2wMPG/l9zrtPuEKDESurHz9rz7qRuYeScJo4cfcmfKEBrp
VG8s+bJ0RvYbsqWIrvheD4KSqcFtmxO/eTS3AuuC6sRmGeeqwokgIoczcKzOQN3B
zwAFPsCmlPCZpGtgJCICyNQlg/DQn17PISP5tQ==
=/PfY

-----END PGP MESSAGE-----

There's a signature in there, but unless the message has been encrypted for you, you'd never find that out.

What would Black Hat have to do to fake a digital signature from Kevin? He'd have to be able to produce an encrypted hash that would decrypt with Kevin's public key. But Black Hat can't do that. No one but Kevin can do that. Black Hat is stopped before he can start.

What would Black Hat have to do to fake a message that would match a digital signature that Kevin had already made? There's nothing to stop Black Hat from simply lifting a valid digital signature from some document of Kevin's. Black Hat would then have to find some other message that had the same hash as Kevin's real message. It might be tempting, for example, to change a figure in Kevin's message from $1000 to $100,000. But that changed message wouldn't have the same hash. And there's no feasible way Black Hat can find any jumble of text that would give the right hash. Stuck.

Digital signatures can be extremely secure. It depends on the strength of the encryption software and hash function.

Opinion, June 1999: I wrote that a couple of years ago, and digital signatures are now all the rage -- especially with many governments wanting to get into the act. They want to assist in "building the infrastructure of e-commerce." Well, they can try. But there are some problems with masses of people relying on digital signatures. Here's how I put it this month to a mailing list:

************************************
I think govt is panting in the wrong direction.

I used to think digital sigs were wonderful (which they are technically and mathematically). And they are just right for authenticating a webhost -- so your trusty browser can check against its built-in certificate authority public keys and let you know if you're hooking up to the company or organisation that you think you are.

But individual digital sigs are sorry tale, if you ask me -- if you hope to make them universal. Because people would have to take such care with their secret key. Otherwise someone might steal their signature and become them, digitally -- if all this grows into law. But how many people are good with even elementary PC security? What about all those yellow stickies with the passwords? See? No one has to "guard" his ordinary signature.

If you think about where digital authentication might be needed for masses of people, it all starts to fade away. If someone sends your company a fax, do you need a whole fandango to prove who they are? Nope. Because such things mainly arrive in a context (after a phone call, say), or as part of a series of connected communications. Or you just can phone and check. There are other channels and the whole business needs to add up, or you just know: whoa, something isn't right here.

And when you come to signing something important, like Death Warrants and Home Loan Contracts, you'll need to do it the old way, for a long time, methinks.

Digital sigs are just too hard for heaps of hassled people to manage. Not to mention seeming very weird. It's trusting something very alien, and for things that may vitally important. Who would?... Would you?

That's what I've come to think, and I once wrote a paper that praised the power of digital sigs.

******************************

More on that, 18 Nov 2000: Bruce Schneier's CRYPTO-GRAM of Nov 15 2000 includes an article Why digital signatures are not signatures. A snippet: "...numerous laws, state and now federal, have codified digital signatures into law. These laws are a mistake. Digital signatures are not signatures, and they can't fulfill their promise."

Anyway, how secure is RSA?

Someone could break RSA by finding a way to calculate the private key from the public key. The security of RSA rests in the severe mathematical difficulty of doing that.

As far as I know, the only feasible way to calculate the private key is to know the prime factors in the public key. To be accurate, the two prime factors in its 'modulus'. If you know what these prime numbers are, then it's possible for your software to calculate the private key. Indeed, that's what RSA does when it generates a person's private key in the first place. It picks two large prime numbers at random and multiplies those together. That gives the public-key modulus. It then picks an exponent to use with the modulus (this could be getting hard to picture, but the drift here is the main thing). Using the two prime numbers and the exponent just picked, RSA then works out the private key. It is a formidable calculation, but possible.

Without the prime numbers, it is worse than formidable: it can be hopeless. But that nearly hopeless problem is what faces an attacker. The attacker only has the modulus (the prime numbers after they've been multiplied together). He doesn't know the two individual primes. So the attacker's software has no leverage on the mathematical problem of calculating the private key. It runs into a sky-high mathematical wall.

The difficulty of finding the prime numbers in a public key of any given size is known, and the time it would take any given computer to do it can be estimated. Here are estimates from Bruce Schneier's "Applied Cryptography" second edition:

Bits in the public key

Mips-years needed to factor
512
30,000
768
2x108
1024
3x1011
1536
3x1016
2048
3x1020

A million instructions per second for a year = 1 mips-year. And to give the public-key sizes a familiar scale, 2048 bits is about 616 digits.

A 100Mhz Pentium is about a 50mips machine, and a 1800-node Intel Paragon is about 50,000mips. So factoring a 512 bit key would take about 600 years on a Pentium, and about seven months on the Paragon. But even a million Paragons working together would take six years to factor a 1024 bit key, and six billion years to factor a 2048 bit key.

If anyone ever finds a much simpler way to factor large numbers, then the RSA system could be broken. But mathematicians have been working on that problem for a couple of thousand years, and the ones working today in number theory are still frowning.

Much data and communications in the world is protected by RSA. So there's a great deal of interest in RSA's security. If any mathematician had found a way in, it's more than likely the news would be out fast. (Unless the mathematician worked for a national security agency.) RSA has been relentlessly and publicly analysed by cryptography experts -- and experts in this field love to upstage rivals by breaking their ciphers, and making the announcement.

So RSA isn't guaranteed unbreakable, like a one-time pad. But most users take their chances that RSA won't be broken for a long time.

Nevertheless, factoring methods and computers are both getting faster. In 1980, only a 60-digit number could be factored. In 1995, a 129-digit RSA key was factored and in 1996 a 130-digit number. Both numbers were factored by gathering spare computing power from lots of Internet users.

RSA Laboratories recommends that keys be at least 230 digits (more than 768 bits).

RSA is everywhere

RSA is so useful as a secure electronic envelope for small messages (especially the symmetric key used to encrypt a larger message) and as a way of signing messages, that it is part of a lot of hardware and software.

RSA's customers include Apple Computer, Novell, Lotus, and AT&T. They have built RSA into their operating systems, networks, email applications, and electronic commerce systems. The system is also used in smartcards, and in some browsers.

Steganography

Steganography hides messages inside harmless-looking messages. Someone intercepting the harmless message doesn't know there's a secret message in there. There's freely available software that will hide a message inside a digitised photograph, drawing, or digitised sound recording. Someone looking at the photograph or listening to the sound recording would never detect any change. In any case, the hidden message itself is usually encrypted, so that even if it were detected, it still couldn't be read.

In extreme situations, steganography might have some business applications. For example, if contract negotiations had to be hidden from intensely interested competitors that might be in league with the hotel your negotiator is staying at, your negotiator could send you many charming photos of buildings and seascapes. The photos could conceal messages about the contract negotiation.

Unfortunately, steganographic software that's freely available isn't 'high quality'. With a careful enough analysis of the transmitted data, it would be evident there was a hidden message. It's because the hidden message needs to mimic the ordinary 'noise' in the digital system where it's hiding. To be undetectable, the hidden message has to have the same statistics as that natural noise. The problem is that encrypted messages usually look much more random than the ordinary 'noise' they are trying to mimic.

If your business is doing something very 'interesting' to foreign governments, or to spookily technical and amoral competitors, then it's certainly possible that steganography wouldn't hide your messages reliably.


RSA + IDEA = PGP

I have referred to PGP. It stands for Pretty Good Privacy and is an encryption system for email and files. It was created and published by Phil Zimmermann in the USA as 'freeware' (free software) in 1991. Zimmermann wrote PGP from public information and bundled it into a software package.

The original version had four main modules: a symmetric cipher (IDEA), a public-key cipher (RSA), a one-way hash (MD5) for digital signatures, and a random number generator (which samples the user's keystrokes to get part of its random input).

PGP's source code is open to view. Anyone can get a copy and examine it. Then -- if they wish -- compile the source code themselves and make their own working program.

That is very unlike some commercial encryption software. Some companies won't tell you much about what's in their software. There have been many cases of 'secret' commercial systems that are trivial to break (for example, using the password to step through the message and then just XORing the two). Other systems have used a secure cipher like DES, but were programmed badly and were a simple walk-in because of the flaw.

I have just said that the PGP source code is freely available. This is a great strength. So we don't leave this topic without exhibiting an example, here's part of a PGP module that generates the two prime numbers needed:



static boolean primetest(unitptr p)
/*
* Returns TRUE iff p is a prime.
* If p doesn't pass through the sieve, then p is definitely NOT a prime.
* If p is small enough for the sieve to prove primality or not,
* and p passes through the sieve, then p is definitely a prime.
* If p is large and p passes through the sieve and may be a prime,
* then p is further tested for primality with a slower test.
*/
{
short i;
static word16 lastprime = 0; /* last prime in primetable */
word16 sqrt_p; /* to limit sieving past sqrt(p), for small p's */

if (!lastprime) { /* lastprime still undefined. So define it. */
/* executes this code only once, then skips it next time */
for (i = 0; primetable[i]; i++); /* seek end of primetable */
lastprime = primetable[i - 1]; /* get last prime in table */
}
if (significance(p) <= (2 / BYTES_PER_UNIT)) /* if p <= 16 bits */
/* p may be in primetable. Search it. */
if (bottom16(p) <= lastprime)
for (i = 0; primetable[i]; i++) {
/* scan until null-terminator */
if (primetable[i] == bottom16(p))
return TRUE; /* yep, definitely a prime. */
if (primetable[i] > bottom16(p)) /* we missed. */
return FALSE; /* definitely NOT a prime. */
} /* We got past the whole primetable without a hit. */
/* p is bigger than any prime in primetable, so let's sieve. */
if (!(lsunit(p) & 1)) /* if least significant bit is 0... */
return FALSE; /* divisible by 2, not prime */

if (mp_tstminus(p)) /* error if p<0 */
return FALSE; /* not prime if p<0 */






Possible attacks on PGP

If you're going to use PGP -- or any encryption software -- for very confidential material, then you need to trust it. People have different approaches to that: they range from examining the source code personally (for those with the right background, and provided the source code is public like PGP's), to asking someone "who should know" to "check this thing out".

That's part of my reason for writing this survey: to give some starting points for technical people who are new to cryptography. For example, there are expert cryptographers at universities (Dr Bill Caelli at the University of Queensland, and Dr Ross Anderson at the University of Cambridge Computer Laboratory, to mention just two) It would be better to start with an academic than with computer-security consultants picked out of the yellow pages. The strength of a cipher system is extremely sensitive to small details. So the academic system of peer review and concern with detail serves well in cryptography. Indeed, commercial encryption systems whose workings were guarded but were later broken into wouldn't have passed a routine academic review.

The following sections outline some of the possible attacks on PGP that have appeared in technical literature. The attacks also apply to other systems with a similar structure: ones that use RSA as a security wrapper to send a key that's then used in a symmetric cipher. Some of the attacks may seem far-fetched (TEMPEST, for example). But it can be valuable to know the extremes. If your company's messages are extraordinarily interesting to well-funded snoopers, then some of the extreme attacks may be used. You can decide in a commonsense way what's likely, and then how much it's worth spending to thwart the attackers (they can all be thwarted, at some expense).

Man-in-the-middle attack

When John wants to start a PGP communication with Terence, they have to exchange public keys. I've pointed out that this can be done by using insecure channels, like the Internet. So it can.

But something can go badly wrong if there's a person (or even a well-programmed computer) that can intercept both their messages. John starts things going by sending Terence his public key (call it JohnKey). Black Hat intercepts and stores this, then forwards John's message to Terence, but substitutes BlackHatKey instead of JohnKey. When Terence gets BlackHatKey, along with John's email saying "here's my key," Terence may be fooled.

Terence may next encrypt a message to John using BlackHatKey. Black Hat intercepts this and decrypts it (it's his public key after all, so there's no problem). Inside he finds a routine message to John, and also Terence's public key (TerenceKey). Black Hat substitutes his key for TerenceKey, and encrypts the message using John's real key (JohnKey).

John gets 'Terence's' message and decrypts it with his own public key. Inside he finds a message from Terence, and a line saying "here's my public key." John believes it, and from then on uses Black Hat's key instead of Terence's key. Just as Terence uses Black Hat's key instead of John's key.

Simple. And it would work easily, provided Black Hat could intercept all the messages and didn't mess anything up. Black Hat stays in the middle, opening messages in both directions, then re-encrypts them with the correct public key and sends them on. He could even alter the messages to suit his own purposes.

This is the greatest hazard with public-key cryptography. But it can be avoided if John and Terence get on the phone and read each other part of their keys (or use the more convenient 'key fingerprints' that they can each generate and verify). Provided they recognise each other's voices, or have some other way to check that they are really talking to the person they think they are.

Another way to stop a man-in-the-middle attack is for John and Terence to each have their public keys 'signed' by someone the other person trusts. A public key can be digitally signed, just like any other electronic file. A company in the US makes a business of signing public keys (Verisign). They check the person's identity, then sign his or her public key. Another way is if someone John knew had personally handed John his public key, and that same person later signed Terence's key. Then John could be confident he had the right key for Terence. "A web of trust" as Phil Zimmermann puts it.

Sniffers

If PGP is run on a remote host, the passphrase and messages are probably sent to the host in the open. (Unless there's session encryption like SSH or DESlogin). Packet-sniffing software lurking between the user's terminal and the host can quietly capture all this information. This way a snooper could read the messages before they were encrypted.

Multi-user systems

In a multi-user system like UNIX, the memory can be scrutinised by anyone with the proper privileges (usually root). Compared with the grim task of factoring a huge number, peeking into 'kmem' and reading the documents there is trivial. This may be done by someone who's allowed to (but isn't supposed to), but also by anyone who hacks into the system and gets root privileges (an art these days).

Multitasking swap files

In multitasking systems like Windows, the operating system will copy memory to disk when it needs more RAM. The information goes into the 'swapfile'. Information written there can sometimes linger there for a long time. Meanwhile, anyone who can get access to the swapfile (usually not protected) can search it for key words, or just browse it. In a network, the swapfile can be copied by a hacker without the owner ever knowing about it.

The swapfile might have anything on it, including the user's passphrase.

Trojan horses

Example: a software company discovered someone was sending out free disks that claimed to be the next version of their software. The disks had a copy of their existing software, with a Trojan horse added. People who installed the software and connected to the Internet automatically opened a 'back door' to their system that could let hackers right in.

If someone can get into a file system, they can read any unencrypted messages there. This is plainly a way around PGP.

A more elaborate Trojan Horse would be to offer free software that helps make PGP 'easier to use'. The system might work well, and look 'cool'. But it could also record the private-key passphrase from the user's keystrokes, then dial up a modem and send out the private-key file and the passphrase. It's possible.

Back doors in PGP

PGP's source code could easily be altered. Someone could insert a back door, compile it and leave the weakened PGP at some download site on the Internet. This would be easy to detect by checking the MD5 hash on the compiled code, but if people were too lazy to do that, the trick could work.

Certain personality types worry about getting a weakened copy of PGP. One of the authors of an overseas version of PGP was finally driven to post this to an Internet discussion group (alt.security.pgp):

I've heard a lot of whining and moaning because people aren't going to get the source code hand-delivered to them by Phil himself, but no one's bothered trying the much simpler alternative: Grab one of a number of crypto libraries and write a PGP-clone yourself. If you get a non-US one like SSLeay or my own cryptlib and do the work outside the US you'll have a complete independent implementation which isn't subject to export restrictions. I'm sure I could throw together a very basic encrypt/decrypt-only PGP implementation in about a day using cryptlib (which already has read support for PGP keys), although the message format means it's painful to work with anything which won't fit into memory. If people spent half the energy they spend complaining on doing a bit of coding, the "problem" would have been solved a long time ago.

-- Peter Gutmann, pgut1@cs.aukuni.ac.nz

Breakthrough factoring attacks on RSA

As I mentioned, RSA's security depends on the difficulty of factoring large numbers. But no one has ever proved this is the only way to break RSA. There may be some other way no one has found yet.

Also, someone may come up with a much faster way to factor numbers. And increases in computer power keep whittling away at the security of RSA keys by making factoring faster, no matter what the factoring system.

But it's easy for RSA users to keep ahead by increasing the size of their RSA keys (it simply needs a decision to do it). Have computers doubled in speed a few times over the years and you're getting worried? No problem: just generate a new and bigger public key that's a trillion times harder to factor.

There have been bright ideas in number theory that have recently made factoring easier. In 1977 one cryptographer suggested that factoring a 125-digit number would take 40 quadrillion years. But in 1994 -- not a quadrillion years later -- a 129-digit number was factored. It took eight months, using idle time on computers across the Internet.

For a survey on the likelihood of breaking RSA by factoring: The future of integer factorization, by Andrew Odlyzdo, AT&T Bell Laboratories (www.research.att.com/~amo/doc/complete.html).

Timing attack on RSA computations

Different RSA calculations take different amounts of time. In some circumstances an attacker could plausibly use slight timing differences in the computations to help calculate the private key. And the attack is passive: the attacker just watches the network and notes the times that the RSA operations take.

That attack doesn't work on PGP used on a laptop, for example, and not connected to a network. And it turns out defeating a timing attack is fairly simple, even on a network. Ron Rivest has also suggested a simple way to 'blind' the data first, and 'unblind' it later, so that the calculations in RSA take a random amount of time.

TEMPEST

TEMPEST is a US government code word for a classified set of standards to limit electromagnetic radiation from electronic equipment. It's a fact that computer monitors give off electromagnetic radiation, and that it can sometimes be intercepted and used to display a copy of what's happening on the victim's monitor. The attacker might sit in his van, parked on the street, and watch the CEO in the building opposite type documents on his wordprocessor. It is possible. Sometimes it may be easy.

Defence contractors and other government agencies apparently spend large sums on "TEMPEST shielding" -- covering the monitors and the cables (even a whole room), with copper or other conductive materials. Sometimes there are more active measures: jamming signals may pour out of such places.

There are few official reports on TEMPEST. But in 1994, the Joint Security Commission published a report to the Secretary of Defence and the Director of Central Intelligence (Redefining Security) that included a section on TEMPEST:

TEMPEST (an acronym for Transient Electromagnetic Pulse Emanation Standard) is both a specification for equipment and a term used to describe the process for preventing compromising emanations. The fact that electronic equipment such as computers, printers, and electronic typewriters give off electromagnetic emanations has long been a concern of the US Government. An attacker using off-the-shelf equipment can monitor and retrieve classified or sensitive information as it is being processed without the user being aware that a loss is occurring. To counter this vulnerability, the US Government has long required that electronic equipment used for classified processing be shielded or designed to reduce or eliminate transient emanations. An alternative is to shield the area in which the information is processed so as to contain electromagnetic emanations or to specify control of certain distances or zones beyond which the emanations cannot be detected. The first solution is extremely expensive, with TEMPEST computers normally costing double the usual price. Protecting and shielding the area can also be expensive. While some agencies have applied TEMPEST standards rigorously, others have sought waivers or have used various levels of interpretation in applying the standard. In some cases, a redundant combination of two or three types of multilayered protection was installed with no thought given either to cost or actual threat.

Private companies in the US, and some in Australia, appear to make a good living from selling TEMPEST-proof electronic equipment. It is impossible to judge how much of their business is shielding companies against wholly imaginary attackers.

There is also a rumour that the TEMPEST risk is a lot less than it used to be.

Monitors have been made quieter and quieter electronically, because people have been worried about possible health risks -- including cancer, in some of the more impressively worrying accounts. One story is that the electronic emission from a modern monitor is now so slight that it can't be picked up more than 10m away.

But I don't know. I only wanted to point out that a TEMPEST attack might happen. Then PGP would be useless.

23 Feb 1998. A few more emanations have leaked out. Markus Kuhn and Ross Anderson at the University of Cambridge Computer Laboratory have announced a possible software protection against TEMPEST attacks. They demonstrate it with a photo of a computer screen that says 'Oxford'. They ran software on the machine that changed the radiated pattern to 'Cambridge'. Sure enough, that's what shows up on the 'attacker' screen they set up. It means you could broadcast nonsense to any attacker who might be out there. Meanwhile, you carry on your own work in privacy. It looks like the beginning of a business shield against TEMPEST intruders. A lot of protection, for little cost. No expensive shielding -- just software.

6 Feb 2000. It seems the term TEMPEST is obsolete. The right word is said to be EMSEC (emission security). TEMPEST 101 is a plausible tutorial on all this, including warnings about con-men who peddle 'TEMPEST' interception systems. And a salutary reminder that messing with interception equipment in the US can intercept your life by plunking you into prison. An engaging read, TEMPEST 101, but I'm not vouching for anything.


Security procedures needed with PGP

Long and messy passphrases, and maybe key-recovery systems

The only thing protecting a person's private key on the hard drive is their passphrase. If the computer is left running and the person is away for awhile, it would take someone only a few seconds to copy the private key to a floppy disk. The owner wouldn't know it had happened. Later the attacker could use a PGP-passphrase cracking program available on the Internet. It searches through a lot of dictionary words and phrases to try to guess the passphrase. Any 'weak' passphrase will be found this way. If it is found, the attacker can unlock the person's private key on the floppy and use it to read intercepted messages.

A long and messy passphrase is the only protection. Eight or ten words, using both upper and lowercase letters, a few numbers and other keyboard characters, and a small section of completely random characters.

The trouble is remembering such a passphrase. Writing it down somewhere can be fatal to security. So businesses sometimes use a backup system that gives several people a different encrypted 'piece' of the passphrase (or the private key itself). The pieces are generated in a way that a certain number of them can be used to recreate the passphrase (or private key). But a fewer number can't. For example, there might be eight 'pieces' (all different) of the passphrase held by eight different people. Any five of the eight -- say -- could get together and run a program to re-create the passphrase.

I have been writing 'piece' in quotes, because they aren't pieces in any usual sense: they are cryptographically generated files, not fragments of the passphrase. The pieces give no information at all for an attacker -- unless the minimum required number can be gathered together.

Using a system like this, any kind of company protocol for passphrase management can be set up.

Erasing files securely

When a file is updated or 'saved', a new copy is made and written anywhere on the disk where there's enough space. Software applications create large numbers of these files and scatter them everywhere. When a file is finally 'deleted', only the last version is affected. The other versions may still be there, and can be viewed with the right software. Even if a file has been partly overwritten by another one, there can be confidential material in what's left. (Using 'Save as' instead of 'save' avoids most of these problems.)

Some software also creates a lot of 'temporary' files as it goes through its routine work. 'Temporary' files can linger and can reveal things to someone who gets access to the computer -- even remotely, by hacking into the network.

There is software that securely wipes files that are no longer needed. But most systems don't have them installed, and some Systems Managers haven't even heard of them. These programs can also be used to write random rubbish all over the swapfile before the computer is shut down.

To delete a file securely, random data has to be written over the whole file. Some people insist that random data be written over the file several times. The reason is that today's magnetic coatings allow high densities of data, but they can be hard to magnetize. So when they're overwritten, some of the tiny magnetic domains stay as they were. They keep a kind of faded copy of the information that was in the file. With each extra rewrite over the file, fewer and fewer of these magnetic domains remain as they were. But before they are overwritten to oblivion, it can be possible to extract the data that lurks there. There are special techniques for doing that, and there are some very secretive commercial services in that business.

It is instructive to consider how governments treat their secret data. In the UK, the Ministry of Defence insists that the surface of the disks with secret data on them has to be ground off and the dust securely stored for twelve years. The dust is still officially 'classified' even after the 12 years. In the US, the treatment of hard disks is similarly drastic. A US naval document (OPNAVINST 5239.1A) says that disks can either have their surfaces sanded away, or be dissolved by acid. The acid treatment seems to be regarded as final, because nothing is said about guarding the acid after that.

Encrypting disk files

More than 200,000 laptop computers are reported stolen each year in the US. Australia isn't exactly crime-free either, but I haven't found statistics on laptop theft. In either country, it would be fair to guess that the information on some of the stolen computers must be worth a lot more than the computers.

Yet many laptop owners rely on a simple startup password (the BIOS password) to stop unauthorised access to their hard disk. This is futile. There's usually a jumper switch inside the computer that will disable the password (all you need is a copy of the manual). Otherwise, taking out the battery on the motherboard will kill the password. And it's always possible to take out the hard disk and put it in any 'friendly' computer and read it there.

The files on a stolen computer aren't safe unless they're securely encrypted. And the encryption must be far stronger than the simple systems used in wordprocessors and spreadsheets. (AccessData's $190 disk will get anyone into those in a few seconds or minutes.)

File-encryption systems need to pass the same tests used to evaluate message-encryption systems: Are the algorithms strong? Is the source code available? Has it been scrutinised for some time by expert cryptographers not associated with the developer? Many commercial systems fail.

Breathe easy... use an air gap

If the computer you're using for PGP connects to the internet, or a LAN, and it's stuffed with software that does everything you want... watch out! As I've been suggesting, the way to break PGP is to find a way around it. Someone might plant a bit of 'co-operative' software in your machine. Co-operative for them. It can happen many ways -- like downloading a new 'screen-saver' or other captivating software that conceals a quietly malicious purpose.

A far-reaching but cheap solution: do all your PGP work on a machine that's dedicated to PGP only. Even a 486. Put a trusted version of PGP on it, but nothing else (except the operating system -- whatever one you want). Don't network the machine. When a PGP message arrives on your internet machine, copy the PGP message to a floppy. Then put the floppy in your 486 (if that's your isolated PGP machine) and decrypt it there. Do the reverse for outgoing messages.

No matter what swarm of sinister software may be active on your main machine, it will be helpless against the parade of PGP messages. No hidden software can capture your passphase. Or get at your secret key. Or capture your keystrokes. Or copy your plain-text messages before they're encrypted, or incoming messages after they're decrypted. Or secretly send copies of your plain-text messages down the wire.

It's called an air gap.

No need for all that? For a salutary little chill, read the "third week" section of "The Internet Auditing Project," by Liraz Siri. (Mirrored here by permission.)




Other email encryption systems

Netscape 4.0 integrated S/MIME (Secure Multipurpose Internet Mail Extensions) in its email system. It works quite a lot like PGP: it uses RSA as a wrapper to send a key to be used in the symmetric cipher that encrypts the message. This was a large event in the history of cryptography: millions of people were then (in theory) able to send each other RSA-secured email with a product they already used. Microsoft soon added S/MIME to Internet Explorer. It was suddenly everywhere.

Whether people are using the S/MIME in any large numbers, I don't know. I doubt it. Most business people I talk to seem baffled by it all -- not least by having to go off and get a digital certificate from some outside company like Verisign. They don't understand it, and they ignore it. (That's my perspective only. If you have figures on S/MIME usage, I'd like to see them.)

Another problem: the strength of the encryption used to be weakened to near insignificance in browsers exported from the US. It certainly wasn't strong enough to rely on for very confidential business email. But these days, you do get full-strength encryption.

Also, in a large piece of software like a web browser, there will be bugs. There always are. Even if there were no bugs in the encryption modules, any bugs elsewhere might be used to bypass the encryption or greatly reduce the amount of computer time needed to break it. Netscape's first adventure with encryption is well-known: there was a weakness in the random-number generation system and that made it almost trivial to break the encryption (even the full 128-bit model, not just the 40-bit export version). There are many important lessons in that episode, so I'll go into it in a little detail.

In the January 1996 issue of Dr. Dobb's Journal there was a technical article by two PhD students in the computer science department at the University of California (Ian Goldberg and David Wagner). They said how they were able to break Netscape's Secure Sockets Layer (SSL) encryption system.

Netscape developed SSL because they wanted to integrate RSA encryption into their web servers and browsers. The system would encrypt data exchanges between a browser and business server. The encryption would take place automatically 'underneath' the applications that run from a browser: http, telnet, ftp, finger and so on. Any data passed back and forth would be encrypted, no matter what application was using the data. There was a random 'session key', used only once per connection, with RSA (as usual) providing the wrapper to send the session key securely.

Goldberg and Wagner wanted to study how all this was done in detail, but Netscape wouldn't release the information. So the students did it the hard way: they reverse-engineered Netscape's algorithm by decompiling their executable program. Always tedious, but always possible.

The security of SSL depends on the unpredictability of the session key. (Just as the security of PGP depends on the unpredictability of the IDEA key.) If an attacker can predict the key or even narrow down the number of keys to try, the system can be broken.

Random numbers are hard to create in a computer. Instead, encryption software has to be satisfied with a pseudo random number generator (PRNG). This starts with a 'seed' number that is as random as it can be made (PGP carefully times people's keystrokes as part of its seed). The PRNG then expands the seed into a longer, random-looking stream of binary bits.

If the seed isn't 'very random', an attacker can guess (or narrow down) which pseudo-random streams of bits would have been used in making the session key.

It turned out that Netscape's seed depended on the time of day, the process ID, and the parent process ID. All three can be found or accurately guessed. An attacker with an account on a UNIX machine running the Netscape browser could get the process ID and the parent process ID simply by using a command that lists the process IDs of all processes on the system.

The other missing information is then the time of day when the session key was generated. But sniffers (like tcpdump) will record the exact time they see each packet go by. That means an attacker can guess the time to within a second. And that in turn means the attacker would only need to try a million seeds in order to get the microseconds input to the PRNG. As Goldberg and Wagner said: "Comparing the computed challenge values to the one we intercepted will reveal the correct value of the secret key. Testing all one million possibilities takes about 25 seconds on an HP 712/80."

They also suggest several tricks to guess the required system data if an attacker doesn't have an account on the attacked UNIX machine.

Goldberg and Wagner sum up what it all means:

The security community has painfully learned that small bugs in a security-critical module of a software system can have serious consequences, and that such errors are easy to commit. The only way to catch these mistakes is to expose the source code to scrutiny by security experts.

Peer review is essential to the development of any secure software. Netscape did not encourage outside auditing or peer review of its software -- and that goes against everything the security industry has learned from past mistakes. By extension, without peer review and intense outside scrutiny of Netscape's software at the source-code level, there is simply no way consumers can know where there will be future security problems with Netscape's products.

Since we announced our attack, Netscape has publicly released the source code to its patch for independent scrutiny. But the company has not made available for public review any other security-critical modules of their programs. Until they learn their lesson and open their security programming to public evaluation, many security experts will remain justifiably sceptical of the company's security claims.

The growth of Internet commerce opens wonderful new opportunities for both businesses and consumers, but these opportunities can be safely exploited only after all parties are satisfied with the security of their online financial transactions. We are concerned that companies are hiding information about their security modules and shunning public review. We hope that the lessons learned from this incident will encourage software companies to openly embrace in-depth public scrutiny of their security software as both a natural and necessary part of the software-development cycle.

I might also mention that the early versions of Windows 95 would send information to Microsoft from the user's hard drive, when the user first logged onto the Microsoft Network. Whether a company that seems so easy-going about people's privacy can be relied on to program an email encryption system is a question that may appear to answer itself. Whether Microsoft can program an encryption system without bugs and unforseen loopholes, is another question that any long-time Windows user might also have an opinion about.

Meanwhile, on a smaller scale in the software world, Phil Zimmermann founded a company in the US called Pretty Good Privacy, Inc. The company now sells an email system with built-in PGP (PGP Mail version 5.0). A wonderfully easy program to use. So I'm told (it isn't legally available outside the US yet). But soon. There's a group in Norway re-packaging the program, starting with a legally-exported copy of the entire source code! Kafka and Gogol would have loved it.

11 Dec 97. The commercial PGP situation is getting as hard to read as PGP cipher. PGP Inc has been bought by McAfee. No one seems sure what that portends. Will the source code for PGP 5.x be available for peer review? Some say yes. My reaction is to gaze watchfully and wait for my betters to sort this out. Meanwhile, we can go on using the old PGP versions like 2.6.1 and know they've been checked. Indeed, the old versions may end up as more than collector's items: they may end up as the only widely-used encryption software that's trusted by people in the know. Bill Unruh, for example, recently said something with a hint of that: "That crypto companies ALL are going the 'trust me' route is I think a very bad thing for crypto. PGP2.6.0 I believe it had a bug in its random number generator, which was caught rapidly only because source was available. What bugs lurk in any of the commercial codes will always remain a mystery (except perhaps to your commercial competitor)."

21 Aug 98. PGP is now owned by Network Associates (NAI), a part of McAfee Associates. (NAI has its headquarters in Santa Clara, California -- in case you want to know.) For business users of PGP in the US, the license requirements are easy to grasp: if you use any version of PGP for a commercial purpose, even a freeware version or if you roll your own from source code, then you have to get a license from NAI.

Overseas, the licensing works almost the same way, after you allow for some distortions caused by US export rules. There are many international versions of PGP: 2.6ui, 2.62ui, 2.64ui, 2.6.3i, 2.6.4ia, 2.6.3in, 5.0i and 5.5i. The last two -- 5.0i and 5.5i -- were created by scanning books of PGP source code that had been legally exported from the US. (You can do that with cryptography books.) But NAI owns the copyright on those books and has all rights over the contents. Equally, NAI has rights on the source code for earlier PGP versions. Which all means if you use any international PGP version for commercial purposes -- no matter how it got 'out there' -- you're required to pay a license fee to a company called Network Associates International BV (in Holland) (www.pgpinternational.com). That company also offers "legally re-engineered" PGP products itself. The fee can be paid to any NAI reseller outside the US.

14 Aug 1999. That last note is correct as far as it goes. But it doesn't stop you from creating your own source code for an encryption system that's compatible with NAI versions. If you have the energy and skill -- and some reason for doing it. You can use the 'OpenPGP' specs and indeed, roll your own. OpenPGP tells you how everything should work, without saying how to write the source code. You won't owe NAI any money, ever. But you will need to get a license from IDEA, and an RSA license if the product is going to be used in the US.

22 Aug 2002. PGP has been bought from NAI by a new company: PGP Corporation. This looks promising. I recognise some of the faces. There's Bruce Schneier of Counterpane, and the Master himself, Phil Zimmermann. They also say they're committed to open source code. For licensing information, see their website. Commercial licenses from NAI carry over to the new company.

Advantages of PGP for email encryption

The biggest advantage, which may remain a unique advantage, is that you know what you are getting. The package does one thing only: it encrypts and decrypts, using well-tested algorithms, and its processes are open for inspection. It's like running your own gas-turbine generator in a country where the power grid is unreliable.

Other encryption systems are riskily jammed into the side of gigantic software (like a browser). It's done as an afterthought. Even if the encryption module happens to be sound, there is no certainty that it won't be weakened or wrecked by bugs or unforeseen interactions with the rest of the software. Furthermore, until recently you weren't even allowed to inspect the source code for the browser. (Early in 1998 Netscape opened its hands and published the source code for its Communicator 5.0 software.)

In any contest between 'look' and 'no-look' encryption, there will be a market among knowledgeable business users for PGP -- or for any similarly open, strong and stand-alone product. It will seem simple prudence.


Encryption laws in a few countries

I used to have a summary table here, but found it went out-of-date too fast. Instead, here's one link:

Crypto Law Survey. By Mr Koops, who must work pretty hard at keeping the information current. He's also author of a book called The Crypto Controversy: A Key Conflict in the Information Society.


Legal points about PGP in Australia

There is no law in Australia prohibiting the use of strong cryptography. The Attorney General's office has even written a letter to the press:

Jackie Cooper implied that PGP is illegal to use in Australia. This is incorrect. The international version of PGP is perfectly legal in Australia. More information can be found on the EFA Crypto pages, http://www.efa.org.au

- Steve Orlowski, Special Adviser, IT Security Policy, Attorney-General's Dept, Canberra, ACT. (From The Australian newspaper, 8 Mar 97.)

There may be Australian restrictions on exporting the software for strong cryptography, but this seems aimed at locally-developed software that may be sold as a package overseas. It is unlikely to apply to an executive taking PGP abroad on his laptop for his own use (even the US allows that). But it may be best to ring the Attorney General's office first to check.


Paranoia may be wise these days

The only system which is truly secure is one which is switched off and unplugged, locked in a titanium lined safe, buried in a concrete bunker, and is surrounded by nerve gas and very highly paid armed guards. Even then, I wouldn't stake my life on it.

-- attributed to Gene Spafford

This section will seem like paranoia to some business people. Your company may not have experienced anything remotely like the attacks on security outlined here. Even if you have heard of some of them, it may seem unlikely such things could happen to your company. But all these things do happen, and some happen daily. How seriously you need to take them is a matter of commonsense business judgement. And that has to include a judgment about just how interested outsiders (or insiders) might be in burrowing into your most confidential company information, or intercepting it as it moves through networks.

Even security experts have a tendency to concentrate on the threats they know how to deal with. Attackers, alas, concentrate on what they know how to exploit. The two rarely seem to match. Many 'secure systems' have been designed -- and sold at high prices -- without considering what the attacker is likely to do.

Password cracking

Most of the 'brilliant' hackers are in fact masters at guessing passwords, or getting them somehow. They may start with the 'temporary' passwords that come with new software. Lots of buyers never bother to change them. If that doesn't work, hackers may try passwords that include your company name, birthdays, manager names, and any other information that's handy to get.

There's also the famous program Crack written by Alec Muffett. Its sole purpose is to break insecure passwords. It's good at it. And it is publicly available -- free, in fact.

If Crack doesn't work -- and that would mean all the users on the system have passwords about as unguessable as kH@8JH3?/MVz93fD -- then Black Hat can use other tricks to break into the system and get 'superuser' privileges. Black Hat can then put the machine into 'promiscuous mode' (so it accepts all Internet data packets, no matter what the packet header says) and then install a sniffer. In many networks, the account and password information flows innocently along in clear-text. Sniff, sniff, sniff. Got it.

Software bugs

Complex software with hundreds of thousands of lines of code will always have bugs. And any bug can possibly wreck security, even bugs that are a long way from the encryption module itself.

Bugs are most dangerous in 'privileged' software (like any of the UNIX daemons). The bugs can be manipulated to persuade the software to do things it wasn't designed to do. A famous case was the 'sendmail debug' hole. This let hackers bootstrap to a 'root' shell. Once there, they could create a new account, copy the password file, or anything at all.

Sometimes an inexperienced System Manager will put together a combination of hardware and software that creates whopping security flaws -- just because all the software packages have been used together as a system.

Or a reasonably secure system is simply misconfigured. It is a large job understanding today's operating systems -- and the software hanging from these operating systems, as if by its nails. And Systems Managers sometimes aren't specialists, but simply chosen from an organisation's staff. Because they are there.

Insiders

If a computer system isn't physically secure, then nothing about the system can be guaranteed secure. If Black Hat can get his hands on the machine, he can stop it and bring it back up in privileged mode. Then do awful things to the disk, plant Trojan horses, and on and on.

Many company insiders have this kind of direct access (at least to network components). Most workstations can be manipulated to get privileged access. It can sometimes be trivial to reboot a workstation into single-user mode and tamper with the workstation's filestore. That then opens up vistas on information flowing along the network.

Confidential backup tapes can be just as revealing, and sometimes even easier to access.

Human engineering

Superstar hacker Kevin Mitnick is said to be a master of human engineering. He might phone the IT section in a company and say, "I'm Dr. Grossworth, Chairman of the Board, and I forgot my password. I'm in Los Angeles and I need contract data for the Directors meeting tomorrow. Please reset my password..." This may happen at two o'clock in the morning. Resistance can be low then.

Or company phone books can be stolen, or company literature simply asked for by phone. The attacker might pose as someone with something useful to sell, or pose as a customer trying to convince you that you should give them some information.

Dec 2003: Mitnick has written a book about this: The Art of Deception. If you're running a company or responsible for securing its network, the single most useful thing you can do is to drop everything right now and read that book.

Spoofing

The headers of email are easily faked. Even hackers who have years ahead of them before puberty can concoct an email from santa@north.pole.com, or kbenson@treasury.gov.

Computer systems can sometimes be fooled the same way. A message or command can seem to come from within a secure network, but might be from outside. Firewalls struggle to stop this sort of thing.

Breaking smartcards

Smartcards are sometimes used now instead of a password. And they are often used for access to secure areas.

Smartcards have won a public reputation for being nearly tamper-proof. That isn't wholly justified. There are a number of attacks, though they're almost unknown except to experts who test computer chips. Smartcards are broken into routinely. Even ones ballyhooed as exceptionally secure are broken (like one that a government signals agency described as 'the most secure processor generally available').

A smartcard usually has an 8-bit microprocessor in a single chip, stuck on a plastic carrier. Information about the key is in the chip's EEPROM.

Ross Anderson at Cambridge University Computer Laboratory explains how to get out the chips: "Removing the chip is easy. First, we use a sharp knife or hand lathe to cut away the plastic behind the chip module until the epoxy resin becomes visible. Now we settle a few drops of fuming nitric acid (>98% HNO3) on the resin and wait a few minutes until some of it has dissolved (the process can be accelerated by heating up the acid with an infra-red radiator). Before the acid dissolves too much epoxy and gets solid, we wash acid and resin away by shaking the card in acetone. We repeat this procedure around five to ten times until the silicon surface of the die is fully exposed. The chip can then be washed and will be fully functional unless one of the bonding wires has been damaged."

Smartcard chips have been fully reverse-engineered at the Cavendish Laboratory in Cambridge. The chips were cleanly etched away, a layer at a time. A thin film of gold or palladium was deposited on the chip. That created a diode that could be read with an electron beam. Data from the layers of the chips was then fed into a PC and the images sharpened up to show all the chip's features.

Sometimes it isn't even necessary to reverse-engineer a chip. Sandia National Laboratories have reported looking through the chip with an infra-red laser set to a wavelength that makes the silicon look transparent. Photocurrents are created and the logic states of the transistors on the chip read off easily.

After all that: what encryption system should you use?

My views (Oct 2003):

  1. For high security, you're still safest with PGP. Provided you use a version that's been out in the field for a while and has been compiled by someone you trust. Anyone can go straight to the new commercial source: PGP Corporation. There is also an open-source (free) version: The GNU Privacy Guard.

  2. There are many file-encryption systems that use strong ciphers and a password. You can use these systems to encrypt files and send them by email. Some of these encryption systems will even let you examine their source code. They certainly use very strong ciphers (Blowfish, IDEA and triple-DES are common choices). But it takes time for any faults in the source code to be pointed out. And even if you're satisfied that a system is flawless, how many people use it? If it isn't used by the business people you want to communicate with, you need to convince them to install the software. Then set up a system for sharing passwords -- which have to be long and messy ones for reasonable security. It can all be done. And it can all be extremely secure. But these exacting and peculiar procedures don't exactly run in the blood of most office staffs.

  3. If something isn't a vital secret, but you'd still like to keep the idly curious from reading it, then the encryption in pkzip may be good enough. Almost everyone has a copy and it's easy to use. It doesn't have a trivial cipher either. Most of the publicly-known ways to break into it rely on software that tries passwords until one works ('brute force'). There is also one 'cracker' that can use a small but exact part of the message you may happen to know (or can guess) and then it works out the password. The simple brute-force cracking systems can be defeated by choosing long and messy passwords. The known-text 'cracker' can be frustrated by changing the password often and avoiding file names that reveal something about the content. Anyway, there's enough work involved in breaking into pkzip encryption to keep out anyone who's a bit snoopy, but lazy.

  4. Set up a secure-message form on your website. Then anyone can send you a message fairly securely. In the next section, my hopes for this take wing.


Secure website forms

Imagine this: every business has a secure-message form on their website, for the convenience of their clients. (Like our secure form.) Any business could then communicate securely with any other business. Easy. Just use the other company's secure form.

People wouldn't have to remember passwords. Masses of people wouldn't have to run around getting their public keys signed by a certificate authority (so they can use S/MIME) and then protecting their private keys with great vigilance (a nearly hopeless prospect, in my opinion). People could be fairly confident about what server they're connecting to -- because secure servers have certificates signed by a certificate authority.

And there's a business reason for putting up a secure form right now: your customers feel easier, and you get their business. (Our secure form is much-used, even by newbies.) If your competitors don't copy you right away, that's their problem. Meanwhile, you and others have made a start. So secure forms avoid the can't-get-it-started lethargy that has afflicted every comprehensive encryption scheme -- where everyone just waits for everyone else to do it first.

The security of secure forms ranges from fair to superb. It depends how secure your server is (where the secure form sits), and what sort of browser someone uses to connect to that server.

The browser side

I mentioned earlier in this paper that browsers are secure in theory, but you can't always be sure because you aren't always allowed to look inside. At least Netscape has published the source code for its Communicator 5.0, and the Mozilla Crypto Group have clipped in a full-strength 128-bit SSL package. (SSL is the standard system for browsers to connect to secure servers. It uses one of several symmetric ciphers, with a randomly-selected key wrapped in an RSA envelope -- much like PGP.) So that's one 'open' browser that can be inspected for fitness. The Opera browser from Norway also has 128-bit SSL. Their source code isn't open, but the SSL was supplied by admirable Eric Young. He's responsible for the free version of SSL (SSLeay). There are sound commercial reasons for Opera doing everything right, in order to avoid having anyone boast about hacks into their SSL. (I haven't heard of any.)

If you're outside the US and haven't fixed up your exported browser with a clip-on like Fortify, you're probably running with 40-bit SSL. I wouldn't say that 40-bit encryption is useless. Hardly. Especially if great numbers of people started using it: snoopers wouldn't know where to start. There's a burden breaking into 40-bit SSL, and an impossible burden if someone tries to break myriad messages.

So from the browser end, you can get reasonable security. Even top security.

The server side

What server does your secure form sit on? And does the server allow browsers to connect at full 128-bit SSL?

If your form is on a commercial web-host, outside your company, then you're also depending on the administrators of that site to keep the server secure from hackers (and not peek at the messages themselves). If you trust the people at your web-hosting service, then things are simple: you put your secure form on their server and set up a system for collecting your messages securely. Our system at Viacorp is like that: when you push SEND on our secure form, it's automatically encrypted with PGP and sent to us by ordinary email. The message is immediately wiped from the server. We get email messages that look like this (fictional) one:


From: ujones@ditherhetlake.com
Date: Tue, 13 Jul 1999 18:11:40 -0700
To: viacorp@viacorp2.com
Subject: reply from Viacorp secure message form

name:  Uriah Jones
email: ujones@ditherhetlake.com

-----BEGIN PGP MESSAGE-----
Version: PGP for Personal Privacy 5.0
MessageID: vKBfk7LHO+N058aluwi17rvBSX0aztnx

hQEGA5wIr/wwiQ5pAQfQj5LJjL/Bgtsn9SWxGC5+gZlJ8Z7xrMnR+hJxriTblU0v
j9SoUP+Lp18pXOr5tDDNdWaLrt9wxNWlFK4UhAyevhkXsOHUOmIQdTGFvAB0qnhM
zGns2FENJWbpbJJC2X7XSkiySX0CPlsk1ZFPZMKTXNZwcTbJ8C0N55uL5IkZDtSw
pPOCi0X+MgUWVykETIEZAclqLEDEMBflwwPixfMC/lACsQ1E5H5NXv4RremFkUx+
7dJMC4zYb1C9SgYeq7Uhy2WLMzxVTbCa2VnHuq5q9lKFuV0rRv+7+PvF01nKxz9i
waouOxFWaIORxjoBReV9fCH3sC5AeSuPQaSMr/91Co0YgWUGZe8o9dtqLQRH5hCR
bD2K5T1wHTo7Xy5q857CrwBgG1H3KTCy947Uwe5ZGCBFyu6vwZQZ3MkNfHtmFBB7
pZbj7DSheJ6AT1Sz6zNGmiJLWtLPmaTGZRPCrq10v9nvt0YAZpR1sQ8vJGsjT+kS
XaQ67E1ZvgpOOqnn97c9lKtI5TM+C4c=
=6uw8
-----END PGP MESSAGE-----

As it happens, we trust the folks who run our secure server. Anyway, our secure form warns people not to send anything life-threatening using this setup.

But there is a far more secure system. You can run your own secure server. Maybe you already do. If the secure server sits in your own building, you can impose any security rules you want to. And make sure unauthorised people can't look at the incoming messages.

I set up a system like that, to see how it was done. I installed Linux on a spare PC. Then put in a free Apache webserver, configured an ISP connection, and arranged for a permanent domain name to be routed to whatever dynamic IP number the ISP assigned the machine at each log-in. Which all worked. Then I added in SSL, using the free SSLeay software. By the end of all that, I was ready for a week in a deck chair. But there it stood: the Linux machine running on one ISP connection, dishing out the secure form when it was accessed from a second machine on another ISP connection. (Two machines, standing side by side, connected in a loop around several continents. Responding instantly. Impressive.)

It worked but we didn't leave it up. We'd have been faced with leaving the machine running perpetually, looking after security patches and warding off possible hacker attacks. Tasks with no end.

But if you already have a web-server in your company, and someone to look after it, that's different. Moreover, all this may be simpler some day. Cisco may decide to market a plug-in secure server. (Why not? They already make an ordinary plug-in webserver.) A small box, like a fax machine. Plug it into the phone line, turn on the power, configure a few things, and lo... there's your secure server. That's all it does, and it costs maybe a few hundred dollars to buy. All cut down to essential things only.

Getting your own secure form

If you want a secure form for your business, how do you get one?

One way: set up an in-house secure server and put the form on that. The rest of your website can stay wherever it is. You might need to hire a computer-security consultant. It depends who you have on staff.

If you want to put the secure form on someone else's server, it's easier. Here's an over-simplified outline: find a web-hosting service you feel confident about, then get them to help with the technicalities -- like a system for getting the incoming messages to you securely. But a form like ours can be hosted for about $15 a month, for example.

If you do anything along these lines, it's better than doing nothing. You'll be offering your visitors some security, maybe a lot, instead of none.




By the same author

Your dog is watching you.

The Debt Book

The security of petrol and diesel supplies in Western Australia.




copyright









compound interest
present value formula
annuity
annuity present value

Perth Australia