Subject: [babel] HMAC authentication: remove TS/PC echo, use a cryptographic handshake

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 26 Jun 2018 13:28:58 +0200

Dear all,

Clara, Weronika and myself have been thinking about the HMAC protocol, and
we're considering replacing the TS/PC echo mechanism with a cryptographic
handshake.  We need the list's opinion.

In RFC 7298, every packet contains a strictly increasing 48-bit integer
known as the TS/PC.  A packet is rejected if its TS/PC is absent or not
strictly larger than the TS/PC previously sent by that node.  Back at
Berlin, Denis showed us that this mechanism is vulnerable to replay.

In 7298bis, this mechanism is augmented with the TS/PC Echo mechanism (my
term).  The TS/PC Echo is a sub-TLV of IHU, and MUST be sent with every
IHU; it contains an echo the latest TS/PC received from the node the IHU
it is destined to.  A packet is rejected if it contains an applicable IHU
whose TS/PC Echo is absent or not fresh enough (but not if it contains no
applicable IHU).  This mechanism was shown to be vulnerable to replay in
my posting of 10 May.

What we've currently implemented is a slight variation of the mechanism in
rfc6126bis: a packet is rejected unless we have received a valid TS/PC
echo from the sender recently enough (within 8 IHU intervals).  This would
appear to not be vulnerable to replay under reasonable conditions (either
at least one node has retained its state, or TS/PC is strictly
increasing), and is easy enough to implement.  However, it has one major
flaw: if a node resets its TS/PC (it loses its state), it is unreachable
for up to one ANMTimeout, which can be on the order of hours.

We propose to drop the TS/PC Echo mechanism and use a cryptographic
handshake instead.  When a node A receives a packet from a node B, it
consults its ANM table for the right TS/PC, just like in RFC 7298.  If
there is no ANM entry, or if the received TS/PC is invalid, it sends
a challenge with a 64-bit cryptographic nonce; B replies with a challenge
reply, which contains an echo of the cryptographic nonce.  If the reply
is valid, A overrides its ANM entry with the TS/PC value from the packet
containing the challenge reply.

We're thinking of encoding the challenge as a sub-TLV of the Ack Request
and Reply TLVs, but that's open to discussion.

Advantages:

  - there's no need to wait for ANMTimeout, just a challenge exchange;
  - the receiver can expire its ANM entry at any time, at the cost of
    issuing a new challenge (packet loss can be avoided by issuing the
    challenge slightly before the ANM entry expires);
  - we avoid bloating IHUs with TS/PC echos, which makes it possible to use
    a larger TS/PC (e.g. to make it unpredictable by inserting randomness
    in the low-order bits).

Disadvantages:

  - slightly more complicated implementation, since the challenge is stateful;
  - occasional packet loss while a challenge is in progress.

I rather like it, so we're probably going to start the implementation.
Please object now rather than later.

-- Juliusz

---

From: Markus Stenberg <[email-masked]>
Date: Tue, 26 Jun 2018 19:24:40 +0300

Disclaimer: Currently mildly sick :-) 

> containing the challenge reply.

Seems like an elegant solution.

> and Reply TLVs, but that’s open to discussion.

Not sure if I am that keen of that, but I would have to think bit more to comment on it more.

>    a larger TS/PC (e.g. to make it unpredictable by inserting randomness

Given the presence of a challenge-response mechanism, I am not sure you really need larger space. Quite the opposite really due to requiring the handshake to create the initial ANM entry. 

Of course, you can stick the nonce in to start/end of ’new TS/PC’ but I would probably rather not transmit it in every packet on the wire but only in e.g. initial challenge-response step and after that assume it to be part of the ANM table entry.

e.g.

-> who are you? nonce=X

<- I am Y! [nonce .]mynonce . hash-with-key(nonce,mynonce)
..

<- stuff . counter . hash-with-key(mynonce . counter . pseudoheader . stuff)

counter on the wire could just be e.g. 16 bits, and mynonce arbitrarily large (but probably e.g. 64 bits with reasonable randomness would be enough).

> Please object now rather than later.

Bit of a strawman proposal but in general I like the idea, usually it is muuch easier to stick in challenge-response to prevent replay attacks than do it fully passively when there is no time/nvram available.

Cheers,

-Markus

---

From: David Schinazi <[email-masked]>
Date: Tue, 26 Jun 2018 11:32:19 -0700

TLDR: I really like this idea, but here be dragons.

The security property we need here is to ensure the freshness of the peer's counter. And that requires MACing the nonce and counter together.
Markus' solution, if I'm understanding it correctly, is vulnerable to a MITM that swaps out the counter in the "I am Y" message because the counter is not hashed.
The Paris proposal solves this problem, because the nonce in the Ack is in the payload with the counter, ensuring that they're MACed together.

It's also critical to not accept a peer's counter until a handshake has been performed, because otherwise a node that just rebooted would be
vulnerable to old replayed packets. But that does mean we have a bootstrapping problem when two routers first discover each other, since
they'll both distrust the other's counter and both send the challenge AckRequests with nonces - but the current design says we must drop
AckRequests that aren't properly MACed, so we never resolve this. We could allow accepting AckRequests with untrusted counters but still need
to verify the hashes because an attacker here could intercept these messages and replace the counters on the fly. So now we need some code that
specifically recognizes these AckRequests and verifies them differently. This isn't horrible but in reduces the elegance a bit. That said this issue
is also present with 7298bis, so don't take this as against your proposal in any way. Just something to think about. Maybe the easiest solution is
to have a new TLV for this that's allowed to be handled when counters haven't been verified yet. And that new TLV would need to only be allowed
over unicast while we're at it.

Another caveat is denial of service, since anyone can cause you to generate a nonce and request echo, ideally we would want to recommend
a way to generate them statelessly, similar to TCP SYN cookies (not sure if possible here), or ensure that nonces only be generated if the original
packet triggering them was properly MACed, just with an untrusted counter.

Another minor point I'll add about nonces: the recommended security practice is to use nonces at least half the number of bits of the hash
function used, so if we use SHA2-256, that would be 128bits. The spec should just allow the requester to set an arbitrary nonce length as a
TLV or sub-TLV whose length can be 0-255, and the peer should just echo that entire nonce TLV without stopping to think about the length.

Also, once you've successfully challenged a peer, I don't think you need to expire that or challenge them again as long as packets are increasing
and in the replay window. But that requires having a counter space large enough to accommodate a reasonable replay window. But 32bits
might suffice.

All that said, I still think this would be easier to implement than TS/PC echo because you just need to keep track of a nonce and whether the
peer completed the challenge. But I'll have to actually implement to confirm that...

David

> On Jun 26, 2018, at 09:24, Markus Stenberg <[email-masked]> wrote:
> 
> _______________________________________________
> babel mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/babel

---

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 26 Jun 2018 22:29:38 +0200

> Given the presence of a challenge-response mechanism, I am not sure you
> really need larger space. Quite the opposite really due to requiring the
> handshake to create the initial ANM entry.

I'll think it over.

> Of course, you can stick the nonce in to start/end of ’new TS/PC’ but
> I would probably rather not transmit it in every packet on the wire but
> only in e.g. initial challenge-response step and after that assume it to
> be part of the ANM table entry.

You couldn't even if you wanted to.  The TS/PC is chosen by the sender, so
it can be the same for all neighbours.  The nonce is chosen by the
receiver, so it must be per-neighbour, and you don't have space in a Babel
packet to send nonces for all neighbours.

-> who are you? nonce=X

> <- stuff . counter . hash-with-key(mynonce . counter . pseudoheader . stuff)

Exactly.

-- Juliusz

---

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

> The security property we need here is to ensure the freshness of the
> peer's counter.

The property that's easy to prove is that we're not vulnerable to replay
if all TS/PC are strictly monotonic, e.g. because you have a (monotonic)
hardware clock or because you have persistent storage.

The other property is that we're not vulnerable to replay if Alice has
lost her state and Bob has disappeared from the network (since in that
case there's nobody to complete the challenge).

We are vulnerable to replay in the case where both Alice and Bob have lost
their state, and Chloe has replayable packets that match Bob's initial
TS/PC.

With the properties above, I believe we're already doing much better than
all other multicast HMAC-based protocols.  I'll be checking the literature
to confirm that over the next days.

So :

  - we're not vulnerable in the "reasonable" cases;
  - the cases in which we're vulnerable are well understood, which means
    we can easily write the Security Considerations section.

As Markus is prone to say, Bob is your uncle.

(I'll answer your other points later, Antonin is telling me that we need
to get some work done before the last metro.)

-- Juliusz

---

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

> Another caveat is denial of service, since anyone can cause you to
> generate a nonce and request echo, ideally we would want to recommend
> a way to generate them statelessly, similar to TCP SYN cookies (not sure
> if possible here), or ensure that nonces only be generated if the original

That's already the case -- the very first thing we do is to check the
HMAC, and if that fails, the packet is silently dropped.  I think that's
an important property of Denis' protocol, and one that we're trying not to
break.

Still, it doesn't prevent DoS -- if Chloe has captured Bob's authentic
packet with a stale TS/PC, she can multicast it around, and cause everyone
to send challenges to Bob.  Cookies won't help here, since Bob is still
getting spammed by the challenges.

> Another minor point I'll add about nonces: the recommended security
> practice is to use nonces at least half the number of bits of the hash
> function used, so if we use SHA2-256, that would be 128bits. The spec
> should just allow the requester to set an arbitrary nonce length as a TLV
> or sub-TLV whose length can be 0-255, and the peer should just echo that
> entire nonce TLV without stopping to think about the length.

Clara, Weronika?

> Also, once you've successfully challenged a peer, I don't think you need
> to expire that or challenge them again as long as packets are increasing
> and in the replay window.

Clara, Weronika?

-- Juliusz

---

From: David Schinazi <[email-masked]>
Date: Tue, 26 Jun 2018 16:49:56 -0700

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

I think we can solve this vulnerability without making the protocol too complex so
I'd recommend trying to solve all scenarios we can and then make tradeoffs
if there's consensus that solving one case adds unreasonable complexity.

David

---

From: David Schinazi <[email-masked]>
Date: Tue, 26 Jun 2018 16:54:29 -0700

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

Cool.

> getting spammed by the challenges.

You could mitigate this by only allowing one challenge per some multiple
of the interval. It's often incredibly hard to entirely solve DoS but we can
do our best to mitigate it.

David

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 27 Jun 2018 12:17:36 +0200

> I think we can solve this vulnerability without making the protocol too
> complex

We spent a few hours yesterday puzzling over it (together with Florian
Horn and Paul Rozière, to whom thanks), and failed.

> I'd recommend trying to solve all scenarios we can and then make
> tradeoffs if there's consensus that solving one case adds unreasonable
> complexity.

I believe we're already doing better than RFC 7182, which would imply that
the existing security properties are good enough for a Standards Track
protocol.  We've got very little time left (my funding ends this Friday,
and it's up to the ladies whether they wish to continue working on the
project after their internship ends), but I hope we'll be able to document
precisely the conditions under which the protocol is known to be secure.

-- Juliusz

---

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

> handshake to create the initial ANM entry.

I'm not sure.

The protocol is vulnerable to replay whenever the TS/PC decreases, or, if
you prefer, the protocol expects TS/PC to be strictly monotonic but
provides a mechanism for gracefully recovering from a TS/PC discontinuity,
at the cost of a vulnerability to replay.  Implementations are strongly
encouraged to make heroic efforts to make sure that the TS/PC remains
strictly increasing.

From an implementation point of view, that's easier if you have enough
space in the TS/PC to encode a timestamp or a reboot counter.  Still, 48
bits is plenty -- it's enough for 32 bits seconds timestamp + 16 bits packet
counter, or 24 bits reboot counter + 24 bits packet counter.  32 bits seems
a little short.

I'm tempted to make it 64 bits and be done with it, but I'm fine with 48 bits.

-- Juliusz