20

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?

  • 3
    Is there any reason public key crypto would be unsuitable in your case? It seems well suited to your problem, and is generally considered secure. – March Ho Apr 21 '16 at 22:01
  • 1
    What about the delayed response attack? User presses door button, attacker intercepts challenge and response and prevents the receiver from receiving the response. User presses it again, attacker re-sends the response (so the door opens) and intercepts the new challenge and response. Now the attacker can re-send the second response three hours later when you're asleep. – immibis Apr 22 '16 at 0:29
  • 1
    I would like to remind everyone that an arduino only has 32kb of ram, and thus may have trouble implementing some forms of full blown complex encryption. – Numeron Apr 22 '16 at 6:20
  • I've came up with the above "algorithm" because 8 bit microcontrollers that I intend to use have very limited memory (only 2kb in my case). – Denis Denisovici Apr 22 '16 at 6:31
  • 1
    I'd like to point out that a would-be thief is probably getting in through an unlocked door or window, rather than hacking your garage door open. Or they might just lift the door manually. I'm not saying this encryption is a bad idea, just that it's only a small part of being secure. – Nic Hartley Apr 22 '16 at 11:16
58

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.

  • 13
    @DenisDenisovici unless you are really really confident that the wireless stream won't glitch resulting in a wrong answer from the right client, I would suggest a slightly more graduated tarpit like doubling the timeout for each consecutive failure. If it were me, hitting the remote and having a 5 minute delay because there was a microwave on or something, would cause me to just ram my car through the thing in frustration. – Jeff Meden Apr 21 '16 at 13:03
  • 9
    @JeffMeden You'd never send an invalid response. You brute-force the value of q locally until you find one which matches a captured C and R pair, and repeat until you have a candidate q value that appears in the results of multiple captured challenge/response pairs. At that point you know K and can produce correct responses just like the real device. The bruteforce approach is just a naive method to get the possible values of q - you're not actually sending any challenges. – Polynomial Apr 21 '16 at 13:11
  • 11
    @DenisDenisovici The delay won't help secure the mechanism at all, and you're in violation of Kerckhoffs' principle. Assume the attacker knows the formula, design your system around that fact. Rate limiting won't help because, as my edit notes, you're passively capturing challenge/response values until you find the value of K (usually the first captured unlock, otherwise certainly the second) at which point you can always impersonate the unlocker perfectly. – Polynomial Apr 21 '16 at 13:21
  • 1
    @JeffMeden Or just use a rolling code approach with a hash. H(k||c) where k is a shared key and c is an incrementing counter kept track of by both sides. Have the receiver accept any c within a range of 10 of the counter and update when a successful request comes in - this allows the system to continue working even if you press the button a few times out of range of the receiver. – Polynomial Apr 21 '16 at 14:42
  • 1
    @cat Proof of Concept. – Polynomial Apr 21 '16 at 22:48
1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.