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.

Rights at the “Border”

“I was actually woken up with a flashlight in my face,” recalled Mike Santomauro, 27, a law student who encountered the [Border Patrol] in April, at 2 a.m. on a train in Rochester.

Across the aisle, he said, six agents grilled a student with a computer who had only an electronic version of his immigration documents. Through the window, Mr. Santomauro said, he could see three black passengers, standing with arms raised beside a Border Patrol van.

“As a citizen I’m offended,” he said. But he added, “To say I didn’t want to answer didn’t seem a viable option.”

From the NYTimes, “ Border Sweeps in North Reach Miles Into U.S..”

If you think this is ok, where in the US should it not be legal for the armed agents of the state to demand your papers without any grounds for suspicion of wrongdoing?

Similarly, if a law student doesn’t see not answering police questions as a “viable option,” what do we do to restore balance to the Constitution?

Previously on Emergent Chaos: “100 Mile Constitution Free Zone.”

Transparency, India, Voting Machines

India’s EVMs are Vulnerable to Fraud. And for pointing that out, Hari Prasad has been arrested by the police in India, who wanted to threaten and intimidate him question him about where he got the machine that he studied. That’s a shame. The correct response is to fund Hari Prasad’s work, not use the police to silence him.

I could write quite a bit about how science and security progress through open debate; about how no one likes to be wrong, but by admitting mistakes, we can improve, or the terrifying power of the state and the need to restrain it.

Rather I’ll just comment that arrogant abuses of power like this serve to de-legitimize the state and undermines the moral basis of claims to a monopoly of violence. When people can’t protest with speech and demonstrations of fact, they’ll continue to pursue their interests by other means with higher stakes.

Wikileaks

Friday night an arrest warrant went out, and was then rescinded, for Wikileaks founder Julian Assange. He commented “We were warned to expect “dirty tricks”. Now we have the first one.” Even the New York Times was forced to call it “strange.”

I think that was the wrong warning. Wikileaks is poking at a very dangerous system. We went to war with Iraq, claiming it had links to Al Qaida and chemical weapons programs. (I think there were good reasons for both Iraqi citizens and Western democracies to want a well planned and executed regime change in Iraq, and even better reasons to expect that attempts to do so would descend into chaos. But that’s besides the point.) Since then, we have publicly announced that we have death squads targeting US citizens. Does Wikileaks expect any less?

The American system of classifying documents is seriously flawed. That’s been the conclusion of every blue ribbon panel that studies it. Transparency and accountability are key tools that we the people use to constrain the power of government. But people in power never like transparency. They don’t like oversight and second-guessing. So over-classification is a natural outcome. Insofar as leaks help to constrain that, they’re useful to us, the governed. To the extent that leaks force a conversation about “why was this document classified,” they’re useful.

Now, leaking the names of informers is clearly problematic. It seems that, like many news organizations, Wikileaks asked the Pentagon for advice on redaction. They were rebuffed.

But that’s not the point of this post. The first point of this post is to say that the Leviathan is an angry and mean son of a bitch that’s now going to attack Wikileaks as hard as it can. If discrediting works, great. If not, expect escalation. Whatever their personal failings may or may not be, more transparency and accountability in government is a worthy goal, and we should support that goal. We should support that goal even as we can see flaws in Wikileaks. And despite their flaws, Wikileaks is making more transparency in less comfortable areas than anyone else.

The right response to the Afghan war diary would be for the Pentagon and for each of our allies to review what they have classified and why, and release more of it. Little of what was released was really surprising, and much of it should have been officially released with minor redaction. But instead of that review, we see the Leviathan lashing out at Wikileaks.

To the extent that Wikileaks pushes governments to become more transparent, we all benefit. If But more transparency not the reaction we’re seeing, and to distract us from that is the dirtiest trick so far.

If you think government has too much power, you should support Wikileaks. If you think that America’s overseas entanglements are hurting America or the world, you should support Wikileaks. If you think military adventurism is hurting the world, you should support Wikileaks. Because whatever Wikileak’s faults, their goals are important ones.

Which brings us to the second point of this post, which is to remind you, when you read negative stories about Wikileaks, ask yourself “who benefits?” The answer isn’t going to be “you and me.”

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.

Databases or Arrests?

From Dan Froomkin, “FBI Lab’s Forensic Testing Backlog Traced To Controversial DNA Database,” we see this example of the mis-direction of key funds:

The pressure to feed results into a controversial, expansive DNA database has bogged down the FBI’s DNA lab so badly that there is now a two-year-and-growing backlog for forensic DNA testing needed to solve violent crimes and missing persons cases.

Civil libertarians call the database — which increasingly includes everyone convicted of every federal law, legally innocent people awaiting trial and non-citizens detained in the U.S. for any reason — unnecessary and unconstitutional.

And yet a review by the Department of Justice’s Inspector General released on Monday concludes that the need to analyze and upload some 96,973 or more DNA samples a year into that database is contributing to a backlog of forensic DNA cases that stood at 3,211 in March.

That translates into a delay of about 150 days to over 600 days for law enforcement agencies who need answers right away.

We need to defund the database and use that money for something more useful, like getting that 150 days down to 5 or 10 for active criminal cases.

Via Michael Froomkin, “FBI Prefers Building DNA Database to Solving Crimes

How not to address child ID theft

(San Diego, CA) Since the 1980?s, children in the US have been issued Social Security numbers (SSN) at birth. However, by law, they cannot be offered credit until they reach the age of 18. A child?s SSN is therefore dormant for credit purposes for 18 years. Opportunists have found novel ways to abuse these “dormant” numbers. Unfortunately, credit issuers do not currently have the ability to verify if a SSN belongs to an adult or a minor. If they knew that the SSN presented belonged to a minor they would automatically deny opening a credit account.

Years ago, the Identity Theft Resource Center envisioned a simple solution to this problem. It is called the Minors 17-10 Database and ITRC has been talking with various government entities and legislators about this concept since July 2005. (…)

The creation of a Minors 17-10 Database would provide credit issuers the tool to verify if the SSN provided belongs to a child. This proposed SSA record file would selectively extract the name, month of birth, year of birth, and SSN of every minor from birth to the age of 17 years and 10 months. This record file, maintained by SSA, would be provided monthly to approved credit reporting agencies. When a credit issuer calls about the creditworthiness of a SSN, if
the number is on the Minors 17-10 Database, they would be told that the SSN belongs to a minor.

That’s from a press release mailed out by the normally very good Identity Theft Resource Center. Unfortunately, this idea is totally and subtly broken.

Today, the credit agencies don’t get lists from the SSA. This is a good thing. There’s no authorization under law for them to do so. The fact that they’ve created an externality on young people is no reason to revise that law. The right fix is for them to fix their systems.

The right fix is for credit bureaus to delete any credit history from before someone turns 18. Birth dates could be confirmed by a drivers license, passport or birth certificate.

Here’s how it would work:

  1. Alice turns 18.
  2. Alice applies for credit and discovers she has a credit history
  3. Alice calls the big three credit agencies and gets a runaround explains she’s just turned 18, and apparently has credit from when she was 13.
  4. The credit agency asks for documents, just like they do today (see “when do I need to provide supporting docs”)
  5. The credit agency looks at the birthday they’ve been provided, and substracts 18 years from the year field.
  6. The credit agency removes the record from the report

It’s easy, and doesn’t require anything but a change in process by the credit bureaus. No wonder they haven’t done it, when they can convince privacy advocates that they should get lists of SSN/name/dob tuples from Uncle Sam.

Bleg: Picture editor?

I used to use “Galerie” on my Mac to put nice pretty frames around pictures I posted here. (See some examples.) Galerie was dependent on … blah, blah, won’t work anymore without some components no longer installed by default. So I’m looking for a replacement that will, with little effort, put pictures in a nice frame for me as I post them.

I’m willing to spend a little money, but not a lot of time per photo.

Your advice please?

Jon Callas on Comedies, Tragedy and PKI

Prompted by Peter Gutmann:

[0] I’ve never understood why this is a comedy of errors, it seems more like a tragedy of errors to me.

Jon Callas of PGP fame wrote the following for the cryptography mail list, which I’m posting in full with his permission:

That is because a tragedy involves someone dying. Strictly speaking, a tragedy involves a Great Person who is brought to their undoing and death because of some small fatal flaw in their otherwise sterling character.

In contrast, comedies involve no one dying, but the entertaining exploits of flawed people in flawed circumstances.

PKI is not a tragedy, it’s comedy. No one dies in PKI. They may get embarrassed or lose money, but that happens in comedy. It’s the basis of many timeless comedies.

Specifically, PKI is a farce. In the same strict definition of dramatic types, a farce is a comedy in which small silly things are compounded on top of each other, over and over. The term farce itself comes from the French “to stuff” and is comedically like stuffing more and more feathers into a pillow until the thing explodes.

So farces involve ludicrous situations, buffoonery, wildly improbable/implausible situations, and crude characterizations of well-known comedic types. Farces typically also involve mistaken identity, disguises, verbal humor including sexual innuendo all in a fast-paced plot that doesn’t let up piling things on top of each other until the whole thing bursts at the seams.

PKI has figured in tragedy, most notably when Polonius asked Hamlet, “What are you signing, milord?” and he answered, “OIDs, OIDs, OIDs,” but that was considered comic relief. Farcical use of PKI is far more common.

We all know the words to Gilbert’s patter-song, “I Am the Very Model of a Certificate Authority,” and Wilde’s genius shows throughout “The Importance of Being Trusted.” Lady Bracknell’s snarky comment, “To lose one HSM, Mr. Worthing, may be regarded as a misfortune, but lose your backup smacks of carelessness,” is pretty much the basis of the WebTrust audit practice even to this day.

More to the point, not only did Cyrano issue bogus short-lived certificates to help woo Roxane, but Mozart and Da Ponte wrote an entire farcical opera on the subject of abuse of issuance, “EV Fan Tutti.” There are some who assert that he did this under the control of the Freemasons, who were then trying to gain control of the Austro-Hungarian authentication systems. These were each farcical social commentary on the identity trust policies of the day.

Mozart touched upon this again (libretto by Bretzner this time) in “The Revocation of the Seraglio,” but this was comic veneer over the discontent that the so-called Aluminum Bavariati had with the trade certifications in siding sales throughout the German states, as well as export control policies since Aluminum was an expensive strategic metal of the time. People suspected the Freemasons were behind it all yet again. Nonetheless, it was all farce.

Most of us would like to forget some of the more grotesque twentieth-century farces, like the thirties short where Moe, Larry, and Shemp start the “Daddy-O” DNS registration company and CA or the “23 Skidoo” DNA-sequencing firm as a way out of the Great Depression. But S.J. Perleman’s “Three Shares in a Boat” shows a real-world use of a threshold scheme. I don’t think anyone said it better than W.C. Fields did in “Never Give a Sucker an Even Break” and “You Can’t Cheat an Honest Man.”

I think you’ll have to agree that unlike history, which starts out as tragedy and replays itself as farce, PKI has always been farce over the centuries. It might actually end up as tragedy, but so far so good. I’m sure that if we look further, the Athenians had the same issues with it that we do today, and that Sophocles had his own farcical commentary.