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.