Graduate Students Unlock Code of 'Thiefproof' Car Key

New York Times
January 29, 2005

Graduate Cryptographers Unlock Code of 'Thiefproof' Car Key
By JOHN SCHWARTZ

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 they had the right key, they could answer future challenges
correctly.

Mr. Sabetti of Texas Instruments argues that grabbing the code from a
key would be very difficult, because the chips have a very short
broadcast range. The greatest distance that his company's engineers
have managed in the laboratory is 12 inches, and then only with large
antennas that require a power source.

Dr. Rubin acknowledged that his team had been able to read the keys
just a few inches from a reader, but said many situations could put an
attacker and a target in close proximity, including crowded elevators.

The researchers used several thousand dollars of off-the-shelf computer
equipment to crack the code, and had to fill a back seat of Mr. Green's
S.U.V. with computers and other equipment to successfully imitate a
key. But the cost of equipment could be brought down to several hundred
dollars, Dr. Rubin said, and Adam Stubblefield, one of the Hopkins
graduate students, said, "We think the entire attack could be done with
a device the size of an iPod."

The Texas Instruments chips are also used in millions of the Speedpass
tags that drivers use to buy gasoline at ExxonMobil stations without
pulling out a credit card, and the researchers have shown that they can
buy gas with a cracked code. A spokeswoman for ExxonMobil, Prem Nair,
said the company used additional antifraud measures, including
restrictions that only allow two gas purchases per day.

"We strongly believe that the Speedpass devices and the checks that we
have in place are much more secure than those using credit cards with
magnetic stripes," she said.

The team discussed its research with Texas Instruments before making
the paper public. Matthew Buckley, a spokesman for RSA Security, said
his company, which offers security consulting services and is
developing radio frequency ID tags that resist unauthorized
eavesdropping, had offered to work with Texas Instruments free of
charge to address the security issues.

Dr. Wagner said that what graduate students could do, organized crime
could also do. "The white hats don't have a monopoly on cryptographic
expertise," he said.

Dr. Rubin said that if criminals did eventually duplicate his students'
work, people could block eavesdroppers by keeping the key or Speedpass
token in a tinfoil sheath when not in use. But Mr. Sabetti, the Texas
Instruments executive, said such precautions were unnecessary. "It's a
solution to a problem that doesn't exist," he said.

Dan Bedore, a spokesman for Ford, said the company had confidence in
the technology. "No security device is foolproof," he said, but "it's a
very, very effective deterrent" to drive-away theft. "Flatbed trucks
are a bigger threat," he said, "and a lot lower tech."

On 29 Jan 2005 17:41:57 -0800, "MrPepper11" > wrote:

>New York Times
>January 29, 2005
>
>Graduate Cryptographers Unlock Code of 'Thiefproof' Car Key
>By JOHN SCHWARTZ

<snip>

I thought it was against the (US) law to try to crack codes like this,
or does that only apply to copy-protection on DVDs and the like?

--
Mr Nobody

MrPepper11 wrote:
>> Graduate Cryptographers Unlock Code of 'Thiefproof' Car Key
>> By JOHN SCHWARTZ

and Mr Nobody replied:
> I thought it was against the (US) law to try to crack codes like this,
> or does that only apply to copy-protection on DVDs and the like?

Maybe the difference is that there's no "intellectual" property being
protected by the car key. Only a car which can't be duplicated. The
government suffers no loss when a car is stolen. If 1,000 copies of a DVD
are made, the government loses tax revenue.

Bob H

Bob Harris wrote:

> MrPepper11 wrote:
>
>>>Graduate Cryptographers Unlock Code of 'Thiefproof' Car Key
>>>By JOHN SCHWARTZ
>
>
> and Mr Nobody replied:
>
>>I thought it was against the (US) law to try to crack codes like this,
>>or does that only apply to copy-protection on DVDs and the like?
>
>
> Maybe the difference is that there's no "intellectual" property being
> protected by the car key. Only a car which can't be duplicated. The
> government suffers no loss when a car is stolen. If 1,000 copies of a DVD
> are made, the government loses tax revenue.

These guys tried it out on vehicles they owned or had permission
to use.

Mr Nobody > writes:

>On 29 Jan 2005 17:41:57 -0800, "MrPepper11" > wrote:

>>New York Times
>>January 29, 2005
>>
>>Graduate Cryptographers Unlock Code of 'Thiefproof' Car Key
>>By JOHN SCHWARTZ

><snip>

>I thought it was against the (US) law to try to crack codes like this,
>or does that only apply to copy-protection on DVDs and the like?

The DMCA specifically exempts research.
(Read the act to get the caveates)

"MrPepper11" > wrote in message
oups.com...
....
> Mr. Sabetti of Texas Instruments argues that grabbing the code from a
> key would be very difficult, because the chips have a very short
> broadcast range. The greatest distance that his company's engineers
> have managed in the laboratory is 12 inches, and then only with large
> antennas that require a power source.

About ten years ago I wrote a patent application for a car lock which was
designed to
protect against dishonest valet-parking staff. Mr Sabetti appears not to
consider this
part of his threat model.

As I had not previously written a patent application, mine followed an
unconventional
structure (for a patent): I described a system, showed how to attack it,
then how to
improve it to guard against the attack; I repeated this until I arrived at a
design that I
was satisfied with.

My patent agent telephoned to tell me that one of my strawmen (i.e. a design
that
I had explicitly rejected) had turned up in his patent search, under the
name 'Tiris',
owned by Texas Instruments.

I'm curious as to how TI's current system differs from the Tiris system?

Are there any commercially-available car locks designed to defend against
somebody
with unsupervised access to the key?

Mark

Bill Unruh > wrote:
>
>The DMCA specifically exempts research.
>(Read the act to get the caveates)

Not really. It exempts the act of circumvention for "encryption
research", but still outlaws the buying/selling/making of the tools
to do so. It also has to be _encryption_ research, so if you break
a security system that does not overtly use encryption, the exemption
doesn't necessarily cover you.

IMHO the research exemption was carefully written to be unusable.
If it actually protects you, it will be because a judge decided to
interpret it very broadly, contradicting the intent of the authors.

What would protect these researchers is that the DMCA only applies
to technologies that protect a copyrighted work. In a couple
court cases, lawyers tried to argue that the security gadget itself
contained copyrighted code, which it "protected" --- but this didn't
fly with the judge.

--Xcott

of course it's against the law, but people will still do it!

y_p_w wrote:
> Bob Harris wrote:
>> MrPepper11 wrote:
>>>> Graduate Cryptographers Unlock Code of 'Thiefproof' Car Key
>>>> By JOHN SCHWARTZ
>>
>> and Mr Nobody replied:
>>> I thought it was against the (US) law to try to crack codes like this,
>>> or does that only apply to copy-protection on DVDs and the like?
>>
>> Maybe the difference is that there's no "intellectual" property being
>> protected by the car key. Only a car which can't be duplicated. The
>> government suffers no loss when a car is stolen. If 1,000 copies of a DVD
>> are made, the government loses tax revenue.
>
> These guys tried it out on vehicles they owned or had permission
> to use.

But the same thing, done to a DVD which I own, is (apparently) illegal. It
is (apparently) illegal to figure out how to break the security on a $25 DVD
but not on a $40,000 car.

Bob H

On Tue, 1 Feb 2005, Bob Harris wrote:

"Illegal! Illegal!"

Ever drive a mile per hour over the speed limit? That's illegal, too.