Subject: [babel] Solving HMAC replay once and for all

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 27 Jun 2018 14:39:27 +0200

Dear all,

I think I've just solved the replay problem in a provably correct manner.
I've run the protocol through Clara and Weronika, and they didn't object,
please double-check.

HMAC is left unchanged -- all packets are protected by HMAC, and a packet
is immediately dropped if the HMAC check fails.

The main idea is that we now have two nonces -- the sender's nonce and the
receiver's nonce.  The sender's nonce is chosen by the sender, is the same
for all receivers, and is sent in each packet.  The receiver's nonce is
per receiver-sender pair, and is only used in a challenge.

Replay protection is achieved by drawing a new sender's nonce whenever the
sender cannot guarantee monotonicity of the packet counter.

Packet format
=============

Packet counter
--------------

Instead of TS/PC, we have a simple packet counter that can be reset at any
time; it carries the sender's nonce:

     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |   Type = TBD  |    Length     |               PC
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                                    |     Sender's Nonce...
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

The packet counter is a simple per-interface counter, it starts at 0 and
is incremented every time a packet is sent (unicast or multicast).
Whenever the sender resets the counter (either because it is restarted or
because the packet counter overflows), it generates a new, unique Sender's
Nonce.

As suggested by David, the Sender's Nonce is of arbitrary length (up to
251 octets).

Challenge and challenge reply
-----------------------------

A challenge contains the receiver's nonce.  The challenge reply contains
an echo of the receiver's nonce.  We haven't decided the exact format
yet -- should it be a separate TLV, a sub-TLV of Hello/IHU, or a sub-TLV
of Ack Request and Ack Reply.  As suggested by David, the Receiver's Nonce
is of arbitrary length (up to 255 octets, eek, inconsistend with the
Sender's Nonce.).

Protocol operation
==================

Bob is the sender.  When he boots, he picks a sufficiently large Sender's
Nonce for each interface, and initialises its per-interface packet counter
to 0.  Whenever he sends a packet, he includes a PC TLV with the
interface's packet counter and nonce, protects the packet with HMAC, and
ships it out.

Alice is the receiver.  She maintains a per-neighbour table of
(sender's nonce, PC).  When she receives a packet from Bob:

  - if there's no information about Bob, she drops Bob's packet and sends
    a challenge;
  - if there's information about Bob, the Sender's Nonces match and the PC
    is strictly increasing, the packet is accepted;
  - if there's information about Bob, and either the Nonces mismatch or
    the PC has decreased, she drops the packet and sends a challenge.

Protocol properties
===================

We haven't worked on the proof yet, but I'm confident that the protocol is
provably invulnerable to replay.  There's one obvious property:

  Property 1: a given Nonce/PC pair is never reused

This is due to Bob generating a new Nonce whenever he cannot guarantee
strict monotonicity of the PC.

Implementability
================

Implementation is simpler for a reason: both the sender and the receiver
can force a challenge at any time; thus, the sender may lose its Packet
Counter and the receiver may lose its per-peer counter, and the cost is
just one extra challenge.

Consequences:

  - there is no need for a persistent packet counter or a hardware clock;
  - there is no need for a persistent ANM;
  - the use of an ANM becomes optional -- a simple implementation may
    choose to keep the per-peer packet counter in the Neighbour Table, at
    the cost of an extra challenge at each mobility event.

The only requirement is a cryptographic PRNG, which is something we may
reasonably assume to be present even in small routers.

Does that sound like a plan?

-- Juliusz

---

From: Markus Stenberg <[email-masked]>
Date: Wed, 27 Jun 2018 15:49:41 +0300

I thought this is what I tried to describe but apparently not in enough detail (nonce = receiver’s nonce, mynonce = sender’s nonce). 

Anyway, you don’t really need to send either of the nonces except in challenges, if you use them in pseudoheader otherwise. If hmac fails due to wrong nonce in pseudoheader, you can do challenge (or not, for DoS protection).

> reasonably assume to be present even in small routers.

_or_ semi-working RTC.

-Markus

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 27 Jun 2018 15:11:10 +0200

> I thought this is what I tried to describe but apparently not in enough
> detail (nonce = receiver’s nonce, mynonce = sender’s nonce).

So either your mail worked on my unconscious, or great minds meet ;-)
Sorry for not realising that earlier.

> Anyway, you don’t really need to send either of the nonces except in
> challenges, if you use them in pseudoheader otherwise. If hmac fails due
> to wrong nonce in pseudoheader, you can do challenge (or not, for DoS
> protection).

Interesting idea.  How do you suggest we decide when to challenge?

> _or_ semi-working RTC.

Uh-huh.  (The nonces don't need to be truly random, just never reused.)

-- Juliusz

---

From: Markus Stenberg <[email-masked]>
Date: Wed, 27 Jun 2018 16:28:21 +0300

> Sorry for not realising that earlier.

No prob, as I said, sick so not neccessarily too lucid emails.

> Interesting idea.  How do you suggest we decide when to challenge?

If hmac fails (and we feel we’re not participating in a DoS by doing it too often). The sender nonce should be part of hmac in the pseudoheader. If it changes, challenge is warranted.

-Markus

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 27 Jun 2018 16:05:20 +0200

> No prob, as I said, sick so not neccessarily too lucid emails.

It was obviously your idea, I just didn't understand it at the time, it
clicked during the night.  Full credit where credit is due.

>>> to wrong nonce in pseudoheader, you can do challenge (or not, for DoS

We've spoken among ourselves, and we're agreed -- we'll do that.

> If hmac fails (and we feel we’re not participating in a DoS by doing it
> too often). The sender nonce should be part of hmac in the
> pseudoheader. If it changes, challenge is warranted.

So challenge on failed HMAC, with rate limiting?  That's definitely doable.

Please let us know if you have any further suggestions.

-- Juliusz

---

From: David Schinazi <[email-masked]>
Date: Wed, 27 Jun 2018 10:10:26 -0700

I'm that sure this addresses my earlier concern.

Let's say Alice and Bob are brand new routers and join the network for the first time.

>  - if there's no information about Bob, she drops Bob's packet and sends

- Bob sends Hello
- Alice has no information about Bob, Alice drops Bob's Hello and sends a Challenge
- Bob doesn't have information about Alice, so Bob drops Alice's challenge instead of responding.

How do they get into a state where they accept the challenge?
I feel I'm missing something here, can someone walk me through it?

Also, my first instinct is to be against the nonce in pseudo-header, because that requires us
to challenge on failed HMAC, which means an attacker can now cause DoS traffic without even
needing to have observed packets to replay.

Anyway, I haven't had my morning coffee yet so I might be confused.

David

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Wed, 27 Jun 2018 23:19:01 +0200

> I feel I'm missing something here, can someone walk me through it?

Presumably the challenge TLV will need to be the only TLV in that packet
(or, depending on the encoding, that packet will only contain
HMAC-related TLVs), in which case it can be treated as a distinct case
and challenges can be replied to (as long as the HMAC is valid).

> Also, my first instinct is to be against the nonce in pseudo-header,
> because that requires us to challenge on failed HMAC, which means an
> attacker can now cause DoS traffic without even needing to have
> observed packets to replay.

I don't think raising the bar for DoS to 'has to sniff a packet off the
network' is really worth putting a lot of effort into. If we are going
to protect against DoS, we need another mechanism anyway, such as the
rate limiting Juliusz and Markus was discussing.

> Anyway, I haven't had my morning coffee yet so I might be confused.

Emailing before coffee? How very brave of you ;)

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 27 Jun 2018 23:35:30 +0200

>   challenge instead of responding.

Noted.  We'll think some more.  (Toke, just because I'm not answering
doesn't mean we're not listening.)

> attacker can now cause DoS traffic without even needing to have observed
> packets to replay.

The DoS attack is pretty trivial in either case -- you just need to
capture one packet and wait until its PC becomes obsolete.  I'm not sure
you're gaining much by encoding the nonce explicitly, I'd like to know why
you think otherwise.

-- Juliusz

---

From: David Schinazi <[email-masked]>
Date: Wed, 27 Jun 2018 15:05:15 -0700

> On Jun 27, 2018, at 14:35, Juliusz Chroboczek <[email-masked]> wrote:
> 

I agree with Toke's approach - having a separate TLV with different semantics
solves the problem.

> you're gaining much by encoding the nonce explicitly, I'd like to know why

Basically this breaks the property that "any packet without a valid HMAC is
silently ignored" and that worries me, as it was a good property to have.
Having some data be implicit in the pseudo header can cause issues
when peers get out of sync. Whereas an explicit signal allows us to more
easily detect problems and send challenges to resync.

Note that if my understanding is correct, having a separate TLV for challenges
with separate semantics solves all of these problems at once without adding
the overhead of a nonce in each packet.

David

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 28 Jun 2018 00:17:54 +0200

> silently ignored" and that worries me, as it was a good property to have.

Good point, noted.

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 28 Jun 2018 00:20:57 +0200

> Good point, noted.

So:

  Property D: a packet is silently ignored after an HMAC failure,

and

  Property M: nonces are not carried in every packet.

are both good properties to have.  Can we have both?

-- Juliusz

---

From: David Schinazi <[email-masked]>
Date: Wed, 27 Jun 2018 16:16:48 -0700

> On Jun 27, 2018, at 15:20, Juliusz Chroboczek <[email-masked]> wrote:
> 

I think so, yes. Straw man proposal:

We add two new TLVs: ChallengeRequest and ChallengeResponse, which MUST be sent unicast.
Those TLVs are allowed to be parsed if the HMAC validates but the counter does not.

Alice is the receiver. Alice maintains a per-neighbour table of counters.
When Alice receives a packet from Bob:
- if HMAC does not validate, Alice drops bob's packet silently
- else if Alice has counter information about Bob, and the counter is in [savedCounter + 1, savedCounter + 256], the packet is accepted and Alice sets savedCounter(Bob) to the counter from the packet;
- else (Alice has no counter information about Bob or Alice has counter information about Bob and the counter is outside of that range), Alice parses Challenge TLVs, silently ignores any non-Challenge TLVs in Bob's packet and sends a challenge (with rate limiting)

Only the challenges contain an arbitrary-length opaque nonce.

The counter should be 48 or 64 bytes long.
- Devices who believe they have reliable monotonically increasing clocks can use their time as a counter
- Devices that can save their counter to disk start at zero and increase for each packet send
- Devices that have neither start off with a random counter then increment by one for the duration of this boot. The security for those devices depends on how much entropy they have in the high order bits of their initial random counter value.

This proposal has Properties D and M, and also

Property S: if Alice and Bob do not have clocks or storage and they reboot at the same time, they are still secure as long as there are enough bits of entropy in the high order bits of their initial counters to ensure that those won't intersect with values they previously chose.

Property R: If something goes wrong (reliable clocks aren't, etc.) devices are able to reestablish communication after 1RTT

Conceptually this is similar to treating the high order bits of the counter as a nonce in cases where you do not have a clock or storage. So I guess for those devices property M is somewhat not quite guaranteed-ish...

Also, to handle reordering we can have a replay window similar to IPsec/ESP where Alice keeps a bit mask of packets received in [savedCounter - 256, savedCounter - 1] to allow receiving out of order packets in that range.

David

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 28 Jun 2018 01:26:49 +0200

> I think so, yes. Straw man proposal:

[...]

> Conceptually this is similar to treating the high order bits of the
> counter as a nonce in cases where you do not have a clock or storage.

I think you're carrying a nonce in every packet (thus violating property
M), just hiding it in the upper bits of the packet counter.  In short,
it's the protocol I suggested this morning, just with a more obfuscated
encoding.

Or am I missing something?

---

From: David Schinazi <[email-masked]>
Date: Wed, 27 Jun 2018 16:34:35 -0700

> On Jun 27, 2018, at 16:26, Juliusz Chroboczek <[email-masked]> wrote:
> 

The key difference is that it's more versatile. Only devices that do not
have clocks or storage treat it as a nonce. It gives better security
properties to devices with clocks or storage because those devices
do not have their security depend on a randomly generated number
being unique.

David

---

From: David Schinazi <[email-masked]>
Date: Wed, 27 Jun 2018 16:40:16 -0700

Also the proposal differentiates between the challenge nonce
(which will be >= 128 bits) and the per-packet "nonce" that's a lot shorter.
This allows us to send fewer bytes on the wire per packet.

David

> On Jun 27, 2018, at 16:34, David Schinazi <[email-masked]> wrote:
> 
> 
> 
> _______________________________________________
> babel mailing list
> [email-masked] <mailto:[email-masked]>
> https://www.ietf.org/mailman/listinfo/babel <https://www.ietf.org/mailman/listinfo/babel>

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Thu, 28 Jun 2018 01:52:12 +0200

>   Property D: a packet is silently ignored after an HMAC failure,

BTW, if we specify this, should we also specify a 'debug mode' in which
an implementation MUST COMPLAIN LOUDLY if an HMAC fails? Not everyone
has the luxury of recompiling their babel daemon with debugging enabled,
and while silently ignoring packets may be good for security, it makes
debugging... interesting...

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 28 Jun 2018 02:02:55 +0200

David Schinazi writes:

>     have clocks or storage treat it as a nonce.

In the Stenberg-Chroboczek proposal, devices that have a reliable clock
and don't fear overflowing the PC space could in principle use a nonce of
length 0.  (That's not recommended, but a device can reasonably use
a 16-bit overflow count as a nonce.)

> Also the proposal differentiates between the challenge nonce (which will
> be >= 128 bits) and the per-packet "nonce" that's a lot shorter.  This
> allows us to send fewer bytes on the wire per packet.

Same with the Stenberg-Chroboczek proposal -- the nonces are variable
size, and implementations can use a short sender's nonce and a long
receiver's nonce.

I'll sleep over it, but I really feel like your proposal is just a less
explicit reencoding of Stenberg-Chroboczek.

-- Juliusz

---

From: David Schinazi <[email-masked]>
Date: Wed, 27 Jun 2018 18:09:26 -0700

I just reread your proposal and I think I agree with you.
If I'm getting this right, my proposal maps to yours with
- nonce = receiver's nonce
- counter = PC and sender's nonce
But I do think in this case less explicit is better. We could give the counter an
arbitrary length selected by the sender and get the best of all worlds here.

Also, since I'm feeling pedantic, a nonce is a number only used once
so your sender's nonce is not technically a nonce and needs to be renamed :)

So apart from naming of things we are in agreement.

David

> On Jun 27, 2018, at 17:02, Juliusz Chroboczek <[email-masked]> wrote:
> 
> David Schinazi writes:
> 
> [email-masked]
> https://www.ietf.org/mailman/listinfo/babel

---

From: Markus Stenberg <[email-masked]>
Date: Thu, 28 Jun 2018 07:18:41 +0300

> On 28.06.2018, at 4.09, David Schinazi <[email-masked]> wrote:

Well if it's transmitted only once (in challenge-response if we choose the not-on-wire property) and used later just as hmac parameter I am not sure I agree with you.

Plenty of protocols do e.g. key derivation based on nonces or establish session in some other way using them. Admittedly here the scheme is bit more interlinked perhaps (as the actual value and not derived key has to be retained).

Do you have a better suggestion? Technically it is some sort of per-boot (or per-router-daemon-lifetime) token.

-Markus

---

From: Markus Stenberg <[email-masked]>
Date: Thu, 28 Jun 2018 07:23:36 +0300

> On 28.06.2018, at 2.16, David Schinazi <[email-masked]> wrote:

I wonder if packet reordering is something we should really incorporate to this design or not.

Typically on one link it does not happen, but if you e.g. have some wireless lower layer with unreliable multicast and 'reliable' unicast, it would be possible to have reordering occur here between unicast and multicast (as seen by receiver). 

I guess also given some sort of bit 'larger' lower layer network (hello ethernet+ISIS) it is possible for packets to use different paths and show up in different order.. Not maybe target domain for Babel but still.

Now that I think more of it, I think ordered delivery is a likely property but not always present one even for stuff that seems like one IP layer link.

-Markus

---

From: Markus Stenberg <[email-masked]>
Date: Thu, 28 Jun 2018 11:51:35 +0300

> Now that I think more of it, I think ordered delivery is a likely property but not always present one even for stuff that seems like one IP layer link.

(Even more thought, bear with me) With that said, noting some replay window semantics are probably useful to mention in the text, but the window size should be left to the implementor. With that, if size=1, the window disappears, so essentially mechanism is implementation-only optional one.

(I think it just leads to some ‘packet loss’ if we get stuff outside replay window, so it is fine; the challenge-response should be probably triggered if and only if no valid stuff has been received for X from the node..)

-Markus

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 28 Jun 2018 11:44:54 +0200

> (I think it just leads to some ‘packet loss’ if we get stuff outside
> replay window, so it is fine; the challenge-response should be probably
> triggered if and only if no valid stuff has been received for X from the
> node..)

Challenge on nonce change only, not on out-of-order PC?

---

From: Markus Stenberg <[email-masked]>
Date: Thu, 28 Jun 2018 13:01:35 +0300

> Challenge on nonce change only, not on out-of-order PC?

I think there is a tradeoff between DoS resistance (no spurious challenges) and fast recovery from sender state loss. There seems to be plenty of design decisions to be made here though, and only based on them sensible choices can be made, but for the time being I am leaning towards the former, so I’d say challenge should be sent iff:

- no sender nonce for node (duh; new node), _or_
- no valid hmac (with valid sender nonce) received over time period of (IHU interval * something)

The messages with counter outside replay window (if used at all) would be just ignored if replay window is not used. 

e.g. sender reboots -> with this scheme, it would only recover with timeout and that’s bit icky as well.. on the other hand, node reboots probably take normally some time as well so I am not sure it is really as bad as one could think on first estimation. Key rotation or intentional counter reset/roll-over might need further thought though..

-Markus

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 28 Jun 2018 12:17:08 +0200

>   (IHU interval * something)

As you note later in your message, we want to allow the sender to rekey at
any time without delay (e.g. because it has just rebooted).  So I'd say
challenge when:

  - no state for sender; or
  - no challenge in the last T seconds AND nonce has changed.

This allows rekeying with no delay, but no more than once every T.  Two
questions:

  - what's the right value for T (Markus suggests deriving from IHU);
  - should we challenge when we see old PC, and if so, how do we avoid
    getting confused in case of packet reordering?

> The messages with counter outside replay window (if used at all) would
> be just ignored if replay window is not used.

Yep.

-- Juliusz

---

From: Markus Stenberg <[email-masked]>
Date: Thu, 28 Jun 2018 13:44:11 +0300

>  - no challenge in the last T seconds AND nonce has changed.

This requires nonce to be on the wire though? I was opting on not having one and have it just be in pseudoheader (one of the design choices).

Otherwise it is impossible to distinguish between hmac failure and (implicit) nonce failure?

>    getting confused in case of packet reordering?

I would prefer not to.

So it actually boils down to getting 2 out of 3:

(1) fast reboot reaction
(2) (minor) DoS resistance
(3) no ’sender nonce' in non-challenge packets

I am personally keen to have (3), (1) and (2) I am more or less ambivalent about, both are nice to have but just hmac-based spurious challenge-responces (in (2)) are not end of the world, and typically routers boot slower than timeouts involved so (1) is probably not an issue either. (.. or they can use random router ids if they really care ..)

Cheers,

-Markus

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 28 Jun 2018 13:15:31 +0200

> This requires nonce to be on the wire though? I was opting on not having
> one and have it just be in pseudoheader (one of the design choices).

Yes, that's what I'm considering right now, since I really like the
property that a spoofed packet (HMAC failure) is dropped right away, it
reduces the attack surface and makes it easier to review the code.
I haven't spoken with Clara and Weronika yet, though, and they might
convince me otherwise.

To put it differently -- what we're trying to do here is to design
a protocol that is simple to implement safely (i.e. that can be
implemented by a reasonably competent fourth year student).  Dropping
packets with bad HMAC early means that you only need to review for parser
vulnerabilities the code that deals with HMAC.

> I am personally keen to have (3),

I'd like to have (3) if it is compatible with the property above.  I'll
rather drop (3) than the property above, unless one of youse convinces me
otherwise.

I do care about (1), since it allows frequent rekeying without any
protocol changes (which might turn out handy if we wish to mitigate
a vulnerability we find in the future).  I don't care about (2), it's
a red herring, since we'll need to do rate limiting in any case.

(Sorry for the length of this message, I didn't have time to make it shorter.)

-- Juliusz

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Thu, 28 Jun 2018 13:20:47 +0200

Juliusz Chroboczek <[email-masked]> writes:

> Dropping packets with bad HMAC early means that you only need to
> review for parser vulnerabilities the code that deals with HMAC.

The implicit assumption here being that if someone knows the HMAC key
they are going to 'be nice', and not try to crack your parser? Is that
really a safe assumption if one wants to build a robust parser? :)

-Toke

---

From: Markus Stenberg <[email-masked]>
Date: Thu, 28 Jun 2018 14:29:37 +0300

> really a safe assumption if one wants to build a robust parser? :)

I think that is bit of an optimistic view as well. While in idealistic OSImodel++ world one would have security in a separate (simple) layer, in real world that does not occur in my experience.

So responding to Juliusz’s comment on (2) being a red herring (I agree but also think (1) is one as well), if we go for (1) and (3), the algorithm turns out to be: challenge iff:

- global/per-peer challenge rate limit not exceeded _AND_

  - no state for sender _OR_
  - HMAC error

I do not think it makes the implementation much harder; we need pseudoheader anyway, and it seems we need challenges, and if those are present, sending sender nonce in every packet seems wasteful to me.

The normal packet reception flow just:
-  computes pseudoheader, hashes that + what was received, and compares it with the trailer HMAC. 
- If success, compare counter, 
  - if too old (modulo replay window if any), drop, otherwise process normally.
- If failure, maybe challenge (see above).

Challenge/challenge-response handling would be subset of above; the sender nonce would be explicit in the packet (for challenge-response) and zeroed in the pseudoheader and obviously you do not want to trigger challenges.. :-p

It would be interesting to compare implementation complexity/size for the different design choices actually. I wish I had the time..

With my bit-thrifty hat on but in too much hurry to write _enough_,

-Markus

---

From: "STARK, BARBARA H" <[email-masked]>
Date: Thu, 28 Jun 2018 11:52:06 +0000

> It gives better security properties to devices with clocks or storage because those devices 
> do not have their security depend on a randomly generated number being unique.

I am reading and enjoying this thread. Just to weigh in with my experience of the likelihood of a device that is intended to do routing having neither clock nor storage: unlikely. The likelihood of a device vendor who cares at all about security producing a router without clock and storage: nil.

Routers that care at all about security have at least some minimal firewalling capability. The one absolute requirement of anything that claims some firewalling is that it be capable of maintaining a timestamped log.

So I have no issue with lower security expectations for router without clock or storage. I wouldn't recommend such a device to anyone.
Barbara

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 28 Jun 2018 19:13:53 +0200

> I am reading and enjoying this thread. Just to weigh in with my
> experience of the likelihood of a device that is intended to do routing
> having neither clock nor storage: unlikely.

Noted, thanks for the input.

As far as I know, though, the mesh networking community is using devices
with no hardware clock that synchronise their time through the network,
and therefore need to participate in routing before they have reliable
time.  These devices need to be able to bootstrap routing before they have
reliable time, even if for some reason they lost their state (e.g. they've
been shut down improperly).

Perhaps more convincing, using a protocol that does not require persistent
state makes the implementation simpler, since reliable persistent state is
not completely trivial to do portably.  (In part because the part of the
filesystem that is persistent differs between devices, in part because
devices can crash at any time.)

So I'd say that having a protocol that solves the problem in the general
case is a net win, and I'm confident we can do that without excessive
complexity.  We'll have an implementation by tonight, we'll reconsider if
it's too ugly.

-- Juliusz

---

From: Ted Lemon <[email-masked]>
Date: Thu, 28 Jun 2018 12:26:05 -0500

How is it that devices of this type manage to keep their clocks
synchronized for transmit and receive slot synchronization if they don't
have clocks?

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Thu, 28 Jun 2018 22:49:50 +0200

Ted Lemon <[email-masked]> writes:

> synchronized for transmit and receive slot synchronization if they
> don't have clocks?

They have clocks; just not battery-backed RTCs. So a device will keep
time while it's powered off, but lose it when power cycling / rebooting.

For WiFi rx/tx, the WiFi hardware generally has its own internal clock,
though, which has nothing to do with system time...

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Fri, 29 Jun 2018 03:13:17 +0200

> really a safe assumption if one wants to build a robust parser? :)

No, that's not the assumption.

The last 50 years have shown us that no matter how hard we try, security
flaws happen, and unlike our predecessors, we no longer have the hubris to
think that we can count on writing bug-free code.  So we strive to write
bug-free code, while at the same time making our best to ensure that,
should we fail, our bugs will have no security consequences.

I'll put it differently.  According to github, there are currently 55
forks of babeld.  At least some of these forks make non-trivial changes to
the protocol, and I'm not quite sure how secure their code is.  I want to
make it likely that any bugs that they introduce are as difficult to
exploit as possible, and dropping evil packets as early as possible is
one of the defenses I'm counting on.

-- Juliusz

---

From: Juliusz Chroboczek <[email-masked]>
Date: Fri, 29 Jun 2018 03:27:06 +0200

> - If failure, maybe challenge (see above).

Hmm... so now both challenges and challenge replies are unprotected by
HMAC (since they need to be acted upon even in case of HMAC failure),
right?  Therefore, we put them in the packet trailer, so that we can
retain the property that we don't parse the packet body before HMAC
validation.

Implementation complexity is comparable, I think.  However, now the
Neighbour Table entry is created before HMAC validation (to keep the
challenge state), so an evil peer is able to create unbounded amounts of
state (by spoofing multiple source addresses).  I guess you could avoid
that by encoding a cookie in your nonce, but that in turn increases
implementation complexity.

Am I missing something?

-- Juliusz "I'll sleep when I retire" Chroboczek

---

From: Markus Stenberg <[email-masked]>
Date: Fri, 29 Jun 2018 07:42:53 +0300

Nah. They have just separate branch which uses explicit sender nonce ( challenge-response ) or no sender nonce ( challenge ). 

-Markus

Sent from my preciouss, aka iPad ;)

---

From: Markus Stenberg <[email-masked]>
Date: Fri, 29 Jun 2018 07:46:37 +0300

I think I prefer the idea of inserting that HMAC handling in the challenge/response TLV itself so in that case strictly speaking you would have no HMAC TLV but those messages would be authenticated too. 

Of course downside is the need to use 2-3 TLVs for HMAC but as they are already used for security not sure there is much of a difference. 

-Markus

> On 29 Jun 2018, at 7.42, Markus Stenberg <[email-masked]> wrote:
>

---

From: Markus Stenberg <[email-masked]>
Date: Fri, 29 Jun 2018 07:53:47 +0300

Or maybe have HMAC TLV have subtlv with explicit nonce in these cases ( or explicit nonce TLV outside HMAC ). Hmm.  With those just same HMAC processing would work with just special casing on where nonce is sourced from. 

I promise this is last one for today, 

-Markus

> On 29 Jun 2018, at 7.46, Markus Stenberg <[email-masked]> wrote:
>

---

From: Juliusz Chroboczek <[email-masked]>
Date: Fri, 29 Jun 2018 09:50:46 +0200

>> right?

> Nah. They have just separate branch which uses explicit sender nonce ( challenge-response ) or no sender nonce ( challenge ). 

Ah, I see.  But you're not making it easy.

-- Juliusz

---

From: Juliusz Chroboczek <[email-masked]>
Date: Fri, 29 Jun 2018 09:52:36 +0200

> Or maybe have HMAC TLV have subtlv with explicit nonce in these cases
> ( or explicit nonce TLV outside HMAC ).

Yes, that looks better.

Hmm.  With those just same HMAC processing would work with just special
casing on where nonce is sourced from.

> I promise this is last one for today, 

I hope that's because you're busy implementing your protocol ;-)

-- Juliusz