Subject: Re: [sidr] [Idr] draft-ymbk-bgp-extended-messages-01

From: Robert Raszuk <[email-masked]>
Date: Thu, 14 Apr 2011 13:13:12 +0200

> no.  it is telling the edge site, your paying customer, that they can
> secure their prefix without upgrading hardware.

Can anyone in IDR or SIDR demystify for us here what securing BGP really 
requires (certificates, signatures, attestations you name it)  if to 
secure a single prefix originated by customer site requires more then 4K 
of BGP message size ?

We already know that update packing is gone and that there is going to 
be single NLRI per update. OK or NOK but a different debate for 
different time.

But if securing 1 prefix really requires more then 4K of data attached 
to it I think we should question the entire approach rather then waist 
time to argue about draft-ymbk-bgp-extended-messages. Well unless this 
secure BGP is the only reason for this draft ;-).

Thx,
R.

---

From: Stephen Kent <[email-masked]>
Date: Fri, 15 Apr 2011 11:46:24 -0400

At 1:13 PM +0200 4/14/11, Robert Raszuk wrote:
>Can anyone in IDR or SIDR demystify for us here what securing BGP 
>really requires (certificates, signatures, attestations you name it) 
>if to secure a single prefix originated by customer site requires 
>more then 4K of BGP message size ?

BGPSEC calls for each AS hop along a path to sign AS path info. 
Although the average path length is a bit less than 4 hops, there are 
some very long paths that appear in FIBs, e.g., over 20 hops. The 
desire to increase the max UPADTE size (from the current 4K limit) is 
intended to accommodate very long paths. The principle contributor to 
the size increase is the digital signature. If on users RSA, each 
signature would be at least 1K bytes, and might be 2K bytes, 
depending on the key length size chosen. So, a 20-hop path could 
yield a 20-40K set of sigs, independent of the other path security 
data.

The good news is that many long paths contain repeated AS#s, which 
could be collapsed into a single signature. But, that optimization 
has not yet been
explored. Also, if we were to use DSA or ECDSA as a signature 
algorithm, instead
of RSA, the signature size could drop to 128 or 256 bytes, from 1-2K, 
a savings of a factor of 4-8. Still, a 20-hop path, with no repeats, 
might not fit in a 4K UPDATE, with all of the other secruity data.

Hope that explanation helps.

Steve

---

From: Robert Raszuk <[email-masked]>
Date: Fri, 15 Apr 2011 17:58:49 +0200

Hi Stephen,

This is really great explanation. I did try to find this in some papers
and your slides but I could not.

So it confirms that even if we use "worse case" BGP update advertised by
customer to provider (1 hop only case) it will fit within 4K limit
easily. Of course for any subsequent advertisement we need increase the
message size and this is where the draft-ymbk-bgp-extended-messages
addresses the issue.

One sentence in your reply is still not clear:

> If on users RSA, each signature would be at least 1K bytes, and might
> be 2K bytes, depending on the key length size chosen. So, a 20-hop
> path could yield a 20-40K set of sigs, independent of the other path
> security data.

- What is the maximum key length possible and how big would be the RSA 
signature with such key length ?

- What are the other path security data and what their size might be 
min-max.

Many thx again,
R.

>>> no. it is telling the edge site, your paying customer, that they
>>> can secure their prefix without upgrading hardware.
>>
>> really requires (certificates, signatures, attestations you name
>> it) if to secure a single prefix originated by customer site
>> requires more then 4K of BGP message size ?
>
> has not yet been explored. Also, if we were to use DSA or ECDSA as a
> signature algorithm, instead of RSA, the signature size could drop to
> 128 or 256 bytes, from 1-2K, a savings of a factor of 4-8. Still, a
> 20-hop path, with no repeats, might not fit in a 4K UPDATE, with all
> of the other secruity data.
>

---

From: Stephen Kent <[email-masked]>
Date: Fri, 15 Apr 2011 15:12:12 -0400

Robert,

First let me apologize as I accidentally put in "bytes" where I meant 
"bits" in the examples I provided. Whoops!  RSA 2K keys are 2K bits, 
i.e., 256 bytes (not 2K bytes). And, 2K RSA sig is the default, as 
this matches the key sizes we have already agreed upon for the RPKI 
certs. Still, a 20-hop path with RSA 2K (bit) sigs exceeds the 4K 
(byte) max UPDATE size, without any other overhead.  Sorry for the 
confusion.

>
>- What is the maximum key length possible and how big would be the 
>RSA signature with such key length ?

There is no max key size, but it does not make sense to push for bigger RSA
key sizes, instead of moving to more efficient (in space and 
computation) sig algorithms. The sig size for RSA is the same size as 
the key.

The likely sucessor algs are DSA or EC-DSA, which use smaller keys, 
but offer secruity equivalent to the larger RSA key sizes. The key 
sizes for those algorithms yield 128 or 256-bit sigs, under current 
hash algs.

>- What are the other path security data and what their size might be min-max.

I defer to Matt Lepinski for the details of the other data, as he is 
the author of the BGPSEC protocol doc.

Steve

---

From: Geoff Huston <[email-masked]>
Date: Sat, 16 Apr 2011 06:09:10 +1000

On 16/04/2011, at 5:12 AM, Stephen Kent wrote:

> Robert,
> 
> First let me apologize as I accidentally put in "bytes" where I meant "bits" in the examples I provided. Whoops!  RSA 2K keys are 2K bits, i.e., 256 bytes (not 2K bytes). And, 2K RSA sig is the default, as this matches the key sizes we have already agreed upon for the RPKI certs. Still, a 20-hop path with RSA 2K (bit) sigs exceeds the 4K (byte) max UPDATE size, without any other overhead.  Sorry for the confusion.
> 
>> 
>> - What is the maximum key length possible and how big would be the RSA signature with such key length ?
> 
> key sizes, instead of moving to more efficient (in space and computation) sig algorithms. The sig size for RSA is the same size as the key.
> 
> The likely sucessor algs are DSA or EC-DSA, which use smaller keys, but offer secruity equivalent to the larger RSA key sizes. The key sizes for those algorithms yield 128 or 256-bit sigs, under current hash algs.
> 
> I defer to Matt Lepinski for the details of the other data, as he is the author of the BGPSEC protocol doc.

I was doing a similar mental sum in my head and 256 bytes per sig is not a lot. As far as I am aware the only other added per-AS part of the attribute is the SKI of the public key. Presumably this is also 256 bytes.

SO thats 500 bytes per AS, and for a 20 AS path thats 10K in additional data.

Is my back of the envelope anywhere near in the right ball park?

Geoff