2
$\begingroup$

I need your advice on following scheme of exchange protocol between remote lock and key. I'm planning to use following algorithm:

  1. Key generates unique value that never repeats (in reality it's just counter that increments every time the button is pressed), let's call it "NONCE1".

  2. Key sends a request to the lock which consists of NONCE1 and H1 = MD5(NONCE1 + KEY1). Second part is used only for "signing" the request, attacker wouldn't be able to generate valid request if he doesn't know KEY1.

  3. Lock checks if H1 = MD5(NONCE1 + KEY1), this is used to check if incoming request is coming from the key (or at least from the one who is aware of the value of KEY1). Additional steps that were not described previously is:

    • Lock checks if NONCE1 of the previous key request less than NONCE1 received just now. This part prevents acting on previously processed requests, attacker who has such request won't be able to go any further. I'm trying to leave him in the situation where old requests are not accepted by the lock, and new requests couldn't be generated because he can't reproduce it without KEY1.

    • Lock sets NONCE1(previous request) = NONCE1(current request)

  4. Lock generates completely unique value that never repeats, let's call it "NONCE2".

  5. Lock sends a response to the key which consists of H2 = MD5(NONCE2 + KEY2). NONCE2 - is counter based (in order to completely exclude possible collisions), so in order to hide it's "counter - based nature" from an attacker, MD5(NONCE2 + KEY2) is used here.

  6. Key does H3 = MD5(H2 + KEY3) and sends it back to the lock

  7. Lock checks if H3 = MD5(H2 + KEY3) and acts on that

What could be possible vulnerabilities? Is it safe enough to use MD5 in this particular case?

I've added some additional "substeps" to clarify it a little bit

Accepted suggestion / solution is following:

  • Get rid of steps 1 - 3
  • Replace MD5 with HMAC-XXX
Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Use HMAC not a silly ad-hoc MAC. $\endgroup$
    – CodesInChaos
    Jan 29, 2016 at 9:05
  • $\begingroup$ 1) salt1/2/3 - yes it's secret keys known only by key and the lock and they never transferred in between. Nonce1 / Nonce2 / Nonce3 - would be correct names for them just for better understanding? 2) How HMAC would possibly improve security in this case? $\endgroup$
    – Ruslan
    Jan 29, 2016 at 9:10
  • $\begingroup$ Your MAC $H(M+K)$ relies on the collision resistance of the hash, which is broken for MD5. $H(K+M)$ would be even worse. HMAC does not rely on collision resistance and is explicitly designed to be used as a MAC. So using HMAC is essential for such a protocol. $\endgroup$
    – CodesInChaos
    Jan 29, 2016 at 9:35
  • $\begingroup$ I'm more or less understand what your point is, but I think that the collision resistance it's not actually what it relies on, because even if you find another string that gives you same hash it won't give you anything? That's why I especially mentioned about MD5 in this very special case, where critical part of it - is ability to find an original message using it's hash, which is I think for MD5 is not that easy. If you know the value of H2, would it be relatively easy to fake (generate) H3? $\endgroup$
    – Ruslan
    Jan 29, 2016 at 9:45

1 Answer 1

Reset to default
6
$\begingroup$

Even after your updates, the first part seems unnecessary. However, steps 4-5 do indeed prevent the attacker from learning future nonces they could ask the key MAC values for. So the protocol steps 4-7 would be secure with a secure MAC.

I agree with CodesInChaos that using HMAC would be better, because H(m||k) has some weaknesses, while HMAC is standard. Unless you have a good reason to use MD5, I would also prefer to use a stronger hash, though HMAC-MD5 is still secure (that is about encrypted data, but applies generally).

However, I do not think the weaknesses actually apply here, since the attacker does not have freedom to choose the values they need to calculate the keyed hash for. So even as is it should be secure. Despite that I would recommend switching to HMAC. Even better would be to use an existing mutual authentication protocol meant for this purpose, like the one descrived in Chapter 10 of HAC (see 10.2.3).

The below applies to the protocol as described in the original version of the question.

  1. Key generates completely unique value that never repeats (some kind of a counter), let's call it "NONCE1".
  2. Key sends a request to the lock which consists of NONCE1 and H1 = MD5(NONCE1 + KEY1)
  3. Lock checks if H1 = MD5(NONCE1 + KEY1)

This part does not prove anything to anyone, so it is useless. An attacker who impersonates the key can reuse any previous nonce+MD5-pair because the lock does not know if the nonce is unique. An attacker who impersonates the lock can simply ignore the data received.

  1. Lock generates completely unique value that never repeats, let's call it "NONCE2".
  2. Lock sends a response to the key which consists of H2 = MD5(NONCE2 + KEY2)

Why not simply send NONCE2 to use as H2? The hash does not seem to help in any way, because the nonce is not used for anything else.

  1. Key does H3 = MD5(H2 + KEY3) and sends it back to the lock
  2. Lock checks if H3 = MD5(H2 + KEY3) and acts on that

This is the only part of the protocol that has a clear purpose: the lock is verifying an ad-hoc MAC to authenticate the key.

Improve this answer
$\endgroup$
10
  • $\begingroup$ 1, 2, 3 - attacker who impersonates the key, won't be able to generate proper request (since he doesn't know KEY1). here is important part that I've not mentioned, lock knows last value of NONCE1 of the key (because NONCE1 - is simple counter which increments everytime when the key sends out it's request). $\endgroup$
    – Ruslan
    Jan 29, 2016 at 10:36
  • $\begingroup$ Missing step is: 3.5 Lock checks if NONCE1 (key counter) > than LOCK_COUNTER, in order to prevent attack using previous nonce+MD5-pair (that has already been used in the past) and increments it's own LOCK_COUNTER accordingly. 4, 5 - "Why not simply send NONCE2 to use as H2?" because NONCE2 is also counter - based, so MD5(NONCE2 + KEY2) hides the details from attacker (otherwise he can try to send NONCE2 + 1 to the key in order to generate valid answer to the next challenge) $\endgroup$
    – Ruslan
    Jan 29, 2016 at 10:37
  • $\begingroup$ > However, I do not think the weaknesses actually apply here, since the attacker would need to calculate the keyed hash for a value chosen by the lock. So unless I miss some attack, the last three steps of the protocol should suffice for authentication. That is what I was aiming for, so first improvement would be to replace MD5 with HMAC-MD5. $\endgroup$
    – Ruslan
    Jan 29, 2016 at 10:37
  • $\begingroup$ @Ruslan, if your NONCE1 is a counter that is checked, then that part correctly authenticates the key, so what is the rest of the protocol for? If the idea is to prevent an attacker first impersonating a server and then a key, you need to define when the counters are incremented and what happens if the key and lock have their counters out of sync. Otherwise it may be possible to man-in-the-middle an authentication attempt but stop it at the last step, then use those results later. I would just use a mutual authentication protocol, like the third scheme in the HAC section I pointed to. $\endgroup$
    – otus
    Jan 29, 2016 at 11:11
  • $\begingroup$ Rest of the protocol is for preventing an attack when an attacker catches requests generated by the key and in the mean time prevents lock from receiving them (blocks it's receiving channel). If I would implement it without steps 4 - 7, then an attacker can later on replay accumulated codes and send them to the lock, which in this case won't see any difference between real key and attacker's key. Key increments it's counter as soon as it woke up (button is pressed), lock sets it's own LOCK_COUNTER = NONCE1 after checking that NONCE1 > than LOCK_COUNTER . $\endgroup$
    – Ruslan
    Jan 29, 2016 at 11:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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