Subject: [babel] Rethinking HMAC authentication

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 30 May 2018 18:18:14 +0200

Dear all,

As I mentioned previously, Clara Dô, Weronika Kołodziejak (in copy of this
mail) and myself are currently working on implementing HMAC authentication
in babeld roughly based on RFC 7298 and rfc7298bis.  Right now, we're not
strictly following Denis's spec, but rather enjoying ourselves and
experimenting with various approaches, in order to gain experience in
a view to defining a common specification by the end of the summer.  The
work is in its very early stages, so all of the choices below are open to
discussion.

1. We're using a pseudo-header, as suggested by David.  The exact
   structure of the pseudo-header is not fixed yet, but it's clearly going
   to include the source and destination link-local IPs.

2. In addition to the pseudo-header, we're hashing the packet header and
   the packet body.

3. Contrary to what Denis did, we're not inserting the HMAC TLV into the
   packet body, but instead appending it in the packet trailer (the part
   of the UDP datagram that's beyond the packet length).  This has two
   pleasant consequences:

     - we don't need to insert the HMAC TLVs before hashing;
     - when receiving a packet, we don't need to do a first parse of the
       whole packet before checking the HMAC, we jump directly to the
       packet trailer.

   We still need to ensure that there is enough space left in the buffer
   to append all HMAC TLVs (the restrictions on packet length in Section 4
   of rfc6126bis apply to the whole packet, not just the packet body).

   Any non-HMAC TLV present in the packet trailer is silently ignored, for
   future extensibility (in case somebody finds a use for a TLV that's not
   protected by HMAC).

4. The TS/PC TLV and the TS/PC echo sub-TLVs are still in the packet body
   (and hence protected by HMAC).

5. We're not checking TS/PC echos yet.  The approach suggested in 7298bis
   revision 00 has been shown to be unsafe, therefore, as suggested by
   Denis in a maling list posting, we're going to use a recent proof of
   liveliness approach.  The exact details are still unclear, but I'm
   thinking about:

     - a packet is accepted if (1) the TS/PC is higher than the previous
       value and (2) a correct TS/PC echo has been received from that peer
       in the last 3 minutes.

   This implies that the protocol will require capping the IHU interval to
   3 minutes (or less, in presence of packet loss).  I believe that's
   acceptable.

As mentioned above, all of this is still open to discussion.  Please speak
up.

-- Juliusz

---

From: David Schinazi <[email-masked]>
Date: Wed, 30 May 2018 10:57:59 -0700

Thanks for sharing Juliusz, this is interesting!

> On May 30, 2018, at 09:18, Juliusz Chroboczek <[email-masked]> wrote:
> 

Don't you still need to do a first parse of the whole packet to extract
the TS/PC for replay protection?

David

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Wed, 30 May 2018 20:12:53 +0200

David Schinazi <[email-masked]> writes:

> Don't you still need to do a first parse of the whole packet to
> extract the TS/PC for replay protection?

Presumably you could check the signature first, then just look for
possible replays while parsing the rest?

-Toke

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Wed, 30 May 2018 20:16:19 +0200

> 2. In addition to the pseudo-header, we're hashing the packet header and

What does packet header mean here? Babel header? UDP header? IP header?
I assume the former, right?

>      - we don't need to insert the HMAC TLVs before hashing;

I like this. The zeroing and rewriting bits in 7298 always struck me as
annoyingly complicated...

> As mentioned above, all of this is still open to discussion. Please
> speak up.

Most of the rest seems sensible. What hashing algorithms are you
implementing? For small routers, blake2s might be good to have as MTI
(http://blake2.net/). I asked the crypto guy at my department what he
would recommend in this day and age, and he basically said "just do
SHA256; and blake2s if you want to be fast on small devices"...

-Toke

---

From: David Schinazi <[email-masked]>
Date: Wed, 30 May 2018 11:21:43 -0700

> On May 30, 2018, at 11:12, Toke Høiland-Jørgensen <[email-masked]> wrote:
> 

The problem is that if there are TLVs before the TS/PC, you don't want to act on
them until you've validated the TS/PC and MAC. This could be solved by
mandating that the TS/PC TLVs MUST come before any other TLVs,
but adding ordering requirements to Babel TLVs makes me cringe.

David

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Wed, 30 May 2018 20:57:03 +0200

David Schinazi <[email-masked]> writes:

> The problem is that if there are TLVs before the TS/PC, you don't want
> to act on them until you've validated the TS/PC and MAC. This could be
> solved by mandating that the TS/PC TLVs MUST come before any other
> TLVs, but adding ordering requirements to Babel TLVs makes me cringe.

Or you could just build a parser that is robust against that sort of
thing? ;)

Arguably, a malformed packet should be discarded without acting on any
TLVs anyway, HMAC or not...

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 30 May 2018 21:02:44 +0200

> I assume the former, right?

Yes.  The relevant data from the IP and UDP headers is in the
pseudo-header (which is open to discussion).

> What hashing algorithms are you implementing? For small routers, blake2s
> might be good to have as MTI (http://blake2.net/).

We're using SHA1 right now, but Denis's protocol is agile, so it's a minor
detail at this stage.

> I asked the crypto guy at my department what he would recommend in this
> day and age, and he basically said "just do SHA256; and blake2s if you
> want to be fast on small devices"...

Noted.  Denis?

-- Juliusz

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 30 May 2018 21:06:00 +0200

>> to act on them until you've validated the TS/PC and MAC.

Right.

>> This could be solved by mandating that the TS/PC TLVs MUST come before
>> any other TLVs, but adding ordering requirements to Babel TLVs makes me
>> cringe.

Me too.

> TLVs anyway, HMAC or not...

Hmm, I want to preserve the ability to interleave parsing and acting.
That's not what your implementation does, Toke, but I want to preserve the
other implementation choice.

It looks like something needs to give.  Let's keep implementing and
thinking (interleaving the two, of course).

-- Juliusz

---

From: Ted Lemon <[email-masked]>
Date: Wed, 30 May 2018 13:35:36 -0700

> other implementation choice.

This is a well-known way to create security problems: if you interleave in this way, it's very easy to take some action based on an incomplete parse that turns out to have been valid, but too late.   TLS implementations have been hacked this way multiple times (I say this based on hearsay that I don't have time to go look up again, so I may be pointing my finger at the wrong thing, but this is definitely a serious problem).  So on the one hand, I would argue that you just shouldn't do this, and it's okay.   But if you insist on doing this, then you have to treat the signature specially.

---

From: David Schinazi <[email-masked]>
Date: Wed, 30 May 2018 14:06:19 -0700

Hi Ted,

While I agree with your statement for some specific protocols, I'm not sure I follow you in the case of Babel.
Babel TLVs can be parsed and acted on as they come, because future TLVs do not impact previous ones.
That's how my implementation currently works, as that is simpler and therefore more robust.
If we want to add security to that, we want to establish the security of a Babel datagram first, then parse-act.
For example, when running babel over DTLS, the parser-actor will only see the first TLV when the entire
datagram has been decrypted and integrity-checked, so there's no risk of needing to roll back anything.
This becomes trickier when it comes to HMAC, because the TS/PC TLVs are inside the datagram.
Therefore, one option is to perform two passes, one that only parses TS/PC+HMAC, and if that succeeds,
a second pass that parse-acts. What we're investigating here is the ability of simplifying this.
What caused the TLS vulnerabilities you described was the complexity of the state machine, and if I
understand the spirit of Babel correctly we won't allow that here because the working group hates complexity.

David

> On May 30, 2018, at 13:35, Ted Lemon <[email-masked]> wrote:
> 
> On May 30, 2018, at 12:06 PM, Juliusz Chroboczek <[email-masked] <mailto:[email-masked]>> wrote:
> _______________________________________________
> babel mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/babel

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Wed, 30 May 2018 23:24:20 +0200

> sure I follow you in the case of Babel.

Uh, I'm going to put that up on my 'famous last words' quote wall ;)

> Babel TLVs can be parsed and acted on as they come, because future
> TLVs do not impact previous ones. That's how my implementation
> currently works, as that is simpler and therefore more robust.

Except we're discussing a case where it breaks down because it is not,
well, robust enough ;)

Snide comments aside, I'm completely fine with finding a way to preserve
this property, BTW, as long as that doesn't just move complexity from
the parser to the protocol spec.

-Toke

---

From: David Schinazi <[email-masked]>
Date: Wed, 30 May 2018 14:26:47 -0700

Hi Toke,

I absolutely agree, so far a two-pass parse system is safe and relatively simple.
Any other proposal would need to be as safe and simpler :)

David

> On May 30, 2018, at 14:24, Toke Høiland-Jørgensen <[email-masked]> wrote:
>

---

From: Gabriel Kerneis <[email-masked]>
Date: Thu, 31 May 2018 10:08:06 +0200

On Wed, May 30, 2018 at 10:35 PM Ted Lemon <[email-masked]> wrote:

> This is a well-known way to create security problems: if you interleave in
> this way, it's very easy to take some action based on an incomplete parse
> that turns out to have been valid, but too late.   TLS implementations have
> been hacked this way multiple times (I say this based on hearsay that I
> don't have time to go look up again, so I may be pointing my finger at the
> wrong thing, but this is definitely a serious problem).  So on the one
> hand, I would argue that you just shouldn't do this, and it's okay.   But
> if you insist on doing this, then you have to treat the signature specially.
>

On a related note, I've looked into fuzzing the packet parsing logic of
babeld recently, and gave up because this interleaving made it too hard.
(Arguably, you could interleave and fuzz with some incremental parsing and
callback, or another kind of inversion of control, but that's not what the
current code does.)

Gabriel

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 31 May 2018 12:43:03 +0200

> the parser to the protocol spec.

Uh-huh.

So with the HMAC in the trailer but TS/PC and TS/PC echo in the body, the
parsing looks as following:

  1. jump to the trailer, check HMAC; reject packet early if no
     matching HMAC.
  2. walk packet a first time to check for increasing TS/PC and refresh
     freshness information; reject at this point if not fresh enough.
  3. walk packet a second time and act on the rest of the information.

That sounds reasonable enough to me.  The obvious alternative is to move
both TS/PC and TS/PC echo to the packet trailer (the latter would
therefore no longer be a sub-TLV of IHU).  I'm not sure what are the
security consequences of no longer covering TS/PC by the HMAC.

We'll keep hacking.

-- Juliusz

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Thu, 31 May 2018 13:12:44 +0200

>   3. walk packet a second time and act on the rest of the information.

Yeah, so this is basically a two-step parsing, except in the first step
you pretend you don't understand any of the normal TLVs...

> That sounds reasonable enough to me. The obvious alternative is to
> move both TS/PC and TS/PC echo to the packet trailer (the latter would

Erm, that they are trivially forgeable? You just take any valid HMACed
packet, stick a new TS/PC in it, and presto, you now have a valid packet
to replay?

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 31 May 2018 20:52:58 +0200

> packet, stick a new TS/PC in it, and presto, you now have a valid packet

Of course.

So now that I have a more realistic assessment of my level of competence
(fairly low), let's do some more exploring of the design space.  The use
of the trailer gives a clear separation between what is being hashed and
what is not:

  pseudo-header: hashed
  packet body: hashed
  trailer: not hashed

The advantage is that it's trivial to verify the hash; however, it does
not remove the need to either do two passes of parsing (my implementation)
or build a parse tree (Toke's implementation).  Either implementation
technique is valid, and if implemented carefully, they should be roughly
equally secure.

What are the disadvantages?  One is that now we need to distinguish
between packet body and trailer, and be careful to ignore any TLVs that
are in the trailer except those that are explicitly allowed there; this
doesn't seem like much of a burden.  The other is that we now create
a difference between DTLS and HMAC, since they don't protect exactly the
same data (DTLS protects the whole packet, while HMAC protects the packet
body only).  I don't see that as a significant flaw, perhaps David or
Denis can comment.

-- Juliusz

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Thu, 31 May 2018 21:02:15 +0200

> body only).  I don't see that as a significant flaw, perhaps David or

I generally agree with the above. One think you haven't mentioned is
that sticking things in the packet trailer actually requires a
specification of how the data in there is going to be interpreted, which
the spec doesn't currently say. Just having it use the same TLV format
is obvious, of course; but it should be specified I guess?

Also, do we risk someone building a stupid parser that doesn't look at
the length in the Babel header and just keeps parsing into the trailer
without noticing? If so, then maybe wrapping the whole trailer in a
single TLV and making everything else subtlvs of that might be a good
idea?

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 31 May 2018 22:58:32 +0200

> single TLV and making everything else subtlvs of that might be a good

Isn't it enough to have the trailer TLV space disjoint from the body TLV
space?

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Thu, 31 May 2018 23:09:45 +0200

> Isn't it enough to have the trailer TLV space disjoint from the body TLV

Hmm, guess so. Or use the same space (assign the HMAC TLV from the
existing registry), and add a flag specifying which ones are allowed to
be in the trailer? Or I guess that was what you were already planning to
do?

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Fri, 01 Jun 2018 00:10:32 +0200

> be in the trailer? Or I guess that was what you were already planning to

Yes.  The meaning of a TLV is determined entirely by the TLV itself, where
it lives only determines whether it's dropped or not.  Semantics of the
mandatory bit in trailer unclear at the moment, I guess I should send
a summary of the discussion to Gwendoline and ask her opinion.

We've got plenty of TLV space (we can switch to 16-bit TLV numbers at any
time, without breaking compatibility or mandatory bits).

-- Juliusz

---

From: Juliusz Chroboczek <[email-masked]>
Date: Fri, 01 Jun 2018 01:54:47 +0200

> mandatory bit in trailer unclear at the moment,

Strawman proposal, in early 21st century RFCese:

  - the trailer is a sequence of TLVs, just like the body;
  - a TLV MUST NOT appear in the trailer unless its specification
    explicitly allows it; if a TLV that is not allowed in the trailer
    appears there, it MUST be silently ignored (but the rest of the packet
    SHOULD still be processed);
  - a mandatory TLV MUST NOT be allowed in the trailer; if a mandatory TLV
    appears in the trailer, the TLV MUST be silently ignored, but the
    mandatory bit SHOULD NOT be acted upon (i.e. the rest of the packet
    SHOULD still be processed);
  - designers of extensions using the trailer should be aware that, since
  - the trailer is processed before cryptographic validation of the 
    packet, the format of TLVs in the trailer should be as simple as
    possible; achieving this simplicity may involve using formats that are
    not self-terminating and not allowing sub-TLVs within trailer TLVs.

-- Juliusz

---

From: David Schinazi <[email-masked]>
Date: Thu, 31 May 2018 17:34:22 -0700

That doesn't sound unreasonable to me, but I was fine with the HMAC TLV in the packet.
Setting the MAC to zero before computing the MAC sounds simpler to explain than these 5 bullet points.
(So far I have no strong opinion either way though)

David

> On May 31, 2018, at 16:54, Juliusz Chroboczek <[email-masked]> wrote:
>

---

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

> That doesn't sound unreasonable to me, but I was fine with the HMAC TLV
> in the packet.  Setting the MAC to zero before computing the MAC sounds
> simpler to explain than these 5 bullet points.

Uh-huh.

Since we walk the packet twice anyway, the main advantage of using the
trailer is gone.  There's still a minor advantage in avoiding walking the
whole packet before validating HMAC -- only authentic and replayed packets
can possibly reach the parser, not spoofed packets, which should make it
more difficult to exploit a flaw in the parser.

At this stage, I feel it's pretty much a wash (assuming I'm using the
idiom correctly), it'll hopefully become clearer as we continue implementing.

-- Juliusz

---

From: David Schinazi <[email-masked]>
Date: Thu, 31 May 2018 20:03:38 -0700

That's a good argument though, might tip the scales.

David

> On May 31, 2018, at 18:17, Juliusz Chroboczek <[email-masked]> wrote:
>