Breaking codes: An impossible task?

Breaking codes: An impossible task?
BBC News Online

 

Recent reports that the United States had broken codes used by the Iranian
intelligence service have intrigued experts on cryptology because a modern
cipher should be unbreakable.
Four leading British experts told BBC News Online that the story, if true,
points to an operating failure by the Iranians or a backdoor way in by the
National Security Agency (NSA) - the American electronic intelligence
organization.

 

The reports, from Washington, suggested that the Iranians had been tipped
off by Ahmed Chalabi, an Iraqi political leader with links to Iran.

 

He is said to have learned about the code-breaking from an American official
who was drunk.

 

Simon Singh, author of "The Code Book", a history of codes, said: "Modern
codes are effectively unbreakable, very cheap and widely available. I could
send an email today and all the world's secret services using all the
computers in the world would not be able to break it. The code maker
definitely has a huge advantage over the code breaker."

 

The reason for this is that an encoded text is so complex that it can resist
all efforts to break it.

 

The key to codes

 

It is probable, though not certain of course, that Iran was using what's
called public-private key or asymmetric cryptography. In this system, the
message is encoded by someone using a freely distributed public key. This
can be decoded only by someone using a different private key.

 

Modern codes are effectively unbreakable, very cheap and widely available
Simon Singh
The public-private key method has largely taken over from the purely private
or symmetric system in which the sender and receiver use the same key to
encrypt and decrypt a message.

 

Some ciphers use a mixture. A private key encrypts and decrypts the message
because this way is less complicated and therefore quicker but the key
itself is sent by the public-private method.

 

Professor Alistair Fitt, head of the School of Mathematics at Southampton
University, said: "The private-private key is seen as obsolete. The
public-private key is better. It does away with the problem of transporting
the key between the two parties."

 

I asked Professor Fitt if he would feel confident of using it if he was an
intelligence chief. He replied "Yes."

 

Too hard to crack

 

Take a public key based on a huge number which is the result of two prime
numbers multiplied together (a prime number being one which can be divided
only by itself or by one). You use this number to encode your message but
you do not need to know the two original prime numbers. Only the person
decoding the message needs to know, because the text was encoded using an
equation and both numbers are needed to reverse that equation.

 

You design the numbers so that if you have more computers than there are in
the world and you run them for ever, they are not enough
Professor Alistair Fitt
The system is safe because it is a curious feature of mathematics that when
two prime numbers are multiplied, it is very difficult to factor, that is to
work out, the two original numbers. Mathematicians have been trying to find
a way to do this quickly for hundreds of years and have failed so far.
Since even computers take time to wade their way through all prime numbers
to find the correct ones, it has been estimated that, if the number is big
enough, the world could end before they succeed. A guess would have a better
chance.

 

A large key

 

The text to be enciphered is basically converted into numbers to which a
numerical key is applied in a mathematical formula. It is important that the
key has enough numbers to keep it safe but not enough to slow the whole
process down too much.

 

Professor Fitt commented: "If you are making a code, you design the numbers
so that if you have more computers than there are in the world and you run
them for ever, they are not enough."

 

The current assessment is that a key containing 128-bits (the binary units
used by computers) is safe.
In a web article "Encryption Basics", Jonathan Hassell of Soho Security said
that it was "extremely difficult and time-consuming" to determine the key
because the numbers were so big: "Mathematically, 128-bit numbers have
3,402,823,669,209,384,634,633,746,074,300,000,
000,000,000,000,000,000,000,000,000,000,000 possible combinations for the
numerical sequence."

 

A decade ago, a key of 40 or 56-bits was thought to be secure from what is
called a brute attack by computers but no longer so.

 

Note that the increase in bits is exponential, because each bit doubles the
total. 128-bits is 309,485,009,821,345,068,724,781,056 times larger than 40.

 

Seeking another answer

 

You can see that the code breakers, or cryptanalysts, have to find some
other solution.

 

Ross Anderson of the Computer Laboratory at Cambridge University pointed to
some of them: "As the former chief scientist of the NSA once remarked at one
of our security workshops, almost all breaks of cipher systems are due to
implementation errors, operational failures, burglary, blackmail and
bribery.

 

There is a difference between breaking a code and breaking a system
Professor Fred Piper
"As for cryptanalysis, it happens, but very much less often than most people
think."
Professor Fred Piper of the Royal Holloway College made the same point
strongly: "There is a difference between breaking a code and breaking a
system.

 

"In general it is true that a system using a practically unbreakable cipher
might be broken though a management fault."

 

The three B's

 

Such faults might include lazy operating procedures or even leaving your key
around on a CD which someone else could read.

 

This is reminiscent of one of the ways the German Enigma codes were broken
during World War II. One German operator always used the name of his
girlfriend Cillie to send a test message. Thereafter the British
code-breakers called all such vulnerable messages "cillies."

 

The three "Bs" - burglary, blackmail and bribery - might have to be employed
if there is no other way of getting at the key. We are back to the world of
spies.

 

Perhaps the need to find keys was what lay behind the former British MI5
agent Peter Wright's revelation in his book "Spycatcher" that he "bugged and
burgled" his way across London.

 

Hidden software

 

Simon Singh says that sometimes there is a backdoor way in through
deliberately corrupted software: "There is always the chance of human error.
Encryption requires a key, and if I get hold of your key then I can read
your messages. Or if I plant some software in I get to see the message
before you encrypt it."

 

Software allowing decryption is known to have been implanted in some ciphers
in the past. In his book "Security Engineering", Ross Anderson tells the
story of how this happened in Sweden: "The Swedish government got upset when
they learned that the 'export version' of Lotus Notes which they used widely
in public service had its cryptography deliberately weakened to allow NSA
access."

 

In another case, intriguingly involving Iran, Ross Anderson reported: "A
salesman for the Swiss firm Crypto AG was arrested in Iran in 1992 and the
authorities accused him of selling them cipher machines which had been
tampered with so that the NSA could get at the plaintext. After he had spent
some time in prison, Crypto AG paid about a $1m to bail him but then fired
him once he got back to Switzerland."

 

Whether something similar happened in this case involving Iran is simply not
known.

 

The internet - is it secure?

 

All this has important implications, incidentally, for internet security.
When you enter a secure area on the internet, to buy something for example,
you are using an encryption system.

 

Professor Alistair Fitt says that the internet codes are safe: "I do not
understand why some people do not trust the internet yet they give their
credit card to some waiter who disappears with it into a back room."

 

You can also use 128-bit encryption for your e-mails. This used not to be
the case. It was only in 2000 that the United States lifted most export
controls on strong encryption programs.

 

Using such encryption, your e-mails should be safe. Unless what apparently
happened to the Iranians happens to you.

 

Story from BBC NEWS:
http://news.bbc.co.uk/go/pr/fr/-/2/hi/technology/3804895.stm