More details here.
High-end manufacturers use expensive challenge-response schemes (the key sends a request, the car answers with a challenge, and the key sends a reply derived from the challenge with some algorithm).
Even so, such algorithms are proprietary, usually not reviewed, and could well be an example of "rolling your own crypto". There are solutions, but to quote the paper below,
Note, however, that a physical implementation of mathematically secure
ciphers still can be vulnerable to side-channel (typically power
analysis) attacks. Also the key distribution/management, when wrongly
implemented like with the Keeloq's manufacturer key, can introduce a
single point of failure into the commercial cryptosystem. In other
words, the chain is as strong as its weakest element, so the marketing
headword 'employes AES' does by far not mean that the product as whole
is secure.
Cheaper manufacturers use a rolling scheme employing a PRNG. Quite often, the car has a "guard period" after receiving a code, in which it will actively not recognize any code, to avoid bruteforcing. Several of these schemes actually relied on the secrecy of the algorithm, and have been broken (link to theory, practice and source code):
Recently it has been demonstrated how the manufacturer key can be
extracted from a receiver device by a physical side-channel
cryptanalysis and how a particular remote control can be cloned
(either knowing a matching manufacturer key without physical access to
the remote, or without manufacturer key but requiring physical access
to the remote)
Still cheaper manufacturers employ a rolling scheme between N codes, which is vulnerable to replay attacks (you get one code) or "stalking" the garage until you get enough codes.
Another vulnerability of remotes is jamming. You stalk a parking lot and fill the 433 MHz band with noise. Out of every ten people that lock their cars with a remote, nine of them will notice that the car lock didn't actually engage. They'll try again, blaming the batteries on the key fob, and finally lock the car manually (or succeed by transmitting from a few inches, which will further convince them it's the fob battery's fault). Maybe one driver in ten will walk away blissfully unaware that his car was actually left unlocked. You can spot him from afar (he's the one who did not turn back) and rob him blind: no need for sophisticated crypto at all. A 433 MHz transmitter and a white noise generator are enough.
Case in point
Your aftermarket key uses a KeeLoq HCS200. This has been proved and confirmed to be insecure:
KeeLoq remote keyless entry systems are widely used for access control
purposes such as garage openers or car door systems. We present the
first successful differential power analysis attacks on numerous
commercially available products employing KeeLoq code hopping. Our new
techniques combine side-channel cryptanalysis with specific
properties of the KeeLoq algorithm. They allow for efficiently
revealing both the secret key of a remote transmitter and the
manufacturer key stored in a receiver. As a result, a remote control
can be cloned from only ten power traces, allowing for a practical
key recovery in few minutes. After extracting the manufacturer key
once, with similar techniques, we demonstrate how to recover the
secret key of a remote control and replicate it from a distance,
just by eavesdropping on at most two messages. This key-cloning
without physical access to the device has serious real-world
security implications, as the technically challenging part can be
outsourced to specialists. Finally, we mount a denial of service
attack on a KeeLoq access control system. All proposed attacks have
been verified on several commercial KeeLoq products
This is not so much due to a shortcoming in KeeLoq's algorithm but in its practical implementation by the vendor. As such, there are claims that an aftermarket key can actually be fixed:
If your receiver device contains a
specialized hardware KeeLoq decoder, it should be possible to flash
your own randomly selected device code into that chip and matching
remotes, following the instructions in appropriate data sheets. In
this way you circumvent the problem with the learning algorithm and
manufacturer key.
(Along with a bounty of information, the page explains why my old garage remote happened to also open the University gate, as I discovered one sleepy morning when I inadvertently picked up the wrong remote - different on the outside, the two receivers must have been identical on the inside).
Update: buttonless fobs
A variation on the concept of "car remote" is the fob. This is normally a passive device (no batteries). It contains a coil that absorbs the nearby electromagnetic field, and if it is powerful enough it awakens and is able to modulate its own absorption. As a result, whatever is transmitting the electromagnetic driving field will experience a sequence of short power losses. By representing a power loss with a 1 and normality with 0, the driver unit will receive something like 000000000...0001101010101110011. The sequence is usually always the same (very high-end units implement challenge-response) and is unique for every fob.
The same or similar technology is used in some contactless cards and keys.
Since this kind of electromagnetic coupling only happens at very short distances, the fob is considered "safe". It most definitely isn't.
Attack 1: while the driver unit is massive (and usually mounted inside a car), it is possible to install one in a suitcase. Pass within one meter from the victim (whose will awaken, believe itself near the car, and transmit the unlock code). Record the unlock code. Profit.
Attack 2: much more expensive, but effective against USD 100,000 cars, so possibly worth your while. Requires two suitcases connected via Internet (put one Android phone in "personal access point mode" inside each for USD 79,98). The first is the same suitcase as above, but it does not record the unlock code, it transmits it to the other suitcase. A coil in the second suitcase starts siphoning energy from the car transmitter. The following "dialogue" (classical man-in-the-middle attack) ensues in the next few milliseconds:
- SUITCASE 1: (absorbing)
- CAR: (sleepily)...is there a fob nearby? Who's drinking me energy?
- SUITCASE 1: Yes, I'm a fob. I'm your fob.
- CAR: let me generate a random unguessable number: 12345. Add yours. What's the answer?
- SUITCASE 1 (to suitcase 2): get me the answer to 12345 +.
- SUITCASE 2 (to fob): My number is 12345. Add yours. What's the answer?
- FOB: It's 73219.
- SUITCASE 2 (to suitcase 1): 73219
- SUITCASE 1 (to car): It's 73219.
- CAR: You're correct. Alarm deactivated, unlocking door. Have a nice day.
UPDATE: and now they did it on CCTV, and the "suitcase" is no larger than a box.
This kind of vulnerability requires a contactless, buttonless fob, and can be protected against by wrapping the fob in electromagnetic shielding. This is not the same thing as aluminum, which protects against radio waves. Magnetic coupling is best shielded by iron foil or special magnetic shielding. Also keeping two identical fobs (of different cars) in close contact will work, if riskier, because by transmitting different codes on the same frequency they're liable to confuse the receiver.