Subject: [babel] Some open HMAC issues

From: Juliusz Chroboczek <[email-masked]>
Date: Sat, 30 Jun 2018 15:04:40 +0200

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)?

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.

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.)

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?

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?)

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;
  - 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.

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?

7. Cryptographic Seqno size

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.)

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).

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).

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

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?

-- Juliusz

---

From: Markus Stenberg <[email-masked]>
Date: Sat, 30 Jun 2018 20:50:50 +0300

> On 30.06.2018, at 16.04, Juliusz Chroboczek <[email-masked]> wrote:

I am obviously biased.. ;) 

> a tiny part of the protocol.

SHA1 should not be done in new algs, and RIPEMD160 is bit niche.

SHA256 is the way to go IMHO.

In theory some (nowadays HW accelerated) AES based thing such as CMAC might be interesting. In practise I haven't seen much uptake on those in recent protocols (typically you go with e.g. AES GCM which also provides encryption in same single pass).

> The Babel packet header has the following format:

It should.

> Does anyone envision a need to carry sub-TLVs on these TLVs?

Depends bit on choice 0.

> Perhaps we should make the timeout explicit in the challenge TLV?)

Should be long-ish, but not too long. 

> going to end up with some pretty enjoyable code obfuscation.)

Must not be protected things sound weird. I do not understand such concept in this context.

>    trailer without ever parsing it.

I think it could be just (usually) last(ish) TLV. Trailers are clunky, traversing toplevel TLVs is easy enough and has less special casing.

> Does anyone see a problem with that?

No.

> 113 years.  All bets are off if you use a fast-running counter, of course.)

I think I prefer 32 bits on further thought. 16 feels bit limited.

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

Seems reasonable enough.

> Does anyone see a problem with that?

Not me.

-Markus