Showing posts with label physics. Show all posts
Showing posts with label physics. Show all posts

[ next | prev | up ]

Permissive Access Links

In 2004, Steve Bellovin gave a talk at Usenix Security speculating about permissive access links (PALs), the (supposedly impossible to bypass) locks that protect nuclear weapons. He repeated the talk in 2006 at the general Usenix. In Bellovin's talk, “Nuclear Weapons, Permissive Action Links, and the History of Public Key Cryptography” (MP3; also PDF and HTML), he says that “Bypassing a PAL should be, as one weapons designer graphically put it, about as complex as performing a tonsillectomy while entering the patient from the wrong end.” But how do they work? Are there lessons that apply to building other kinds of secure systems? He touches on these questions, but in the end, it's mostly speculation. Even so, it's a fascinating talk.

He does tease out a few interesting historical details. In particular, National Security Action Memorandum 160, signed by President Kennedy, has been claimed by former NSA insiders to be the impetus for the NSA's invention of public key cryptography. There is no evidence that public key cryptography ended up being used in PALs, but it's possible that digital signatures were invented in direct response to the requirement that, after a weapon was launched, it be possible to determine who authorized the launch. It's also possible that public key cryptography was invented and used to transmit the PAL codes securely.

Other interesting facts. The U.S. offered PALs to the Soviets (presumably to keep weapons from falling into other hands), but they turned them down. For years after the initial U.S. PAL deployments, the launch codes were all set to 00000000. The bandwidth of the extra-long frequency extremely low frequency (ELF) communication link to submerged submarines is 1 bit/minute.

Traffic Lights and Buridan's Ass

Buridan's ass is a donkey in a thought experiment proposed by French philosopher Jean Buridan. Placed exactly halfway between two bales of hay, the purely rational, deterministic donkey starves to death trying to decide which to eat: there is no reason to prefer one bale over the other.

Arbiters, electronic circuits that decide whether a particular voltage is a binary 0 or 1, have the same problem: voltages in the middle can force arbitrarily long decision times. This is known as the arbiter problem or glitch phenomenon.

Leslie Lamport observed that the arbiter problem also explains human indecisiveness at critical moments. His paper, “Buridan's Principle,” attempts to make the phenomenon known outside of computer science. Lamport explains the paper's fate:

I have observed that the arbiter problem occurs in daily life. Perhaps the most common example is when I find myself unable to decide for a fraction of a second whether to stop for a traffic light that just turned yellow or to go through. I suspect that it is actually a cause of serious accidents, and that people do drive into telephone poles because they can't decide in time whether to go to the left or the right.

A little research revealed that psychologists are totally unaware of the phenomenon. I found one paper in the psychology literature on the time taken by subjects to choose between two alternatives based on how nearly equal they were. The author's theoretical calculation yielded a formula with a singularity at zero, as there should be. He compared the experimental data with this theoretical curve, and the fit was perfect. He then drew, as the curve fitting the data, a bounded continuous graph. The singularity at zero was never mentioned in the paper.

I feel that the arbiter problem is important and should be made known to scientists outside the field of computing. So I wrote this paper, which describes the problem in its classical formulation as the problem of Buridan's ass—an ass that starves to death because it is placed equidistant between two bales of hay and has no reason to prefer one to the other. Philosophers have discussed Buridan's ass for centuries, but it apparently never occurred to any of them that the planet is not littered with dead asses only because the probability of the ass being in just the right spot is infinitesimal.

So, I wrote this paper for the general scientific community. I probably could have published it in some computer journal, but that wasn't the point. I submitted it first to Science. The four reviews ranged from “This well-written paper is of major philosophical importance” to “This may be an elaborate joke.” One of the other reviews was more mildly positive, and the fourth said simply “My feeling is that it is rather superficial.” The paper was rejected.

Some time later, I submitted the paper to Nature. I don't like the idea of sending the same paper to different journals hoping that someone will publish it, and I rarely resubmit a rejected paper elsewhere. So, I said in my submission letter that it had been rejected by Science. The editor read the paper and sent me some objections. I answered his objections, which were based on reasonable misunderstandings of the paper. In fact, they made me realize that I should explain things differently for a more general audience. He then replied with further objections of a similar nature. Throughout this exchange, I wasn't sure if he was taking the matter seriously or if he thought I was some sort of crank. So, after answering his next round of objections, I wrote that I would be happy to revise the paper in light of this discussion if he would then send it out for review, but that I didn't want to continue this private correspondence. The next letter I received was from another Nature editor saying that the first editor had been reassigned and that he was taking over my paper. He then raised some objections to the paper that were essentially the same as the ones raised initially by the first editor. At that point, I gave up in disgust.

I still think that this paper is worth publishing for a general scientific audience. Among other things, it has a nice analysis of a quantum-mechanical arbiter. However, I have no idea where to publish it.

My problems in trying to publish this paper are part of a long tradition. According to one story I've heard (but haven't verified), someone at G. E. discovered the phenomenon in computer circuits in the early 60s, but was unable to convince his managers that there was a problem. He published a short note about it, for which he was fired. Charles Molnar, one of the pioneers in the study of the problem, reported the following in a lecture given on February 11, 1992, at HP Corporate Engineering in Palo Alto, California:

One reviewer made a marvelous comment in rejecting one of the early papers, saying that if this problem really existed it would be so important that everybody knowledgeable in the field would have to know about it, and “I'm an expert and I don't know about it, so therefore it must not exist.”

Lamport's publications page is full of interesting papers.

Debugging the Universe

Every programmer knows what debugging is. Given a program that isn't behaving as expected, you slowly refine your understanding of both the program and the anomalous behavior until you understand exactly why the two aren't in agreement. Sometimes the bug is in the program, other times in your understanding of the program. Then you fix it.

Physicists debug the universe. When the universe doesn't behave as expected, they debug it, trying to reconcile their understanding of the universe and what they are seeing. The difference is that the bug, by definition, is always in their understanding and never in the universe.

During the development of the Global Positioning System (GPS), the physicists and programmers had to debug general relativity. To tell the story, you need to know a tiny bit about how GPS works.

Each GPS satellite broadcasts a known pseudo-random number sequence. A simple GPS receiver has its own pseudo-random sequence generator that is synced with the satellites. By timing how far “behind” the satellite sequences appear to be compared to the receiver's time, the receiver can determine how far away they are. Using the known positions of and distances to three satellites, a GPS receiver can triangulate its position in three-dimensional space. If the GPS receiver's clock is not exactly in sync with the satellites, it can use readings from four satellites to triangulate its position in four-dimensional space-time, synchronizing its clock in the process.

All this assumes that the clocks in the satellites are running at the same speed as the clocks on the Earth, but the satellites are literally running circles around the Earth; at those speeds, relativity kicks in and unexpected behaviors emerge. This was actually something the GPS engineers had to consider. Peter Galison tells the story better than I can:

According to relativity, satellites that were orbiting the earth at 12,500 miles per hour ran their clocks slow (relative to the earth) by 7 millionths of a second per day. Even general relativity (Einstein's theory of gravity) had to be programmed into the system. Eleven thousand miles in space, where the satellites orbited, general relativity predicted that the weaker gravitational field would leave the satellite clocks running fast (relative to the earth's surface) by 45 millionths of a second per day. Together, these two corrections add up to a staggering correction of 38 millionths (that is, 38,000 billionths) of a second per day in a GPS system that had to be accurate to within 50 billionths of a second each day. Before the first cesium atomic clock launch in June 1977, some GPS engineers were sufficiently dubious about these enormous relativistic effects to insist that the satellite's atomic clock broadcast its time “raw.” Its relativity-correction mechanism idled onboard. Down came the signal, running fast over the first twenty-four hours almost precisely by the predicted 38,000 billionths of a second. After twenty days of such gains, ground control commanded the frequency synthesizer to activate, correcting the broadcast time signal. Without that relativistic correction, it would have taken less than two minutes for the GPS system to exceed its allowable [daily] error.


(From Peter Galison, Einstein's Clocks, Poincaré's Maps pp. 288-289.)

I heartily recommend Galison's book, a history of the development of the physical concept of time throughout the twentieth century. Galison has doctorates in both physics and the history of science; using his dual expertise he makes the material accessible to dual laymen.

For a more technical account, the book's endnotes cite Neil Ashby, “General Relativity in the Global Positioning System