Challenge/response authentication for garage door opener
No.
Let's write it up:
- C is the challenge message
- R is the response message
- K is the secret key
- C = q ⊕ K where q is a random number.
- R = ((C ⊕ K)2 - 5) ⊕ K, or if we skip the decryption step: R = (q2 - 5) ⊕ K.
The attacker can see both C and R. If the attacker then xors the two values:
C ⊕ R = (q2 - 5) ⊕ K ⊕ q ⊕ K
Since we're xoring with K twice, we can just drop those operations out. This gives the attacker the following:
C ⊕ R = (q2 - 5) ⊕ q
There are only a few values for q for any given value of C ⊕ R in the 32-bit space. In fact, it's an easy enough operation to just brute force: just try all q values until you find all the values that match.
This gives you some possible value of q, the random number. Since C = q ⊕ K, just compute C ⊕ q for each candidate q to get a small number of possible K values. Repeat this process for a second time and see which candidate K value came up in both runs: this gives you K.
I even wrote a PoC!
// our key!
int k = 0xBAD1DEA;
void Main()
{
// output the key just so we can see it in the output
Console.WriteLine("Key is: 0x{0:X8}", k);
int challenge = GenerateChallenge();
int response = GenerateResponse(challenge);
Console.WriteLine();
Console.WriteLine("Cracking the challenge and response...");
// this is the attacker: they know only the challenge and respoonse!
Crack(challenge, response);
}
int GenerateChallenge()
{
Random rng = new Random();
// I'm keeping the random number small-ish to avoid the c^2 operation from overflowing
// this is just a limitation of the fact that .NET has sane integer types that don't wrap on multiplication overflows
int q = rng.Next(0, 10000000);
Console.WriteLine("I picked q={0}", q);
int challenge = k ^ q;
return challenge;
}
int GenerateResponse(int c)
{
c ^= k;
return ((c * c) - 5) ^ k;
}
void Crack(int c, int r)
{
int c_r = c ^ r;
// try all possible 'q' values.
for (int q = 1; q < int.MaxValue; q++)
{
if ((((q * q) - 5) ^ q) == c_r)
{
// got a match, output it
Console.WriteLine("q candidate: {0}", q);
Console.WriteLine("k candidate: 0x{0:X8}", q ^ c);
}
}
}
Sample output:
Key is: 0x0BAD1DEA
I picked q=2847555
Cracking the challenge and response...
q candidate: 2847555
k candidate: 0x0BAD1DEA
The "cracking" process took less than a second on my system.
EDIT: Since this apparently wasn't clear: you're not bruteforcing anything against the real system. This approach doesn't involve you sending any data to the receiver at all. You simply sit there with a software defined radio (SDR) and capture the signals produced when the owner opens their garage door. You then extract the challenge and response values from those signals - these are C and R. Given C and R you can use the above process to compute a few possible q values for that particular challenge/response pair. In some cases you'll get only one, in some cases you might get 2 or 3. Compute q ⊕ C for each candidate q to get a list of candidate K values. If you get more than one, wait for them to open their garage again and capture another C and R pair, re-run the process, and see which candidate K values match the first time around - this will give you the real K value. Once you've got that, you've got everything you need to impersonate the real opener device. You can reply correctly every time since you know the value of K.