Subject: Re: [babel] Some open HMAC issues

From: David Schinazi <[email-masked]>
Date: Sun, 01 Jul 2018 21:48:29 -0700

> On Jun 30, 2018, at 06:04, Juliusz Chroboczek <[email-masked]> wrote:
> 
> 0. Explicit vs. implicit Indices
> 
> The discussion between explicit (DKC variant) and implicit (Stenberg
> variant) indices is still open.  Just because we've made DKC code
> available doesn't mean the WG needs to follow our idiosyncrasies.
> 
> (I'll try to find the inner strength to summarise the discussion at some
> point.)
> 
> 
> 1. Implemented and MTI HMACs
> 
> We've followed Denis' text, and implemented SHA1 and RIPEMD160.  Could any
> security specialists please advise:
> 
>  - which algorithms should be implemented;
>  - which algorithms should we propose to the WG as Mandatory to
>    Implement (MTI)?

I think SHA2-256 should be the only MTI, as it is considered secure and
is widely available.

> On a related note, should we be looking at algorithms other than HMAC?
> The challenge mechanism is fairly generic, and the actual hashing is just
> a tiny part of the protocol.

What other algorithms did you have in mind? I think HMAC fits what
we need here.

> 2. Should the HMAC cover the packet header?
> 
> The Babel packet header has the following format:
> 
>     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
>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>    |     Magic     |    Version    |        Body length            |
>    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> 
> Right now, Version is fixed at 2, but if we ever define Babel version 3,
> we might become susceptible to downgrade attacks.  I don't recall why we
> skipped the header in HMAC computation, but I think it's a bug.
> 
> (As far as I can tell, 7298bis hashes the whole packet, including the
> packet trailer.)

Yes, it should cover the header to avoid tampering.

> 3. Packet format
> 
> There are three new TLVs (HMAC, Challenge, Challenge Reply).  They are
> variable-length and therefore non-terminating in the sense of rfc6126bis
> Section 4.4, which means that they cannot carry sub-TLVs.  This follows
> Denis' original design, and I think it's the right thing to do since it
> makes the packet format simpler.
> 
> Does anyone envision a need to carry sub-TLVs on these TLVs?

I don't have any ideas for that.

> 4. Challenge timeout
> 
> How long does a receiver have to reply to a challenge?  We see no
> vulnerability here, but we feel that a challenge reply coming a few hours
> late is at the very least suspicious.
> 
> (Our code apparently uses 300ms, but I think it's a bug -- it should be on
> the order of tens of seconds, since a peer is allowed to aggregate its
> challenge reply with other unicast TLVs -- that's the first time I see
> a convincing use-case for Unicast Hellos, by the way.  Note that we don't
> necessarily know the peer's Hello and IHU intervals when we challenge.
> Perhaps we should make the timeout explicit in the challenge TLV?)

Having an Interval in the ChallengeRequest would be similar to
Acknowledgment Requests, so that makes sense to me.

> 5. Use of the packet trailer
> 
> The HMAC TLV is carried in the packet trailer, which makes it clear which
> part of the packet is protected by HMAC and avoids the need to clear parts
> of the packet body before hashing.  (Think about extensibility -- there
> might be other TLVs in the future that must not be protected, and if
> different extensions require clearing different parts of the packet, we're
> going to end up with some pretty enjoyable code obfuscation.)
> 
> Does anyone have technical arguments against the use of the packet
> trailer?  For the record, Denis didn't use a packet trailer, and David has
> expressed some mild reservations about its use (he feels that we're
> trading specification simplicity for implementation simplicity and
> extensibility, and while I agree with this, I happen to think it's the
> right tradeoff in this particular case).
> 
> If we keep the trailer, well need to add something to 6126bis.  I suggest
> the following RFCese:
> 
>  - the packet trailer is a sequence of TLVs, just like the packet body,
>    and the TLV number space is the same;
>  - a TLV that appears in the packet trailer MUST be ignored on reception
>    unless its definition explicitly states that it is allowed in the
>    packet trailer;

So far I agree.

>  - the mandatory bit MUST NOT be acted upon when it appears in the packet
>    trailer; as a consequence, an implementation that doesn't grok any
>    TLVs that can appear in the trailer MAY simply ignore the packet
>    trailer without ever parsing it.

I'm not sure I understand this. Why wouldn't mandatory sub-TLVs
in the trailer behave like they do in the body?

> 6. Cryptographic Seqno increase
> 
> A peer is allowed to increase its Cryptographic Seqno by an arbitrary
> value (more than 1).  This allows the use of fast-running counters, for
> example based on a hardware clock.
> 
> For example, an implementation might encode a 1µs-granularity clock in
> the Cryptographic Seqno, end encode the top-order 16 bits in the Index.
> There would be a spurious challenge every 72 minutes, and the Index would
> overflow every 9 years (meaning you'd need to perform key rotation at
> least that often).
> 
> Does anyone see a problem with that?

SGTM

> 7. Cryptographic Seqno size

Can we call this the Packet Counter? We already have two seqnos in Babel.

> The Cryptographic Seqno is of a fixed size; if it overflows, the sender
> must pick a new index and suffer packet loss during at least one RTT
> (while it's waiting for a new challenge).
> 
> The Cryptographic Seqno is currently 32 bits long.  Does it make sense to
> reduce it to 16 bits?  That would shave 2 octets from each packet, at the
> cost of more frequent challenges.  I think it should stay at 32 bits,
> since it makes it possible for people to use a fast-running counter (see
> point 5 above).
> 
> (In a stable network with 1000 nodes and the default parameters, babeld
> should be sending on the order of 1.2 packets per second.  A 16-bit
> counter will overflow after 15 hours, a 32-bit counter will overflow after
> 113 years.  All bets are off if you use a fast-running counter, of course.)

Agree for 32bits.

> 8. Index and Nonce size
> 
> Indices and Nonces are of variable size (up to the maximum TLV size): our
> implementation selects 80-bit values, but it will handle values of up to
> 251 resp. 255 octets (as much as fits in a TLV).
> 
> While having variable-length values slightly complicates the implementation,
> I think it's a good idea:
> 
>  - an implementation might want to encode a cookie in the Nonce in order
>    to have stronger DoS protection, thus needing a larger Nonce;
>  - an implementation with a stable clock might want to use a tiny Index
>    (see point 5 above).

Agree.

> I suggest we should limit indices and nonces to 192 octets, indices and
> nonces larger than that MUST NOT be sent.  This gives enough margin to
> carry a nonce or index in a sub-TLV (which we're not currently planning to
> do, but what the heck).

Not sure I see the benefit of this limitation.

> (This means we allow 0-octet Nonces.  Haha.)

Nothing wrong with that, each node is responsible for their own security choices.

> 9. Lack of an ANM
> 
> Since the new protocol is not vulnerable to replay, we don't use
> a separate ANM, but keep all the per-peer state in the ordinary Neighbours
> Table -- if a neighbour entry expires, we'll need to challenge again.
> We intend to put this in the spec, and add an implementation note to
> explain that implementations that wish to avoid spurious challenges may
> use a persistent ANM to keep the neighbour state.
> 
> Does anyone see a problem with that?

SGTM

I'd also add:

10. KeyID

I think there is value in having a KeyID next to the HMAC to allow better
performance when using multiple keys. RFC7298 had a 16bit KeyID,
and that sounded reasonable to me.

David

---

From: Juliusz Chroboczek <[email-masked]>
Date: Mon, 02 Jul 2018 09:21:03 +0200

> and that sounded reasonable to me.

Please describe the user interface to that.

-- Juliusz

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Mon, 02 Jul 2018 12:23:35 +0200

> I think SHA2-256 should be the only MTI, as it is considered secure and

+1 on sha-256, but I think it might be worth considering blake2s as
well, since that gives smaller sigs and is specifically designed for
low-powered devices, such as mips-based routers :)

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Mon, 02 Jul 2018 14:16:16 +0200

> low-powered devices, such as mips-based routers :)

Noted.

We're putting in HMAC-SHA256 as MTI, we'll add recommendations for other
algorithms later.

-- Juliusz

---

From: David Schinazi <[email-masked]>
Date: Mon, 02 Jul 2018 09:30:21 -0700

> Please describe the user interface to that.

I'm not very familiar with the babeld user interface / config file,
but I assume you have a place where you set either what the raw key value
is or what the path to the key file is. Next to there you would add an integer.
All nodes need to configure the same key, making sure they configure the
same integer with that key sounds straightforward enough?

David

---

From: Dave Taht <[email-masked]>
Date: Mon, 2 Jul 2018 09:39:22 -0700

Defeating SHA1 to my knowledge requires a ridiculous amount of data to obtain
a collision. when the total amount of data you are covering ranges
from 64-1500 bytes, I don't see a problem.

(totally not a crypto expert here, however)

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Mon, 02 Jul 2018 18:58:31 +0200

David Schinazi <[email-masked]> writes:

> but I assume you have a place where you set either what the raw key
> value is or what the path to the key file is. Next to there you would
> add an integer. All nodes need to configure the same key, making sure
> they configure the same integer with that key sounds straightforward
> enough?

But why is it needed? It's just one more thing to configure, which makes
configuration more verbose and prone to errors...

-Toke

---

From: David Schinazi <[email-masked]>
Date: Mon, 02 Jul 2018 10:05:01 -0700

> On Jul 2, 2018, at 09:58, Toke Høiland-Jørgensen <[email-masked]> wrote:
> 

Without a KeyID, the receiving complexity is proportional to the number of
configured keys. That means that nodes configured with n keys not
only spend O(n) times more CPU per received packet, they are also n times
more vulnerable to DoS attacks. This becomes a tradeoff between
- better performance, slightly better security
OR
- slightly easier configuration, two bytes saved on the wire

I'm not advocating that this is absolutely necessary, but I'd like to
discuss the pros and cons in case people think of other ways this
is better or worse.

David

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Mon, 02 Jul 2018 19:19:21 +0200

> discuss the pros and cons in case people think of other ways this

Hmm, I'm not sure that I am convinced that it is worth the tradeoff to
add the key ID. But assuming it is: Is there any reason why this ID
needs to be user configured? We could just define it as a 16-bit
truncated hash of the key itself, or something like that?

-Toke

---

From: David Schinazi <[email-masked]>
Date: Mon, 02 Jul 2018 10:41:50 -0700

> On Jul 2, 2018, at 10:19, Toke Høiland-Jørgensen <[email-masked]> wrote:
> 

I like this idea, but we'd have to be careful to not open up offline
attacks this way.

David

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Mon, 02 Jul 2018 21:35:55 +0200

> I like this idea, but we'd have to be careful to not open up offline

Yeah, it should be purely an optimisation, and all security properties
should be derived from the full HMAC. And we should be able to handle
duplicate keyIDs due to collisions.

So as long as it is implemented as:

if (keyid != hash16bit(key_bytes)) {
  skip HMAC tlv
}

and not

if (keyid == hash16bit(key_bytes) && !is_valid(hmac)) {
  reject packet
}

we should be fine, I think...

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 03 Jul 2018 01:50:43 +0200

> only spend O(n) times more CPU per received packet,

Where n is just the number of keys configured, and not something an
attacker can control (see Sections 1.1 and 4.3 of draft-do-babel-hmac).
In practice, I expect n to be usually just 1, and at most 2 during key
rotation.

Without an explicit KeyID, the set of keys is just a set -- it can be
implemented for example as a directory of keys, where adding a new key is
just an scp to the directory, or it can be implemented as a set of TLVs
flooded by HNCP, where adding a key consists in flooding a new TLV.

If you have an explicit KeyID, then you need to make sure that the KeyID
is consistent among all of the routers in a given security domain.  You
can no longer just scp the key, you need to pick a KeyID that is currently
unused.  If you're using an automated distribution protocol, then the
protocol must be able to choose a KeyID that is currently unused not only
by nodes that participate in said protocol, but also by nodes that don't.

Worse is better, David.  It is better to have a protocol that has a slight
inefficiency but is easy to deploy and to manage, than a protocol that is
slightly more efficient but that nobody will want to deploy because of the
very significant complications due to the KeyID.

-- Juliusz

---

From: David Schinazi <[email-masked]>
Date: Mon, 02 Jul 2018 17:06:00 -0700

> On Jul 2, 2018, at 16:50, Juliusz Chroboczek <[email-masked]> wrote:
> 

In homenet there was discussion of pairwise symmetric keys
distributed via HNCP. So n could be quadratic in the number of routers.

> flooded by HNCP, where adding a key consists in flooding a new TLV.

If you have a TLV you use to deploy the key, you can deploy the KeyID as
the first two bytes of that TLV. That way both the KeyID and key are flooded
together.

> can no longer just scp the key,

KeyID does not prevent scp, just put the keyID in the name:
scp my_new_secret.key babel-router42.local:/etc/babeld/keys/foo-12345.key

> you need to pick a KeyID that is currently

I don't see why. Having a KeyID conflict just means you'll try both keys.

> very significant complications due to the KeyID.

I'm less worried about efficiency and more about robustness to DoS.

An implementation is free to always send KeyID as 42 and silently drop
any HMAC TLV KeyID that isn't 42 if it can't handle the complexity.

In general I agree with your position that adding unnecessary
complexity is bad. But here I'm not sure I agree with how much complexity
this actually represents.

David

---

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 03 Jul 2018 02:28:05 +0200

>> you need to pick a KeyID that is currently unused.

> I don't see why. Having a KeyID conflict just means you'll try both keys.

Ah, that's the bit that I was missing -- you allow multiple keys with the
same ID.  So the UI issue goes away -- you just set the KeyID to 0 by
default.  And an implementation is free to ignore KeyIDs on reception.

I lift my opposition.  If the WG wants KeyIDs, and provides me with
suitable text to put in the spec, I'll implement them.  In which case
I reserve the right to make sarcastic comments in public.

> any HMAC TLV KeyID that isn't 42 if it can't handle the complexity.

Nah, you just check all keys, ignoring their KeyID.  In other words, the
KeyID degenerates to a field that "may be ignored on reception".

> distributed via HNCP.

That's not what the protocol was designed for.  We send one HMAC per key
in every freaking packet, and if we've got more than 60 or so, we'll quite
simply run out of space in the Ethernet frame.  All keys, no data, the
drunken cryptographer's dream.

If you want pairwise keying, use a protocol that uses pairwise communication.
Also known as unicast.  I hear you're the co-author of just such a protocol.

-- Juliusz

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Fri, 13 Jul 2018 18:30:31 +0200

Seeing as I have now implemented the draft, I have some more opinions on

> The Babel packet header has the following format:

Yes, I see now reason not to hash the whole thing.

>     trailer without ever parsing it.

I agree that sticking the signatures in the packet trailer is the right
thing to do. The zero out / hash self / rewrite hash dance is way too
annoying. Also, when the signature is in the packet trailer the hash
check can move straight to that and ignore the rest of the packet; and
the regular parser can ignore the packet trailer and just parse the
regular TLVs.

> carry a nonce or index in a sub-TLV (which we're not currently planning to

Letting the nonce be of arbitrary size is fine, but doing the same thing
for the index is incredibly annoying. Since the index needs to be stored
with the same lifetime as the neighbour, making it arbitrary size means
there's another blob of dynamically assigned memory to keep track of.
Which may have to be resized later if the peer changes its index size.

If we want to allow really small indexes, that is fine, but then limit
the max size to (say) 10 bytes; that way, a buffer of the maximum size
can be statically assigned in the neighbour struct (251 or even 192
bytes is way too much for static allocation).

Or maybe just forgo the complexity entirely and make the index a fixed
size; you just know that someone is going to pick a way too small value
and make themselves susceptible to replay attacks at some point...

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Sun, 15 Jul 2018 02:08:12 +0200

> Yes, I see now reason not to hash the whole thing.

Fully agreed.  That's what draft-do-...-00 says, and what we've
implemented (not very well, by the way).

> the regular parser can ignore the packet trailer and just parse the

That's what I think too, but David disagreed last time I asked him.
Since you agree with me, I think I'm going to insist on this one.

(I assume your implementation correctly drops all non-HMAC TLVs from the
packet trailer, including PAD1.)

> Which may have to be resized later if the peer changes its index size.

I think we have some time to decide, but here's a few arguments both ways.

1. We really want nonces to be of arbitrary size, so implementations have
   the space to encode a cookie if they're concerned about DoS.

2. Having nonces of arbitrary size implies dynamic allocation.  At any
   rate, you need dynamic allocation for nonces, since they're short-lived
   and per-neighbour.

3. You do want to allow tiny indices (unless we adopt Markus' proposal),
   since some implementations will want to save bytes on the wire by using
   a real-time clock.

4. I don't see any good reason right now for long indices (more than 16
   bytes, say).

So right now (likely to change in the future), I'd argue for:

  - variable size nonces with no size limit;
  - variable size indices.

I haven't made an opinion yet on whether we want a limit to the size of
indices.
   
> bytes is way too much for static allocation).

Agreed.

> and make themselves susceptible to replay attacks at some point...

Disagreed.

-- Juliusz

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Sun, 15 Jul 2018 11:57:59 +0200

Juliusz Chroboczek <[email-masked]> writes:

>> Yes, I see no reason not to hash the whole thing.
>

Cool.

> packet trailer, including PAD1.)

If by 'drop' you mean 'ignore', then yes. I'm just reusing the TLV
parsing loop with a different offset, and ignoring anything that's not
HMAC.

>    the space to encode a cookie if they're concerned about DoS.

Sure, that's fine.

>    rate, you need dynamic allocation for nonces, since they're
>    short-lived and per-neighbour.

Not necessarily. When receiving a challenge request, you can just do
memcpy(outgoing_packet_buffer, incoming_packet_buffer, nonce->size). And
for the nonces you send yourself you know in advance what size they are
going to be, so you can just put a static buffer of that size in 'struct
neighbour'.

>    since some implementations will want to save bytes on the wire by
>    using a real-time clock.

Sure, that's fine. Should 0-size be allowed, or should we require at
least one byte?

> 4. I don't see any good reason right now for long indices (more than 16

Nope, me neither.

>   - variable size nonces with no size limit;

I'm fine with this.

> I haven't made an opinion yet on whether we want a limit to the size of

Well, I think we should. My implementation will currently discard any PC
TLVs with an index longer than 10 bytes :)

>> Or maybe just forgo the complexity entirely and make the index a
>> fixed size; you just know that someone is going to pick a way too
>> small value and make themselves susceptible to replay attacks at some
>> point...
>
> Disagreed.

Right, fair enough. As long as the danger of replay attacks is spelled
out clearly in the draft I guess we can trust implementors to not do
something stupid...

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Sun, 15 Jul 2018 13:25:29 +0200

> going to be, so you can just put a static buffer of that size in 'struct

Right on both counts.  My bad.

> Sure, that's fine. Should 0-size be allowed, or should we require at

Allow it.  The property that's required is that a node never reuses the
same index with the same key -- one possible implementation strategy would
be to perform key rotation whenever state has been lost, in which case
0-size indices would be fine.

> TLVs with an index longer than 10 bytes :)

Hmm.

I mean, hmm.

> out clearly in the draft I guess we can trust implementors to not do

More implementation guidance is needed in the draft, granted.

-- Juliusz

---

From: David Schinazi <[email-masked]>
Date: Sun, 15 Jul 2018 09:06:21 -0400

> On Jul 14, 2018, at 20:08, Juliusz Chroboczek <[email-masked]> wrote:
> 

I didn't disagree. My point was that I wasn't bothered by the
zero out / hash / rewrite hash dance. But packet trailer is fine by me.

David

---

From: Juliusz Chroboczek <[email-masked]>
Date: Sun, 15 Jul 2018 15:34:28 +0200

> zero out / hash / rewrite hash dance. But packet trailer is fine by me.

Appendix A.  Use of the packet trailer

   The protocol described in this document uses the packet trailer for
   storing HMAC TLVs.  RFC 6126bis [RFC6126bis] leaves the format of the
   packet trailer undefined.  If the final version of this specification
   uses the packet trailer, RFC 6126bis will need to be extended with
   information about the format of the packet trailer.

   This document assumes that the packet trailer has the same format as
   the packet body, i.e., that it consists of a sequence of TLVs.  The
   receiver MUST silently ignore any TLV found in the packet trailer
   unless its definition states that the TLV is allowed in the packet
   trailer.

Do y'all think we can achieve some sort of consensus on that, so I can go
update 6126bis?

-- Juliusz

---

From: David Schinazi <[email-masked]>
Date: Sun, 15 Jul 2018 10:47:51 -0400

That's fine by me.

David

> On Jul 15, 2018, at 09:34, Juliusz Chroboczek <[email-masked]> wrote:
> 
> _______________________________________________
> babel mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/babel

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Sun, 15 Jul 2018 22:05:32 +0200

Juliusz Chroboczek <[email-masked]> writes:

> same index with the same key -- one possible implementation strategy
> would be to perform key rotation whenever state has been lost, in
> which case 0-size indices would be fine.

OK, fine with me.

>> TLVs with an index longer than 10 bytes :)

What? Are you saying that getting standards modified so they fit your
implementation is *not* how one is supposed to approach the IETF? ;)

-Toke

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Sun, 15 Jul 2018 22:05:47 +0200

> That's fine by me.

Also fine with me.

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Mon, 16 Jul 2018 00:44:24 +0200

> implementation is *not* how one is supposed to approach the IETF? ;)

For the record, my approach to IETF activities is:

  - implement the protocol we have in mind;
  - describe our implementation in an I-D;
  - get Toke to implement the I-D;
  - say hmm;
  - win the World Cup (a pity for Croatia, though);
  - produce a new I-D integrating Toke's comments.

-- Juliusz

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Mon, 16 Jul 2018 11:39:47 +0200

>   - get Toke to implement the I-D;

With you so far...

>   - win the World Cup (a pity for Croatia, though);

... but this implies our next window for publishing anything is 2022,
and that we would all have to root for France. I'm not sure I'm okay
with either of those conditions.

>   - produce a new I-D integrating Toke's comments.

This is, of course, the central point that I can only agree with :D

-Toke