Subject: [Sidr] Question about draft-ietf-sidr-roa-format-03.txt

From: Geoff Huston <[email-masked]>
Date: Tue, 15 Jul 2008 06:49:49 +1000

Hi,

In reading draft-ietf-sidr-roa-format-03.txt with the changes to the ROA format arising from the last WG meeting, I was wondering if there was a "canonical form" for a ROA, or not.

e.g. If I have a ROA that includes

10.0.0.0/8, maxlength=32
and
10.0.0.0/24 maxlength=32

then obviously the second entry is redundant. 

Also there are more "compressed" formats and less "compressed" formats

e.g.

10.0.0.0/8 maxlength=8
10.0.0.0/9 maxlength=9

could be "compressed" to

10.0.0.0/8 maxlength=9

My question is: is it of any value to define a "canonical" format for a ROA? 

Is there an obvious answer to this question that I am missing? 

Would you like to lead a WG discussion of  this question at the SIDR WG meeting, as an agenda item?

regards,

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

---

From: Rob Austein <[email-masked]>
Date: Mon, 14 Jul 2008 18:30:43 -0400

At Tue, 15 Jul 2008 06:49:49 +1000, Geoff Huston wrote:
> 
> In reading draft-ietf-sidr-roa-format-03.txt with the changes to the
> ROA format arising from the last WG meeting, I was wondering if
> there was a "canonical form" for a ROA, or not.
> 

Yes.

> Also there are more "compressed" formats and less "compressed" formats

No.  10.0.0.0/8-9 isn't 10.0.0.0/8,10.0.0.0/9.

10.0.0.0/8-9 is 10.0.0.0/8,10.0.0.0/9,10.128.0.0/9.

This stuff is trickier than it looks.

ABNF for those who haven't seen the above text notation before:

  <ROAIPAddress> ::= <address> "/" <prefixlen> [ "-" <maxLength> ]
			; Where <maxLength> defaults to the same
			; value as <prefixlen>.

  <ROAIPAddressList> ::= <ROAIPAddress> *( "," <ROAIPAddress> )

> My question is: is it of any value to define a "canonical" format

Perhaps, but the definition would likely be hard to get right and
harder to implement.  The only real definition I can think of would
involve computing the union of the set of prefixes expressed by each
prefix-maxLength pair, then attempting to compute some kind of minimal
expression of that set.  This also begs the question of whether it's
an error to specify a redundant set of prefix-maxLength pairs.

I suspect that in the vast majority of cases there will not be any
useful canonicalization to be performed, ie, the output of the
canonicalization function will end up being the same as the input.

In the absence of a useful definition of canonicalization, my own
implementation just includes the prefix-maxLength pairs as specified
by the user.
_______________________________________________
Sidr mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/sidr

---

From: Stephen Kent <[email-masked]>
Date: Tue, 15 Jul 2008 10:12:15 -0400

>WG meeting, as an agenda item?

A canonical format is required for any signed object. ASN.1 will 
yield a canonical rep for the ipAddressBlocks SEQUENCE, but that is a 
different from the higher level canonical rep you're asking about. 
There the advantage to having such a rep is to better enable 
comparisons between the values in the ROAs and the associated EE 
certs. There is also the matter of being able to match BGP UPDATE 
prefixes against these values.

Prior to adding the max prefix length value, we had a canonical 
representation algorithm, based on the one defined for RFC 3779 
address extensions. The only issue is how that changes based on the 
inclusion of the maxlength parameter. I think we can define a new 
canonical representation by making an arbitrary decision about how to 
represent a given value when the use of the explicit maxlength value 
might introduce ambiguity. I'll leave the details for Matt to work 
out when he returns from vacation ;-).

Steve

---

From: Stephen Kent <[email-masked]>
Date: Tue, 15 Jul 2008 10:58:34 -0400

Rob,

Geoff's question was about representing data in ROAs.

The ABNF you cite is for RPSL, right? This has become a complicated 
discussion because the max length parameter is taken from RPSL, but a 
ROA does not directly represent RPSL. Moreover, as I noted in my 
message to Geoff, one thing we do with a ROA is to check that the EE 
cert used to verify the signature on a ROA authorizes the assertion 
made by the ROA. So, we have to begin by comparing the ROA address 
prefixes against the RFC 3779 address ranges in the EE cert. That 
motivates the adoption of a canonical (at a high level) 
representation for these prefixes, augmented by the max length 
parameter.

So, we have to deal with two external data sources simultaneously: 
3779 extensions in the EE cert and the RPSL-inspired max length 
parameter. Also, after we have validated a ROA, we will use it to 
generate RPSL, so we have to keep that in mind as well :-).

Steve

---

From: Rob Austein <[email-masked]>
Date: Tue, 15 Jul 2008 11:28:01 -0400

> Geoff's question was about representing data in ROAs.

I know.

> The ABNF you cite is for RPSL, right?

No.  It's a text format that a friend and I cooked up in order to have
a way to write down ROA prefix lists as ASCII text, since some of us
need such a format in our implementations and it seemed potentially
useful to have one generally agreed upon text format rather than
having each implementation invent a new one.
_______________________________________________
Sidr mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/sidr

---

From: Stephen Kent <[email-masked]>
Date: Tue, 15 Jul 2008 11:53:07 -0400

>having each implementation invent a new one.

Oh, now I'm really confused. Geoff gave an example motivated by data 
from a ROA, and used a syntax for his example. I didn't see where 
Geoff indicated that the syntax he used in his example was the one 
you and a fried cooked up, vs. anything else.

Steve

---

From: Rob Austein <[email-masked]>
Date: Tue, 15 Jul 2008 12:15:43 -0400

> you and a fried cooked up, vs. anything else.

I know that the authors of the ROA specification have seen the text
syntax I was using before, because it was after seeing that ABNF that
one of your co-authors decided to make the maxLength field optional in
the ROA ASN.1.

But perhaps, rather than arguing about notation, it might be more
useful to go back to my response to Geoff, now that you understand
that I was talking about ROAs, not RPSL.
_______________________________________________
Sidr mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/sidr

---

From: Stephen Kent <[email-masked]>
Date: Tue, 15 Jul 2008 13:34:33 -0400

>one of your co-authors decided to make the maxLength field optional in

I am one of the two active co-authors, and I didn't remember it :-).

>But perhaps, rather than arguing about notation,

Agreed.

>it might be more

My response was in the the part of my previous message that you 
elided in your response.

Steve

---

From: Geoff Huston <[email-masked]>
Date: Thu, 17 Jul 2008 06:58:34 +1000

>> there was a "canonical form" for a ROA, or not.

[...]
> an error to specify a redundant set of prefix-maxLength pairs.

Well the middle of that paragraph is an algorithm, to be sure, but is it
the same as the specification of a "canonical form"?

To put it in a slightly different way, what I wondering was is there a
means of specifying this "minimal expression" you refer to?

> canonicalization function will end up being the same as the input.

My intuition about use cases leads me to a different conclusion, but
its all speculation at this stage, of course.

My question was motivated by working through some interface issues in
terms of tools to manage ROAs, and the concepts of comparison operators
and equivalence came up. I was wondering how to compare the address part
of ROAs for equivalence and from this I was lead to the question of
canonical representations, since at some point you either have to fully 
expand (this could be potentially yicky - 10.0.0.0/8-24 would be a relatively
large set I guess) or fully compress the ROA into some "canonical form" in 
order to undertake the  comparison operation.

regards,

  Geoff

---

From: Jeffrey Haas <[email-masked]>
Date: Wed, 16 Jul 2008 23:07:53 -0400

> My question is: is it of any value to define a "canonical" format for a 

I don't think it adds much in the way of value to enforce this within
the ROA.  The noise it adds is harmless.

-- Jeff

---

From: Robert Loomans <[email-masked]>
Date: Thu, 17 Jul 2008 14:03:42 +1000

>> My question is: is it of any value to define a "canonical" format for a 

I believe that we should have a canonical form for the resources in a 
ROA, and that we mandate that form in the ROA.

If you cannot define a canonical form, how do you define equivalence?

(Yes, you can define equivalence algorithmically, but that algorithm is 
essentially a method for deriving a canonical form...)

Are we saying we don't need a definition of equivalence?

> the ROA.  The noise it adds is harmless.

Having a canonical form can reduce the number of interoperability 
problems and makes writing test cases easier.

Rob

-- 
Robert Loomans                                  Email: [email-masked]
Senior Software Engineer, APNIC                 Phone:   +61 7 3858 3100
http://www.apnic.net                              Fax:   +61 7 3858 3199
_______________________________________________
Sidr mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/sidr

---

From: Robert Kisteleki <[email-masked]>
Date: Thu, 17 Jul 2008 09:13:29 +0200

> Are we saying we don't need a definition of equivalence?

Can you give an example of where this would be useful?

Robert

---

From: Rob Austein <[email-masked]>
Date: Thu, 17 Jul 2008 04:02:34 -0400

> the same as the specification of a "canonical form"?

Almost certainly not, since the whole point of the maxLength parameter
in the ASN.1 is to avoid having to specify the full expansion of the
set of prefixes in the ROA.

> means of specifying this "minimal expression" you refer to?

Aye, that is the question.  I've tried to specify an algorithm for
this twice already, and failed both times.  I have a third approach in
mind as I type this, dunno yet whether it'll work, and I haven't even
gotten to the point of trying to optimize this.  I'm not saying this
can't be done, but it's significantly harder than figuring out whether
a ROA covers a particular prefix or figuring out what RFC 3779
resources a certificate must contain to cover a ROA.

> order to undertake the  comparison operation.

As Jeff and the other Robs have been discussing, there's some question
of whether one actually needs an equivalence operation; more
precisely, whether one needs an efficient equivalence operation.

Absent somebody being very clever, either the ROA producer or the ROA
consumer will have to perform the icky expansion, whether to generate
the canonical form or to do the comparision.  If equivalence tests are
an operation that we expect consumers to need to do frequently, it
makes sense for the producer to do the work of generating a canonical
form.  But it's far from clear to me that ROA equivalence per se is an
important operation for the consumer.  If most consumer don't care,
perhaps we should leave the work to the few consumers that do care.
_______________________________________________
Sidr mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/sidr

---

From: Jeffrey Haas <[email-masked]>
Date: Thu, 17 Jul 2008 08:51:46 -0400

On Thu, Jul 17, 2008 at 04:02:34AM -0400, Rob Austein wrote:
> this twice already, and failed both times.

Unless I have missed something about the subtleties of an ROA, the
prefixes contained therein are of the form:
<prefix> [maxlen <n>] | n >= prefix-length.

Given any two prefixes, A and B of the above form where A has the
shorter prefix length:
If prefix A covers prefix B and
maxlength A >= maxlength B
Then A completely covers B and B is redundant.

If prefix A covers prefix B and
maxlength B > maxlength A
Then B has a portion of it's address space that is not covered by A.

Given the above, you can pair-wise compare each prefix and eliminate
redundant prefixes.  (Insert common optimizations of pre-sorting by
prefix length, etc.)

I'd honestly just expect implementors to toss the prefixes into a prefix
trie and not worry about the redundant nodes.

> precisely, whether one needs an efficient equivalence operation.

The main concern would be someone's ROA having so much noise in it that
it's consider a resource exhaustion attack.  Given that people would be
using these things to say "hey, I want traffic to reach my network!" it
seems less than likely that someone would intentionally try to do that,
especially since the response is to blacklist the ROA.

-- Jeff