Breaking codes: An impossible task?

dod

http://news.bbc.co.uk/2/hi/technology/3804895.stm

Breaking codes: An impossible task?

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 organisation.

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 codebreaker."

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.

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.

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.

"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 programmes.

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

Gavin

A fairly flimsy and vague article. Surprising to see the BBC producing crap like that.

Gav

ecksor

Why? Some of the assertions are open to question (i.e, we don't actually know what the security agencies know or don't know no matter what rumours we've heard) but factually it seems pretty accurate.

Gavin

Ok, I admit I exaggerated a bit. The vague comments at the top seemed there to create a more sensationalist article.

The reports, from Washington,

eh ? That is just a tad vague.

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

That's slightly suspicious. An official privy to such info is unlikely to get drunk with an iraqi leader surely..

And also he offended me when he talked about asymmetric encryption and mentioned 128 bit keys. Unfortunately I seem to be turning into an internet pedant. It's all downhill from here.

tribble

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.

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.

This is the most muddled explaination I have heard todate.

tribble

ecksor

Have you seen better explanations? Not meaning to poke or nitpick, just curious. The one above seems to be trying to explain without giving details which is always a tricky thing to do I guess.

Capt'n Midnight

Of course the Iranians might have been deliberatly "leaking" data.

And if you had managed to get your hands on the recipients key...

Then there is the WEP type problem - if an encryption algorithm is not porperly implemented or is inherently weak then it might be easier to find the key then you'd think.

Martyr

Originally posted by ecksor
we don't actually know what the security agencies know or don't know no matter what rumours we've heard

very true, some need to remember that security agencies aren't going to tell
the general public what flaws or weaknesses they know about
in encryption algorithms.
they're not gonna release details of how they decode encrypted messages,
thats just stupid, in my opinion anyway, it would be irresponsible to
do that, when they are trying to combat terrorism and snoop
on other countries..for perhaps economic reasons.

Even if you look at Fortezza, when SkipJack was classified, most cryptographers
could already assume that it would not have any strong features
in its design, incase it were reverse-engineered, and they were right.

I don't see the point in U.S allowing for export of encryption
that an agency like the NSA couldn't crack easily.

Sort of leaves them & their country vulnerable to any possible
terrorist that might want to use encryption for communication.

Capt'n Midnight

Originally posted by Average Joe
I don't see the point in U.S allowing for export of encryption that an agency like the NSA couldn't crack easily.

Sort of leaves them & their country vulnerable to any possible terrorist that might want to use encryption for communication.

Like they had a choice - the rest of the planet was able to use crypto programs developed outside the USA, and of course the NSA would less of a chance for backdoors. Also most terrorism in the US is home grown (look at the number of murders - a 9/11 every month) and of course they would already have the full lot. Actually most of the terrorism the US is involved with is state scantioned - ie. killing of innocents by US military interventions , regime changes by CIA etc. - except the victims ain't US voters.

as for economic reasons - that's what echelon is for.

Again by denying export of strong encryption you also block exportation of backdoors.