http://www.nytimes.com/2005/01/28/science/28cnd-key.html?ei=5094&en=48eb306a45a3b7a0&hp=&ex=1106974800&oref=login&partner=homepage&pagewanted=all&position=
Students Find Hole in Car Security Systems
By JOHN SCHWARTZ
Published: January 28, 2005
BALTIMORE - Matthew Green starts his 2005 Ford Escape with a duplicate key he
had made at Lowe's. Nothing unusual about that, except that the automobile
industry has spent millions of dollars to keep him from being able to do it.
Mr. Green, a graduate student at Johns Hopkins University, is part of a team
that plans to announce on Jan. 29 that it has cracked the security behind
"immobilizer" systems from Texas Instruments Inc. The systems reduce car
theft, because vehicles will not start unless the system recognizes a tiny
chip in the authorized key. They are used in millions of Fords, Toyotas and
Nissans.
All that would be required to steal a car, the researchers said, is a moment
next to the car owner to extract data from the key, less than an hour of
computing, and a few minutes to break in, feed the key code to the car and
hot-wire it.
An executive with the Texas Instruments division that makes the systems did
not dispute that the Hopkins team had cracked its code, but said there was
much more to stealing a car than that. The devices, said the executive, Tony
Sabetti, "have been fraud-free and are likely to remain fraud-free."
The implications of the Hopkins finding go beyond stealing cars.
Variations on the technology used in the chips, known as RFID for radio
frequency identification, are widely used. Similar systems deduct highway
tolls from drivers' accounts and restrict access to workplaces.
Wal-Mart is using the technology to track inventory, the Food and Drug
Administration is considering it to foil drug counterfeiting, and the medical
school at the University of California, Los Angeles, plans to implant chips
in cadavers to curtail unauthorized sale of body parts.
The Johns Hopkins researchers say that if other radio frequency ID systems
are vulnerable, the new field could offer far less security than its
proponents promise.
The computer scientists are not doing R.&D. for the Mafia. Aviel D. Rubin, a
professor of computer science who led the team, said his three graduate
students did what security experts often do: showed the lack of robust
security in important devices that people use every day.
"What we find time and time again is the security is overlooked and not done
right," said Dr. Rubin, who has exposed flaws in electronic voting systems
and wireless computer networks.
David Wagner, an assistant professor of computer science at the University of
California, Berkeley, who reviewed a draft of a paper by the Hopkins team,
called it "great research," adding, "I see it as an early warning" for all
radio frequency ID systems.
The "immobilizer" technology used in the keys has been an enormous success.
Texas Instruments alone has its chips in an estimated 150 million keys.
Replacing the key on newer cars can cost hundreds of dollars, but the
technology is credited with greatly reducing auto theft. - Early versions of
in-key chips were relatively easy to clone, but the Texas Instruments chips
are considered to be among the best. Still, the amount of computing the chip
can do is restricted by the fact that it has no power of its own; it builds a
slight charge from an electromagnetic field from the car's transmitter.
Cracking the system took the graduate students three months, Dr. Rubin said.
"There was a lot of trial and error work with, every once in a while, a
little 'Aha!' "
The Hopkins researchers got unexpected help from Texas Instruments itself.
They were able to buy a tag reader directly from the company, which sells
kits for $280 on its Web site. They also found a general diagram on the
Internet, from a technical presentation by the company's German division. The
researchers wrote in the paper describing their work that the diagram
provided "a useful foothold" into the system. (The Hopkins paper, which is
online at www.rfidanalysis.org, does not provide information that might allow
its work to be duplicated.
The researchers discovered a critically important fact: the encryption
algorithm used by the chip to scramble the challenge uses a relatively short
code, known as a key. The longer the code key, which is measured in bits, the
harder it is to crack any encryption system.
"If you were to tell a cryptographer that this system uses 40-bit keys, you'd
immediately conclude that the system is weak and that you'd be able to break
it," said Ari Juels, a scientist with the research arm of RSA Security, which
financed the team and collaborated with it.
The team wrote software that mimics the system, which works through a pattern
of challenge and response. The researchers took each chip they were trying to
clone and fed it challenges, and then tried to duplicate the response by
testing all 1,099,511,627,776 possible encryption keys. Once
