Subject: [babel] HMAC routerid->key mappings?

From: Dave Taht <[email-masked]>
Date: Sat, 1 Dec 2018 11:52:43 -0800

in reading over and attempting to deploy the hmac specification, I
think the code, at least, currently misses an optimization, and
perhaps the spec needs a tweak...

as keys (currently) protect each interface, not each router association...

It protects a single domain from (some) internal attacks.
It protects a p2p interchange

consider, instead a case where you are dropping a bunch of networks
into an information interchange (call it "BIX"[1]), where a bunch of
networks have agreed to interconnect, over a single "wire", much like
how BGP network interchanges work today. Key exchange here, in the BGP
world, is on a per-router, not per-interface, basis.

Net  A Net B Net C Net D Net E
   |           |       |         |          |
------------------------------------------
  |        |       |       |          |
 F        G     H    I          J

As per the spec:

"When a node A receives a
   packet over an interface that requires cryptographic protection, it
   independently computes a set of HMACs and compares them to the HMACs
   appended to the packet; if there is no match, the packet is
   discarded."

It is unwise to share one key with all interchangers. Co-ordinating a
key rollover with that many different entities on that wire is hard.

Using specific keys instead for each of the A-F, A-G, A-B, etc,
associations limits the geometric growth and security vulnerabilities.

A) while we can append quite a few HMACs in a hello, at some point,
when an interchange's hmacs grows past the size of a packet, we run
out of space. What happens? Can we resend that hello with even more
HMAC's attached, and win?

B) As an optimization, unicast transfers can just be hmac'd with the
keys defined for that routerid association.

So if the code (in addition to protecting interfaces) could also (or
instead of interfaces) associate keys to routerids, we scale to this
scenario.

Alternatively we could just say:

1) Use BGP instead at large interchanges
2) Use DTLS
3) Use a minimal number for all associations on an interface scaled to
the max size of hello + ihu + hmacs

[1] I have fond memories of the original BIX from byte magazine

-- 

Dave Täht
CTO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-831-205-9740

---

From: Juliusz Chroboczek <[email-masked]>
Date: Sat, 01 Dec 2018 21:34:55 +0100

> as keys (currently) protect each interface, not each router association...

Correct.  Babel uses both unicast and multicast, and Babel-HMAC is
designed so that it can protect multicast traffic while remaining immune
to replay, even in the absence of persistent state or hardware clocks.

> world, is on a per-router, not per-interface, basis.

BGP is a unicast-only protocol, hence it can easily use per-peer keys.

> associations limits the geometric growth and security vulnerabilities.

The clean solution would be to use a bunch of point-to-point interfaces,
either by replacing your switch with direct router-to-router links, or by
putting up a bunch of VLANs or GRE tunnels.  Then you can use Babel-HMAC
unmodified.

> HMAC's attached, and win?

Sort of.  However, if there are any plaintext routers on the same link,
they will parse both packets.  I think that Babel should deal fairly well
with packet duplication, but I'm not sure.

But at that point, you might as well use DTLS.

> instead of interfaces) associate keys to routerids, we scale to this

I'm not going to do that, unless there are any good reasons why you don't
want to use DTLS in that case.

> 1) Use BGP instead at large interchanges

Yep.  If your routing tables are relatively stable, BGP is the right choice.

> 2) Use DTLS

Yep.  It supports per-peer keying out of the box.

> the max size of hello + ihu + hmacs

Not so keen on that -- while the protocol does in principle support
multiple HMACs, both the amount of overhead and the amount of computation
go up linearly with the number of HMACs.  It's really not designed for that.

Of course, you could envision using the unicast variant of the protocol
(the one that rejects all multicast packets except Hellos) and protect
unicast packets with HMAC instead of DTLS.  But at that point, you might
just as well use DTLS.

Quite frankly -- just use DTLS, or run HMAC over point-to-point links.

-- Juliusz

---

From: Dave Taht <[email-masked]>
Date: Sat, 1 Dec 2018 16:42:32 -0800

> either by replacing your switch with direct router-to-router links, or by

Would be a rather big switch to replace, so, no, not in this model...

> putting up a bunch of VLANs or GRE tunnels.  Then you can use Babel-HMAC

Well, an even cleaner solution for that wire would be to be using one
veth per link (or in the case of vms,
dockers, snaps, etc, the virtual interface they present), bridged to
the wire, which is a common deployment model. A vm
is often migrated between machines, and it would just pick up in one
place and resume in another.

Incidentally, "multiple vms bridged to a wire" was my mental model for
setting up a bunch of vms to test interop, simulating various
conditions. I have a standard veth model for simulating delay and
multiple routers for the wifi work also (using namespaces).

Anyway:

The "one interface per key" rule adds complexity but I think it also
brings benefits by requiring such. In such an environment
you'd want to rate limit and observe how much bandwidth is being used
for each interconnect anyway.

Other stats and abstractions fall out of it.

In the case of bridging veths like this, we'd still end up with mcast
hellos hitting the wire, but using unicast
then for everything else, and I'd judge hmacing and discarding those
extra hellos as pretty cheap, although noisy in the log file.

About the only issue I see for an interchange like this is that you'd
also need one ipv4 address per veth, which are kind of scarce.

unless there was a way to do the obscure extended nexthop idea in
https://tools.ietf.org/rfc/rfc5549.txt in babel and linux?

https://www.oreilly.com/library/view/bgp-in-the/9781491983416/ch04.html
goes into it. It makes my brain hurt.

> they will parse both packets.

Definitely would not allow any plaintext routers on that wire.

>  I think that Babel should deal fairly well

Yea! More things for me to try blowing up!

Has anyone here ever futzed with a fuzzer, btw? This looks good:
http://lcamtuf.coredump.cx/afl/

> But at that point, you might as well use DTLS.

Heh. I would like hmac to stabilize first.

> want to use DTLS in that case.

Look forward to trying it.

> Yep.  If your routing tables are relatively stable, BGP is the right choice.

There are many, many, reasons to not want to use another routing
protocol as complicated and difficult to use and configure as BGP in
any scenario smaller than the global scale internet. There's also
source specific routing, which I think is still problematic in any BGP
protocol? I see ISIS in FRR has got it now.

> Yep.  It supports per-peer keying out of the box.

K.

> go up linearly with the number of HMACs.  It's really not designed for that.

The HMAC benchmarks were promising yesterday. (compared to DTLS!!!!???? )

I guess my mental model about key rollover was pretty different -
where everyone was assuming at most 2 keys, I
was assuming potentially many and key rollovers taking weeks. "dang, I
really need to ask joe to retire that old key, and when does mary get
back from vacation?"

The optimization I had in mind was to enthusiastically sign hellos
with every active key you have, but only sign unicast with the keys
you know are working.

> unicast packets with HMAC instead of DTLS.

That is what works, theoretically, right now, with the existing codebase.

>  But at that point, you might
> just as well use DTLS.
>

-- 

Dave Täht
CTO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-831-205-9740

---

From: Juliusz Chroboczek <[email-masked]>
Date: Sun, 02 Dec 2018 02:52:12 +0100

> brings benefits by requiring such.

It's conceptually elegant and easy to explain.  These are good features to have.

> https://tools.ietf.org/rfc/rfc5549.txt in babel and linux?

Babel (at least babeld, don't know about BIRD) should deal fine with
Linux-style unnumbered links (which are different from Cisco-style
unnumbered links).

In the Linux style, you put the same IPv4 address on multiple links:

  ip addr add 192.0.2.1/32 dev eth0
  ip addr add 192.0.2.1/32 dev eth1
  ip addr add 192.0.2.1/32 dev wlan0

Now you run babeld on all interfaces, and everything should just work --
look, Ma, just one IPv4 address per host.

(In Cisco style, you put your IPv4 address on the loopback interface, and
the other interfaces magically borrow the loopback's IPv4 address.  I find
the Linux style easier to comprehend, but perhaps that's just me.)

-- Juliusz