Modern Ciphers

The magazine of the Melbourne PC User Group
Modern Ciphers
Dr. Steve Roberts
cipher@steveroberts.com.au

Ciphers and Codes

Alice and Bob, the two protagonists of cryptography, wish to communicate in privacy. They can use a cipher to disguise their information as it flows through - the resulting "ciphertext" will be the same length as the input "plaintext". A cipher uses a key, and an algorithm to apply the key to scramble the plaintext.

The key is secret - usually 10-40 digits - whereas the algorithm is public knowledge. To have everyone knowing how the cipher works may seem like bad security - but everyone knows, for example, how a Yale lock works, but only I have the key for my house. The most recent attempt to have a secret algorithm was Skipjack, which sank into a sort of morass of derision. Even if it hadn't been faulty, once the algorithm is reverse engineered and published, how secret will it be then?

Let's mention codes in passing - unlike ciphers, codes use a codebook that is very like a dictionary. The codebook might be secret, or publicly available. Instead of sending eight words "I do love you, will you marry me" Bob could simply look it up and send one word like VUGAK, which Alice could go and look up in her copy of the codebook. They were very popular when telegrams were charged word by word. But let's move on to worry about ciphers, which will be seen to come in two types.

Symmetric Ciphers

All historical ciphers, and most of those in use today, are said to be symmetric because the users must all have the same secret key. Alice enciphers her message using the key K, Bob applies the same key K to decipher it and the postman can't read it. Symmetric ciphers in use today include DES, IDEA, CAST, RC4, and BLOWFISH among many others. These algorithms are all public knowledge, although some of them are complicated.

The amount of security provided by an algorithm varies, but some (including all the above) are believed to give the highest possible security - they have no feasible attack except for exhaustion of all the possible keys. The most secure cipher of all is ironically the simplest one - the one-time pad, or XOR algorithm. This requires an enormous amount of random key material; the key is as long as the plaintext and you simply exclusive-or the two of them together. This is used by spies in the field but hardly anyone else, the main problems being to issue a vast quantity of key in the first place, and to store it so it remains secret. If you ever use the same key twice, your enemies (who never sleep, and who mercilessly copy all your traffic accurately) will recover the key that was used plus both the plaintexts.

Symmetric ciphers have worked well in most situations - but there has always been the problem of getting the secret key to Alice and Bob in the first place.

If Alice mails the key K to Bob, then the mailman can read it. Even when the key K is in place, it can't be replaced easily, since an enemy might have broken the cipher and knows the existing key, so Alice can't simply send a new key K' enciphered by the old key K. If 1000 people want to talk using a symmetric cipher, each of them must possess 999 keys - 1000*999/2 keys in all.

Another problem with symmetric ciphers arose in banking, where Alice might be an ATM and Bob might be the bank's host computer. The programmers of the Alice system can encipher a message involving money, send it to themselves and get Alice to process it as if it came from Bob. Conversely, the managers of the Bob system can apply this logic and deny that Bob sent a message that actually was sent.

Asymmetric Ciphers

These problems of "authenticity" and "repudiation" were almost solved by the discovery of asymmetric ciphers in the mid 1970s - the public names are Diffie-Hellman and RSA (Rivest, Shamir and Adleman), but the notion was discovered at GCHQ in the early 1970s and abandoned as not a very good idea. (I worked there later, and have never liked asymmetric ciphers either). An asymmetric cipher has two related keys - one public, one secret. You apply either of these keys to encipher a message, and apply the other key to decipher it. Unlike those for symmetric ciphers, the algorithm for RSA is wonderfully simple (see Figure 1).

P,Q large primes; N=PQ; E a small prime, say 3; D such that EDº1 mod (P-1)(Q-1). The public key is (N,E), the secret key is (N,D). A message M (<N) is enciphered by exponentiation to get M^E or M^D modulo N. To decipher those, raise them to the power of the other exponent to make (M^E)^D º M^D)^E º M, modulo N.

Figure 1. The algorithm for RSA

To send a message to Bob, Alice must know Bob's public key, and she enciphers the message using that. In fact, the whole world can know Bob's public key without loss of security; but only Bob knows Bob's secret key and can read the message. RSA is therefore one-way or asymmetric. To reply to Alice, Bob has to use Alice's public key. However, the main use of RSA is the other way round - Bob uses his secret key to encipher a message that everyone else can decipher. This may sound a bit strange, but since only Bob can have prepared that message, he has effectively signed it, which is impossible with a symmetric cipher. He can't deny sending it and nobody else can forge a message like it. RSA is therefore used to sign messages, such as e-mails and financial obligations.

In theory, RSA does not have the problem of getting the keys set up beforehand - everyone's public key is simply published everywhere. However there are problems with the authenticity of those keys - perhaps someone else publishes a key and tells everyone it's Bob's - which has left the RSA system not mature yet, with a hoped-for "web of trust" of reliable public keys not yet having materialised. RSA also requires large keys (the primes P and Q are typically 512 bits each) which makes it slow to calculate, and has proved vulnerable to impersonations and attack, with more attacks being invented and developed at a feverish pace. I told you I never did like it ... The replacement for RSA will be a system based on Elliptic Curves, using complex maths but smaller keys; research on these is still incomplete.

Beware Of Making Rash Predictions

The discoverers of RSA published their method in Scientific American in 1977, together with a message enciphered by an RSA key of 429 bits (512, 768 and 1024 bits are now common). They offered a $100 prize and claimed that it would take 40,000 trillion years to break a sample enciphered message ... and were shown to be nearly right when 17 years later someone broke it. The underlying message read "The magic words are squeamish ossifrage". I would have given much more than $100 to be the first to ring up Rivest, Shamir or Adleman and ask "how's your ossifrage today?"

Hash Algorithms

Having described symmetric and asymmetric ciphers I will mention a sort of third class of cipher, the hash algorithm. This is a complex one-way process with no key, which produces a 16- to 64-byte checksum from a text of any length in a very short time. Every bit of the checksum is affected by every bit of the source file. It is not feasible to find a "collision" where two texts give the same checksum, so it can be used in signing a document electronically. Instead of signing, say a 100 MB file, you calculate the 16-byte MD5 digest of it (a fast process) and sign that instead. However, with signing there are all sorts of legal loopholes yet to be visited and I don't believe it will ever catch on. Popular hash algorithms are MD5 and SHA; and strictly also the much older LRC and CRC, although these allow collisions.

The Data Encryption Standard (DES)

People have had a desire for secrecy for centuries - both individuals and governments have had things worth hiding, whether it's just from their enemies or from everyone. Until about 1970 cryptology, the science of managing secrets through encipherment, was restricted to military and diplomatic realms. Then a need to protect commercial secrets was acknowledged (it had been there for decades already -there was snooping not only from rival companies, but also from entrepreneurial foreign powers).

The US Government held a competition in the early 1970s to find a cipher that would be suitable for public and corporation use, without wishing to make available any of the existing very good military/diplomatic ciphers for unhealthy study or exploitation. The winner was an IBM submission that became known as the Data Encryption Standard (DES) and is still in very common use worldwide today. It had a 64-bit key, but through a mysterious governmental process it was decided that 56 bits would be enough and the algorithm was dummied down accordingly by making 8 of the 64 bits become almost useless parity bits. As a result there have always been rumours that DES has a trapdoor or (more credibly) that NSA have a DES cracker. Now, 25 years later, the DES algorithm is still revealing its security and beauty in the public domain; for example a major new attack was discovered in 1992; it later turned out that the inventors had foreseen it and designed DES against it, in 1972.

The only feasible way to attack DES is by exhaustion - you try all 2⁵⁶ possible keys. Now 2⁵⁶ may be a big number, but computers have always followed Moore's Law and doubled in power or halved in cost every 18 months. Little attention was paid to frantic warnings around 1990 that it would be possible to build a DES cracker - but when in 1998 somebody actually built one (at hobbyist cost) and cracked a message with it, people began to respond. DES is now being replaced by triple-DES, a system that uses two keys to get 112 bits instead of 56 bits of security.

How to Make a Good Cipher from a Bad One

Here's how triple-DES works - in fact here's how to make ANY cipher, however bad, into a secure cipher, however good you need it to be. Let's write the basic ciphering operation as Z = eK1(D) - "ciphertext Z is made by enciphering data D with key K1". That small "e" represents the encipherment operation - there is also a small "d" for decipherment. In the DES system, K, D and Z are all 64 bits (8 characters), but this logic will work for any cipher. To get more security, we could try having a second encipherment, Z' = eK2(Z) = eK2(eK1(D)). However, this is vulnerable to a meet-in-the-middle attack which can recover K2 and K1 separately, as follows. If the attacker knows several pairs of D and Z' - an acceptable assumption in the vicious world of cryptology - he/she makes two (big) lists of eK(D) and dK(Z') for all possible K. Entries in the two lists will always match when K=K1 in the first list and K=K2 in the second list - voila, recovery of both.

DES has a 56-bit key, so the number of DES operations required for this attack is 2⁵⁶ plus 2⁵⁶ = 2⁵⁷, but we were hoping for 2⁵⁶ times 2⁵⁶ = 2¹¹². To achieve that bigger number, we have to do a third encipherment:
Z'' = eK3(eK2(eK1(D))) which requires 2⁵⁶ plus 2¹¹² DES operations to break. It turns out that K3 can be the same as K1 without any significant loss to security. Also without loss of security, triple-DES is specified with a decipherment for the middle operation:
Z'' = eK1(dK2(eK1(D))), since this makes it compatible with single DES when K1=K2.

So triple-DES keys are usually made from two single-DES keys, not three. Triple-DES has been in use in a few places since about 1990, but now it is (or should be) appearing everywhere DES is used. Even with Moore's Law, 2¹¹² DES operations is too many for any computer - using 1 quantum of energy and 1 atom to implement a register operation, you would need a computer the mass of the Sun and the age of the Universe to exhaust 2¹¹² operations. Then there's the electricity bill (hmmm, is that why it's been so hot this summer?)

To get even more security, we could use three keys in quintuple-DES or four keys in heptuple-DES, etc. This is relevant because governments have tried to limit the security of ciphers that are exported, with comical results. With this technique you can take a code wheel from your Weeties packet and make a cipher that would require 2⁵⁰⁰⁰ operations to break - or any other level of security. But don't keep the keys in your desk diary!

The Advanced Encryption Standard (AES)

Despite the security of triple-DES, its basic algorithm still dates from the 1970s and there has been pressure for long-term improvement with a new and faster algorithm. This new cipher is to be called AES for "Advanced Encryption Standard" and have three modes of operation with keys of 128, 192 and 256 bits. An open competition was announced by NIST (standards body of the US Government) in 1998, 15 candidate algorithms were submitted and weeded down to five in the first phase of the selection process. The authors had to give a 15-minute description of their algorithms in front of a hostile audience of each other and various eminent mathematicians - one of the candidate algorithms was shot down from the audience during its 15-minute presentation.

The five finalist algorithms (Mars, RC6, Rijndael, Serpent and Twofish) all had spotless security and came from impeccable origins by acknowledged authors. The second phase involved intense scrutiny of these five algorithms, most especially by the authors of the rival algorithms, culminating in a five minute speech for each algorithm. Public comments were received by NIST, who were allowed to define that AES would be any of these algorithms, or any combination or modification - anything at all really. All submissions up to this point were public, and could be followed on NIST's web site - you can also get the source code for all 15 original candidates.

NIST then went into a private conclave for months, and when the white smoke eventually drifted over the rooftops in October 2000, they announced that the winner was Rijndael. This was interesting because Rijndael's authors are Belgians, not Americans, giving the lie to this all being an in-house show. The AES standard will soon be published for commercial and industrial use, however triple-DES is nearly as secure and will persist for some years to come.

Security on home PCs

First, remember that the protocol and key-management of ciphers are far weaker links than the ciphers themselves. To paraphrase a recent remark of Bruce Schneier (author of good introductory books Applied Cryptography and Secrets and Lies), enciphering messages in a vulnerable world is like making a one metre stretch of your garden wall very high. Other stretches of the wall relate to issuing the key, keeping the key secret, stopping people from posing as you, etc. A good cipher such as DES can make its part of the wall a kilometre high; improving DES to triple-DES makes it 100 kilometres high, but without affecting the other parts of the wall. (In my humble opinion, RSA is the garden gate).

Let's think about what's in your home computer system - in increasing order of sensitivity there are

The evil people who are going to attack your computer can do so in a variety of ways. In particular they can

Securing your computer files and your e-mail messages is just like securing your home against theft. Despite very good locks and alarm mechanisms being available, even to ordinary folk, burglaries are as popular as ever and everybody hopes it won't happen to them. People buy heavy locks for their doors then don't lock them, or hang the key up outside, or they don't defend the back door; then the burglars come through the window anyway.

Until now you had to encipher files and e-mails manually, but there are privacy products that will automatically encipher your files, e-mails and even your whole hard disk. As with most computer programs, some of these are truly awful and others are quite good. I use PGP - it includes PGPdisk which keeps files on my hard disk safe, you can get it as freeware or a licensed copy is only $30 from Harvey Norman.

As people began to expect some degree of protection, ciphering has started to be included in commonplace products and SSL, in particular, now provides a good degree of privacy. When you communicate with another computer, the SSL's in both machines start with a "handshaking" conversation where they find out what ciphers the other machine possesses and what it has been told to use. There are two common standards: the default 40-bit keys give hardly any security, but 128-bit keys give very good privacy.

A major attack on a computer that has been configured to use 128-bit keys is to make your SSL tell it that you can use only 40-bit, whereupon some machines will drop theirs to 40-bit and send away. Browsers display a little padlock or similar to indicate what standard of privacy is actually in use.

Ciphering is also used to restrict users from doing things - for example Microsoft have implanted an RSA public key in Windows which prevents upgrades or changes being made, unless the upgrade is signed with the corresponding secret key, which only Microsoft possess. Ironically and for unknown reasons they implanted a second RSA key for the same purpose, which you can freely replace with your own public key, thus gaining the ability to modify Windows.

Extreme Ciphers

The standards for military and diplomatic ciphers, which protect lives and the welfare of nations, are far higher than for commercial ciphers such as DES and RSA, which protect comparative trivia such as money and privacy. They include concepts like these:

However there are no comparably vicious standards on how to generate, issue and manage the keys, or prevent the users from misusing their machines. Which leads us back into the PC world for our conclusion.

Bad Habits

Despite the availability of good enough security tools, computer users will go to great lengths to help attackers - and I've done some of these things myself, under pressure to be more concerned with tasks that generate money (and preventing theft does not count as generating money). After debugging a secure system using toy development keys, bear in mind that replacing them with secret production keys will cost time and effort, for no visible gain.

When a password is required for something, try typing just Enter, or "a", or "11111". If the system disallows all the same digit then try "11112". If you do use a decent password (of at least 8 characters, and including both letters and numbers), then write it in your desk diary or even on the wall, and try to avoid ever changing it. Hard code it into your logon script if you can. If the password must be changed monthly, then the name of the month 'mar2001' saves a lot of trouble (woops - sorry if I have just exposed the master password for any large corporate computer systems ... change it in April eh?) And feel free to tell your colleagues your password - not just anyone, of course, only the people to whom you already lend your building access pass...

But seriously, when cost-conscious managers ask "how many successful attacks have there been so far?" ask in return "how many successful attacks should we allow?". The same logic applies to securing your confidential data as to backing up your files, locking your house doors or wearing a car seat belt - there's no need to bother at all, except just before a disaster.

About the Author:
Dr Roberts, cipher@steveroberts.com.au is an independent security consultant specialising in evaluating algorithms and devices for the banking industry. See http://www.steveroberts.com.au for additional information.

Reprinted from the March 2001 issue of PC Update, the magazine of Melbourne PC User Group, Australia