[Babel-users] [babel] Babel MAC auth fails due to packet reordering

[Toke Høiland-Jørgensen]

Juliusz Chroboczek <jch at irif.fr> writes:

>> Ah, I see! Okay, that makes sense. Also, it occurred to me that the
>> window-based approach likely isn't enough when there are multiple
>> neighbours and you do unicast updates, as then another neighbour can eat
>> up a whole chunk of PC number space that you never see.
>
> Exactly.  The sender maintains just one (index, PC) state per interface,
> not one state per destination.  (In constrained environments, you could in
> principle have just one state for all interfaces, although that's not
> allowed by the RFC as it is currently written.)
>
>> However, what about other sources of reordering? Should we still do
>> window-based verification to deal with this?
>
> We might add it as an option to the document you suggest.  I'm not
> currently planning to add it to babeld, but I might change my mind if new
> evidence that it is needed surfaces.  Ok?

OK, sounds reasonable :)

>> Also, I guess this could all be described in a "relaxed PC verification
>> to deal with reordering" document that could be optional to implement
>> (i.e., you could still be compliant with RFC 8967 if you don't implement
>> it)?
>
> I tend to agree, but I'd rather we did the implementation first, to see
> how it goes.

Right, okay. I updated the Bird patch to implement both the separate
ucast/mcast values and the window (patch below). Daniel, could you
please test this in your environment?

>>> Expect on the order of 60 routes per packet. 64 packets gives you on
>>> the order of 3800 routes.
>
>> Right. Which is a lot for a local mesh network, but not a lot for the
>> internet.
>
> OTOH, you should be spreading the updates over the whole length of the
> update interval to avoid sending bursts of packets.  It's been on my todo
> list for babeld for a long time, but I never got around to implementing it.

Yeah, that's on my list of things to do for Bird as well. 

>> Do you have any insights into typical sizes of real-world babel
>> deployments in terms of the number of routes?
>
> Nexedi have around 1000 routers.  I don't know how many routes they're
> advertising in total.

OK, thanks for the data point.

-Toke

Updated patch for Bird (also here:
https://github.com/tohojo/bird/tree/babel-ooo-pc) below:


diff --git a/proto/babel/babel.c b/proto/babel/babel.c
index 4a7d550f5efe..cfd0e0eab7bc 100644
--- a/proto/babel/babel.c
+++ b/proto/babel/babel.c
@@ -1486,7 +1486,8 @@ babel_auth_check_pc(struct babel_iface *ifa, struct babel_msg_auth *msg)
     n->auth_index_len = msg->index_len;
     memcpy(n->auth_index, msg->index, msg->index_len);
 
-    n->auth_pc = msg->pc;
+    n->auth_pc_ucast = n->auth_pc_mcast = msg->pc;
+    n->auth_pc_window_ucast = n->auth_pc_window_mcast = 0;
     n->auth_passed = 1;
 
     return 1;
@@ -1505,18 +1506,85 @@ babel_auth_check_pc(struct babel_iface *ifa, struct babel_msg_auth *msg)
     return 0;
   }
 
-  /* (6) Index matches; only accept if PC is greater than last */
-  if (n->auth_pc >= msg->pc)
+  /* (6) Index matches; only accept if PC is greater than last; we keep separate
+   * counters for unicast and multicast because multicast packets can be delayed
+   * significantly on wireless networks (leading to them being received
+   * out-of-order).
+   */
+  u32 *auth_pc = msg->is_unicast ? &n->auth_pc_ucast : &n->auth_pc_mcast;
+  u64 *auth_pc_window = msg->is_unicast ? &n->auth_pc_window_ucast : &n->auth_pc_window_mcast;
+  const char *cname = msg->is_unicast ? "ucast" : "mcast";
+
+  if (*auth_pc >= msg->pc)
   {
     LOG_PKT_AUTH("Authentication failed for %I on %s - "
-		 "lower packet counter (rcv %u, old %u)",
-                 msg->sender, ifa->ifname, msg->pc, n->auth_pc);
+		 "lower %s packet counter (rcv %u, old %u)",
+                 msg->sender, ifa->ifname, cname,
+                 msg->pc, *auth_pc);
     return 0;
   }
 
-  n->auth_pc = msg->pc;
-  n->auth_passed = 1;
+  /* If the msg PC is larger than the last seen value, use the auth_pc_window to
+   * keep track of which values we've seen; each PC value will only be allowed
+   * once, but PC values arriving out-of-order within the size of the window
+   * will be allowed.
+   *
+   * First, check if if msg PC is more than twice over the replay window, in
+   * which case there's no point in shifting the window, as we'd just shift it
+   * to 0 anyway; so just reset it and exit immediately.
+   */
+  if (msg->pc - *auth_pc > 128) {
+    LOG_PKT_AUTH("Authentication PC (%s) moved past 2x reorder window "
+		 "(rcv %u, window end %u) - resetting window",
+                 msg->sender, ifa->ifname, cname,
+                 msg->pc, *auth_pc + 64);
+
+    *auth_pc = msg->pc;
+    *auth_pc_window = 0;
+    n->auth_passed = 1;
+    return 1;
+  }
+
+  u8 auth_bit = msg->pc - *auth_pc - 1;
+
+  /* Moved past the high end of the window, shift it by the minimum required to
+   * fit this bit (keeping as much of the old window as possible).
+   */
+  if (auth_bit >= 64)
+  {
+    u8 fwd = auth_bit - 63;
+
+    LOG_PKT_AUTH("Authentication PC (%s) moved past reorder window "
+		 "(rcv %u, window end %u) - fast-forwarding window by %u",
+                 msg->sender, ifa->ifname, cname, msg->pc, *auth_pc + 64, fwd);
 
+    *auth_pc += fwd;
+    *auth_pc_window >>= fwd;
+    auth_bit -= fwd;
+  }
+
+  if (*auth_pc_window & (1 << auth_bit))
+  {
+    LOG_PKT_AUTH("Authentication PC (%s) %u already seen "
+                 "(window start %u, value %x)",
+                 msg->sender, ifa->ifname, cname,
+                 msg->pc, *auth_pc + 1, *auth_pc_window);
+    return 0;
+  }
+  *auth_pc_window |= (1 << auth_bit);
+
+  /* If we just closed a whole (or this was the lowest bit), advance the window
+   * to clear any all-one bits at the lower end
+   */
+  u64 auth_bit_mask = (((u64)-1) >> (64 - auth_bit - 1));
+
+  if ((*auth_pc_window & auth_bit_mask) == auth_bit_mask)
+  {
+    *auth_pc_window >>= auth_bit + 1;
+    *auth_pc += auth_bit + 1;
+  }
+
+  n->auth_passed = 1;
   return 1;
 }
 
diff --git a/proto/babel/babel.h b/proto/babel/babel.h
index 84feb085dae7..711b933851d7 100644
--- a/proto/babel/babel.h
+++ b/proto/babel/babel.h
@@ -224,7 +224,10 @@ struct babel_neighbor {
   u16 next_hello_seqno;
   uint last_hello_int;
 
-  u32 auth_pc;
+  u32 auth_pc_ucast;
+  u32 auth_pc_mcast;
+  u64 auth_pc_window_ucast;
+  u64 auth_pc_window_mcast;
   u8 auth_passed;
   u8 auth_index_len;
   u8 auth_index[BABEL_AUTH_INDEX_LEN];
@@ -403,6 +406,7 @@ struct babel_msg_auth {
   u8 challenge_seen;
   u8 challenge_len;
   u8 challenge[BABEL_AUTH_MAX_NONCE_LEN];
+  u8 is_unicast;
 };
 
 static inline int babel_sadr_enabled(struct babel_proto *p)
diff --git a/proto/babel/packets.c b/proto/babel/packets.c
index 2647a79f1baf..a94bba4c1bb2 100644
--- a/proto/babel/packets.c
+++ b/proto/babel/packets.c
@@ -1656,6 +1656,7 @@ babel_read_pc(struct babel_tlv *hdr, union babel_msg *m UNUSED,
   state->auth.pc_seen = 1;
   state->auth.index_len = index_len;
   state->auth.index = tlv->index;
+  state->auth.is_unicast = state->is_unicast;
   state->current_tlv_endpos += index_len;
 
   return PARSE_SUCCESS;