Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!

 


Forgot your password?
Close
typodupeerror
×
Encryption Security Science

Breaking a Car's Cipher 253

Posted by kdawson from the soon-all-cryptographers-will-drive-fancy-cars dept.
An anonymous reader alerts us to research out of Belgium and Israel that claims a practical attack on the KeeLoq auto anti-theft cipher. Here are slides from a talk (PDF) at CRYPTO 2007. From the researchers' site: "KeeLoq is a cipher used in several car anti-theft mechanisms distributed by Microchip Technology Inc. It may protect your car if you own a Chrysler, Daewoo, Fiat, General Motors, Honda, Toyota, Volvo, Volkswagen, or a Jaguar. The cipher is included in the remote control device that opens and locks your car and that controls the anti-theft mechanisms. The 64-bit key block cipher was widely believed to be secure. In a recent research, a method to identify the key in less than a day was found. The attack requires access for about 1 hour to the remote control (for example, while it is stored in your pocket). The attacker than runs the implemented software, finds the secret cryptographic key, and drives away in your car after copying the key." Update: 07/23 15:27 GMT by KD : One of the researchers, Sebastiaan Indesteege, pointed out that the link to the paper was incorrect; their paper has not yet been released to the public. I also managed to mis attribute his nationality. He is Belgian, not Dutch. My apologies.
This discussion has been archived. No new comments can be posted.

Breaking a Car's Cipher More

Breaking a Car's Cipher

Comments Filter:

  • Wrong paper (Score:3, Informative)

    by mkilmo ( 1146159 ) on Thursday August 23, 2007 @10:14AM (#20329919)
    The linked paper is by Bugadanov (requires the entire code book). The authors of this paper have not published their paper in the wild (yet).

  • So? (Score:4, Insightful)

    by Rob_Ogilvie ( 872621 ) <rob@axpr.net> on Thursday August 23, 2007 @10:14AM (#20329923) Homepage
    If a car thief has access to your keys for an hour, aren't you going to lose your car anyway?
    • Thanks. We can now safely end this discussion. This being Slashdot though, all the cryptography "experts" will tell us how things should have been implemented.

      • Re:So? (Score:4, Funny)

        by tomstdenis ( 446163 ) <tomstdenis@gma[ ]com ['il.' in gap]> on Thursday August 23, 2007 @10:22AM (#20330029) Homepage
        Step 1. Stop being lazy. Just turn the damn key in the door.

        Step 2. Yeah, if they used 3DES or Blowfish at the time, this wouldn't be an issue.

        Step 3. See Step 1.

        • Re: (Score:2)

          by hjf ( 703092 )
          But never use AES, it's a government booby trap!

        • Re: (Score:2)

          by nsayer ( 86181 ) *

          Stop being lazy. Just turn the damn key in the door.

          If anything, that's probably less secure [wikipedia.org].

          • I like my security system the best... I drive a PoS. Nothing deters theft more than apathy!

            • Re: (Score:3, Funny)

              by jridley ( 9305 )
              Yup, my brother's truck has no working door locks, and the ignition is an on/off switch and the starter is a pushbutton.
              Nobody'd steal it though. Heck, even I check under/behind the seat before I get in; I'm always worried that some kind or animal will have started living in there and I might get bit.

            • Re: (Score:3, Interesting)

              by Torvaun ( 1040898 )
              A friend of mine had his minivan stolen. It was returned, three days and 8 miles later. We have never stopped giving him shit for that.

      • Re:So? (Score:5, Funny)

        by Otter ( 3800 ) on Thursday August 23, 2007 @10:33AM (#20330193) Journal
        This being Slashdot though, all the cryptography "experts" will tell us how things should have been implemented.

        Sorry, we can only communicate through analogies to either automobiles or door locks. Discussion of actual automotive door locks is therefore impossible, and referring to Belgium as "the Netherlands" will have to be the site's sole contribution.

      • Re:So? (Score:5, Funny)

        by wiredlogic ( 135348 ) on Thursday August 23, 2007 @11:59AM (#20331367)
        This being Slashdot though, all the cryptography "experts" will tell us how things should have been implemented.

        A Beowulf cluster of keys (bound by a token ring) would make it difficult to interrogate any specific key.

    • Re: (Score:2, Insightful)

      by mvanvoorden ( 861050 )
      It's not necessary to physically access the keys, and the owner of the keys doesn't have to press any buttons either, just having the keys in range will suffice. Probably the keys use something like RFID or so.

      • Re: (Score:2)

        by Locutus ( 9039 )
        what blows me away is that nobody has mentioned, nor the manufacturers implemented, a simple RF shield around the keyfob. Simply shielding the keyfob, which should have an actual key in it too, prevents someone from just sitting next to you or atleast in front of your home, and hacking away at your keyfobs security. Did the auto manufacturers think we are so lazy we can't even temporarily pop the xmitter outside the shield long enough for the car to "see" us at a distance and unlock? And the other thing the

    • Re:So? (Score:5, Funny)

      by iggymanz ( 596061 ) on Thursday August 23, 2007 @10:18AM (#20329987)
      a long time ago I had a girlfriend who liked to put her hand in my pocket and had access to my master key for hours. one day she took something from me using the key, but it wasn't my car

    • Re: (Score:3, Insightful)

      by varmittang ( 849469 )
      From the description, they do not need physical access to your keys, that why they said in your pocket. That means the person next to you, or a few feet/meters away could be stealing the car keys.

      • Re:So? (Score:5, Funny)

        by dkf ( 304284 ) <donal.k.fellows@manchester.ac.uk> on Thursday August 23, 2007 @10:30AM (#20330137) Homepage

        That means the person next to you, or a few feet/meters away could be stealing the car keys.
        So now we need tinfoil pocket protectors as well as tinfoil hats?

      • Re: (Score:3, Informative)

        by morgan_greywolf ( 835522 )
        On most newer cars, there's also an anti-theft chip in the key itself. The information stored on this chip is directly linked to the VIN number of the car. So the person would ALSO have to copy your key, as it says in TFS. These keys are around $80, and you used to have to get them from the dealer, but apparently nowadays you can get them from Wal*Mart.

        • Re: (Score:2, Funny)

          by Pojut ( 1027544 )
          I hate to be a bastard, but someone has to say it.

          The information stored on this chip is directly linked to the VIN number of the car
          Vehicle Identification Number Number?

          • Re:So? (Score:4, Funny)

            by Anonymous Coward on Thursday August 23, 2007 @11:14AM (#20330765)
            You bastard.
          • There are some acronyms that have become so well-used that they are, for all intents and purposes, words themselves. Thus, there is no 'duplication' of wording when saying (for instance):

            ATM Machine
            SCUBA Gear (The 'A' stands for "Apparatus")
            PIN number
            VIN number
            etc.
            • The head of the network for my entire school district back when I was in HS called NICs "Network Interface NIC Cards"

              And, for some odd reason, the schools called me and my friend before him when they had computer problems.

            • Re: (Score:2)

              by Pojut ( 1027544 )

              Is that what you tell yourself so you can sleep at night?

              /ducks

      • Re: (Score:2)

        by BuR4N ( 512430 )
        "From the description, they do not need physical access to your keys, that why they said in your pocket."

        It sounds strange that its possible to read something from the key while not pressing any of the button on it. If it constantly sends out stuff, shouldnt the batteries go away directly then ? Or did I miss something ?

        • Re:So? (Score:4, Informative)

          by Znork ( 31774 ) on Thursday August 23, 2007 @11:25AM (#20330943)
          "Or did I miss something ?"

          Yep. Passive RFID chips require so little energy that the reader can power them with the current the antenna produces when hit by the EM waves from the reader. Usually this means that you have to hold the chip (card, key, etc) very close to the reciever (against it, the key in the lock, etc).

          However, that proximity is only necessary if you use the standard reader. There's nothing stopping someone from getting a standard reader and jacking up the power enough to activate and read the chips from a much greater distance.

          Unless you get a tin-foil wallet. And tin-foil pockets. Etc.
          • Everyone has always laughed at me for the last 15 years for augmenting my clothes with tin foil. Especially those guys in the next lab with the large microwave emitter. But who's laughing NOW?

    • Re:So? CNC... (Score:5, Interesting)

      by foodnugget ( 663749 ) <eric-slashdot@NOSpAm.ericfeldman.com> on Thursday August 23, 2007 @10:31AM (#20330149)
      While it may be simple to break the code on the chip, you still need a copy of the key unless the car is push-button-ignition.
      These days, many high-end car keys are CNC cut (my mini's key has huuuuuge tooling marks from a spindle-out-of-square), which will actually cause a bit of trouble. This isn't something you could easily do a putty-transfer on, nor does the group of people who spend a lot of time breaking cyphers typically overlap with the group of people who have and can work with CNC equipment.
      In the end, I think flatbedding the car is the way to go. All the big chop shops are doing this now. If you're small-time, carjack. Alternately, get a real job.

      • Re: (Score:3, Interesting)

        by Magada ( 741361 )
        A physical key is still a key, y'know? There is considerable overlap in concepts and techniques - why, putty transfer is simply a replay attack, while a rake is actually used to brute-force a lock by generating many pin position combinations in a very short time.
        • Have you seen the laser cut keys? You can't rake those locks.
      • Nice to see a fellow Mini driver on /.

        Anyway, correct me if I'm wrong, but doesn't the Mini key communicate with the car's computer system when it's inserted?

        I know when I take my car in for its 10k checkups, they just drop the key in this little scanner and pull the mileage off. Could be RF, too, for all I know. I guess one check would be to take my spare key around the car, but not use it to start/unlock the doors and then take it to the dealer and trick em.
        • Your (and my!) Mini key is made by Valeo - here are the FCC OET [fcc.gov] pages on it.

          It consists of an RF transmitter to open the doors, etc, and a passive RFID chip that had to be read by the steering column before the car will start. If you look at the other products on the FCC site by Valeo, you'll see various steering column readers and door lock receivers. The transmitter is actually fairly complex - it uses rolling codes to help prevent theft by replaying/predicting codes.

    • No the intro clearly states that the thief has to have access to the remote control while is it in your pocket.

      So next time you let a car thief put his hands into your pocket, make sure it's only for 50 minutes.

      It is just me, or a lot of exploits like this. A Thief can gain access to ANYTHING in your house once they are INSIDE! OMFG!
    • "(for example, while it is stored in your pocket)"

      Missed that bit of the summary did you? Sounds like they can do it all remotely.. may someone who has RTFA could shine some light on this area

    • Re:So? (Score:5, Funny)

      by Phisbut ( 761268 ) on Thursday August 23, 2007 @12:21PM (#20331709)

      If a car thief has access to your keys for an hour, aren't you going to lose your car anyway?

      Basically, these electronic-chips-encrypted-stuff-on-the-car-key aren't meant to make it any harder for a car thief to get your car. It's just there to manage to increase the penalty for car theft.

      Car theft isn't that much of a crime nowadays. However, breaking the cipher will net you a DMCA violation and such things will carry the death penalty pretty soon.

    • There are many instances of car keys being duplicated by thieves in league with garages, valet parkings and so forth.
      The important thing here is that the person you *think* was guarding your key *could not* have stolen your car.
      In fact, you have no way of knowing how yuo car was stolen.

      In an interesting varient, thieves also hire cars, dup the keys, then just drive 'em away after rental return...

      So yes, it's important that they can crack the crypto, so can duplicate...

  • Obligatory (Score:5, Funny)

    by Billosaur ( 927319 ) * <wgrotherNO@SPAMoptonline.net> on Thursday August 23, 2007 @10:15AM (#20329931) Journal

    KITT: Michael, someone's trying to hack into my operating system! Help me Michael!

    • Re: (Score:2)

      by Shotgun ( 30919 )
      KITT: Michael, someone's trying to hack into my operating system! Help me Michael!

      Allow or deny?
  • There's still a mechanical lock preventing the ignition from being engaged, and they would also have a steering wheel lock to work around. This is effectively bypassing the imobilizer that comes equipt on most modern cars. If someone wants your car bad enough now-a-days, they just take your keys from you.

    • Re: (Score:2, Interesting)

      by account_deleted ( 4530225 )
      Comment removed based on user account deletion
      • "Some of these cars could quite possibly contain that whole "key in range push button to start" option. My cousin has that option on her car, though I forgot the make/model..."

        I believe the Prius does that....I seem to remember a friend of mine showing me this 'feature'.

    • Not really (Score:5, Insightful)

      by dachshund ( 300733 ) on Thursday August 23, 2007 @10:40AM (#20330309)
      There's still a mechanical lock preventing the ignition from being engaged, and they would also have a steering wheel lock to work around. This is effectively bypassing the imobilizer that comes equipt on most modern cars. If someone wants your car bad enough now-a-days, they just take your keys from you.


      I just purchased a new car that doesn't have a mechanical ignition system. There's an place to attach the key (doesn't have metal teeth or anything), and a big "Start/Stop" button. The steering wheel lock is also electronic, and is controlled by the electronic signal from the key. I have no idea if my car uses KeyLoq--- I sure hope not.

      Mechanical locks are on their way out, largely because they're ineffective against even moderately sophisticated criminals. That's the whole reason Immobilizer systems were rolled out in the first place. This attack effectively stips the immobilizer out of the car and rolls the security back to pre-Immobilizer levels. You only need to look at theft rates among models with and without immobilizers to see what impact that has.

      Finally, for those who say that 1-hr access to the key is unreasonable: remember that the attack here is _key copying_, not theft. The immobilizer systems are designed to prevent copying, so that your valet or repair person can't make a copy of your key and steal it later. This attack takes a lot longer than other attacks which are out there (example [wikipedia.org]), but it's still not out of the question.

      The basic lesson of all these attacks is that manufacturers need to use strong cryptography rather than custom, homebrewed ciphers. Hopefully with fabrication prices dropping, this will be the last generation of truly ridiculous authentication systems.

      • There's an place to attach the key (doesn't have metal teeth or anything), and a big "Start/Stop" button.

        I like my Prius also. I have an older one that still uses a chip in the key. When you hack my remote, you also have to hack my key. The Prius does not have a 12 volt starter at all. The throttle is fly by wire. The EV transmission is a computer controlled motor/generator set. Unless you can convince the computer to operate, there is absolutely no way to drive it off with nothing but the data from t
      • My old car just had a plain old key. No chip, nothing. When I bought it, all I got was one valet key and one original. I went into a locksmith store and asked for a copy of the original.

        I assumed he'd just take the original and copy it, like most box stores. Not this guy. He said no thanks, went out to my car, and without my keys he made a working key in about 5 minutes.

        I wouldn't have believe it possible unless I saw it with my own eyes. He filed a blank key until it worked, feeling the lock. I thin
    • Some cars have a system where there is no mechanical key. MB & MBW have it, I hear Toyota has some too, presumably Lexus too. Basically, you have a card or fob in your pocket and you press a button to start the car.

  • oh brudder (Score:2, Funny)

    by e-scetic ( 1003976 ) *

    Another reason to carry around an RFID jammer.

    Quick, someone create Faraday pants, or should I line my pockets with tinfoil?

  • After following me around the mall for an hour with this little device, they would run the software, get into my Honda Civic, and then...

    Hotwire it.

    How easy is that? I think they'd just carjack someone before going through the trouble.

  • learn to read, you insensitive clod (Score:5, Informative)

    by Anonymous Coward on Thursday August 23, 2007 @10:28AM (#20330109)
    OK, what part of "Katholieke Universiteit Leuven, Belgium" looks like "researchers in The Netherlands"??

    In other news: The Canadian president George W. Bush invaded Iran because of the 9/11 attack on the World Trade Center of Chicago.

    • In other news: The Canadian president George W. Bush invaded Iran because of the 9/11 attack on the World Trade Center of Chicago.

      Why did you post anonymously? This is a variation on a classic Slashdot +5 funny!

      I'm American; There is no way I'd mod this down.

      YMMV though, I've seen some weird mod's over the years. Like the American political system, I think there are problems with the Slashdot mod system, but it's better than anything else I've seen. And I really believe that the only way to fix it is to get people to understand that the reason for modding at all is to establish how interesting, relevant, or readable a comment is, ra

    • Re: (Score:2)

      by pla ( 258480 )
      OK, what part of "Katholieke Universiteit Leuven, Belgium" looks like "researchers in The Netherlands"??

      The part that starts with wierd non-English words, and ends with somewhere (probably somewhere smallish) in Northwestern Europe.

      Like it or not, most Americans parse it exactly that way. "Belgium? Nah, I prefer the regular kind of waffles, thanks."



      / self-debasing, here, not trolling
      // also not really kidding, unfortunately

  • Summary (Score:3, Interesting)

    by Anonymous Coward on Thursday August 23, 2007 @10:29AM (#20330125)
    According to their slides, all you need is proximity to one of these devices for an hour, and the master key for the manufacturer can be found - which is simply XORd to the vehicle ID to authenticate. They were relying on a vast keyspace instead of a secure encryption method - security through obscurity.

    Break one key device, break them all.

  • Daewoo? more like Daew00t. (Score:3, Funny)

    by that IT girl ( 864406 ) on Thursday August 23, 2007 @10:37AM (#20330259) Journal

    It may protect your car if you own a Chrysler, Daewoo,...

    That's okay. If you own a Daewoo, you could hand the key to a thief and they still wouldn't steal it. Nothing to see here, move along.

  • Symmetric Key Exchange (Score:4, Interesting)

    by Doc Ruby ( 173196 ) on Thursday August 23, 2007 @10:43AM (#20330361) Homepage Journal
    Why don't remote keys resync symmetric, unbreakable keys with the car every time they're physically inserted into the ignition?

    When someone patents that device, just point to this post as prior art. If it's patent free, anyone can use it, and there's no excuse for not securing cars (and homes, and bikes, and ...) properly.

    You're welcome.

    • Re: (Score:3, Insightful)

      by DangerTenor ( 104151 )
      Because when my wife used her key to start the car, it wouldn't work...

      • Re: (Score:3, Interesting)

        by Doc Ruby ( 173196 )
        Why doesn't your car have a different symmetric password for each physical key? Make it easier to secure the car after losing a key. And to restore her personal settings for seat position, mirrors, stereo, etc.

  • Broken Cipher, you say (Score:3, Funny)

    by Hoplite3 ( 671379 ) on Thursday August 23, 2007 @11:35AM (#20331039)
    Well, that's very interesting, but I have to go.

    I'm headed to the annual "Vegan food and wifi jamboree" at the co-op where I expect to "win" a new Prius.

      Of course I have to bring my laptop. Don't worry, just because I'm sitting at the table next to you doesn't mean I'm using my machine to crack the crypto on your key while we enjoy our roasted yams. I'm just writing my tract about municipal wifi and organic gardening.

    Oh, yeah? You own a Prius? In red? I always liked red. Man, you have the only red one here...
  • No such thing as a truly unbreakable anti-theft system.

    1. What happens if someone genuinely loses their keys? There needs to be some way for the manufacturer to sort them out.
    2. Car theft won't stop overnight. But it will cause more things like carjackings (rather more violent and distressing) and key theft.
    3. In any major city, there are enough tow trucks that nobody will bat an eyelid if they see a car being lifted onto the back of one. It's brazen, but by the time it dawns on the driver that their
  • As an American, I'll gladly admit that I don't know the difference between Dutchland and Belgia.
  • OK, so in one hour with close proximity (measured in feet) to the controller, they can crack it. Give a guy (valet parking anyone?) your keys and he can copy it in 5 seconds. This is not news at all. You want to impress/scare me? Tell me they can do it without the remote.
  • ... window is a much easier way in.

  • It's not that hard... (Score:3, Insightful)

    by sjames ( 1099 ) on Thursday August 23, 2007 @01:07PM (#20332311) Homepage Journal

    If the manufacturers ACTUALLY gave a crap about security they could easily enough make the system secure. Instead they're more interested in patentable special sauce and NIH.

    The thing is, cryptography is at the same time very easy or very hard. It's very easy to utilize one of several freely available strong systems in order to be secure. It's very easy to invent a system from scratch that YOU don't know how to crack. It's very hard to invent your own system that nobody else will know how to crack. It's very easy to introduce a serious flaw when re-implementing someone elses crypto. If you haven't devoted your professional career to cryptography, the best bet is to utilize someone elses.

    For example, Blowfish is completely free of encumberance and has several fully public domain implementations available in C. RSA is (now) equally free. It is well understood, has years of successful use behind it and years of analysis demonstrating that it would cost WAY more to crack the key than any car is worth (not to mention that it would take longer than the typical lifetime of a car). There are plenty of years old CPUs out there that have more than enough "oomph" to handle RSA and are well suited to embedded use. They might cost a dollar more, but this sort of system is not used in "bargain basement" cars.

    They spend the extra cash on fine leather seats and steering wheel covers but use Yugo quality locks to protect it?

  • Ok, interesting post, but why wasn't the master key posted? I want to make a legit copy of the key of my neighb^h^h^h^h^h^hjaquar. Without it, no 65 minute crack...

Slashdot Top Deals

I have hardly ever known a mathematician who was capable of reasoning. -- Plato

Close