Subject: [babel] Babel-MAC: Blake2s is 128-bits by default

From: Juliusz Chroboczek <[email-masked]>
Date: Fri, 06 Nov 2020 23:31:23 +0100

Dear all,

We've had a discussion with Barbara and Toke today, and we've come to the
conclusion that there is an oversight in draft-ietf-babel-hmac-12.  In
Section 4.1, we say

   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.

As Valery Smyslov noted, BLAKE2s is able to produce hashes of any size
between 1 and 32 octets (8 and 256 bits).  However, both implementations
of Babel-MAC only ever produce 16-octet BLAKE2s hashes.  This is done for
the following reasons:

  - Babel-MAC is not believed to be vulnerable to collision attacks, hence
    128 bits is believed to be large enough;

  - BLAKE2s is intended as a more lightweight alternative to SHA2-256,
    which is the recommended algorithm if 128-bit hashes are believed to
    not be sufficient.

However, the digest size is not indicated in the draft.  Therefore, in
order to align the draft with implementation practice, I am asking the
list's permission to clarify the draft by changing the paragraph cited
above to say:

   Every implementation MUST implement HMAC-SHA256 as defined in [RFC6234]
   and Section 2 of [RFC2104], SHOULD implement keyed BLAKE2s [RFC7693]
   with 16-octet (128-bit) hashes, and MAY implement other MAC algorithms
   and hash sizes.

Donald, assuming nobody objects to the above, what is the right point at
which to request this clarification?  AUTH48?  Or publish an erratum just
after the RFC goes out?

Sorry for the oversight, and thanks for everyone's help,

-- Juliusz

---

From: David Schinazi <[email-masked]>
Date: Fri, 6 Nov 2020 14:42:51 -0800

I support this change.

David

On Fri, Nov 6, 2020 at 2:31 PM 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: Fri, 06 Nov 2020 23:51:33 +0100

Juliusz Chroboczek <[email-masked]> writes:

> of Babel-MAC only ever produce 16-octet BLAKE2s hashes.

Okay, something seemed off about this when I read it just now, so I just
double checked: And in fact both implementations use 32-byte Blake2s
digest sizes...

I still support making the change and specifying the size, but to
correspond to current implementation practice the change would need to
be "with 256-bit (32 octet) hashes".

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Sat, 07 Nov 2020 00:06:18 +0100

> double checked: And in fact both implementations use 32-byte Blake2s

Looking through the git history... the original version implemented by
Clara, Weronika and myself used 16-byte hashes, which was the original
intent, for the reasons outlined in my previous mail.

The version currently maintained by Antonin does indeed generate 32-byte
hashes.  While I haven't checked myself, Toke says that so does his
version, and the two versions have been shown to interoperate.

> be "with 256-bit (32 octet) hashes".

No strong opinion either way.  Let's give people a chance to comment.

-- Juliusz

---

From: Antonin Décimo <[email-masked]>
Date: Fri, 06 Nov 2020 23:53:54 +0100

> double checked: And in fact both implementations use 32-byte Blake2s

That also seemed off to me. To be fair regarding babeld, the "old"
hmac branch used 16-bytes blake2s, and my rewrite uses 32-bytes. We’re
using the reference blake2s implementation, and I changed 16 to the
provided BLAKE2S_OUTBYTES = 32 constant.

> be "with 256-bit (32 octet) hashes".

Me too. I an exchange earlier this year, Donald and Juliusz explained
to me that the size of the output hash is considered part of the
hashing algorithm, so yes, I support making that explicit for blake2s.

-- Antonin

---

From: David Schinazi <[email-masked]>
Date: Fri, 6 Nov 2020 16:14:38 -0800

Random thought: the draft mentions that the MAC algorithm
is configured alongside the key for it. Perhaps we should
add an explicit sentence such as "For MAC algorithms that
support multiple digest sizes (such as BLAKE2s), the digest
size needs to be communicated alongside the MAC algorithm.".

I agree that the "SHOULD implement BLAKE2s" should
mention a key length, but I have no preference between:
- SHOULD implement BLAKE2s with 16-octet hashes
- SHOULD implement BLAKE2s with 32-octet hashes
- SHOULD implement BLAKE2s with both 16 and 32-octet hashes

David

---

From: Donald Eastlake <[email-masked]>
Date: Fri, 6 Nov 2020 20:52:52 -0500

I guess AUTH48 is probably the right time to do this.

Speaking as a WG member, although my opinion is not very strong, I would
suggest
 - SHOULD implement BLAKE2s with 32-octet hashes

Thanks,
Donald
===============================
 Donald E. Eastlake 3rd   +1-508-333-2270 (cell)
 2386 Panoramic Circle, Apopka, FL 32703 USA
 [email-masked]

---

From: Juliusz Chroboczek <[email-masked]>
Date: Sun, 15 Nov 2020 18:54:56 +0100

After reading your replies, and thinking it over carefully, I disagree
with the apparent consensus.  I think Blake2s in Babel-MAC should use
128-bit keys, as in the initial implementation.  Please hear me out.

Toke and Dave originally suggested adding Blake2s to Babel-HMAC for two
reasons:

  - it is more computationally lightweight on platforms that don't
    implement SHA-256 in hardware;
  - it may serve as a fallback if SHA2 is ever broken.

While I am still not quite convinced by these arguments, I've agreed to
add the SHOULD Blake2s and to implement Blake2s for the following reasons:

  - it serves as a good example of adding a new algorithm to Babel-MAC;
  - with 128-bit signatures, it is useful on low-rate networks, which
    Babel is commonly used with.

For these reasons, we implemented Blake2s with 128-bit signatures.
Unfortunately, some confusion ensued, Toke implemented Blake2s with
256-bit signatures, Antonin changed our implementation to interoperate
with Toke's (without discussing the issue with me beforehand), hence the
current situation.

If Blake2s uses 256-bit signatures, then I see little convincing reason to
keep it around in addition to SHA-256.  For this reason, I recommend the
following course of action:

  1. Toke agrees to switch to 128-bit Blake2s signatures;
  2. we discard Antonin's branch (which is just a private branch), and do
     128-bit Blake2s signatures instead;
  3. during AUTH48, I make the clarification that the SHOULD implement
     applies to 128-bit signatures.

Two more points.  First, under no circumstances will I go against WG
consensus on this point -- if the WG strongly believes that the SHOULD
applies to 256-bit signatures, I will naturally follow the consensus.
Second, Babel-HMAC is an extensible protocol, so even if the RFC ends up
recommending n-bit signatures, nothing prevents a given implementation
from implementing m-bit signatures in addition to the RFC-recommended
n-bit signatures.

Sorry again for the confusion.

-- Juliusz

---

From: Donald Eastlake <[email-masked]>
Date: Sun, 15 Nov 2020 23:28:25 -0500

H Juliusz,

Speaking as a WG participant, I think your argument make sense and I
would supporting going in the direction you suggest.

Thanks,
Donald

---

From: Gabriel Kerneis <[email-masked]>
Date: Mon, 16 Nov 2020 12:52:06 +0100

I'm sorry I didn't reply earlier on this thread. Even before Juliusz'
email, the consensus seemed odd to me, for the reasons he outlined and I
intended to raise this up. Note that I have not taken part in any
implementation Babel, and I am basing my opinion purely on the facts laid
out in this thread. I think blake2s should use 128-bit signatures.

Gabriel Kerneis

On Mon, Nov 16, 2020 at 5:28 AM Donald Eastlake <[email-masked]> wrote:

>  Donald E. Eastlake 3rd   +1-508-333-2270 <(508)%20333-2270> (cell)

---

From: Juliusz Chroboczek <[email-masked]>
Date: Mon, 16 Nov 2020 14:13:02 +0100

> Note that I have not taken part in any implementation Babel

    $ cd /usr/local/src/babel/babeld
    $ git log | grep -i kerneis | wc -l
    10

Gabriel is also the co-author of the integration of babeld into OpenWRT.

-- Juliusz

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Mon, 16 Nov 2020 14:51:25 +0100

> with Toke's (without discussing the issue with me beforehand), hence the

Note sure that I quite agree with your history here, but that doesn't
really matter; I'm not actually opposed to 128-bit signatures per se,
although I would be more comfortable if someone with a crypto background
could weigh in with an opinion on this.

(Note that the way blake2s implements this is just by truncating the
output to whatever size you specify, the rest of the algorithm is
exactly the same).

>   1. Toke agrees to switch to 128-bit Blake2s signatures;

I think what would happen is that Bird would support both. It already
supports a whole bunch of other signature schemes (some of which, like
MD5, should probably not be used), and my patch adds support for both
blake2s and blake2b. I'll think about what the best UI for this is, and
ask the Bird devs as well I suppose.

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 18 Nov 2020 00:47:13 +0100

>> Toke and Dave originally suggested adding Blake2s to Babel-HMAC [...]

> Note sure that I quite agree with your history here,

It's quite likely I got it wrong, sorry if that's the case.

> I'm not actually opposed to 128-bit signatures per se, although I would
> be more comfortable if someone with a crypto background could weigh in
> with an opinion on this.

Valery, perhaps you could help?

> I think what would happen is that Bird would support both.

Ok.

You didn't address the most important question: do you agree with modifying
the RFC-to-be so that the SHOULD applies to 128-bit signatures, and
clarifying the information model that the "Blake2s" algorithm implies
128-bit signatures?

-- Juliusz

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Wed, 18 Nov 2020 11:57:21 +0100

> clarifying the information model that the "Blake2s" algorithm implies

I asked my go-to crypto guy who assured me that 128 bits is sufficient
for this use case. So no objections from me :)

(He also helpfully pointed out that I was completely wrong to assert
that Blake2s just truncates the hash if it's configured for shorter
output; so much for my C reading comprehension skills :/)

-Toke

---

From: "Valery Smyslov" <[email-masked]>
Date: Wed, 18 Nov 2020 15:44:18 +0300

Hi Juliusz,

> Valery, perhaps you could help?

I'll try to help, but [full disclaimer] I'm not a cryptographer, just a user of crypto :-)

I'm not very familiar with blake2s, but I assume that it's a strong cryptographic MAC function,
so the best possible attack is brute force. So 128 bits for MAC size generally looks OK if the key length
is also at least 128 bits and has enough entropy.

That said, I have two concerns with these figures. First, from my understanding of how
MAC is used in babel, it seems that the keys are long lived, so you potentially protect
very large number of packets using one key. That gives an attacker much more opportunities
to attack algorithm itself. For example, the CFRG has a draft draft-irtf-cfrg-aead-limits 
discussing limits of data to be safely protected with one key (well it's for AEAD ciphers,
but the same concerns applies for any crypto algorithm). I'd feel more comfortable to use 
longer MACs for long-lived keys, but, on the other hand, from my understanding 
routing protocols send relatively little data, so probably 128 bits is OK for babel.

My second concern is mostly theoretical one for now - it's quantum computers.
It is known that for any symmetric crypto quantum computers would reduce 
the effective key size by half (using Grover's algorithm). I'm not quite sure,
but that might apply to forging MACs too (finding second preimage). 

Anyway, this is my personal opinion and I think that CFRG should be asked 
if you want to get more authoritative answer. 

Regards,
Valery.

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Mon, 23 Nov 2020 11:55:36 +0100

> for this use case. So no objections from me :)

This does raise one question, though (as I just found out while
implementing the option for a 128-bit version): How does this impact the
recommendations for key size? I've been restricting the key size to
always be equal to the output size, so does this also imply that the key
size recommendation should change to 16 bytes?

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 25 Nov 2020 19:28:03 +0100

> recommendations for key size?

I suggest that they remain the same (SHOULD be 32 bytes).

The digest size impacts the overhead carried by every packet.  Not so the
key size: increasing the key size is essentially free.  As a matter of
fact, Blake2s will pad the key with zeroes before it is used.

Thus:

  - allowing shorter keys gains no generality (the user may achieve the
    same result by padding with zeroes before passing the key to Blake2s);

  - disallowing shorter keys causes confusion (by using a value different
    from both HMAC-SHA-256 and the Blake2s maximum), and has no measurable
    benefits.

I do not believe that it impacts the security in any way (2^128 ns is
roughly 10^12 times the age of the universe), but I could be wrong.

-- Juliusz

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Thu, 26 Nov 2020 11:26:29 +0100

> roughly 10^12 times the age of the universe), but I could be wrong.

Yeah, makes sense, let's keep it at 32 bytes :)

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Thu, 26 Nov 2020 13:04:40 +0100

> Yeah, makes sense, let's keep it at 32 bytes :)

Excellent.  I'm therefore going to make the following change in AUTH48:

  - in Section 4.1, replace

   Every implementation MUST implement HMAC-SHA256 as defined in [RFC6234]
   and Section 2 of [RFC2104], SHOULD implement keyed BLAKE2s with 128-bit
   (16-octet) digests [RFC7693], and MAY implement other MAC algorithms.

I will not change the following text in Section 7:

    Ideally, they should have a length of 32 octets (both for HMAC-SHA256
    and Blake2s), and be chosen randomly.

Donald, are you willing to call consensus on this point?

-- Juliusz

---

From: Antonin Décimo <[email-masked]>
Date: Thu, 26 Nov 2020 13:25:12 +0100

I support Juliusz' changes, and I have a patch ready ;-)

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Thu, 26 Nov 2020 14:04:08 +0100

> I support Juliusz' changes, and I have a patch ready ;-)

The Bird implementation[0][1] is already updated (apart from the key
size thing[2]), so feel free to test against that :)

-Toke

[0] http://trubka.network.cz/pipermail/bird-users/2020-November/015033.html
[1] https://github.com/tohojo/bird/tree/babel-mac-03
[2] http://trubka.network.cz/pipermail/bird-users/2020-November/015047.html

---

From: Donald Eastlake <[email-masked]>
Date: Thu, 26 Nov 2020 14:02:47 -0500

Hi Juliusz,

> Donald, are you willing to call consensus on this point?

All this has been discussed on the WG mailing list with no objection and
there has been some further success but just to be sure, I'd like to wait a
couple of days before declaring consensus.

Thanks,
Donald

---

From: Donald Eastlake <[email-masked]>
Date: Sat, 28 Nov 2020 13:42:11 -0500

Hi Juliusz,

There having been no further comments and given the extent to the
discussion of this on the WG mailing list, I'm declaring WG consensus
for this minor change.

Thanks,
Donald

On Thu, Nov 26, 2020 at 2:02 PM Donald Eastlake <[email-masked]> wrote:
> All this has been discussed on the WG mailing list with no objection and there has been some further success but just to be sure, I'd like to wait a couple of days before declaring consensus.
>
> Thanks,
> Donald

---

From: "STARK, BARBARA H" <[email-masked]>
Date: Mon, 30 Nov 2020 21:10:27 +0000

Just to confirm (because assuming is bad)...

> Yeah, makes sense, let's keep it at 32 bytes :)

... this means that other than changing "BLAKE2s" to "BLAKE2s-128" (consistent
with the list of "possible values" change), no other change is needed to the text 
in info model re BLAKE2s key length:

      If the algorithm is "BLAKE2s-128",
      the length MUST be between 0 and 32 bytes inclusive, as described
      in [RFC7693].

Barbara

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Tue, 01 Dec 2020 00:26:09 +0100

>       the length MUST be between 0 and 32 bytes inclusive, as described

AFAICT, you are quite right! :)

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 01 Dec 2020 00:39:45 +0100

>       the length MUST be between 0 and 32 bytes inclusive, as described

That looks correct to me.