Locks aren't unique, are they?

[elfkin477]

There are millions of doors on homes and cars and other things that have locks, but how many lock patterns are there? They can't all be as unique as snowflakes, right? Do they sort this out by creating a lot of different lock patterns, and making sure they don't distribute cars/other lock sets in a manner that would make it likely that other people's keys would open the locks? Or do they really only make one lock of a certain pattern and no more?

[dobro4]

Pontiac Grand Prix's (at least since the electronic remotes) only have 4 different keyless remotes.

[Darryl Lict]

I don't know how many mechanical locks car manufacturer uses, but a friend of mine was in a rental car (Ford Explorer), unlocked it, got into it and was a half a mile up the road before he realized he was in the wrong car (same color both exterior and interior).

[SCSimmons]

Pontiac Grand Prix's (at least since the electronic remotes) only have 4 different keyless remotes.

Cite? That seems absurdly low to me ... These are only anti-theft-effective if there's a pretty low probability of a random 'key' working on a random car.

[appleciders]

There are millions of doors on homes and cars and other things that have locks, but how many lock patterns are there? They can't all be as unique as snowflakes, right? Do they sort this out by creating a lot of different lock patterns, and making sure they don't distribute cars/other lock sets in a manner that would make it likely that other people's keys would open the locks? Or do they really only make one lock of a certain pattern and no more?

Well, there are a number of things you can vary. The most obvious would be the number of tumblers in the lock, with each tumbler having maybe five or six different possible heights. You could then vary the distances between the tumblers, if you felt fancy. You can also add a whole extra row of tumblers, too, although I imagine such locks are expensive.

The house key on my key ring has five tumblers. If we assume that each tumbler is sensitive enough to allow a maximum of five possible tumbler positions, then we get a maximum of 3125 possible key combinations. If we assume 7 possible tumbler positions, then we get a maximum of 78,125 possible keys.

This is a purely mathematical analysis- someone who knows more about keys and locks could explain the hardware side of it a little better, I'm sure.

[Markxxx]

One thing also to consider is not all locks are as sensitive as they should be.

I've made keys that were off and still worked. By rights they were off enough by siting that they shouldn't have worked, but with a little jiggle the locked opened.

So it's possible after a lot of use or whatever reason the lock or key becomes worn down and will allow itself to be opened when it shouldn't

[RealityChuck]

Yale locks used to bill themselves as being the first company to mass manufacture items in non-identical forms. I've never known a Yale key that opened anything other than the lock it was intended to open.

Tumbler locks have millions of possible combinations. While in theory two could be alike, it'd be hard to find them.

This doesn't count things like passkeys* or locks deliberately keyed alike. But locks for houses have been nonidentical for over a century.

It may be different for cars. I know that some construction vehicles are all keyed alike; there used to be a problem about people stealing Ford steam shovels because they all had one key (convenient if you owned several, but also for thieves). I've also heard stories of people driving off with the wrong car. It's possible the auto manufacturers are cutting corners by sticking with just a handful of lock combinations.

*In Russia, they passkey down the streetsky.

[Q.E.D.]

But locks for houses have been nonidentical for over a century.

Not even close. The typical "Arrow" type house key has, as noted above, five tumbler positions with each capable of 6 different pin lengths for a total of 15,575 combinations. Long odds for finding a duplicate, but far short of being identical.

[Magiver]

There have always been overlapping keys for cars but with the advent of the the computer chipped key it is now possible to reduce that to zero as it relates to operating the vehicle. A chip could have billions of combinations available to it. I'm surprised that nobody has come out with a USB memory stick as an electronic key so that people could program their own cars. You could feed in your high school poem on cheese-wiz as a security code and still have enough room left over for 24 days of continuous music.

[Zany Zeolite Zipper]

How do you manufacture something where every unit is different? If you picked two locks in series off of the same machine would they be different? Or do they build one lock for six months, then go to another pattern. Are industrial machinery precise enough to change between each and every lock (or 100 locks*)?

*Any factory worthy of the name will be producing hundreds of thousands of locks a day, I would think.

[Chronos]

This is a purely mathematical analysis- someone who knows more about keys and locks could explain the hardware side of it a little better, I'm sure.One complication I know of is that you can't vary the depths of the cuts too abruptly, or you'll get a weak piece of metal that breaks too easily. So you might, for instance, be able to have cut depths ranging from 1 to 6, but any two adjacent loci can only have a difference of 3.

Another complication is that not all locks use all of the tumblers that the key would allow for. For instance, you might have several rooms in a building such that each room needs its own key, but any of the room keys will open the door to the building. In some cases, you can even have a master key that'll open the building and all of the rooms.

[Whack-a-Mole]

FWIW, and no cite, I have heard car manufacturers make ~1000 key sets. As noted already (and I have heard similar stories) it is possible to use your keys on a car that is not yours. Just have to try a bunch.

ETA: IIRC Mercedes had some "laser cut keys" that in some fashion were an extra security measure. I think they dropped them when people lost their keys and were told a replacement set would cost a few hundred dollars.

[Q.E.D.]

Are industrial machinery precise enough to change between each and every lock (or 100 locks*)?

You've never watched How It's Made, have you? Yes, the machinery is easily able to make consecutive unique locks. The series actually did tu7mbler locks, and basically the machinery randomly selects a set of tumbler pins, and then cuts a key suing the pinset as a template. The key is then sent along the production line with the lock so that they are packaged together.

[Chronos]

Oh, I forgot to mention another situation that might be of interest to the OP: In high school, we were all issued combination padlocks for our lockers. But friends often told each other their combinations, and it quickly became apparent that many locks, though they had different numbers, had the same pattern. For instance, one student's might be 17-21-30, and another student would have 23-27-36 (the first student's combination +6). So you could make batches of 40 identical locks at a time and just put the dial on differently, and you'd end up with 40 different combinations, but they wouldn't really be secure, since you could get someone's combo by finding out what the last digit is (by looking at the lock after they'd opened it), and then guessing which of about 10 different patterns they had.

[hekk]

Anecdotal cite for car locks:

When I embarrassingly locked my keys in the trunk while talking my girlfriend out to eat, the locksmith that came had a key ring with about 100 different Ford trunk/door keys and tried a couple dozen until one worked. Car was an 80 something Mercury Grand Marquis, without that nifty number entry thing that would have saved me $50.

Considering that Ford used those same keys for decades (early 70's to mid 90's IME), I'd say that there are thousands of like keyed cars out there in the real world.

[MikeS]

\The house key on my key ring has five tumblers. If we assume 7 possible tumbler positions, then we get a maximum of 78,125 possible keys.
Maybe it's just late at night and I'm overtired, but shouldn't this be 75 = 16 807 keys, rather than 57 = 78 125?

[Sunspace]

You could feed in your high school poem on cheese-wiz as a security code and still have enough room left over for 24 days of continuous music.I love modern technology. :)

[amarinth]

I don't know how many mechanical locks car manufacturer uses, but a friend of mine was in a rental car (Ford Explorer), unlocked it, got into it and was a half a mile up the road before he realized he was in the wrong car (same color both exterior and interior).I've done the same. Well, not a Ford Explorer, but my make and model of car. And the two times it happened, I looked over and noticed that the crapload of stuff that is usually in my car wasn't in the one I just opened. And then locked the door and found my actual car.

[Snnipe 70E]

House or office keys.

Schlage and Baldwin locks with a "C" keyway.
5 pin lock each pin will have 10 sifferent lenghts from 0 to 9. That will get you a combination of 100,000. If the differance is 8 or 9 the key can not be cut. If the differance is 8 or greater when the key is cut the differance will be 7. As an example a key with the binning of 46901 when it is cut will end up being 46921.

Now if you go to a 6 pin lock, mostly on commercial locks, the starting number will be 1,000,000.

Now throw in other keyway and I believe Schlage has 9 keyway.

Now if you want to pay a littler more get a Schlage Primus lock. It has a registgered side bar on the key and lock. Schlage keeps track of where each key was used and will not sell a like key in the same area.

[1010011010]

Keyless Entry can be brute forced in 3129 key presses (http://www.hackosis.com/2008/01/12/security-brute-force-a-car-keyless-entry-pad/). Don't get too excited about "electronic keys" just yet.

Often the difference in the price of a lock isn't in materials or construction, it's how many duplicates were present in the total run of locks/tumblers. A high-end top-of-the-line run would only make as many locks as there are unique combinations for the design. A low-end run might make ten or hundreds of each combination.

[mhendo]

Keyless Entry can be brute forced in 3129 key presses (http://www.hackosis.com/2008/01/12/security-brute-force-a-car-keyless-entry-pad/). Don't get too excited about "electronic keys" just yet.But the way the lock described in that story works has some crucial differences from how a better-designed electronic key might work.

1. In the story you linked, the ten numbers are really only 5 buttons, meaning that from the very beginning you don't have too many combinations to work with. Make the electronic key alpha-numeric, and you increase the number of possible combinations incredibly.

2. The keypad on that car requires exactly 5 numbers in the code. A better system would not only allow more digits, but would allow you to set the number yourself, like a password, again increasing the number of possible combinations.

3. The keypad on that car will open the door as soon as you press the five correct numbers in order, even if you have pressed 500 numbers beforehand. An improved system would require you to start over each time you try a new combination, eliminating the type of brute force hack used in that article. You would still be able to use brute force, but it would require many more keypresses.

Of course, one downside of allowing more complex electronic codes is that, like with computer passwords, people will probably end up choosing completely obvious codes, like "password" or "myinitials123" or something.

[clayton_e]

When I was in sixth grade I found a key in the school parking lot that was light blue and shiny.. It had in very small raised letters (not stamped into it like someone might do for some sort of prank) "Master Key, all 1991 Ford F-150" or some such model.. It might've been more specific, my memory is a little hazy on the details.

To this day I just don't remember what happened to it. I was in 6th grade and should've handed it in to the police.. I had no intention of using it for any reason.. But I thought it was cool.

I'm pretty sure I put it on a keyring with other keys and lost it.

[pulykamell]

Not even close. The typical "Arrow" type house key has, as noted above, five tumbler positions with each capable of 6 different pin lengths for a total of 15,575 combinations. Long odds for finding a duplicate, but far short of being identical.

It has actually happened to me once with a standard 5-pin tumbler. We had a music practice space and, one caffeine-deprived morning, I slipped my key in, unlocked and opened the door, took the key out, and realized that I had opened the door with my apartment key. I looked closely at the keys and, sure enough, they were identical cuts. The apartment key worked in the practice space and vice versa. Hell of a coincidence, but it happens.

[sailor]

Keyless Entry can be brute forced in 3129 key presses (http://www.hackosis.com/2008/01/12/security-brute-force-a-car-keyless-entry-pad/). Don't get too excited about "electronic keys" just yet. I do not know what car uses that type but my truck has one single button and billions of combinations and the combination changes every time. The system in that link looks like some toy thing or something like that.

http://auto.howstuffworks.com/remote-entry2.htm

The controller chip in any modern controller uses something called a hopping code or a rolling code to provide security. For example, if you read this PDF, it describes a system that uses a 40-bit rolling code. Forty bits provide 2^40 (about 1 trillion) possible codes. Here's how it works:

The transmitter's controller chip has a memory location that holds the current 40-bit code. When you push a button on your key fob, it sends that 40-bit code along with a function code that tells the car what you want to do (lock the doors, unlock the doors, open the trunk, etc.).

The receiver's controller chip also has a memory location that holds the current 40-bit code. If the receiver gets the 40-bit code it expects, then it performs the requested function. If not, it does nothing.

Both the transmitter and the receiver use the same pseudo-random number generator. When the transmitter sends a 40-bit code, it uses the pseudo-random number generator to pick a new code, which it stores in memory. On the other end, when the receiver receives a valid code, it uses the same pseudo-random number generator to pick a new one. In this way, the transmitter and the receiver are synchronized. The receiver only opens the door if it receives the code it expects.

[Critical1]

go to any big hardware store and check out the deadbolt section, you will be able to find matching sets of locks so you can buy say 2 or 3 dead bolts so you only need one key for your house no matter what door you try to get in through...last time I did this there were only about 6 different locks to choose from in the type I looked at and it was a big name brand.

a friend of mine growing up had a garage door key that would open doors to at least 3 other houses we knew of.

once I wen to get in my car to leave and it was sitting there running, some chick got in and started it (evidently it was a bit hard to get the key to turn to start it) and when she tried to put it in gear she realized her car was an automatic...and the damn key wouldnt come out. it was a strange way to meet a cute girl.

at this point its still going to be to expensive to make each physical lock so unique that no one elses key would open your lock.

[sailor]

go to any big hardware store and check out the deadbolt section, you will be able to find matching sets of locks so you can buy say 2 or 3 dead bolts so you only need one key for your house no matter what door you try to get in through...They sell the in sets especifically for that purpose. They also sell sets of padlocks keyed alike. All the padlocks on my boat use the same key.
last time I did this there were only about 6 different locks to choose from in the type I looked at and it was a big name brand. i do not believe that for a second. If all they had was 6 types it was because all they had was 6 locks. I can guarantee you that any name brand which makes locks will make them in thousands of different combinations.

at this point its still going to be to expensive to make each physical lock so unique that no one elses key would open your lock.Nonsense.

[ticker]

I have one of these (http://www.yalelock.co.uk/en/yale/couk/ProductsDB/?groupId=261&productId=6792) which the manufacturer claims to have 100,000 combinations.

[beowulff]

I do not know what car uses that type but my truck has one single button and billions of combinations and the combination changes every time. The system in that link looks like some toy thing or something like that.

As usual, it's not as secure as advertised: http://www.theregister.co.uk/2007/08/24/car_cypher_crack/

[BellRungBookShut-CandleSnuffed]

Not two weeks ago I was moving boxes to my friend's car. She told me it was the first one in the lot. As I was moving the baby seats to make room for the boxes, I began to wonder why she had never told me that she had kids or did babysitting on the side.

Turns out her first car was from my perspective the last car. I had been moving someone else's baby seats around. Not even the same car manufacturer either. I think she has a Land Rover and I unlocked a Jeep or something.

[Philster]

Anecdotes:

I've opened the wrong car door twice with my keys.

Once in high school I had my car keys ('85 Pontiac Firebird) in my pocket and put the key into a fellow students Pontiac Firebird and, voila, it opened. We were actually kidding before-hand saying, "I wonder what the odds are of my key opening your door?"

The other time was a few years ago when I came out of the barber shop, walked up to what I thought was my red Jetta, inserted the key and opened the door, but it felt strange, because as I looked up from the lock I clearly could see my Jetta a few spots over. The owner of the Jetta came over with a smile and in so many words said, "I've done the same thing".

[muldoonthief]

Maybe it's just late at night and I'm overtired, but shouldn't this be 75 = 16 807 keys, rather than 57 = 78 125?

You're right, it's (number of positions)^(number of tumblers). Consider the degenerate case - 1 tumbler, 7 positions. Obviously there are 7 different possible keys. 1^7 = 1, incorrect, but 7^1 = 7, correct.

[Philster]

Anecdotes:

I've opened the wrong car door twice with my keys.

Once in high school I had my car keys ('85 Pontiac Firebird) in my pocket and put the key into a fellow students Pontiac Firebird and, voila, it opened. We were actually kidding before-hand saying, "I wonder what the odds are of my key opening your door?"

The other time was a few years ago when I came out of the barber shop, walked up to what I thought was my red Jetta, inserted the key and opened the door, but it felt strange, because as I looked up from the lock I clearly could see my Jetta a few spots over. The owner of the Jetta came over with a smile and in so many words said, "I've done the same thing".

[ftg]

In replay to Critical1:
...
i do not believe that for a second. If all they had was 6 types it was because all they had was 6 locks. I can guarantee you that any name brand which makes locks will make them in thousands of different combinations.

Nonsense.

I was going to post pretty much what Critical1 said about the very limited offerings at big box hardware stores. Sure they can make a lot of combinations, but a given store will only stock a very small number of them. So if a builder is putting up some houses, there's probably going to be some of them that have the same keysets. Food for thought about how much do you trust your subdivision neighbors.

As for keyless cars and security: start reading here. (http://slashdot.org/article.pl?sid=06/05/03/1928256)

[ivan astikov]

As an ex-acquaintance of several car thieves in my misspent youth, I can add that certain keys were highly valued amongst them, for their ability to open the locks of any Ford car, up to a certain registration year.

[sailor]

As for keyless cars and security: start reading here. (http://slashdot.org/article.pl?sid=06/05/03/1928256)That links to http://www.leftlanenews.com/gone-in-20-minutes-using-laptops-to-steal-cars.html which explains little. As usual news articles are so badly done as to be worthless. One reporter will write an article saying electronic locks are 100% safe and the next reporter will say they are worthless crap, and both of them will use a few fancy words they do not understand but none of them will be able to give any sort of meaningful explanation.

It is possible that particular models have particular weaknesses but that is not inherent in the system. A wireless system can be made as safe as you like and virtually impossible to crack.

By the way, do they sell similar wireless controls for homes? Or maybe I could adapt one of a car.

[Stranger On A Train]

Oh, I forgot to mention another situation that might be of interest to the OP: In high school, we were all issued combination padlocks for our lockers. But friends often told each other their combinations, and it quickly became apparent that many locks, though they had different numbers, had the same pattern. For instance, one student's might be 17-21-30, and another student would have 23-27-36 (the first student's combination +6). So you could make batches of 40 identical locks at a time and just put the dial on differently, and you'd end up with 40 different combinations, but they wouldn't really be secure, since you could get someone's combo by finding out what the last digit is (by looking at the lock after they'd opened it), and then guessing which of about 10 different patterns they had.It is possible (by a method I will not elucidate on but which can readily be found elsewhere) on most spin dial combination padlocks to read the last number in the combo, and often the middle number as well, and since even well built consumer combopads (Master, Abus) the error range is +/- one digit, you have only about a few dozen combinations to try. Cable dial combo locks are even worse; with a little practice it is possible to read the combo in under twenty seconds and walk away with a bike.

With regard to pin tumbler locks, most common locks have only five or six tumblers, and four or five height settings, which gives between 1024 and 7776 possible combinations not including the mechanical limitations previously indicated by Chronos. (The variation in height settings are created by using different combinations of key and driver pins to provide a shear line; see the Wikipedia article (http://en.wikipedia.org/wiki/Pin_tumbler_lock) on the topic.) In addition, many pin tumbler locks for commercial buildings and apartments are master keyed (meaning they have two sets of key tumblers) which creates additional shear lines; such locks are typically easier to pick. The use of all-out tumblers, alignment sensitive (mushroom) tumblers, and a second line of internal tumblers is intended to make bypassing the lock mechanism more complex, but none of these means is foolproof or ensures that keying is unique.

However, the concern about having unique key combinations is rather a minor issue; the number of combinations virtually ensures that no casual user will have a similar key (stories about car makes sharing a small number of combinations aside), but it is typically easier to bypass the lock by some means other than picking the tumblers, especially in pursuit of nefarious purposes where damage to the lock or other entry points is immaterial. Most padlocks can be readily bypassed by a shimming attack on the shackle, and that assumes that the hasp itself is secure from attack. Most houses are far more vulnerable to entry via window or glass door than a frontal attack on a door lock. So trying to make locks unique in combination is not only futile, but pointless from a security aspect as well.

Mechanical locks should really be considered an anachronism at this point; it is relatively simple to make an inexpensive, self-contained locking system using an encrypted electronic handshake that is unique and essentially mathematically unbreakable. However, the desire to have a purely mechanical system is entrenched in both the lock manufacturing industry and the public at large.

Stranger

[Chefguy]

Not even close. The typical "Arrow" type house key has, as noted above, five tumbler positions with each capable of 6 different pin lengths for a total of 15,575 combinations. Long odds for finding a duplicate, but far short of being identical.

Pin length is not the only variable for keyways. You also have the "left", "center", and "right" options for each cut. Medeco locks throw in a fourth option which makes the lock virtually unpickable.

[CookingWithGas]

As usual, it's not as secure as advertised: http://www.theregister.co.uk/2007/08/24/car_cypher_crack/Oddly that article says, " It's far easier to capture the code used by a target when he opens his car and then replay it, rather than getting into all this complicated code breaking stuff." But defeating an attempt to capture a single code and replay it is exactly what these devices are good at, even though they could be cracked by more sophisticated means. Does the author know what he's talking about?

[sailor]

Oddly that article says, " It's far easier to capture the code used by a target when he opens his car and then replay it, rather than getting into all this complicated code breaking stuff." But defeating an attempt to capture a single code and replay it is exactly what these devices are good at, even though they could be cracked by more sophisticated means. Does the author know what he's talking about? Exactly, most news articles are written by people who are woefully ignorant of the topic. Capturing a code gains you nothing because each code is used once and then discarded. A new code is required each time.

[beowulff]

Exactly, most news articles are written by people who are woefully ignorant of the topic. Capturing a code gains you nothing because each code is used once and then discarded. A new code is required each time.

That's not completely true. Capturing the code may give you information as to where in the sequence the pseudo-random number generator is. Also, there are possible vulnerabilities due to the necessity to account for the transmitter and receiver getting out of sync (what happens if you press the transmitter button when you are too far away for the receiver to detect it?)

[sailor]

That's not completely true. Capturing the code may give you information as to where in the sequence the pseudo-random number generator is. Nope because the pseudo random number generators are seeded with different codes in each car so you have no idea what the next "random" number is going to be. If you could guess one number from the previous one it would not be random at all.
Also, there are possible vulnerabilities due to the necessity to account for the transmitter and receiver getting out of sync (what happens if you press the transmitter button when you are too far away for the receiver to detect it?)That has been explained. The receiver accepts a number N of subsequent codes so you are safe as long as you do not "lose" more than N-1 codes. If you press the button more than N times then it probably means a trip to the dealer, who has a master code... which can be leaked and this is probably the weakness in the system. That is the whole point, You can make the system as secure as you want but people demand an easy way of getting in if they mess up. You can't have it both ways. You can easily make a system which is unbreakable but then it is unbreakable if you mess up and people don't want that.

[beowulff]

Nope because the pseudo random number generators are seeded with different codes in each car so you have no idea what the next "random" number is going to be. If you could guess one number from the previous one it would not be random at all.

One doesn't have to "guess" what the next number is, if the algorithm and the seed are known. If you read my link above, this sort of remote control system has already been cracked.

[Omegaman]

Chrysler uses 8 pin locks and in addition, since some are computer encrypted ,must also be programmed to the vehicles computer. Although a key may fit the cylinder (lock) a skim code or pin number must be used to allow access to the vehicles computer. All keys for the vehicle must be programed at the same time, any key that still fits the lock will not start the vehicle unless programmed to the vehicles computer.

The skim code is 4 digit.

[yelimS]

I hate the straight dope. Final exams tomorrow, and all of a sudden, I've acquired an immense interest for keys.

[sailor]

One doesn't have to "guess" what the next number is, if the algorithm and the seed are known. If you read my link above, this sort of remote control system has already been cracked.I am afraid you are totally misunderstanding how the system works. The seed is not known. The fact that it has been cracked does not mean the system itself was cracked but more likely that a back door (which was implemented so dealers could open cars) has been leaked. With today's technology it is trivially easy to design a system which is unbreakable and I would be quite sure the systems in use are unbreakable by direct brute force if they are well designed. Now, back dorrs are another thing but a manufacturer who did not offer a back door would have to face irate customers who had messed up. It is a compromise.

As I say, devising a secure system is trivially easy.

[Stranger On A Train]

I am afraid you are totally misunderstanding how the system works. The seed is not known. The fact that it has been cracked does not mean the system itself was cracked but more likely that a back door (which was implemented so dealers could open cars) has been leaked. With today's technology it is trivially easy to design a system which is unbreakable and I would be quite sure the systems in use are unbreakable by direct brute force if they are well designed. Now, back dorrs are another thing but a manufacturer who did not offer a back door would have to face irate customers who had messed up. It is a compromise.A system using an asymmetric key system (like the public key encryption system used in the RSA SecurID) would provide a computationally secure means of key verification; that is to say, while the algorithm can technically be broken, it is computationally prohibitive to do so for any reasonable purpose as it would take thousands of years of calculations to crack the seed pseudoprime. Such a system is still technically vulnerable to "cellar door" and "man in the middle" type attacks, but these can be managed. You can make the system more secure by limiting access (i.e. physical access rather than radio signal) and not providing any kind of back door access, but then you run into Lao-Tze's modification of Clarke's Third Law:

Any sufficiently secure system will be indistinguishable from a large, featureless block of granite.

Well, maybe Lao-Tze didn't actually say that, but he would of if he had to deal with modern security systems.

Stranger

[OldGuy]

I do not know what car uses that type but my truck has one single button and billions of combinations and the combination changes every time. The system in that link looks like some toy thing or something like that.

The car must then store the information for every key that is used with it since I use one of my car keys all the time and leave the other hung on a pin in a closet at home. Nevertheless when i take it out maybe twice a year, it works fine though it can't possibly be synchronized with the other key any more.


And one other question. If I idly sit here pressing my remote when the car is too far away can I de-synch them? There must be some slack in the system whereby any of the next 100? (certainly more than 10) numbers in sequence will work.

[yelimS]

And one other question. If I idly sit here pressing my remote when the car is too far away can I de-synch them? There must be some slack in the system whereby any of the next 100? (certainly more than 10) numbers in sequence will work.

I suppose if you could de-sync it, that it would be possible to make the lock so it could be re-synced, too. Say if you pressed the button five-ten times in a row, and your car discovered that the sequence was contained somewhere in it's algorithm, only a bit off from the where it last synced. (billions of numbers still shouldn't take more than a few seconds to cycle through)

[sailor]

The car must then store the information for every key that is used with it since I use one of my car keys all the time and leave the other hung on a pin in a closet at home. Nevertheless when i take it out maybe twice a year, it works fine though it can't possibly be synchronized with the other key any more. That can easily be resolved by having the receiver acceptr two or more different senders.
And one other question. If I idly sit here pressing my remote when the car is too far away can I de-synch them? There must be some slack in the system whereby any of the next 100? (certainly more than 10) numbers in sequence will work. Yes, you can de-synch them by pressing the button repeatedly while out of range but it would have to be a huge number. (I still think it would be a neat thing to do to a hated coworker.) And probably that is one reason dealers need to have a back door. Which creates a vulnerability.

[sailor]

A system using an asymmetric key system (like the public key encryption system used in the RSA SecurID) would provide a computationally secure means of key verification; You do not even need that. Think about it. All you need is a key or password which is different every time. That's all. And rather than carry on sender and receiver all the millions of codes, all you need is a pseudorandom number generator which is seeded in both with the same code. After that the sequence is the same in both.

[Chronos]

The way I would do it would be a two-way communication: The key has a private crypto key, and the lock has a random number generator (possibly not even pseudo- : It woudn't use up entropy very fast, so it could use some sort of environmental sampling) and the public key. When you press the button on the key, it sends a signal to the lock. On receiving this signal, the lock produces a random number, encrypts it using the public key, and transmits the encrypted number to the remote. The remote then decrypts it using its private key, and transmits the decrypted number back to the lock. If it matches the original random number, the lock opens, otherwise it doesn't. Fully secure, intercepted signals are useless, and it can use any number of remotes without any of them ever getting out of synch.

[WhyNot]

Just anecdotally, I chose my best friends based on their front door keys. Okay, not really, but purely coincidentally, my own housekey has opened my best friend's door, through 4 best friends and four pairs of locks now. It's a little eerie, actually. First one was in high school, when we found out due to desperation when she locked herself out in the middle of a snowstorm and we tried my key, "just for the hell of it." It worked.

Next in college, a friend and I had been out drinking and she handed me her keys to unlock her front door, only they were actually my keys, but they worked anyhow.

Third I was joking around, telling the story of the first two times and laughing about, "wouldn't it be funny if..." and, well, I got dared to try it on her door, and it worked.

The fourth time I just got all Jedi certain that my key juju was going to work, and indeed it does.

One house and three apartments for me and each of those keys worked in the lock of a friend. I'm pretty convinced locks are nearly 100% psychological, and if you tried yours in your friends' homes, a startling number of them would work.

[Chronos]

Either that, or you have a magical key. Have you ever tried using it to open an old medicine cabinet with a plastic Indian figure in it?

[sailor]

The way I would do it would be a two-way communication: The key has a private crypto key, and the lock has a random number generator (possibly not even pseudo- : It woudn't use up entropy very fast, so it could use some sort of environmental sampling) and the public key. When you press the button on the key, it sends a signal to the lock. On receiving this signal, the lock produces a random number, encrypts it using the public key, and transmits the encrypted number to the remote. The remote then decrypts it using its private key, and transmits the decrypted number back to the lock. If it matches the original random number, the lock opens, otherwise it doesn't. Fully secure, intercepted signals are useless, and it can use any number of remotes without any of them ever getting out of synch.
This is unnecessaryly complicated. You (and others in this thread) are overthinking this problem. There is no need for two way communication or for encryption. It solves nothing and just complicated the mechanics of implementing it. Encryption is needed when you want to communicate information but keep it secret from listeners. Here there is no need to keep it secret because the code changes once it has been used. There is no point in keeping it secret.

All you need is that transmitter and receiver agree on a long list of keys beforehand. This could be done simply with the keys being kept by both in memory but it is more practical to use a pseudorandom number generator. Keys are then used and discarded. Encryption and two way adds nothing but complexity. If you want to add security you make the key longer.

[Q.E.D.]

How would your system handle the case of the remote button being pressed beyond the range of the receiver?

[sailor]

How would your system handle the case of the remote button being pressed beyond the range of the receiver? Have you tried reading the thread? Because it has been addressed. More than once.

[sailor]

By the way, it is not "my" system. It is what most vehicles use today. I will repeat the link:
http://auto.howstuffworks.com/remote-entry2.htm

[Q.E.D.]

Oh, I thought you were devising your own new system, since one major version of the system you're describing has been cracked, as previously noted; something you've failed twice now to address.

[WhyNot]

Either that, or you have a magical key. Have you ever tried using it to open an old medicine cabinet with a plastic Indian figure in it?
Wouldn't that be awesome? But no, it's been four different keys of mine that open four different friends different abodes. That's the really weird part. It's not one uber skeleton key, it's just coincidence after coincidence.

[sailor]

Again, and I repeat myself, it seems most probable that the sistem has not been cracked but that what has been cracked is a back door implemented. Which I have already posted. Please try to keep up. Or show that the system has indeed been cracked rather than the back door. Because closing the back door is extremely easy but customers would not want that. If you had read the thread I would not need to repeat this and you could be addressing those points directly.

You would also need to prove that the two way system is more robust in every way. Which I think is not the case. I think it has greater vulnerability.

[Q.E.D.]

We have only Microchip's (http://blog.wired.com/27bstroke6/2007/08/keeloq-company-.html) word for it, but as they refuse to provide details, I can only assume the system is not, in fact, as secure as they (and you) would have us believe.

[sailor]

My point, in response to Chronos is that adding two way encryption (a) significantly complicates the system and (b) probably weakens the security rather than enhances it.

The present system can be made arbitrarily robust because you can make the keycode as long as you like and the pseudorandom number generator as big as you like. The limit of this is the one time pad. There is just no way that this sytem can be cracked.

Now implement a back door so that dealers can open cars for users who lost their keys or de-sync'd their transmitters and you have a weakness which is exploitable. And once you have that weakness built into the system it makes no sense to build it stronger than reasonably necessary.

So, yes, the system is not as robust as it may be. But that is not the point I made. The point I made is that two way encryption adds great complexity without adding security and very probably weakening the system.

Many beginners might think encrypting twice always adds strength but this is not the case and in many cases it weakens the system. Here we have a case where I believe the pseudo one time patch is stronger than anything else.

If someone wants to argue the contrary I'll be happy to hear arguments.

[Chronos]

OK, here's one way the pseudo-one time pad is weaker than the two-way communicator: If I get ahold of the remote away from the car, I can press the button a few times next to a receiver and grab the next few codes, and then leave the remote right where I found it with the owner none the wiser. I can't do that with the encryption method, since the only secret information is the private encryption key, and that's never broadcast.

Many beginners might think encrypting twice always adds strength but this is not the case and in many cases it weakens the system.First of all, no decent encryption is weakened by being encrypted again, because if it were, then the first thing an attacker would do with an encrypted text is to just encrypt it again. Second, even if it were true, I have no idea what relevance that would have to my proposal, since I'm only encrypting once and decrypting once.

Could you care to describe how the encryption in any way weakens the system?

[sailor]

OK, here's one way the pseudo-one time pad is weaker than the two-way communicator: If I get ahold of the remote away from the car, I can press the button a few times next to a receiver and grab the next few codes, and then leave the remote right where I found it with the owner none the wiser. That gives you no useful information whatsoever (except that if you have the remote you can open the car -- which is the whole point of the remote and which you could do with any remote).

I can't do that with the encryption method, since the only secret information is the private encryption key, and that's never broadcast. Again, you are missing the point that no secret is needed because there is no need to keep the codes secret because they are immediately discarded and nothing can be discovered from the old code about the new code. That is the basis of the whole concept as implemented.

First of all, no decent encryption is weakened by being encrypted again, because if it were, then the first thing an attacker would do with an encrypted text is to just encrypt it again. Sometimes things are not as they seem. I remember reading (maybe in the code book by Singh) several examples of cedes being weakend by being encrypted twice because that introduced redundancy. Each code needs to be studied independently. But the obvious case is the Enigma where encoding a second time with the same key gives you the original cleartext directly. And I think the allies during WWII would have considered Enigma a "decent" encryption (even though it is outdated today).

Second, even if it were true, I have no idea what relevance that would have to my proposal, since I'm only encrypting once and decrypting once. My comment was not supposing you would encrypt twice but to show that sometimes adding things which you would at first blush think were good might turn out to be bad.

Could you care to describe how the encryption in any way weakens the system? As i said, I think in the best of cases it adds nothing because the present system can be made as strong as you want and unbreakable (without counting back doors, stolen keys etc, to which no system is immune) but by adding encryption, while adding no further security, you are adding complexity and cost unnecessarily which can lead to malfunction more easily. You would need a *much* more complex remote, with more processing power. And it adds nothing.

[sailor]

To simplify my reasoning: each successive code is random and cannot be guessed by knowing the previous codes. The only way to know the next code is to have access to the seed (the key) but, obviously, if you have access to the key you can get in in any case.

That's the simple analysis. Encryption adds nothing. Now, you can't say "well, suppose you have a really shitty pseudo random number generator and really good encryption..." because that is not a fair comparison.

The present system can easily be made as strong as you like with little complication, just by adding bits. The howstuffworks article says 40 bits are used. Suppose the next 256 (8 bits) codes are accepted, that means that the chance of guessing a valid code by chance is one in 2.3^10. Implement gradual increasing delays as wrong codes come in and there is no way in the world this system can be broken.

Again, the weakness comes from the people. If the guy at the dealer or the factory knows the backdoor and reveals it there is no system in the world which will prevent that.

[Stranger On A Train]

Sometimes things are not as they seem. I remember reading (maybe in the code book by Singh) several examples of cedes being weakend by being encrypted twice because that introduced redundancy. Each code needs to be studied independently. But the obvious case is the Enigma where encoding a second time with the same key gives you the original cleartext directly. And I think the allies during WWII would have considered Enigma a "decent" encryption (even though it is outdated today).The Enigma system (which was neither a single cyphertext system nor a single type of machine) had some significant cryptographic weaknesses which, combined with knowledge of key settings or a small amount of plaintext message, could be readily broken even using the primitive electromechanical computers of the time. Comparing even the more capable plugboard Enigma systems to a modern public-private key digital encryption system is like comparing a crossbow to an LGM-118A Peacekeeper ICBM. Enigma and similar systems are laughably insecure by any modern cryptographic standard.

And encryption is useful for more than just concealing data; PGP/GPG and derivatives are routinely used to digitally sign plaintext data in order to assure the end user that the data has not been adulterated in transmission. Similarly with a keycode system encryption can be used to assure that the handshake is secure, even though the signal itself it is available for all to see.

Stranger

[sailor]

The Enigma system (which was neither a single cyphertext system nor a single type of machine) had some significant cryptographic weaknesses which, combined with knowledge of key settings or a small amount of plaintext message, could be readily broken even using the primitive electromechanical computers of the time. Comparing even the more capable plugboard Enigma systems to a modern public-private key digital encryption system is like comparing a crossbow to an LGM-118A Peacekeeper ICBM. Enigma and similar systems are laughably insecure by any modern cryptographic standard. I already said that. What I am also saying is that I have read in some books about cryptography that encrypting twice can weaken rather than strengthen the encryption. And it makes sense to me even if it is not obvious at first sight. I am not comapring Enigma to anything, I am using it as a proof of concept.
And encryption is useful for more than just concealing data; PGP/GPG and derivatives are routinely used to digitally sign plaintext data in order to assure the end user that the data has not been adulterated in transmission. Similarly with a keycode system encryption can be used to assure that the handshake is secure, even though the signal itself it is available for all to see.

Stranger I am very familiar with PGP which I have used for many years now and which I use daily. But that does not answer the question: How does encryption improve the present system of electronic car locks? Because sliced bread is also very useful for making sandwiches and I hope no one will deny that but how is that relevant to the question I asked? Please explain it, don't just say it is so.

[Chronos]

That gives you no useful information whatsoever (except that if you have the remote you can open the car -- which is the whole point of the remote and which you could do with any remote).No, that means that I can open the car without the remote, because I have the next few codes the lock is going to expect. You don't get much of a bigger violation of security than that. Further, the dealer backdoor is only needed in your scheme to cover for the possibility of the remote and lock getting too far out of synch: If you remove that possibility, then you don't need the dealer's backdoor any more.

Your system also has the vulnerability that you need a pseudorandom number generator which can produce unpredictable digits so long as the initial seed isn't known, even when an arbitrary set of previous outputs is known. That's a very tall order to fill: Usually, pseudorandom number generators produce sequences of numbers by using each number in the sequence as the key to produce the next one. Unless you have some specific algorithm in mind that meets these criteria, and that algorithm has been proven to be secure? My proposal doesn't have this problem at all, because, since there's no need for synchronization, I can use a true random number generator.

In short, I know how secure my system is, since it's composed entirely of off-the-shelf algorithms which have been studied in great detail. Can you say the same of yours?

[sailor]

No, that means that I can open the car without the remote, because I have the next few codes the lock is going to expect. You don't get much of a bigger violation of security than that. Well, the way I see it, the whole system in both cases is based on the remote not being compromised. If the remote is compromised then whoever has the remote can open the car. You introduce the variant that the bad guy, rather than just open the car with the remote, can copy the codes and use them later (but before the remote is actually used again by the owner). I suppose it is theoretically a valid vulnerability although in the real world I do not think it merits much concern. Interesting idea though.
Further, the dealer backdoor is only needed in your scheme to cover for the possibility of the remote and lock getting too far out of synch: If you remove that possibility, then you don't need the dealer's backdoor any more. No, the backdoor is needed also when customers lose or destroy their remotes. I believe a back door is commercially necessary and that no automaker would sell a car without a means of easily getting in if the customer's remote stopped working because it went in the washer with the pants. But that is a different discussion.
Your system also has the vulnerability that you need a pseudorandom number generator which can produce unpredictable digits so long as the initial seed isn't known, even when an arbitrary set of previous outputs is known. That's a very tall order to fill: Usually, pseudorandom number generators produce sequences of numbers by using each number in the sequence as the key to produce the next one. Unless you have some specific algorithm in mind that meets these criteria, and that algorithm has been proven to be secure? My proposal doesn't have this problem at all, because, since there's no need for synchronization, I can use a true random number generator.

In short, I know how secure my system is, since it's composed entirely of off-the-shelf algorithms which have been studied in great detail. Can you say the same of yours? As I said, the whole discussion involves pseudo random number generator and encryption either theoretically perfect or both of the same quality. If you compare a bad pseudo random number generator with good encryption then that's not a fair comparison. Pseudo random number generators can be made as good as you want and beyond all practical needs for such an application. In practical terms I believe the present system is good beyond any practical needs and that any vulnerabilities introduced by having back doors exist regardless of the system.

In other words, it does not matter how strong the front door is if you have a vulnerable back door. If I want to steal a car it is easier for me to find the back door than to try to break the front door. The system is as weak as the weakest link. Given that the back door is incredibly weak, seeing how it can be opened by thjousands of people already, it does not make sense to build a more robust front door.

Now, in a different situation, say the code which would open the door to the gold at Forth Knox, which would have no back door and which would be had by only a few individuals, then yes, I agree that encryption is better.

[sailor]

By the way, it would be interesting to know what happens in real life when you lose the remote. You call the dealer and give them the VIN. What happens next?

The problem, as I see it, is that, not only do you need a new remote but both the remote and the vehicle need to be re-seeded and synchronized. So I suppose there is some way to do that by just standing outside the car with the proper gear.

If the password was constant and encrypted and could be changed by the user then this problem would not arise because the user could just program a new remote with his old password. This would add the complexity of adding two way encryption and of allowing the user to program the password but it would obviate the need for a back door when the user loses the physical remote (although the back door is still needed if the user loses the password). It seems there is a balance between security and having a back door.

It seems that car manufacturers for now have decided one way rolling codes offer sufficient security. This might change if they decide to implement things like being able to communicate with your vehicle using your blackberry or mobile phone. it would be interesting to have a vehicle which to be operated needed continuing validation every few minutes from the owner's blackberry, whether in the car or thousands of miles away. That way the owner could always know where the vehicle is and could stop operation at any time.

[Stranger On A Train]

I already said that. What I am also saying is that I have read in some books about cryptography that encrypting twice can weaken rather than strengthen the encryption. And it makes sense to me even if it is not obvious at first sight. I am not comapring Enigma to anything, I am using it as a proof of concept.The overall scheme used with the Enigma encoder was not a "strong" encryption scheme. (I'm using strong in the strict cryptographic sense which is a measure of the randomness of the resultant message.) Enigma relied on having a large number of permutations to prevent cracking by brute force attack; however, with certain configurations of the encoder and particular settings of the plugboard discernible patterns could readily be found in the encrypted text. The "unsteckered" commercial Enigma could actually be broken by hand, and the military versions of Enigma were broken largely because of a methodological error, to wit the use of a keycode group that preceded each individual message that was encrypted using the daily key and repeated, which provided a crib that allowed for generally easy cracking of the message cypher.

In contrast, a modern asymmetric cryptographic system using a sufficiently large key size is essentially unbreakable by any unaided analytical attack in any reasonable amount of time, even allowing for a vast future increase in computation capability. This is because the resultant encryption scheme is an essentially random number (a number formed from an algorithm using two very large pseudoprime numbers) but not requiring a shared private key like a one-time-pad cypher that could be intercepted or duplicated. A scheme like the RSA system or similar systems allows communication between parties who have no shared private keys, and there is no way to back out the private key from shared public keys; in fact, it isn't even possible to decrypt a message by having the sender's private and public keys; the message has to be decoded using the receiver's private key. Nor is it effectively possible to weaken the message by a second encryption pass, since the key has no repetition of the preceding key.

With all due respect, you may have read a few books on encryption but you don't seem to understand the fundamentals of the methodologies, specifically, what made the Enigma-based systems weak, and why modern encryption algorithms and encoders don't suffer from those weaknesses (though they do potentially have others, as listed above).

How does encryption improve the present system of electronic car locks? Because sliced bread is also very useful for making sandwiches and I hope no one will deny that but how is that relevant to the question I asked? Please explain it, don't just say it is so.The same way a digital signature on an electronic document or e-mail does; it provides a robust, effectively unique, non-repeatable confirmation signal. It's like having your locks changed every time you leave your car. Even if someone steals the keys out of your pocket, by the time they get to the car the combo has changed, and in a way that isn't predictable just by seeing the shared key.

Stranger