Page 51 of 56
And you can help:
The M4 Project is an effort to break 3 original Enigma messages with the help of distributed computing. The signals were intercepted in the North Atlantic in 1942 and are believed to be unbroken.
EDITED TO ADD (3/8): One message has been broken.
Here’s an interesting rebuttal of Laszlo Kish’s theoretically secure classical communications scheme.
EDITED TO ADD (2/18): Kish’s response.
I get e-mail, occasionally weird e-mail. Every once in a while I get an e-mail like this:
I know this is going to sound like a plot from a movie. It isn’t. A very good friend of mine Linda Rayburn and her son Michael Berry were brutally murdered by her husband…the son’s stepfather.
They were murdered on February 3rd, 2004. He then hung himself in the basement of their house. He left behind a number of disturbing items.
However, the most intriguing is a cryptogram handwritten on paper utilizing letters, numbers and symbols from a computer keyboard. Linda’s daughter Jenn was the one who found the bodies. Jenn is a very good friend of mine and I told her I would do everything within my power to see if this cryptogram is truly a cryptogram with valuable information or if it is a wild goose chase to keep us occupied and wondering forever what it means.
I have no idea if any of this is true, but here’s a news blip from 2004:
Feb. 2: Linda Rayburn, 44, and Michael Berry, 23, of Saugus, both killed at home. According to police, Rayburn’s husband, David Rayburn, killed his wife and stepson with a hammer. Their bodies were found in adjacent bedrooms. David Rayburn left a suicide note, went to the basement, and hanged himself.
And here is the cryptogram:
The rectangle drawn over the top two lines was not done by the murderer. It was done by a family member afterwards.
Assuming this is all real, it’s a real-world puzzle with no solution. No one knows what the message is, or even if there is a message.
If anyone figures it out, please let me know.
Super Cipher P2P Messenger uses “unbreakable Infinity bit Triple Layer Socket Encryption for completely secure communication.”
Wow. That sure sounds secure.
EDITED TO ADD (2/15): More humor from their website:
Combining today’s most advanced encryption techniques, and expanding on them. The maximum encryption cipher size is Infinity! Which means each bit of your file or message is encrypted uniquely, with no repetition. You define a short key in the program, this key is used in an algorithm to generate the Random Infinity bit Triple Cipher. Every time you send a message or file, even if it is exactly the same, the Triple Cipher completely changes; hence then name ‘Random’. Using this method a hackers chances of decoding your messages or file is one to infinity. In fact, I challenge anyone in the world to try and break a single encrypted message; because it can’t be done. Brute Force and pattern searching will never work. The Encryption method Super Cipher P2P Messenger uses is unbreakable.
Last month, researchers found the 43rd Mersenne Prime: 230,402,457-1. It’s 9,152,052 decimal digits long.
This is a great use of massively parallel computing:
The 700 campus computers are part of an international grid called PrimeNet, consisting of 70,000 networked computers in virtually every time zone of the world. PrimeNet organizes the parallel number crunching to create a virtual supercomputer running 24×7 at 18 trillion calculations per second, or ‘teraflops.’ This greatly accelerates the search. This prime, found in just 10 months, would have taken 4,500 years on a single PC.
Interesting interview:
Federico Biancuzzi interviews OpenSSH developer Damien Miller to discuss features included in the upcoming version 4.3, public key crypto protocols details, timing based attacks and anti-worm measures.
My eighth Wired column:
How would you feel if you invested millions of dollars in quantum cryptography, and then learned that you could do the same thing with a few 25-cent Radio Shack components?
I’m exaggerating a little here, but if a new idea out of Texas A&M University turns out to be secure, we’ve come close.
Earlier this month, Laszlo Kish proposed securing a communications link, like a phone or computer line, with a pair of resistors. By adding electronic noise, or using the natural thermal noise of the resistors—called “Johnson noise”—Kish can prevent eavesdroppers from listening in.
In the blue-sky field of quantum cryptography, the strange physics of the subatomic world are harnessed to create a secure, unbreakable communications channel between two points. Kish’s research is intriguing, in part, because it uses the simpler properties of classic physics—the stuff you learned in high school—to achieve the same results.
At least, that’s the theory.
I go on to describe how the system works, and then discuss the security:
There hasn’t been enough analysis. I certainly don’t know enough electrical engineering to know whether there is any clever way to eavesdrop on Kish’s scheme. And I’m sure Kish doesn’t know enough security to know that, either. The physics and stochastic mathematics look good, but all sorts of security problems crop up when you try to actually build and operate something like this.
It’s definitely an idea worth exploring, and it’ll take people with expertise in both security and electrical engineering to fully vet the system.
There are practical problems with the system, though. The bandwidth the system can handle appears very limited. The paper gives the bandwidth-distance product as 2 x 106 meter-Hz. This means that over a 1-kilometer link, you can only send at 2,000 bps. A dialup modem from 1985 is faster. Even with a fat 500-pair cable you’re still limited to 1 million bps over 1 kilometer.
And multi-wire cables have their own problems; there are all sorts of cable-capacitance and cross-talk issues with that sort of link. Phone companies really hate those high-density cables, because of how long it takes to terminate or splice them.
Even more basic: It’s vulnerable to man-in-the-middle attacks. Someone who can intercept and modify messages in transit can break the security. This means you need an authenticated channel to make it work—a link that guarantees you’re talking to the person you think you’re talking to. How often in the real world do we have a wire that is authenticated but not confidential? Not very often.
Generally, if you can eavesdrop you can also mount active attacks. But this scheme only defends against passive eavesdropping.
For those keeping score, that’s four practical problems: It’s only link encryption and not end-to-end, it’s bandwidth-limited (but may be enough for key exchange), it works best for short ranges and it requires authentication to make it work. I can envision some specialized circumstances where this might be useful, but they’re few and far between.
But quantum key distributions have the same problems. Basically, if Kish’s scheme is secure, it’s superior to quantum communications in every respect: price, maintenance, speed, vibration, thermal resistance and so on.
Both this and the quantum solution share another problem, however; they’re solutions looking for a problem. In the realm of security, encryption is the one thing we already do pretty well. Focusing on encryption is like sticking a tall stake in the ground and hoping the enemy runs right into it, instead of building a wide wall.
Arguing about whether this kind of thing is more secure than AES—the United States’ national encryption standard—is like arguing about whether the stake should be a mile tall or a mile and a half tall. However tall it is, the enemy is going to go around the stake.
Software security, network security, operating system security, user interface—these are the hard security problems. Replacing AES with this kind of thing won’t make anything more secure, because all the other parts of the security system are so much worse.
This is not to belittle the research. I think information-theoretic security is important, regardless of practicality. And I’m thrilled that an easy-to-build classical system can work as well as a sexy, media-hyped quantum cryptosystem. But don’t throw away your crypto software yet.
Here’s the press release, here’s the paper, and here’s the Slashdot thread.
EDITED TO ADD (1/31): Here’s an interesting rebuttal.
Snake-oil isn’t only in commercial products. Here’s a piece of research published (behind a paywall) in Nature that’s just full of it.
The article suggests using chaos in an electro-optical system to generate a pseudo-random light sequence, which is then added to the message to protect it from interception. Now, the idea of using chaos to build encryption systems has been tried many times in the cryptographic community, and has always failed. But the authors of the Nature article show no signs of familiarity with prior cryptographic work.
The published system has the obvious problem that it does not include any form of message authentication, so it will be trivial to send spoofed messages or tamper with messages while they are in transit.
But a closer examination of the paper’s figures suggests a far more fundamental problem. There’s no key. Anyone with a valid receiver can decode the ciphertext. No key equals no security, and what you have left is a totally broken system.
I e-mailed Claudio R. Mirasso, the corresponding author, about the lack of any key, and got this reply: “To extract the message from the chaotic carrier you need to replicate the carrier itself. This can only be done by a laser that matches the emitter characteristics within, let’s say, within 2-5%. Semiconductor lasers with such similarity have to be carefully selected from the same wafer. Even though you have to test them because they can still be too different and do not synchronize. We talk abut a hardware key. Also the operating conditions (current, feedback length and coupling strength) are part of the key.”
Let me translate that. He’s saying that there is a hardware key baked into the system at fabrication. (It comes from manufacturing deviations in the lasers.) There’s no way to change the key in the field. There’s no way to recover security if any of the transmitters/receivers are lost or stolen. And they don’t know how hard it would be for an attacker to build a compatible receiver, or even a tunable receiver that could listen to a variety of encodings.
This paper would never get past peer review in any competent cryptography journal or conference. I’m surprised it was accepted in Nature, a fiercely competitive journal. I don’t know why Nature is taking articles on topics that are outside its usual competence, but it looks to me like Nature got burnt here by a lack of expertise in the area.
To be fair, the paper very carefully skirts the issue of security, and claims hardly anything: “Additionally, chaotic carriers offer a certain degree of intrinsic privacy, which could complement (via robust hardware encryption) both classical (software based) and quantum cryptography systems.” Now that “certain degree of intrinsic privacy” is approximately zero. But other than that, they’re very careful how they word their claims.
For instance, the abstract says: “Chaotic signals have been proposed as broadband information carriers with the potential of providing a high level of robustness and privacy in data transmission.” But there’s no disclosure that this proposal is bogus, from a privacy perspective. And the next-to-last paragraph says “Building on this, it should be possible to develop reliable cost-effective secure communication systems that exploit deeper properties of chaotic dynamics.” No disclosure that “chaotic dynamics” is actually irrelevant to the “secure” part. The last paragraph talks about “smart encryption techniques” (referencing a paper that talks about chaos encryption), “developing active eavesdropper-evasion strategies” (whatever that means), and so on. It’s just enough that if you don’t parse their words carefully and don’t already know the area well, you might come away with the impression that this is a major advance in secure communications. It seems as if it would have helped to have a more careful disclaimer.
Communications security was listed as one of the motivations for studying this communications technique. To list this as a motivation, without explaining that their experimental setup is actually useless for communications security, is questionable at best.
Meanwhile, the press has written articles that convey the wrong impression. Science News has an article that lauds this as a big achievement for communications privacy.
It talks about it as a “new encryption strategy,” “chaos-encrypted communication,” “1 gigabyte of chaos-encrypted information per second.” It’s obvious that the communications security aspect is what Science News is writing about. If the authors knew that their scheme is useless for communications security, they didn’t explain that very well.
There is also a New Scientist article titled “Let chaos keep your secrets safe” that characterizes this as a “new cryptographic technique, ” but I can’t get a copy of the full article.
Here are two more articles that discuss its security benefits. In the latter, Mirasso says “the main task we have for the future” is to “define, test, and calibrate the security that our system can offer.”
And their project web page says that “the continuous increase of computer speed threatens the safety” of traditional cryptography (which is bogus) and suggests using physical-layer chaos as a way to solve this. That’s listed as the goal of the project.
There’s a lesson here. This is research undertaken by researchers with no prior track record in cryptography, submitted to a journal with no background in cryptography, and reviewed by reviewers with who knows what kind of experience in cryptography. Cryptography is a subtle subject, and trying to design new cryptosystems without the necessary experience and training in the field is a quick route to insecurity.
And what’s up with Nature? Cryptographers with no training in physics know better than to think they are competent to evaluate physics research. If a physics paper were submitted to a cryptography journal, the authors would likely be gently redirected to a physics journal—we wouldn’t want our cryptography conferences to accept a paper on a subject they aren’t competent to evaluate. Why would Nature expect the situation to be any different when physicists try to do cryptography research?
Recently I have been hearing some odd “Twofish has been broken” rumors. I thought I’d quell them once and for all.
Rumors of the death of Twofish has been greatly exaggerated.
The analysis in question is by Shiho Moriai and Yiqun Lisa Yin, who published their results in Japan in 2000. Recently, someone either got a copy of the paper or heard about the results, and rumors started spreading.
Here’s the actual paper. It presents no cryptanalytic attacks, only some hypothesized differential characteristics. Moriai and Yin discovered byte-sized truncated differentials for 12- and 16-round Twofish (the full cipher has 16 rounds), but were unable to use them in any sort of attack. They also discovered a larger, 5-round truncated differential. No one has been able to convert these differentials into an attack, and Twofish is nowhere near broken. On the other hand, they are excellent and interesting results—and it’s a really good paper.
In more detail, here are the paper’s three results:
One possible interpretation of their result would be to conjecture that the 2nd byte of ciphertext difference will be 0 with probability 2-8 + 2-40.9 for Twofish, but only 2-8 for an ideal cipher. Their characteristic is just one path. If one is lucky, perhaps all other paths behave randomly and contribute an additional 2-8 factor to the total probability of getting a 0 in the 2nd byte of ciphertext difference. Perhaps. One might conjecture that, anyway.
It is not at all clear whether this conjecture is true, and the authors are careful not to claim it. If it were true, it might lead to a theoretical distinguishing attack using 275 chosen plaintexts or so (very rough estimate). But I’m not at all sure that the conjecture is true.
Analogously to the first result, one might conjecture that the 2nd byte of the ciphertext difference will be 0 with probability 2-8 + 2-57.3 for Twofish, but probability 2-8 for an ideal cipher. If this were true, one might be able to mount a distinguishing attack with 2100 chosen plaintexts or so (another very rough estimate). But I have no idea whether the conjecture is true.
The paper theorizes that all of these characteristics might be useful in an attack, but I would be very careful about drawing any conclusions. It can be very tricky to go from single-path characteristics whose probability is much smaller than the chances of it happening by chance in an ideal cipher, to a real attack. The problem is in the part where you say “let’s just assume all other paths behave randomly.” Often the other paths do not behave randomly, and attacks that look promising fall flat on their faces.
We simply don’t know whether these truncated differentials would be useful in a distinguishing attack. But what we do know is that even if everything works out perfectly to the cryptanalyst’s benefit, and if an attack is possible, then such an attack is likely to require a totally unrealistic number of chosen plaintexts. 2100 plaintexts is something like a billion billion DVDs’ worth of data, or a T1 line running for a million times the age of the universe. (Note that these numbers might be off by a factor of 1,000 or so. But honestly, who cares? The numbers are so huge as to be irrelevent.) And even with all that data, a distinguishing attack is not the same as a key recovery attack.
Again, I am not trying to belittle the results. Moriai and Yin did some great work here, and they deserve all kinds of credit for it. But even from a theoretical perspective, Twofish isn’t even remotely broken. There have been no extensions to these results since they were published five years ago. The best Twofish cryptanalysis is still the work we did during the design process: available on the Twofish home page.
A team at the German Federal Agency for Information Technology Security has factored a 193-digit number. (Note that this is not a record; in May a 200-digit number was factored. But there’s a cash prize associated with this one.)
The links do a good job explaining the news and giving context.
Sidebar photo of Bruce Schneier by Joe MacInnis.