Subject: [sidr] about "beaconing" and the bgspec-protoocol

From: "Murphy, Sandra" <[email-masked]>
Date: Fri, 7 Dec 2012 19:38:17 +0000

>From comments made at the mike in the last IETG sidr session after the discussion of key rollover techniques, I think there might be a bit of confusion about beaconing.

An Expire Time was a feature of the bgpsec protocol in versions 00-01.  The purpose of the Expire Time  was to prevent replay and ensure freshness.  The effect of this feature was to require periodic readvertisements of all prefixes, hence the name "beaconing".

Based on wg discussions, "beaconing" was removed from the bgpsec protocol in versions 02 (Mar 12) forward.

Protection against human time scale replay, e.g., from neighbor relationships that change, was suggested to be possible through the use of key rollover.

--Sandy, speaking as co-chair

---

From: Danny McPherson <[email-masked]>
Date: Fri, 7 Dec 2012 18:24:00 -0500

> Protection against human time scale replay, e.g., from neighbor relationships that change, was suggested to be possible through the use of key rollover.

I'm pretty sure the captured proceedings for "Discussion of Key Rollover Mechanisms for Replay-Attack Protection" [!=beacon?] mentions "beacon" at least eleven times.  Additionally, "BGPSEC router key rollover" was about periodic updates (aka "beacons") as well.

Folks can name them periodic updates, or beacons, or even stretch and call them triggered updates if you want.  Adding new attributes to standards-track BGP that require a "refresh" function through *some* new attribute by the origin AND independently by each transit AS (and perhaps each BGPSEC-enabled BGP router therein) under the auspices of "key rollover" rather than "freshness" is, well, still pretty much the same thing functionally - they're still periodic updates in a soft state protocol that don't exist in BGP today.

I still contend that doing anything to introduce periodic updates in the global inter-domain routing system is a terrible idea and is something we should avoid altogether.  Even [ripv1-rfc1058] provides some hints as to why this is a bad idea.

I know we're focusing on hyper-deduced stuff here, but the combinatorial effects of orders of magnitude larger updates in BGP through BGPSEC proposals, breaking and effectively disabling the ability for BGP update packing anywhere, considerable added churn through origination and transit node-triggered "beacons", and added processing overhead for cryptographic functions for signing and validation, all in today's BGP, sure makes me real concern about our goals and if the reward outweighs the risk here.

I highly recommend that these documents be experimental and people playing with this stuff in BGP do so in closed environments, not on routers attached to the global routing system; it's fragile enough as is.

-danny

[!=beacon?] http://www.ietf.org/proceedings/85/slides/slides-85-sidr-4.pdf
[ripv1-1058] http://tools.ietf.org/html/rfc1058

---

From: "Sriram, Kotikalapudi" <[email-masked]>
Date: Sat, 8 Dec 2012 09:25:14 -0500

> I'm pretty sure the captured proceedings for "Discussion of Key Rollover Mechanisms for Replay-Attack Protection" [!=beacon?] mentions "beacon" at least eleven times.  Additionally, "BGPSEC router…

Semantically, Beaconing = Periodic re-origination of prefixes

Beaconing (i.e., periodic re-origination) was an attribute of the explicit Expire Time method, 
and it IS an attribute of the periodic key rollover (PKR) method as well.
However, beaconing (periodic re-origination) IS NOT an attribute of the Event-driven Key Rollover (EKR) method. 
This is all fairly well documented in [draft-sriram-replay-protection-design-discussion]:
 
http://tools.ietf.org/html/draft-sriram-replay-protection-design-discussion-00 

and also in my presentation slides from the Atlanta IETF SIDR session:
  
http://www.ietf.org/proceedings/85/slides/slides-85-sidr-4.pdf

Periodic key rollover (PKR) is currently recommended in [draft-ietf-sidr-bgpsec-rollover] 
as evident from the following quote (from Section 4.2):

  “For  this reason, it is recommended that routers in this scenario been
   provisioned with two certificates: one to sign BGP UPDATES in transit
   and a second one to sign BGP UPDATE for prefixes originated in its
   AS.  Only the second certificate (for prefixes originated in its AS)
   should be rolled-over frequently as a means of limiting replay attach
   windows.  The transit BGPSEC certificate is expected to be longer
   living than the origin BGPSEC certificate.”

In the PKR method, the "current" origination cert (and key pair) expires at periodic intervals 
and updates are re-originated signed by the "next" origination cert.
No CRLs need to propagate; the cert expiry is automated by setting NotValidAfter time,
and the "next" cert is always pre-provisioned well in advance. 
None of it is tied to human scale intervention -- it can all be automated.

In the same section (section 4.2) , the authors also observed:

“Advantage of Re-keying as replay attack protection mechanism:
  	 1.  Does not require beaconing”

However, that advantage #1 is not correct for the periodic key rollover method, which is currently recommended. 

>
> considerable added churn through origination and transit node-triggered "beacons", and added processing overhead for cryptographic functions for signing and validation, 
>

Just to clarify, *transit* prefixes are not beaconed (i.e., not "periodically" re-propagated)
by *transit routers* in any of the key rollover methods.
The PKR method has periodic re-origination of origination prefixes only 
(i.e., each eBGP router periodically re-originates its origination prefixes).
The EKR method by definition is event-driven, hence does not entail any periodic re-originations. 
The events (topology changes, etc.) are presumably rare/infrequent. 

Sriram

---

From: "Murphy, Sandra" <[email-masked]>
Date: Mon, 10 Dec 2012 14:38:05 +0000

>I'm pretty sure the captured proceedings for "Discussion of Key Rollover Mechanisms for 
>Replay-Attack Protection" [!=beacon?] mentions "beacon" at least eleven times.

And hence the confusion.

Sriram's presentation was about strategies of doing key rollover, not a protocol feature.

>Adding new attributes to standards-track BGP that require a "refresh" function through *some* 
>new attribute by the origin AND independently by each transit AS (and perhaps each 
>BGPSEC-enabled BGP router therein) under the auspices of "key rollover" rather than 
>"freshness" is, well, still pretty much the same thing functionally - they're still periodic updates
 >in a soft state protocol that don't exist in BGP today.

One of the strategies Sriram mentioned involved key rollover at regular intervals.  The other strategies do not change keys regularly.

The new attribute does not have a required refresh function.  It uses crypto and any use of crypto requires the ability to change keys.  

The strategy for changing the crypto keys is an individual decision of the ISPs, not a protocol feature.  ISPs may decide to change keys at regular periods, or they may not. (And reports of current ISP behavior wrt TCP MD5 keys seems to be that they currently decide never to change keys at all, ironically.)  No one knows what ISPs will decide, so it is incorrect to describe the system effects of this one strategy out of many key rollover strategies as a feature of the protocol.

>I still contend that doing anything to introduce periodic updates in the global inter-domain routing system 
>is a terrible idea and is something we should avoid altogether.  Even [ripv1-rfc1058] provides some 
>hints as to why this is a bad idea.

Periodic updates are not introduced in this wg.  Periodic updates are not a feature of the protocol.  Periodic updates could arise only if everyone chose the regular interval key rollover strategy. There is nothing in this sidr work that forces that choice.   The strategy for changing keys is a function of the *individual* *independent* decisions by the ISPs.

Perhaps you would prefer it if the ops document discouraged the ISPs from choosing that particular key rollover strategy.

________________________________________
From: Danny McPherson [[email-masked]]
Sent: Friday, December 07, 2012 6:24 PM
To: Murphy, Sandra
Cc: [email-masked]
Subject: Re: [sidr] about "beaconing" and the bgspec-protoocol

-danny

---

From: Randy Bush <[email-masked]>
Date: Tue, 11 Dec 2012 02:17:56 +0900

> reports of current ISP behavior wrt TCP MD5 keys seems to be that they
> currently decide never to change keys at all, ironically.

currently, you would have to synch simultaneous config changes at both
ends of the wire, not reasonable.  and, instead of vendors doing the
simple hack of rfc 4808, we've been waiting five+ years for the promised
nirvana of tcp-ao.  a kewpie doll for the first person who can cite a
real deployed tcp-ao implementation.

randy

---

From: Danny McPherson <[email-masked]>
Date: Mon, 10 Dec 2012 14:51:24 -0500

On Dec 10, 2012, at 9:38 AM, Murphy, Sandra wrote:

> Periodic updates are not introduced in this wg.

Sandy, 
The very fact that this WG is putting forth new architectures that change BGP such that "key rollover" will need to be reflected in some manner directly in the routing system is indeed solely on this WG.  That's an architectural thing that does NOT exist today.

-danny

---

From: Danny McPherson <[email-masked]>
Date: Mon, 10 Dec 2012 14:58:55 -0500

> real deployed tcp-ao implementation.

And that's between adjacent BGP speaking routers for a single transport connection!

I can't wait until my prefix doesn't make it 'n' AS hops through the Internet because I used an origin or forward signing key in BGPSEC secure path bits and an RP (BGP router) upstream didn't have that particular validation key in their onboard state 'at the ready.  

-danny

---

From: "Murphy, Sandra" <[email-masked]>
Date: Mon, 10 Dec 2012 20:22:32 +0000

wrt:

>I can't wait until my prefix doesn't make it 'n' AS hops through the Internet 
>because I used an origin or forward signing key in BGPSEC secure path bits 
>and an RP (BGP router) upstream didn't have that particular validation key 
>in their onboard state 'at the ready. 

Keys on routers are not required for origin validation.

--Sandy, speaking as regular ol' member

________________________________________
From: [email-masked] [[email-masked]] on behalf of Danny McPherson [[email-masked]]
Sent: Monday, December 10, 2012 2:58 PM
To: sidr wg list
Subject: Re: [sidr] about "beaconing" and the bgspec-protoocol

-danny
_______________________________________________
sidr mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/sidr

---

From: Danny McPherson <[email-masked]>
Date: Mon, 10 Dec 2012 17:20:32 -0500

> Keys on routers are not required for origin validation.

They are required for validation of the origin ASes Signature Segment in the Signature_Block in the BGPSEC_Path attribute, no?  I.e., such that the SKI can be used by the recipients of the route advertisement to identify the proper certificate to use in verifying the signature?

And to be clear, we're talking about BGPSEC here, not "origin validation" as currently supported by the rpki-rtr protocol (that has no crypto machinery, just 'prefix,origin' bindings).

-danny

---

From: Danny McPherson <[email-masked]>
Date: Mon, 10 Dec 2012 19:48:34 -0500

>   living than the origin BGPSEC certificate.”

Note: There are two grammatical errors / typos in _that text fragment.

That said, 

> and updates are re-originated signed by the "next" origination cert.

OK, this IS _the new added churn I was referring to.  This doesn't occur in BGP today.

> The EKR method by definition is event-driven, hence does not entail any periodic re-originations. 

You're introducing a new "event" here that has an periodic expiry attribute, this IS _the new added churn I was referring to.  This doesn't occur in BGP today.

> The events (topology changes, etc.) are presumably rare/infrequent. 

"presumably rare/infrequent" != "does not occur". 

To that, how was it determined that "Transit cert can have a very large NotValidAter time", what requirement led to this? 

Again, we can repurpose and reapply terms for beacon/periodic/triggered/event-driven words all we want, but if an intermediate AS needs to retransmit an advertisement because it's forwarding signing "Transit cert" rollover; solely because of some refresh or expiry action related to key rollover then that's something that doesn't occur in BGP today, and yet another place where combinatorial effects of all these "capabilities" give me concern, and represent _the new added churn I was referring to.  This doesn't occur in BGP today.

Given, leaving the attack window larger for "transit certs" reduces churn, but it should lead one to question the broader objectives and implications.

Finally, all these options mean relying parties (i.e., BGPSEC routers) must have all the old and new (and future?) certificates onboard and know which to use at what time for validating which origin_as or transit signature blocks at what times.  As Randy points out, we have a hard enough time rolling keys between adjacent BGP speaking routers for transport connection protections.  What you're proposing gives me some real concern...

-danny

---

From: "Murphy, Sandra" <[email-masked]>
Date: Tue, 11 Dec 2012 17:33:38 +0000

>They are required for validation of the origin ASes Signature Segment

Apologies, I misunderstood your comment.  I read "an origin or forward signing key" as "(an origin) or (forward signing key)".  oops.

>And to be clear, we're talking about BGPSEC here, not "origin validation"

Yep.  Glad to be clear.

________________________________________
From: Danny McPherson [[email-masked]]
Sent: Monday, December 10, 2012 5:20 PM
To: Murphy, Sandra
Cc: sidr wg list
Subject: Re: [sidr] about "beaconing" and the bgspec-protoocol

-danny

---

From: Danny McPherson <[email-masked]>
Date: Fri, 7 Dec 2012 17:50:48 -0500

---

From: "Sriram, Kotikalapudi" <[email-masked]>
Date: Wed, 12 Dec 2012 20:19:04 -0500

>>  "For  this reason, it is recommended that routers in this scenario been
>>   living than the origin BGPSEC certificate."
>

The quote was from [draft-ietf-sidr-bgpsec-rollover] which is authored by Roque/Keyur/BrianW.
Hopefully, they will make note of your comment.

>
>> In the PKR method, the "current" origination cert (and key pair)
>> expires at periodic intervals and updates are re-originated signed by the "next"
>origination cert.
>
>> Just to clarify, *transit* prefixes are not beaconed (i.e., not
>> "periodically" re-propagated) by *transit routers* in any of the key rollover
>methods.
>> The PKR method has periodic re-origination of origination prefixes
>> only (i.e., each eBGP router periodically re-originates its origination prefixes).
>You're introducing a new "event" here that has an periodic expiry attribute, this
>IS _the new added churn I was referring to.  This doesn't occur in BGP today.
>
>To that, how was it determined that "Transit cert can have a very large
>NotValidAter time", what requirement led to this?

The taxonomy and details & design rationale of the different key rollover methods are 
fairly well explained in [draft-sriram-replay-protection-design-discussion] in Section 5. 

>
>Again, we can repurpose and reapply terms for
>beacon/periodic/triggered/event-driven words all we want, but if an
>intermediate AS needs to retransmit an advertisement because it's forwarding
>signing "Transit cert" rollover; solely because of some refresh or expiry action
>related to key rollover then that's something that doesn't occur in BGP today,
>and yet another place where combinatorial effects of all these "capabilities"
>give me concern, and represent _the new added churn I was referring to.  This
>doesn't occur in BGP today.
>
>Given, leaving the attack window larger for "transit certs" reduces churn, but it
>should lead one to question the broader objectives and implications.

Here you have the benefit of decent descriptions of the different methods,
their pros/cons etc. in [draft-sriram-replay-protection-design-discussion].
The churn is reasonably well modeled/quantified in my Atlanta presentation 
(slides 8 thru 11):
http://www.ietf.org/proceedings/85/slides/slides-85-sidr-4.pdf
Please let me know if you have specific questions about the analysis/data
on churn after taking another look at slides 8-11.
Please keep in mind that the churn triggered by an event such as
a topology change or a policy change happens even today in BGP-4.
So that type of churn is not new.
As for the *new* background churn in BGPSEC with *PKR*, 
we have shown that it is nearly two orders of magnitude less compared 
to today's BGP (when peak seconds are compared) as shown in slide 8
for a 24 hour replay-attack vulnerability window (in PKR).
So the additional churn in BGP due to the background churn of BGPSEC with *PKR*
is practically negligible (see slide 8 - note that the y-axis is logarithmic scale.)

Again, in [draft-sriram-replay-protection-design-discussion] we are not
advocating any specific choice of key rollover. It is a discussion document
and a companion to [draft-ietf-sidr-bgpsec-rollover]. 
The latter is planned to be a BCP and authored by Roque/Keyur/BrianW.  

>
>Finally, all these options mean relying parties (i.e., BGPSEC routers) must have
>all the old and new (and future?) certificates onboard and know which to use at
>what time for validating which origin_as or transit signature blocks at what
>times.

There should be no such confusion. Receiving router does not need to do any timing in this context.
At the signing router, the "next" cert becomes "current" cert when a key rollover happens.
The "current" cert becomes a previous cert.
The updates are always signed by the "current" cert.
The "staging", "twilight" etc. w.r.t to "current" and "next" certs propagation are streamlined 
(see Section 3.1 of [draft-ietf-sidr-bgpsec-rollover]).  

Also, please take a look at [draft-ymbk-rpki-rtr-keys]
https://datatracker.ietf.org/doc/draft-ymbk-rpki-rtr-keys/?include_text=1
RPKI cache sends {ASN, SKI, PubKey} data for all valid certs to RP routers,
and withdraws the same for any revoked/expired certs.
The updates carry ASN and SKI corresponding each signature.
The {ASN, SKI} combination maps uniquely to a router's PubKey.
So a BGPSEC router would be able to unambiguously pick the exact right PubKey 
needed to verify each signature in an update.
Assume the router has two updates - the signature in one update is signed 
using "current" cert of a router R1 and the signature in the second update is signed  
using "previous" cert of the same router (R1).
If both "current" and "previous" certs of the signing router (R1) happen to be valid 
at that time, the router can unambiguously find the correct PubKey to verify either signature. 
Eventually, the "previous" cert would be revoked or would expire, and then the second
update would be invalid. 

Sriram