Subject: Re: [saag] Fate of BFD extended authentication mechanisms

From: Stephen Farrell <[email-masked]>
Date: Thu, 7 Jul 2016 19:01:05 +0100

Folks,

Is there anyone who'll be in Berlin who'd be able to take a few
minutes to chat with Jeff and friends about bfd security?

We're often quite rightly scathing when folks develop protocols
in the IETF that have no or not well designed security and in
this case Jeff is asking for help to try avoid that bad outcome
and hoefully lead to the kind of good outcome that we security
folks keep on saying is what's needed.

If you're willing to meet Jeff and co for a chat/beer/coffee in
Berlin please drop Kathleen or I a line and we'll send the right
set of intros.

In case it helps, I think this could be an interesting enough
challenge - iiuc bfd is trying to amortise crypto costs over a
bunch of messages in the face of pretty tight performance
constraints.

Anyway, we'd really appreciate if if someone could help out here,
Thanks in advance,
S.

On 24/05/16 20:24, Jeffrey Haas wrote:
> Security-folk,
> 
> Partially as a response to work concluded in the KARP Working Group, there
> was previously some effort to enhance the cryptographic authentication
> mechanisms present in BFD.  The core BFD protocol is described in RFC 5880,
> including its authentication mechanisms.
> 
> The two main documents covering this work are below:
> 
> https://tools.ietf.org/html/draft-ietf-bfd-generic-crypto-auth-06
> https://tools.ietf.org/html/draft-ietf-bfd-hmac-sha-05
> 
> To somewhat tritely summarize the work in these two documents, the generic
> doc provides for:
> - Increase the number space of authentication sequence number to 64 bits
>   from 32.
> - Provide a larger numbering space for key identifiers, from 8 bits to 16
>   bits.
> - Re-using this structure for all future types rather than making it a
>   property of the individual authentication section for a given mechanism.
> 
> The hmac-sha doc describe SHA-2 variants of ciphers.
> 
> In general, these are understood to be the Right Things to do for BFD.
> However, lack of interest in the industry from either vendors or customers,
> and lack of drive from within the working group have contributed to these
> documents going stale.
> 
> There is also the secondary issue that as a result of the speed at which BFD
> operates and the fact it is often operating under extremely constrained
> compute resources, even existing ciphers are not well deployed in spite of
> the known weaknesses in the strength of those ciphers.  There is a separate
> effort beginning in BFD that may mitigate these issues, but I have requested
> the authors of that draft to contact the security area separately to discuss
> their proposal:
> 
> https://datatracker.ietf.org/doc/draft-ietf-bfd-optimizing-authentication/
> 
> Now to my question:
> 
> It's generally understood that implementations of security mechanisms often
> lag their specifications.  It's also generally understood that you want
> those specifications to exist because when you need them, it's possibly
> already too late.
> 
> Given this, I'm looking at options to help drive the BFD generic crypto and
> hmac-sha document to publication.
> 
> As mentioned, the interest in the BFD WG is low.
> 
> My question is what is the perceived status of security related documents
> that are on the Experimental track?  
> 
> For these documents to progress on the standards track, they'd have to have
> some likelihood of being deployed.  That point is, as above, unclear.
> 
> -- Jeff
> 
> _______________________________________________
> saag mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/saag
>

---

From: Alan DeKok <[email-masked]>
Date: Thu, 7 Jul 2016 15:21:00 -0400

> minutes to chat with Jeff and friends about bfd security?

  I should be there, barring last-minute surprises.

  I've talked with Jeff in passing before about BFD.  I've implemented RFC 5880, and have been on the mailing list for a while, but unable to keep up with recent activity.

> Berlin please drop Kathleen or I a line and we'll send the right

  Count this as my interest.

> bunch of messages in the face of pretty tight performance

  Hmm... 

https://tools.ietf.org/html/draft-ietf-bfd-optimizing-authentication-01

   Authenticating every BFD [RFC5880] packet with a Simple Password, or
   with a MD5 Message-Digest Algorithm [RFC1321] , or Secure Hash
   Algorithm (SHA-1) algorithms is computationally intensive process,
   making it difficult if not impossible to authenticate every packet -
   particularly at faster rates.

  What "faster" rates are required here?  As a case in point, RADIUS requires that each packet be authenticated via MD5, and possibly HMAC-MD5.  Sometimes both.  Commodity hardware is easily capable of doing 10Kpps.  I've managed to get 500Kpps with dedicated implementations.  Even older hardware (2000 era or so) was easily able to reach 2Kpps without much engineering effort.

  Alan DeKok.

---

From: Watson Ladd <[email-masked]>
Date: Thu, 7 Jul 2016 20:03:50 -0700

>   What "faster" rates are required here?  As a case in point, RADIUS requires that each packet be authenticated via MD5, and possibly HMAC-MD5.  Sometimes both.  Commodity hardware is easily capabl…

You want speed? Ask Cisco about GCM. Or Intel about GCM. Yes, these
require nonces, but they can also be used with both keys the output of
a PRF applied to a much longer nonce, and thus make a random nonce
safe. (The risk of collision is for a single value of H: changing the
key solves the problem). For commodity CPUs without binary multipliers
Poly1305 is a viable solution, as discussed in RFC 7539. It would be
nice to know what hardware we are thinking of.

If these haven't been considered yet, they should be.

---

From: Sam Hartman <[email-masked]>
Date: Fri, 08 Jul 2016 00:57:15 -0400

>>>>> "Watson" == Watson Ladd <[email-masked]> writes:

    Watson> You want speed? Ask Cisco about GCM. Or Intel about
    Watson> GCM. Yes, these require nonces, but they can also be used
    Watson> with both keys the output of a PRF applied to a much longer
    Watson> nonce, and thus make a random nonce safe. (The risk of
    Watson> collision is for a single value of H: changing the key
    Watson> solves the problem). For commodity CPUs without binary
    Watson> multipliers Poly1305 is a viable solution, as discussed in
    Watson> RFC 7539. It would be nice to know what hardware we are
    Watson> thinking of.

Not surprisingly, this has been hashed to death already.  When the BFD
security analysis team brought their findings to KARP, all of this was
discussed.  Plenty of people who are well aware of counter-mode-based
MACs as well as other fast MAC solutions discussed BFD in great detail.
I don't remember the specific conclusions--there were lots of tradeoffs
involving existing hardware, and constraints on what changes could be
made.  However, this is a case where asking questions rather than
jumping in with a solution is far more helpful.  I'd suggest one of your
first questions should be a request for pointers to the extensive
discussions including the BFD security analysis draft.

---

From: Jeffrey Haas <[email-masked]>
Date: Fri, 8 Jul 2016 15:53:08 -0400

[Choosing this message as my reply point.]

>   What "faster" rates are required here?  As a case in point, RADIUS requires that each packet be authenticated via MD5, and possibly HMAC-MD5.  Sometimes both.  Commodity hardware is easily capabl…

RADIUS won't get unhappy with you if you ignore it for 10ms.

It's likely obvious to all on this mailing list that with sufficient CPU,
it's possible to send N 3.3ms BFD packets using a given MAC mechanism in a
given slice of time.

To properly implement BFD, you'll be sending those N packets every 3.3ms.
In the absence of meticulous crypto mode in BFD, you don't have to do
anything other than I/O.  Once you do need to do meticulous crypto mode in
BFD, CPU must be spent on the MAC.

Given a CPU of a particular size, and I/O taking a known amount of time,
it's pretty easy to figure out what the maximum number of 3.3ms sessions you
could support if you were doing nothing other than BFD.  

The issue is line card CPUs are never doing just BFD.

The problem BFD developers are facing is how to do the most work in the
available amount of time slice they can be given for the BFD task along with
everything else, and schedule things sufficiently such that BFD sessions are
maintained without issue.

This resource scheduling issue really isn't the item up for debate here.
The constraints a given implementor faces in trying to write their code will
depend on environment, OS and other things.  However, it does mean that
trying to work on this problem from the standpoint of "the crypto isn't
expensive" isn't a good starting point for our problem.  It's expensive
enough that it simply isn't getting deployed in existing hardware.  Future
hardware is of course amenable to different tradeoffs.

-- Jeff

---

From: Jeffrey Haas <[email-masked]>
Date: Fri, 8 Jul 2016 15:57:30 -0400

On Thu, Jul 07, 2016 at 08:03:50PM -0700, Watson Ladd wrote:
> For commodity CPUs without binary multipliers

To pick a random example, feel free to consider an MPC8548 clocked at around
1Ghz.

-- Jeff

---

From: Alan DeKok <[email-masked]>
Date: Fri, 8 Jul 2016 16:18:25 -0400

> RADIUS won't get unhappy with you if you ignore it for 10ms.

  Very true.

> maintained without issue.

  I've gone back and read RFC 7492.  The latency and load requirements are clearly laid out there.

> hardware is of course amenable to different tradeoffs.

  The question then becomes what crypto will be adequate, while still meeting the latency / load requirements.

  I'll do some more reading and research.  We can get together in Berlin.

  Alan DeKok.