The Hunt for the Kill Switch

http://spectrum.ieee.org/may08/6171

Are chip makers building electronic trapdoors in key military hardware? The Pentagon is making its biggest effort yet to find out...

According to a U.S. defense contractor who spoke on condition of anonymity, a "European chip maker" recently built into its microprocessors a kill switch that could be accessed remotely. French defense contractors have used the chips in military equipment, the contractor told IEEE Spectrum. If in the future the equipment fell into hostile hands, "the French wanted a way to disable that circuit," he said. Spectrum could not confirm this account independently, but spirited discussion about it among researchers and another defense contractor last summer at a military research conference reveals a lot about the fever dreams plaguing the U.S. Department of Defense (DOD)...

The dwindling of domestic chip and electronics manufacturing in the United States, combined with the phenomenal growth of suppliers in countries like China, has only deepened the U.S. military's concern.

Recognizing this enormous vulnerability, the DOD recently launched its most ambitious program yet to verify the integrity of the electronics that will underpin future additions to its arsenal. In December, the Defense Advanced Research Projects Agency (DARPA), the Pentagon's R&D wing, released details about a three-year initiative it calls the Trust in Integrated Circuits program...In January, the Trust program started its prequalifying rounds by sending to three contractors four identical versions of a chip that contained unspecified malicious circuitry. The teams have until the end of this month to ferret out as many of the devious insertions as they can...

In 2004, the Defense Department created the Trusted Foundries Program to try to ensure an unbroken supply of secure microchips for the government...

Three years ago, the prestigious Defense Science Board, which advises the DOD on science and technology developments, warned in a report that the continuing shift to overseas chip fabrication would expose the Pentagon's most mission-critical integrated circuits to sabotage. The board was especially alarmed that no existing tests could detect such compromised chips, which led to the formation of the DARPA Trust in IC program...

So what's the best way to kill a chip? No one agrees on the most likely scenario, and in fact, there seem to be as many potential avenues of attack as there are people working on the problem. But the threats most often mentioned fall into two categories: a kill switch or a backdoor.

A kill switch is any manipulation of the chip's software or hardware that would cause the chip to die outright—to shut off an F-35's missile-launching electronics, for example. A backdoor, by contrast, lets outsiders gain access to the system through code or hardware to disable or enable a specific function. Because this method works without shutting down the whole chip, users remain unaware of the intrusion. An enemy could use it to bypass battlefield radio encryption, for instance...

Almost all FPGAs are now made at foundries outside the United States, about 80 percent of them in Taiwan. Defense contractors have no good way of guaranteeing that these economical chips haven't been tampered with. Building a kill switch into an FPGA could mean embedding as few as 1000 transistors within its many hundreds of millions. "You could do a lot of very interesting things with those extra transistors," Collins says.

The rogue additions would be nearly impossible to spot. Say those 1000 transistors are programmed to respond to a specific 512-bit sequence of numbers. To discover the code using software testing, you might have to cycle through every possible numerical combination of 512-bit sequences. That's 13.4 × 10153 combinations. (For perspective, the universe has existed for about 4 × 1017 seconds.) And that's just for the 512-bit number—the actual number of bits in the code would almost certainly be unknown. So you'd have to apply the same calculations to all possible 1024-bit numbers, and maybe even 2048-bit numbers, says Tim Holman, a research associate professor of electrical engineering at Vanderbilt University, in Nashville. "There just isn't enough time in the universe." ...

Clearly, the companies participating in the Trust in IC program have their work cut out for them. As Collins sees it, the result has to be a completely new chip-verification method. He's divided up the Trust participants into teams: one group to create the test chips from scratch; another to come up with malicious insertions; three more groups, which he calls "performers," to actually hunt for the errant circuits; and a final group to judge the results.

To fabricate the test chips, Collins chose the Information Sciences Institute at the University of Southern California, Los Angeles. He picked MIT's Lincoln Laboratory to engineer whatever sneaky insertions they could devise, and he tapped Johns Hopkins University Applied Physics Laboratory, in Laurel, Md., to come up with a way to compare and assess the performers' results.

The three performers are Raytheon, Luna Innovations, and Xradia. None of the teams would speak on the record, but their specialties offer some clues to their approach. Xradia, in Concord, Calif., builds nondestructive X­ray microscopes used widely in the semiconductor industry, so it may be looking at a new method of inspecting chips based on soft X­ray tomography...

Luna Innovations, in Roanoke, Va., specializes in creating antitamper features for FPGAs. Princeton's Lee suggests that Luna's approach may involve narrowing down the number of possible unspecified functions...

Raytheon, of Waltham, Mass., has expertise in hardware and logic testing, says Collins. He believes the company will use a more complex version of a technique called Boolean equivalence checking to analyze what types of inputs will generate certain outputs...