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.

Bush's Law -- Less Safe, Less Free

I'd like to review two recent books on the war on terror: "Bush's Law: The Remaking of American Justice" by by Eric Lichtblau, and "Less Safe, Less Free: Why America Is Losing the War on Terror" by David Cole and Jules Lobel. Both are well written assaults on the way in which the Bush administration is conducting itself, although each takes a tact aligned with the author's background and history. Lichtblau is a reporter, currently for the New York Times, and Cole and Lobel are law professors.

Bush's Law is an extended view into some of the major stories that Lichtblau has covered. Included are the NSA's warrant-less wiretapping, the SWIFT following of the money, and the Comey/Ashcroft hospital story. Even as someone who follows these stories fairly closely, I still learned quite a bit-some new, some not previously reported, and all better organized and more readable than in the newspaper. The theme that emerges from Bush's Law is one of secrecy, and the conflict which a free society faces when repeatedly begged to `trust us' by an administration which seems to not understand how its actions undermine trust.

The undermining of trust is also a major theme of Less Safe, Less Free. Before getting into the meat of the book, let me say that this is law professor writing at its best. It's clear and compelling, and the notes are at the end. They lay out a strong case that the Bush administration's concept of how to engage with the world is is at its core, preventative, rather than reactive. In theory, this seems like a great plan. In practice Cole and Lobel show how it inevitably undermines the concepts of justice on which our society is founded, as well as our reputation with the rest of the world. That is, it is not merely a practical failure, it was inevitably going to be a practical failure. Predictions are hard, especially about the future. Reasonable people may disagree on the reasonableness of a preventative action. The difficulty of reaching proof "beyond a reasonable doubt" about what would have happened undermines the legitimacy of claims about the future.

The essence of their argument is that prevention, be it preventative war, such as in Iraq, or preventative law enforcement, such as with the justice, always requires the showing of evidence. You can't simply detain someone because they might in the future commit a crime. In a court, no single body acts as judge, jury and executioner. Each party gets their day in court, with an opportunity to examine the evidence against them. These things are impossible in the preventative paradigm. Not only are sources and methods secret (sometimes with good reason), but the evidence is often lacking. In the case of war, the court is that of public opinion in many places. They also show a plethora of historical cases where preventative war went horribly wrong, and relate preventative war to a set of regimes with which no reasonable person wants to be associated.

The core reason which we demand that justice be reactive, or, at its fastest, at the instant of a crime, is that we rightfully fear the powers we invest in our government. It is a mighty and fearsome machine which can crush anything in its path. When it is allowed to do so, we are all less safe, and less free.

Two asides: I paid for both books, and I love the endnote styling of page number, excerpt, note used in Bush's Law.

Everybody Run, Crispin's Got a Blog

My buddy, collaborator and co-worker Crispin Cowan has started a blog. The first post is "Security Is Simple: Only Use Perfect Software."

[Update: Added a link to Crispin's home page, because some readers apparently have trouble with a search engine.]

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.

The messenger is the message

In a blog post entitled "Lending Tree A Little Late In Cutting Off Network Access?", I read that in the recent Lending Tree breach:

several former employees may have helped a handful of mortgage lenders gain access to Lending Tree's customer information by sharing confidential passwords with the lenders.

Later, the author describes "an obvious chink in Lending Tree's information security armor", (reprinting a U.S. News quotation from Brian Cleary):

These are former employees—how can those user accounts to critical customer data still be active? Those should be shut down. So, their access to all of the information and resources should be revoked on the day of their termination.

USNews.com

Finally, he observes that

If you're going to rely primarily on human beings to implement the policies, then you'd better make sure that those human beings are either themselves subject to checks and reviews to make certain that they're following the policies.

All of this is nothing new to EC readers. What surprised me, and what I think is noteworthy here, is that the guy writing this is not some CISSP, CISA, or even CISO. He's the voice behind the Bank Lawyer's Blog, an attorney with banking and other corporate clients.

Not to read too much into this, but when the legal profession starts commenting knowledgeably about access termination policies, there's something interesting afoot.

Who Watches the Watchlists?

The idea of "watchlists" has proliferated as part of the War on Terror. There are now more than 63 of them:

As part of its regular "risk management" service, which provides screening, tracing, and identity and background checks on potential clients or trading partners, MicroBilt will now offer a "watch list" service that checks these individuals against 63 different lists from 35 sources, including OFAC, the FBI, and Interpol, Bradley says. ("Companies May Be Held Liable for Deals With Terrorists, ID Thieves", DarkReading)

I say more than 63 because some unknown number are secret. The poor souls who find themselves on these lists have, in essence, no recourse. Convincing 35 or more agencies that their presumption of your guilt is incorrect might, in theory, be possible. In reality, the agency has no reason to do anything but drag its feet: there are no penalties to them for declaring you guilty. In contrast, a failure to put your name on the list risks them not having prevented you from your future thoughtcrime.

But there's hope. And it's not in MicroBilt's stock price (MicroBilt is a subsidiary of First Advantage). Rather, it's in the courage of a judge, who ruled that any American who has been routinely detained because they are on a watch list knows that they are on a list, and thus the government's 'State Secrets' privilege isn't applicable:

since the government admits it has stopped the six men and two women more than 35 times, federal Magistrate Judge Sidney Schenkier of the United States Northern Illinois District Court dismissed that argument. Instead he found that the government "failed to establish that, under all the circumstances of this case, disclosure of that information would create a reasonable danger of jeopardizing national security." (" Court: Government Must Reveal Watch-List Status to Constantly Detained Americans," Wired's excellent 27B-6 Mk IIa blog)

5754463f

The ACM has a list of classic computer science works put together based on responses to a survey of the membership.

I'm no computer scientist (though I've lived with my share...) but I'm shocked that none of Knuth's works is on this list, even if it is basically a beauty contest.

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?

Good problems to have

You don't have much credibility looking for a publisher for a book on rum when you're sailing in the Caribbean drinking the best rums you can find in the name of research. Most people just didn't take me seriously that there was even a need for a book on rum. It took quite a while to get things rolling.

See the Ministry of Rum FAQ.

University of Miami: Good for the body, bad for the soul?

The University of Miami has chosen to notify 41,000 out of 2.1 million patients whose personal information was exposed when thieves stole backup tapes.

The other 2.1 million people, apparently, should be reassured, that their personal medical data was stolen, but the University feels it would be hard to read, and well, there's no financial identity theft risk associated with it. If you believe the sorts of people who notify 1.9% of the victims of a breach. Sorry, ChoicePoint. Unfair comparison. You notified about 18% of the victims*, nearly ten-fold as many.

There's some analysis of how hard it would be to read the tapes. I'm skeptical: why does someone steal tapes from an Iron Mountain van if not to read them?

The Breach Blog feels differently. In "University of Miami reports stolen tapes affecting patients," he digs into the likelihood of the data being accessed.

Now, the University claims that the tapes are in a "complex and proprietary format," which seems to be "Tivoli Storage Management" from IBM. Now, Tivoli storage manager has encryption capabilities (page 3 of this PDF.) I'm curious why that wasn't in use.

Also, looking around, I found this quote at an IBM partner site:

Much is made of the inbred security of the TSM system since the backed up data is so closely linked with the TSM database. While, to the layman this is true, and it is almost impossible to reconstruct TSM data without the database, it is possible in the right scenario, with the right skills at your disposal.

Until I hear more, I'm skeptical of the University's claims. I don't believe, and I have not believed for a long time, that breach notices are about identity theft. They're about the performance of a promise to protect information.

(*Footnote: 18% being 30/160, approximate numbers for the ChoicePoint incident.)

Point Break, Live

The starring role of Johnny Utah is selected from the audience each night, and reads their entire script off of cue-cards. This method manages to capture the rawness of a Keanu Reeves performance even from those who generally think themselves incapable of acting. The fun starts immediately with the "screen test" wherein the volunteer Keanus (usually 5-15 men and women vie for the role) go through a grueling audition process. The part is then cast via applaus-o-meter.

Point Break Live. So very attitudinally mis-adjusted.. Via JWZ.

Marty Lederman, on a roll

You see, the CIA apparently uses the less dangerous version of "waterboarding" -- not the Spanish Inquisition method, but the technqiue popularized by the French in Algeria, and by the Khmer Rouge -- involving the placing of a cloth or plastic wrap over or in the person's mouth, and pouring or dripping water onto the person's head. That's the civilized version of waterboarding -- the benign, anodyne, variant of the water treatment, the kind carefully administered by professionals. We would never dream of the barbaric practice of actually forcing the water into the nose and mouth.

Go read "The Underdeveloped Jurisprudence of the Forcing/Pouring Distinction" and wonder how the next President is going to avoid prosecution.

Microsoft Security Intelligence Report V4

Microsoft Security Intelligence Report (July - December 2007)

This volume of the SIR focuses on the second half of the 2007 calendar year (from July through December) and builds upon the data published in the previously released volumes of the SIR. Using data derived from several hundred million Windows users, and some of the busiest online services on the Internet, this report provides an in-depth perspective on trends in software vulnerability disclosures as well as trends in the malicious and potentially unwanted software landscape, and an update on trends in software vulnerability exploits. The scope of this fourth volume of the report has been expanded to include a focus on privacy and breach notifications, and a look at Microsoft’s work supporting law enforcement agencies worldwide in the fight against cyber criminals. [Emphasis added.]

Emergent Chaos readers are unlikely to learn new details in the analysis. What's important to me is that this helps to establish a new normal baseline around the way we're using information that's disclosed and gathered by folks like Attrition.

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?

Reality imitates the Onion

I'm somewhat sure this is a real AP story, "Al-Qaida No. 2 says 9/11 theory propagated by Iran." The Onion scooped them, with "9/11 Conspiracy Theories 'Ridiculous,' Al Qaeda Says."

Unfortunately, no progress on the "fake tape" issue:

The authenticity of the two-hour audio recording posted on an Islamic Web site could not be independently confirmed. But the voice sounded like past audiotapes from the terror leader, and the posting where it was found bore the logo of Al-Sahab, al-Qaida's official media arm.

(Via Orin Kerr at Volokh.)

Keynoting at ISSA tomorrow

I'll be delivering the keynote at " The Fourth Annual ISSA Northwest Regional Security Conference" tomorrow in Olympia, Washington. I'm honored to have been selected, and really excited to be talking about "the crisis in information security."

The topics will be somewhat familiar to readers of this blog, but in a longer, more coherent format than the emergent chaos which makes it here.

I should mention, I'm doing this wearing my own hat, not a Microsoft one, and will avoid most any mention of threat modeling or SDL.

WEIS 2008: Register now

Registration is under way for the seventh Workshop on the Economics of Information Security , hosted by the Center for Digital Strategies at Dartmouth's Tuck School of Business June 25-28, 2008

The call for papers, and archives of past workshops give a good sense of what you'll find (and it is awesome and well worth your time).

Unfortunately, the complete program for this year is not up yet on the site, although hotel discounts end on April 24.

I'm going, and may show up a 2-3 days early. EC readers who also will be in town early and want to do some hiking, drop me a line and maybe we can arrange something.

More New School Reviews

Gary McGraw says buy it for the cover:

The New School of Information Security is a book worth buying for the cover alone. I know of no other computer security book with a Kandinski on the front. Even though I know Adam Shostack from way back (and never could have predicted that he would become a Microsoft guy), I saw his book at RSA, bought it for the cover, and only then discovered that he was the author! My plan was to give the book to a good friend who I know is a huge Kandinski fan. On the way to complete that errand, I had a chance to look though the book and now I need a copy of my own! If you’re a follower of the economics of security school (which Ross and Bruce Schneier have helped spearhead), you’ll like this book. (Gary McGraw)

while Ben Rothke says buy it for what's in between:

The New School of Information Security is a ground-breaking text in that it attempts to remove the reader from the hype of information security, and enables the reader to focus on the realities of security. The fact that such a book needs to be written in 2008 shows the sorry state of information security.

...
Let's hope The New School of Information Security is indeed a new start for information security. The book is practical and pragmatic, and one of the most important security books of the last few years. Those serious about information security should definitely read it, and encourage others to do the same. (Ben Rothke's review on Slashdot)

Thanks very much for the awesome review, Ben!