http://www.theregister.co.uk/2008/04/03/keeloq_master_key_found/ 

By Dan Goodin in San Francisco
The Register
3rd April 2008

A team of German scientists say they have cracked the encryption of a 
device widely used in keyless entry systems that electronically secure 
cars, garages and office buildings.

The finding by the scientists from Ruhr University in Bochum, Germany, 
means it is now relatively straightforward to clone the remote control 
devices that act as the electronic keys that unlock these restricted 
areas.

In a paper published earlier this week, they demonstrated a method they 
say completely breaks the encryption used in the Keeloq security system, 
which is used by manufacturers of cars, garage door openers and other 
devices. The hardware-based block cipher is made by US-based Microchip 
Technology and is used by Honda, Toyota, Volvo, Volkswagen and other 
manufacturers to securely transmit access codes that are transmitted 
using radio frequency identification technology.

The scientists from Ruhr's Electrical Engineering and Information 
Sciences Department were able to defeat the Keeloq's security because it 
relies on poor key management, in which every key is derived from a 
master key that's stored in the reading device, according to Timo 
Kasper, a PhD candidate who worked on the paper. Moreover, it uses a 
proprietary algorithm that had already been shown to generate 
cryptographically weak output.

The algorithm was kept secret for most of the two decades it's been in 
use. That changed about 18 months ago, when an an entry on Wikipedia 
published the cipher. The research team almost immediately spotted 
weaknesses.

"If they had made it public they would have found out 20 years ago that 
it's insecure," Kasper said in an interview. "Now it's a little bit too 
late, because it's already built into all the garages and cars."

Microchip officials wouldn't be interviewed for this story. They issued 
a statement that stated: "The most recently published German paper on 
theoretical attack requires detailed knowledge of the system 
implementation and a combination of data, specialized skills, equipment 
and access to various components of a system, which is seldom feasible. 
These theoretical attacks are not unique to the Keeloq system and could 
be applied to virtually any security system."

The paper describes a two-step approach to the crack. The first is 
what's known as a side-channel attack to deduce the master key that 
manufacturers build into each car lock, garage door opener or other 
access device that is equipped with Keeloq. One side-channel technique 
uses an oscilloscope to map how much power is used at precise time 
intervals while the Keeloq-based access device derives a new key. A 
similar method analyzes electromagnetic radiation.

Because most access devices are publicly available, it's not too hard 
for attackers to get their hands on one to perform the analysis. The 
hack requires about $3,000 worth of equipment and a fair amount of 
technical skill, but once the unique master key for a particular model 
is available, it works universally, Kasper said.

Armed with the master key, the researchers move to the second step, 
which involves eavesdropping on the targeted access device as it 
communicates via RFID with a remote control key. This can be done from a 
distance of 100 meters or more and requires the capture of just two 
messages.

By plugging the intercepted message data into a laptop and analyzing it, 
the researchers are able to obtain the unique key that the remote device 
uses to communicate with the access reader. The key can then be loaded 
onto a blank remote. Because of the speed and distance allowed in an 
attack, targets would likely have no idea their garage door opener or 
RFID-based car key had just been cloned.

"There are no fingerprints or other traces left," Kasper said. "That's 
the funny thing about the attack."

The demonstration is separate from a Keeloq hack that went public last 
summer. That method took closer to a day to crack the device key and 
required close proximity to the remote for about an hour. Microchip 
later labeled the attack "theoretical," and said the technique wouldn't 
be effective in real-world scenarios.

The new research follows by a few months the cracking of encryption in 
the widely used Mifare Classic smartcard, which is used around the world 
to control access subways, military installations and other restricted 
areas. In both cases, the companies relied on proprietary algorithms 
that ultimately were found to produce cryptographically weak output.

Kasper said the Keeloq is used in more than 90 per cent of the world's 
garage door openers and in many devices for controling access to 
buildings. The device uses a 64-bit encryption key, a length that makes 
a brute force attack impractical, if not impossible, in real-world 
situations. It also employs what's known alternately as hopping code and 
rolling code, which requires a new authentication code each session. 
That prevents attackers from gaining unauthorized access by capturing 
old output and retransmitting it to the reader.

"The lesson is that manufacturers definitely have to apply appropriate 
encryption in their devices and protect the encryption against 
side-channel attacks," Kasper said. "This is not only a topic that 
applies to garage door openers and car alarms; it applies to all kinds 
of RFID applications, all kinds of access systems. It has to be 
appropriately secured."


___________________________________________________      
Subscribe to InfoSec News
http://www.infosecnews.org/mailman/listinfo/isn