EKR: December 2006 Archives


December 31, 2006

Mark Kleiman points to this article about the enormous drop in the street price of heroin. Largely due to the ready availability of high quality Afghan product, the price is down to $90/g. Ordinarily, when the price of a product drops, that's good news for consumers of the product, but Kleiman claims otherwise:
The price of having a heroin habit, by contrast, doesn't go down much. Opiate tolerance is virtually complete, so in the medium term an addict's consumption is limited only by his ability to find cash; the cheaper the stuff gets, the more he uses, without getting any more pleasure out of it once his receptors have adapted.

I didn't know that opiate tolerance was that extreme, but I'm willing to take Kleiman's word for it. That said, I'm not convinced that what he says about the cost to users is right. At any given time, the amount of heroin you can take is limited by your tolerance (lest you overdose). This represents the upper bound. The lower bound is what it takes for you to get high all. Between these two points, there's presumably some pleasure/dosage curve with decreasing marginal pleasure per dose. Thus, if heroin is a lot cheaper, you'll tend to be somewhat more aggressive in terms of how much heroin you use, but it's still limited by the overdose point.

So, if heroin is a lot cheaper, you'll tend to develop tolerance somewhat faster, but there's still a maximum rate at which you can develop it, even if you have unlimited access to the drugs. So, cheap drugs extend the time during which you can afford to maintain your habit (before it exceeds your resources). In the limiting case, if drugs were free then you would never exceed your resources. As I understand it, users develop techniques for managing tolerance—detoxing in order to let their receptors recover, for instance—cheaper drugs would seem to reduce the frequency at which you had to do this, which, if you're a user, sounds like a win.


December 30, 2006

One of the annoyances of checkin on international flights is the need to show some human your passport. No longer:

At least in YVR, United's automated checkin system will scan your passport (and green card in the same scanner which is kind of cool since they're a different size). Maybe next year our robot overlords can replace the human customs and immigration inspectors.

After a few years of deployment, our passive capture system is pretty stable, but there's nothing so stable that it can't be screwed up by some programmer. I was recently the author of such a screwup when I decided to make the system multithreaded.

It looked like a straightforward job, and it worked fine in smoke testing, but almost as soon as we started running a lot of traffic through it, it started to crash consistently with memory errors (SEGVs) in the TIME_WAIT cleanup code.

A little background is probably in order here. TCP doesn't have connection identifiers; the way you distinguish packets from different connections is by the source and destination IP addresses and port numbers. However, those aren't globally unique, so it's potentially possible to confuse packets from two different connections with the same host/port quartets if they occur sufficiently close together. In order to avoid this problem, when a TCP connection is closed it's put into a TIME_WAIT state. Any packets that potentially correspond to that connection are rejected until TIME_WAIT expires. The timer is set to be twice the maximum segment lifetime (2MSL). This makes sure that there aren't any packets from the closed connection hanging around the network. Once the 2MSL timer expires, then the host/port quartet can be reused.

TIME_WAIT implementation
Our system has two relevant data structures. Every connection has an associated tcp_conn object. These objects are stored in a hash table keyed by the host/port quartet. Whenever a new packet comes in we look up the connection in the hash table and then process the packet.

The way we implement TIME_WAIT in our code is using a sorted queue. When a connection is closed we put it at the end of the 2MSL queue (but it stays in the connection table). Since the timer is always the same length, this automatically sorts things. Periodically we traverse the queue from the front discarding any connection whose timer has expired. The data structure looks like this:

The crash

All this stuff worked great until we tried to multithread the system. The implementation I decided on was to have a bunch of worker threads (one for each processor), each of which works semi-independently. The global TCP data structures (connection table, 2MSL queue, etc.) are shared by all the threads. Of course, this means that any reads and writes have to be surrounded by thread locks, which I duly added.

As noted prevously, this all worked fine in smoke testing, but when we started to actually run performance tests, it started to crash pretty reliably. You'd be running the 2MSL queue flush routine and one of the entries in the queue would be total garbage and you'd get a segmentation fault. At this point you're probably thinking we had a locking problem and that's what we thought too. Sure enough, when we went looking for it, we found that in a moment of insanity I'd surrounded the routines that modified the conn table and the 2MSL queue with read (shared) locks rather than write (exclusive) locks. This is obviously bad and I fixed it. So far so good, right? Wrong. A little more testing revealed that we were still getting this kind of crash and detailed code inspection didn't turn up any missing locks.

Debugging the Problem (1)
Concurrency problems are notoriously hard to debug because they generally depend on timing. So, when you bring the program into the debugger and single step through it all the timing changes and you can't reproduce the problem. The situation was even worse in this case because you had to run tens of thousands of connections through the system before it would crash.1 To make matters even more confusing, setting the number of worker threads to 1 didn't fix the problem, casting doubt on the whole concurrency theory.

We relatively quickly determined that some connections that were supposed to have been destroyed were somehow ending up back on the 2MSL queue. This actually makes the situation more rather than less confusing, since there are two questions.

  1. The destructor (yeah, this is C, but it's still a destructor) is supposed to zero the connection data structure.
  2. How did it get back on the queue?

The destructor looked fine, so we had to get primitive. We added some sentinel values before and after the queue pointers to detect over and underruns. No joy — they were never triggered. We and started littering the program with printfs but nothing obvious appeared. Finally, we added a secondary state variable in the connection that was set in the 2MSL queue reaper proper. Sure enough, when these connections got resurrected, they already had the variable set. So, why weren't they being destroyed?

A bunch more printfs later we had the answer. The 2MSL queue reaper locked the global TCP state data structures--as it should. Then the destructor also tried to lock those data structures. This makes sense because it can be called in contexts where they're not already locked. Unfortunately, pthreads doesn't support recursive locks, so the second lock fails even though it's in the same thread. Unfortunately, we don't ignore the error but instead of crashing with a "can't happen" like we probably should have (though ignoring destructor failures is a pretty common practice) we handle the error smoothly and exit the destructor function without zeroizing the connection structure or removing it from the connection table.

Obviously, this is a bug and it's somehow related to our real bug. More importantly, fixing it by avoiding double locks makes the crash go away. However, it doesn't really explain what the problem was: before we call the destructor we do remove the connection from the TIME_WAIT queue, so this should just look like a memory leak. Why does it cause crashes? I hate mysteries and I hate leaving bugs partially fixed, so we kept looking.

Debugging the Problem (2)
Let's review what we know so far. Connections close and get placed at the end of the 2MSL queue. That queue is reaped from the front and any connections whose timers have expired are destroyed. However, due to our faulty thread locking code, those entries are removed from the 2MSL queue but never destroyed. So, the key question is how this is different from if things were functioning correctly:

  1. The connections are still in the connection table.
  2. The connection structures are never zeroized.
  3. The connection structures are never freed.

It's hard to see how (3) can be causing our problem. Sure, it leaks memory but that causes a different kind of crash—running out of memory—and we're not close to that yet. Similarly, it's hard to see how failing to zeroize can be causing the problem since this memory shouldn't be being used anyway. The only reason we zeroize is to help detect bugs. So, it must be something about it being in the connection table: more packets must be coming in and be being processed using this connection. Some printfs verify this. But why does that cause a problem?

The answer to this question isn't intuitive so what we ended up doing was brute forcing it. Once we realized the problem was reuse we littered that code branch with checks for whether the 2MSL queue contained bad data or not (luckily it was always ending up at the front of the queue, which is puzzling but turns out to have been a clue that we were only able to interpret in retrospect.) This let us track down where it was getting corrupted.

The answer turns out to be TIME_WAIT assassination. Ordinarily, when packets come in for a connection in TIME_WAIT we simply discard them. However, if you receive a SYN (connection open) packet that matches a connection in TIME_WAIT but the sequence number clearly is for a new connection, you cancel the 2MSL timer and start the new connection. (This actually isn't recommended behavior and not all stacks do this, but it's common enough that a passive decoder needs to implement it.) Ordinarily, this isn't something you see a lot, but because the traffic we're running is from a simulator with only a few client machines, you see a lot of host/port quartet reuse.

So, what happens when a connection is TIME_WAIT assassinated?

  1. The packet comes in and we find the relevant connection in the connection table.
  2. We notice we're in TIME_WAIT state.
  3. If the packet is a SYN and the sequence number is in the right range we need to assassinate.
  4. We dequeue the connection from the TIME_WAIT queue.
  5. We remove it from the TCP connection table.
  6. We destroy it.

Ordinarily this works smoothly, but what happens here is that connections which have already been partially destroyed stick around and get assassinated. Those connections aren't actually on the 2MSL queue, having been removed when we reaped them earlier. However, in the queue implementation we're using (BSD sys/queue), entries don't know that they have been removed from a queue, so when you re-remove them, you get weird side effects, namely a spurious re-insert.

Remove; Remove == Insert
So why do double removes of a queue entry cause spurious reinserts? The generic removal procedure for an element E in a doubly linked list L is something like:

1 If E->prev==NULL (E is the first element in L)
2   Set L->first = E->next
3 else
4   Set E->prev->next = E->next

5 If E->next == NULL (is the last element in L)
6   Set L->last = E->prev
7 else
8   Set E->next->prev = E->prev

Note that we don't need to change E at all, since it's being taken out of the list anyway. So, what happens if E is the first element in the list2, we remove it, then we remove it again? Well, when we do step 1, E->prev==NULL3 so we set L->first = E->next. Now, E->next points to whatever was right after E on the list at the time of removal. That element could have been freed, destroyed, even re-allocated by now. Since E probably wasn't also last, we jump to step 8, which might cause a crash, but probably won't4. The end result is that L->first ends up pointing to some random memory location. When we finally get around to looking at L, our code freaks out.

Note that in this particular case, what happens is that whatever entry was immediately after the entry getting doubly removed gets reinserted at the head of the queue, even if that entry has been deleted and/or destroyed long ago. What makes this so hard to track down is that the offending connection isn't the one that gets reinserted into the connection queue, so a lot of common debugging techniques (e.g., trying to track the fate of the offending connection) don't work well.

1. Don't tell me to use Valgrind. It crashed and didn't find anything. I miss Purify (which might not have found anything but most likely wouldn't have crashed).
2. Which is what always happens in 2MSL queue reaping. Because the connections are sorted on the queue, we never reap a connection unless all previous connections have also been reaped.
3. Note that there's a dependency on the way I'm checking whether E is first. If I compared to L->first the behavior would be different and we'd always end up executing line 4, which would (in this case) induce a crash because E->prev == NULL. Of course, BSD sys/queue uses quite different algorithms.
4 Remember that destruction of E->next probably failed as well, so this isn't even a free memory write. And FMR's don't generally cause immediate crashes, though Purify/Valgrind/etc. do catch them..

UPDATE: Fixed a bug in line 4, found by Kevin Ballard.


December 29, 2006

Sitting in the YVR Maple Leaf Lounge this morning I reflexively looked for wireless access, but of course it way a pay hotspot. But on my way to the bathroom I noticed that they have a table with a bunch of chairs and Cat 5 cables attached. Plugging in, it turns out that there's quite workable—though a bit slow—Internet access. Worth knowing.

December 27, 2006

Went climbing last night at The Edge. Normally when you drop in at a place like this you can't find anyone to belay you, so you end up just bouldering. The Edge has an unusual feature: auto-belay devices. Basically, it's a web belt attached to what seems to be a spring-loaded device at the top of the wall. You attach it to your harness and as you climb it automatically takes up the slack. If you fall off, it pays out slowly, lowering you to the ground safely (at least theoretically).

The obvious advantage of a gizmo like this is that it lets you climb on your own without a belayer. Also, you can train continuously without having a belay slave. The major practical disadvantage is that it doesn't lock, so there's no way to hang and work out a move. If you fall, you have to start over again from the bottom, which means that it's a lot harder to work through difficult moves, since you're tired by the time you get there.

Psychologically, though, it's even weirder. When someone is belaying you and you fall, the rope stretches a bit (assuming it's a dynamic rope) but then you stop dead. With an auto-belay, you just fall slowly. If you're used to a regular belay, your first thought is "my belayer has screwed up and I'm about to fall to my death". That's not really an easy reaction to suppress, which makes it a lot harder to climb near your limit, as well as making letting go to descend at the top of the climb a real act of will.

Last night, Mrs. Guesswork, Natasha, and I went looking for dinner in Vancouver. After an abortive attempt to get into Guu with Garlic (90 minute wait) we ended up at Simba's Grill. Pretty solid food with a sort of exotic taste. Highlights were Prawns Pili-Pili (barbecued (on a stick)) and Kuku Paka (chicken in a green coconut curry with a really unusual, subtle taste). Both came on rice, which was extremely well executed, fluffy and with a strong saffron taste. Fast, friendly service. Worth a shot.

December 26, 2006

Anecdotally, it's starting to seem like a pretty good algorithm for getting Internet service on the road is to look for a neighborhood coffee shop. A large fraction of the one's I've been in lately seem to have wireless Internet service, often of the "buy something and we'll give you the WEP password" variety. Given that it's pretty hard to sit in a Starbucks and not buy some drink, this seems to dominate the T-Mobile/Starbucks commercial offering—assuming you can find a suitable coffee shop. Even if you weren't planning to buy anything, $3-5 for a latte dominates T-Mobile's $10 daily fee (the economics change a bit if you travel enough to actually subscribe to a data plan).

As this gets more and more common, it seems like the lifespan of the Starbucks offering is likely to be kind of limited. Remember that for Starbucks it's not just a matter of people substituting their wireless provider but also of them substituting their coffee provider. And since the actual marginal cost of providing this service is so cheap...


December 24, 2006

  • At 6:00 in the morning, it takes less than 10 minutes to get from Anza Parking to SFO Terminal 2
  • The elite security line is to the right of the stairwell/pillar as you enter SFO. Don't be fooled by the regular security line.
  • If you accidentally bring a Nalgene bottle of water through the security checkpoint, they make you go back outside the sterile zone to dump it out. Apparently the TSA is too busy collecting your personal information to install a bucket.1
  • If you fly at an inconvenient time when lots of people who aren't frequent travellers are also flying, you might get an OpUp, even if you're only 1P.
  • Don't believe Orbitz when they tell you that your car is reserved in some random non-airport location. Verify that that location is actually open on the day that you're picking up the car. Don't expect Orbitz customer service to actually do anything useful to solve your problem when it turns out that it isn't open.
  • The Semiahmoo Blenz outlet has free Internet if you buy something. The scones are pretty good, as is the dark chocolate hot chocolate. They also have power.

That is all.

1. Mrs. Guesswork points out that I could have just drunk the water. Would that I had thought of this at the time.


December 22, 2006

Mrs. Guesswork and I are watching Harry Potter and the Goblet of Extreme LiabilityFire and in my sheer frustration over the plot holes I'm reminded of Tom Franck's hatchet job on Quidditch. Amazingly, HPATGOEL is even more nuts. Spoilers below.

December 20, 2006

This Chrishannukwanzaa I was the proud recipient of some SquidSoap:

The concept here is that the top of the dispenser has an ink pad on it so that when you press down to get the soap it puts an ink mark on your hand. That ink mark takes about 20 seconds to wash off, so you get positive reinforcement of good washing habits. This is a pretty clever idea but the execution is a little off. With my model you need to press down unnaturally hard to get the ink to mark your hand much at all. That seems easily fixable.

A more serious problem is that while just getting people to wash long enough is important, there's a lot more to good handwashing than that—you need to wash your whole hand, not just the palms. Really getting your hands clean turns out to require quite a bit of dedicated scrubbing. I once attended an exhibit at the Puyallup Fair designed to demonstrate this. They had you rub this lotion onto your hands and then wash it off. Once you thought you'd done an adequate job of washing you put your hand under a UV light at which point all the lotion that you haven't washed off glows brightly. I thought I'd done a good job of washing already and was appalled at all the places that were still glowing (the webbing in between my hands, cuticles, under the nails, etc.) This is one reason for the growing emphasis on waterless hand sanitizers which do a pretty good job with less scrubbing. Still, washing for 20 seconds is a lot better than nothing. Now if we could just get a gizmo which would teach people to wash their hands at all!


December 19, 2006

As you may have noticed, it's become quite inconvenient to get pseudoephedrine. Luckily, Pfizer has rolled out a replacement, Sudafed PE, containing phenylephrine, a common topical nasal decongestant Not so luckily, there's no good evidence that it works as an oral decongestant, and substantial reason to think it doesn't, as indicated in this review by Ronald Eccles (þ Robert Cohen via Radley Balko) :
The aim of this review was to investigate the rationale for replacing the nasal decongestant pseudoephedrine (PDE) with phenylephrine (PE) as a means of controlling the illicit production of methamphetamine. A literature search was conducted in electronic databases and use of textbooks. Restrictions have been placed on the sale of PDE in the USA in an attempt to control the illicit production of methamphetamine. This has caused a switch from PDE to PE in many common cold and cough medicines. PE is a poor substitute for PDE as an orally administered decongestant as it is extensively metabolized in the gut and its efficacy as a decongestant is unproven.

Pseudoephedrine, by the way, does work. Outstanding!


December 18, 2006

Asahi reports on Nathan's hot dog champ Kobayashi's training regimen:
"Eating is my job," Kobayashi says. His life very much resembles that of athletes participating in conventional sports. Two months ahead of an event, he gets into fighting mode and starts maintaining meal logs. To put on weight (he now weighs between 70 to 80 kg at competitions) Kobayashi eats six to eight high-protein meals a day, totaling about 10,000 calories. But he emphasizes that his usual meal style is normal, eating conventional food at an average speed.

Wannabe speed eaters should start by increasing their food intake, Kobayashi advises. He emphasizes the importance of keeping logs. "Without precise logs, you can't tell whether your stuffiness comes from overeating or poor metabolism."

The champ lifts weight to tone up his muscles and improve his metabolism. He says that having a high metabolic rate makes weight control easy. Also by staying active, he is able to maintain motivation when no competitions are in sight. "I don't directly work on my abs so I won't damage them," he says. He has started running 10 kilometers in the morning and 10 kilometers at night to improve stamina.

I know elite triathletes who put in less than 20 km (13 mi)/day. A lot less.


December 17, 2006

The Times runs the story of Donald Vance, a US contractor in Iraq who was an informant for the FBI and then was captured when the company he worked for was raided:
The detainee was Donald Vance, a 29-year-old Navy veteran from Chicago who went to Iraq as a security contractor. He wound up as a whistle-blower, passing information to the F.B.I. about suspicious activities at the Iraqi security firm where he worked, including what he said was possible illegal weapons trading.

But when American soldiers raided the company at his urging, Mr. Vance and another American who worked there were detained as suspects by the military, which was unaware that Mr. Vance was an informer, according to officials and military documents.


Nathan Ertel, the American held with Mr. Vance, brought away military records that shed further light on the detention camp and its secretive tribunals. Those records include a legal memorandum explicitly denying detainees the right to a lawyer at detention hearings to determine whether they should be released or held indefinitely, perhaps for prosecution.

The story told through those records and interviews illuminates the haphazard system of detention and prosecution that has evolved in Iraq, where detainees are often held for long periods without charges or legal representation, and where the authorities struggle to sort through the endless stream of detainees to identify those who pose real threats.

"Even Saddam Hussein had more legal counsel than I ever had", said Mr. Vance, who said he planned to sue the former defense secretary, Donald H. Rumsfeld, on grounds that his constitutional rights had been violated. "While we were detained, we wrote a letter to the camp commandant stating that the same democratic ideals we are trying to instill in the fledgling democratic country of Iraq, from simple due process to the Magna Carta, we are absolutely, positively refusing to follow ourselves."

A spokeswoman for the Pentagons detention operations in Iraq, First Lt. Lea Ann Fracasso, said in written answers to questions that the men had been treated fair and humanely, and that there was no record of either man complaining about their treatment.

She said officials did not reach Mr. Vances contact at the F.B.I. until he had been in custody for three weeks. Even so, she said, officials determined that he posed a threat and decided to continue holding him. He was released two months later, Lieutenant Fracasso said, based on a subsequent re-examination of his case, and his stated plans to leave Iraq.


The military has never explained why it continued to consider Mr. Vance a security threat, except to say that officials decided to release him after further review of his case.

In case it's not obvious, this is why the ordinary criminal justice system doesn't allow people to be held indefinitely without access to counsel or habeas corpus hearings. If your job is to catch and detain security threats, you don't have a lot of incentive to let people if you aren't totally sure about them. For that matter, you don't have a lot of incentive to sort out who's a security threat and who's not. The point of an adversarial system is to institutionalize that kind of incentive. Of course, in this particular case the suspect is an American citizen so he had family who could make a fuss (though as you can see above, it's not entirely clear why Mr. Vance was released, I imagine bad PR is something even the American military cares about.) I suspect that having your average Iraqi family upset about the fact that their son is being held incommunicado probably isn't quite as effective.



December 16, 2006

KishKish has released a Skype add-on that does voice stress analysis (VSA) (þ ITwire). The American Polygraph Association (not exactly an unbiased source) claims that VSA doesn't work, but let's say it does work. How hard is it to counteract? The high-tech way is to build a filter that removes the signal that the analyzer on the other end is looking for. This probably isn't that hard, especially since the developers of the filter can use a local copy of the analyzer as an oracle to figure out whether they've got it right or not. The low-tech way to do this is to run a local copy of the voice stress analyzer and use it as a biofeedback monitor to detect when the analyzer on the other end would think you were lying. Of course, if you're dealing with someone who is running voice stress analysis on your phone call, you might consider finding new people to talk to.
While nearly all children are able to digest milk, a large fraction of adults lose their ability to process lactose (milk sugar) as they age (lactose intolerance). However, in many cultures (e.g., the Masai, dairy is a major part of the diet, so being able to consume milk is an obviously desirable adaptation, or rather four adaptations.

In this week's Nature Genetics (behind paywall, this post based on the Science summary above). Tishkoff et al. report on a study of African populations finding three novel mutations that allow the digestion of lactose (add this to a previously known mutation found in Finns). As with altitude adaptation, we see that there's been a remarkable amount of separate adaptation to the same problems in different human populations.


December 14, 2006

The feds have cracked down on pseudoephedrine sales but it's still possible to order it from Amazon. Possible, but not convenient:
Due to recent DEA (U.S. Drug Enforcement Agency) restrictions on the sale of products containing Pseudoephedrine ("PSE"), the drugstore.com Web Store is now required to obtain additional information from customers who order PSE products.

The DEA now requires that we verify identification by seeing a copy of photo identification from all customers who purchase items that contain PSE. We are pleased to offer three methods by which you can satisfy this requirement:

1. You may scan or take a legible digital photo of your drivers license, or other photo ID issued by a State or Federal government, and email a copy to pse@drugstore.com. --Recommended--

2. You may fax a copy of your drivers license, or other photo ID issued by a State or Federal government, to the following number 1-866-764-4886 (poor quality or illegible copies will delay your order).

3. You may mail a copy of your drivers license, or other photo ID issued by a State or Federal government, to the following address:

I wonder what they do with that low quality scan of your driver's license, something that really isn't that hard to fake up, assuming you know someone's name and DL #, something which isn't exactly a secret. It seems like there are two possibilities. First, they could look it up in some central database to verify that really exist and live at the address that you're having stuff shipped to. Of course, if they do that, then there's no need to actuallly see your license, they just need the number to use it as a database locator and verify that it matches your address. The other alternative is that they just stuff it into some file folder somewhere. That doesn't seem very useful either.

What's more likely, actually, is that they're just complying with a generic requirement to show a driver's license that never really contemplated mail particularly well. Having to show a drivers license for in-person sales does make (some) sense (assuming that you think restricting pseudoephedrine sales is a good idea in the first place). It lets you identify who is buying the drug and therefore at least in theory prevent multiple sales. But it's not really clear it does anything very useful in this context.


December 13, 2006

Hack report has an interview with MagiQ CEO Bob Gelfond in which he claims that quantum cryptography is almost ready for prime time:
What's the standard price for the appliance and what is included?

For a point-to-point encryption you need a system that consists of 2 appliances - sender and receiver. The cost is around $100k, plus support depending on your needs.

When do you think we'll see service providers offer quantum cryptography services to their end-customers?

This will happen within one year and we'll see fairly wide adoption within the next three years. We are working with big carriers such as Verizon and AT&T as well as some companies that own fiber networks. The goal is to embed quantum cryptography into the technology infrastructure so it becomes totally transparent to the end-user. For example, if you are already leasing a fiber line, you can then add an extra level of security by activating the quantum service. The whole thing won't be disruptive to your infrastructure and it can sit on top of whatever you are using now. Since it won't interfere with your existing technology you can have a fall back mechanisms to switch back to whatever you have today.

The important thing to remember is that the security guarantees of quantum key exchange (such as they are) only apply when you have a direct link between point A and point B--i.e., if you're renting a fiber from AT&T between two offices. They don't apply if the data is being packet switched, such as in the kind of MPLS-style virtual cirtuit that people typically buy (because buying a dedicated fiber is too expensive). So, if AT&T sells you a QC-protected line, it just goes to one of their routers. Of course, AT&T could have a QC-link for each hop, but that's not an end-to-end security guarantee. You now have to trust each router in every data center.

Moreover, the current limit on a QC link is about 120 km. After that you have to use repeaters, which creates another potential point of compromise.

Apart from the usual high assurance customers, do you see any other industries that can benefit from (and justify) a quantum cryptography solution?

I think so, anyone who has to store and secure records for a number of years will benefit from it. One strategy eavesdroppers can deploy is to capture everything they can get their hands on. Even if they can't decrypt it today, they might be able to do that in a few years down the road. So the only way to defend against that is to use quantum cryptography. You have to make sure it's not just secure today but also going forward. Take healthcare for example, they have an obligation to protect my healthcare data forever. The real threat is that while theoretically current systems might be impossible to crack, the reality is that keys are not flipped frequently enough or might not be stored securely. All that can be used by an attacker to start a brute force attack. So if you have enough repeats it might just take them a couple of days to break them. And many companies do not flip their keys very frequently since it's a time-consuming task. In contrast if you deploy our system -- keys get flipped every few seconds -- automatically.

This argument confuses several points. What you have to know is that quantum cryptography systems like MagiQ's are actually used as what's called "quantum key exchange" mode. The bit rate of the quantum cryptography system isn't high enough to carry data so you use it to exchange keys which are then used in a conventional cipher like AES to encrypt the actual data. So, in that respect, QC systems are quite a bit like a conventional cryptographic protocol like SSL/TLS or IPsec, but with the QKE replacing the Diffie-Hellman/RSA/whatever.

Gelford's claim here is that the attackers are going to get their hands on (either by capturing off the network or getting access to your stored data) your encrypted data and mount a brute force attack on it in the future. In order for this to be plausible, one has to assume one of three things:

  • The attackers will somehow get access to the stored keys.
  • There is some analytic attack on current symmetric systems such as AES that we don't know about.
  • Attackers will in the future have radically better capabilities than we imagine (because the keys used for AES are outside the realm of what can be brute forced with any kind of conventional computation in anything like the foreseeable future).

Case 1 is exactly the same for QKE and conventional systems, since however you exchanged the keys you have to store them somehow. In fact, if you establish a lot of unrelated keys frequently then in some sense this makes the situation worse because you need to store them somewhere that has a lot of space which makes using really secure storage methods more difficult. This is one reason people tend to store their keys under some master key. So, there's a tradeoff here that doesn't clearly favor QC.

Cases 2 and 3 are sort of the same. In both cases we assume you don't have the keys but you do have the ciphertext. Now, there are two major reasons why in this attack model you might want to use a lot of keys rather than one. The first is that old-style ciphers (e.g., Enigma) were often easier to attack if you had a large amount of ciphertext or ciphertext/plaintext pairs. I think this is what Gelford means when he talks about repeats. This isn't really true for any modern algorithm except when the amount of ciphertext gets really huge (~1010 bytes for DES, ~1020 bytes for AES). This only really applied to analytic attacks in any case. In a brute force attack, one or two plaintext/ciphertext pairs are enough. The other reason you'd want to use a large number of keys is to slightly increase the attacker's work factor. If he has to attack 100 keys rather than 1, then it's 100 times harder for him. Mostly, if you get to the point where the cipher is so weak (case 3) that you have to worry abot this you need a new cipher and QKE isn't going to help you much.

The other weird thing about this argument is that conventional systems are quite capable of rekeying frequently and if you use Diffie-Hellman, there's no real concern about exposure of long-term keys. Sure, people don't typically rekey their IPsec or SSL connections frequently, but it's a simple software change and certainly quite a bit more convenient than buying a bunch of gear from MagiQ.


December 11, 2006

If you're a phisher your basic strategy is to convince the victim that he's talking to some site he regularly does business with. Now, you can't control the user's experience when he's talking to the legit site so what you do instead is make the experience you provide as much like the legit site as possible, hence tools for mirroring the site you're impersonating. If you're a potential victim of impersonation, you want to get the user into the habit of not trusting indicia that the phishers can easily indicate. To that end, you might want to tell your users not to click on URLs they receive in e-mail claiming to be from you. Unless, that is, you're Amazon:
From: Amazon.com Customer Service 
Date: 11 Dec 2006 11:42:28 -0800
Subject: Payment for Your Amazon.com Order (#ORDER-NUMBER-HERE)
To: ekr@rtfm.com
Cc: payment-update@amazon.com

Greetings from Amazon.com.

We're writing to let you know that we are having difficulty processing your
Visa (exp. YYYY/MM).

We will try charging your credit card again shortly. It is not necessary to
place a new order, but you may want to review the payment information for
your order and make sure it is correct and current.

To do this:

1. Go to our home page (www.amazon.com) then click "Your Account" on the
top right menu.

2. Choose the option "Change payment method" (found under "View by Order"
in the "Where's My Stuff" box).

3. After you sign in, you will see all your current open orders. You can
click the "View or change order" button beside any order and make changes.

4. Click "Change" button in the "Payment Information" box beside "Payment
Method." At this point, you may review your current payment method, choose
a different payment method, or enter a new one.

Thanks for shopping at Amazon.com.

Amazon.com Customer Service

Please note: This e-mail was sent from a notification-only address that
cannot accept incoming e-mail. Please do not reply to this message.

Now, this mail has been sent in plaintext (i.e., text/plain) so there aren't any links. (Though you could of course get caught by cutting and pasting out of the message.) Unfortunately, Gmail decided to help me out and turned everything that looks like a domain name or URL into a link. Now, as it happens I had screwed up something with my credit card and this isn't a phishing message and, but it just as easily could have been. For extra credit, if you put a link to a different location in your message, Gmail will display it exactly like the links it auto-formats. Outstanding!


December 10, 2006

If you're a Chicago expat you complain about how you can't get decent pizza and if you're from Philadelphia you complain about how you can't get a decent cheesesteak. It's pretty hard to understand what the problem is here: you're frying thinly sliced meat, slapping on some American cheese and then putting it on a bun. Yet, for some reason whenever I've tried cheesesteaks at local places they've fallen rather short of Philly standards (this isn't just that things taste better in memory—I've been back to Philadelphia recently enough to have a reference point).

Anyway, some research turns up Jersey Joe's in San Carlos, which makes a pretty solid steak. Not the best I've ever had, but easily good enough to save a 5 hour flight to Philadelphia.


December 9, 2006

A few weeks ago I helped a friend calibrate the color on his photo printer. The basic idea here is that you print out a test sheet containing patches of various colors. You then scan each patch with a handheld sensor. The color correction software compares the intended color to the actual printed color and generates a correction profile for the printer.

The process is simple but tedious. The basic test sheet contains a hundred or so patches and you need to scan each one individually. Something like this:

Once you've printed the test sheet, you position the sensor over each patch, press the botton on the top of the sensor, wait for it to scan, and then move onto the next patch. Aside from being boring, this procedure is kind of error prone. It's pretty easy to forget to press the button and get off by one or two targets. And since the whole point of the exercise is to deal with the printed colors being wrong, the software doesn't freak out when the colors don't match. Luckily, it does tell you which patches it thinks you've scanned, so by the time you get to the end of the row, you do figure out it but then you probably have to rescan it.

This isn't awful, but there's an easy hack that would make it better. The reason that the software can't detect that you've made a mistake is that the the test sheet is basically a color ramp, so color patch n and color patch n+1 are quite similar. Simply re-arranging the colors so that contiguous colors are quite different would make it possible to automatically detect mistakes (unless the printer is incredibly screwed up).


December 5, 2006

Thanks to the DVD TV-show time machine, I'm watching The Rockford Files Season 1 (1974). Rockford's at the Office of Vital Statistics:

Rockford: Could you tell me, are the dates of death and the birth certificates cross-referenced.
Clerk: Are you kidding, that would be a monumental task.
Rockford: So, the date of death doesn't appear anywhere on the birth certificate index.
Clerk: You got it.
Rockford: Doesn't that leave a rather large hole in the system?
Clerk: They're a lot of holes in the system. So what?
Rockford: So what? Do you realize that you could adopt a new identity by ordering a birth certificate of somebody that's already dead. And you'd mail it out without question because the date of death doesn't appear anywhere in the birth records.
Clerk: You're a genius.

Of course, with digital records this is a simple database query—though that isn't to say that modern birth certificates are handled much better.

Of course, 1974 was right when records were starting to go digital. Later in the episode Rockford has someone look up a bunch of insurance records, which goes pretty fast since "they're all on the computer."


December 4, 2006

In a post titled "Is there a simple way to make a pdf call home?" and filed in the category "good code", Larry Lessig asks:
Let's say you release a draft of a paper using PDF. But when people open the paper to read it, you'd like the PDF to check whether there's a more recent version available. If there is, you'd like it to indicate as much — somewhere. Obviously, you could always include a link that says "For the most current version, go here." But is there a way to say, "A more recent version of this document is available here."?

I'm sure a feature like that would never be abused!


December 3, 2006

In all the excitement about DHS's ATS program and "terrorist scores", one of the things that's getting missed is that the system isn't just being used to look for terrorists, but also "criminals":
The Homeland Security Department called the program "one of the most advanced targeting systems in the world" and said the nation's ability to spot criminals and other security threats "would be critically impaired without access to this data."

It's also been in use since the 1990s:

Ahern declined to disclose any of the rules, but a Homeland Security document on data-mining gave this innocuous example of a risk assessment rule: "If an individual sponsors more than one fiancee for immigration at the same time, there is likelihood of immigration fraud."

Ahern said ATS was first used to rate the risk posed by travelers in the late 1990s, using personal information about them voluntarily supplied by air and cruise lines.

I totally agree that stopping immigration fraud justifies the government knowing what I had for lunch on my last flight to Canada. Don't you? Of course, what's especially telling about this example is that duplicate fiancee visas are something that CIS can easily detect via ordinary records searches (i.e., look for duplicate applications under the same SSN) without any kind of fancy data mining.

DHS has been secretly developing/using an Automated Targeting System. Basically, it's a data mining system designed, well, let's let AP tell it:
The scores are assigned to people entering and leaving the United States after computers assess their travel records, including where they are from, how they paid for tickets, their motor vehicle records, past one-way travel, seating preference and what kind of meal they ordered.


Government officials could not say whether ATS has apprehended any terrorists. Customs and Border Protection spokesman Bill Anthony said agents refuse entry to about 45 foreign criminals every day based on all the information they have. He could not say how many were spotted by ATS.


The government notice says some or all of the ATS data about an individual may be shared with state, local and foreign governments for use in hiring decisions and in granting licenses, security clearances, contracts or other benefits. In some cases, the data may be shared with courts, Congress and even private contractors.


In a privacy impact assessment posted on its website this week, Homeland Security said ATS is aimed at discovering high-risk individuals who "may not have been previously associated with a law enforcement action or otherwise be noted as a person of concern to law enforcement."

Ahern said ATS does this by applying rules derived from the government's knowledge of terrorists and criminals to the passenger's travel patterns and records.

For security reasons, Ahern declined to disclose any of the rules, but a Homeland Security document on data-mining gave an innocuous example of a risk assessment rule: "If an individual sponsors more than one fiancee for immigration at the same time, there is likelihood of immigration fraud."

Here's the list of the "predictors" they're using:

  • Passenger manifests
  • Immigration control records
  • Information from personal searches
  • Property seizure records
  • Vehicle seizure records
  • Aircraft arrival records
  • Visa data
  • FBI National Criminal Information Center data
  • Treasury enforcement actions involving people and businesses
  • Dates of flight reservation and travel
  • Passenger name
  • Passenger seat information
  • Passenger address
  • Form of travel payment
  • Billing address
  • E-mail address
  • Telephone numbers
  • Travel itinerary
  • Miles flown as a frequent flyer
  • Travel agency used
  • Travel agent who made arrangements
  • Passenger travel status
  • History of one-way travel
  • History of not showing up for flights
  • Number of bags
  • Special services, such as need for wheelchair or special meals for dietary or religious reasons
  • Voluntary/involuntary upgrades
  • Historical changes to the passenger's record

A few observations:

  • Deciding whether any given variable is a good predictor for any other variable is a hard statistics/econometrics problem. It's not incredibly difficult if the effect is big and the variables are reasonably independent, but generally that's not the case. Doing a study like this with 25+ predictors is a major undertaking—whole papers are written on the topic of a single predictor. Think of all the work that's gone into the far easier question of whether moderate levels of drinking improve health.
  • The more variables you have, the larger data set you need in order to perform the fit. It's very hard to believe that we have anywhere enough data points (known terrorists plus their travel histories) in order to do a proper study. We of course have much more data on "criminals" but even then, answering questions like this with any level of certainty is really hard.
  • At least some of these predictors seem to have a high degree of multicollinearity. In particular, frequent travelers tend to have a lot of frequent flier miles, voluntary upgrades, and low baggage check rates. This kind of multicollinearity tends not to be great when you're performing regression analysis. Of course, it's certainly possible that whoever is doing the analysis pruned their predictor set, but it suggests that there's some gap between what we're seeing and what's really being done (or the analysis isn't being done properly). It's hard to distinguish these without more data.
  • Looking at a lot of the predictors here, it's pretty hard to believe most of them provide a useful signal. I know people with all kinds of travel histories from no travel to United 1K, and as far as I know none of them are terrorists. Personally, I've been everything from UA "General Member" to Premier Executive and haven't blown up any planes.

Unsurprisingly, DHS hasn't disclosed any real information about their methodology, but based on the above, I'm skeptical that they've done any real statistical modelling of the data (whether by regression analysis or neural networks or whatever). More likely, it's just some set of rules of thumb that DHS has come up with, maybe augmented by some ad hoc stats. While you don't necessarily need a model where everything is significant at p<.05, you definitely need effects that give you a very large odds ratio. Otherwise you end up with totally unacceptable false positive rates.

I can certainly understand that DHS wouldn't want to reveal their methodology. After all, in theory terrorists or criminals could change their behavior to evade detection. Of course they could perfectly well release whether they've actually found any terrorists using these techniques. On the other hand, if it turns out they don't work I could understand why they wouldn't want to release that either.


December 1, 2006

TSA is testing backscatter x-ray scanning for secondary screening (þ Lauren Weinstein):
The technology, called backscatter, has been around for several years but has not been widely used in the U.S. as an anti-terrorism tool because of privacy concerns.

The Transportation Security Administration said it has found a way to refine the machine's images so that the normally graphic pictures can be blurred in certain areas while still being effective in detecting bombs and other threats.


The security agency's Web site indicates that the technology will be used initially as a secondary screening measure, meaning that only those passengers who first fail the standard screening process will be directed to the X-ray area.

Even then, passengers will have the option of choosing the backscatter or a traditional pat-down search.

So, on the one hand, these backscatter x-rays are pretty privacy defeating, not to mention unflattering. They certainly show a lot more than just weapons, and it's not like you want everyone checking out your body shape, piercings, etc. On the other hand, it's clearly more convenient than actually being patted down, especially since there have been reports that the screeners aren't necessarily as courteous as one would like, especially when women are being patted down. So, arguably if you're going to be aggressively searched, you'd prefer it to be by backscatter x-ray rather than by pat-down.

On the third hand, precisely because this kind of screening is relatively fast and physically unintrusive—and the general public isn't largely aware of how much it reveals—you should expect the barriers to it being widely deployed to be a lot lower than for patdowns. As Weinstein observes, it will eventually be practical to use this kind of scanning as a form of primary rather than secondary screening. It's not clear that that's an equilibrium that those of us who do care about this kind of privacy—and who expect that our fellow citizens eventually will as well— are likely to welcome, especially since we don't exactly have a rash of hijackings and plane bombings with the current system. (Don't forget, the 9/11 hijackers used weapons that were allowed through security.) >