Emergent Chaos

Quantum Debate

The debate about Shor's Algorithm (which I blogged about a couple days ago) continues. Rod Van Meter has a good blog post about it here.

While there are plenty of people who have just wholesale dismissed the Hill/Viamontes paper outright, apparently because they know Shor's algorithm works and that building a working quantum computer is obviously merely a matter of making some qubits, Van Meter is more to my thinking about the whole thing.

I have read it, but not studied it in major detail yet. I don't know either of the authors personally, but the second author has done good work; he is certainly no dummy.

The argument is pretty straightforward, arguably naive. That doesn't mean it's wrong, but there are a lot of assumptions and simplifications in the work, and they need to be examined carefully.

He also says:

Anyway, I hope this at least short-circuits any rush to burn Peter Shor in effigy. He's way too smart and sweet for that.

Here's where I think I need to rant a bit. I'm certainly not calling for anyone to be burned in effigy or reality. I can't testify to how sweet Peter Shor is, but I agree that he's brilliant and I admire him.

However, Leibniz was also smart and worked in the forefront of calculation as well. His calculator had issues with propagating carry with two-digit or three-digit multipliers. That doesn't make Leibniz any less brilliant or his achievements any less.

Peter Shor is brilliant, and his algorithms are marvelous works. If no one implements them, for whatever reasons, they won't be any less marvelous, and he won't be any less brilliant.

And for that matter, Hill and Viamonthes may turn out to be wrong, too. Or they may inspire someone to a tweak that makes Shor's algorithm work (or work better).

The present spectator sport is how science works. It's what makes it exciting.

Quantum Uncertainty

Technology Review has a pair of articles on D-Wave's adiabatic quantum computer. Quantum pioneer Seth Lloyd writes in "Riding D-Wave" about quantum computing in general, adiabatic quantum computing, and D-Wave's efforts to show that they've actually built a quantum computer.

Linked to that is Scott Aaronson's article, "Desultory D-Wave," in which Lloyd's nail-biting is made a bit more plain. I hate giving away the punch line, but here's what Aaronson sums up with:

Let me be clear: I think that quantum computers are possible in principle, and that D-Wave's approach might even get us there. I've also met people from D‑Wave; I don't think they're frauds. But the human capacity for self-deception being what it is, scientists train themselves to look for red flags--and D-Wave is pretty much a red-flag factory.

Beyond that, there's a new paper that shows problems not in just one implementation of quantum computing, but about its very theoretical core. In "Operator Imprecision and Scaling of Shor's Algorithm," authors C. Ray Hill and George F. Viamontes claim that Shor's Algorithm doesn't work at an interesting scale.

The reason is that errors in the quantum fourier transforms accumulate faster than quantum error correcting codes can get rid of them, particularly when factoring the sort of numbers that a sane person might use for a public key. Hill and Viamontes seem to think that it is not possible to factor a key much more than 256 bits in length. Most importantly of all, the errors accumulate linearly with the number of quantum operations and the number of operations increases polynomially with the size of the integer. My peeks at the error rate graph lead me to guess that a hard limit is reached before you get to a 512-bit number, which is no longer considered interesting using conventional sieve methods.

Here is their abstract:

Shor's algorithm (SA) is a quantum algorithm for factoring integers. Since SA has polynomial complexity while the best classical factoring algorithms are sub-exponential, SA is cited as evidence that quantum computers are more powerful than classical computers. SA is critically dependent on the Quantum Fourier Transform (QFT) and it is known that the QFT is sensitive to errors in the quantum state input to it. In this paper, we show that the polynomial scaling of SA is destroyed by input errors to the QFT part of the algorithm. We also show that Quantum Error Correcting Codes (QECC) are not capable of suppressing errors due to operator imprecision and that propagation of operator precision errors is sufficient to severely degrade the effectiveness of SA. Additionally we show that operator imprecision in the error correction circuit for the Calderbank-Shor-Steane QECC is mathematically equivalent to decoherence on every physical qubit in a register. We conclude that, because of the effect of operator precision errors, it is likely that physically realizable quantum computers will be capable of factoring integers no more efficiently than classical computers.

Hill and Viamontes also claim that this brings up a serious question about quantum computing in general. Take a deep breath and read this:

It is natural to ask whether these results have wider implications about the power of quantum computers relative to classical computers. While the results presented in this paper do not answer this question definitively, it is important to note the singular stature of Shor’s algorithm as the only quantum algorithm that appears to efficiently solve a classically intractable problem. The fact that Shor’s algorithm is not more efficient than classical algorithms removes the only strong evidence for the superior computational power of quantum computers relative to classical computers.

Wow. They have by no means the last word on this, but this means that quantum computing is going to get much more interesting as a spectator sport. And perhaps this fall's Post-Quantum Cryptography workshop will be a little less interesting.

Security Metric?

Ross Anderson has made PDF versions of several chapters of his Security Engineering (second edition) available on-line. The entire first edition has been available for some time.

I am sure this second edition will be outstanding. I would rank the first edition as one of the top three technical books I've read. It would likely be number one. I have high expectations for the second edition, stemming in large part from the author's academic discipline.

How many security titles have a 104 page bibliography?

Quantum Cryptography Broken and Fixed

Researchers at Linköping University in Sweden have found flaws in quantum cryptography. They also supply a fix. The announcement is here; a FAQ is here; full paper is at the IEEE here (but requires an IEEE membership).

The announcement says:

Jan-Åke Larsson, associate professor of applied mathematics at Linköping University, working with his student Jörgen Cederlöf, has shown that not even quantum cryptography is 100-percent secure. There is a theoretical possibility that an unauthorized person can extract the key without being discovered, by simultaneously manipulating both the quantum-mechanical and the regular communication needed in quantum cryptography.

Interestingly, the fix is to add some random bits into the channel. My understanding (I haven't read the paper, just the announcement and the FAQ) is that this effectively adds a nonce to the protocol. I am amused that even an allegedly pure-physics security system needs a software patch.

This brings up an interesting question, though -- if, with all its hype, quantum cryptography is not 100% secure, how secure is it? Is it 99.999999999999% secure? And why wouldn't you just use 256-bit conventional crypto on a pair of IPsec routers you bought at Fry's instead?

The FDIC's Cyber Fraud Report

The FDIC's Division of Supervision and Consumer Protection didn't release a report titled "Cyber Fraud and Financial Crime" on November 9, 2007. That release was left to Brian Krebs, a reporter with the Washington Post, in early March, who blogged about it in "Banks: Losses From Computer Intrusions Up in 2007" and "The FDIC Computer Intrusion Report."

One of the great things about having the full report is that we don't need to rely on Brian to interpret it for us. I love having data, and hate how rare it is for people who work in information security to have anything but summaries.

I found a couple of things interesting. At first they seem un-related:

• The largest category is mortgage fraud, costing roughly $600MM in the 2nd quarter of 2007, and up 15% from Q1.
• The second largest is check fraud. Check fraud is up, according to the FDIC (page 9) because the "Check21" program which sends images (rather than physical checks) is not sensitive enough to show watermarks or alteration detection by chemicals in the paper.

Both are really about risk tradeoffs, and it seems that with the rise in employment as a short term deal, the organizations become more focused on the short-term. [Updated: clarified that sentence a little.]

An example is the "zippy" memo, where JPMorgan Chase employees traded information about how to fool the computer into approving loans. (See "How to Get an "Iffy" loan approved at JPM Chase," or "Chase mortgage memo pushes 'Cheats & Tricks.'" Chase fired at least one person for distributing it.)

The advice included:

1. Lump all of an applicant's compensation as the applicant's base income, rather than breaking out commissions, bonuses and tips.
2. Do not disclose use of gifts for down payments.
3. If all else fails, simply inflate the applicant's income. "Inch it up $500 to see if you can get the findings you want. Do the same for assets.

Now, any security professional worth their salt can come up, post-facto, with fixes for each of these behaviors that prevent or detect them. But the real problem is that the commission isn't paid over the life of the loan, it's paid up front. Of course people are going to find ways to get the loans approved, and not worry about what happens next. Your community banker didn't actually get bonuses over the life of the loan, but did expect to be with the bank when a problem happened.

As long as (as Martin Wolff says) "no industry has a comparable talent for privatising gains and socialising losses," we should expect to be unpleasantly surprised by reading about bank fraud. (A bit more context on the Wolff quote can be found in this excerpt.)

More Hardware Security Shown to be Bunk

After showing that "encrypted" disk drives only encrypted the password you use, not the data, Heise-Online now shows that fingerprint-access is often bunk:

Manufacturers of USB sticks and cards with fingerprint readers promise us that their data safes can only be opened with the right fingerprint. It turns out that an easy-to-find tool allows nosy parties to get around the protection in some products.

Basically, all you have to do is get a low-level USB tool, PLscsi, and have it tell the device to ignore all that security stuff. Yes, I'm over-simplifying, but I'm disgusted. Read the article for details.

I got a rockin' pneumonia, I need a jolt of arrythmic blues!

By now, you've probably seen the news that "A Heart Device Is Found Vulnerable to Hacker Attacks." Bruce Schneier has some good analysis, "Hacking Medical Devices." I just wanted to shock Jerry Lee Lewis fans.

Diebold Accidentally Leaks Results Of 2008 Election Early

Diebold Accidentally Leaks Results Of 2008 Election Early

Economist Debates Security V Privacy

The Economist emails:

Our second series of three debates kicks off today and the first proposition raises important questions about civil rights and the trade-off between Privacy vs. Security. As a blogger and member of the community that The Economist aims to serve with this lively debate, we wanted to extend an invitation to you and the readers of Emergent Chaos to join the debate by blogging or commenting to the debate floor. (No subscription is necessary).

The debate: "Proposition: Security in the modern age cannot be established without some erosion of individual privacy."

Have at Mr. Livingstone, arguing for the side of order and no emergent chaos, or, if you must, Mr. Barr, on the side of truth, justice, and the American way.

How To Fly With An Expired License

Yahoo news recently reported the story of Charleston, West Virginia Mayor Danny Jones who used a photo of himself in a magazine to prove his identity. In brief, he was flying out of John Wayne Airport and his drivers license was expired so he wasn't going to be allowed to get past security. The Charleston Daily Mail adds that the same license was sufficient to allow him to check his bags. However, Mayor Jones did have a copy of a magazine that had a photo of him in downtown Charleston which was deemed by the local agents to sufficient ID. So, what we have (quelle surprise!) is inconsistency in how security is applied between the ticket agents and the security guards, security guards who didn't seem to properly understand the process of handling people without proper ID and finally agents who were willing to accept a worse form of ID than an expired drivers license. I feel safer, how about you?

A Cha-cha all the way to the bank

On the beaches of Mexico, they're talking about Copacabana, a new cipher-cracker that works on DES and other ciphers with a 64-bit key. Yes, this has been done before, but this is interesting for a number of reasons.

First is the price. About €9,000. Second, there's the performance. A complete DES keyspace sweep in a fortnight. That's not bad. If you think about Deep Crack and what you'd expect from normal semiconductor advances.

The news, however, is that apparently there are banks using two-factor authentication tokens with DES-based keys, and if you're clever, you can break this token with far less than a full key search. You only need to observe the supposedly one-time password (or two or three of them), and then with a fortnight's of computing, you can generate any one-time password the real owner can.

Maddeningly, there are other systems based on AES or some other crypto that aren't at all vulnerable to this attack -- because they have better keys. People who are vulnerable to this attack need not be.

Apparently, these banks have fallen in love with DES. But falling in love is dangerous. It's also negligent, when it's so easy to get shot.

Photo courtesy of Imagem Compartilhada.

Stupid Safety Feature Of The Week

I love my Prius. It's fun to drive, eco-friendly and even has lots of geek appeal. However it has one incredibly moronic safety feature which I was reminded of while driving through the snow the other day. Now I have the base model which means I don't have fancy features like the automatic skid prevention. Instead, what I have is a flashing light. When the wheels lose traction, a little icon starts flashing on the dashboard. Now that's what's useful, a distraction as the car starts to slide. More of a danger than anything else. Maybe next time, they can add an audible alarm as well. Then the car will feel even more like an airplane cockpit....

Banksy Would Be Proud

In a feat that would make Banksy proud, members of Untergunther, who the Guardian calls "cultural guerrillas", restored the antique clock at the Panthéon. They spent about a year, beginning in September of 2005, in a hidden workshop, dismantling and rebuilding the entire clockwork which had been abandoned in the 1960s. They were never discovered despite having taped into the electrical and network systems.

Getting into the building was the easiest part, according to Klausmann. The squad allowed themselves to be locked into the Panthéon one night, and then identified a side entrance near some stairs leading up to their future hiding place. "Opening a lock is the easiest thing for a clockmaker," said Klausmann. From then on, they sneaked in day or night under the unsuspecting noses of the Panthéon's officials.

Their presence only became known when they revealed themselves so the curators would know to wind the clock. This is far from the first project Untergunther has undertaken.

Klausmann and his crew are connoisseurs of the Parisian underworld. Since the 1990s they have restored crypts, staged readings and plays in monuments at night, and organised rock concerts in quarries. The network was unknown to the authorities until 2004, when the police discovered an underground cinema, complete with bar and restaurant, under the Seine. They have tried to track them down ever since.

So keep an eye on the news, you never know where they'll pop up next.

How Government Can Improve Cyber-Security

In "How Can Government Improve Cyber-Security?" Ed Felten says:

Wednesday was the kickoff meeting of the Commission on Cyber Security for the 44th Presidency, of which I am a member. The commissionhas thirty-four members and has four co-chairs: Congressmen Jim Langevin and Michael McCaul, Admiral Bobby Inman, and Scott Charney. It was organized by the Center for Strategic and International Studies, a national security think tank in Washington. Our goal is to provide advice about cyber-security policy to the next presidential administration.

First, congratulations on the appointment, Ed! Given that Scott Charney is a chair, I want to be clear that, as always, my comments here are my own.

There are some great comments about economics and motivations, and I'd like to offer up a different answer, which is that the government can improve cybersecurity by helping us gather more and better data.

This is a normal and regular role of government. For example, the US government runs and publishes a census, a statistical abstract of the United States, the CIA produces their World Factbook, and the FBI produces Uniform Crime Reports, and the Department of Justice does a National Crime Victimization Survey.

In information security, we have a paucity of good information to help us make good decisions. For example, are insiders really responsible for 70% of all attacks?

Many of the data gathering processes that the government runs are obsessed with secrecy. CERT, ISACs and others sometimes publish statistics, but they're sparse. Over the last few years, laws relating to reporting data breaches have sprung up in 39 states. Hackers at Attrition.org have assembled a database of over 800 breaches, and Privacy Rights Clearinghouse maintains a similar list. These lists contain specific data on what's gone wrong at a wide variety of companies and institutions. There are two key lessons we can get from this.

Many of our fears about what happens after a company is breached have turned out to be false. This is the first key lesson. We have feared that companies will go out of business, people will lose their jobs, and customers will flee. Generally, these things happen only in extreme outliers, if at all. (Two companies have gone out of business; average customer churn is about 2%.)

The second lesson comes from studying the data. The dataloss list contains less selection bias about a broader set of incidents than any other public data I've ever seen.

So my goal for the 44th Presidency would be to overcome the fear that has held us back from having national cybercrime statistics, in the form of good law requiring breach disclosure.

By good law, I mean breadth of what must be reported on, no expensive and anti-consumer 'trigger provisions,' central reporting of detail, and publication of those details and summaries by an agency tasked with data sharing and advancing knowledge.

That said, congratulations on the appointment, and I'd be happy to delve deeper.

Security is never static

There's a story in the Wall St Journal, "London's Congestion Fee Begets Pinched Plates:"

This city's congestion pricing for drivers is heralded around the world for reducing traffic and pollution. It's also causing an unintended effect: a sharp jump in thieves stealing or counterfeiting license plates.

Thieves are pinching plates by the dozens every day to fool the city's traffic cameras, which enforce the £8 ($16) daily charge to drive in central London as well as other traffic infractions ... With someone else's license plate on their car, scofflaws can drive around free, and any fines are billed to the plate's rightful owners.

Before the congestion charge took effect in February 2003, police didn't bother to track stolen number plates...because so few incidents were reported ... Reports of stolen plates in the city spiked to 9,777 last year.

This is precisely the opposite of how we'd want such a system to work: it should catch criminals and ignore the rest of us. [Updated this for clarity.]

Unfortunately, most tracking systems are perverse, and do exactly what we don't want: criminals learn to get around them, and the general public loses their privacy.

When looking at a system, ask yourself, "is this good enough to stop people motivated to get around it? If it's not, then look at the costs.

We can do this with the new American approach to tourism:

"Since September 11, 2001, the United States has experienced a 17 percent decline in overseas travel, costing America 94 billion dollars in lost visitor spending, nearly 200,000 jobs and 16 billion dollars in lost tax revenue. ("'Unwelcoming' US sees sharp fall in visitors since 9/11," Discover America travel advocacy group.)

Terrorists are going to enter the country illegally, using paths worn smooth by millions of illegal immigrants. Meanwhile, millions of people are deciding to take their business and leisure elsewhere, because of the harsh face we show the world at our borders.

License plate story via David Lesher in the Risks Digest, tourism story via BoingBoing. Photo by ChiquitaNerd.

Ceremony Design and Analysis

Carl Ellison has been doing some really interesting work on what he calls Ceremonies:

The concept of ceremony is introduced as an extension of the concept of network protocol, with human nodes alongside computer nodes and with communication links that include UI, human-to-human communication and transfers of physical objects that carry data. What is out-of-band to a protocol is in-band to a ceremony, and therefore subject to design and analysis using variants of the same mature techniques used for the design and analysis of protocols. Ceremonies include all protocols, as well as all applications with a user interface, all workflow and all provisioning scenarios. A secure ceremony is secure against both normal attacks and social engineering. However, some secure protocols imply ceremonies that cannot be made secure.

He's talked about it in public a little before, and now has a paper available from the IACR eprint service, "Ceremony Design and Analysis."

If you design network protocols, or think about the intersection of security and usability, this is very much worth reading.

Occluded Chaos, or the next 25 years of Eclipses

Thanks Les!

Bank Note of the Year

Who knew there's an International Bank Note Society? Or that they have a prize for best bank note of the year? This year's winner is the "1,000-franc note issued by the Banque Centrale des Comores, the central bank of the Comoros, an archipelago located between Madagascar and the east coast of southern Africa."

Don't miss the discussion of the note's security features:

Despite a low face value (approximately US$2.70 at current exchange rates), the 1,000-franc note sports an impressive array of security features. Portions of the design are printed with the intaglio process, imparting a tactile element to the raised ink, along with the latent image created by the BCC embossed above the signatures. Counterfeiting is made more difficult through the use of microtext, incorporation of a perfect-registration device, and the inclusion of Omron rings. The paper contains an embedded security strip that fluoresces under UV light, and a watermark of a crescent moon, four stars, and the letters BCC. Finally there is an iridescent band on the front of the note that can be seen only when tilting the note at an angle to the light.

Incidentally, the term "Omron rings" seems to describe what's better known as the "EURion Constellation," the set of rings that break various scanning devices.

Via Davi's Flying Penguin.