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:


sender initiates communication
receiver sends a random 32 bit number XORed with a secret key
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)
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?

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.
