research!rsc

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.

Posted by rsc on Monday, February 25, 2008 | 0 comments |
Labels: history, physics, security

Disk-based computer viruses came of age with MS-DOS; network-based viruses came of age with Microsoft Windows. (The most stunning recent example is the widespread Storm worm which is at this very minute probably sending you pump-and-dump and greeting card spam.)

Most Linux and OS X users have a frustratingly smug attitude of “we're immune to viruses, because we use Unix.” This is obviously false: the original Internet worm ran on Unix. The simple security mechanisms in Unix-based systems do raise the virus-writing bar slightly, but a more likely explanation of the lack of viruses on Unix-based systems is their lack of current market share: Windows users are simply a much bigger and therefore more attractive target.

Especially for these smug Unix users, it should be sobering to read Tom Duff's 1987 technical report “Viral Attacks on UNIX® System Security,” which describes a simple, benign disk-based virus targeted at Unix executables. Even working under the constraints of the Unix permission bits, Duff managed to infect 466 files across 46 systems over a period of a few months, including an experimental “secure” version of Unix (to its credit, the kernel on that system did detect the virus). Duff's paper also describes a simple virus written in shell script. He cautions:

However sorely you are tempted, do not run this code. It got loose on my machine while being debugged for inclusion in this paper, and within an hour had infected about 140 files, at which time several copies were energetically seeking other files to infect, running the machine's load average, normally between .05 and 1.25, up to about 17. I had to stop the machine in the middle of a work day and spend three hours scouring the disks, earning the ire of ten or so co-workers. I feel extremely fortunate that it did not escape onto the Datakit network.

Doug McIlroy's 1989 paper “Virology 101” (gzipped PostScript) carries the shell script virus farther, developing progressively more virulent strains. McIlroy summarizes his paper:

There is nothing mysterious about computer viruses. A working, but easily observable, virus can be written in a few lines of code. Although particular virus attacks may be guarded against, no general defense within one domain of reference is possible; viruses are a natural consequence of stored-program computation. Like other hazards of technology, their thread may be mitigated by cautious behavior and community sanctions.

(Finally, of course, there is Thompson's “Reflections on Trusting Trust,” but that's a discussion for another day.)

Posted by rsc on Friday, February 01, 2008 | 4 comments |
Labels: Bell Labs, security

For two centuries, Benjamin Franklin had the final word on sharing secrets: “Three may keep a Secret, if two of them are dead.”

Shamir's 1979 paper “How to share a secret” is a significant advance over Franklin's algorithm. It shows how to split a secret into n pieces such that any k pieces can be used to reconstruct the secret but k–1 cannot.

Best of all, the idea is dead simple. Assume the secret s is a number smaller than some prime p. Then pick random integer coefficients to create a degree-k–1 polynomial f(x) computed mod p. Set the x⁰ coefficient to the secret message s, so that f(0) = s. Then hand out the pairs (1, f(1)), (2, f(2)), ..., (n, f(n)) as the secret shares. Since any polynomial of degree k–1 is uniquely determined by k points, any k shares can be used to reconstruct the original polynomial and then compute f(0). But each set of k–1 shares is consistent with p different possible polynomials, each with a different f(0) value, and thus leak no information at all.

Shamir's idea is not quite as simple as Franklin's, but I'm confident Franklin would have understood it.

Martin Tompa and Heather Woll explain how to detect participants that lie about their shares in “How to Share a Secret with Cheaters.”

Posted by rsc on Monday, January 21, 2008 | 0 comments |
Labels: math, security, theory