Challenge/response authentication for garage door opener

Question

I'm building an Arduino based radio garage door opener, and in order to protect it from replay attacks I've came up with this algorithm:

1. sender initiates communication
2. receiver sends a random 32 bit number XORed with a secret key
3. sender reverses the XOR operation using the same secret key, resolves the challenge (ex: challenge ^ 2 - 5), XORes and sends the result to the receiver together with the command (gate up or gate down)
4. receiver compares the response with it's own calculation of the challenge and executes the command if they match.

I'm curious, do the steps described above ensure that the response is impossible to guess for an attacker?

Answer 1

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)² - 5) ⊕ K, or if we skip the decryption step: R = (q² - 5) ⊕ K.

The attacker can see both C and R. If the attacker then xors the two values:

C ⊕ R = (q² - 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 = (q² - 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.

Answer 2

First of all, you need a cryptographic function whose relationship between input and output is not readily discernible. XOR just won't cut it. A slow but effective way to encrypt the data would be to split the 32 bit value into two halves, H and L, and iterate the following a few times:

• Pad H with enough bytes to make a cryptographic block for DES, AES, or some other decent scheme (and a secret key) and encrypt it.
• Set H to the old value of L, and set L to the old value of H xor'ed with 16 bits from the encrypted block.

If one uses the above approach with a decent encryption method at its core, the result will be a secure 32-bit-to-32-bit mapping. The inverse mapping can be obtained by swapping H and L, doing the above procedure, and swapping them back.

A 32-bit payload is somewhat small, but could provide a reasonable level of security if challenges are never repeated. That could be accomplished by having the sender keep a lifetime count of how many challenges have been sent, and using that as the challenge data to be encrypted and validated.

Answer 3

Your step 4 says it all, "receiver compares the response with it's own calculation"

You don't need reversible encryption if the receiver is just comparing the response to a single expected value (it's own calculation)

What you want is to HASH, not encrypt.

Not only does reversible encryption require more hardware, but that reversibility does establish a relationship between the plain text and the cipher text that an attacker can use to determine the secret key. As mentioned by polynomial in other comments, xor is very weak.

What you want, is to force an attacker to brute force a very large key space. A one-way hashing function does exactly that.

This is how most challenge response authentication works. The nonce is randomly generated and sent in the clear, then it is hashed with a secret key kind of like a salt. That's the response that gets sent back. Mutual authentication challenge and response does this twice.

For added security yes, you can iterate the hashing function multiple times. It makes it more computationally difficult to brute Force. The receiver need only wait a short time before it forgets it's nonce, eliminating the possibility of replay attack.

Polynomial did mention using a hash table, which is interesting, precisely because that's how most modern garage door openers work today. Problem with that is, they are subject to rolljam attacks. An attacker merely forces an out of sync condition which can be exploited. Challenge and response eliminates that vulnerability because the random challenge is never repeated.