Subject: [sidr] multiply signed roas are useless

From: Randy Bush <[email-masked]>
Date: Mon, 06 Oct 2008 05:54:21 -0700

[ since my last message on this subject was not approved for posting to
  this list, i am inflicting myself directly on you.  apologies. ]

i am told that multiply signed roas are reappearing like whack-a-mole.
they are as operationally useful as gears on a fish, and serve only to
make it harder for the poor thing to swim.

the fantasy that receiving two aggregatable prefixes from two different
parents is as O(likely) as brownian motion causing all the molecules of
air in the room to rush into one corner and stay there,

and all the complexity it would produce in relying implementations would
save the announcement of one prefix in the global routing table.  wow!
just announce the two prefixes.  sheesh!

if it would save the over 50% pollution of the routing table by idiocy,
then i would leap to advocating it.  but one bleeping prefix, and with a
0.00001% probability at that?  you must be kidding.

is life not hard enough already?  notice how rirs' promises of delivery
have already slipped by years.  this is not easy stuff.  do everything
you can to simplify it, not complicate it.

and surely we can find better ways to amuse ourselves by complicating
things.  like how about we propose a second and less efficient protocol
for fetching repositories?

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

---

From: Geoff Huston <[email-masked]>
Date: Tue, 7 Oct 2008 09:40:17 +1100

My WG-Chair hat tossed into the corner for this posting....

On 06/10/2008, at 11:54 PM, Randy Bush wrote:

> I am told that multiply signed roas are reappearing  [...]

As I understand the substance of this post, the comment has been  
raised (again) that this is an unlikely situation and there is no need  
to make the specification more complex for unlikely cases.

In response I would argue (again) that the specification should be  
complete and provide appropriate guidance to implementors for all  
situations where interoperability is required, and this case, although  
not common, has been visible in the routing table already and will  
likely be visible in the routing table in future. Given that this does  
not define a new signature standard for CMS, nor a major change in the  
logic of ROA processing I do not see that this adds any undue  
complexity to implementations and has the benefit of covering the full  
range of anticipated use cases for ROAs in their application to  
signing route origination.

   Geoff

---

From: Randy Bush <[email-masked]>
Date: Mon, 06 Oct 2008 15:42:53 -0700

> raised (again) that this is an unlikely situation and there is no
> need to make the specification more complex for unlikely cases.
> 
> situations where interoperability is required, and this case,
> although not common, has been visible in the routing table already
> and will likely be visible in the routing table in future.

boiling the ocean is not necessary nor it is useful

> I do not see that this adds any undue complexity to implementations

do you just delete rob's mail unread?

randy

---

From: Rob Austein <[email-masked]>
Date: Mon, 06 Oct 2008 19:08:32 -0400

At Tue, 7 Oct 2008 09:40:17 +1100, Geoff Huston wrote:
> 
> ... I would argue (again) that the specification should be  

It adds a requirement that the validator, rather than doing a "simple"
tree walk, must now attempt to trace multiple paths through the tree
in order to check the signatures on the ROA.  This adds quite a bit of
complexity to the validation process, for no gain that I can see.
Unnecessary complexity in a security-sensitive piece of software is a
bad thing, so I have no intention of implementing this even if you do
get it into the specification.
_______________________________________________
sidr mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/sidr

---

From: Randy Bush <[email-masked]>
Date: Mon, 06 Oct 2008 16:10:47 -0700

> in order to check the signatures on the ROA.

s/multiple/an unconstrained number of/

randy

---

From: Terry Manderson <[email-masked]>
Date: Tue, 7 Oct 2008 09:12:30 +1000

Hi Randy,

On 06/10/2008, at 10:54 PM, Randy Bush wrote:

While sometimes I enjoy reading pointed rhetoric dismissing everyone  
else's view of the world, I'll skip it for today thanks.

> for fetching repositories?

Thanks for the deeply considered response to the sidr-fetch draft -  
gosh I'm assuming that is the draft you are targeting in your comment.  
I'd hate to misread your intention.

Do you have any other comments you would like to share? Perhaps in  
line with what the draft is trying to achieve in terms of utility,  
security, scalability, integrity .. and any other "ity" words we might  
like to bring up, like compatibility..

.. and yes I do find many things amusing.

Cheers
Terry

---

From: Geoff Huston <[email-masked]>
Date: Tue, 7 Oct 2008 10:34:19 +1100

WG chair hgat off

On 07/10/2008, at 10:08 AM, Rob Austein wrote:

>> although

Rather rather than a single check that the single certificate in the  
<certificates> field of the Signed Data type is valid this becomes a  
iterative loop that invokes the validation procedure for each  
certificate in the <certificates> field of the Signed Data type.  
Faiure at any stage is failure of the validation procedure. So far I'm  
not seeing complexity.

Rather than a single pass through step 1 of the algorithm specified in  
section 3 of the draft there is a loop for each SignerInfo instance n  
the CMS. Again I'm not seeing complexity here.

step 2 of that process is also repeated for each EE certificate rater  
than a single call.

step 3 requires that the IP addresses in the collection of the EE  
certificates be merged into a single set before the "encompass" test  
is performed Without specifying the algorithm in detail here, I cannot  
see that this is a complex piece of code.

Step 4 is repeated for each EE certificate, as noted above. Again I'm  
not seeing complexity here.

>  This adds quite a bit of
> complexity to the validation process,

If one assumes that iterative loops are complex then I could readily  
agree with this assertion. But I've never found them complex myself.

Geoff

---

From: Randy Bush <[email-masked]>
Date: Mon, 06 Oct 2008 16:42:15 -0700

it is not necessary.  it is not operationally useful.  it adds
complexity to a security application.

is there a netowrk operator here who really needs it?

and we have already heard from the major open source full system
implementor, who does not plan to add it.

randy

---

From: George Michaelson <[email-masked]>
Date: Tue, 7 Oct 2008 09:46:27 +1000

Randy, all our objects are now defined in terms of CMS.

CMS defines a multiple sign model. Its integral to the definition of  
CMS.

If we defined a multiple sign model for our data objects now, then we  
effectively future proof the design against any emergent need to have  
multiple sign over objects to validate them for RFC3779.

This is a remarkably low barrier right now, in a world of single sign.  
it is designing a data model to encompass a potential future need.

I do not believe one implementors view on optimal processing defines  
the scalability of multiple signer checking: for instance, a DB  
centric model would have no particular problem locating the set of  
direct signers, and in a pre-validated certificate hierarchy, (ie the  
covering trees for each certificate already being known) the edge- 
validation of the object by the EE certificates which signed it, which  
can be validated against the DB seems to me to be scaleable.

-George

---

From: Geoff Huston <[email-masked]>
Date: Tue, 7 Oct 2008 11:19:22 +1100

WG Chair hat off:

But I've said all this already, so nothing new from me either yet.

In a (possibly futile) effort to break out of this cycle of mindless  
repetition, here's a further contribution looking at what text would  
change in the ROA specification draft-ietf-sidr-roa-format to allow  
this proposed resolution to the issue:

section 2.1.4

...the end entity certificate(s) needed to validate this ROA.

section 3

   step 1 d. ... contains one or more EE certificates, where each EE  
certificate's Subject Key Identifier (SKi) matches the sid field of  
one instance of the SignerInfo object.

section 3

   step 2    ... in each EE certificate ...

section 3

   step 3   ... and that the union of the IP address prefix(es) in the  
EE certificate(s) extension(s) encompass the Ip address prefix(es) in  
the ROA.

section 3

   step 4   ... that each EE certificate is...

section 3

    Remove the sentences starting with "Note that ..." and "Indeed,  
since ..."

section 4

    ...  are encompassed by those in thge address space extension(s)  
in the EE certificate(s) used to sign the ROA.

   Geoff

---

From: Randy Bush <[email-masked]>
Date: Mon, 06 Oct 2008 17:21:29 -0700

> situations where interoperability is required,

boiling the ocean.

> and this case, although not common, has been visible in the routing
> table already

oh?  and how do you detect it?  how many are there?  how much of a real
problem is it?

randy

---

From: Rob Austein <[email-masked]>
Date: Mon, 06 Oct 2008 22:23:14 -0400

I look forward to reading your code, Geoff.

The process of retrieving and checking an RPKI tree is already a
fairly complex recursive tree walk with many fiddly checks that have
to be done in the right order to avoid various attack scenarios.  The
last thing this traversal algorithm needs is a gratuitous requirement
that at each ROA it finds it must be prepared to go haring off after
an arbitrarily large number of new certificate chains in different
parts of the tree on a pointless quest to solve a non-problem.

Do you have ANY evidence whatsoever for compelling real world cases?
Don't talk theory.  Show me a real case where this would matter.
_______________________________________________
sidr mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/sidr

---

From: George Michaelson <[email-masked]>
Date: Tue, 7 Oct 2008 12:33:31 +1000

clearly, I am not Geoff.

But in any case, I don't understand why you only analyze the costs of  
this test in the context of complete chain-validation tests,  
validating signed objects.

Why can you not test signed objects and the EE certificates against a  
*pre-validated* information structure for the hierarchy, and so only  
have to test the EE cert, and object validation at one level, instead  
of completely to the root?

what am I mis-understanding about end-sign validation?

I don't believe at this time that any multi-sign outcomes would exist  
except at the edge: end-entity objects.

so I don't see why an entire tree-validation is needed, if you have a  
pre-validated repository of known good certificate chains. The end- 
entity certs, the signed objects, surely the validation is far simpler  
than you imply?

> Do you have ANY evidence whatsoever for compelling real world cases?

post rundown, the likelihood that resources do not compress simply to  
single certificate chains seems to me a likely scenario. ie, people  
will be holding large sets of dis-aggregated resources, and need to  
assert route validation over them effectively.

if they do this as a set of disjoint end objects you move validation  
costs to a simpler process per object, that then has to be  
(re)combined to make the real information you need.

If we can find a way to make multi-sign work, there could be  
significantly less objects in play, in the system as a whole.

Rob, I don't mean to be dis-respectful, but I find the vehemance "this  
can't work: its too expensive" over-stated. I don't buy it. I think  
you're at risk of entrenching a view that is as equally shakey as my  
belief multi-sign may turn out to be needed.

> Don't talk theory.  Show me a real case where this would matter.

Its hard for anyone to do that in a world where no routing security  
exists. But I am tempted to observe that in the WG discussions we  
seemed to be confident the *intended* security model in respect of IRR  
demanded more than one participant sign information to validate the  
relationship between AS in routing, and prefix being routed. (I do not  
mean ROA here, I am talking about things beyond the ROA. So I have  
moved the agenda sideways)

I know that others believe this is irrelevant, but I still see it  
documented in the RFCs and in the actual code which implements checks  
on who authorizes updates in WHOIS..

cheers

-George

---

From: "Vishwas Manral" <[email-masked]>
Date: Tue, 7 Oct 2008 14:15:00 +1100

Hi Rob/ George,

I had raised issues about SIDR and we had a long healthy discussion on
it in February on the SIDR as well as the OPSEC lists.

I had written a draft too but I guess it did not get promoted enough.
Do have a look at :

www.archivum.info/[email-masked]/2008-02/msg00035.html and let me know
what you think about the ideas of the draft.

Thanks,
Vishwas

---

From: Rob Austein <[email-masked]>
Date: Mon, 06 Oct 2008 23:24:47 -0400

> what you think about the ideas of the draft.

No offense, but I see no relevance to the topic at hand.
_______________________________________________
sidr mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/sidr

---

From: Geoff Huston <[email-masked]>
Date: Tue, 7 Oct 2008 14:33:11 +1100

WG char hat off

On 07/10/2008, at 1:23 PM, Rob Austein wrote:

> parts of the tree on a pointless quest to solve a non-problem.

What I understand from your posting is that this makes ROA validation  
horrendously complex. An algorithm that attempts to validate  
everything at a repository publication point before moving on to the  
next repository publication point will have problems with any form of  
multi-signed object. On the other hand an algorithm that validates  
certificates (and CRLs) in a first pass and signed objects in a second  
pass would not encounter the same problems, as the collection of ee  
certificates required to validate the multisigned object would be  
already validated in the first pass.

So is what I'm hearing here from your posting: "I implemented it one  
way and if the draft is changed then my code will need to change, and  
I really don't want to do that, therefore I'm opposed to any change in  
the draft"?

But in that case there is a problem here for this type of algorithm in  
validating any form of multi-signed object, not just ROAs.

What about proxy aggregation in BGP? How can one validate any element  
that is constructed from a set of components other than by multo- 
signed objects? How are those multi-signed objects to be validated?

What about if one wanted to implement the RPSS security framework  
where the analogous security mechanism to the Route Object is that the  
AS holder and the prefix holder sign the route object? How are those  
multi-signed objects to be validated?

What about an AS adjacency attestation that is signed by both AS's?  
How are those multi-signed objects to be validated?

What about a generic form of AS Path validation where the credentials  
are progressively signed by the sequence of AS's?  How are those multi- 
signed objects to be validated?

Is what you are really voicing here an opposition to any form of  
multiple RPKI signatures being placed on any signed object within this  
framework? If that's the case I _personally_ see that as a very short- 
sighted limitation, a I for one see multiple signatures in the RPKI as  
being a valuable attribute in the long run in terms of the flexibility  
of the PKI to suit a broad as possible number of potential areas of  
application including BGP itself.

    Geoff

---

From: Geoff Huston <[email-masked]>
Date: Tue, 7 Oct 2008 15:07:55 +1100

> what you think about the ideas of the draft.

WG Chair HAT *ON*

Vishwas,

Thanks for your pointer and the reference you the draft you had  
written earlier this year.

The charter of the SIDR working group (http://www.ietf.org/html.charters/sidr-charter.html 
) includes the following:

"Document specific routing functionality modules within this
architecture that are designed to address specific secure routing
requirements as they are determined by the RPSEC Working Group"

To date, the RPSEC Working Group has concluded that securing the  
origination of routing advertisements IS a secure routing requirement,  
and on that basis the SIDR Working Group has been working on  
mechanisms that will allow the origination of route objects to be  
secured. The work on ROAs in precisely focused on this requirement.

The comments you reference, and the draft you cite, appear to point to  
a requirement relating to AS path security, and the specification of  
mechanisms that would allow relying parties to detect efforts by third  
parties to place false information into the AS Path of a routing  
advertisement. This precise nature of this requirement has been the  
subject of an extended study in the RPSEC Working Group, and the  
precise security requirements arising from that study are still  
somewhat unclear at the moment. I refer you to the RPSEC Working Group  
and its drafts and mailing list archives for more details on this  
study. At this stage it is my understanding, as a co-chair of the SIDR  
Working Group, that the general subject of AS Path validation has not  
yet been passed over to SIDR as a well-defined security requirement  
from the RPSEC Working Group, or from the Area Director in the form of  
a revised charter for this Working Group.

At some stage its likely that this will be part of the SIDR WG  
activities, and your contributions regarding effective and secure  
mechanism to safeguard the AS Path from various forms of unauthorized  
alteration would be welcome. However, before you brush up your  
previous draft and resubmit it, you may find some broad background  
reading on this topic to be helpful to your contribution, as the topic  
of securing the inter-domain routing system is one that has been the  
subject of a considerable number of research and operational papers as  
well as the subject of various efforts in the IETF and elsewhere over  
the past decade or so.

kind regards,

  Geoff Huston

   This time speaking as the co-chair of this Working Group

---

From: Randy Bush <[email-masked]>
Date: Mon, 06 Oct 2008 23:24:31 -0700

> oh?  and how do you detect it?  how many are there?  how much of a real

so i had a three hour drive from seeing kids in portland to the exciting
westin colo in seattle.  i did not even make it through the neil young
on my ipod.  but i kept thinking of how one could test or demonstrate
your assertion.  perhaps neil scrambled my thinking, but it did not even
get to winterlude.

for each prefix in some routing table, rv, dump of one of my routers,
whatever, see if that prefix can be decomposed into two or more prefixes
which one can demonstrate are 'given' to the announcing asn by two or
more different would-be certificate authoritiess, e.g. rirs or disparate
delegatees of rirs.

i could not really see how to do this for other than the case where the
prefix can be shown to be in the delegation registries of two rirs.

please give us one example which supports your assertion, or whack me
with a clue by four about how one could better test/demonstrate your
assertion.

randy

---

From: Brian Dickson <[email-masked]>
Date: Tue, 07 Oct 2008 02:48:14 -0400

> with a clue by four about how one could better test/demonstrate your

Let me ask Geoff about the specific kinds of scenarios, to simplify
things a bit. (I'm curious, too.)

Would the visible examples be adjacent prefixes (suitable for
aggregation) originated by one specific ASN?

Or, would the visible examples be adjacent prefixes from two ASNs, being
*proxy* aggregated by a third ASN?

Or some other variation involving one or two ASNs?

Try as I might, I am unable to figure out any way to split a block more
than one way.

And for two blocks to be able to be aggregated (without covering other
prefixes, i.e. not a proxy aggregate for any third parties), they have
to be adjacent.

Which means the two entities giving those blocks, would have to give the
*whole* block (in both cases) to the recipient, with nothing left over
for the giver or the giver's other customers.

A=CIDR(x/n) -> B=CIDR(x/n+1) + C=CIDR(x+foo/n+1)
RIR split A, gives B to Bob and C to Carol. Bob gives B to Dave, and
Carol gives C to Dave. Dave can now join B+C to get A again.
Nothing else works, unless B is passed down through Eric, Franz, and
Greg, and C is passed down through Harriet, Ian, and James. In each
case, without taking anything from B or C.

Is this known to have happened, and is it visible in the routing table??

Brian

---

From: Randy Bush <[email-masked]>
Date: Tue, 07 Oct 2008 00:09:09 -0700

apologies.  before someone over 40 catches me, i 'fess up that i was
wrong.  the cut i wanted was winterlong, not winterlude <blush>.  and i
did not get to cortez the killer either.

and i still have not figured out how to demonstrate/test your assertion.

randy, who clearly is not having a very good night
_______________________________________________
sidr mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/sidr

---

From: Geoff Huston <[email-masked]>
Date: Tue, 7 Oct 2008 19:22:40 +1100

WG Chair hat _OFF_

> aggregation) originated by one specific ASN?

yes

> *proxy* aggregated by a third ASN?

yes - I had a quick scan through the routing table this afternoon and  
saw two
potential instances of this.

> Or some other variation involving one or two ASNs?

I do not believe
> Is this known to have happened, and is it visible in the routing  

If you have a detailed look at the RIR's stats files you find that the  
older address space is somewhat fragmented across RIRs. If you also  
try and take into account a certain amount if NIR fragmentation what  
you have is the basic set of prefixes and their associated  
certification path.

Now construct this table of allocations for every day for the past,  
say year.

Then pull the set of all BGP updates for the same period (route views  
is a decent source of all such updates over the past year)

Now look up each updated prefix in the relevant daily table and see if  
the prefix fits within a single allocation space.

Report anomalies.

There may be more efficient approaches.

   Geoff

---

From: Geoff Huston <[email-masked]>
Date: Tue, 7 Oct 2008 19:42:55 +1100

WG Chair hat _OFF_

> randy, who clearly is not having a very good night

A source of a relatively complete set of individual allocations can be  
retrieved from http://bgp.potaroo.net/stats/nro/delegated

then take a large set of updates and examine each prefix - the Route  
views update archive is a good source

and then perform a lookup into the individual allocation list for each  
updates / withdrawn prefix

and report anomalies that straddle multiple allocations

is one way to understand the level of historical occurrence.

There could be other approaches of course.

Geoff

---

From: Randy Bush <[email-masked]>
Date: Tue, 07 Oct 2008 05:25:38 -0700

> is one way to understand the level of historical occurrence.

again, could you give us one or two examples of this actually occurring,
an asn aggregating prefixes from multiple rirs, i.e. what not having
multiply signed roas would preclude?

you did say "and this case, although not common, has been visible in the
routing table already."

randy

---

From: Stephen Kent <[email-masked]>
Date: Tue, 7 Oct 2008 11:13:34 -0400

Vishwas,

I replied to your message from Feb 27, back in that time frame.  I noted that:

	- the RPKI is the first step toward providing better BGP security
	- the SIDR WG understands the limitations of using ROAs for origin
	  AS validation (vs. full path validation)
	- both the soBGP and the SBGP proposals rely on a PKI of the sort that
	  the SIDR work is standardizing
	- use of ROAs and the RPKI allows one to more readily distinguish
	  between benign errors and malicious attacks, which is valuable

I don't think that your 1-page I-D is a useful characterization of 
the motivation for the SIDR work, or the residual secruity issues to 
be addressed after the RPKI foundation is standardized.   I do think 
we should make sure that the SIDR architecture document capture these 
issues, e.g., in the secruity considerations section.

Steve

---

From: Geoff Huston <[email-masked]>
Date: Wed, 8 Oct 2008 07:47:25 +1100

WG Chair hat off

> you did say "and this case, although not common, has been visible in  

I did say that and I based that comment on my earlier work in  
constructing the BGP report and looking at aggregation possibilities  
in the routing table and figuring out why the code was failing for  
certain advertised prefixes (its always the bugs that are more  
interesting than the working code). That was over 4 years ago, and  
after correcting (!) the code not to look for such cases where the  
prefix straddled across allocation boundaries I've not had to go back  
there again until this conversation.

So if you are after current examples, then its a case of  
reconstructing the code and running through the routing updates again.  
It may be some weeks before I can get around to this task personally.  
Others may be better situated to perform such an investigation in a  
faster timeframe.

   Geoff

---

From: Brian Dickson <[email-masked]>
Date: Tue, 07 Oct 2008 16:54:23 -0400

> there again until this conversation.

Even historical examples from 4 years ago, if you can find the prefixes
in question and other attributes, would be very interesting to most
folks, I believe.
(Most of us have access to the old data too, so we can look at the
then-relevant state of the world as relates to those prefixes.)

If you have them handy, that is.

Brian

---

From: Randy Bush <[email-masked]>
Date: Tue, 07 Oct 2008 14:16:31 -0700

the data are broken in the first place.  there are duplicate entries!

% grep ipv4 delegated | awk 'BEGIN {FS="|";} {print $4}' | sort | uniq
-c | grep -v '  1 '
   2 132.11.0.0
   2 132.17.0.0
   2 156.112.0.0
   2 156.113.0.0
   2 192.52.232.0
   2 192.94.234.0
   2 193.194.128.0
   2 193.227.128.0
   2 194.9.64.0
   2 194.9.82.0
   2 195.234.185.0
   2 195.234.252.0

randy

---

From: Geoff Huston <[email-masked]>
Date: Wed, 8 Oct 2008 08:45:00 +1100

WG Chair hat off

> If you have them handy, that is.

I did not think that they were interesting at the time, and never kept  
any records (yeah, I'm too slack! :-( ) - so its a case of getting out  
the BGP update microscope and doing it all over again.

   Geoff

---

From: Geoff Huston <[email-masked]>
Date: Wed, 8 Oct 2008 09:00:33 +1100

WG Chair hat OFF

> % grep ipv4 delegated | awk 'BEGIN {FS="|";} {print $4}' | sort | uniq

Yes, I agree that the RIR allocation data is imperfect as well, so the  
summary file of the union of the RIR's data is also imperfect in terms  
of uniqueness. :-( Obviously, his does not make the task easier.

    Geoff