Subject: [sidr] Keys and algorithms for Updates - feasibility analysis? (was Re: RPKI and private keys)

From: Brian Dickson <[email-masked]>
Date: Mon, 7 May 2012 14:58:31 -0400

At the interim meeting (30th of April 2012), I briefly discussed the
performance differential of doing something other than the proposed crypto,
for "signing" updates.

While the relative benefit I suggested, "100x - 1000x" raised some
eyebrows, it was something I thought worth exploring a bit further. It
turns out to be 7000x (to as much as 50,000x, depending on amount of
entropy desired.)

I did some simple benchmarks, to try to compare a very limited work-load,
apples-to-apples.

The test cases all presume everything/nothing regarding validation; I was
interested only in the absolute and relative workloads imposed by "signing"
when done by a bgpsec-speaker in sending to another bgpsec-speaker.

Any of the per-session (initialization overhead) was ignored, since that is
presumed only needed for setting up the initial state for the speakers'
session.

These test cases are designed to compare what is currently specified in the
-algorithms (and referenced via the -protocol) specs, to something based on
random data, where the latter would require some out-of-band method for
doing validation.

The results were a real eye-opener, and as such, I am hoping I'm not the
only one to have done this, and that there exists some of this kind of
testing, done previously.

So, what I'm asking is, have such results been published or shared to the
SIDR group, and if so, would someone please send me a link to them?

And if not, then maybe this is something that either needs to be discussed,
or is a big enough deal that I will feel obliged to work on my own stuff,
outside of SIDR.

Brian

Simple test results follow:
===================

Scenario 1:
perform basic update signature once, repeat for routing table of 400,000 in
size.
  signature operation:
     set message size to N bytes, representing size of previous sig, plus
added elements (receiver ASN, etc.)
     perform sha256 on message, producing digest
     perform ecdsa on digest, using secp256r1, producing signature

Scenario 1 platform: Macbook Pro late 2011, 15" (intel i7 single cpu,
dual-core, 8GB ram)
Scenario 1 results, estimated: 700 seconds

Scenario 2:
perform basic pseudo-signature once, repeat for routing table of 400,000 in
size.
  pseudo-signature operation:
     use N distinct pseudo-random number generators (PNRG), seeded
separately with state preservation (N=8 corresponds to 256 bits of entropy)
     call random() from each preserved state to generate a 32-bit random
number, concatenate the N x 32 bit values

Scenario 2 platform - same as Scenario 1
Scenario 2 results, estimated: 0.09 seconds

==================

While the 7000+ relative performance is pretty substantial, the absolute
time required is the deal-breaker.

Getting signatures attached to one copy of the routing table, being sent
over a single BGPSEC session, taking 700 seconds on modern commodity
hardware is beyond the pale.
And given that current generation hardware has CPUs at least an order of
magnitude slower, or possibly two orders of magnitude, suggests that
software-based bgpsec can never work.
The fact that bgpsec is strictly an overhead function, generating no
revenue, means that requiring hardware support for crypto is mandatory, for
every router in the signing path.

When this is contrasted with 0.09 seconds (for adding a high-entropy,
unique nonce, to every prefix on a copy of the full routing table sent over
a single session), the contrast is stark.

If alternatives to the heavy crypto have never been explored, maybe they
should be.

Yes, the OOB validation presents a challenge, for validation. But, given
that validation itself in the current protocol requires yet-to-be-designed
methods for getting certs onto routers (with the embedded public keys), I'm
not sure this is a de-facto valid criticism, or is at best hypocritical.

I suspect that while I may be participating as an observer in SIDR, without
looking at alternatives like this, the only real value I see in the work by
SIDR is the RPKI (and maybe rpki-rtr).

I do want to work on things that will provide protection against threats to
BGP.
However, the solution IMHO needs to be incrementally deployable, meaning on
existing classes of hardware.
And the threats need to include path shortening, route leaks, and
replay/withdrawl-blocking.

I'm not sure I expect responses from anyone in particular, but want to be
clear on where I see the important issues as lying.
If the work I'm interested in isn't something the WG wants to pursue,
that's okay - I'll pursue it on my own.

Regards,
Brian

---

From: Christopher Morrow <[email-masked]>
Date: Mon, 7 May 2012 16:29:16 -0400

I'm probably confused, or the example has been simplified.. but

> number, concatenate the N x 32 bit values

how do I check 3 as-hops away that whatever is attached to the update
means that the update was signed? you seem to be saying: "sign with
some random bytes that you make up on the fly".

-chris

---

From: Christopher Morrow <[email-masked]>
Date: Mon, 7 May 2012 16:52:33 -0400

> software-based bgpsec can never work.

for clarity, I think a 'normal':
 o 7200 these days ships with a 1ghz cpu
 o Cisco CRS ~2.13ghz Intel
 o Juniper M/T/MX ~2ghz Intel
 o Cisco 12000/XR (prp2 single-core, 3 dual-core) 1.3GHz PPC

None of these is an order of magnitude smaller than a desktop-cpu.
Even a 7500 with a 600mhzRISC is not an order of magnitude. (by the
mhz/ghz numbers at least, speedups in math done in assembly aside)

---

From: Brian Dickson <[email-masked]>
Date: Mon, 7 May 2012 16:56:30 -0400

The particulars are a bit vague at the moment, beyond a
back-of-the-envelope design.

For OOB validation, you need the following kinds of things:
- a validator box
- an auth-data source of truth
- some way of knowing that the source of truth is legitimate
- a way for the signing router to establish sync with the source of truth

The auth-data source-of-truth could have credentials in RPKI. (Actually,
this would probably be mandatory.)
The router and source-of-truth would need to have some scheme for seeding
PNRGs identically, e.g. using DH shared secret(s).
The source-of-truth would probably need a running feed of discarded nonces
(to avoid memory exhaustion), possibly via ordinals (N for Nth PNRG value,
rather than the value itself), possibly using RLE (run-length encoding).
The validator would need to talk to the source-of-truth, using a
query/answer type protocol, preferably with cacheable answers, preferably
over some secured channel (e.g. using DH shared secret).

So the process for validating 3 as-hops away would be something like:
- receive the nonced-update
- send the relevant bits to the OOB validator (locally operated cacheing
validator "box")
- wait for an appropriate answer from the OOB validator, mark according to
the answer received
- OOB validator can be treated as a modest-latency, high-bandwidth
black-box,maybe with some occasional jitter.

The validator would handle a feed per peering session, per router; how it
scales is a question of implementation, optimization, load issues, etc.
Cacheable answers yield benefits immediately, in terms of scaling behavior.

The validator would probably want to handle several aspects of its job in a
smart manner
- sensible behavior regarding latency to individual source-of-truth hosts
- sensible behavior in the face of network issues
- local optimizations intra-AS and even inter-AS for additional caching
- pre-loaded data for validation of cached data (e.g. KSK DNSKEYs for zones
if the validation uses DNSSEC, as an example.)
- sufficient number of answer "states" which can be interpreted in a
suitable fashion, like FAILED_VALIDATION, NO_ANSWER_YET, NO_ANSWER,
NOT_FOUND, ORIGIN_VALIDATION_FAILED, or VALID
- sane design regarding FIFO nature of BGP (mandatory) and head-of-line
blocking (bad juju)

Fundamentally, though, modulo caching logic, the validator would directly
query the source-of-truth for the ASN which is 3 as-hops away.

Brian

---

From: Brian Dickson <[email-masked]>
Date: Mon, 7 May 2012 17:00:55 -0400

Even at CPU parity, or even with modest N x CPU performance for single
digit N, same ballpark.
The expected performance once you load up the number of BGPSEC sessions,
add on churn, etc., is a lot worse.
And, my little laptop was basically idle, not doing all the other work that
a router CPU needs to do.

Brian

---

From: "Sriram, Kotikalapudi" <[email-masked]>
Date: Mon, 7 May 2012 20:14:35 -0400

Brian,

Thanks. I bring this back on the SIDR list as others may be having the same questions. 

I have no grasp of the details of your method based on crypto fundamentals yet,
but at a different level I have some performance questions based on the descriptions
that you have provided.

Per your explanation below, the validating router or the OOB validator is doing query/response per update.
That would entail one or more round-trip messaging delays (between the validating entity
and each of the signing ASes or "sources-of-truth") in the validation processing time of each update. 
These delays would need to be factored into processing speed estimate for update validation,
which may be slowed down considerably as a result. Would you agree?

For the signing speed, earlier you had estimated 400,000/(0.09 sec) = 4.4 million (approx.) signings per second.
Now you are saying, "Software-based signing at 10,000/sec is still able to produce
adequate results at very low costs."
What caused the drastic lowering of the signing speed estimate from 4.4 million to 10,000 per sec
(or perhaps I misunderstood something)?

Sriram 

>
>From: Brian Dickson [mailto:[email-masked]]
>Sent: Monday, May 07, 2012 6:21 PM
>To: Sriram, Kotikalapudi
>Subject: Re: [sidr] Keys and algorithms for Updates - feasibility analysis? (was Re:
>RPKI and private keys)
>
>Yes, per update.
>
>The router would spew its incoming updates (or pieces of them) to the OOB
>validator, who would be responsible for looking them up, doing retries/time-
>out/caching, etc.
>
>The router would not be doing the queries, per se. But it would pass on the bulk
>update data, and the validator would need to possible/probably do multiple
>queries per update.
>
>E.g. If there was a single update with AS path of "3 2 1"  (originated by AS 1), and
>nonces "N3 N2 N1", the router would send a request to the validator, saying
>"isvalid:3,2,1:N3,N2,N1", and the validator would then look up N3 at the source-
>of-truth for AS 3, as well as looking up N2 at AS 2's source-of-truth, and N1 at AS
>1's source of truth.
>
>Depending on how the system was built and operated, any number of things
>could optimize look-ups:
>- the OOB validator (for this router) might have cached values for any or all of N1,
>N2, N3
>- the lookup for N2 might start with asking the source-of-truth for AS 3, if that
>host had a cached value for N2
>- if a cached value is used, the cached value might need some other validation
>processing (e.g. DNSSEC validation, if the data is in DNS)
>
>DNS authoritative servers are known to be able to serve up data at rates >>
>100K/s.
>DNS hardware-based DNSSEC signers can sign-on-the-fly Even if an AS has a
>bunch of routers, and each router has a bunch of peers, the DNSSEC data would
>likely be served out of a single DNSSEC zone (simplifies signing considerably).
>Hardware-based signing with a small number of keys, with redundant hardware
>and redundant geographical locations, is a solved problem.
>Hardware modules can be configured to make keys unrecoverable, i.e. strictly
>kept inside the hardware, hardened against any kind of inspection.
>
>Managed (by a third party) DNS with DNSSEC is a viable option here. The signing
>of data does not require exposing the private key, if the private key is inside
>hardware and is not recoverable.
>
>Nobody queries the signing router directly, ever.
>
>The signing router sends a unidirectional feed of what range of current sequences
>are, and what updates have been over-ridden or withdrawn, over a secure
>channel to the "source of truth".
>
>The workload of the signing router is extremely small.
>The workload of the validator (OOB) is moderate, but scales well when handling
>multiple routers (since many of the updates will share some ancestry).
>The workload of the source-of-truth is also moderate, mostly because it is looking
>up fixed values in a hash table and quickly giving an answer.
>The scope of the source-of-truth is its own ASN, plus perhaps any other ASNs on
>whose behalf it is operating the service (third party customer).
>A validator would potentially need to have all the public keys of all the ASNs in
>existence, but that is not excessively large, and will generally not change much at
>all.
>The keys can either be pre-loaded, or cached as needed, depending on the
>performance characteristics of the local AS.
>
>The design is deliberately lightweight, and scalable. The traffic levels (packet/sec)
>might be low or high, the capacity offered performance-wise (to handle worst
>case scenarios) should be very high, and would be low cost.
>
>Hardware-based DNSSEC signing would be an optimization, not a mandatory
>requirement. Software-based signing at 10,000/sec is still able to produce
>adequate results at very low costs.
>
>Brian
>
>>On Mon, May 7, 2012 at 5:49 PM, Sriram, Kotikalapudi
>><[email-masked]> wrote:
>>
>>>The validator would need to talk to the source-of-truth, using a query/answer
>>>type protocol, preferably with cacheable answers, preferably over some secured
>>>channel (e.g. using DH shared secret).
>>
>>Brian,
>>
>>Are these query/answer per update?
>>Does the validating router make a query to each signing router (or AS) for each
>>update?
>>
>>Sriram

---

From: Brian Dickson <[email-masked]>
Date: Mon, 7 May 2012 21:50:23 -0400

> (or perhaps I misunderstood something)?
The router-side of things is just adding a nonce to each update. It is a
substitute for signing, but technically isn't signing.
That is the thing where 4+M/s is level-of-effort.

The source-of-truth, for example, if it is doing DNSSEC signing, would be
capable of 10K/s signatures, give or take.
Hardware of course massively improves this.

The point of the DNSSEC software signing is showing a low barrier to entry.
Where there is reason to go bigger, outsourcing or taking advantage of
already-owned DNSSEC hardware means marginal costs are lower too.

For a stub edge, what the stub would need to sign would be limited to its
own prefixes and its own customers' prefixes.

Also, the source-of-truth could, in theory, generate signatures before
deciding that they are ready to be "released".
It would be bending some of the rules for DNSSEC, in the interests of using
time vs space to its advantage, rather than falling behind during a burst
of new updates to sign.

E.g. 10,000/s x 400 seconds (working ahead of a burst) = 4M "in the pipe"
which would allow a 1s burst at peak router rate with no impact to system
performance.

As for round-trips - they only are an issue if the latency is severe, or if
there is head-of-line blocking.
If the lookup OOB validator is able to continue reading from the router's
queue and doing queries in parallel, the only time blocking would happen is
if there were persistent failures at the front of the queue.
This would be a reason for having more states to reflect lookup-failures,
rather than "validate" or "fail".
Caching would also be beneficial, since adjacent ASes (topologically
speaking) would likely share common nonces that need to be looked up in
short succession.

Thanks for the questions, and hopefully this helps clarify the distinctions
between nonces and signatures.

(Also, rather than traditional anonymous parties, where there is no trust,
having direct queries to source-of-truth over validated channels means it
would be feasible to skip the DNSSEC validation when getting a direct
answer. This leads to 100K/s or better levels, vs 10K/s.)

Brian

> >DNS authoritative servers are known to be able to serve up data at rates
> >>
> >100K/s.
> query/answer

---

From: "[email-masked]" <[email-masked]>
Date: Thu, 10 May 2012 09:35:23 +0100

Sriram

You can't get 10,000 signature creations and verifications a second on
a standard Intel core. You can get maybe 100.

Your colleagues who work on smart grid standards have experience of
this. The IEC working group assumed that all LAN traffic in
electricity substations could be authenticated by digital signatures.
This turned out to not work, and caused a major stall in the smart
grid security program. Some substation LAN traffic has a hard
end-to-end latency bound of 4ms, and that simply can't be achieved on
standard cores using 1024-bit RSA signatures. You need custom
hardware, which brings serious export control headaches as well as
significant costs. We wrote this up in

  http://www.cl.cam.ac.uk/~sf392/publications/S4-1010.pdf

Ross

On 08/05/2012, Sriram, Kotikalapudi <[email-masked]> wrote:
> _______________________________________________
> sidr mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/sidr
>

---

From: "Sriram, Kotikalapudi" <[email-masked]>
Date: Thu, 10 May 2012 09:05:04 -0400

Hi Ross,

The 10,000/s number is Brian Dickson's and
it is not related to ECDSA (or RSA) signing/verification of BGPSEC updates.

In my work on performance modeling of BGPSEC, I have used the basic
signing/verification measurement data from the eBACS benchmarking effort: 
http://bench.cr.yp.to/results-sign.html
The measurement numbers they report are in the same ballpark as yours for RSA signing.
However, the BGPSEC spec draft specifies ECDSA-P256, which is much faster than RSA-2048 for signing.
(Side note: ECDSA-P256 was also preferred because it results in a much lower size for BGPSEC updates
and hence lower router RIB memory size.
http://www.nist.gov/itl/antd/upload/BGPSEC_RIB_Estimation.pdf  )

Regarding how the eBACS measurement data were used to model BGPSEC CPU performance, 
please see:
http://ripe63.ripe.net/presentations/127-111102.ripe-crypto-cost.pdf
(slides 10 and 11 summarize signing/verification speeds for various latest Intel and Cavium processors)
or see,
http://www.ietf.org/proceedings/83/slides/slides-83-sidr-7.pdf
(slides 7 and 8).

The performance modeling and measurement work is still evolving and there is still ways to go 
w.r.t. prototyping of BGPSEC and measurements with actual signed updates, etc. 

Sriram

________________________________________
From: [email-masked] [[email-masked]]
Sent: Thursday, May 10, 2012 4:35 AM
To: Sriram, Kotikalapudi
Cc: Brian Dickson ([email-masked]); sidr wg list ([email-masked])
Subject: Re: [sidr] Keys and algorithms for Updates - feasibility analysis? (was Re: RPKI and private keys)

Sriram

Ross

---

From: "Murphy, Sandra" <[email-masked]>
Date: Fri, 11 May 2012 18:00:36 +0000

Before we get too involved in discussing performance and different methods of measuring performance, I think it is very important to address the features of what Brian is suggesting;

such as:

what security services are being supplied?
who is involved in the service - where is the service applied and where validated?
what is being protected?
what are the components and the architecture?

etc.

--Sandy, speaking as wg co-chair

________________________________________
From: [email-masked] [[email-masked]] on behalf of Sriram, Kotikalapudi [[email-masked]]
Sent: Thursday, May 10, 2012 9:05 AM
To: [email-masked]
Cc: sidr wg list ([email-masked])
Subject: Re: [sidr] Keys and algorithms for Updates - feasibility analysis? (was Re: RPKI and private keys)

Hi Ross,

Sriram

Sriram

Ross

---

From: Brian Dickson <[email-masked]>
Date: Fri, 11 May 2012 15:44:42 -0400

On Fri, May 11, 2012 at 2:00 PM, Murphy, Sandra <[email-masked]>wrote:

> Before we get too involved in discussing performance and different methods
> of measuring performance, I think it is very important to address the
> features of what Brian is suggesting;
>
>
Would you be so kind as to explain why you believe this is important? It's
not like the WG mailing list is overloaded or the participants doing much
(or even responding very much, it would seem.)
I was asked about this at the interim meeting, and there were many SIDR
participants who were not at the meeting (physically or remotely.) My
follow-up is pretty much required, just to inform the rest of the
participants.

We have not had, to the best of my knowledge, any (or much at all if there
was some) in-SIDR discussion of performance metrics on the proposed
mechanisms, when implemented in software, or when implemented in hardware.

It has been proposed that a roadmap timeframe of 5-7 years is acceptable,
in order that vendors provide hardware-based implementations. No
justification for this has been offered, beyond "well, it is common sense".

The requirements doc explicitly calls out hardware-based solutions as
acceptable, without any cost analysis or cost/benefit analysis, or absolute
performance metrics for requirements.

I think the starting point should have been previously, and in the context
of the current suggestions should be, performance numbers based on actual
experiments using the protocols in question (and alternatives where
alternatives have been suggested). In fact, the results from such testing
should help inform discussion on acceptable performance, and those
acceptable levels should be based on real-world observations of absolute
rates.

> what are the components and the architecture?

This can be addressed, for the moment, in a "Napoleon Dynamite" fashion.
- whatever is needed
- whoever wants to  & what do you mean by "service being validated"?
- bgp paths vs threats
- whatever they need to be, and whatever works

The basic thing here is, I'm asking the question, "Why is the heavy-duty
crypto needed?".
When I start using formal logic, I take a bunch of axioms, and rules based
off those axioms.
Then, take a hypothetical additional piece of logic (rule or assumption),
and see what it can be reduced to, in terms of which axioms or rules are
violated.

Working backwards, it appears the crypto is needed because all the
validation is based on information passed in-band.
Without the crypto, anyone can take part of another update, and forge
additions to it, or changes to it, trivially. (That's the case with vanilla
BGP, too.)

The additional assumption is, assume some OOB validation process, e.g.
suing an outside-of-BGP communication path of some sort.

And my question was, if we start the analysis by ignoring the details of
the OOB system, but merely presume it exists as an adjunct, what are the
minimum things we can do to tie into that system by adding _something_ to
BGP updates, and how does that change the performance (and thus cost) of
on-router stuff?

The reason it is fair to ignore the OOB element is, that unlike on-router
stuff, the possibility of achieving scaling benefits exists, since multiple
routers could conceivably use a shared OOB black box.

By definition, on-router stuff can't achieve scaling benefits of this sort.

And, also by definition, there is no requirement that the OOB component
look anything like the in-band stuff. The OOB could conceivably be anything
under the sun, and be implemented by any existing or new technology. It
could use DNSSEC, it could use IPSEC, it could use LDAP, it could use
Kerberos (how, I don't know, but it could), it could even use carrier
pigeons or SMTP or SNMP or quantum encryption.

And systemically, any number of topologies are possible, since they are not
fundamentally tied to the topology of the BGP infrastructure itself.

> --Sandy, speaking as wg co-chair

When you speak as wg co-chair, I think it is important to be clear on the
rationale for any attempt to moderate on-topic discussion. No offense
intended, but not providing rationale looks to WG participants as political.

Thanks,
Brian

> From: [email-masked] [[email-masked]] on behalf of Sriram,
> Kotikalapudi [[email-masked]]
> Subject: Re: [sidr] Keys and algorithms for Updates - feasibility
> analysis? (was Re: RPKI and private keys)
>
> Hi Ross,
>
> Subject: Re: [sidr] Keys and algorithms for Updates - feasibility
> analysis? (was Re: RPKI and private keys)
>
> Sriram
>

---

From: Christopher Morrow <[email-masked]>
Date: Fri, 11 May 2012 16:20:18 -0400

On Fri, May 11, 2012 at 3:44 PM, Brian Dickson
<[email-masked]> wrote:
> It has been proposed that a roadmap timeframe of 5-7 years is acceptable, in
> order that vendors provide hardware-based implementations. No justification
> for this has been offered, beyond "well, it is common sense".

I believe the timeframes take into account common larger-network
depreciation rates for equipment.
  core -> agg -> fastedge -> hinter-lands-edge -> gone

takes ~4-7 years... or so network folk had said (this came out in the
RAWS WG as well, in 2006)

-chris

---

From: "Murphy, Sandra" <[email-masked]>
Date: Fri, 11 May 2012 20:31:02 +0000

Answering a response to a statement made as wg chair

wrt:

Brian Dickson [[email-masked]] said on Friday, May 11, 2012 3:44 PM

>On Fri, May 11, 2012 at 2:00 PM, Murphy, Sandra 
><[email-masked]> wrote:
>
>
>>Before we get too involved in discussing performance and different 
>>methods of measuring performance, I think it is very important to 
>>address the features of what Brian is suggesting;

>Would you be so kind as to explain why you believe this is important? 

I believe that analyzing performance measures of a system is premature before its features are at least well enough established to understand that it meets the requirements and does not have systemic architectural drawbacks.

To choose an extreme example, for illustrative purposes only, the NULL algorithm has really wonderful performance measures, but would not suit the purpose.

Furthermore, it is difficult to know what performance to measure if the system is not understood to some degree.

--Sandy, answering as wg co-chair

From: Brian Dickson [[email-masked]]

Sent: Friday, May 11, 2012 3:44 PM

To: Murphy, Sandra

Cc: Sriram, Kotikalapudi; [email-masked]; sidr wg list ([email-masked])

On Fri, May 11, 2012 at 2:00 PM, Murphy, Sandra 
<[email-masked]> wrote:

Would you be so kind as to explain why you believe this is important? It's not like the WG mailing list is overloaded or the participants doing much (or even responding very much, it would seem.)
I was asked about this at the interim meeting, and there were many SIDR participants who were not at the meeting (physically or remotely.) My follow-up is pretty much required, just to inform the rest of the participants.

We have not had, to the best of my knowledge, any (or much at all if there was some) in-SIDR discussion of performance metrics on the proposed mechanisms, when implemented in software, or when implemented in hardware.

It has been proposed that a roadmap timeframe of 5-7 years is acceptable, in order that vendors provide hardware-based implementations. No justification for this has been offered, beyond "well, it is common sense".

The requirements doc explicitly calls out hardware-based solutions as acceptable, without any cost analysis or cost/benefit analysis, or absolute performance metrics for requirements.

I think the starting point should have been previously, and in the context of the current suggestions should be, performance numbers based on actual experiments using the protocols in question (and alternatives where alternatives have been suggested).
 In fact, the results from such testing should help inform discussion on acceptable performance, and those acceptable levels should be based on real-world observations of absolute rates.

such as:

what is being protected?

etc.

The basic thing here is, I'm asking the question, "Why is the heavy-duty crypto needed?".
When I start using formal logic, I take a bunch of axioms, and rules based off those axioms.
Then, take a hypothetical additional piece of logic (rule or assumption), and see what it can be reduced to, in terms of which axioms or rules are violated.

Working backwards, it appears the crypto is needed because all the validation is based on information passed in-band.
Without the crypto, anyone can take part of another update, and forge additions to it, or changes to it, trivially. (That's the case with vanilla BGP, too.)

The additional assumption is, assume some OOB validation process, e.g. suing an outside-of-BGP communication path of some sort.

And my question was, if we start the analysis by ignoring the details of the OOB system, but merely presume it exists as an adjunct, what are the minimum things we can do to tie into that system by adding _something_ to BGP updates, and how does that change
 the performance (and thus cost) of on-router stuff?

The reason it is fair to ignore the OOB element is, that unlike on-router stuff, the possibility of achieving scaling benefits exists, since multiple routers could conceivably use a shared OOB black box.

And, also by definition, there is no requirement that the OOB component look anything like the in-band stuff. The OOB could conceivably be anything under the sun, and be implemented by any existing or new technology. It could use DNSSEC, it could use IPSEC,
 it could use LDAP, it could use Kerberos (how, I don't know, but it could), it could even use carrier pigeons or SMTP or SNMP or quantum encryption.

And systemically, any number of topologies are possible, since they are not fundamentally tied to the topology of the BGP infrastructure itself.

When you speak as wg co-chair, I think it is important to be clear on the rationale for any attempt to moderate on-topic discussion. No offense intended, but not providing rationale looks to WG participants as political.

Thanks,
Brian

From: 
[email-masked] [[email-masked]] on behalf of Sriram, Kotikalapudi [[email-masked]]

To: 
[email-masked]

Hi Ross,

please see:

or see,

(slides 7 and 8).

Sriram

From: 
[email-masked] [[email-masked]]

To: Sriram, Kotikalapudi

Sriram

Ross

sidr mailing list

[email-masked]

sidr mailing list

[email-masked]

---

From: Brian Dickson <[email-masked]>
Date: Fri, 11 May 2012 17:19:03 -0400

While analysis of a completed system is valuable, it also requires analysis
of the components of the system.

If we want to consider any solution to the requirements, I believe we need
to perform analysis on the performance of the components, as well as of the
system, and validate that it meets the requirements.

So, when do you suggest doing that for the system and components specified
in the -protocol document and in the -requirements document?

If you aren't going to do that, then I suggest that doing analysis and
comparison on components is valid.

What I am looking at is exclusively the following elements:
(1) the signatures for the -protocol document (and _explicitly_ excluding
the validation steps, which will be necessary regardless of solution),
versus
(2) the nonces for my comparative performance suggestion (N bit nonces
constructed using N/32 independently generated PNRG 32-bit values (with
N/32 different seeds)).

Comparative analysis of the validation components and system of the
-protocol, along with suggested OOB methods (plural - once you go OOB you
have as many options as you want, and those aren't limited to ones already
suggested by me) are still going to be needed to do a complete comparison.

However, the results for (1) and (2) are likely to provide motivation for
the related follow-on work.

Your choice of NULL as a way of discrediting alternatives is quite telling.
What about the risks vs performance of CRC-32, or MD4, or ROT13?

Shared-key cyphers are well-known and have superb performance
characteristics with predictable risk. It is suitable for the purpose, IFF
the architecture avoids exposing key data.

You have already said that you presume (in the case of on-router private
key data) that key data would never be exposed.

So, does this mean we can now make similar assumptions about competing
architectures?

Or do you want to supply a legitimate risk analysis of key management
practices, predictable-text risks, entropy sources, etc., for the primary
SIDR proposal(s)?

Brian

P.S. The same argument for the incompletely specified proposals holds - the
SIDR bgpsec system is incompletely specified, so it follows there is no
reason to not allow competing (incompletely specified) proposals, certainly
not on the basis of being incompletely specified, nor on the basis of
quantitative benefits of system components.

On Fri, May 11, 2012 at 4:31 PM, Murphy, Sandra <[email-masked]>wrote:

> I believe that analyzing performance measures of a system is premature
> before its features are at least well enough established to understand that
> it meets the requirements and does not have systemic architectural
> drawbacks.
>
> To choose an extreme example, for illustrative purposes only, the NULL
> algorithm has really wonderful performance measures, but would not suit the
> purpose.
>
> alternatives have been suggested).
>  In fact, the results from such testing should help inform discussion on
> acceptable performance, and those acceptable levels should be based on
> real-world observations of absolute rates.
>
>
>
>
>
> such as:
>
>
>
> BGP updates, and how does that change
> could use DNSSEC, it could use IPSEC,
>  it could use LDAP, it could use Kerberos (how, I don't know, but it
> could), it could even use carrier pigeons or SMTP or SNMP or quantum
> encryption.
>
>
>
> And systemically, any number of topologies are possible, since they are
> not fundamentally tied to the topology of the BGP infrastructure itself.
>
>
>
>
>
>
>
> [email-masked] [[email-masked]] on behalf of Sriram,

---

From: Brian Dickson <[email-masked]>
Date: Fri, 11 May 2012 17:27:51 -0400

I was referring to the use of HW-based crypto (which is not cheap), not the
timeframe (5-7 years), as having lack of quantitative analysis on
cost/benefit, cost barrier to entry, or other supporting justification.
The argument that "we can't do the crypto without HW" is circular, when the
argument for crypto is "we can include the HW for crypto in the next
go-around of HW".
If crypto requires HW, the incremental cost needs to be considered, along
with justification that shows that the market will accept and fully adopt
HW crypto universally.
The premise is bgpsec requires universal adoption to have end-to-end
delivery of protection.
The deployment scenario where anything less than the vast majority of ASNs
do bgpsec, quickly devolves to negative cost-benefit.
If the only parties deploying bgpsec are a closed set of peers who already
trust each other and already do TCP-AO (aka MD5), the net benefit is zero.

So, who is going to write up the cost benefit, deployment model (inter-as),
and critical mass required document?
Or the market analysis (how many routers with this will be needed), vendor
survey with committed roadmap (when will this be available, on what
platforms)?
Or the export restrictions limitations to deployment (serious crypto
hardware being deployed to the state-department listed countries?) and/or
alternative vendor support?

Basically, if the assumption is HW crypto, please go the extra mile and
show that this assumption is based on verifiable "stuff", i.e. that this is
not just fantasy.

Brian

On Fri, May 11, 2012 at 4:20 PM, Christopher Morrow <[email-masked]
> wrote:

---

From: Christopher Morrow <[email-masked]>
Date: Fri, 11 May 2012 21:23:23 -0400

On Fri, May 11, 2012 at 5:27 PM, Brian Dickson
<[email-masked]> wrote:
> The argument that "we can't do the crypto without HW"

i didn't see anyone say that though.

---

From: Brian Dickson <[email-masked]>
Date: Mon, 14 May 2012 10:27:34 -0400

We can't do the crypto without HW on some of the routers involved in
deployment of bgpsec.

I've heard just about everyone say that, quite possibly including yourself.

One of the reasons for questioning the choice of crypto, is exploring the
feasibility of solutions which do not require on-router HW for doing
signing.

Brian

On Fri, May 11, 2012 at 9:23 PM, Christopher Morrow <[email-masked]

---

From: Christopher Morrow <[email-masked]>
Date: Mon, 14 May 2012 10:37:09 -0400

> I've heard just about everyone say that, quite possibly including yourself.

I don't think I've said that recently, one of the items brought out
during discussions of this was that often the hardware accelerators
for this are optimised for 'use one key a lot', not for 'swap in a new
key for every operation' (the key swap is very costly).

Sriram has some numbers for different co-processors which are
interesting, but I don't think that means we need on-board crypto
accelerators.

> feasibility of solutions which do not require on-router HW for doing

sure, but you also invented a whole other (seemingly complex) system
to keep track of data (nonces and such) across multiple
trust/administrative domains. it seems unwieldy, to me at least.

One of the larger stumbling blocks though is ram for RIB storage. (or
that seems to be one of the larger problems to address)

-chris

>
> Brian
>
>
> On Fri, May 11, 2012 at 9:23 PM, Christopher Morrow
> <[email-masked]> wrote:
>>

---

From: "[email-masked]" <[email-masked]>
Date: Mon, 14 May 2012 16:18:36 +0100

Hardware cryptoprocessors raise the issue of export licenses. They are
also expensive. There will have to be software alternatives.

If we want widespread adoption, there must be an option to "just turn
it on" without having to shell out a load of extra money and fill a
lot of forms.

Security usability means more than just a zero-marginal-cost software
implementation. It means easy setup of keys and certificates, and
probably the option of running in "advisory more" where verification
failures raise error messages but do not cause routes to fail. That
will enable ASes to try, watch, and gain the confidence to turn it on.

Who's looking at security usability?

Ross

---

From: Christopher Morrow <[email-masked]>
Date: Mon, 14 May 2012 12:48:24 -0400

> also expensive. There will have to be software alternatives.

the vendors who've been involved so far didn't mention
export-problems, but that's a fair thing to keep in mind. The cost is
also interesting, but on the other side of a 200k USD device, is the
coprocessor (if needed at all, and if ONLY used for this function) a
show stopper at 100 USD/item? (at 1000? what is an average cost
Sriram?)

> it on" without having to shell out a load of extra money and fill a

sure.

> failures raise error messages but do not cause routes to fail. That

I think in no case will the validation just drop a route, or the plan
so far has simply been adding an ability to mark an update with some
key (community, localpref, etc) and use that in determining what to do
with the route. If you can match on validity state you COULD simply
DROP the route, but I don't think that'll be the end state for a very,
very long time.

> Who's looking at security usability?

smb? would you like to help? :)
^^^ - probably others as well, but he's been a voice so far, as has mr turner.

-chris

---

From: "Montgomery, Douglas" <[email-masked]>
Date: Mon, 14 May 2012 13:16:34 -0400

>^^^ - probably others as well, but he's been a voice so far, as has mr

We have a usability group that has several projects underway on security.
Not this particular topic though.
http://www.nist.gov/itl/iad/vug/

Is there a specific usability question in this space to be posed?

Dougm

---

From: Wes Hardaker <[email-masked]>
Date: Wed, 23 May 2012 16:04:54 -0700

Brian Dickson <[email-masked]> writes:

Hi Brian,

I believe I understand your system as functionally creating an
BGPSEC_Path_Signatures attribute with a algorithm/signature set that is
based off of adding random numbers to the signature field(s) instead of
adding cryptographically generated hashes.  IE, we end up with something
like this being received by a RP:

  |----------------------|
  | AS Number 1          |
  | Random Bytes from #1 |
  |----------------------|
  | AS Number 2          |
  | Random Bytes from #2 |
  |----------------------|
  | ...                  |

This obviously greatly simplifies the diagram from the -protocol
document section 3, but is sufficient for the discussion.  The point
being is that the BGPSEC_Path_Signatures is a list of ASes that the
update has gone through.  Roughly.

Now, I'm all for updating the signature field to the fastest
cryptography that meets the goals.  We just need to agree on what the
goals are, and how the resulting system is subject to attacks against
those goals.

So, lets consider a few things first:

1) A random number generation using a PRF is an interesting concept.
   And you're right, that if you assume a OOB cache that can verify the
   results is available, it'll offload much of the computation from the
   RP router.  It's a worthy goal.  [However, I'd argue that you could
   do that without changing the crypto as well; though it may still be a
   goal to lower the crypto cost of the OOB cache machine anyway]

2) A random number generator can only be compared against an existing
   system in turns of speed if it provides a similar amount of security,
   or the reduced security is an acceptable trade off for the speed
   gain.  So, let me start with the concept of generating a nonce from a
   32 bit generating PRF (or, as you stated, N instances of a 32 bit
   PRF).  

   The problem with a 32 bit PRF and repeating it N times is that you
   don't get 32*N bits of entropy.  You only get 32 bits.  Specifically,
   if I'm given M random number Rs that were concatenated into a nonce,
   what do I have to do in order to predict the next 32*N bit field?
   Functionally, I need to figure out the original seed so that I can
   calculate the next 32*N bit field.  But to calculate all the N
   fields, I really only need to sweep through the entire 32 bits
   looking for each of the N values, and work backward to the seed.

   Using a single 2.4GHz i7 core, I calculate it would take me 1.4 hours
   to search the entire 32bit space of random numbers looking backward
   for a seed.  And much of that time is devoted just to initializing
   the random number generator, as producing 4 random numbers from a
   single seed (say you want to drop the first bunch of random numbers
   so it's harder for me to work backward) doesn't really help much, as
   the time needed only jumps to 1.5 hours to calculate 4 times the
   number of random numbers per seed.  Then, you have to think about
   dictionary attacks.  Storing an entire 32 bit set of random numbers
   generated from any 32-bit PRF requires only 16GB of storage, which is
   probably about the same as your ram limit without even going into
   disk-storage.

   The other problem with a simple PRF implementation (such as random()
   on most systems) is that it's not designed to be unreversable.  IE,
   it's not designed to be cryptographically random and a random
   generator should be picked with care if you're using it for "proof"
   points of view.

   The end result of this, is that if you want to compare the speed of
   using random numbers against the speed of a real crypto function, you
   probably want to use a random number generator that won't let me
   predict the next one so easily.  You need a random number generator
   that can output a much larger set of bits (IE, returns an number much
   bigger than a 32-bit int and requires a random seed (if any) much
   bigger than a 32-bit int).

But lets say you come up with a random number generator that is
strong enough to do what you want, and we agree the OOB problem can
be solved in a way that everyone can be happy with (which I know is
one of your statements: worry about it later; I'm not sure we can
meet that goal either, but I'm even willing to worry about it later
for the time being).

IE, let us say that an architecture is found that allows an OOB or
the router itself to authoritatively say "AS A really did use random
number R a while ago".  What does the resulting algorithm really let you
say?

3) It lets you say that "AS A really did use random number R a while
   ago".  IE, if you see this:

   |------|
   | AS A |
   | R    |
   |------|
   | AS B |
   | Q    |
   |------|
   | ...  |

   Then you can say "yep, R was generated by A".

4) But.... does it really tell you that R was generated by A for that
   particular update path?  It doesn't, right?  All you know is that at
   some point in the past that AS A really did issue R.  And possibly,
   assuming you keep a running memory cache to avoid replay, that it
   hasn't been seen yet so you should trust it.  But, it may have been
   monitored/stolen from a different path instead, etc.  EG, consider
   two trust caches that neither of which has seen AS R yet.  They could
   both vouch for completely different paths advertised.

5) And in fact, there is no assurance that the random number generated
   matches anything.  Thus any of the following paths would be treated
   the same:

   |------|   |------|   |------|   |------|   |------|
   | AS A |   | AS A |   | AS C |   | AS A |   | AS B |
   | R    |   | R    |   | N    |   | R    |   | Q    |
   |------|   |------|   |------|   |------|   |------|
   | AS B |   | AS C |   | AS A |              
   | Q    |   | Q    |   | R    |              
   |------|   |------|   |------|              
   | ...  |   | ...  |   | ...  |              

   IE, any update with AS A/num=R in it will verify, but it won't matter
   if the order is added-to, reversed, deleted, dropped, etc.

   In the end, it doesn't really provide any of the protection services
   that the original cryptographically-chained algorithm provides: proof
   that the path wasn't modified.

So, as I said, I'm all for a system that is equally secure, or provides
the minimal security properties that we need at a much faster speed.
But I fail to see how your system provides any security.  At least as
you've defined it to date.  And even a 50,000x potential improvement you
claimed doesn't seem to make me happier if we're getting nothing out of
it.

Even if we had a more secure random number generator in use (which would
be likely slower than the existing one you were testing but still
faster than a ECDSA signing system), I fail to see how the designed
system with any random number generator will help out because we're
loosing all the path binding properties that BGPSEC is trying to secure
in the first place.

-- 
Wes Hardaker
SPARTA, Inc.