Subject: [babel] A few observations about HMAC authentication

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 12 Jun 2018 19:31:46 +0200

Clara and Weronika have made good progress today -- we've got roughly the
functionality of 7298 (modulo some minor bugs) plus the pseudo-header.

1. Original Babel is fairly robust against packet reordering.  This is no
   longer the case with HMAC authentication, where any reordered packets
   will be dropped due to TS/PC mis-ordering.

2. We don't understand why TS/PC are two integers.  As far as the protocol
   is concerned, TS/PC is just a 48-bit string ordered lexicographically.
   Have we missed something?

3. I'm still not convinced we want a keyID.  Please convince me either way.

We'll keep youse updated,

-- Juliusz

---

From: Markus Stenberg <[email-masked]>
Date: Tue, 12 Jun 2018 20:40:29 +0300

>   will be dropped due to TS/PC mis-ordering.

Considering there is no guarantee of packet ordering in general, you would really want something more like IPsec replay window (i.o.w. most recent N remembered as bits ’seen this, not that’) than just plain increasing order-or-die. 

That said, I am not sure how much of reordering would you get on link-local anyway, the reordering is more of an issue on longer routes.

> 3. I'm still not convinced we want a keyID.  Please convince me either way.

Well, it is tradeoff between 2 options:

- flag day update of network configuration which isn’t really an option (I know for a fact that key rotation is required in A LOT of places these days as a matter of course)

- attempting ‘few’ keys to see if hash matches one of them 

The procedure is basically

1. one key rules!
2. gradually roll out configurations with both ‘the one key’ and new key accepted while all send old one, then
3. update all configurations just to send new one, and
4. yet once more update configurations to get rid of old one.

during [2/3] you would have to essentially accept both keys to avoid flag day.

There are arguably also other configurations, where you have overlapping domains with some parts of it using different keys, but I am not going to tinfoil hat land here; the above is a scenario I have seen in action ‘enough’.

Anyway, from my point of view, just one hash + no key id is fine, if we don’t try to make the hash actually hard to brute force. If we do that, then trying two keys might be prohibitively expensive but then again, it would be too easy to DoS too.

Cheers,

-Markus

---

From: David Schinazi <[email-masked]>
Date: Tue, 12 Jun 2018 11:06:52 -0700

> On Jun 12, 2018, at 10:40, Markus Stenberg <[email-masked]> wrote:
> 

Has the Babel community observed reordering of Babel packets? Is this on local networks or overlays only?
If reordering does happen, I agree with the replay window solution.

>>  Have we missed something?

I'm equally confused, I'm assuming having the standard only define one string ordered lexicographically would be easier to implement - and therefore safer.

> There are arguably also other configurations, where you have overlapping domains with some parts of it using different keys, but I am not going to tinfoil hat land here; the above is a scenario I h…

I think the tradeoff is
1) with keyID
	- bad: you have to send two bytes of keyID per hash
	- good: you only need to try one key when receiving a hash: O(1)
2) without keyID
	- bad: you have to try as many hashes as keys you know: O(n), that opens up DoS
	- good: you save two bytes for each hash sent over the wire

I'd prefer to spend the two bytes to minimize CPU utilization and DoS risk.

> Anyway, from my point of view, just one hash + no key id is fine, if we don’t try to make the hash actually hard to brute force. If we do that, then trying two keys might be prohibitively expensive…

Unless I'm missing something, having a reasonable hash function (SHA2-256) and a large-enough key (256bits) is enough to prevent brute-forcing without the need to perform multiple rounds of hashing.

David

---

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 12 Jun 2018 22:34:34 +0200

>> That said, I am not sure how much of reordering would you get on
>> link-local anyway, the reordering is more of an issue on longer routes.

Agreed.  I think we're going to implement with no reordering allowed, but
the spec should be flexible enough to allow a reordering window.  I'll be
grateful for help with this.

>> - flag day update of network configuration which isn’t really an option
>>   (I know for a fact that key rotation is required in A LOT of places
>>   these days as a matter of course)

I think there's consensus that we want to support key rotation -- carrying
multiple HMACs for a single packet will be allowed in either case.  The
question is whether the HMACs are decorated with a Key ID -- in Denis'
draft, there's an explicit Key ID, so you only check the HMACs that
correspond to keys you already know.  In our implementation, there's no
Key ID, so you have to check all HMACs before you decide whether any match.

> 	- good: you only need to try one key when receiving a hash: O(1)

The main issue is one of manageability.  With no Key ID, before doing key
rotation, you just deploy the new key -- nothing to worry about except the
hash function and the key.  With a Key ID, you need to find an unused Key
ID and ensure you deploy with the same Key ID to all routers.

> 	- bad: you have to try as many hashes as keys you know: O(n), that

I don't see that.  The "n" in O(n) is the number of keys you already know
(normally just 1 or 2), so it's not controlled by the attacker.

The procedure is simply:

  - compute HMAC(packet, key) for all keys known to you;
  - compare the result with each of the HMAC TLVs in the received packet.

It can be optimised somewhat with a Key ID, but not much, unless you've
got dozens of keys deployed simultaneously.

-- Juliusz