Home

Risk Analysis

About us

Alice and Bob

Cryptography

Security Courses

Security Healthcheck

Customers

Office Systems

cCrypt

The Story of Alice and Bob

Alice and Bob After-Dinner Speech

given at the Zurich Seminar, April 1984, by
John Gordon
by invitation of
Professor James Massey

Good evening Ladies and Gentlemen.

There comes a time when people at a technical conference like this need something more relaxing.A change of pace. A shift of style.To put aside all that work stuff and think of something refreshingly different.

So let's talk about coding theory.

There are perhaps some of you here tonight who are not experts in coding theory, who have been dragged here kicking and screaming.  So I thought it would be a good idea if I gave you an instant, graduate course in coding theory.

Coding theorists are concerned with two things.

Firstly and most importantly they are concerned with the private lives of two people called Alice and Bob.  In theory papers, whenever a coding theorist wants to describe a transaction between two parties he doesn't call then A and B. No. For some longstanding traditional reason he calls then Alice and Bob.

Now there are hundreds of papers written about Alice and Bob. Over the years Alice and Bob have tried to defraud insurance companies, they've played poker for high stakes by mail, and they've exchanged secret messages over tapped telephones.

If we put together snippets from lots of papers, we get a fascinating picture of their lives.This may be the first time a definitive biography of Alice and Bob has been given. In papers written by American authors Bob is frequently selling stock to speculators. From the number of stock market deals Bob is involved in we infer that he is probably a stockbroker.

However from his concern about eavesdropping he's probably active in some subversive enterprise as well. And from the number of times Alice tries to buy stock from him we infer she is probably a speculator.

Alice is also concerned that her financial dealings with Bob are not brought to the attention of her husband.

So Bob is a subversive stockbroker and Alice is a two-timing speculator.

But Alice has a number of serious problems.

She and Bob only get to talk by telephone or by electronic mail. In the country where they live the telephone service is very expensive. And Alice and Bob are cheapskates. So the first thing Alice must do is MINIMIZE THE COST OF THE PHONE CALL.

The telephone is also very noisy. Often the interference is so bad that Alice and Bob can hardly hear each other.   So another of Alice's problems is DEALING WITH NOISE.

On top of that Alice and Bob have very powerful enemies. One of their enemies is the Tax Authority. Another is the Secret Police.

This is a pity since their favourite topics of discussion are tax frauds and overthrowing the government.

These enemies have almost unlimited resources. They always listen in to telephone conversations between Alice and Bob.   So Alice also has the problem of ENSURING CONFIDENTIALITY.

And these enemies are very sneaky. One of their favourite tricks is to telephone Alice and pretend to be Bob. Well, you think, so all Alice has to do is listen very carefully to be sure she recognises Bob's voice.

But no. You see Alice has never met Bob. She has no idea what his voice sounds like.  So IDENTIFICATION is another of Alice's problems.

So you see Alice has a whole bunch of problems to face. Oh yes, and there is one more thing I forgot so say - Alice doesn't trust Bob. We don't know why she doesn't trust him, but at some time in the past there has been an incident.  So she's got an AUTHENTICATION problem too.

Now most people in Alice's position would give up. Not Alice. She has courage which can only be described as awesome.

Against all odds, over a noisy telephone line, tapped by the tax authorities and the secret police, Alice will happily attempt, with someone she doesn't trust, whom she cannot hear clearly, and who is probably someone else, to fiddle her tax returns and to organise a coup d'etat, while at the same time minimising the cost of the phone call.

A coding theorist is someone who doesn't think Alice is crazy.

Information

The other thing coding theorists are concerned with is information.

Nothing else is like information. Information is very peculiar stuff. It can both be created and destroyed. You can steal it without removing it. You can often get some just by guessing.

Yet it can have great value. It can be bought and sold. One type of information is called Money. There are people who refuse to concede that money can be created and destroyed. They spend their entire lives altering records and making adjustments to ensure that every time a bit of money leaves some place, an equal bit seems to appear somewhere else. These people are called accountants.

Source, channel and secrecy coding

Coding theory like Gaul is divided into three parts called Source coding, channel coding and secrecy coding.

Source coding

First I'll tell you about source coding.

Source coding is what Alice uses to save money on her telephone bills.

It is usually used for data compression. In other words to make messages shorter. There is a story about a student of information theory on his first day at college. He had entered a strange, bizarre world. The only sounds were the occasional calling out of a number by one of the professors, followed by laughter. One professor would say '52', there would be a short pause then peels of laughter. Someone else says '713'. Same thing, everyone falls down laughing. "What's going on here" he asked his tutor.

"We're telling jokes" said his tutor.

"Telling Jokes?"

"Yes, you see we’ve all worked here so long we know each other's jokes. There are a thousand of them. So, being information theorists we applied data compression. We just assigned them all numbers, 0 thru 999. It saves a lot of time and effort. Would you like to try? Just say any number 0 to 999..."

He wasn't fully convinced. But he tried. Very quietly he whispered "477".

Hardly a murmur.

He looked at his tutor. "What's wrong" he said.

"Try again" says the tutor.

So he does. "318" - same again, not a thing, hardly a murmur.

"Something's wrong" he says.

"Well" says the tutor, it's like this.- It's not so much the joke as the way you tell it!"

There is a curious sequel to this story. This student eventually succeeded by accident in the most dramatic and unexpected way.He called out a number outside the range 0 to 999. "Minus 105" he said.

At first there was stunned amazement, then first one professor laughed, then another then another, till they were all rolling about holding their sides.

None of them had heard that one before.

Channel coding

Next we come to channel coding.

Channel coding is what Alice uses to overcome the noise and interference on the line. Most people have a natural instinct for channel coding. What they do is to spell out important words. This adds redundancy and enables the listener to cross check. If part of the message is lost the missing bit can be reconstructed from the remaining part. Many organizations such as the military, the aviation community, the Police and so on use a standard phonetic alphabet specially designed for this purpose.

It goes Alpha, Bravo, Charlie, Delta, Echo, Foxtrot, etc. So one says "Mike" and "November", which is much clearer than saying "M" and "N" which are easily confused otherwise.

Alice uses this to explain to Bob that her husband Michael is getting suspicious of her stock option dealing.

"I have to tell you about Mike" she says.

But Bob hears "I XXve to tell u XXt Xxike".

"What's that again" says Bob.

"I have to tell you about Mike" says Alice.

"Didn't get the last word Alice" says Bob, "Can you spell it out"

"Mike India Kilo Echo" says Alice.

"Got India Kilo Echo, What was the first word" says Bob.

"Mike"

"Can you spell that?"

"Mike India Kilo Echo" etc.

Actually there have been lots of other phonetic alphabets, The predecessor to the International Phonetic Alphabet went Able, Baker, Charlie...

Then there are those based on names of countries:- Africa, Brazil, Chile, Denmark, England, France, Greenland, Holland, India, Japan, Khazakistan, Lithuania, Morocco, Niger, Oman, Papua, Qatar, Russia, Spain, Tanzania, Uruguay, Venezuela, WestPhalia, Yemen, Xanadu, Zambia.

My personal favorite is this

Secrecy coding

Finally we come to Secrecy Coding, or Cryptography.

Secrecy Coding is what Alice uses to try to stop the tax authorities and the secret police understanding her telephone conversations.

Now cryptographers are very peculiar people. They have very devious minds.

Sometimes they encrypt jokes. Security agencies call these "Covert Jokes". People who make them are CryptoLaffers.

An intelligible joke in its raw form is called the Plainjoke, and after encryption is called the Cipherjoke or Cryptojoke.

Cipherjokes are intelligible of course only after Decryption, or as some people call it, after explanation.

There are three kinds of attack on an unintelligible cryptojoke according to the Jokeanalyst's resources.

Firstly there is the Cipherjoke-only attack in which the Jokeanalyst is assumed to have unlimited amounts of material which is alleged to be funny.

Secondly and more powerfully there is the Known Plainjoke Attack in which he is given examples of jokes together with their explanations.

But most powerful of all is the Chosen Plainjoke Attack where he gets to ask the Cryptolaffer to explain WHY the joke is funny.

Feeble jokes are usually encrypted using only a very simple cipher, like changing the punch line. This is called the DEFLECTED ENDING SYSTEM or DES.

Very good jokes, the comprehension of which by outsiders could constitute a threat to national security, are encrypted much more securely, usually by completely changing the scenario, the plot and the conclusion. This is the PARTICULARLY KLEVER COVERUP or PKC.

The best known PKC RESISTS SERIOUS ATTACK and is therefore called the RSA.

As a corollary of course, it follows that only very gifted, intelligent people can truly appreciate a funny speech.

Standardisation

Since it is difficult to design a good cipher, and since the apparatus is very expensive, a lot of work has been done recently to try to standardise on them. Even as I speak the International Standards Organization is meeting to decide on this very issue. Since there is a lot of confusion on this point I have been asked to make the position clear. The purpose of language is to convey information. This only works if both sender and receiver of information both use the same system. In other words language only works precisely because it is standardised.

The purpose of cryptography on the other hand is to make the message unintelligible except to one person. In other words cryptography only works precisely because it is NOT standardised.

So what they do is to make most of the cipher standardised, and to concentrate the non-standardization into one part called the key.

So far so good. But of course the key, the non-standardised part, must be nonstandard in only standardised ways. And also key management must conform to certain standards. In other words standards are being formulated whereby the nonstandard parts, which must conform to certain standards of non-standardization are also to be handled only in a standardised nonstandard way in order to standardise on the overall non-standardization.

I hope this makes the position clear.

Weak keys

Many cipher have certain bad keys. If you use one of them the cipher is easily broken. For instance all-zeros is a weak key for the DES. There has been a lot of research done into searching for weak keys. Over the years more and more weak keys have been found till now one has to be quite careful to avoid them.

Perhaps it would be a better idea if we looked for strong keys. In fact why not look for THE STRONGEST POSSIBLE KEY. Then we could all standardise on it.

Processing delay

Coding theory is not without its problems. The introduction of source coding, channel coding and secrecy coding often introduces something called PROCESSING DELAY. This is the delay caused by the time it takes to do all this coding and decoding. These delays can be enormous. History gives us instances when this delay has changed the course of world events. There is a recorded case of a two-word military signal which suffered a processing delay of 150 years. The message, deciphered at the Pentagon in 1972 simply read

"Send Reinforcements"

It was sent on 1830 from Little Bighorn by General Custer.

Consider the message:

"Return home at once, trip cancelled."

and think of the effect on world events if it had been decoded in time. It was sent in 1492 by Isobella of Spain to Christopher Columbus.