Subject: [babel] Babel-MAC: key size and digest size

From: Antonin Décimo <[email-masked]>
Date: Fri, 27 Dec 2019 20:46:31 +0100

Dear all,

After working a bit on the MAC authentication for Babel implementation
in babeld, I think that the draft need clarification on two points:

1. Key size

The draft reads: §7
> Ideally, they should have a length of 32 octets (both for
> HMAC-SHA256 and Blake2s)

Other RFCs state:
- https://tools.ietf.org/html/rfc2104#section-3
  > However, less than L [hashing function block size] bytes is
  > strongly discouraged as it would decrease the security strength of
  > the function.
- https://tools.ietf.org/html/rfc4868#section-2.1.2

SHA256 has a block size of 64 octets (see RFC6234, search
SHA256_Message_Block_Size).
Blake2s key length is 0 <= kk <= 32
(see https://tools.ietf.org/html/rfc7693#section-2.1)

HMAC algorithms deal with shorter keys by padding them with zeroes up
to some size, and with longer keys by hashing them first.

I suggest we rephrase the draft to state that key length should
ideally be the maximum key length advertised by the hashing algorithm,
which for Blake2s is explicitly 32 octets, or no less than the block
size of the hashing algorithm which is 64 octets for SHA256.

2. Digest size

The length of the digest (= the MAC) produced by Blake2s may be
configured. Blake2s: 1 <= nn <= 32

For instance, the API of the reference implementation let the
programmer ask for specific digest length (outlen parameter).

    // Initialize the hashing context "ctx" with optional key "key".
    //      1 <= outlen <= 32 gives the digest size in bytes.
    //      Secret key (also <= 32 bytes) is optional (keylen = 0).
    int blake2s_init(blake2s_ctx *ctx, size_t outlen,
        const void *key, size_t keylen);

The MAC TLV §6.1 is composed by the length L of the digest, followed
by the digest D. On reception of a packet, D must be validated. A
logical thing to do is to compute a digest of length L with Blake2s.

The draft does not explicitly state that the checking code must use L
for the digest length, and not say, the maximum digest length.

We may conservatively assume that if two digests D1 and D2 of length
L1 < L2 are computed from the same message, D1 won't necessarily be a
prefix of D2.

Now, suppose that we allow digests of various length for the same
hashing algorithm. What happens when we receive a MAC TLV of length 0?
Or what if an attacker captures a packet, tampers with it, removes all
MAC TLVs, and adds 256 MAC TLVs of length 1 with all 256 possible
digest values? A least one MAC would be accepted, and the overhead is
only 3*256=768 octets.

If I am not mistaken this breaks the first assumption of the protocol
§1.2:
> that the Message Authentication Code (MAC) being used is
> invulnerable to pre-image attacks, i.e., that an attacker is unable
> to generate a packet with a correct MAC without access to the secret
> key;

Short digest lengths should not be allowed; a fix could be that the
draft explicitly states that only digests of the maximum (or a
predefined) length for each hashing algorithm should be send and
checked on reception.

Cheers!

-- Antonin

---

From: Antonin Décimo <[email-masked]>
Date: Sat, 28 Dec 2019 19:15:54 +0100

Hello again,

I'm keeping in mind that (§7):
> Every implementation MUST implement HMAC-SHA256 as defined in
> [RFC6234] and Section 2 of [RFC2104] , SHOULD implement keyed
> BLAKE2s [RFC7693] , and MAY implement other MAC algorithms.

1. Key length

This is the change I'm proposing in §7:

 Keys must be chosen in a manner that makes them difficult to guess.
-Ideally, they should have a length of 32 octets (both for HMAC-SHA256
-and Blake2s), and be chosen randomly.
+Ideally, they should be chosen randomly, and have the maximum key
+length supported by the MAC algorithm (32 octets for keyed BLAKE2S)
+or no less than the block size of the MAC algorithm (64 octets for
+HMAC-SHA256).

2. Digest length

After a bit of sleep, I realised that reading the length of the MAC
TLV in order to compute a MAC of this length is not compliant with the
protocol (§4.3) since MACs are computed without looking into the
packet.

> Then, for each key configured on the receiving interface, the
> receiver computes the MAC of the packet. It then compares every
> generated MAC against every MAC included in the packet;

Still, it was an error I was almost going to make. I propose the
following change to ensure that we're always using the maximum digest
length of the MAC algorithm.

This is the change I'm proposing in §4.1:

 implementation MUST implement HMAC-SHA256 as defined in
 <xref target="RFC6234"/> and Section 2 of <xref target="RFC2104"/>,
 SHOULD implement keyed BLAKE2s <xref target="RFC7693"/>, and MAY implement
 other MAC algorithms.
+The length of the MAC MUST be the maximum MAC length computable by
+the MAC algorithm (32 octets for both HMAC-SHA256 and keyed
+BLAKE2S).

3. Lazy computation

With the idea that computing a MAC is more costly than comparing MACs,
and that there's a very limited amount of MACs to check, I propose we
lazily compute MACs. Instead of computing the MAC for every key on
packet reception, we compute the MAC with the first key, then check it
against the MACs carried by the packet. If there's a match, the packet
is immediately accepted. If there's no match, we the proceed to the
next key until all keys are exhausted, and the packet is rejected.

This is the change I'm proposing in §4.3:

-Then, for each key configured on the receiving interface, the
-receiver computes the MAC of the packet.  It then compares every
-generated MAC against every MAC included in the packet; if there is
-at least one match, the packet passes the MAC test; if there is none,
-the packet MUST be silently dropped and processing stops at this
-point.
+Then, for each key configured on the receiving interface, the
+receiver computes the MAC of the packet and compares it against every
+MAC included in the packet; if there is at least one match, the
+packet passes the MAC test; if there is none, the receiver proceeds
+with the next key.  If none of the MAC matched, the packet MUST be
+silently dropped and processing stops at this point.

Cheers!

-- Antonin