Author: mordaxus

Groundrules on Complaining About Security

Groundrules on Complaining About Security

In this article, I want to lead into some other articles I’m working on. In those, I’m going to complain about security. But I want those complaints to be thoughtful and within a proper context.

You will hear many of us in security talk about threat models. Adam literally wrote the book on threat models and if you don’t have a copy, you should get one.

Threat models are a way of thinking about security in a somewhat rigorous way. Without some sort of threat model, you’re not really doing security.

Threat models sound complex, but they’re really not. We all do them intuitively all the time, and here’s the basic outline of how to make one. You want answers to these questions:

  1. What are you doing?
  2. What could go wrong?
  3. What are you doing about it?

Among the valuable things in Adam’s book, he talks about these and more, but these three simple questions frame how to talk about security no matter who you are. If you don’t have a threat model, you might be doing something useful, but it’s not really security.

If you are a maker of security, without a threat model you might have a solution in search of a problem. You might also have a stone soup security system, in which you throw a bunch of things in a pot, and while tasty (or secure), isn’t organized. There are many, many stone soup security systems out there.

If you’re going to use a security system, without a threat model you have no way to know if what you’re getting meets your needs.

If you’re challenging a security system, without a threat model, your criticisms may be true but irrelevant.

It is these latter two cases – deciding what security system to you and providing a critique of a security system – that I’m going to focus on, particularly since I’m going to be engaging in challenges, and people selecting a system also need to think about what their own threat model is when selecting a system. If you’re going to use a secuity system, a little bit of thought about what you expect it to do and what you expect it to protect you from is in required.

Let me move a bit away from computer security for a moment; analogies often help.

Let’s look at this statement:

  • Aspirin doesn’t cure cancer.

It’s true. Aspirin doesn’t cure cancer. It doesn’t do half-bad on headaches (with of course, a number of other qualifiers), but it doesn’t cure cancer.

However, if Alice says, “I’m going to go take an aspirin” and Bob says, “Aspirin doesn’t cure cancer,” he has implicitly assumed that her threat model is not:

  • I have a headache
  • I’m going to take an aspirin to cure it

but

  • I have cancer
  • I’m going to take an aspirin to cure it.

Even if Alice actually does have cancer, she might also have a headache. Especially if she has to deal with someone with simplisitic thinking like Bob. This is the sort of headache that got me to write this essay.

Getting back to security, while I was typing the first part of this, a friend and I started on a discussion. We started with wondering if since most front door locks are easily picked, does that mean that they’re just security theatre. The discussion then went into social value of locks (most people are honest, after all), the technological merits of Abloy locks, the expense of getting a good lock for all your doors, the human factors aspects of wanting one key for all your doors, the security problem of weak points from the porch to the windows, and then on to reinforcing hinges and even the front door itself. It was a fun discussion, but it wasn’t a good security discussion, it was security stone soup. The initial question of whether most door locks do anything was the pot of water with a stone in it and we kept adding in garnishes until we ended up with a tasty conversation. However, at no point did we discuss a threat model. We don’t know what we were trying to protect, what threats we were protecting it from, or anything that turns it into a real security discussion.

I think we were talking about a stereotypical threat of a burglar backing up a van to the house and carting off a lot of valuables, but I am just presuming that.

I know of what I speak in this issue of threat models because I’m guilty of it, too. It’s so easy to get caught up in security stone soup that it happened to me while I was writing an essay on threat models and security stone soup.

Now that I have a couple of ground rules in place as a preface, I will complain about security in my next essay.

Microsoft Backs Laws Forbidding Windows Use By Foreigners

According to Groklaw, Microsoft is backing laws that forbid the use of Windows outside of the US. Groklaw doesn’t say that directly. Actually, they pose charmingly with the back of the hand to the forehead, bending backwards dramatically and asking, “ Why Is Microsoft Seeking New State Laws That Allow it to Sue Competitors For Piracy by Overseas Suppliers? ” Why, why, why, o why, they ask.

The headline of this article is the obvious reason. Microsoft might not know they’re doing it for that reason. Usually, people with the need to do something, dammit because they fear they might be headed to irrelevancy think of something and follow the old Aristotelian syllogism:

Something must be done.
This is something.
Therefore, it must be done.

It’s pure logic, you know. This is exactly how Britney Spears ended up with Laurie Anderson’s haircut and the US got into policing China’s borders. It’s logical, and as an old colleague used to say with a sigh, “There’s no arguing with logic like that.”

Come on, let’s look at what happens. I run a business, and there’s a law that says that if my overseas partners aren’t paying for their Microsoft software, then Microsoft can sue me, what do I do?

Exactly right. I put a clause in the contract that says that they agree not to use any Microsoft software. Duh. That way, if they haven’t paid their Microsoft licenses, I can say, “O, you bad, naughty business partner. You are in breach of our contract! I demand that you immediately stop using Microsoft stuff, or I shall move you from being paid net 30 to net 45 at contract renegotiation time!” End of problem.

And hey, some of my partners will actually use something other than Windows. At least for a few days, until they realize how badly Open Office sucks.

Ambrose Bierce Punks Richard Feynman

Via Boing Boing, where Maggie Koerth-Baker gave a delightful pointer to this film of Feynman explaining for seven-and-a-half minutes why he can’t really explain why magnets repel each other. Or attract, either.

And trumping him in time and space, Bierce gave us this in 1906:

MAGNET, n.
Something acted upon by magnetism.

MAGNETISM, n.
Something acting upon a magnet.

The two definitions immediately foregoing are condensed from the works of one thousand eminent scientists, who have illuminated the subject with a great white light, to the inexpressible advancement of human knowledge.

Quantum Crypto is Quantum Backdoored, But It's Not a Problem

Nature reports that Quantum Cryptography has been completely broken in “Hackers blind quantum cryptographers.” Researcher Vadim Makarov of the Norwegian University of Science and Technology

constructed an attack on a quantum cryptography system that “gave 100% knowledge of the key, with zero disturbance to the system,” as Makarov put it.

There have been other attacks on quantum cryptography, but this is the first in which there is no indication that the key has been stolen. In those attacks, the operator of the system would see the transmission error rate go up, but in Makarov’s attack, the operator sees nothing. In short, they are completely, utterly defeated. The attacker gets everything with impunity.

As usual, the quantum crypto crowd doesn’t see that a 100% loss of key with no inkling of the loss is a problem. Makarov himself said to Nature, “If you want state-of-the-art security, quantum cryptography is still the best place to go.”

Perhaps the kicker is this in Nature’s article:

Ribordy [CEO of ID Quantique] and Zavriyev [Director of R&D at MagiQ] stress that the open versions of their systems that are sold to university researchers are not the same as those sold for security purposes, which contain extra layers of protection. For instance, the fully commercial versions of IDQ’s system also use classical cryptographic techniques as a safety net, says Ribordy.

Huh? We can trust commercial versions of quantum crypto because it uses classical crypto as a safety net? That’s saying that the quantum coolness is really just icing over a VPN. Isn’t it? Am I missing something?

Now it’s time for a rant. Quantum cryptography is really, really cool technology, but the whole point of it is, well, security, and if the state of the art is that the system is breakable, then the art is in a sorry state. It’s a state of being a research toy, not a real security system.

The whole point of quantum crypto is that it isn’t even really crypto. It’s communications that can’t be eavesdropped on. It’s a magical tour-de-force of science and technology. But if it can be silently thwarted, it’s no good. If there is no way that it can be tested to be good, it’s no good. Moreover, the latter is more important than anything else.

For quantum crypto to be viable and trusted, we have to have some way that we know that the boxes were designed and manufactured in such a way that we can be confident that there’s no silent quantum backdoor in the box, then it has no value. You might as well just get a VPN router from the usual suspects and be done with it. If you’re really paranoid, just lay down some glass fiber and put it in a conduit.

Quantum information science as a discipline needs to start taking security seriously. It can’t just brush off a break of this magnitude, and remain credible. Come on, at least admit this is serious and has to be reflected in the manufacturing and testing. Come up with countermeasures, something.

P != NP and Security

There’s been a lot of discussion about the paper written by mathematician Vinay Deolalikar on this interesting problem.

The P!=NP problem is so interesting that there’s a million-dollar prize for solving it. It might even be interesting because there’s a million-dollar prize for solving it. It might also have some applicability to computer science and even cryptography. The August 11 edition of Deolalikar’s paper can be found here.

Because this is an interesting problem, there’s a lot of pressure on domain experts and pseudo-experts to comment. I classify myself as more pseudo-expert than expert, so color your filters accordingly.

Among the real experts, my favorite is Scott Aaronson, who is an expert in complexity theory and quantum information science. If you aren’t completely clear on the whole thing, his essay, “P vs. NP for Dummies” is a good place to start.

His essay, “Putting my money where my mouth isn’t,” is a marvelous snap response. In it, he says that he’s willing to contribute his on $200,000 to the million-dollar prize, should this proof be right. He gives some great reasons for his own snap commentary and his own decision not to cancel his vacation to look at the paper.

Aaronson also points to his own essay from 2008, “Ten Signs a Claimed Mathematical Breakthrough is Wrong,” which you should be reading before you read anything about Deolalikar’s paper. It’s not about Deolalikar, it’s about the general issue of breakthrough papers of any sort.

But getting back to this particular paper, there’s a lot of skepticism, and a good summary of the skepticism comes from Terence Tao.

I’ll add in my own raised eyebrow along with my own general discussion of P!=NP. I have three points:

  1. P!=NP really isn’t interesting.
  2. Most comments about the whole P vs. NP don’t understand the ramifications of it, especially when dealing with practical disciplines like computer science and cryptography.
  3. The reason I have a raised eyebrow centers around those two above.

So here we go.

P!=NP really isn’t interesting. What would be interesting would be if someone proved that P=NP. We all expect that P!=NP, we act as if it’s true. On the one hand, that means I’m far more likely to believe Deolalikar because he’s proving that which we expect to be true. On the other hand, that means it’s harder evaluate his proof because it is proving something we all think is true.

Understanding P vs. NP. Conventional wisdom about P and NP often includes thoughts such as, “The implications of this [P=NP] on applications such as cryptography, and on the general philosophical question of whether human creativity can be automated, would be profound.” I disagree. I think that if it turns out to the shock of everyone that P=NP, it will be a yawn.

Let’s suppose that P=NP, which means that a large class of problems have solutions in polynomial time. Great. That doesn’t mean they’re easy to solve. It doesn’t mean that the solutions are even useful.

Here’s an example. A few years ago, we got a polynomial time primality test algorithm, the AKS test (named for its authors, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena). Originally, it was an x12 algorithm, and everyone needing primality testing ignored it, because that’s too slow. It’s been improved to x6, which is still too slow. It’s polynomial, but that doesn’t matter.

In practical terms for cryptography, let’s suppose you want to generate a 2048-bit RSA key. For that, you need two 1024-bit primes. Right now, the tests that we use are “probabilistic.” I put quotes around it because while there’s no guarantee that the number that passes the probabilistic test is actually prime, no one has ever (knowingly) found a number that passed the probabilistic test and was not actually prime. In fact, if you found such a number, it would be a result worthy of publication. Thus, the risk of the inexact test is very low. But the cost of the exact test is 10246 which is a very large number, 1,152,921,504,606,846,976, and we can’t really afford that.

Thus, for this function that’s useful for crypto, primality testing, we know that there is a P solution, x6 is too large a P. The fact that it is P turns out to be uninteresting.

For the purposes of cryptography, even x3 is probably not good enough. Some time ago, I harumphed about quantum computers doing factoring, and much of my harumphing boils down this observation — that even a low power polynomial like a cubic may leave the advantage to the code-maker over the code-breaker.

This is why I think that if P=NP, it could still be a yawn. If you find a polynomial solution with an exponent of somewhere in the 3-10 range, they are so hard so fast that the fact that the solution is polynomial is a merely a factoid. It seems a good bet that if there were a quadratic-scale algorithm for factoring, we’d know it.

This is a subtle point, so I’ll make it one more time. If P=NP, it’s only interesting if the polynomial is of low order. Polynomial-time problems can easily be intractable.

If it turns out that a bunch of cryptographic problems are polynomial, but order x6 or more, then the cryptographers aren’t going to lose a lot of sleep. In fact, they’ll have a good reason to get everyone to upgrade all their software, and that will be pretty much the end of it.

On the flip side of this, most NP-complete problems we know about are not as hard as we’re led to believe. The most famous NP-complete is the Traveling Salesman Problem. While it is indeed very hard to come up with the shortest solution for arbitrary problems, it’s actually very easy to come up with acceptable solutions for reasonable problems. Heck, it’s not like actual traveling salesmen have lots of problems covering their routes. There is even a nice web page that computes routes on Google Maps. I think a good way to put this in perspective with the P vs. NP problem is to note that there is a prize for solving a 100,000 city problem, and that prize is $100.

Most of the genuine hard problems we have are only hard to solve on edge conditions. There are many attempts to create cryptosystems out of real NP-complete problems, and their track record is pitiful. We really don’t have any of them. I say “really” because we have one — lattice cryptography — and it still has issues. It’s slow, big, and complicated with intellectual property. Worse, some forms of lattice cryptography have had problems similar to the Traveling Salesman Problem. The GGH cryptosystem has the flaw that all ciphertexts leak information about the plaintext. Oops.

The bottom line here is that many problems that we know to be hard are easy in most cases and that “easy” problems might still be hard enough that they’re useful for protecting secrets. Whether P=NP or P!=NP is something that is interesting to mathematicians and philosophers far more than to scientists and engineers.

Raised eyebrow department. Now I get to why I’m so far skeptical. The quote that I gave above about what it would mean if P=NP comes from Deolalikar’s paper. Perhaps naïvely, I expect an expert on complexity theory to go beyond the usual science-reporting ooo-ahhs. I expect a complexity theorist to understand that complexity is complex, or at least subtle. I’m not a complexity theorist, I’m a mere complexity practitioner and I understand that complexity is hard to understand.

However, he’s right. If P=NP, it would be a deep discovery and have philosophical import. However, however, he’s proved the opposite, and so discussion about what it would mean if his proof were out of phase with what it actually proves seems weird.

Fine, fine. Everyone’s entitled to their soapbox, particularly when they do something significant. But reading through the proof there’s something missing. In brief, his proof has to prove that something that everyone thinks is hard is in fact actually hard. Ironically, this is harder than proving that it’s actually easy (which is again the proof of the opposite thing). Part of proving that something is hard ought to include showing that a related problem is easy.

In the P vs. NP world he’s chosen, he is showing that 3SAT is hard. 3SAT, to oversimplify, looks at the combinations of three boolean operations, such as A or B and C. 2SAT (combinations of two boolean operations) is known not to be hard. Had Deolalikar shown that 3SAT is hard and 2SAT is easy, I think we’d all be wowed. With only half of that, we’re left hanging and scratching our heads. Since we expect 3SAT to be hard, there needs to be some contrast against a related known easy problem for contrast. Without that contrast, it’s very hard to value the proof.

Worse, if one were to take his proof mechanism and apply it to 2SAT and come up with a conclusion that 2SAT is also hard, then there’s a huge hole in the proof. If I were analyzing the proof, I would in fact start by seeing how it applies to a few known-P problems. If it proves they are NP, we have a problem.

To sum up, I bet the proof doesn’t hold up because it only addresses the wheat, not the chaff. Any prover of P!=NP has to deal with the problem that we expect that to be true and that it’s hard to prove that something we think is hard actually is hard. Disproving it is easier in the sense that if you come up with an easy solution to something everyone thinks is hard, it is — um, well — hard to argue with that. Without some contrast, any proof of P!=NP looks on its surface as if you’re saying, “Hey everyone, you know that problem no one can easily solve? I can’t easily solve it, either!” That lacks intellectual force.

Nonetheless, maybe he has it. Maybe in a few months we’ll all be wowed, once it sinks in. Heck, maybe he doesn’t have it this summer, but next summer a revised proof will have us all cheering. Only time will tell. But right now, it’s interesting but unconvincing.

My personal bet, which I have no proof for, is that P!=NP is true but unprovable. I’m holding out for the proof that it’s unprovable.

Ridiculing the Ridiculous: Terrorist Tweets

A group of soldiers with the US Army’s 304th Military Intelligence Battalion have managed to top previous military research on terrorist use of World of Warcraft.

Realizing that mentioning the word “terrorist” can allow researchers to acquire funding to play the popular MMOG, they turned attention to the popular, if architecturally unscalable micro-blogging system, Twitter.

Surpassing the threat-analysis skill of super-spy Chad Feldheimer from the recent documentary “Burn After Reading,” they mention not only the threat of “socialists,” “communists,” and “anarchists,” in using Twitter to “communicate with each other and to send messages to broader audiences,” but the wider and more up-to-date threats from “religious communities,” “atheists,” “political enthusiasts,” “human rights groups,” “vegetarians,” and last but not least, “hacktivists.” They notably left out delinquent teenagers, so one presumes they don’t use systems like Twitter.

The Military Intelligence group also discovered that people can use GPS in phones like the Nokia 6210 and Nokia Maps to know where they are. This could let terrorists who want to illegally cross a border know where that border is, or to know that a certain large triangular stone thing is the Pyramid of Cheops (category: Attraction).

The report’s cutting edge thinking also discusses how terrorists could use voice-changing software such as AV Voice Changer Diamond to make prank phone calls and effectively hide under an abaya.

The full report, marked “For Official Use Only,” can be found here. It also redacts with a dark gray splash of ink the email address of sarah.e.womer@ugov.gov, from whom you can get a copy of the report if you do not have access to INTELINK, Cryptome, or the Federation of American Scientists.

I think the report speaks for itself. I just can’t make this stuff up, apart from the bit about hiding under an abaya.

Elections Are Done For Me

I Think I Voted

Forty Percent of California voters are “permanent absentee” voters. Oregon runs entirely by mail-in votes. Other US states have some sort of mail-in or absentee status that people can assign themselves to.

For those people, including me, elections are a slice of time that ends on election day. This isn’t new, until relatively recently, it all worked that way. You couldn’t expect everyone to all be in town on that one day. It is only urbanization that allows us to have elections be an event rather than a process. I sat down last night and waded through the whole mass of offices, measures, and initiatives. I have now completed my civic duty.

This is probably a good idea, as many of the issues with voting and counting votes and securing them have in their model that it has to be done on one day, and as quickly as possible after the polls close. It improves security and accountability to allow and encourage people to vote over an interval of a few weeks.

Emergence Emerges

This paper, “More Really is Different,” may be one of the most important papers of the last half-millenium. It argues that P.W. Anderson’s concept of “emergence” is provable. It may have even proved it.

The idea of emergence, from whence this blog gets its name is the opposite of reductionism. It is the idea that a complex system acquires properties that the underlying parts cannot predict. It’s nothing more and nothing less than a formalization of the adage, “The whole is more than the sum of its parts.”

The authors, Mile Gu, Christian Weedbrook, Alvaro Perales, and Michael A. Nielsen, argue directly that this may mean that a “Theory of Everything” may therefore be impossible.

This is big, big news. Read the paper. Read the commentary in The New Scientist, “Why nature can’t be reduced to mathematical laws.”

If they are right, this goes to the core of the philosophical underpinnings of the way we understand the world. It may help explain everything from weather prediction to the origins of life to whether souls exist. I might even be engaging in understatement rather than hyperbole on that last bit. You may think it’s a long way down to the chemist’s, but this is big.

While you’re at it, expect some highly entertaining debate, and pseudo-scientific whackos of every stripe to start quoting this. Maybe the next Kuhnian revolution has begun.

Navigation